Performance: Improve efficiency of source file lookup in cmMakefile

This reintroduces the change from commit v3.10.0-rc1~69^2 (Performance:
Improve efficiency of source file lookup in cmMakefile, 2017-08-17) with
some corrections.  The original was rolled back by commit
v3.10.0-rc1~52^2~1 (Revert "Performance: ...", 2017-09-25) due to
incompatibilities found.  The rollback was followed-up by addition of a
test for the offending case, and this revision passes the test.

8 files changed, 84 insertions, 40 deletions

diff --git a/Source/cmAuxSourceDirectoryCommand.cxx b/Source/cmAuxSourceDirectoryCommand.cxx
index 847a416..fcdc632 100644
--- a/Source/cmAuxSourceDirectoryCommand.cxx
+++ b/Source/cmAuxSourceDirectoryCommand.cxx
@@ -54,10 +54,8 @@ bool cmAuxSourceDirectoryCommand::InitialPass(
         std::string ext = file.substr(dotpos + 1);
         std::string base = file.substr(0, dotpos);
         // Process only source files
-        std::vector<std::string> const& srcExts =
-          this->Makefile->GetCMakeInstance()->GetSourceExtensions();
-        if (!base.empty() &&
-            std::find(srcExts.begin(), srcExts.end(), ext) != srcExts.end()) {
+        auto cm = this->Makefile->GetCMakeInstance();
+        if (!base.empty() && cm->IsSourceExtension(ext)) {
           std::string fullname = templateDirectory;
           fullname += "/";
           fullname += file;
diff --git a/Source/cmExtraCodeBlocksGenerator.cxx b/Source/cmExtraCodeBlocksGenerator.cxx
index 9c9b75b..76fc8f1 100644
--- a/Source/cmExtraCodeBlocksGenerator.cxx
+++ b/Source/cmExtraCodeBlocksGenerator.cxx
@@ -345,8 +345,7 @@ void cmExtraCodeBlocksGenerator::CreateNewProjectFile(
   all_files_map_t allFiles;
   std::vector<std::string> cFiles;
 
-  std::vector<std::string> const& srcExts =
-    this->GlobalGenerator->GetCMakeInstance()->GetSourceExtensions();
+  auto cm = this->GlobalGenerator->GetCMakeInstance();
 
   for (cmLocalGenerator* lg : lgs) {
     cmMakefile* makefile = lg->GetMakefile();
@@ -377,12 +376,7 @@ void cmExtraCodeBlocksGenerator::CreateNewProjectFile(
             std::string lang = s->GetLanguage();
             if (lang == "C" || lang == "CXX") {
               std::string const& srcext = s->GetExtension();
-              for (std::string const& ext : srcExts) {
-                if (srcext == ext) {
-                  isCFile = true;
-                  break;
-                }
-              }
+              isCFile = cm->IsSourceExtension(srcext);
             }
 
             std::string const& fullPath = s->GetFullPath();
diff --git a/Source/cmExtraCodeLiteGenerator.cxx b/Source/cmExtraCodeLiteGenerator.cxx
index 5a02d54..383942b 100644
--- a/Source/cmExtraCodeLiteGenerator.cxx
+++ b/Source/cmExtraCodeLiteGenerator.cxx
@@ -198,8 +198,7 @@ std::string cmExtraCodeLiteGenerator::CollectSourceFiles(
   std::map<std::string, cmSourceFile*>& cFiles,
   std::set<std::string>& otherFiles)
 {
-  const std::vector<std::string>& srcExts =
-    this->GlobalGenerator->GetCMakeInstance()->GetSourceExtensions();
+  auto cm = this->GlobalGenerator->GetCMakeInstance();
 
   std::string projectType;
   switch (gt->GetType()) {
@@ -233,12 +232,7 @@ std::string cmExtraCodeLiteGenerator::CollectSourceFiles(
         std::string lang = s->GetLanguage();
         if (lang == "C" || lang == "CXX") {
           std::string const& srcext = s->GetExtension();
-          for (std::string const& ext : srcExts) {
-            if (srcext == ext) {
-              isCFile = true;
-              break;
-            }
-          }
+          isCFile = cm->IsSourceExtension(srcext);
         }
 
         // then put it accordingly into one of the two containers
diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index 4109b90..c642db7 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -3120,9 +3120,16 @@ 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;
+  auto name = this->GetCMakeInstance()->StripExtension(sfl.GetName());
+#if defined(_WIN32) || defined(__APPLE__)
+  name = cmSystemTools::LowerCase(name);
+#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;
@@ -3136,6 +3143,14 @@ cmSourceFile* cmMakefile::CreateSource(const std::string& sourceName,
     sf->SetProperty("GENERATED", "1");
   }
   this->SourceFiles.push_back(sf);
+
+  auto name =
+    this->GetCMakeInstance()->StripExtension(sf->GetLocation().GetName());
+#if defined(_WIN32) || defined(__APPLE__)
+  name = cmSystemTools::LowerCase(name);
+#endif
+  this->SourceFileSearchIndex[name].push_back(sf);
+
   return sf;
 }
 
diff --git a/Source/cmMakefile.h b/Source/cmMakefile.h
index 6867c02..7c27aef 100644
--- a/Source/cmMakefile.h
+++ b/Source/cmMakefile.h
@@ -821,7 +821,18 @@ protected:
   // libraries, classes, and executables
   mutable cmTargets Targets;
   std::map<std::string, std::string> AliasTargets;
-  std::vector<cmSourceFile*> SourceFiles;
+
+  typedef std::vector<cmSourceFile*> SourceFileVec;
+  SourceFileVec 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_map<std::string, SourceFileVec> SourceFileMap;
+  SourceFileMap SourceFileSearchIndex;
 
   // Tests
   std::map<std::string, cmTest*> Tests;
diff --git a/Source/cmSourceFileLocation.cxx b/Source/cmSourceFileLocation.cxx
index 4f337f2..6add7b3 100644
--- a/Source/cmSourceFileLocation.cxx
+++ b/Source/cmSourceFileLocation.cxx
@@ -8,9 +8,7 @@
 #include "cmSystemTools.h"
 #include "cmake.h"
 
-#include <algorithm>
 #include <assert.h>
-#include <vector>
 
 cmSourceFileLocation::cmSourceFileLocation()
   : Makefile(nullptr)
@@ -86,13 +84,9 @@ void cmSourceFileLocation::UpdateExtension(const std::string& name)
   // The global generator checks extensions of enabled languages.
   cmGlobalGenerator* gg = this->Makefile->GetGlobalGenerator();
   cmMakefile const* mf = this->Makefile;
-  const std::vector<std::string>& srcExts =
-    mf->GetCMakeInstance()->GetSourceExtensions();
-  const std::vector<std::string>& hdrExts =
-    mf->GetCMakeInstance()->GetHeaderExtensions();
+  auto cm = mf->GetCMakeInstance();
   if (!gg->GetLanguageFromExtension(ext.c_str()).empty() ||
-      std::find(srcExts.begin(), srcExts.end(), ext) != srcExts.end() ||
-      std::find(hdrExts.begin(), hdrExts.end(), ext) != hdrExts.end()) {
+      cm->IsSourceExtension(ext) || cm->IsHeaderExtension(ext)) {
     // This is a known extension.  Use the given filename with extension.
     this->Name = cmSystemTools::GetFilenameName(name);
     this->AmbiguousExtension = false;
@@ -149,14 +143,8 @@ bool cmSourceFileLocation::MatchesAmbiguousExtension(
   // disk.  One of these must match if loc refers to this source file.
   std::string const& ext = this->Name.substr(loc.Name.size() + 1);
   cmMakefile const* mf = this->Makefile;
-  const std::vector<std::string>& srcExts =
-    mf->GetCMakeInstance()->GetSourceExtensions();
-  if (std::find(srcExts.begin(), srcExts.end(), ext) != srcExts.end()) {
-    return true;
-  }
-  std::vector<std::string> hdrExts =
-    mf->GetCMakeInstance()->GetHeaderExtensions();
-  return std::find(hdrExts.begin(), hdrExts.end(), ext) != hdrExts.end();
+  auto cm = mf->GetCMakeInstance();
+  return cm->IsSourceExtension(ext) || cm->IsHeaderExtension(ext);
 }
 
 bool cmSourceFileLocation::Matches(cmSourceFileLocation const& loc)
diff --git a/Source/cmake.cxx b/Source/cmake.cxx
index fde77a7..2a5bb6c 100644
--- a/Source/cmake.cxx
+++ b/Source/cmake.cxx
@@ -200,6 +200,11 @@ cmake::cmake(Role role)
   this->SourceFileExtensions.push_back("M");
   this->SourceFileExtensions.push_back("mm");
 
+  std::copy(this->SourceFileExtensions.begin(),
+            this->SourceFileExtensions.end(),
+            std::inserter(this->SourceFileExtensionsSet,
+                          this->SourceFileExtensionsSet.end()));
+
   this->HeaderFileExtensions.push_back("h");
   this->HeaderFileExtensions.push_back("hh");
   this->HeaderFileExtensions.push_back("h++");
@@ -208,6 +213,11 @@ cmake::cmake(Role role)
   this->HeaderFileExtensions.push_back("hxx");
   this->HeaderFileExtensions.push_back("in");
   this->HeaderFileExtensions.push_back("txx");
+
+  std::copy(this->HeaderFileExtensions.begin(),
+            this->HeaderFileExtensions.end(),
+            std::inserter(this->HeaderFileExtensionsSet,
+                          this->HeaderFileExtensionsSet.end()));
 }
 
 cmake::~cmake()
@@ -1647,6 +1657,21 @@ void cmake::AddCacheEntry(const std::string& key, const char* value,
   this->UnwatchUnusedCli(key);
 }
 
+std::string cmake::StripExtension(const std::string& file) const
+{
+  auto dotpos = file.rfind('.');
+  if (dotpos != std::string::npos) {
+    auto ext = file.substr(dotpos + 1);
+#if defined(_WIN32) || defined(__APPLE__)
+    ext = cmSystemTools::LowerCase(ext);
+#endif
+    if (this->IsSourceExtension(ext) || this->IsHeaderExtension(ext)) {
+      return file.substr(0, dotpos);
+    }
+  }
+  return file;
+}
+
 const char* cmake::GetCacheDefinition(const std::string& name) const
 {
   return this->State->GetInitializedCacheValue(name);
diff --git a/Source/cmake.h b/Source/cmake.h
index 5c5a90d..02c6cdb 100644
--- a/Source/cmake.h
+++ b/Source/cmake.h
@@ -8,6 +8,7 @@
 #include <map>
 #include <set>
 #include <string>
+#include <unordered_set>
 #include <vector>
 
 #include "cmInstalledFile.h"
@@ -225,11 +226,27 @@ public:
   {
     return this->SourceFileExtensions;
   }
+
+  bool IsSourceExtension(const std::string& ext) const
+  {
+    return this->SourceFileExtensionsSet.find(ext) !=
+      this->SourceFileExtensionsSet.end();
+  }
+
   const std::vector<std::string>& GetHeaderExtensions() const
   {
     return this->HeaderFileExtensions;
   }
 
+  bool IsHeaderExtension(const std::string& ext) const
+  {
+    return this->HeaderFileExtensionsSet.find(ext) !=
+      this->HeaderFileExtensionsSet.end();
+  }
+
+  // Strips the extension (if present and known) from a filename
+  std::string StripExtension(const std::string& file) const;
+
   /**
    * Given a variable name, return its value (as a string).
    */
@@ -486,7 +503,9 @@ private:
   std::string CheckStampList;
   std::string VSSolutionFile;
   std::vector<std::string> SourceFileExtensions;
+  std::unordered_set<std::string> SourceFileExtensionsSet;
   std::vector<std::string> HeaderFileExtensions;
+  std::unordered_set<std::string> HeaderFileExtensionsSet;
   bool ClearBuildSystem;
   bool DebugTryCompile;
   cmFileTimeComparison* FileComparison;