ENH: Improve dynamic variable scope implementation

Previously each new variable scope (subdirectory or function call) in
the CMake language created a complete copy of the key->value definition
map.  This avoids the copy using transitive lookups up the scope stack.
Results of queries answered by parents are stored locally to maintain
locality of reference.

The class cmDefinitions replaces cmMakefile::DefinitionsMap, and is
aware of its enclosing scope.  Each scope stores only the definitions
set (or unset!) inside it relative to the enclosing scope.

6 files changed, 301 insertions, 95 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index 090f840..f17c0d6 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -116,6 +116,8 @@ SET(SRCS
   cmComputeTargetDepends.cxx
   cmCustomCommand.cxx
   cmCustomCommand.h
+  cmDefinitions.cxx
+  cmDefinitions.h
   cmDepends.cxx
   cmDepends.h
   cmDependsC.cxx
diff --git a/Source/cmDefinitions.cxx b/Source/cmDefinitions.cxx
new file mode 100644
index 0000000..13bfc6a
--- /dev/null
+++ b/Source/cmDefinitions.cxx
@@ -0,0 +1,167 @@
+/*=========================================================================
+
+  Program:   CMake - Cross-Platform Makefile Generator
+  Module:    $RCSfile$
+  Language:  C++
+  Date:      $Date$
+  Version:   $Revision$
+
+  Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
+  See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
+
+     This software is distributed WITHOUT ANY WARRANTY; without even
+     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+     PURPOSE.  See the above copyright notices for more information.
+
+=========================================================================*/
+#include "cmDefinitions.h"
+
+//----------------------------------------------------------------------------
+cmDefinitions::Def cmDefinitions::NoDef;
+
+//----------------------------------------------------------------------------
+cmDefinitions::cmDefinitions(cmDefinitions* parent): Up(parent)
+{
+}
+
+//----------------------------------------------------------------------------
+void cmDefinitions::Reset(cmDefinitions* parent)
+{
+  this->Up = parent;
+  this->Map.clear();
+}
+
+//----------------------------------------------------------------------------
+cmDefinitions::Def const&
+cmDefinitions::GetInternal(const char* key)
+{
+  MapType::const_iterator i = this->Map.find(key);
+  if(i != this->Map.end())
+    {
+    return i->second;
+    }
+  else if(cmDefinitions* up = this->Up)
+    {
+    // Query the parent scope and store the result locally.
+    Def def = up->GetInternal(key);
+    return this->Map.insert(MapType::value_type(key, def)).first->second;
+    }
+  return this->NoDef;
+}
+
+//----------------------------------------------------------------------------
+cmDefinitions::Def const&
+cmDefinitions::SetInternal(const char* key, Def const& def)
+{
+  if(this->Up || def.Exists)
+    {
+    // In lower scopes we store keys, defined or not.
+    MapType::iterator i = this->Map.find(key);
+    if(i == this->Map.end())
+      {
+      i = this->Map.insert(MapType::value_type(key, def)).first;
+      }
+    else
+      {
+      i->second = def;
+      }
+    return i->second;
+    }
+  else
+    {
+    // In the top-most scope we need not store undefined keys.
+    this->Map.erase(key);
+    return this->NoDef;
+    }
+}
+
+//----------------------------------------------------------------------------
+const char* cmDefinitions::Get(const char* key)
+{
+  Def const& def = this->GetInternal(key);
+  return def.Exists? def.c_str() : 0;
+}
+
+//----------------------------------------------------------------------------
+const char* cmDefinitions::Set(const char* key, const char* value)
+{
+  Def const& def = this->SetInternal(key, Def(value));
+  return def.Exists? def.c_str() : 0;
+}
+
+//----------------------------------------------------------------------------
+cmDefinitions cmDefinitions::Closure() const
+{
+  return cmDefinitions(ClosureTag(), this);
+}
+
+//----------------------------------------------------------------------------
+cmDefinitions::cmDefinitions(ClosureTag const&, cmDefinitions const* root):
+  Up(0)
+{
+  std::set<cmStdString> undefined;
+  this->ClosureImpl(undefined, root);
+}
+
+//----------------------------------------------------------------------------
+void cmDefinitions::ClosureImpl(std::set<cmStdString>& undefined,
+                                cmDefinitions const* defs)
+{
+  // Consider local definitions.
+  for(MapType::const_iterator mi = defs->Map.begin();
+      mi != defs->Map.end(); ++mi)
+    {
+    // Use this key if it is not already set or unset.
+    if(this->Map.find(mi->first) == this->Map.end() &&
+       undefined.find(mi->first) == undefined.end())
+      {
+      if(mi->second.Exists)
+        {
+        this->Map.insert(*mi);
+        }
+      else
+        {
+        undefined.insert(mi->first);
+        }
+      }
+    }
+
+  // Traverse parents.
+  if(cmDefinitions const* up = defs->Up)
+    {
+    this->ClosureImpl(undefined, up);
+    }
+}
+
+//----------------------------------------------------------------------------
+std::set<cmStdString> cmDefinitions::ClosureKeys() const
+{
+  std::set<cmStdString> defined;
+  std::set<cmStdString> undefined;
+  this->ClosureKeys(defined, undefined);
+  return defined;
+}
+
+//----------------------------------------------------------------------------
+void cmDefinitions::ClosureKeys(std::set<cmStdString>& defined,
+                                std::set<cmStdString>& undefined) const
+{
+  // Consider local definitions.
+  for(MapType::const_iterator mi = this->Map.begin();
+      mi != this->Map.end(); ++mi)
+    {
+    // Use this key if it is not already set or unset.
+    if(defined.find(mi->first) == defined.end() &&
+       undefined.find(mi->first) == undefined.end())
+      {
+      std::set<cmStdString>& m = mi->second.Exists? defined : undefined;
+      m.insert(mi->first);
+      }
+    }
+
+  // Traverse parents.
+  if(cmDefinitions const* up = this->Up)
+    {
+    up->ClosureKeys(defined, undefined);
+    }
+}
diff --git a/Source/cmDefinitions.h b/Source/cmDefinitions.h
new file mode 100644
index 0000000..f83e9f6
--- /dev/null
+++ b/Source/cmDefinitions.h
@@ -0,0 +1,88 @@
+/*=========================================================================
+
+  Program:   CMake - Cross-Platform Makefile Generator
+  Module:    $RCSfile$
+  Language:  C++
+  Date:      $Date$
+  Version:   $Revision$
+
+  Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
+  See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
+
+     This software is distributed WITHOUT ANY WARRANTY; without even
+     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+     PURPOSE.  See the above copyright notices for more information.
+
+=========================================================================*/
+#ifndef cmDefinitions_h
+#define cmDefinitions_h
+
+#include "cmStandardIncludes.h"
+
+/** \class cmDefinitions
+ * \brief Store a scope of variable definitions for CMake language.
+ *
+ * This stores the state of variable definitions (set or unset) for
+ * one scope.  Sets are always local.  Gets search parent scopes
+ * transitively and save results locally.
+ */
+class cmDefinitions
+{
+public:
+  /** Construct with the given parent scope.  */
+  cmDefinitions(cmDefinitions* parent = 0);
+
+  /** Reset object as if newly constructed.  */
+  void Reset(cmDefinitions* parent = 0);
+
+  /** Returns the parent scope, if any.  */
+  cmDefinitions* GetParent() const { return this->Up; }
+
+  /** Get the value associated with a key; null if none.
+      Store the result locally if it came from a parent.  */
+  const char* Get(const char* key);
+
+  /** Set (or unset if null) a value associated with a key.  */
+  const char* Set(const char* key, const char* value);
+
+  /** Compute the closure of all defined keys with values.
+      This flattens the scope.  The result has no parent.  */
+  cmDefinitions Closure() const;
+
+  /** Compute the set of all defined keys.  */
+  std::set<cmStdString> ClosureKeys() const;
+
+private:
+  // String with existence boolean.
+  struct Def: public cmStdString
+  {
+    Def(): cmStdString(), Exists(false) {}
+    Def(const char* v): cmStdString(v?v:""), Exists(v?true:false) {}
+    Def(Def const& d): cmStdString(d), Exists(d.Exists) {}
+    bool Exists;
+  };
+  static Def NoDef;
+
+  // Parent scope, if any.
+  cmDefinitions* Up;
+
+  // Local definitions, set or unset.
+  typedef std::map<cmStdString, Def> MapType;
+  MapType Map;
+
+  // Internal query and update methods.
+  Def const& GetInternal(const char* key);
+  Def const& SetInternal(const char* key, Def const& def);
+
+  // Implementation of Closure() method.
+  struct ClosureTag {};
+  cmDefinitions(ClosureTag const&, cmDefinitions const* root);
+  void ClosureImpl(std::set<cmStdString>& undefined,
+                   cmDefinitions const* defs);
+
+  // Implementation of ClosureKeys() method.
+  void ClosureKeys(std::set<cmStdString>& defined,
+                   std::set<cmStdString>& undefined) const;
+};
+
+#endif
diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index 5edbaa6..84d82df 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -33,6 +33,7 @@
 #endif
 #include "cmInstallGenerator.h"
 #include "cmTestGenerator.h"
+#include "cmDefinitions.h"
 #include "cmake.h"
 #include <stdlib.h> // required for atoi
 
@@ -40,12 +41,19 @@
 
 #include <cmsys/auto_ptr.hxx>
 
+#include <stack>
 #include <ctype.h> // for isspace
 
+class cmMakefile::Internals
+{
+public:
+  std::stack<cmDefinitions, std::list<cmDefinitions> > VarStack;
+};
+
 // default is not to be building executables
-cmMakefile::cmMakefile()
+cmMakefile::cmMakefile(): Internal(new Internals)
 {
-  this->DefinitionStack.push_back(DefinitionMap());
+  this->Internal->VarStack.push(cmDefinitions());
 
   // Setup the default include file regular expression (match everything).
   this->IncludeFileRegularExpression = "^.*$";
@@ -85,8 +93,10 @@ cmMakefile::cmMakefile()
   this->PreOrder = false;
 }
 
-cmMakefile::cmMakefile(const cmMakefile& mf)
+cmMakefile::cmMakefile(const cmMakefile& mf): Internal(new Internals)
 {
+  this->Internal->VarStack.push(mf.Internal->VarStack.top().Closure());
+
   this->Prefix = mf.Prefix;
   this->AuxSourceDirectories = mf.AuxSourceDirectories;
   this->cmStartDirectory = mf.cmStartDirectory;
@@ -117,13 +127,11 @@ cmMakefile::cmMakefile(const cmMakefile& mf)
   this->SourceGroups = mf.SourceGroups;
 #endif
 
-  this->DefinitionStack.push_back(mf.DefinitionStack.back());
   this->LocalGenerator = mf.LocalGenerator;
   this->FunctionBlockers = mf.FunctionBlockers;
   this->DataMap = mf.DataMap;
   this->MacrosMap = mf.MacrosMap;
   this->SubDirectoryOrder = mf.SubDirectoryOrder;
-  this->TemporaryDefinitionKey = mf.TemporaryDefinitionKey;
   this->Properties = mf.Properties;
   this->PreOrder = mf.PreOrder;
   this->ListFileStack = mf.ListFileStack;
@@ -1421,7 +1429,7 @@ void cmMakefile::InitializeFromParent()
   cmMakefile *parent = this->LocalGenerator->GetParent()->GetMakefile();
 
   // copy the definitions
-  this->DefinitionStack.front() = parent->DefinitionStack.back();
+  this->Internal->VarStack.top().Reset(&parent->Internal->VarStack.top());
 
   // copy include paths
   this->IncludeDirectories = parent->IncludeDirectories;
@@ -1640,14 +1648,13 @@ void cmMakefile::AddDefinition(const char* name, const char* value)
     }
 #endif
 
-  this->TemporaryDefinitionKey = name;
-  this->DefinitionStack.back()[this->TemporaryDefinitionKey] = value;
+  this->Internal->VarStack.top().Set(name, value);
 
 #ifdef CMAKE_BUILD_WITH_CMAKE
   cmVariableWatch* vv = this->GetVariableWatch();
   if ( vv )
     {
-    vv->VariableAccessed(this->TemporaryDefinitionKey,
+    vv->VariableAccessed(name,
                          cmVariableWatch::VARIABLE_MODIFIED_ACCESS,
                          value,
                          this);
@@ -1696,26 +1703,13 @@ void cmMakefile::AddCacheDefinition(const char* name, const char* value,
     }
   this->GetCacheManager()->AddCacheEntry(name, val, doc, type);
   // if there was a definition then remove it
-  this->DefinitionStack.back().erase( DefinitionMap::key_type(name));
+  this->Internal->VarStack.top().Set(name, 0);
 }
 
 
 void cmMakefile::AddDefinition(const char* name, bool value)
 {
-  if(value)
-    {
-    this->DefinitionStack.back()
-      .erase( DefinitionMap::key_type(name));
-    this->DefinitionStack.back()
-      .insert(DefinitionMap::value_type(name, "ON"));
-    }
-  else
-    {
-    this->DefinitionStack.back()
-      .erase( DefinitionMap::key_type(name));
-    this->DefinitionStack.back()
-      .insert(DefinitionMap::value_type(name, "OFF"));
-    }
+  this->Internal->VarStack.top().Set(name, value? "ON" : "OFF");
 #ifdef CMAKE_BUILD_WITH_CMAKE
   cmVariableWatch* vv = this->GetVariableWatch();
   if ( vv )
@@ -1745,7 +1739,7 @@ void cmMakefile::AddCacheDefinition(const char* name,
 
 void cmMakefile::RemoveDefinition(const char* name)
 {
-  this->DefinitionStack.back().erase(DefinitionMap::key_type(name));
+  this->Internal->VarStack.top().Set(name, 0);
 #ifdef CMAKE_BUILD_WITH_CMAKE
   cmVariableWatch* vv = this->GetVariableWatch();
   if ( vv )
@@ -2087,14 +2081,8 @@ const char* cmMakefile::GetRequiredDefinition(const char* name) const
 
 bool cmMakefile::IsDefinitionSet(const char* name) const
 {
-  const char* def = 0;
-  DefinitionMap::const_iterator pos = 
-    this->DefinitionStack.back().find(name);
-  if(pos != this->DefinitionStack.back().end())
-    {
-    def = (*pos).second.c_str();
-    }
-  else
+  const char* def = this->Internal->VarStack.top().Get(name);
+  if(!def)
     {
     def = this->GetCacheManager()->GetCacheValue(name);
     }
@@ -2121,14 +2109,8 @@ const char* cmMakefile::GetDefinition(const char* name) const
       RecordPropertyAccess(name,cmProperty::VARIABLE);
     }
 #endif
-  const char* def = 0;
-  DefinitionMap::const_iterator pos = 
-    this->DefinitionStack.back().find(name);
-  if(pos != this->DefinitionStack.back().end())
-    {
-    def = (*pos).second.c_str();
-    }
-  else
+  const char* def = this->Internal->VarStack.top().Get(name);
+  if(!def)
     {
     def = this->GetCacheManager()->GetCacheValue(name);
     }
@@ -2144,11 +2126,9 @@ const char* cmMakefile::GetDefinition(const char* name) const
     else
       {
       // are unknown access allowed
-      DefinitionMap::const_iterator pos2 =
-        this->DefinitionStack.back()
-        .find("CMAKE_ALLOW_UNKNOWN_VARIABLE_READ_ACCESS");
-      if (pos2 != this->DefinitionStack.back().end() &&
-          cmSystemTools::IsOn((*pos2).second.c_str()))
+      const char* allow = this->Internal->VarStack.top()
+        .Get("CMAKE_ALLOW_UNKNOWN_VARIABLE_READ_ACCESS");
+      if(cmSystemTools::IsOn(allow))
         {
         vv->VariableAccessed(name,
           cmVariableWatch::ALLOWED_UNKNOWN_VARIABLE_READ_ACCESS, def, this);
@@ -2177,29 +2157,24 @@ const char* cmMakefile::GetSafeDefinition(const char* def) const
 std::vector<std::string> cmMakefile
 ::GetDefinitions(int cacheonly /* = 0 */) const
 {
-  std::map<cmStdString, int> definitions;
+  std::set<cmStdString> definitions;
   if ( !cacheonly )
     {
-    DefinitionMap::const_iterator it;
-    for ( it = this->DefinitionStack.back().begin();
-          it != this->DefinitionStack.back().end(); it ++ )
-      {
-      definitions[it->first] = 1;
-      }
+    definitions = this->Internal->VarStack.top().ClosureKeys();
     }
   cmCacheManager::CacheIterator cit =
     this->GetCacheManager()->GetCacheIterator();
   for ( cit.Begin(); !cit.IsAtEnd(); cit.Next() )
     {
-    definitions[cit.GetName()] = 1;
+    definitions.insert(cit.GetName());
     }
 
   std::vector<std::string> res;
 
-  std::map<cmStdString, int>::iterator fit;
+  std::set<cmStdString>::iterator fit;
   for ( fit = definitions.begin(); fit != definitions.end(); fit ++ )
     {
-    res.push_back(fit->first);
+    res.push_back(*fit);
     }
   return res;
 }
@@ -3387,19 +3362,13 @@ std::string cmMakefile::GetListFileStack()
 
 void cmMakefile::PushScope()
 {
-  // Get the index of the next stack entry.
-  std::vector<DefinitionMap>::size_type index = this->DefinitionStack.size();
-
-  // Allocate a new stack entry.
-  this->DefinitionStack.push_back(DefinitionMap());
-
-  // Copy the previous top to the new top.
-  this->DefinitionStack[index] = this->DefinitionStack[index-1];
+  cmDefinitions* parent = &this->Internal->VarStack.top();
+  this->Internal->VarStack.push(cmDefinitions(parent));
 }
 
 void cmMakefile::PopScope()
 {
-  this->DefinitionStack.pop_back();
+  this->Internal->VarStack.pop();
 }
 
 void cmMakefile::RaiseScope(const char *var, const char *varDef)
@@ -3409,33 +3378,14 @@ void cmMakefile::RaiseScope(const char *var, const char *varDef)
     return;
     }
 
-  // multiple scopes in this directory?
-  if (this->DefinitionStack.size() > 1)
-    {
-    if(varDef)
-      {
-      this->DefinitionStack[this->DefinitionStack.size()-2][var] = varDef;
-      }
-    else
-      {
-      this->DefinitionStack[this->DefinitionStack.size()-2].erase(var);
-      }
-    }
-  // otherwise do the parent (if one exists)
-  else if (this->LocalGenerator->GetParent())
+  cmDefinitions& cur = this->Internal->VarStack.top();
+  if(cmDefinitions* up = cur.GetParent())
     {
-    cmMakefile *parent = this->LocalGenerator->GetParent()->GetMakefile();
-    if (parent)
-      {
-      if(varDef)
-        {
-        parent->AddDefinition(var,varDef);
-        }
-      else
-        {
-        parent->RemoveDefinition(var);
-        }
-      }
+    // First localize the definition in the current scope.
+    cur.Get(var);
+
+    // Now update the definition in the parent scope.
+    up->Set(var, varDef);
     }
 }
 
diff --git a/Source/cmMakefile.h b/Source/cmMakefile.h
index 7a235f9..5cd3587 100644
--- a/Source/cmMakefile.h
+++ b/Source/cmMakefile.h
@@ -56,6 +56,8 @@ class cmCMakePolicyCommand;
  */
 class cmMakefile
 {
+  class Internals;
+  cmsys::auto_ptr<Internals> Internal;
 public:
   /**
    * Return the major and minor version of the cmake that
@@ -792,7 +794,6 @@ public:
   // Get the properties
   cmPropertyMap &GetProperties() { return this->Properties; };
 
-  typedef std::map<cmStdString, cmStdString> DefinitionMap;
   ///! Initialize a makefile from its parent
   void InitializeFromParent();
   
@@ -889,7 +890,6 @@ protected:
   std::vector<cmSourceGroup> SourceGroups;
 #endif
 
-  std::vector<DefinitionMap> DefinitionStack;
   std::vector<cmCommand*> UsedCommands;
   cmLocalGenerator* LocalGenerator;
   bool IsFunctionBlocked(const cmListFileFunction& lff, 
@@ -924,8 +924,6 @@ private:
   StringStringMap MacrosMap;
 
   std::map<cmStdString, bool> SubDirectoryOrder;
-  // used in AddDefinition for performance improvement
-  DefinitionMap::key_type  TemporaryDefinitionKey;
 
   cmsys::RegularExpression cmDefineRegex;
   cmsys::RegularExpression cmDefine01Regex;
diff --git a/bootstrap b/bootstrap
index 113cbb9..4710eca 100755
--- a/bootstrap
+++ b/bootstrap
@@ -172,6 +172,7 @@ CMAKE_CXX_SOURCES="\
   cmCommandArgumentLexer \
   cmCommandArgumentParser \
   cmCommandArgumentParserHelper \
+  cmDefinitions \
   cmDepends \
   cmDependsC \
   cmDocumentationFormatter \