<commit_before>/*
 * SessionCodeSearch.cpp
 *
 * Copyright (C) 2009-12 by RStudio, Inc.
 *
 * Unless you have received this program directly from RStudio pursuant
 * to the terms of a commercial license agreement with RStudio, then
 * this program is licensed to you under the terms of version 3 of the
 * GNU Affero General Public License. This program is distributed WITHOUT
 * ANY EXPRESS OR IMPLIED WARRANTY, INCLUDING THOSE OF NON-INFRINGEMENT,
 * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Please refer to the
 * AGPL (http://www.gnu.org/licenses/agpl-3.0.txt) for more details.
 *
 */

#include "SessionCodeSearch.hpp"

#include <iostream>
#include <vector>
#include <set>

#include <boost/bind.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>
#include <boost/format.hpp>
#include <boost/regex.hpp>
#include <boost/algorithm/string/predicate.hpp>
#include <boost/algorithm/string/split.hpp>

#include <core/Error.hpp>
#include <core/Exec.hpp>
#include <core/FilePath.hpp>
#include <core/FileSerializer.hpp>
#include <core/SafeConvert.hpp>
#include <core/collection/Tree.hpp>

#include <core/r_util/RSourceIndex.hpp>

#include <core/system/FileChangeEvent.hpp>
#include <core/system/FileMonitor.hpp>

#include <r/RRoutines.hpp>
#include <r/RExec.hpp>
#include <r/RRoutines.hpp>

#include <session/SessionUserSettings.hpp>
#include <session/SessionModuleContext.hpp>
#include <session/SessionAsyncRProcess.hpp>
#include <session/projects/SessionProjects.hpp>

#include "SessionAsyncRCompletions.hpp"

#include "SessionSource.hpp"
#include "clang/DefinitionIndex.hpp"

#define CODESEARCH_DEBUG_LEVEL 0
#if CODESEARCH_DEBUG_LEVEL > 0

#define DEBUG(STRING) { \
   std::cerr << STRING << std::endl; \
}
#else

#define DEBUG(STRING)

#endif

using namespace core ;

namespace session {  
namespace modules {
namespace code_search {

namespace {


bool isGlobalFunctionNamed(const r_util::RSourceItem& sourceItem,
                           const std::string& name)
{
   return sourceItem.braceLevel() == 0 &&
          (sourceItem.type() == r_util::RSourceItem::Function ||
           sourceItem.type() == r_util::RSourceItem::Method) &&
          sourceItem.name() == name;
}

// return if we are past max results
template <typename T>
bool enforceMaxResults(std::size_t maxResults,
                        T* pNames,
                        T* pPaths,
                        bool* pMoreAvailable)
{
   if (pNames->size() >= maxResults)
   {
      *pMoreAvailable = true;
      pNames->resize(maxResults);
      pPaths->resize(maxResults);
      return true;
   }
   else
   {
      return false;
   }
}


// index entries we are managing
struct Entry
{
   explicit Entry()
   {
   }

   explicit Entry(const FileInfo& fileInfo)
      : fileInfo(fileInfo)
   {
   }
   
   Entry(const FileInfo& fileInfo,
         boost::shared_ptr<core::r_util::RSourceIndex> pIndex)
      : fileInfo(fileInfo), pIndex(pIndex)
   {
   }
   
   FileInfo fileInfo;
   boost::shared_ptr<core::r_util::RSourceIndex> pIndex;
   
   bool hasIndex() const { return pIndex.get() != NULL; }
   
   bool operator < (const Entry& other) const
   {
      return core::fileInfoPathLessThan(fileInfo, other.fileInfo);
   }
   
   bool operator == (const Entry& other) const
   {
      return fileInfo == other.fileInfo;
   }
};

void print_tree(tree<Entry> const& tr)
{
#if CODESEARCH_DEBUG_LEVEL > 0
   std::cerr << "Tree of size " << tr.size() << ".\n";
   tree<Entry>::iterator it = tr.begin();
   for (; it != tr.end(); ++it)
   {
      int depth = tr.depth(it);
      for (int i = 0; i < depth; i++)
         std::cerr << "--";
      std::cerr << (*it).fileInfo.absolutePath() << "\n";
   }
#endif
}

class EntryTree
      : public tree<Entry>
{
public:
   
   EntryTree()
   {
      // NOTE from tree.hh, line 914:
      //
      // If your program fails here you probably used 'append_child' to add the top
      // node to an empty tree. From version 1.45 the top element should be added
      // using 'insert'. See the documentation for further information, and sorry about
      // the API change.
      //
      // We work around this by explicitly inserting a root node on construction.
      Entry dummy(FileInfo("", true));
      insert(begin(), dummy);
   }
   
   // make this BOOST_FOREACH aware
   typedef iterator const_iterator;
   
   const_iterator const_begin() const
   {
      return static_cast<const_iterator>(begin());
   }
   
   const_iterator const_end() const
   {
      return static_cast<const_iterator>(end());
   }
   
   void insertEntry(const Entry& entry)
   {
      std::string absolutePath = entry.fileInfo.absolutePath();
      if (absolutePath.empty())
         return;

      DEBUG("");
      DEBUG("Begin entry insertion: '" << absolutePath << "'");
      
      // construct a tree branch from the path, with each directory forming a new node, e.g
      //
      //   foo/bar/baz
      //
      // becoming
      //
      // foo
      //     --> foo/bar
      //                  --> foo/bar/baz
      iterator parent = begin();
      DEBUG("First parent: '" << (*parent).fileInfo.absolutePath() << "'");

      std::string::size_type matchIndex = absolutePath.find('/');
      
      DEBUG("Entering directory node insertion phase");
      while (matchIndex != std::string::npos)
      {
         FileInfo path(
                  absolutePath.substr(0, matchIndex), // note: don't include the trailing '/'
                  true);
         
         Entry entry(path);
         DEBUG("Entry: '" << entry.fileInfo.absolutePath() << "'");

         if (*parent == entry)
         {
            DEBUG("- Node already exists as parent; skipping...");
         }

         else if (number_of_children(parent) == 0)
         {
            DEBUG("- Inserting new node as first child of '" << (*parent).fileInfo.absolutePath() << "'");

            iterator newItr = append_child(parent, entry);
            DEBUG("- Parent now has " << number_of_children(parent) << " children.");
            DEBUG("- Parent now has " << number_of_siblings(parent) << " siblings.");
            parent = newItr;
         }
         else
         {
            DEBUG("- Searching the children of this node");
            sibling_iterator it = parent.begin();
            sibling_iterator end = parent.end();

            for (; it != end; ++it)
            {
               DEBUG("-- Current node: '" << (*it).fileInfo.absolutePath() << "'");
               if (it->fileInfo.absolutePath() == entry.fileInfo.absolutePath())
               {
                  DEBUG("-- Found it!");
                  break;
               }
            }

            if (it == end)
            {
               DEBUG("- Adding another child to parent '" << (*parent).fileInfo.absolutePath() << "'");
               parent = append_child(parent, entry);
            }
            else
            {
               DEBUG("- Node already exists; setting parent to child (" << (*parent).fileInfo.absolutePath() << ")");
               parent = it;
            }
         }
         
         matchIndex = absolutePath.find('/', matchIndex + 1);
      }
      DEBUG("Exiting directory node insertion phase");
      
      // Now, we have the filename. We append that to the parent.
      DEBUG("Parent: '" << (*parent).fileInfo.absolutePath() << "'");
      DEBUG("Entry: '" << entry.fileInfo.absolutePath() << "'");
      if (parent.number_of_children() == 0)
      {
         DEBUG("- No children at parent node; adding child");
         parent = append_child(parent, entry);
      }

      // We check for a dummy node. If we are inserting a file
      // into a folder with just a dummy node, replace that node.
      else if (parent.number_of_children() == 1 &&
               !entry.fileInfo.isDirectory() &&
               *child(parent, 0) == dummyEntry_)
      {
         DEBUG("- Replacing dummy node");
         iterator firstChild = child(parent, 0);
         *firstChild = entry;
      }

      // Otherwise, loop through all the children and try to find
      // the node. If we don't find it, append it, otherwise no-op.
      else
      {
         sibling_iterator it = parent.begin();
         sibling_iterator end = parent.end();
         for (; it != end; ++it)
         {
            DEBUG("-- Current node: '" << (*it).fileInfo.absolutePath() << "'");
            DEBUG("-- Entry       : '" << entry.fileInfo.absolutePath() << "'");
            
            if (it->fileInfo.absolutePath() == entry.fileInfo.absolutePath())
            {
               DEBUG("- Found it!");
               break;
            }
         }

         if (it == end)
         {
            DEBUG("- Adding another child to parent");
            parent = append_child(parent, entry);
         }
         else
         {
            DEBUG("- Already has this entry; skipping");
         }
      }

      // If we just inserted a folder, we append an empty child
      // to the node. This is done to optimize lookup time.
      if (entry.fileInfo.isDirectory())
      {
         DEBUG("Inserted empty directory; adding dummy child to folder node");
         parent = append_child(parent, dummyEntry_);
      }
      DEBUG("");

      DEBUG("Tree is now:");
      print_tree(*this);
      DEBUG("");
   }

private:

   iterator find_leaf(const Entry& entry)
   {
      leaf_iterator it = begin_leaf();
      for (; is_valid(it); ++it)
         if (*it == entry)
            return it;
      return this->end();
   }

   iterator find_branch(const Entry& entry)
   {
      iterator parent = begin();
      iterator result = end();
      do_find_branch(entry, parent, &result);
      return result;
   }

   void do_find_branch(const Entry& entry,
                       iterator parent,
                       iterator* pResult)
   {
      sibling_iterator it = parent.begin();
      sibling_iterator end = parent.end();
      for (; it != end; ++it)
      {
         DEBUG("- Current branch: '" << (*it).fileInfo.absolutePath() << "'");
         if (*it == entry)
         {
            *pResult = it;
            return;
         }

         if (number_of_children(it) > 0)
         {
            DEBUG("-- Searching children of branch");
            do_find_branch(entry, it, pResult);
         }
      }
   }

public:

   iterator find(const Entry& entry)
   {
      if (entry.fileInfo.isDirectory())
         return find_branch(entry);
      else
         return find_leaf(entry);
   }

private:

   Entry dummyEntry_;
   
};

class SourceFileIndex : boost::noncopyable
{
public:
   SourceFileIndex()
      : pEntries_(new EntryTree()), indexing_(false)
   {
   }

   virtual ~SourceFileIndex()
   {
   }

   // COPYING: prohibited

   template <typename ForwardIterator>
   void enqueFiles(ForwardIterator begin, ForwardIterator end)
   {
      // add all files to the indexing queue
      using namespace core::system;
      for ( ; begin != end; ++begin)
      {
         FileChangeEvent addEvent(FileChangeEvent::FileAdded, *begin);
         indexingQueue_.push(addEvent);
      }

      // schedule indexing if necessary. perform up to 200ms of work
      // immediately and then continue in periodic 20ms chunks until
      // we are completed.
      if (!indexingQueue_.empty() && !indexing_)
      {
         indexing_ = true;

         module_context::scheduleIncrementalWork(
                           boost::posix_time::milliseconds(200),
                           boost::posix_time::milliseconds(20),
                           boost::bind(&SourceFileIndex::dequeAndIndex, this),
                           false /* allow indexing even when non-idle */);
      }
   }

   void enqueFileChange(const core::system::FileChangeEvent& event)
   {
      // add to the queue
      indexingQueue_.push(event);

      // schedule indexing if necessary. don't index anything immediately
      // (this is to defend against large numbers of files being enqued
      // at once and typing up the main thread). rather, schedule indexing
      // to occur during idle time in 20ms chunks
      if (!indexing_)
      {
         indexing_ = true;

         module_context::scheduleIncrementalWork(
                           boost::posix_time::milliseconds(20),
                           boost::bind(&SourceFileIndex::dequeAndIndex, this),
                           false /* allow indexing even when non-idle */);
      }
   }

   bool findGlobalFunction(const std::string& functionName,
                           const std::set<std::string>& excludeContexts,
                           r_util::RSourceItem* pFunctionItem)
   {
      std::vector<r_util::RSourceItem> sourceItems;
      BOOST_FOREACH(const Entry& entry, *pEntries_)
      {
         // bail if there is no index
         if (!entry.hasIndex())
            continue;

         // bail if this is an exluded context
         if (excludeContexts.find(entry.pIndex->context()) !=
             excludeContexts.end())
         {
            continue;
         }

         // scan the next index
         sourceItems.clear();
         entry.pIndex->search(
                  boost::bind(isGlobalFunctionNamed, _1, functionName),
                  std::back_inserter(sourceItems));

         // return if we got a hit
         if (sourceItems.size() > 0)
         {
            *pFunctionItem = sourceItems[0];
            return true;
         }
      }

      // none found
      return false;
   }

   void searchSource(const std::string& term,
                     std::size_t maxResults,
                     bool prefixOnly,
                     const std::set<std::string>& excludeContexts,
                     std::vector<r_util::RSourceItem>* pItems)
   {
      BOOST_FOREACH(const Entry& entry, *pEntries_)
      {
         // skip if it has no index
         if (!entry.hasIndex())
            continue;

         // bail if this is an exluded context
         if (excludeContexts.find(entry.pIndex->context()) !=
             excludeContexts.end())
         {
            continue;
         }

         // scan the next index
         entry.pIndex->search(term,
                              prefixOnly,
                              false,
                              std::back_inserter(*pItems));

         // return if we are past maxResults
         if (pItems->size() >= maxResults)
         {
            pItems->resize(maxResults);
            return;
         }
      }
   }
   
   template <typename T>
   void searchFiles(const std::string& term,
                    std::size_t maxResults,
                    bool prefixOnly,
                    bool sourceFilesOnly,
                    const FilePath& parentPath,
                    T* pNames,
                    T* pPaths,
                    bool* pMoreAvailable)
   {
      // default to no more available
      *pMoreAvailable = false;

      // create wildcard pattern if the search has a '*'
      boost::regex pattern = regex_utils::regexIfWildcardPattern(term);
      
      // get the start and end iterators -- default to all leaves
      EntryTree::leaf_iterator it = pEntries_->begin_leaf();
      
      DEBUG("Searching for node '" << parentPath.absolutePath());
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parent = pEntries_->find(parentEntry);
      if (parent != pEntries_->end())
      {
         DEBUG("Found node: '" + (*parent).fileInfo.absolutePath() + "'");
         DEBUG("Node has: '" << pEntries_->number_of_children(parent) << "' children.");
         DEBUG("Node has: '" << pEntries_->number_of_siblings(parent) << "' siblings.");

         it = parent.begin();
      }
      else
      {
         DEBUG("Failed to find node.");
         LOG_ERROR_MESSAGE("Failed to find parent node when searching index");
         return;
      }
      
      // iterate over the files
      for (; pEntries_->is_valid(it); ++it)
      {
         Entry entry = *it;
         
         DEBUG("Node: '" << (*it).fileInfo.absolutePath() << "'");
         
         // skip if it's not a source file
         if (sourceFilesOnly && !isSourceFile(entry.fileInfo))
            continue;
         
         // get file and name
         FilePath filePath(entry.fileInfo.absolutePath());
         std::string name = filePath.filename();

         // compare for match (wildcard or standard)
         bool matches = false;
         if (!pattern.empty())
         {
            matches = regex_utils::textMatches(name,
                                               pattern,
                                               prefixOnly,
                                               false);
         }
         else
         {
            if (prefixOnly)
               matches = boost::algorithm::istarts_with(name, term);
            else
            {
               // We allow the user to submit queries of the form e.g.
               // <query>:<row><column>; make sure we only take items
               // on the query up to ':'
               std::string::size_type queryEnd = term.find(":");
               if (queryEnd == std::string::npos)
                  queryEnd = term.length();

               matches = string_utils::isSubsequence(name,
                                                     term,
                                                     queryEnd,
                                                     true);
            }
         }

         // add the file if we found a match
         if (matches)
         {
            // name and aliased path
            pNames->push_back(filePath.filename());
            pPaths->push_back(module_context::createAliasedPath(filePath));

            // return if we are past max results
            if (enforceMaxResults(maxResults, pNames, pPaths, pMoreAvailable))
               return;
         }
      }
   }
   
   template <typename T>
   void searchFolders(const std::string& term,
                      const FilePath& parentPath,
                      std::size_t maxResults,
                      T* pPaths,
                      bool* pMoreAvailable)
   {
      // Find the parent node in the tree
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parentItr = pEntries_->find(parentEntry);
      if (parentItr == pEntries_->end())
      {
         std::stringstream ss;
         ss << "Expected node '" << parentPath.absolutePath() << "' in index tree but none found";
         LOG_ERROR_MESSAGE(ss.str());
         return;
      }
      
      EntryTree::iterator it = parentItr.begin();
      EntryTree::iterator end = parentItr.end();
      for (; it != end; ++it)
      {
         const FileInfo& fileInfo = (*it).fileInfo;
         if (fileInfo.isDirectory())
         {
            int lastSlashIndex = fileInfo.absolutePath().rfind('/');

            std::string fileName =
                  fileInfo.absolutePath().substr(lastSlashIndex + 1);

            bool isSubsequence =
                  string_utils::isSubsequence(fileName, term, true);

            if (isSubsequence)
            {
               pPaths->push_back(fileInfo.absolutePath());
               if (pPaths->size() >= maxResults)
               {
                  *pMoreAvailable = true;
                  return;
               }
            }

         }
      }
   }

   template <typename T>
   void searchFilesAndFolders(const std::string& term,
                              const FilePath& parentPath,
                              std::size_t maxResults,
                              T* pPaths,
                              bool* pMoreAvailable)
   {
      // Find the parent node in the tree
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parentItr = pEntries_->find(parentEntry);
      if (parentItr == pEntries_->end())
      {
         std::stringstream ss;
         ss << "Expected node '" << parentPath.absolutePath() << "' in index tree but none found";
         LOG_ERROR_MESSAGE(ss.str());
         return;
      }

      EntryTree::iterator it = parentItr.begin();
      EntryTree::iterator end = parentItr.end();
      for (; it != end; ++it)
      {
         const FileInfo& fileInfo = (*it).fileInfo;

         // Avoid dummy nodes
         if (fileInfo.empty())
            continue;

         int lastSlashIndex = fileInfo.absolutePath().rfind('/');

         std::string fileName =
               fileInfo.absolutePath().substr(lastSlashIndex + 1);

         bool isSubsequence =
               string_utils::isSubsequence(fileName, term, true);

         if (isSubsequence)
         {
            pPaths->push_back(fileInfo.absolutePath());
            if (pPaths->size() >= maxResults)
            {
               *pMoreAvailable = true;
               return;
            }
         }
      }
   }

   void clear()
   {
      indexing_ = false;
      indexingQueue_ = std::queue<core::system::FileChangeEvent>();
      pEntries_->clear();
   }

private:

   bool dequeAndIndex()
   {
      using namespace core::system;

      if (!indexingQueue_.empty())
      {
         // remove the event from the queue
         FileChangeEvent event = indexingQueue_.front();
         indexingQueue_.pop();

         // process the change
         const FileInfo& fileInfo = event.fileInfo();
         switch(event.type())
         {
            case FileChangeEvent::FileAdded:
            case FileChangeEvent::FileModified:
            {
               updateIndexEntry(fileInfo);
               break;
            }

            case FileChangeEvent::FileRemoved:
            {
               removeIndexEntry(fileInfo);
               break;
            }

            case FileChangeEvent::None:
               break;
         }
      }

      // return status
      indexing_ = !indexingQueue_.empty();
      return indexing_;
   }

   void updateIndexEntry(const FileInfo& fileInfo)
   {
      // index the source if necessary
      boost::shared_ptr<r_util::RSourceIndex> pIndex;
      if (isIndexableSourceFile(fileInfo))
      {
         // read the file
         FilePath filePath(fileInfo.absolutePath());
         std::string code;
         Error error = module_context::readAndDecodeFile(
                                 filePath,
                                 projects::projectContext().defaultEncoding(),
                                 true,
                                 &code);
         if (error)
         {
            // log if not path not found error (this can happen if the
            // file was removed after entering the indexing queue)
            if (!core::isPathNotFoundError(error))
            {
               error.addProperty("src-file", filePath.absolutePath());
               LOG_ERROR(error);
            }
            return;
         }

         // add index entry
         std::string context = module_context::createAliasedPath(filePath);
         pIndex.reset(new r_util::RSourceIndex(context, code));
      }

      // attempt to add the entry
      Entry entry(fileInfo, pIndex);
      pEntries_->insertEntry(entry);

      // kick off an update
      r_completions::AsyncRCompletions::update();
   }

   void removeIndexEntry(const FileInfo& fileInfo)
   {
      // create a fake entry with a null source index to pass to find
      Entry entry(fileInfo, boost::shared_ptr<r_util::RSourceIndex>());

      EntryTree::iterator it = pEntries_->find(entry);
      if (it != pEntries_->end())
      {
         pEntries_->erase(it);
      }
   }

   static bool isSourceFile(const FileInfo& fileInfo)
   {
      FilePath filePath(fileInfo.absolutePath());

      // screen directories
      if (!module_context::isUserFile(filePath))
         return false;

      // filter files by name and extension
      std::string ext = filePath.extensionLowerCase();
      std::string filename = filePath.filename();
      return !filePath.isDirectory() &&
              (ext == ".r" || ext == ".rnw" ||
               ext == ".rmd" || ext == ".rmarkdown" ||
               ext == ".rhtml" || ext == ".rd" ||
               ext == ".h" || ext == ".hpp" ||
               ext == ".c" || ext == ".cpp" ||
               ext == ".json" ||
               filename == "DESCRIPTION" ||
               filename == "NAMESPACE" ||
               filename == "README" ||
               filename == "NEWS" ||
               filename == "Makefile" ||
               filename == "configure" ||
               filename == "cleanup" ||
               filename == "Makevars" ||
               filePath.hasTextMimeType());
   }

   static bool isIndexableSourceFile(const FileInfo& fileInfo)
   {
      FilePath filePath(fileInfo.absolutePath());
      if (!filePath.isDirectory())
      {
         std::string lowerExtension = filePath.extensionLowerCase();
         return
               lowerExtension == ".r" ||
               lowerExtension == ".s" ||
               lowerExtension == ".q";
         
      }
      
      return false;
   }

private:
   // index entries
   boost::shared_ptr<EntryTree> pEntries_;

   // indexing queue
   bool indexing_;
   std::queue<core::system::FileChangeEvent> indexingQueue_;
};

// global source file index
SourceFileIndex s_projectIndex;

// maintain an in-memory list of R source document indexes (for fast
// code searching)
class RSourceIndexes : boost::noncopyable
{
public:
   RSourceIndexes() {}
   virtual ~RSourceIndexes() {}

   // COPYING: boost::noncopyable

   void initialize()
   {
      source_database::events().onDocUpdated.connect(
                              boost::bind(&RSourceIndexes::update, this, _1));
      source_database::events().onDocRemoved.connect(
                              boost::bind(&RSourceIndexes::remove, this, _1));
      source_database::events().onRemoveAll.connect(
                              boost::bind(&RSourceIndexes::removeAll, this));
   }

   void update(boost::shared_ptr<session::source_database::SourceDocument> pDoc)
   {
      // is this indexable? if not then bail
      if (!pDoc->canContainRCode())
         return;
      
      // index the source
      boost::shared_ptr<r_util::RSourceIndex> pIndex(
                 new r_util::RSourceIndex(pDoc->path(), pDoc->contents()));
      
      // insert it
      indexes_[pDoc->id()] = pIndex;

      // kick off an update if necessary
      r_completions::AsyncRCompletions::update();
   }
   
   boost::shared_ptr<r_util::RSourceIndex> get(const std::string& id)
   {
      return indexes_[id];<commit_msg>avoid inserting null pointers into index<commit_after>/*
 * SessionCodeSearch.cpp
 *
 * Copyright (C) 2009-12 by RStudio, Inc.
 *
 * Unless you have received this program directly from RStudio pursuant
 * to the terms of a commercial license agreement with RStudio, then
 * this program is licensed to you under the terms of version 3 of the
 * GNU Affero General Public License. This program is distributed WITHOUT
 * ANY EXPRESS OR IMPLIED WARRANTY, INCLUDING THOSE OF NON-INFRINGEMENT,
 * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Please refer to the
 * AGPL (http://www.gnu.org/licenses/agpl-3.0.txt) for more details.
 *
 */

#include "SessionCodeSearch.hpp"

#include <iostream>
#include <vector>
#include <set>

#include <boost/bind.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>
#include <boost/format.hpp>
#include <boost/regex.hpp>
#include <boost/algorithm/string/predicate.hpp>
#include <boost/algorithm/string/split.hpp>

#include <core/Error.hpp>
#include <core/Exec.hpp>
#include <core/FilePath.hpp>
#include <core/FileSerializer.hpp>
#include <core/SafeConvert.hpp>
#include <core/collection/Tree.hpp>

#include <core/r_util/RSourceIndex.hpp>

#include <core/system/FileChangeEvent.hpp>
#include <core/system/FileMonitor.hpp>

#include <r/RRoutines.hpp>
#include <r/RExec.hpp>
#include <r/RRoutines.hpp>

#include <session/SessionUserSettings.hpp>
#include <session/SessionModuleContext.hpp>
#include <session/SessionAsyncRProcess.hpp>
#include <session/projects/SessionProjects.hpp>

#include "SessionAsyncRCompletions.hpp"

#include "SessionSource.hpp"
#include "clang/DefinitionIndex.hpp"

#define CODESEARCH_DEBUG_LEVEL 0
#if CODESEARCH_DEBUG_LEVEL > 0

#define DEBUG(STRING) { \
   std::cerr << STRING << std::endl; \
}
#else

#define DEBUG(STRING)

#endif

using namespace core ;

namespace session {  
namespace modules {
namespace code_search {

namespace {


bool isGlobalFunctionNamed(const r_util::RSourceItem& sourceItem,
                           const std::string& name)
{
   return sourceItem.braceLevel() == 0 &&
          (sourceItem.type() == r_util::RSourceItem::Function ||
           sourceItem.type() == r_util::RSourceItem::Method) &&
          sourceItem.name() == name;
}

// return if we are past max results
template <typename T>
bool enforceMaxResults(std::size_t maxResults,
                        T* pNames,
                        T* pPaths,
                        bool* pMoreAvailable)
{
   if (pNames->size() >= maxResults)
   {
      *pMoreAvailable = true;
      pNames->resize(maxResults);
      pPaths->resize(maxResults);
      return true;
   }
   else
   {
      return false;
   }
}


// index entries we are managing
struct Entry
{
   explicit Entry()
   {
   }

   explicit Entry(const FileInfo& fileInfo)
      : fileInfo(fileInfo)
   {
   }
   
   Entry(const FileInfo& fileInfo,
         boost::shared_ptr<core::r_util::RSourceIndex> pIndex)
      : fileInfo(fileInfo), pIndex(pIndex)
   {
   }
   
   FileInfo fileInfo;
   boost::shared_ptr<core::r_util::RSourceIndex> pIndex;
   
   bool hasIndex() const { return pIndex.get() != NULL; }
   
   bool operator < (const Entry& other) const
   {
      return core::fileInfoPathLessThan(fileInfo, other.fileInfo);
   }
   
   bool operator == (const Entry& other) const
   {
      return fileInfo == other.fileInfo;
   }
};

void print_tree(tree<Entry> const& tr)
{
#if CODESEARCH_DEBUG_LEVEL > 0
   std::cerr << "Tree of size " << tr.size() << ".\n";
   tree<Entry>::iterator it = tr.begin();
   for (; it != tr.end(); ++it)
   {
      int depth = tr.depth(it);
      for (int i = 0; i < depth; i++)
         std::cerr << "--";
      std::cerr << (*it).fileInfo.absolutePath() << "\n";
   }
#endif
}

class EntryTree
      : public tree<Entry>
{
public:
   
   EntryTree()
   {
      // NOTE from tree.hh, line 914:
      //
      // If your program fails here you probably used 'append_child' to add the top
      // node to an empty tree. From version 1.45 the top element should be added
      // using 'insert'. See the documentation for further information, and sorry about
      // the API change.
      //
      // We work around this by explicitly inserting a root node on construction.
      Entry dummy(FileInfo("", true));
      insert(begin(), dummy);
   }
   
   // make this BOOST_FOREACH aware
   typedef iterator const_iterator;
   
   const_iterator const_begin() const
   {
      return static_cast<const_iterator>(begin());
   }
   
   const_iterator const_end() const
   {
      return static_cast<const_iterator>(end());
   }
   
   void insertEntry(const Entry& entry)
   {
      std::string absolutePath = entry.fileInfo.absolutePath();
      if (absolutePath.empty())
         return;

      DEBUG("");
      DEBUG("Begin entry insertion: '" << absolutePath << "'");
      
      // construct a tree branch from the path, with each directory forming a new node, e.g
      //
      //   foo/bar/baz
      //
      // becoming
      //
      // foo
      //     --> foo/bar
      //                  --> foo/bar/baz
      iterator parent = begin();
      DEBUG("First parent: '" << (*parent).fileInfo.absolutePath() << "'");

      std::string::size_type matchIndex = absolutePath.find('/');
      
      DEBUG("Entering directory node insertion phase");
      while (matchIndex != std::string::npos)
      {
         FileInfo path(
                  absolutePath.substr(0, matchIndex), // note: don't include the trailing '/'
                  true);
         
         Entry entry(path);
         DEBUG("Entry: '" << entry.fileInfo.absolutePath() << "'");

         if (*parent == entry)
         {
            DEBUG("- Node already exists as parent; skipping...");
         }

         else if (number_of_children(parent) == 0)
         {
            DEBUG("- Inserting new node as first child of '" << (*parent).fileInfo.absolutePath() << "'");

            iterator newItr = append_child(parent, entry);
            DEBUG("- Parent now has " << number_of_children(parent) << " children.");
            DEBUG("- Parent now has " << number_of_siblings(parent) << " siblings.");
            parent = newItr;
         }
         else
         {
            DEBUG("- Searching the children of this node");
            sibling_iterator it = parent.begin();
            sibling_iterator end = parent.end();

            for (; it != end; ++it)
            {
               DEBUG("-- Current node: '" << (*it).fileInfo.absolutePath() << "'");
               if (it->fileInfo.absolutePath() == entry.fileInfo.absolutePath())
               {
                  DEBUG("-- Found it!");
                  break;
               }
            }

            if (it == end)
            {
               DEBUG("- Adding another child to parent '" << (*parent).fileInfo.absolutePath() << "'");
               parent = append_child(parent, entry);
            }
            else
            {
               DEBUG("- Node already exists; setting parent to child (" << (*parent).fileInfo.absolutePath() << ")");
               parent = it;
            }
         }
         
         matchIndex = absolutePath.find('/', matchIndex + 1);
      }
      DEBUG("Exiting directory node insertion phase");
      
      // Now, we have the filename. We append that to the parent.
      DEBUG("Parent: '" << (*parent).fileInfo.absolutePath() << "'");
      DEBUG("Entry: '" << entry.fileInfo.absolutePath() << "'");
      if (parent.number_of_children() == 0)
      {
         DEBUG("- No children at parent node; adding child");
         parent = append_child(parent, entry);
      }

      // We check for a dummy node. If we are inserting a file
      // into a folder with just a dummy node, replace that node.
      else if (parent.number_of_children() == 1 &&
               !entry.fileInfo.isDirectory() &&
               *child(parent, 0) == dummyEntry_)
      {
         DEBUG("- Replacing dummy node");
         iterator firstChild = child(parent, 0);
         *firstChild = entry;
      }

      // Otherwise, loop through all the children and try to find
      // the node. If we don't find it, append it, otherwise no-op.
      else
      {
         sibling_iterator it = parent.begin();
         sibling_iterator end = parent.end();
         for (; it != end; ++it)
         {
            DEBUG("-- Current node: '" << (*it).fileInfo.absolutePath() << "'");
            DEBUG("-- Entry       : '" << entry.fileInfo.absolutePath() << "'");
            
            if (it->fileInfo.absolutePath() == entry.fileInfo.absolutePath())
            {
               DEBUG("- Found it!");
               break;
            }
         }

         if (it == end)
         {
            DEBUG("- Adding another child to parent");
            parent = append_child(parent, entry);
         }
         else
         {
            DEBUG("- Already has this entry; skipping");
         }
      }

      // If we just inserted a folder, we append an empty child
      // to the node. This is done to optimize lookup time.
      if (entry.fileInfo.isDirectory())
      {
         DEBUG("Inserted empty directory; adding dummy child to folder node");
         parent = append_child(parent, dummyEntry_);
      }
      DEBUG("");

      DEBUG("Tree is now:");
      print_tree(*this);
      DEBUG("");
   }

private:

   iterator find_leaf(const Entry& entry)
   {
      leaf_iterator it = begin_leaf();
      for (; is_valid(it); ++it)
         if (*it == entry)
            return it;
      return this->end();
   }

   iterator find_branch(const Entry& entry)
   {
      iterator parent = begin();
      iterator result = end();
      do_find_branch(entry, parent, &result);
      return result;
   }

   void do_find_branch(const Entry& entry,
                       iterator parent,
                       iterator* pResult)
   {
      sibling_iterator it = parent.begin();
      sibling_iterator end = parent.end();
      for (; it != end; ++it)
      {
         DEBUG("- Current branch: '" << (*it).fileInfo.absolutePath() << "'");
         if (*it == entry)
         {
            *pResult = it;
            return;
         }

         if (number_of_children(it) > 0)
         {
            DEBUG("-- Searching children of branch");
            do_find_branch(entry, it, pResult);
         }
      }
   }

public:

   iterator find(const Entry& entry)
   {
      if (entry.fileInfo.isDirectory())
         return find_branch(entry);
      else
         return find_leaf(entry);
   }

private:

   Entry dummyEntry_;
   
};

class SourceFileIndex : boost::noncopyable
{
public:
   SourceFileIndex()
      : pEntries_(new EntryTree()), indexing_(false)
   {
   }

   virtual ~SourceFileIndex()
   {
   }

   // COPYING: prohibited

   template <typename ForwardIterator>
   void enqueFiles(ForwardIterator begin, ForwardIterator end)
   {
      // add all files to the indexing queue
      using namespace core::system;
      for ( ; begin != end; ++begin)
      {
         FileChangeEvent addEvent(FileChangeEvent::FileAdded, *begin);
         indexingQueue_.push(addEvent);
      }

      // schedule indexing if necessary. perform up to 200ms of work
      // immediately and then continue in periodic 20ms chunks until
      // we are completed.
      if (!indexingQueue_.empty() && !indexing_)
      {
         indexing_ = true;

         module_context::scheduleIncrementalWork(
                           boost::posix_time::milliseconds(200),
                           boost::posix_time::milliseconds(20),
                           boost::bind(&SourceFileIndex::dequeAndIndex, this),
                           false /* allow indexing even when non-idle */);
      }
   }

   void enqueFileChange(const core::system::FileChangeEvent& event)
   {
      // add to the queue
      indexingQueue_.push(event);

      // schedule indexing if necessary. don't index anything immediately
      // (this is to defend against large numbers of files being enqued
      // at once and typing up the main thread). rather, schedule indexing
      // to occur during idle time in 20ms chunks
      if (!indexing_)
      {
         indexing_ = true;

         module_context::scheduleIncrementalWork(
                           boost::posix_time::milliseconds(20),
                           boost::bind(&SourceFileIndex::dequeAndIndex, this),
                           false /* allow indexing even when non-idle */);
      }
   }

   bool findGlobalFunction(const std::string& functionName,
                           const std::set<std::string>& excludeContexts,
                           r_util::RSourceItem* pFunctionItem)
   {
      std::vector<r_util::RSourceItem> sourceItems;
      BOOST_FOREACH(const Entry& entry, *pEntries_)
      {
         // bail if there is no index
         if (!entry.hasIndex())
            continue;

         // bail if this is an exluded context
         if (excludeContexts.find(entry.pIndex->context()) !=
             excludeContexts.end())
         {
            continue;
         }

         // scan the next index
         sourceItems.clear();
         entry.pIndex->search(
                  boost::bind(isGlobalFunctionNamed, _1, functionName),
                  std::back_inserter(sourceItems));

         // return if we got a hit
         if (sourceItems.size() > 0)
         {
            *pFunctionItem = sourceItems[0];
            return true;
         }
      }

      // none found
      return false;
   }

   void searchSource(const std::string& term,
                     std::size_t maxResults,
                     bool prefixOnly,
                     const std::set<std::string>& excludeContexts,
                     std::vector<r_util::RSourceItem>* pItems)
   {
      BOOST_FOREACH(const Entry& entry, *pEntries_)
      {
         // skip if it has no index
         if (!entry.hasIndex())
            continue;

         // bail if this is an exluded context
         if (excludeContexts.find(entry.pIndex->context()) !=
             excludeContexts.end())
         {
            continue;
         }

         // scan the next index
         entry.pIndex->search(term,
                              prefixOnly,
                              false,
                              std::back_inserter(*pItems));

         // return if we are past maxResults
         if (pItems->size() >= maxResults)
         {
            pItems->resize(maxResults);
            return;
         }
      }
   }
   
   template <typename T>
   void searchFiles(const std::string& term,
                    std::size_t maxResults,
                    bool prefixOnly,
                    bool sourceFilesOnly,
                    const FilePath& parentPath,
                    T* pNames,
                    T* pPaths,
                    bool* pMoreAvailable)
   {
      // default to no more available
      *pMoreAvailable = false;

      // create wildcard pattern if the search has a '*'
      boost::regex pattern = regex_utils::regexIfWildcardPattern(term);
      
      // get the start and end iterators -- default to all leaves
      EntryTree::leaf_iterator it = pEntries_->begin_leaf();
      
      DEBUG("Searching for node '" << parentPath.absolutePath());
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parent = pEntries_->find(parentEntry);
      if (parent != pEntries_->end())
      {
         DEBUG("Found node: '" + (*parent).fileInfo.absolutePath() + "'");
         DEBUG("Node has: '" << pEntries_->number_of_children(parent) << "' children.");
         DEBUG("Node has: '" << pEntries_->number_of_siblings(parent) << "' siblings.");

         it = parent.begin();
      }
      else
      {
         DEBUG("Failed to find node.");
         LOG_ERROR_MESSAGE("Failed to find parent node when searching index");
         return;
      }
      
      // iterate over the files
      for (; pEntries_->is_valid(it); ++it)
      {
         Entry entry = *it;
         
         DEBUG("Node: '" << (*it).fileInfo.absolutePath() << "'");
         
         // skip if it's not a source file
         if (sourceFilesOnly && !isSourceFile(entry.fileInfo))
            continue;
         
         // get file and name
         FilePath filePath(entry.fileInfo.absolutePath());
         std::string name = filePath.filename();

         // compare for match (wildcard or standard)
         bool matches = false;
         if (!pattern.empty())
         {
            matches = regex_utils::textMatches(name,
                                               pattern,
                                               prefixOnly,
                                               false);
         }
         else
         {
            if (prefixOnly)
               matches = boost::algorithm::istarts_with(name, term);
            else
            {
               // We allow the user to submit queries of the form e.g.
               // <query>:<row><column>; make sure we only take items
               // on the query up to ':'
               std::string::size_type queryEnd = term.find(":");
               if (queryEnd == std::string::npos)
                  queryEnd = term.length();

               matches = string_utils::isSubsequence(name,
                                                     term,
                                                     queryEnd,
                                                     true);
            }
         }

         // add the file if we found a match
         if (matches)
         {
            // name and aliased path
            pNames->push_back(filePath.filename());
            pPaths->push_back(module_context::createAliasedPath(filePath));

            // return if we are past max results
            if (enforceMaxResults(maxResults, pNames, pPaths, pMoreAvailable))
               return;
         }
      }
   }
   
   template <typename T>
   void searchFolders(const std::string& term,
                      const FilePath& parentPath,
                      std::size_t maxResults,
                      T* pPaths,
                      bool* pMoreAvailable)
   {
      // Find the parent node in the tree
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parentItr = pEntries_->find(parentEntry);
      if (parentItr == pEntries_->end())
      {
         std::stringstream ss;
         ss << "Expected node '" << parentPath.absolutePath() << "' in index tree but none found";
         LOG_ERROR_MESSAGE(ss.str());
         return;
      }
      
      EntryTree::iterator it = parentItr.begin();
      EntryTree::iterator end = parentItr.end();
      for (; it != end; ++it)
      {
         const FileInfo& fileInfo = (*it).fileInfo;
         if (fileInfo.isDirectory())
         {
            int lastSlashIndex = fileInfo.absolutePath().rfind('/');

            std::string fileName =
                  fileInfo.absolutePath().substr(lastSlashIndex + 1);

            bool isSubsequence =
                  string_utils::isSubsequence(fileName, term, true);

            if (isSubsequence)
            {
               pPaths->push_back(fileInfo.absolutePath());
               if (pPaths->size() >= maxResults)
               {
                  *pMoreAvailable = true;
                  return;
               }
            }

         }
      }
   }

   template <typename T>
   void searchFilesAndFolders(const std::string& term,
                              const FilePath& parentPath,
                              std::size_t maxResults,
                              T* pPaths,
                              bool* pMoreAvailable)
   {
      // Find the parent node in the tree
      Entry parentEntry(core::toFileInfo(parentPath));
      EntryTree::iterator parentItr = pEntries_->find(parentEntry);
      if (parentItr == pEntries_->end())
      {
         std::stringstream ss;
         ss << "Expected node '" << parentPath.absolutePath() << "' in index tree but none found";
         LOG_ERROR_MESSAGE(ss.str());
         return;
      }

      EntryTree::iterator it = parentItr.begin();
      EntryTree::iterator end = parentItr.end();
      for (; it != end; ++it)
      {
         const FileInfo& fileInfo = (*it).fileInfo;

         // Avoid dummy nodes
         if (fileInfo.empty())
            continue;

         int lastSlashIndex = fileInfo.absolutePath().rfind('/');

         std::string fileName =
               fileInfo.absolutePath().substr(lastSlashIndex + 1);

         bool isSubsequence =
               string_utils::isSubsequence(fileName, term, true);

         if (isSubsequence)
         {
            pPaths->push_back(fileInfo.absolutePath());
            if (pPaths->size() >= maxResults)
            {
               *pMoreAvailable = true;
               return;
            }
         }
      }
   }

   void clear()
   {
      indexing_ = false;
      indexingQueue_ = std::queue<core::system::FileChangeEvent>();
      pEntries_->clear();
   }

private:

   bool dequeAndIndex()
   {
      using namespace core::system;

      if (!indexingQueue_.empty())
      {
         // remove the event from the queue
         FileChangeEvent event = indexingQueue_.front();
         indexingQueue_.pop();

         // process the change
         const FileInfo& fileInfo = event.fileInfo();
         switch(event.type())
         {
            case FileChangeEvent::FileAdded:
            case FileChangeEvent::FileModified:
            {
               updateIndexEntry(fileInfo);
               break;
            }

            case FileChangeEvent::FileRemoved:
            {
               removeIndexEntry(fileInfo);
               break;
            }

            case FileChangeEvent::None:
               break;
         }
      }

      // return status
      indexing_ = !indexingQueue_.empty();
      return indexing_;
   }

   void updateIndexEntry(const FileInfo& fileInfo)
   {
      // index the source if necessary
      boost::shared_ptr<r_util::RSourceIndex> pIndex;
      if (isIndexableSourceFile(fileInfo))
      {
         // read the file
         FilePath filePath(fileInfo.absolutePath());
         std::string code;
         Error error = module_context::readAndDecodeFile(
                                 filePath,
                                 projects::projectContext().defaultEncoding(),
                                 true,
                                 &code);
         if (error)
         {
            // log if not path not found error (this can happen if the
            // file was removed after entering the indexing queue)
            if (!core::isPathNotFoundError(error))
            {
               error.addProperty("src-file", filePath.absolutePath());
               LOG_ERROR(error);
            }
            return;
         }

         // add index entry
         std::string context = module_context::createAliasedPath(filePath);
         pIndex.reset(new r_util::RSourceIndex(context, code));
      }

      // attempt to add the entry
      Entry entry(fileInfo, pIndex);
      pEntries_->insertEntry(entry);

      // kick off an update
      r_completions::AsyncRCompletions::update();
   }

   void removeIndexEntry(const FileInfo& fileInfo)
   {
      // create a fake entry with a null source index to pass to find
      Entry entry(fileInfo, boost::shared_ptr<r_util::RSourceIndex>());

      EntryTree::iterator it = pEntries_->find(entry);
      if (it != pEntries_->end())
      {
         pEntries_->erase(it);
      }
   }

   static bool isSourceFile(const FileInfo& fileInfo)
   {
      FilePath filePath(fileInfo.absolutePath());

      // screen directories
      if (!module_context::isUserFile(filePath))
         return false;

      // filter files by name and extension
      std::string ext = filePath.extensionLowerCase();
      std::string filename = filePath.filename();
      return !filePath.isDirectory() &&
              (ext == ".r" || ext == ".rnw" ||
               ext == ".rmd" || ext == ".rmarkdown" ||
               ext == ".rhtml" || ext == ".rd" ||
               ext == ".h" || ext == ".hpp" ||
               ext == ".c" || ext == ".cpp" ||
               ext == ".json" ||
               filename == "DESCRIPTION" ||
               filename == "NAMESPACE" ||
               filename == "README" ||
               filename == "NEWS" ||
               filename == "Makefile" ||
               filename == "configure" ||
               filename == "cleanup" ||
               filename == "Makevars" ||
               filePath.hasTextMimeType());
   }

   static bool isIndexableSourceFile(const FileInfo& fileInfo)
   {
      FilePath filePath(fileInfo.absolutePath());
      if (!filePath.isDirectory())
      {
         std::string lowerExtension = filePath.extensionLowerCase();
         return
               lowerExtension == ".r" ||
               lowerExtension == ".s" ||
               lowerExtension == ".q";
         
      }
      
      return false;
   }

private:
   // index entries
   boost::shared_ptr<EntryTree> pEntries_;

   // indexing queue
   bool indexing_;
   std::queue<core::system::FileChangeEvent> indexingQueue_;
};

// global source file index
SourceFileIndex s_projectIndex;

// maintain an in-memory list of R source document indexes (for fast
// code searching)
class RSourceIndexes : boost::noncopyable
{
public:
   RSourceIndexes() {}
   virtual ~RSourceIndexes() {}

   // COPYING: boost::noncopyable

   void initialize()
   {
      source_database::events().onDocUpdated.connect(
                              boost::bind(&RSourceIndexes::update, this, _1));
      source_database::events().onDocRemoved.connect(
                              boost::bind(&RSourceIndexes::remove, this, _1));
      source_database::events().onRemoveAll.connect(
                              boost::bind(&RSourceIndexes::removeAll, this));
   }

   void update(boost::shared_ptr<session::source_database::SourceDocument> pDoc)
   {
      // is this indexable? if not then bail
      if (!pDoc->canContainRCode())
         return;
      
      // index the source
      boost::shared_ptr<r_util::RSourceIndex> pIndex(
                 new r_util::RSourceIndex(pDoc->path(), pDoc->contents()));
      
      // insert it
      indexes_[pDoc->id()] = pIndex;

      // kick off an update if necessary
      r_completions::AsyncRCompletions::update();
   }
   
   boost::shared_ptr<r_util::RSourceIndex> get(const std::string& id)
   {
      if (indexes_.find(id) != indexes_.end())
         return indexes_[id];
      return boost::shared_ptr<r_util::RSourceIndex>();
{'fraction_non_alphanumeric': 0.11753755899441551, 'fraction_numerical': 0.0018426940939773988, 'mean_word_length': 1.7799905911870786, 'pattern_counts': {'":': 2, '<': 310, '<?xml version=': 0, '>': 204, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '519670', 'n_tokens_mistral': 14441, 'n_tokens_neox': 14072, 'n_words': 3573}