From 699e3bc87d1cbb3c2b19ddaf5db37909cb49f47b Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Fri, 20 Jan 2017 12:38:06 +0200 Subject: Remove prerequisite caching in scope We don't share them often and those that are shared (e.g., cxx{} in obja/objs{}) are lightweight (SOO). --- build2/algorithm.cxx | 2 +- build2/cc/link.cxx | 8 +-- build2/cli/rule.cxx | 2 +- build2/install/rule.cxx | 2 +- build2/parser.cxx | 81 +++++++++++++---------------- build2/prerequisite | 132 ++++++++++-------------------------------------- build2/prerequisite.cxx | 78 ++++++++++++---------------- build2/scope | 24 ++++----- build2/target | 87 +++++++++++++++---------------- build2/target.ixx | 28 +++------- build2/target.txx | 2 +- build2/test/common.cxx | 4 +- 12 files changed, 166 insertions(+), 284 deletions(-) diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx index 22633bb..f3bb8a0 100644 --- a/build2/algorithm.cxx +++ b/build2/algorithm.cxx @@ -277,7 +277,7 @@ namespace build2 void search_and_match_prerequisites (action a, target& t, scope* s) { - for (prerequisite p: group_prerequisites (t)) + for (prerequisite& p: group_prerequisites (t)) { target& pt (search (p)); diff --git a/build2/cc/link.cxx b/build2/cc/link.cxx index e1dac16..a8b7dcb 100644 --- a/build2/cc/link.cxx +++ b/build2/cc/link.cxx @@ -165,7 +165,7 @@ namespace build2 // If the prerequisite came from the lib{} group, then also // add it to lib's prerequisite_targets. // - if (!p.prerequisite.belongs (t)) + if (p.prerequisite.owner != t) t.group->prerequisite_targets.push_back (pt); t.prerequisite_targets.push_back (pt); @@ -487,7 +487,7 @@ namespace build2 // @@ Why are we creating the obj{} group if the source came from a // group? // - bool group (!p.prerequisite.belongs (t)); // Group's prerequisite. + bool group (p.prerequisite.owner != t); // Group's prerequisite. const prerequisite_key& cp (p.key ()); // C-source (X or C) key. const target_type& tt (group ? obj::static_type : ott); @@ -614,7 +614,7 @@ namespace build2 { // Note: add the source to the group, not the member. // - ot.prerequisites.emplace_back (p.as_prerequisite (trace)); + ot.prerequisites.push_back (p.as_prerequisite_for (ot)); // Add our lib*{} prerequisites to the object file (see the export.* // machinery for details). @@ -634,7 +634,7 @@ namespace build2 for (prerequisite& p: group_prerequisites (t)) { if (p.is_a () || p.is_a () || p.is_a ()) - ot.prerequisites.emplace_back (p); + ot.prerequisites.emplace_back (p, ot); } build2::match (a, *pt); diff --git a/build2/cli/rule.cxx b/build2/cli/rule.cxx index d457e6d..f5405a5 100644 --- a/build2/cli/rule.cxx +++ b/build2/cli/rule.cxx @@ -136,7 +136,7 @@ namespace build2 if (g == nullptr) g = &targets.insert (t.dir, t.out, t.name, trace); - g->prerequisites.emplace_back (p.as_prerequisite (trace)); + g->prerequisites.push_back (p.as_prerequisite_for (*g)); } else l4 ([&]{trace << ".cli file stem '" << p.name () << "' " diff --git a/build2/install/rule.cxx b/build2/install/rule.cxx index 036f01f..a727acc 100644 --- a/build2/install/rule.cxx +++ b/build2/install/rule.cxx @@ -49,7 +49,7 @@ namespace build2 { tracer trace ("install::alias_rule::apply"); - for (prerequisite p: group_prerequisites (t)) + for (prerequisite& p: group_prerequisites (t)) { target& pt (search (p)); diff --git a/build2/parser.cxx b/build2/parser.cxx index 9ce916e..7997d10 100644 --- a/build2/parser.cxx +++ b/build2/parser.cxx @@ -635,11 +635,28 @@ namespace build2 else attributes_pop (); - // Prepare the prerequisite list. + // First enter all the targets (normally we will have just one). // - target::prerequisites_type ps; - ps.reserve (pns.size ()); + small_vector, 1> tgs; + for (auto& tn: ns) + { + if (tn.qualified ()) + fail (nloc) << "project name in target " << tn; + + // @@ OUT TODO + // + enter_target tg (*this, move (tn), name (), nloc, trace); + + if (default_target_ == nullptr) + default_target_ = target_; + + target_->prerequisites.reserve (pns.size ()); + tgs.push_back (*target_); + } + + // Now enter each prerequisite into each target. + // for (auto& pn: pns) { optional e; @@ -653,8 +670,6 @@ namespace build2 if (!pn.dir.empty ()) pn.dir.normalize (false, true); - // Find or insert. - // // @@ OUT: for now we assume the prerequisite's out is // undetermined. The only way to specify an src prerequisite // will be with the explicit @-syntax. @@ -665,36 +680,20 @@ namespace build2 // natually suppress any searches by specifying the absolute // path. // - prerequisite& p ( - scope_->prerequisites.insert ( - pn.proj, - *ti, - move (pn.dir), - dir_path (), - move (pn.value), - move (e), - *scope_, - trace).first); - - ps.emplace_back (p); - } - - for (auto& tn: ns) - { - if (tn.qualified ()) - fail (nloc) << "project name in target " << tn; - - // @@ OUT TODO + prerequisite p (pn.proj, + *ti, + move (pn.dir), + dir_path (), + move (pn.value), + move (e), + tgs.back ()); + + // Move last prerequisite (which will normally be the only one). // - enter_target tg (*this, move (tn), name (), nloc, trace); - - //@@ OPT: move if last/single target (common cases). - // - target_->prerequisites.insert ( - target_->prerequisites.end (), ps.begin (), ps.end ()); - - if (default_target_ == nullptr) - default_target_ = target_; + for (target& t: tgs) + t.prerequisites.push_back (&t == &p.owner + ? move (p) + : prerequisite (p, t)); } } @@ -3559,7 +3558,7 @@ namespace build2 targets.find (dir::static_type, // Explicit current dir target. scope_->out_path (), dir_path (), // Out tree target. - "", + string (), nullopt, trace) != targets.end ()) return; @@ -3572,19 +3571,11 @@ namespace build2 targets.insert (dir::static_type, scope_->out_path (), dir_path (), - "", + string (), nullopt, trace).first); - prerequisite& p ( - scope_->prerequisites.insert ( - nullopt, - dt.key (), - *scope_, // Doesn't matter which scope since dir is absolute. - trace).first); - - p.target = &dt; - ct.prerequisites.emplace_back (p); + ct.prerequisites.emplace_back (dt, ct); } void parser:: diff --git a/build2/prerequisite b/build2/prerequisite index 60970d6..f951e0a 100644 --- a/build2/prerequisite +++ b/build2/prerequisite @@ -5,7 +5,6 @@ #ifndef BUILD2_PREREQUISITE #define BUILD2_PREREQUISITE -#include // hash #include #include @@ -22,6 +21,11 @@ namespace build2 // Light-weight (by being shallow-pointing) prerequisite key, similar // to (and based on) target key. // + // Note that unlike prerequisite, the key is not (necessarily) owned by a + // target. So for the key we instead have the base scope of the target that + // (would) own it. Note that we assume keys to be ephemeral enough for the + // base scope to remain unchanged. + // class prerequisite_key { public: @@ -38,52 +42,14 @@ namespace build2 bool is_a (const target_type& tt) const {return tk.is_a (tt);} }; - inline bool - operator== (const prerequisite_key& x, const prerequisite_key& y) - { - assert (x.scope == y.scope); - return x.proj == y.proj && x.tk == y.tk; - } - - inline bool - operator!= (const prerequisite_key& x, const prerequisite_key& y) - { - return !(x == y); - } - ostream& operator<< (ostream&, const prerequisite_key&); -} - - -namespace std -{ - // Note that we ignore the extension when calculating the hash because of - // its special "unspecified" logic (see target_key::operator==). - // - template <> - struct hash - { - using argument_type = build2::prerequisite_key; - using result_type = size_t; - - size_t - operator() (const build2::prerequisite_key& k) const noexcept - { - return build2::combine_hash (hash> () (k.proj), - hash () (k.tk)); - } - }; -} -namespace build2 -{ class prerequisite { public: typedef build2::target target_type; typedef build2::target_type target_type_type; - typedef build2::scope scope_type; // Note that unlike targets, for prerequisites an empty out directory // means undetermined rather than being definitely in the out tree. @@ -94,7 +60,9 @@ namespace build2 const dir_path out; // Empty, normalized absolute, or relative. const string name; const optional ext; // Absent if unspecified. - scope_type& scope; + + target_type& owner; // Target to which this prerequisite belongs. + target_type* target; // NULL if not yet resolved. Note that this // should always be the "primary target", not // a member of a target group. @@ -106,28 +74,40 @@ namespace build2 dir_path o, string n, optional e, - scope_type& s) + target_type& w) : proj (move (p)), type (t), dir (move (d)), out (move (o)), name (move (n)), ext (move (e)), - scope (s), + owner (w), target (nullptr) {} + // Make a copy for a new owner target. Note that both owner targets should + // be in the same scope. + // + prerequisite (const prerequisite&, target_type& owner); + + // Make a prerequisite from a target. + // + prerequisite (target_type&, target_type& owner); + + prerequisite (const prerequisite&) = delete; + prerequisite (prerequisite&&) = default; + + prerequisite& operator= (const prerequisite&) = delete; + prerequisite& operator= (prerequisite&&) = default; + // Note that the returned key "tracks" the prerequisite; that is, any // updates to the prerequisite's members will be reflected in the key. // prerequisite_key - key () const - { - return prerequisite_key {proj, {&type, &dir, &out, &name, ext}, &scope}; - } + key () const; - public: // Prerequisite (target) type. // + public: template bool is_a () const {return type.is_a ();} @@ -136,69 +116,11 @@ namespace build2 is_a (const target_type_type& tt) const {return type.is_a (tt);} }; - inline bool - operator== (const prerequisite& x, const prerequisite& y) - { - return x.key () == y.key (); - } - - inline bool - operator!= (const prerequisite& x, const prerequisite& y) - { - return !(x == y); - } - inline ostream& operator<< (ostream& os, const prerequisite& p) { return os << p.key (); } - -} - -namespace std -{ - template <> - struct hash - { - using argument_type = build2::prerequisite; - using result_type = size_t; - - size_t - operator() (const build2::prerequisite& p) const noexcept - { - return hash () (p.key ()); - } - }; -} - -namespace build2 -{ - // Set of prerequisites in a scope. - // - // Similar to targets, specified and unspecified extensions are considered - // equal and we may update the extension in the existing entry. To make - // this work we use a hash set. - // - struct prerequisite_set: std::unordered_set - { - pair - insert (optional proj, - const target_type&, - dir_path dir, - dir_path out, - string name, - optional ext, - scope&, - tracer&); - - pair - insert (optional proj, const target_key& tk, scope& s, tracer& t) - { - return insert ( - move (proj), *tk.type, *tk.dir, *tk.out, *tk.name, tk.ext, s, t); - } - }; } #endif // BUILD2_PREREQUISITE diff --git a/build2/prerequisite.cxx b/build2/prerequisite.cxx index bcd4123..469bdf9 100644 --- a/build2/prerequisite.cxx +++ b/build2/prerequisite.cxx @@ -5,7 +5,7 @@ #include #include -#include // target_type +#include #include #include @@ -48,53 +48,41 @@ namespace build2 return os << pk.tk; } - // prerequisite_set + // prerequisite // - auto prerequisite_set:: - insert (optional proj, - const target_type& tt, - dir_path dir, - dir_path out, - string name, - optional ext, - scope& s, - tracer& trace) -> pair + prerequisite:: + prerequisite (const prerequisite& p, target_type& w) + : proj (p.proj), + type (p.type), + dir (p.dir), + out (p.out), + name (p.name), + ext (p.ext), + owner (w), + target (nullptr) { - //@@ OPT: would be nice to somehow first check if this prerequisite is - // already in the set before allocating a new instance. Something with - // bounds and insert hints? - - // Find or insert. - // - auto r (emplace (move (proj), - tt, - move (dir), - move (out), - move (name), - ext, // Note: cannot move. - s)); - prerequisite& p (const_cast (*r.first)); - - // Update extension if the existing prerequisite has it unspecified. - // - if (p.ext != ext) - { - l5 ([&]{ - diag_record r (trace); - r << "assuming prerequisite " << p << " is the same as the " - << "one with "; - if (!ext) - r << "unspecified extension"; - else if (ext->empty ()) - r << "no extension"; - else - r << "extension " << *ext; - }); + assert (&w.base_scope () == &p.owner.base_scope ()); + } - if (ext) - const_cast&> (p.ext) = move (ext); - } + // Make a prerequisite from a target. + // + prerequisite:: + prerequisite (target_type& t, target_type& w) + : proj (nullopt), + type (t.type ()), + dir (t.dir), + out (t.out), // @@ If it's empty, then we treat as undetermined? + name (t.name), + ext (t.ext), + owner (w), + target (&t) + { + } - return pair (p, r.second); + prerequisite_key prerequisite:: + key () const + { + return prerequisite_key { + proj, {&type, &dir, &out, &name, ext}, &owner.base_scope ()}; } } diff --git a/build2/scope b/build2/scope index f22383a..eff60b0 100644 --- a/build2/scope +++ b/build2/scope @@ -15,7 +15,7 @@ #include #include -#include +#include #include #include #include @@ -184,18 +184,14 @@ namespace build2 // variable_type_map target_vars; - // Prerequisite cache. - // - public: - prerequisite_set prerequisites; - // Meta/operations supported by this project (set on the root // scope only). // + public: build2::meta_operations meta_operations; build2::operations operations; - typedef build2::path path_type; + using path_type = build2::path; // Set of buildfiles already loaded for this scope. The included // buildfiles are checked against the project's root scope while @@ -261,13 +257,13 @@ namespace build2 // NULL means no strong amalgamtion. }; - // Temporary scope. The idea is to be able to create a temporary - // scope in order not to change the variables in the current scope. - // Such a scope is not entered in to the scope map. As a result it - // can only be used as a temporary set of variables. In particular, - // defining targets/prerequisites directly in such a scope will surely - // end up badly. Defining any nested scopes will be as if defining - // such a scope in the parent (since path() returns parent's path). + // Temporary scope. The idea is to be able to create a temporary scope in + // order not to change the variables in the current scope. Such a scope is + // not entered in to the scope map. As a result it can only be used as a + // temporary set of variables. In particular, defining targetsdirectly in + // such a scope will surely end up badly. Defining any nested scopes will be + // as if defining such a scope in the parent (since path() returns parent's + // path). // class temp_scope: public scope { diff --git a/build2/target b/build2/target index 421c20a..a41c5b9 100644 --- a/build2/target +++ b/build2/target @@ -95,26 +95,6 @@ namespace build2 target_state group_action (action, target&); // Defined in . - // Prerequisite references as used in the target::prerequisites list - // below. - // - struct prerequisite_ref: reference_wrapper - { - typedef reference_wrapper base; - - using base::base; - - // Return true if this reference belongs to the target's prerequisite - // list. Note that this test only works if you use references to - // the container elements and the container hasn't been resized - // since such a reference was obtained. Normally this function is - // used when iterating over a combined prerequisites range (see - // group_prerequisites below). - // - bool - belongs (const target&) const; - }; - // A view of target group members. // struct group_view @@ -253,15 +233,6 @@ namespace build2 } public: - virtual - ~target (); - - target (const target&) = delete; - target& operator= (const target&) = delete; - - target (dir_path d, dir_path o, string n, optional e) - : dir (move (d)), out (move (o)), name (move (n)), ext (move (e)) {} - // Reset the target before matching it to a rule. The default // implementation clears the auxilary data and prerequisite_targets. // @@ -317,7 +288,7 @@ namespace build2 // Prerequisites. // public: - typedef vector prerequisites_type; + using prerequisites_type = small_vector; prerequisites_type prerequisites; // Targets to which prerequisites resolve for this recipe. Note @@ -566,10 +537,33 @@ namespace build2 virtual const target_type& dynamic_type () const = 0; static const target_type static_type; + public: + virtual + ~target (); + + target (const target&) = delete; + target& operator= (const target&) = delete; + + // The only way to create a target should be via the targets set below. + // + public: + friend class target_set; + + target (dir_path d, dir_path o, string n, optional e) + : dir (move (d)), out (move (o)), name (move (n)), ext (move (e)) {} + private: recipe_type recipe_; }; + // All targets are from the targets set below. + // + inline bool + operator== (const target& x, const target& y) {return &x == &y;} + + inline bool + operator!= (const target& x, const target& y) {return !(x == y);} + inline ostream& operator<< (ostream& os, const target& t) {return os << t.key ();} @@ -580,9 +574,9 @@ namespace build2 // come first followed by the member's. If you need to see them // in the other direction, iterate in reverse, for example: // - // for (prerequisite_ref& pr: group_prerequisites (t)) + // for (prerequisite& p: group_prerequisites (t)) // - // for (prerequisite_ref& pr: reverse_iterate (group_prerequisites (t)) + // for (prerequisite& p: reverse_iterate (group_prerequisites (t)) // // Note that in this case the individual elements of each list will // also be traversed in reverse, but that's what you usually want, @@ -708,7 +702,7 @@ namespace build2 using prerequisite_type = build2::prerequisite; using target_type_type = build2::target_type; - prerequisite_ref& prerequisite; + prerequisite_type& prerequisite; target_type* target; template @@ -717,35 +711,33 @@ namespace build2 { return target != nullptr ? target->is_a () != nullptr - : prerequisite.get ().is_a (); + : prerequisite.is_a (); } bool is_a (const target_type_type& tt) const { - return target != nullptr - ? target->is_a (tt) - : prerequisite.get ().is_a (tt); + return target != nullptr ? target->is_a (tt) : prerequisite.is_a (tt); } prerequisite_key key () const { return target != nullptr - ? prerequisite_key {prerequisite.get ().proj, target->key (), nullptr} - : prerequisite.get ().key (); + ? prerequisite_key {prerequisite.proj, target->key (), nullptr} + : prerequisite.key (); } const target_type_type& type () const { - return target != nullptr ? target->type () : prerequisite.get ().type; + return target != nullptr ? target->type () : prerequisite.type; } const string& name () const { - return target != nullptr ? target->name : prerequisite.get ().name; + return target != nullptr ? target->name : prerequisite.name; } const optional& @@ -755,7 +747,7 @@ namespace build2 // return target != nullptr ? prerequisite_key::nullproj - : prerequisite.get ().proj; + : prerequisite.proj; } target_type& @@ -764,8 +756,13 @@ namespace build2 return target != nullptr ? *target : build2::search (prerequisite); } - prerequisite_type& - as_prerequisite (tracer&) const; + // Return as a new prerequisite instance for the specified owner target. + // Note that if this is a prerequisite, then both owners should be in the + // same scope (not a requirement if this is a target because then its path + // will be absolute). + // + prerequisite_type + as_prerequisite_for (target_type& owner) const; }; // It is often stored as the target's auxiliary data so make sure there is @@ -835,7 +832,7 @@ namespace build2 iterator (const prerequisite_members_range* r, const base_iterator& i) : r_ (r), i_ (i), g_ {nullptr, 0}, k_ (nullptr) { - if (r_->members_ && i_ != r_->e_ && i_->get ().type.see_through) + if (r_->members_ && i_ != r_->e_ && i_->type.see_through) switch_mode (); } diff --git a/build2/target.ixx b/build2/target.ixx index 2d4fff8..9c2c838 100644 --- a/build2/target.ixx +++ b/build2/target.ixx @@ -4,32 +4,20 @@ namespace build2 { - // prerequisite_ref - // - inline bool prerequisite_ref:: - belongs (const target& t) const - { - const auto& p (t.prerequisites); - return !(p.empty () || this < &p.front () || this > &p.back ()); - } - // prerequisite_member // - inline prerequisite& prerequisite_member:: - as_prerequisite (tracer& trace) const + inline prerequisite prerequisite_member:: + as_prerequisite_for (target_type& owner) const { if (target == nullptr) - return prerequisite; + return prerequisite_type (prerequisite, owner); // An ad hoc group member cannot be used as a prerequisite (use the whole // group instead). // assert (!target->adhoc_member ()); - // The use of the group's prerequisite scope is debatable. - // - scope& s (prerequisite.get ().scope); - return s.prerequisites.insert (nullopt, key ().tk, s, trace).first; + return prerequisite_type (*target, owner); } // prerequisite_members @@ -50,7 +38,7 @@ namespace build2 // target* t (g_.count != 0 ? j_ != 0 ? g_.members[j_ - 1] : nullptr // enter_group() - : i_->get ().target); + : i_->target); if (t != nullptr && t->member != nullptr) k_ = t->member; } @@ -66,7 +54,7 @@ namespace build2 { ++i_; - if (r_->members_ && i_ != r_->e_ && i_->get ().type.see_through) + if (r_->members_ && i_ != r_->e_ && i_->type.see_through) switch_mode (); } @@ -82,7 +70,7 @@ namespace build2 // target* t (g_.count != 0 ? j_ != 0 ? g_.members[j_ - 1] : nullptr - : i_->get ().target); + : i_->target); if (t != nullptr && t->member != nullptr) k_ = t->member; @@ -117,7 +105,7 @@ namespace build2 { target* t (g_.count != 0 ? j_ != 0 ? g_.members[j_ - 1] : nullptr - : i_->get ().target); + : i_->target); if (t != nullptr && t->member != nullptr) k_ = t->member; } diff --git a/build2/target.txx b/build2/target.txx index 66acfb8..b72af7d 100644 --- a/build2/target.txx +++ b/build2/target.txx @@ -27,7 +27,7 @@ namespace build2 break; } } - while (++i_ != r_->e_ && i_->get ().type.see_through); + while (++i_ != r_->e_ && i_->type.see_through); } // diff --git a/build2/test/common.cxx b/build2/test/common.cxx index afd52e6..66be9d8 100644 --- a/build2/test/common.cxx +++ b/build2/test/common.cxx @@ -143,7 +143,7 @@ namespace build2 t.name == n->value && // Name matches. tt.name == n->type && // Target type matches. d == n->dir && // Directory matches. - &search (*n, *root_) == &t; + search (*n, *root_) == t; if (r) break; @@ -190,7 +190,7 @@ namespace build2 t.name == n->value && tt.name == n->type && d == n->dir && - &search (*n, *root_) == &t; + search (*n, *root_) == t; if (!r) continue; // Not our target. -- cgit v1.1