[LLDB][GUI] Add source file searcher

[OmarEmaraDev]

Summary

This patch adds a new searcher to find source files and a new shortcut
to the sources window (F) that changes the displayed file to the one
selected in the searcher dialog. The added searcher displays the
smallest unique path that identifies the file for a more compact and
friendly representation.

This patch is not sufficient for the workflow outlined, because the
sources window was not made for that purpose and would need refactoring
to support arbitrary files that are independent of a symbol context. An
attempt at refactoring proved a bit involved, so it will be done later
in a separate patch.

[OmarEmaraDev]

An example typical workflow for navigating to a file and adding a breakpoint.

[OmarEmaraDev]

@clayborg Did you take a look at this?

[clayborg]

Sorry for the delay, yes this looks good.

lldb/source/Core/IOHandlerCursesGUI.cpp

 public:
   SearcherDelegate() {}
 
   virtual ~SearcherDelegate() = default;
 
   virtual int GetNumberOfMatches() = 0;
 
   // Get the string that will be displayed for the match at the input index.
-  virtual const std::string &GetMatchTextAtIndex(int index) = 0;
+  virtual std::string GetMatchTextAtIndex(int index) = 0;
 
   // Update the matches of the search. This is executed every time the text
   // field handles an event.
   virtual void UpdateMatches(const std::string &text) = 0;
 
   // Execute the user callback given the index of some match. This is executed
   // once the user selects a match.
   virtual void ExecuteCallback(int match_index) = 0;
public:
 
   CommonCompletionSearcherDelegate(Debugger &debugger, uint32_t completion_mask,
                                    CallbackType callback)
       : m_debugger(debugger), m_completion_mask(completion_mask),
         m_callback(callback) {}
 
   int GetNumberOfMatches() override { return m_matches.GetSize(); }
 
-  const std::string &GetMatchTextAtIndex(int index) override {
+  std::string GetMatchTextAtIndex(int index) override {
     return m_matches[index];
   }
 
   void UpdateMatches(const std::string &text) override {
     CompletionResult result;
     CompletionRequest request(text.c_str(), text.size(), result);
     CommandCompletions::InvokeCommonCompletionCallbacks(
         m_debugger.GetCommandInterpreter(), m_completion_mask, request,
protected:
   // A compound mask from CommonCompletionTypes.
   uint32_t m_completion_mask;
   // A callback to execute once the user selects a match. The match is passed to
   // the callback as a string.
   CallbackType m_callback;
   StringList m_matches;
 };
 
+class SourceFileSearcherDelegate : public SearcherDelegate, public Searcher {
+public:
+  typedef std::function<void(const FileSpec &)> CallbackType;
+
+  SourceFileSearcherDelegate(Debugger &debugger, CallbackType callback)
+      : m_debugger(debugger), m_callback(callback) {}
+
+  int GetNumberOfMatches() override { return m_matches.GetSize(); }
+
+  bool IsFileNameUnique(const FileSpec &file) {
+    auto is_file_name_equal = [&file](const FileSpec &f) {
+      return (&f != &file) && file.FileEquals(f);
+    };
+
+    FileSpecList::const_iterator begin = m_matches.begin();
+    FileSpecList::const_iterator end = m_matches.end();
+    return find_if(begin, end, is_file_name_equal) == end;
+  }
+
+  // Find the smallest unique path assuming the file name is not unique.
+  // We start from the file name and progressively prepend the last remaining
+  // path component until we find a path that is unique across matches, that is,
+  // none of the matched files' paths ends with it.
+  std::string FindSmallestUniquePath(const FileSpec &file) {
+    FileSpec unique_spec(file.GetFilename().GetStringRef());
+    FileSpec remaining = file.CopyByRemovingLastPathComponent();
+
+    while (true) {
+      ConstString last_componenet = remaining.GetLastPathComponent();
+      unique_spec.PrependPathComponent(last_componenet.GetStringRef());
+      std::string unique_path = unique_spec.GetPath();
+
+      auto ends_with_path = [&file, &unique_path](const FileSpec &f) {
+        std::string path = f.GetPath();
+        return (&f != &file) && StringRef(path).endswith(unique_path);
+      };
+
+      FileSpecList::const_iterator begin = m_matches.begin();
+      FileSpecList::const_iterator end = m_matches.end();
+      if (find_if(begin, end, ends_with_path) == end)
+        return unique_path;
+
+      if (!remaining.RemoveLastPathComponent()) {
+        // We will return before we reach this point, but break in any case.
+        break;
+      }
+    }
+
+    return unique_spec.GetPath();
+  }
+
+  std::string GetMatchTextAtIndex(int index) override {
+    const FileSpec &file = m_matches.GetFileSpecAtIndex(index);
+
+    // If no other matched file have the same name, then only return the name.
+    if (IsFileNameUnique(file))
+      return file.GetFilename().GetStringRef().str();
+
+    // If another matched file have the same name, then return the smallest
+    // unique path of the file across matches.
+    return FindSmallestUniquePath(file);
+  }
+
+  void UpdateMatches(const std::string &text) override {
+    m_matches.Clear();
+    m_file_name_partial = text;
+    if (text.empty())
+      return;
+    TargetSP target = m_debugger.GetSelectedTarget();
+    SearchFilterForUnconstrainedSearches filter(target);
+    filter.Search(*this);
+  }
+
+  void ExecuteCallback(int match_index) override {
+    m_callback(m_matches.GetFileSpecAtIndex(match_index));
+  }
+
+  // Searcher implementation.
+
+  lldb::SearchDepth GetDepth() override { return lldb::eSearchDepthCompUnit; }
+
+  Searcher::CallbackReturn SearchCallback(SearchFilter &filter,
+                                          SymbolContext &context,
+                                          Address *addr) override {
+    if (context.comp_unit == nullptr)
+      return Searcher::eCallbackReturnContinue;
+
+    const FileSpec primary_file = context.comp_unit->GetPrimaryFile();
+    StringRef file_name = primary_file.GetFilename().GetStringRef();
+
+    if (!file_name.startswith(m_file_name_partial))
+      return Searcher::eCallbackReturnContinue;
+
+    m_matches.Append(context.comp_unit->GetPrimaryFile());
+
+    return Searcher::eCallbackReturnContinue;
+  }
+
+protected:
+  Debugger &m_debugger;
+  // A callback to execute once the user selects a match. The match is passed to
+  // the callback as a FileSpec.
+  CallbackType m_callback;
+  // A list of file specs corresponding to source files that were matches.
+  FileSpecList m_matches;
+  // A partial file name to use in the search. This should be set in
+  // UpdateMatches before executing the search.
+  std::string m_file_name_partial;
+};
+
 ////////
 // Menus
 ////////
 
 class MenuDelegate {
 public:
   virtual ~MenuDelegate() = default;
 
static curses::KeyHelp g_source_view_key_help[] = {
         {'N', "Step over (single instruction)"},
         {'f', "Step out (finish)"},
         {'s', "Step in (source line)"},
         {'S', "Step in (single instruction)"},
         {'u', "Frame up"},
         {'d', "Frame down"},
         {',', "Page up"},
         {'.', "Page down"},
+        {'F', "Find source file"},
         {'\0', nullptr}};
     return g_source_view_key_help;
   }
 
   bool WindowDelegateDraw(Window &window, bool force) override {
     ExecutionContext exe_ctx =
         m_debugger.GetCommandInterpreter().GetExecutionContext();
     Process *process = exe_ctx.GetProcessPtr();
case 'd': // 'd' == frame down
         else if (c == 'd' && frame_idx > 0)
           --frame_idx;
         if (thread->SetSelectedFrameByIndex(frame_idx, true))
           exe_ctx.SetFrameSP(thread->GetSelectedFrame());
       }
     }
       return eKeyHandled;
 
+    case 'F':
+      LaunchSourceFileSearcher(window);
+      return eKeyHandled;
+
     case 'h':
       window.CreateHelpSubwindow();
       return eKeyHandled;
 
     default:
       break;
     }
     return eKeyNotHandled;
   }
 
+  void LaunchSourceFileSearcher(Window &window) {
+    SourceFileSearcherDelegate::CallbackType callback =
+        [this](const FileSpec &match) { ChangeFile(match); };
+    SearcherDelegateSP searcher_delegate_sp = SearcherDelegateSP(
+        new SourceFileSearcherDelegate(m_debugger, callback));
+    Rect bounds = window.GetParent()->GetCenteredRect(80, 22);
+    WindowSP new_window_sp =
+        window.GetParent()->CreateSubWindow("Find Source File", bounds, true);
+    new_window_sp->SetDelegate(
+        WindowDelegateSP(new SearcherWindowDelegate(searcher_delegate_sp)));
+  }
+
+  void ChangeFile(const FileSpec &file) {
+    m_selected_line = 0;
+    m_file_sp = m_debugger.GetSourceManager().GetFile(file);
+  }
+
   void ToggleBreakpointOnSelectedLine() {
     ExecutionContext exe_ctx =
         m_debugger.GetCommandInterpreter().GetExecutionContext();
     if (!exe_ctx.HasTargetScope())
       return;
     if (GetNumSourceLines() > 0) {
       // Source file breakpoint.
       BreakpointList &bp_list = exe_ctx.GetTargetRef().GetBreakpointList();