Merge topic 'perf-source-lookup'

3b95ab56 Performance: Improve efficiency of source file lookup in cmMakefile
e0188803 cmMakefile: Drop unused method
fe1e811b cmSourceFileLocation: Drop unnecessary copy-assignment operator

Acked-by: Kitware Robot <kwrobot@kitware.com>
Merge-request: !1154

5 files changed, 66 insertions, 23 deletions

diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index e51cfcc..c96b892 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -3082,9 +3082,18 @@ void cmMakefile::SetArgcArgv(const std::vector<std::string>& args)
 cmSourceFile* cmMakefile::GetSource(const std::string& sourceName) const
 {
   cmSourceFileLocation sfl(this, sourceName);
-  for (cmSourceFile* sf : this->SourceFiles) {
-    if (sf->Matches(sfl)) {
-      return sf;
+
+#if defined(_WIN32) || defined(__APPLE__)
+  const auto& name = cmSystemTools::LowerCase(sfl.GetName());
+#else
+  const auto& name = sfl.GetName();
+#endif
+  auto sfsi = this->SourceFileSearchIndex.find(name);
+  if (sfsi != this->SourceFileSearchIndex.end()) {
+    for (auto sf : sfsi->second) {
+      if (sf->Matches(sfl)) {
+        return sf;
+      }
     }
   }
   return nullptr;
@@ -3098,6 +3107,41 @@ cmSourceFile* cmMakefile::CreateSource(const std::string& sourceName,
     sf->SetProperty("GENERATED", "1");
   }
   this->SourceFiles.push_back(sf);
+
+  auto name = sf->GetLocation().GetName();
+#if defined(_WIN32) || defined(__APPLE__)
+  name = cmSystemTools::LowerCase(name);
+#endif
+
+  // For a file in the form "a.b.c" add the cmSourceFile to the index
+  // at "a.b.c", "a.b" and "a".
+  auto partial = name;
+  while (true) {
+    this->SourceFileSearchIndex[partial].insert(sf);
+    auto i = partial.rfind('.');
+    if (i == std::string::npos) {
+      break;
+    }
+    partial = partial.substr(0, i);
+  }
+
+  if (sf->GetLocation().ExtensionIsAmbiguous()) {
+    // For an ambiguous extension also add the various "known"
+    // extensions to the original filename.
+
+    const auto& srcExts = this->GetCMakeInstance()->GetSourceExtensions();
+    for (const auto& ext : srcExts) {
+      auto name_ext = name + "." + cmSystemTools::LowerCase(ext);
+      this->SourceFileSearchIndex[name_ext].insert(sf);
+    }
+
+    const auto& hdrExts = this->GetCMakeInstance()->GetHeaderExtensions();
+    for (const auto& ext : hdrExts) {
+      auto name_ext = name + "." + cmSystemTools::LowerCase(ext);
+      this->SourceFileSearchIndex[name_ext].insert(sf);
+    }
+  }
+
   return sf;
 }
 
diff --git a/Source/cmMakefile.h b/Source/cmMakefile.h
index 398604d..2cae659 100644
--- a/Source/cmMakefile.h
+++ b/Source/cmMakefile.h
@@ -13,6 +13,7 @@
 #include <stddef.h>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "cmAlgorithms.h"
@@ -623,7 +624,6 @@ public:
   {
     return this->SourceFiles;
   }
-  std::vector<cmSourceFile*>& GetSourceFiles() { return this->SourceFiles; }
 
   /**
    * Is there a source file that has the provided source file as an output?
@@ -809,7 +809,17 @@ protected:
   // libraries, classes, and executables
   mutable cmTargets Targets;
   std::map<std::string, std::string> AliasTargets;
+
   std::vector<cmSourceFile*> SourceFiles;
+  // Because cmSourceFile names are compared in a fuzzy way (see
+  // cmSourceFileLocation::Match()) we can't have a straight mapping from
+  // filename to cmSourceFile.  To make lookups more efficient we store the
+  // Name portion of the cmSourceFileLocation and then compare on the list of
+  // cmSourceFiles that might match that name.  Note that on platforms which
+  // have a case-insensitive filesystem we store the key in all lowercase.
+  typedef std::unordered_set<cmSourceFile*> SourceFileSet;
+  typedef std::unordered_map<std::string, SourceFileSet> SourceFileMap;
+  SourceFileMap SourceFileSearchIndex;
 
   // Tests
   std::map<std::string, cmTest*> Tests;
diff --git a/Source/cmSourceFileLocation.cxx b/Source/cmSourceFileLocation.cxx
index 727adeb..4f337f2 100644
--- a/Source/cmSourceFileLocation.cxx
+++ b/Source/cmSourceFileLocation.cxx
@@ -28,21 +28,6 @@ cmSourceFileLocation::cmSourceFileLocation(const cmSourceFileLocation& loc)
   this->Name = loc.Name;
 }
 
-cmSourceFileLocation& cmSourceFileLocation::operator=(
-  const cmSourceFileLocation& loc)
-{
-  if (this == &loc) {
-    return *this;
-  }
-  this->Makefile = loc.Makefile;
-  this->AmbiguousDirectory = loc.AmbiguousDirectory;
-  this->AmbiguousExtension = loc.AmbiguousExtension;
-  this->Directory = loc.Directory;
-  this->Name = loc.Name;
-  this->UpdateExtension(this->Name);
-  return *this;
-}
-
 cmSourceFileLocation::cmSourceFileLocation(cmMakefile const* mf,
                                            const std::string& name)
   : Makefile(mf)
diff --git a/Source/cmSourceFileLocation.h b/Source/cmSourceFileLocation.h
index 6dbc2da..fb5b330 100644
--- a/Source/cmSourceFileLocation.h
+++ b/Source/cmSourceFileLocation.h
@@ -29,7 +29,6 @@ public:
   cmSourceFileLocation(cmMakefile const* mf, const std::string& name);
   cmSourceFileLocation();
   cmSourceFileLocation(const cmSourceFileLocation& loc);
-  cmSourceFileLocation& operator=(const cmSourceFileLocation& loc);
 
   /**
    * Return whether the given source file location could refers to the
@@ -79,7 +78,7 @@ public:
    */
   cmMakefile const* GetMakefile() const { return this->Makefile; }
 private:
-  cmMakefile const* Makefile;
+  cmMakefile const* const Makefile;
   bool AmbiguousDirectory;
   bool AmbiguousExtension;
   std::string Directory;
@@ -90,6 +89,9 @@ private:
   // Update the location with additional knowledge.
   void Update(cmSourceFileLocation const& loc);
   void UpdateExtension(const std::string& name);
+
+  cmSourceFileLocation& operator=(const cmSourceFileLocation& loc)
+    CM_EQ_DELETE;
 };
 
 #endif
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index c26d49a..49b0664 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -5,6 +5,7 @@
 #include "cmsys/RegularExpression.hxx"
 #include <algorithm>
 #include <assert.h>
+#include <iterator>
 #include <map>
 #include <set>
 #include <sstream>
@@ -592,8 +593,9 @@ public:
   {
     std::vector<std::string> files;
     cmSystemTools::ExpandListArgument(entry, files);
-    std::vector<cmSourceFileLocation> locations(files.size());
-    std::transform(files.begin(), files.end(), locations.begin(),
+    std::vector<cmSourceFileLocation> locations;
+    locations.reserve(files.size());
+    std::transform(files.begin(), files.end(), std::back_inserter(locations),
                    CreateLocation(this->Needle.GetMakefile()));
 
     return std::find_if(locations.begin(), locations.end(),