Introduce line editor library.

[pcc]

Summary

This library will be used by clang-query. I can imagine LLDB becoming another
client of this library, so I think LLVM is a sensible place for it to live.
It wraps libedit, and adds tab completion support.

The code is loosely based on the line editor bits in LLDB, with a few
improvements:

• Polymorphism for retrieving the list of tab completions, based on the concept pattern from the new pass manager.
• Tab completion doesn't corrupt terminal output if the input covers multiple lines. Unfortunately this can only be done in a truly horrible way, as far as I can tell. But since the alternative is to implement our own line editor (which I don't think LLVM should be in the business of doing, at least for now) I think it may be acceptable.
• Includes a fallback for the case where the user doesn't have libedit installed.

Note that this uses C stdio, mainly because libedit also uses C stdio.

[silvas]

Why not base it on https://github.com/antirez/linenoise?

[pcc]

I did consider linenoise. My thoughts are that if we were to implement our own line editor, linenoise would be a good starting point. Unfortunately, it does not implement the style of tab completion (show all completions, rather than cycle through each completion) that I think clients such as clang-query would really benefit from, mainly by being able to teach users the matcher syntax as they use it by showing type information for each completing matcher. While libedit does not natively support tab completion, it gives you just enough control to implement it in the way that we need.

[klimek]

Before doing a more in-depth review of the code, i'd want Doug's OK for this to go in in general...

[doug.gregor]

This seems generally useful to me. Looking forward to it growing some functionality beyond a libedit wrapper ;)

[pcc]

Manuel: ping.

[klimek]

lib/LineEditor/LineEditor.cpp

36 ↗

(On Diff #5602)

Perhaps "Action"? Completion seems to be clear from the context.

43–53 ↗

(On Diff #5602)

I'd pull that out into a method.

55 ↗

(On Diff #5602)

That needs an explanation - why is the action kind "ShowCompletions" if we have no common prefix, and "Insert" otherwise?

79 ↗

(On Diff #5602)

I'd propose to have an interface, have two .cc files where the libedit one is only compiled if HAVE_LIBEDIT, and allow the main function of a tool to select one and inject it into the edit flow (while the tool that does the edit flow is free to have a default instantiation based on what is available).

[pcc]

Address review comments.

lib/LineEditor/LineEditor.cpp

36 ↗

(On Diff #5602)

Well, you could have other actions associated with a line editor, like the action when a bound key is pressed or when a line is entered. So I think this name makes things clear.

43–53 ↗

(On Diff #5602)

Done.

55 ↗

(On Diff #5602)

Added.

79 ↗

(On Diff #5602)

So this would allow clients to select the fgets implementation even if libedit is available, right? Is there any use case for such behaviour?

Also, in the long term I think we should have our own line editor implementation here, at which point there will be only one implementation.

[klimek]

lg

lib/LineEditor/LineEditor.cpp

36 ↗

(On Diff #5602)

Oh, I didn't mean the class name, I mean the local variable name (basically s/CA/Action/). I think "Action" is in this context easier to understand than CA. I strongly oppose initializations unless they are very very commonly used (an example is SM used in clang; but even there it quickly becomes a problem if it's not consistent, which it is not ;)

55 ↗

(On Diff #5602)

Ah, now it all makes sense - thanks!

79 ↗

(On Diff #5602)

To me having an interface would be simpler here - I agree that's a trade-off though, and I don't think it needs to block the patch from landing.

[pcc]

Closed by commit rL200595 (authored by @pcc).

[pcc]

lib/LineEditor/LineEditor.cpp

36 ↗

(On Diff #5602)

Makes sense - renamed.

llvm/trunk/autoconf/configure.ac

AC_ARG_ENABLE(terminfo,AS_HELP_STRING(
   [Query the terminfo database if available (default is YES)]),
   [case "$enableval" in
     yes) llvm_cv_enable_terminfo="yes" ;;
     no)  llvm_cv_enable_terminfo="no"  ;;
     *) AC_MSG_ERROR([Invalid setting for --enable-terminfo. Use "yes" or "no"]) ;;
   esac],
   llvm_cv_enable_terminfo="yes")
 
+dnl --enable-libedit: check whether the user wants to turn off libedit.
+AC_ARG_ENABLE(libedit,AS_HELP_STRING(
+  [--enable-libedit],
+  [Use libedit if available (default is YES)]),
+  [case "$enableval" in
+    yes) llvm_cv_enable_libedit="yes" ;;
+    no)  llvm_cv_enable_libedit="no"  ;;
+    *) AC_MSG_ERROR([Invalid setting for --enable-libedit. Use "yes" or "no"]) ;;
+  esac],
+  llvm_cv_enable_libedit="yes")
+
 dnl --enable-libffi : check whether the user wants to turn off libffi:
 AC_ARG_ENABLE(libffi,AS_HELP_STRING(
   --enable-libffi,[Check for the presence of libffi (default is NO)]),
   [case "$enableval" in
     yes) llvm_cv_enable_libffi="yes" ;;
     no)  llvm_cv_enable_libffi="no"  ;;
     *) AC_MSG_ERROR([Invalid setting for --enable-libffi. Use "yes" or "no"]) ;;
   esac],

 dnl The curses library is optional; used for querying terminal info
 if test "$llvm_cv_enable_terminfo" = "yes" ; then
   dnl We need the has_color functionality in curses for it to be useful.
   AC_SEARCH_LIBS(setupterm,tinfo terminfo curses ncurses ncursesw,
                  AC_DEFINE([HAVE_TERMINFO],[1],
                            [Define if the setupterm() function is supported this platform.]))
 fi
 
+dnl The libedit library is optional; used by lib/LineEditor
+if test "$llvm_cv_enable_libedit" = "yes" ; then
+  AC_SEARCH_LIBS(el_init,edit,
+                 AC_DEFINE([HAVE_LIBEDIT],[1],
+                           [Define if libedit is available on this platform.]))
+fi
+
 dnl libffi is optional; used to call external functions from the interpreter
 if test "$llvm_cv_enable_libffi" = "yes" ; then
   AC_SEARCH_LIBS(ffi_call,ffi,AC_DEFINE([HAVE_FFI_CALL],[1],
                  [Define if libffi is available on this platform.]),
                  AC_MSG_ERROR([libffi not found - configure without --enable-libffi to compile without it]))
 fi
 
 dnl mallinfo is optional; the code can compile (minus features) without it

llvm/trunk/cmake/config-ix.cmake

if( NOT PURE_WINDOWS )
   endif()
   check_library_exists(dl dlopen "" HAVE_LIBDL)
   check_library_exists(rt clock_gettime "" HAVE_LIBRT)
   if (LLVM_ENABLE_ZLIB)
     check_library_exists(z compress2 "" HAVE_LIBZ)
   else()
     set(HAVE_LIBZ 0)
   endif()
+  check_library_exists(edit el_init "" HAVE_LIBEDIT)
   if(LLVM_ENABLE_TERMINFO)
     set(HAVE_TERMINFO 0)
     foreach(library tinfo terminfo curses ncurses ncursesw)
       string(TOUPPER ${library} library_suffix)
       check_library_exists(${library} setupterm "" HAVE_TERMINFO_${library_suffix})
       if(HAVE_TERMINFO_${library_suffix})
         set(HAVE_TERMINFO 1)
         set(TERMINFO_LIBS "${library}")

llvm/trunk/configure

--enable-targets        Build specific host targets: all or
                           (default=all)
   --enable-experimental-targets
                           Build experimental host targets: disable or
                           target1,target2,... (default=disable)
   --enable-bindings       Build specific language bindings:
                           all,auto,none,{binding-name} (default=auto)
   --enable-terminfo       Query the terminfo database if available (default is
                           YES)
+  --enable-libedit        Use libedit if available (default is YES)
   --enable-libffi         Check for the presence of libffi (default is NO)
   --enable-ltdl-install   install libltdl
 
 Optional Packages:
   --with-PACKAGE[=ARG]    use PACKAGE [ARG=yes]
   --without-PACKAGE       do not use PACKAGE (same as --with-PACKAGE=no)
   --with-optimize-option  Select the compiler options to use for optimized
                           builds

 echo "$as_me: error: Invalid setting for --enable-terminfo. Use \"yes\" or \"no\"" >&2;}
    { (exit 1); exit 1; }; } ;;
   esac
 else
   llvm_cv_enable_terminfo="yes"
 fi
 
 
+# Check whether --enable-libedit was given.
+if test "${enable_libedit+set}" = set; then
+  enableval=$enable_libedit; case "$enableval" in
+    yes) llvm_cv_enable_libedit="yes" ;;
+    no)  llvm_cv_enable_libedit="no"  ;;
+    *) { { echo "$as_me:$LINENO: error: Invalid setting for --enable-libedit. Use \"yes\" or \"no\"" >&5
+echo "$as_me: error: Invalid setting for --enable-libedit. Use \"yes\" or \"no\"" >&2;}
+   { (exit 1); exit 1; }; } ;;
+  esac
+else
+  llvm_cv_enable_libedit="yes"
+fi
+
+
 # Check whether --enable-libffi was given.
 if test "${enable_libffi+set}" = set; then
   enableval=$enable_libffi; case "$enableval" in
     yes) llvm_cv_enable_libffi="yes" ;;
     no)  llvm_cv_enable_libffi="no"  ;;
     *) { { echo "$as_me:$LINENO: error: Invalid setting for --enable-libffi. Use \"yes\" or \"no\"" >&5
 echo "$as_me: error: Invalid setting for --enable-libffi. Use \"yes\" or \"no\"" >&2;}
    { (exit 1); exit 1; }; } ;;
libltdl_cv_need_uscore=unknown
           save_LIBS="$LIBS"
           LIBS="$LIBS $LIBADD_DL"
     if test "$cross_compiling" = yes; then :
   libltdl_cv_need_uscore=cross
 else
   lt_dlunknown=0; lt_dlno_uscore=1; lt_dlneed_uscore=2
   lt_status=$lt_dlunknown
   cat > conftest.$ac_ext <<EOF
-#line 10666 "configure"
+#line 10681 "configure"
 #include "confdefs.h"
 
 #if HAVE_DLFCN_H
 #include <dlfcn.h>
 #endif
 
 #include <stdio.h>
 

 cat >>confdefs.h <<\_ACEOF
 #define HAVE_TERMINFO 1
 _ACEOF
 
 fi
 
 fi
 
+if test "$llvm_cv_enable_libedit" = "yes" ; then
+  { echo "$as_me:$LINENO: checking for library containing el_init" >&5
+echo $ECHO_N "checking for library containing el_init... $ECHO_C" >&6; }
+if test "${ac_cv_search_el_init+set}" = set; then
+  echo $ECHO_N "(cached) $ECHO_C" >&6
+else
+  ac_func_search_save_LIBS=$LIBS
+cat >conftest.$ac_ext <<_ACEOF
+/* confdefs.h.  */
+_ACEOF
+cat confdefs.h >>conftest.$ac_ext
+cat >>conftest.$ac_ext <<_ACEOF
+/* end confdefs.h.  */
+
+/* Override any GCC internal prototype to avoid an error.
+   Use char because int might match the return type of a GCC
+   builtin and then its argument prototype would still apply.  */
+#ifdef __cplusplus
+extern "C"
+#endif
+char el_init ();
+int
+main ()
+{
+return el_init ();
+  ;
+  return 0;
+}
+_ACEOF
+for ac_lib in '' edit; do
+  if test -z "$ac_lib"; then
+    ac_res="none required"
+  else
+    ac_res=-l$ac_lib
+    LIBS="-l$ac_lib  $ac_func_search_save_LIBS"
+  fi
+  rm -f conftest.$ac_objext conftest$ac_exeext
+if { (ac_try="$ac_link"
+case "(($ac_try" in
+  *\"* | *\`* | *\\*) ac_try_echo=\$ac_try;;
+  *) ac_try_echo=$ac_try;;
+esac
+eval "echo \"\$as_me:$LINENO: $ac_try_echo\"") >&5
+  (eval "$ac_link") 2>conftest.er1
+  ac_status=$?
+  grep -v '^ *+' conftest.er1 >conftest.err
+  rm -f conftest.er1
+  cat conftest.err >&5
+  echo "$as_me:$LINENO: \$? = $ac_status" >&5
+  (exit $ac_status); } &&
+   { ac_try='test -z "$ac_c_werror_flag" || test ! -s conftest.err'
+  { (case "(($ac_try" in
+  *\"* | *\`* | *\\*) ac_try_echo=\$ac_try;;
+  *) ac_try_echo=$ac_try;;
+esac
+eval "echo \"\$as_me:$LINENO: $ac_try_echo\"") >&5
+  (eval "$ac_try") 2>&5
+  ac_status=$?
+  echo "$as_me:$LINENO: \$? = $ac_status" >&5
+  (exit $ac_status); }; } &&
+   { ac_try='test -s conftest$ac_exeext'
+  { (case "(($ac_try" in
+  *\"* | *\`* | *\\*) ac_try_echo=\$ac_try;;
+  *) ac_try_echo=$ac_try;;
+esac
+eval "echo \"\$as_me:$LINENO: $ac_try_echo\"") >&5
+  (eval "$ac_try") 2>&5
+  ac_status=$?
+  echo "$as_me:$LINENO: \$? = $ac_status" >&5
+  (exit $ac_status); }; }; then
+  ac_cv_search_el_init=$ac_res
+else
+  echo "$as_me: failed program was:" >&5
+sed 's/^/| /' conftest.$ac_ext >&5
+
+
+fi
+
+rm -f core conftest.err conftest.$ac_objext \
+      conftest$ac_exeext
+  if test "${ac_cv_search_el_init+set}" = set; then
+  break
+fi
+done
+if test "${ac_cv_search_el_init+set}" = set; then
+  :
+else
+  ac_cv_search_el_init=no
+fi
+rm conftest.$ac_ext
+LIBS=$ac_func_search_save_LIBS
+fi
+{ echo "$as_me:$LINENO: result: $ac_cv_search_el_init" >&5
+echo "${ECHO_T}$ac_cv_search_el_init" >&6; }
+ac_res=$ac_cv_search_el_init
+if test "$ac_res" != no; then
+  test "$ac_res" = "none required" || LIBS="$ac_res $LIBS"
+
+cat >>confdefs.h <<\_ACEOF
+#define HAVE_LIBEDIT 1
+_ACEOF
+
+fi
+
+fi
+
 if test "$llvm_cv_enable_libffi" = "yes" ; then
   { echo "$as_me:$LINENO: checking for library containing ffi_call" >&5
 echo $ECHO_N "checking for library containing ffi_call... $ECHO_C" >&6; }
 if test "${ac_cv_search_ffi_call+set}" = set; then
   echo $ECHO_N "(cached) $ECHO_C" >&6
 else
   ac_func_search_save_LIBS=$LIBS
 cat >conftest.$ac_ext <<_ACEOF

llvm/trunk/include/llvm/Config/config.h.cmake

 #cmakedefine HAVE_LIBSHELL32 ${HAVE_LIBSHELL32}
 
 /* Define to 1 if you have the `udis86' library (-ludis86). */
 #undef HAVE_LIBUDIS86
 
 /* Define to 1 if you have the 'z' library (-lz). */
 #cmakedefine HAVE_LIBZ ${HAVE_LIBZ}
 
+/* Define to 1 if you have the 'edit' library (-ledit). */
+#cmakedefine HAVE_LIBEDIT ${HAVE_LIBEDIT}
+
 /* Define to 1 if you have the <limits.h> header file. */
 #cmakedefine HAVE_LIMITS_H ${HAVE_LIMITS_H}
 
 /* Define if you can use -rdynamic. */
 #define HAVE_LINK_EXPORT_DYNAMIC 1
 
 /* Define if you can use -Wl,-R. to pass -R. to the linker, in order to add
    the current directory to the dynamic linker search path. */

llvm/trunk/include/llvm/Config/config.h.in

 #undef HAVE_ISNAN_IN_CMATH
 
 /* Set to 1 if the isnan function is found in <math.h> */
 #undef HAVE_ISNAN_IN_MATH_H
 
 /* Define if you have the libdl library or equivalent. */
 #undef HAVE_LIBDL
 
+/* Define if libedit is available on this platform. */
+#undef HAVE_LIBEDIT
+
 /* Define to 1 if you have the `imagehlp' library (-limagehlp). */
 #undef HAVE_LIBIMAGEHLP
 
 /* Define to 1 if you have the `m' library (-lm). */
 #undef HAVE_LIBM
 
 /* Define to 1 if you have the `psapi' library (-lpsapi). */
 #undef HAVE_LIBPSAPI

llvm/trunk/include/llvm/LineEditor/LineEditor.h

+//===-- llvm/LineEditor/LineEditor.h - line editor --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LINEEDITOR_LINEEDITOR_H
+#define LLVM_LINEEDITOR_LINEEDITOR_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/OwningPtr.h"
+#include <stdio.h>
+#include <string>
+#include <vector>
+
+namespace llvm {
+
+class LineEditor {
+public:
+  /// Create a LineEditor object.
+  ///
+  /// \param ProgName The name of the current program. Used to form a default
+  /// prompt.
+  /// \param HistoryPath Path to the file in which to store history data, if
+  /// possible.
+  /// \param In The input stream used by the editor.
+  /// \param Out The output stream used by the editor.
+  /// \param Err The error stream used by the editor.
+  LineEditor(StringRef ProgName, StringRef HistoryPath = "", FILE *In = stdin,
+             FILE *Out = stdout, FILE *Err = stderr);
+  ~LineEditor();
+
+  /// Reads a line.
+  ///
+  /// \return The line, or llvm::Optional<std::string>() on EOF.
+  llvm::Optional<std::string> readLine() const;
+
+  void saveHistory();
+  void loadHistory();
+
+  static std::string getDefaultHistoryPath(StringRef ProgName);
+
+  /// The action to perform upon a completion request.
+  struct CompletionAction {
+    enum ActionKind {
+      /// Insert Text at the cursor position.
+      AK_Insert,
+      /// Show Completions, or beep if the list is empty.
+      AK_ShowCompletions
+    };
+
+    ActionKind Kind;
+
+    /// The text to insert.
+    std::string Text;
+
+    /// The list of completions to show.
+    std::vector<std::string> Completions;
+  };
+
+  /// A possible completion at a given cursor position.
+  struct Completion {
+    Completion() {}
+    Completion(const std::string &TypedText, const std::string &DisplayText)
+        : TypedText(TypedText), DisplayText(DisplayText) {}
+
+    /// The text to insert. If the user has already input some of the
+    /// completion, this should only include the rest of the text.
+    std::string TypedText;
+
+    /// A description of this completion. This may be the completion itself, or
+    /// maybe a summary of its type or arguments.
+    std::string DisplayText;
+  };
+
+  /// Set the completer for this LineEditor. A completer is a function object
+  /// which takes arguments of type StringRef (the string to complete) and
+  /// size_t (the zero-based cursor position in the StringRef) and returns a
+  /// CompletionAction.
+  template <typename T> void setCompleter(T Comp) {
+    Completer.reset(new CompleterModel<T>(Comp));
+  }
+
+  /// Set the completer for this LineEditor to the given list completer.
+  /// A list completer is a function object which takes arguments of type
+  /// StringRef (the string to complete) and size_t (the zero-based cursor
+  /// position in the StringRef) and returns a std::vector<Completion>.
+  template <typename T> void setListCompleter(T Comp) {
+    Completer.reset(new ListCompleterModel<T>(Comp));
+  }
+
+  /// Use the current completer to produce a CompletionAction for the given
+  /// completion request. If the current completer is a list completer, this
+  /// will return an AK_Insert CompletionAction if each completion has a common
+  /// prefix, or an AK_ShowCompletions CompletionAction otherwise.
+  ///
+  /// \param Buffer The string to complete
+  /// \param Pos The zero-based cursor position in the StringRef
+  CompletionAction getCompletionAction(StringRef Buffer, size_t Pos) const;
+
+  const std::string &getPrompt() const { return Prompt; }
+  void setPrompt(const std::string &P) { Prompt = P; }
+
+  // Public so callbacks in LineEditor.cpp can use it.
+  struct InternalData;
+
+private:
+  std::string Prompt;
+  std::string HistoryPath;
+  OwningPtr<InternalData> Data;
+
+  struct CompleterConcept {
+    virtual ~CompleterConcept();
+    virtual CompletionAction complete(StringRef Buffer, size_t Pos) const = 0;
+  };
+
+  struct ListCompleterConcept : CompleterConcept {
+    ~ListCompleterConcept();
+    CompletionAction complete(StringRef Buffer, size_t Pos) const;
+    static std::string getCommonPrefix(const std::vector<Completion> &Comps);
+    virtual std::vector<Completion> getCompletions(StringRef Buffer,
+                                                   size_t Pos) const = 0;
+  };
+
+  template <typename T>
+  struct CompleterModel : CompleterConcept {
+    CompleterModel(T Value) : Value(Value) {}
+    CompletionAction complete(StringRef Buffer, size_t Pos) const {
+      return Value(Buffer, Pos);
+    }
+    T Value;
+  };
+
+  template <typename T>
+  struct ListCompleterModel : ListCompleterConcept {
+    ListCompleterModel(T Value) : Value(Value) {}
+    std::vector<Completion> getCompletions(StringRef Buffer, size_t Pos) const {
+      return Value(Buffer, Pos);
+    }
+    T Value;
+  };
+
+  llvm::OwningPtr<const CompleterConcept> Completer;
+};
+
+}
+
+#endif

llvm/trunk/lib/CMakeLists.txt

 add_subdirectory(LTO)
 add_subdirectory(MC)
 add_subdirectory(Object)
 add_subdirectory(Option)
 add_subdirectory(DebugInfo)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(Target)
 add_subdirectory(AsmParser)
+add_subdirectory(LineEditor)

llvm/trunk/lib/LLVMBuild.txt

 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [common]
-subdirectories = Analysis AsmParser Bitcode CodeGen DebugInfo ExecutionEngine Linker IR IRReader LTO MC Object Option Support TableGen Target Transforms
+subdirectories = Analysis AsmParser Bitcode CodeGen DebugInfo ExecutionEngine LineEditor Linker IR IRReader LTO MC Object Option Support TableGen Target Transforms
 
 [component_0]
 type = Group
 name = Libraries
 parent = $ROOT

llvm/trunk/lib/LineEditor/CMakeLists.txt

+add_llvm_library(LLVMLineEditor
+  LineEditor.cpp
+  )
+
+if(HAVE_LIBEDIT)
+  target_link_libraries(LLVMLineEditor edit)
+endif()

llvm/trunk/lib/LineEditor/LLVMBuild.txt

+;===- ./lib/LineEditor/LLVMBuild.txt ---------------------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = LineEditor
+parent = Libraries
+required_libraries = Support

llvm/trunk/lib/LineEditor/LineEditor.cpp

+//===-- LineEditor.cpp - line editor --------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/LineEditor/LineEditor.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Config/config.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+#include <stdio.h>
+#ifdef HAVE_LIBEDIT
+#include <histedit.h>
+#endif
+
+using namespace llvm;
+
+std::string LineEditor::getDefaultHistoryPath(StringRef ProgName) {
+  SmallString<32> Path;
+  if (sys::path::home_directory(Path)) {
+    sys::path::append(Path, "." + ProgName + "-history");
+    return Path.str();
+  }
+  return std::string();
+}
+
+LineEditor::CompleterConcept::~CompleterConcept() {}
+LineEditor::ListCompleterConcept::~ListCompleterConcept() {}
+
+std::string LineEditor::ListCompleterConcept::getCommonPrefix(
+    const std::vector<Completion> &Comps) {
+  assert(!Comps.empty());
+
+  std::string CommonPrefix = Comps[0].TypedText;
+  for (std::vector<Completion>::const_iterator I = Comps.begin() + 1,
+                                               E = Comps.end();
+       I != E; ++I) {
+    size_t Len = std::min(CommonPrefix.size(), I->TypedText.size());
+    size_t CommonLen = 0;
+    for (; CommonLen != Len; ++CommonLen) {
+      if (CommonPrefix[CommonLen] != I->TypedText[CommonLen])
+        break;
+    }
+    CommonPrefix.resize(CommonLen);
+  }
+  return CommonPrefix;
+}
+
+LineEditor::CompletionAction
+LineEditor::ListCompleterConcept::complete(StringRef Buffer, size_t Pos) const {
+  CompletionAction Action;
+  std::vector<Completion> Comps = getCompletions(Buffer, Pos);
+  if (Comps.empty()) {
+    Action.Kind = CompletionAction::AK_ShowCompletions;
+    return Action;
+  }
+
+  std::string CommonPrefix = getCommonPrefix(Comps);
+
+  // If the common prefix is non-empty we can simply insert it. If there is a
+  // single completion, this will insert the full completion. If there is more
+  // than one, this might be enough information to jog the user's memory but if
+  // not the user can also hit tab again to see the completions because the
+  // common prefix will then be empty.
+  if (CommonPrefix.empty()) {
+    Action.Kind = CompletionAction::AK_ShowCompletions;
+    for (std::vector<Completion>::iterator I = Comps.begin(), E = Comps.end();
+         I != E; ++I)
+      Action.Completions.push_back(I->DisplayText);
+  } else {
+    Action.Kind = CompletionAction::AK_Insert;
+    Action.Text = CommonPrefix;
+  }
+
+  return Action;
+}
+
+LineEditor::CompletionAction LineEditor::getCompletionAction(StringRef Buffer,
+                                                             size_t Pos) const {
+  if (!Completer) {
+    CompletionAction Action;
+    Action.Kind = CompletionAction::AK_ShowCompletions;
+    return Action;
+  }
+
+  return Completer->complete(Buffer, Pos);
+}
+
+#ifdef HAVE_LIBEDIT
+
+// libedit-based implementation.
+
+struct LineEditor::InternalData {
+  LineEditor *LE;
+
+  History *Hist;
+  EditLine *EL;
+
+  unsigned PrevCount;
+  std::string ContinuationOutput;
+};
+
+static const char *ElGetPromptFn(EditLine *EL) {
+  LineEditor::InternalData *Data;
+  if (el_get(EL, EL_CLIENTDATA, &Data) == 0)
+    return Data->LE->getPrompt().c_str();
+  return "> ";
+}
+
+// Handles tab completion.
+//
+// This function is really horrible. But since the alternative is to get into
+// the line editor business, here we are.
+static unsigned char ElCompletionFn(EditLine *EL, int ch) {
+  LineEditor::InternalData *Data;
+  if (el_get(EL, EL_CLIENTDATA, &Data) == 0) {
+    if (!Data->ContinuationOutput.empty()) {
+      // This is the continuation of the AK_ShowCompletions branch below.
+      FILE *Out;
+      if (::el_get(EL, EL_GETFP, 1, &Out) != 0)
+        return CC_ERROR;
+
+      // Print the required output (see below).
+      ::fwrite(Data->ContinuationOutput.c_str(),
+               Data->ContinuationOutput.size(), 1, Out);
+
+      // Push a sequence of Ctrl-B characters to move the cursor back to its
+      // original position.
+      std::string Prevs(Data->PrevCount, '\02');
+      ::el_push(EL, (char *)Prevs.c_str());
+
+      Data->ContinuationOutput.clear();
+
+      return CC_REFRESH;
+    }
+
+    const LineInfo *LI = ::el_line(EL);
+    LineEditor::CompletionAction Action = Data->LE->getCompletionAction(
+        StringRef(LI->buffer, LI->lastchar - LI->buffer),
+        LI->cursor - LI->buffer);
+    switch (Action.Kind) {
+    case LineEditor::CompletionAction::AK_Insert:
+      ::el_insertstr(EL, Action.Text.c_str());
+      return CC_REFRESH;
+
+    case LineEditor::CompletionAction::AK_ShowCompletions:
+      if (Action.Completions.empty()) {
+        return CC_REFRESH_BEEP;
+      } else {
+        // Push a Ctrl-E and a tab. The Ctrl-E causes libedit to move the cursor
+        // to the end of the line, so that when we emit a newline we will be on
+        // a new blank line. The tab causes libedit to call this function again
+        // after moving the cursor. There doesn't seem to be anything we can do
+        // from here to cause libedit to move the cursor immediately. This will
+        // break horribly if the user has rebound their keys, so for now we do
+        // not permit user rebinding.
+        ::el_push(EL, (char *)"\05\t");
+
+        // This assembles the output for the continuation block above.
+        raw_string_ostream OS(Data->ContinuationOutput);
+
+        // Move cursor to a blank line.
+        OS << "\n";
+
+        // Emit the completions.
+        for (std::vector<std::string>::iterator I = Action.Completions.begin(),
+                                                E = Action.Completions.end();
+             I != E; ++I) {
+          OS << *I << "\n";
+        }
+
+        // Fool libedit into thinking nothing has changed. Reprint its prompt
+        // and the user input. Note that the cursor will remain at the end of
+        // the line after this.
+        OS << Data->LE->getPrompt()
+           << StringRef(LI->buffer, LI->lastchar - LI->buffer);
+
+        // This is the number of characters we need to tell libedit to go back:
+        // the distance between end of line and the original cursor position.
+        Data->PrevCount = LI->lastchar - LI->cursor;
+
+        return CC_REFRESH;
+      }
+    }
+  } else {
+    return CC_ERROR;
+  }
+}
+
+LineEditor::LineEditor(StringRef ProgName, StringRef HistoryPath, FILE *In,
+                       FILE *Out, FILE *Err)
+    : Prompt((ProgName + "> ").str()), HistoryPath(HistoryPath),
+      Data(new InternalData) {
+  if (HistoryPath.empty())
+    this->HistoryPath = getDefaultHistoryPath(ProgName);
+
+  Data->LE = this;
+
+  Data->Hist = ::history_init();
+  assert(Data->Hist);
+
+  Data->EL = ::el_init(ProgName.str().c_str(), In, Out, Err);
+  assert(Data->EL);
+
+  ::el_set(Data->EL, EL_PROMPT, ElGetPromptFn);
+  ::el_set(Data->EL, EL_EDITOR, "emacs");
+  ::el_set(Data->EL, EL_HIST, history, Data->Hist);
+  ::el_set(Data->EL, EL_ADDFN, "tab_complete", "Tab completion function",
+           ElCompletionFn);
+  ::el_set(Data->EL, EL_BIND, "\t", "tab_complete", NULL);
+  ::el_set(Data->EL, EL_BIND, "^r", "em-inc-search-prev",
+           NULL); // Cycle through backwards search, entering string
+  ::el_set(Data->EL, EL_BIND, "^w", "ed-delete-prev-word",
+           NULL); // Delete previous word, behave like bash does.
+  ::el_set(Data->EL, EL_BIND, "\033[3~", "ed-delete-next-char",
+           NULL); // Fix the delete key.
+  ::el_set(Data->EL, EL_CLIENTDATA, Data.get());
+
+  HistEvent HE;
+  ::history(Data->Hist, &HE, H_SETSIZE, 800);
+  ::history(Data->Hist, &HE, H_SETUNIQUE, 1);
+  loadHistory();
+}
+
+LineEditor::~LineEditor() {
+  saveHistory();
+
+  FILE *Out;
+  if (::el_get(Data->EL, EL_GETFP, 1, &Out) != 0)
+    Out = 0;
+
+  ::history_end(Data->Hist);
+  ::el_end(Data->EL);
+
+  if (Out)
+    ::fwrite("\n", 1, 1, Out);
+}
+
+void LineEditor::saveHistory() {
+  if (!HistoryPath.empty()) {
+    HistEvent HE;
+    ::history(Data->Hist, &HE, H_SAVE, HistoryPath.c_str());
+  }
+}
+
+void LineEditor::loadHistory() {
+  if (!HistoryPath.empty()) {
+    HistEvent HE;
+    ::history(Data->Hist, &HE, H_LOAD, HistoryPath.c_str());
+  }
+}
+
+Optional<std::string> LineEditor::readLine() const {
+  // Call el_gets to prompt the user and read the user's input.
+  int LineLen = 0;
+  const char *Line = ::el_gets(Data->EL, &LineLen);
+
+  // Either of these may mean end-of-file.
+  if (!Line || LineLen == 0)
+    return Optional<std::string>();
+
+  // Strip any newlines off the end of the string.
+  while (LineLen > 0 &&
+         (Line[LineLen - 1] == '\n' || Line[LineLen - 1] == '\r'))
+    --LineLen;
+
+  HistEvent HE;
+  if (LineLen > 0)
+    ::history(Data->Hist, &HE, H_ENTER, Line);
+
+  return std::string(Line, LineLen);
+}
+
+#else
+
+// Simple fgets-based implementation.
+
+struct LineEditor::InternalData {
+  FILE *In;
+  FILE *Out;
+};
+
+LineEditor::LineEditor(StringRef ProgName, StringRef HistoryPath, FILE *In,
+                       FILE *Out, FILE *Err)
+    : Prompt((ProgName + "> ").str()), Data(new InternalData) {
+  Data->In = In;
+  Data->Out = Out;
+}
+
+LineEditor::~LineEditor() {
+  ::fwrite("\n", 1, 1, Data->Out);
+}
+
+void LineEditor::saveHistory() {}
+void LineEditor::loadHistory() {}
+
+Optional<std::string> LineEditor::readLine() const {
+  ::fprintf(Data->Out, "%s", Prompt.c_str());
+
+  std::string Line;
+  do {
+    char Buf[64];
+    char *Res = ::fgets(Buf, sizeof(Buf), Data->In);
+    if (!Res) {
+      if (Line.empty())
+        return Optional<std::string>();
+      else
+        return Line;
+    }
+    Line.append(Buf);
+  } while (Line.empty() ||
+           (Line[Line.size() - 1] != '\n' && Line[Line.size() - 1] != '\r'));
+
+  while (!Line.empty() &&
+         (Line[Line.size() - 1] == '\n' || Line[Line.size() - 1] == '\r'))
+    Line.resize(Line.size() - 1);
+
+  return Line;
+}
+
+#endif

llvm/trunk/lib/LineEditor/Makefile

+##===- lib/LineEditor/Makefile -----------------------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+LIBRARYNAME = LLVMLineEditor
+BUILD_ARCHIVE := 1
+
+include $(LEVEL)/Makefile.common
+

llvm/trunk/lib/Makefile

 ##===- lib/Makefile ----------------------------------------*- Makefile -*-===##
 #
 #                     The LLVM Compiler Infrastructure
 #
 # This file is distributed under the University of Illinois Open Source
 # License. See LICENSE.TXT for details.
 #
 ##===----------------------------------------------------------------------===##
 LEVEL = ..
 
 include $(LEVEL)/Makefile.config
 
 PARALLEL_DIRS := IR AsmParser Bitcode Analysis Transforms CodeGen Target \
                  ExecutionEngine Linker LTO MC Object Option DebugInfo   \
-                 IRReader
+                 IRReader LineEditor
 
 include $(LEVEL)/Makefile.common

llvm/trunk/unittests/CMakeLists.txt

 add_custom_target(UnitTests)
 set_target_properties(UnitTests PROPERTIES FOLDER "Tests")
 
 function(add_llvm_unittest test_dirname)
   add_unittest(UnitTests ${test_dirname} ${ARGN})
 endfunction()
 
 add_subdirectory(ADT)
 add_subdirectory(Analysis)
 add_subdirectory(Bitcode)
 add_subdirectory(CodeGen)
 add_subdirectory(DebugInfo)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(IR)
+add_subdirectory(LineEditor)
 add_subdirectory(MC)
 add_subdirectory(Object)
 add_subdirectory(Option)
 add_subdirectory(Support)
 add_subdirectory(Transforms)

llvm/trunk/unittests/LineEditor/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  LineEditor
+  )
+
+add_llvm_unittest(LineEditorTests
+  LineEditor.cpp
+  )

llvm/trunk/unittests/LineEditor/LineEditor.cpp

+//===-- LineEditor.cpp ----------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/LineEditor/LineEditor.h"
+#include "llvm/Support/Path.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+class LineEditorTest : public testing::Test {
+public:
+  SmallString<64> HistPath;
+  LineEditor *LE;
+
+  LineEditorTest() {
+    init();
+  }
+
+  void init() {
+    sys::fs::createTemporaryFile("temp", "history", HistPath);
+    ASSERT_FALSE(HistPath.empty());
+    LE = new LineEditor("test", HistPath);
+  }
+
+  ~LineEditorTest() {
+    delete LE;
+    sys::fs::remove(HistPath.str());
+  }
+};
+
+TEST_F(LineEditorTest, HistorySaveLoad) {
+  LE->saveHistory();
+  LE->loadHistory();
+}
+
+struct TestListCompleter {
+  std::vector<LineEditor::Completion> Completions;
+
+  TestListCompleter(const std::vector<LineEditor::Completion> &Completions)
+      : Completions(Completions) {}
+
+  std::vector<LineEditor::Completion> operator()(StringRef Buffer,
+                                                 size_t Pos) const {
+    EXPECT_TRUE(Buffer.empty());
+    EXPECT_EQ(0u, Pos);
+    return Completions;
+  }
+};
+
+TEST_F(LineEditorTest, ListCompleters) {
+  std::vector<LineEditor::Completion> Comps;
+
+  Comps.push_back(LineEditor::Completion("foo", "int foo()"));
+  LE->setListCompleter(TestListCompleter(Comps));
+  LineEditor::CompletionAction CA = LE->getCompletionAction("", 0);
+  EXPECT_EQ(LineEditor::CompletionAction::AK_Insert, CA.Kind);
+  EXPECT_EQ("foo", CA.Text);
+
+  Comps.push_back(LineEditor::Completion("bar", "int bar()"));
+  LE->setListCompleter(TestListCompleter(Comps));
+  CA = LE->getCompletionAction("", 0);
+  EXPECT_EQ(LineEditor::CompletionAction::AK_ShowCompletions, CA.Kind);
+  ASSERT_EQ(2u, CA.Completions.size());
+  ASSERT_EQ("int foo()", CA.Completions[0]);
+  ASSERT_EQ("int bar()", CA.Completions[1]);
+
+  Comps.clear();
+  Comps.push_back(LineEditor::Completion("fee", "int fee()"));
+  Comps.push_back(LineEditor::Completion("fi", "int fi()"));
+  Comps.push_back(LineEditor::Completion("foe", "int foe()"));
+  Comps.push_back(LineEditor::Completion("fum", "int fum()"));
+  LE->setListCompleter(TestListCompleter(Comps));
+  CA = LE->getCompletionAction("", 0);
+  EXPECT_EQ(LineEditor::CompletionAction::AK_Insert, CA.Kind);
+  EXPECT_EQ("f", CA.Text);
+}

llvm/trunk/unittests/LineEditor/Makefile

+##===- unittests/LineEditor/Makefile -----------------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+TESTNAME = LineEditor
+LINK_COMPONENTS := lineeditor
+
+include $(LEVEL)/Makefile.config
+include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest

llvm/trunk/unittests/Makefile

 ##===- unittests/Makefile ----------------------------------*- Makefile -*-===##
 #
 #                     The LLVM Compiler Infrastructure
 #
 # This file is distributed under the University of Illinois Open Source
 # License. See LICENSE.TXT for details.
 #
 ##===----------------------------------------------------------------------===##
 
 LEVEL = ..
 
-PARALLEL_DIRS = ADT Analysis Bitcode CodeGen DebugInfo \
-    ExecutionEngine IR Linker MC Object Option Support Transforms
+PARALLEL_DIRS = ADT Analysis Bitcode CodeGen DebugInfo ExecutionEngine IR \
+    LineEditor Linker MC Object Option Support Transforms
 
 include $(LEVEL)/Makefile.config
 include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest
 
 clean::
   $(Verb) $(RM) -f *Tests