From fd10589995fe942ceecbc0e1d5f869a534abdbba Mon Sep 17 00:00:00 2001 From: Brad King Date: Wed, 22 Jul 2009 14:22:45 -0400 Subject: 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. --- Source/CMakeLists.txt | 2 + Source/cmDefinitions.cxx | 167 +++++++++++++++++++++++++++++++++++++++++++++++ Source/cmDefinitions.h | 88 +++++++++++++++++++++++++ Source/cmMakefile.cxx | 132 ++++++++++++------------------------- Source/cmMakefile.h | 6 +- bootstrap | 1 + 6 files changed, 301 insertions(+), 95 deletions(-) create mode 100644 Source/cmDefinitions.cxx create mode 100644 Source/cmDefinitions.h 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 undefined; + this->ClosureImpl(undefined, root); +} + +//---------------------------------------------------------------------------- +void cmDefinitions::ClosureImpl(std::set& 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 cmDefinitions::ClosureKeys() const +{ + std::set defined; + std::set undefined; + this->ClosureKeys(defined, undefined); + return defined; +} + +//---------------------------------------------------------------------------- +void cmDefinitions::ClosureKeys(std::set& defined, + std::set& 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& 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 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 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& undefined, + cmDefinitions const* defs); + + // Implementation of ClosureKeys() method. + void ClosureKeys(std::set& defined, + std::set& 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 // required for atoi @@ -40,12 +41,19 @@ #include +#include #include // for isspace +class cmMakefile::Internals +{ +public: + std::stack > 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 cmMakefile ::GetDefinitions(int cacheonly /* = 0 */) const { - std::map definitions; + std::set 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 res; - std::map::iterator fit; + std::set::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::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 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 DefinitionMap; ///! Initialize a makefile from its parent void InitializeFromParent(); @@ -889,7 +890,6 @@ protected: std::vector SourceGroups; #endif - std::vector DefinitionStack; std::vector UsedCommands; cmLocalGenerator* LocalGenerator; bool IsFunctionBlocked(const cmListFileFunction& lff, @@ -924,8 +924,6 @@ private: StringStringMap MacrosMap; std::map 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 \ -- cgit v0.12