From 430296dc962bad3ada1e9174f529a53ca676c7df Mon Sep 17 00:00:00 2001 From: Brad King Date: Sun, 23 Dec 2007 15:03:42 -0500 Subject: ENH: Moved global inter-target dependency analysis and cycle-prevention code up from cmGlobalUnixMakefileGenerator3 to cmGlobalGenerator. Simplified cmGlobalUnixMakefileGenerator3 to use it. Later other generators may be modified to use it also. --- Source/cmGlobalGenerator.cxx | 177 +++++++++++++++++++++--------- Source/cmGlobalGenerator.h | 19 +++- Source/cmGlobalUnixMakefileGenerator3.cxx | 163 +++------------------------ Source/cmGlobalUnixMakefileGenerator3.h | 13 +-- Source/cmLocalUnixMakefileGenerator3.cxx | 3 +- Source/cmLocalUnixMakefileGenerator3.h | 2 +- Source/cmTarget.h | 2 +- 7 files changed, 157 insertions(+), 222 deletions(-) diff --git a/Source/cmGlobalGenerator.cxx b/Source/cmGlobalGenerator.cxx index a0eb31a..708bb86 100644 --- a/Source/cmGlobalGenerator.cxx +++ b/Source/cmGlobalGenerator.cxx @@ -725,10 +725,6 @@ void cmGlobalGenerator::Configure() // so create the map from project name to vector of local generators this->FillProjectMap(); - // Create a map from local generator to the complete set of targets - // it builds by default. - this->FillLocalGeneratorToTargetMap(); - if ( !this->CMakeInstance->GetScriptMode() ) { this->CMakeInstance->UpdateProgress("Configuring done", -1); @@ -791,6 +787,10 @@ void cmGlobalGenerator::Generate() this->LocalGenerators[i]->GenerateTargetManifest(this->TargetManifest); } + // Create a map from local generator to the complete set of targets + // it builds by default. + this->FillLocalGeneratorToTargetMap(); + // Generate project files for (i = 0; i < this->LocalGenerators.size(); ++i) { @@ -1264,6 +1264,7 @@ void cmGlobalGenerator::FillProjectMap() // generator directory level. void cmGlobalGenerator::FillLocalGeneratorToTargetMap() { + this->LocalGeneratorToTargetMap.clear(); // Loop over all targets in all local generators. for(std::vector::const_iterator lgi = this->LocalGenerators.begin(); @@ -1282,14 +1283,14 @@ void cmGlobalGenerator::FillLocalGeneratorToTargetMap() clg = clg->GetParent()) { // This local generator includes the target. - std::set& targetSet = + std::set& targetSet = this->LocalGeneratorToTargetMap[clg]; targetSet.insert(&target); // Add dependencies of the included target. An excluded // target may still be included if it is a dependency of a // non-excluded target. - std::vector& tgtdeps = this->GetTargetDepends(target); + TargetDependSet const& tgtdeps = this->GetTargetDepends(target); targetSet.insert(tgtdeps.begin(), tgtdeps.end()); } } @@ -1681,79 +1682,147 @@ void cmGlobalGenerator::AppendDirectoryForConfig(const char*, const char*, } //---------------------------------------------------------------------------- -std::vector& cmGlobalGenerator -::GetTargetDepends(cmTarget& target) +cmGlobalGenerator::TargetDependSet const& +cmGlobalGenerator::GetTargetDepends(cmTarget const& target) { + // Clarify the role of the input target. + cmTarget const* depender = ⌖ + // if the depends are already in the map then return - std::map >::iterator tgtI = - this->TargetDependencies.find(target.GetName()); - if (tgtI != this->TargetDependencies.end()) + TargetDependMap::const_iterator tgtI = + this->TargetDependencies.find(depender); + if(tgtI != this->TargetDependencies.end()) { return tgtI->second; } - // A target should not depend on itself. + // Create an entry for this depender. + TargetDependSet& depender_depends = this->TargetDependencies[depender]; + + // Keep track of dependencies already listed. std::set emitted; - emitted.insert(target.GetName()); - // the vector of results - std::vector& result = - this->TargetDependencies[target.GetName()]; + // A target should not depend on itself. + emitted.insert(depender->GetName()); - // Loop over all library dependencies but not for static libs - if (target.GetType() != cmTarget::STATIC_LIBRARY) + // Loop over all targets linked directly. + cmTarget::LinkLibraryVectorType const& tlibs = + target.GetOriginalLinkLibraries(); + for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin(); + lib != tlibs.end(); ++lib) { - const cmTarget::LinkLibraryVectorType& tlibs = target.GetLinkLibraries(); - for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin(); - lib != tlibs.end(); ++lib) + // Don't emit the same library twice for this target. + if(emitted.insert(lib->first).second) { - // Don't emit the same library twice for this target. - if(emitted.insert(lib->first).second) - { - cmTarget *target2 = - target.GetMakefile()->FindTarget(lib->first.c_str(), false); - - // search each local generator until a match is found - if (!target2) - { - target2 = this->FindTarget(0,lib->first.c_str(), false); - } - - // if a match was found then ... - if (target2) - { - // Add this dependency. - result.push_back(target2); - } - } + this->ConsiderTargetDepends(depender, depender_depends, + lib->first.c_str()); } } // Loop over all utility dependencies. - const std::set& tutils = target.GetUtilities(); + std::set const& tutils = target.GetUtilities(); for(std::set::const_iterator util = tutils.begin(); util != tutils.end(); ++util) { // Don't emit the same utility twice for this target. if(emitted.insert(*util).second) { - cmTarget *target2=target.GetMakefile()->FindTarget(util->c_str(), false); + this->ConsiderTargetDepends(depender, depender_depends, + util->c_str()); + } + } - // search each local generator until a match is found - if (!target2) - { - target2 = this->FindTarget(0,util->c_str(), false); - } + return depender_depends; +} - // if a match was found then ... - if (target2) - { - // Add this dependency. - result.push_back(target2); - } +//---------------------------------------------------------------------------- +bool +cmGlobalGenerator::ConsiderTargetDepends(cmTarget const* depender, + TargetDependSet& depender_depends, + const char* dependee_name) +{ + // Check the target's makefile first. + cmTarget const* dependee = + depender->GetMakefile()->FindTarget(dependee_name, false); + + // Then search globally. + if(!dependee) + { + dependee = this->FindTarget(0, dependee_name, false); + } + + // If not found then skip then the dependee. + if(!dependee) + { + return false; + } + + // Check whether the depender is among the dependee's dependencies. + std::vector steps; + if(this->FindDependency(depender, dependee, steps)) + { + // This creates a cyclic dependency. + bool isStatic = depender->GetType() == cmTarget::STATIC_LIBRARY; + cmOStringStream e; + e << "Cyclic dependency among targets:\n" + << " " << depender->GetName() << "\n"; + for(unsigned int i = static_cast(steps.size()); + i > 0; --i) + { + cmTarget const* step = steps[i-1]; + e << " -> " << step->GetName() << "\n"; + isStatic = isStatic && step->GetType() == cmTarget::STATIC_LIBRARY; + } + if(isStatic) + { + e << " All targets are STATIC libraries.\n"; + e << " Dropping " + << depender->GetName() << " -> " << dependee->GetName() + << " to resolve.\n"; + cmSystemTools::Message(e.str().c_str()); } + else + { + e << " At least one target is not a STATIC library.\n"; + cmSystemTools::Error(e.str().c_str()); + } + return false; + } + else + { + // This does not create a cyclic dependency. + depender_depends.insert(dependee); + return true; } - return result; +} + +//---------------------------------------------------------------------------- +bool +cmGlobalGenerator +::FindDependency(cmTarget const* goal, cmTarget const* current, + std::vector& steps) +{ + if(current == goal) + { + steps.push_back(current); + return true; + } + TargetDependMap::const_iterator i = this->TargetDependencies.find(current); + if(i == this->TargetDependencies.end()) + { + return false; + } + TargetDependSet const& depends = i->second; + for(TargetDependSet::const_iterator j = depends.begin(); + j != depends.end(); ++j) + { + if(this->FindDependency(goal, *j, steps)) + { + steps.push_back(current); + return true; + } + } + return false; } void cmGlobalGenerator::AddTarget(cmTargets::value_type &v) diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h index dff2ca7..edb2019 100644 --- a/Source/cmGlobalGenerator.h +++ b/Source/cmGlobalGenerator.h @@ -223,8 +223,11 @@ public: virtual const char* GetRebuildCacheTargetName() { return 0; } virtual const char* GetCleanTargetName() { return 0; } + // Class to track a set of dependencies. + class TargetDependSet: public std::set {}; + // what targets does the specified target depend on - std::vector& GetTargetDepends(cmTarget& target); + TargetDependSet const& GetTargetDepends(cmTarget const& target); const std::map >& GetProjectMap() const {return this->ProjectMap;} @@ -260,7 +263,8 @@ protected: cmLocalGenerator* CurrentLocalGenerator; // map from project name to vector of local generators in that project std::map > ProjectMap; - std::map > LocalGeneratorToTargetMap; + std::map > + LocalGeneratorToTargetMap; // Set of named installation components requested by the project. std::set InstallComponents; @@ -286,13 +290,20 @@ private: // this is used to improve performance std::map TotalTargets; std::map ImportedTotalTargets; - - std::map > TargetDependencies; cmExternalMakefileProjectGenerator* ExtraGenerator; // track files replaced during a Generate std::vector FilesReplacedDuringGenerate; + + // Track inter-target dependencies. + bool ConsiderTargetDepends(cmTarget const* depender, + TargetDependSet& depender_depends, + const char* dependee_name); + bool FindDependency(cmTarget const* goal, cmTarget const* current, + std::vector& steps); + typedef std::map TargetDependMap; + TargetDependMap TargetDependencies; }; #endif diff --git a/Source/cmGlobalUnixMakefileGenerator3.cxx b/Source/cmGlobalUnixMakefileGenerator3.cxx index 792ee56..ff29c4a 100644 --- a/Source/cmGlobalUnixMakefileGenerator3.cxx +++ b/Source/cmGlobalUnixMakefileGenerator3.cxx @@ -848,7 +848,7 @@ cmGlobalUnixMakefileGenerator3 //---------------------------------------------------------------------------- int cmGlobalUnixMakefileGenerator3 -::GetTargetTotalNumberOfActions(cmTarget& target, +::GetTargetTotalNumberOfActions(cmTarget const& target, std::set &emitted) { // do not double count @@ -861,9 +861,9 @@ int cmGlobalUnixMakefileGenerator3 (target.GetMakefile()->GetLocalGenerator()); result = static_cast(lg->ProgressFiles[target.GetName()].size()); - std::vector& depends = this->GetTargetDepends(target); + TargetDependSet const& depends = this->GetTargetDepends(target); - std::vector::iterator i; + TargetDependSet::const_iterator i; for (i = depends.begin(); i != depends.end(); ++i) { result += this->GetTargetTotalNumberOfActions(**i, emitted); @@ -877,11 +877,11 @@ unsigned long cmGlobalUnixMakefileGenerator3 ::GetNumberOfProgressActionsInAll(cmLocalUnixMakefileGenerator3 *lg) { unsigned long result = 0; - std::set& targets = this->LocalGeneratorToTargetMap[lg]; - for(std::set::iterator t = targets.begin(); + std::set& targets = this->LocalGeneratorToTargetMap[lg]; + for(std::set::iterator t = targets.begin(); t != targets.end(); ++t) { - cmTarget* target = *t; + cmTarget const* target = *t; cmLocalUnixMakefileGenerator3 *lg3 = static_cast (target->GetMakefile()->GetLocalGenerator()); @@ -898,80 +898,18 @@ cmGlobalUnixMakefileGenerator3 ::AppendGlobalTargetDepends(std::vector& depends, cmTarget& target) { - // Keep track of dependencies already listed. - std::set emitted; - - // A target should not depend on itself. - emitted.insert(target.GetName()); - - // Loop over all library dependencies. - const cmTarget::LinkLibraryVectorType& - tlibs = target.GetOriginalLinkLibraries(); - for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin(); - lib != tlibs.end(); ++lib) - { - // Don't emit the same library twice for this target. - if(emitted.insert(lib->first).second) - { - // Add this dependency. - this->AppendAnyGlobalDepend(depends, lib->first.c_str(), target); - } - } - - // Loop over all utility dependencies. - const std::set& tutils = target.GetUtilities(); - for(std::set::const_iterator util = tutils.begin(); - util != tutils.end(); ++util) - { - // Don't emit the same utility twice for this target. - if(emitted.insert(*util).second) - { - // Add this dependency. - this->AppendAnyGlobalDepend(depends, util->c_str(), target); - } - } -} - - -//---------------------------------------------------------------------------- -void -cmGlobalUnixMakefileGenerator3 -::AppendAnyGlobalDepend(std::vector& depends, const char* name, - cmTarget &target) -{ - cmTarget *result; - cmLocalUnixMakefileGenerator3 *lg3; - - // first check the same dir as the current target - lg3 = static_cast - (target.GetMakefile()->GetLocalGenerator()); - result = target.GetMakefile()->FindTarget(name, false); - - // search each local generator until a match is found - if (!result) + TargetDependSet const& depends_set = this->GetTargetDepends(target); + for(TargetDependSet::const_iterator i = depends_set.begin(); + i != depends_set.end(); ++i) { - result = this->FindTarget(0, name, false); - if (result) - { - lg3 = static_cast - (result->GetMakefile()->GetLocalGenerator()); - } - } - - // if a match was found then ... - if (result) - { - // Avoid creating cyclic dependencies. - if(!this->AllowTargetDepends(&target, result)) - { - return; - } - // Create the target-level dependency. - std::string tgtName = lg3->GetRelativeTargetDirectory(*result); + cmTarget const* dep = *i; + cmLocalUnixMakefileGenerator3* lg3 = + static_cast + (dep->GetMakefile()->GetLocalGenerator()); + std::string tgtName = lg3->GetRelativeTargetDirectory(*dep); tgtName += "/all"; depends.push_back(tgtName); - return; } } @@ -1057,76 +995,3 @@ bool cmGlobalUnixMakefileGenerator3 } return false; } - -//---------------------------------------------------------------------------- -bool -cmGlobalUnixMakefileGenerator3 -::AllowTargetDepends(cmTarget const* depender, cmTarget const* dependee) -{ - // Check whether the depender is among the dependee's dependencies. - std::vector steps; - if(this->FindDependency(depender, dependee, steps)) - { - // This creates a cyclic dependency. - bool isStatic = depender->GetType() == cmTarget::STATIC_LIBRARY; - cmOStringStream e; - e << "Cyclic dependency among targets:\n" - << " " << depender->GetName() << "\n"; - for(unsigned int i = static_cast(steps.size()); - i > 0; --i) - { - cmTarget const* step = steps[i-1]; - e << " -> " << step->GetName() << "\n"; - isStatic = isStatic && step->GetType() == cmTarget::STATIC_LIBRARY; - } - if(isStatic) - { - e << " All targets are STATIC libraries.\n"; - e << " Dropping " - << depender->GetName() << " -> " << dependee->GetName() - << " to resolve.\n"; - cmSystemTools::Message(e.str().c_str()); - } - else - { - e << " At least one target is not a STATIC library.\n"; - cmSystemTools::Error(e.str().c_str()); - } - return false; - } - else - { - // This does not create a cyclic dependency. - this->TargetDependencies[depender].insert(dependee); - return true; - } -} - -//---------------------------------------------------------------------------- -bool -cmGlobalUnixMakefileGenerator3 -::FindDependency(cmTarget const* goal, cmTarget const* current, - std::vector& steps) -{ - if(current == goal) - { - steps.push_back(current); - return true; - } - TargetDependMap::const_iterator i = this->TargetDependencies.find(current); - if(i == this->TargetDependencies.end()) - { - return false; - } - TargetDependSet const& depends = i->second; - for(TargetDependSet::const_iterator j = depends.begin(); - j != depends.end(); ++j) - { - if(this->FindDependency(goal, *j, steps)) - { - steps.push_back(current); - return true; - } - } - return false; -} diff --git a/Source/cmGlobalUnixMakefileGenerator3.h b/Source/cmGlobalUnixMakefileGenerator3.h index 8ee023c..49c4689 100644 --- a/Source/cmGlobalUnixMakefileGenerator3.h +++ b/Source/cmGlobalUnixMakefileGenerator3.h @@ -114,7 +114,7 @@ public: const char* config, bool ignoreErrors, bool fast); // returns some progress informaiton - int GetTargetTotalNumberOfActions(cmTarget& target, + int GetTargetTotalNumberOfActions(cmTarget const& target, std::set &emitted); unsigned long GetNumberOfProgressActionsInAll (cmLocalUnixMakefileGenerator3 *lg); @@ -145,9 +145,6 @@ protected: void AppendGlobalTargetDepends(std::vector& depends, cmTarget& target); - void AppendAnyGlobalDepend(std::vector& depends, - const char* name, - cmTarget &target); // does this generator need a requires step for any of its targets bool NeedRequiresStep(cmTarget const&); @@ -179,14 +176,6 @@ protected: std::map TargetSourceFileCount; bool ForceVerboseMakefiles; - - bool AllowTargetDepends(cmTarget const* depender, - cmTarget const* dependee); - bool FindDependency(cmTarget const* goal, cmTarget const* current, - std::vector& steps); - class TargetDependSet: public std::set {}; - typedef std::map TargetDependMap; - TargetDependMap TargetDependencies; }; #endif diff --git a/Source/cmLocalUnixMakefileGenerator3.cxx b/Source/cmLocalUnixMakefileGenerator3.cxx index 49a068c..3ceeccc 100644 --- a/Source/cmLocalUnixMakefileGenerator3.cxx +++ b/Source/cmLocalUnixMakefileGenerator3.cxx @@ -823,7 +823,8 @@ cmLocalUnixMakefileGenerator3 //---------------------------------------------------------------------------- std::string -cmLocalUnixMakefileGenerator3::GetRelativeTargetDirectory(cmTarget& target) +cmLocalUnixMakefileGenerator3 +::GetRelativeTargetDirectory(cmTarget const& target) { std::string dir = this->HomeRelativeOutputPath; dir += this->GetTargetDirectory(target); diff --git a/Source/cmLocalUnixMakefileGenerator3.h b/Source/cmLocalUnixMakefileGenerator3.h index dcef5b5..c41d0d8 100644 --- a/Source/cmLocalUnixMakefileGenerator3.h +++ b/Source/cmLocalUnixMakefileGenerator3.h @@ -210,7 +210,7 @@ public: void WriteSpecialTargetsTop(std::ostream& makefileStream); void WriteSpecialTargetsBottom(std::ostream& makefileStream); - std::string GetRelativeTargetDirectory(cmTarget& target); + std::string GetRelativeTargetDirectory(cmTarget const& target); // File pairs for implicit dependency scanning. The key of the map // is the depender and the value is the explicit dependee. diff --git a/Source/cmTarget.h b/Source/cmTarget.h index 879693a..8439ee1 100644 --- a/Source/cmTarget.h +++ b/Source/cmTarget.h @@ -181,7 +181,7 @@ public: */ void AddUtility(const char* u) { this->Utilities.insert(u);} ///! Get the utilities used by this target - std::setconst& GetUtilities() { return this->Utilities; } + std::setconst& GetUtilities() const { return this->Utilities; } void AnalyzeLibDependencies( const cmMakefile& mf ); -- cgit v0.12