From fefe0657f29b8db782f7a722dd46b074b991cf08 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 23 Feb 2015 15:56:03 +0200 Subject: Redo rule match/build logic Now the rule is fully responsible for searching, matching, and building of prerequisites. --- build/algorithm | 46 ++++++++- build/algorithm.cxx | 141 ++++++++++++++++++++++------ build/algorithm.ixx | 16 ++++ build/algorithm.txx | 59 ++++++++++++ build/b.cxx | 79 +--------------- build/buildfile | 4 +- build/context | 14 +-- build/context.cxx | 20 +--- build/cxx/rule.cxx | 247 ++++++++++++++++++++----------------------------- build/cxx/target.cxx | 60 +++++++++--- build/diagnostics | 24 ++++- build/diagnostics.cxx | 19 ++++ build/key-set | 41 ++++++++ build/native.cxx | 20 +++- build/parser.cxx | 12 +-- build/prerequisite.cxx | 4 +- build/rule.cxx | 70 +++++++------- build/search | 31 +++++++ build/search.cxx | 144 ++++++++++++++++++++++++++++ build/target | 74 ++++++++++----- build/target.cxx | 162 ++++++++++++++++++++++++-------- build/types | 20 ++++ 22 files changed, 891 insertions(+), 416 deletions(-) create mode 100644 build/algorithm.ixx create mode 100644 build/algorithm.txx create mode 100644 build/key-set create mode 100644 build/search create mode 100644 build/search.cxx create mode 100644 build/types (limited to 'build') diff --git a/build/algorithm b/build/algorithm index a3b0db9..82913ad 100644 --- a/build/algorithm +++ b/build/algorithm @@ -5,16 +5,58 @@ #ifndef BUILD_ALGORITHM #define BUILD_ALGORITHM +#include +#include + namespace build { - class target; class prerequisite; + // The default prerequsite search implementation. It first calls the + // target-type-specific search function. If that doesn't yeld anything, + // it creates a new target. + // target& search (prerequisite&); - bool + // Match a rule to the target with ambiguity detection. + // + void match (target&); + + // The default prerequisite search and match implementation. It calls + // search() and then match() for each prerequisite in a loop. + // + void + search_and_match (target&); + + target_state + update (target&); + + // The default prerequisite update implementation. It calls update() + // for each prerequisite in a loop. Returns target_state::updated + // if any of them were updated and target_state::uptodate otherwise. + // + target_state + update_prerequisites (target&); + + // A version of the above that also determines whether the target + // needs updating based on the passed timestamp. + // + bool + update_prerequisites (target&, const timestamp&); + + // Another version of the above that does two extra things for the + // caller: it determines whether the target needs updating based + // on the passed timestamp and, if so, finds a prerequisite of the + // specified type. + // + template + T* + update_prerequisites (target&, const timestamp&); } +#include +#include + #endif // BUILD_ALGORITHM diff --git a/build/algorithm.cxx b/build/algorithm.cxx index 9d1a6fa..5026782 100644 --- a/build/algorithm.cxx +++ b/build/algorithm.cxx @@ -13,6 +13,7 @@ #include #include #include +#include #include #include @@ -23,37 +24,17 @@ namespace build target& search (prerequisite& p) { - tracer trace ("search"); - assert (p.target == nullptr); - //@@ TODO for now we just default to the directory scope. - // - path d; - if (p.dir.absolute ()) - d = p.dir; // Already normalized. - else - { - d = p.scope.path () / p.dir; - d.normalize (); - } - - // Find or insert. - // - auto r (targets.insert (p.type, move (d), p.name, p.ext, trace)); - - level4 ([&]{trace << (r.second ? "new" : "existing") << " target " - << r.first << " for prerequsite " << p;}); + if (target* t = p.type.search (p)) + return *t; - p.target = &r.first; - return r.first; + return create_new_target (p); } - bool - match (target& t) + void + match_impl (target& t) { - assert (!t.recipe ()); - for (auto tt (&t.type ()); tt != nullptr && !t.recipe (); tt = tt->base) @@ -131,6 +112,14 @@ namespace build if (!ambig) { + auto g ( + make_exception_guard ( + [](target& t, const string& n) + { + info << "while selecting rule " << n << " for target " << t; + }, + t, n)); + t.recipe (ru.select (t, m)); break; } @@ -140,6 +129,106 @@ namespace build } } - return bool (t.recipe ()); + if (!t.recipe ()) + fail << "no rule to update target " << t; + } + + void + search_and_match (target& t) + { + for (prerequisite& p: t.prerequisites) + { + if (p.target == nullptr) + search (p); + + match (*p.target); + } + } + + target_state + update (target& t) + { + // Implementation with some multi-threading ideas in mind. + // + switch (target_state ts = t.state ()) + { + case target_state::unknown: + { + t.state (target_state::failed); // So the rule can just throw. + + auto g ( + make_exception_guard ( + [](target& t){info << "while updating target " << t;}, + t)); + + ts = t.recipe () (t); + assert (ts != target_state::unknown && ts != target_state::failed); + t.state (ts); + return ts; + } + case target_state::uptodate: + case target_state::updated: + return ts; + case target_state::failed: + throw failed (); + } + } + + target_state + update_prerequisites (target& t) + { + target_state ts (target_state::uptodate); + + for (const prerequisite& p: t.prerequisites) + { + assert (p.target != nullptr); + + if (update (*p.target) != target_state::uptodate) + ts = target_state::updated; + } + + return ts; + } + + bool + update_prerequisites (target& t, const timestamp& mt) + { + bool u (mt == timestamp_nonexistent); + + for (const prerequisite& p: t.prerequisites) + { + assert (p.target != nullptr); + target& pt (*p.target); + + target_state ts (update (pt)); + + if (!u) + { + // If this is an mtime-based target, then compare timestamps. + // + if (auto mpt = dynamic_cast (&pt)) + { + timestamp mp (mpt->mtime ()); + + // What do we do if timestamps are equal? This can happen, for + // example, on filesystems that don't have subsecond resolution. + // There is not much we can do here except detect the case where + // the prerequisite was updated in this run which means the + // target must be out of date. + // + if (mt < mp || mt == mp && ts == target_state::updated) + u = true; + } + else + { + // Otherwise we assume the prerequisite is newer if it was updated. + // + if (ts == target_state::updated) + u = true; + } + } + } + + return u; } } diff --git a/build/algorithm.ixx b/build/algorithm.ixx new file mode 100644 index 0000000..02c223c --- /dev/null +++ b/build/algorithm.ixx @@ -0,0 +1,16 @@ +// file : build/algorithm.ixx -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +namespace build +{ + void + match_impl (target&); + + inline void + match (target& t) + { + if (!t.recipe ()) + match_impl (t); + } +} diff --git a/build/algorithm.txx b/build/algorithm.txx new file mode 100644 index 0000000..9086bfe --- /dev/null +++ b/build/algorithm.txx @@ -0,0 +1,59 @@ +// file : build/algorithm.txx -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +namespace build +{ + template + T* + update_prerequisites (target& t, const timestamp& mt) + { + //@@ Can factor the bulk of it into a non-template code. Can + // either do a function template that will do dynamic_cast check + // or can scan the target type info myself. I think latter. + // + + T* r (nullptr); + bool u (mt == timestamp_nonexistent); + + for (const prerequisite& p: t.prerequisites) + { + assert (p.target != nullptr); + target& pt (*p.target); + + target_state ts (update (pt)); + + if (!u) + { + // If this is an mtime-based target, then compare timestamps. + // + if (auto mpt = dynamic_cast (&pt)) + { + timestamp mp (mpt->mtime ()); + + // What do we do if timestamps are equal? This can happen, for + // example, on filesystems that don't have subsecond resolution. + // There is not much we can do here except detect the case where + // the prerequisite was updated in this run which means the + // target must be out of date. + // + if (mt < mp || mt == mp && ts == target_state::updated) + u = true; + } + else + { + // Otherwise we assume the prerequisite is newer if it was updated. + // + if (ts == target_state::updated) + u = true; + } + } + + if (r == nullptr) + r = dynamic_cast (&pt); + } + + assert (r != nullptr); + return u ? r : nullptr; + } +} diff --git a/build/b.cxx b/build/b.cxx index c9322a0..a71a866 100644 --- a/build/b.cxx +++ b/build/b.cxx @@ -34,76 +34,6 @@ using namespace std; namespace build { - bool - match_recursive (target& t) - { - // Because we match the target first and then prerequisites, - // any additional dependency information injected by the rule - // will be covered as well. - // - if (!t.recipe ()) - { - if (!match (t)) - { - error << "no rule to update target " << t; - return false; - } - } - - for (prerequisite& p: t.prerequisites) - { - // Resolve prerequisite to target (prerequisite search). We - // do this after matching since the rule can alter search - // paths. - // - if (p.target == nullptr) - search (p); - - if (!match_recursive (*p.target)) - { - info << "required by " << t; - return false; - } - } - - return true; - } - - target_state - update (target& t) - { - assert (t.state () == target_state::unknown); - - auto g ( - make_exception_guard ( - [](target& t){info << "while building target " << t;}, - t)); - - for (prerequisite& p: t.prerequisites) - { - target& pt (*p.target); - - if (pt.state () == target_state::unknown) - { - target_state ts (update (pt)); - - if (ts == target_state::failed) - return ts; - } - } - - // @@ Why do we indicate failure via code rather than throw? Now - // there is no diagnostics via exception_guard above. - - const recipe& r (t.recipe ()); - - target_state ts (r (t)); - - assert (ts != target_state::unknown); - t.state (ts); - return ts; - } - void dump () { @@ -125,7 +55,6 @@ namespace build cout << endl; } - } #include @@ -261,14 +190,11 @@ main (int argc, char* argv[]) // Build. // if (default_target == nullptr) - { fail << "no default target"; - } target& d (*default_target); - if (!match_recursive (d)) - return 1; // Diagnostics has already been issued. + match (d); dump (); @@ -282,9 +208,6 @@ main (int argc, char* argv[]) case target_state::updated: break; case target_state::failed: - { - fail << "failed to update target " << d; - } case target_state::unknown: assert (false); } diff --git a/build/buildfile b/build/buildfile index 819f2e4..14f1063 100644 --- a/build/buildfile +++ b/build/buildfile @@ -1,3 +1,3 @@ exe{b1}: cxx{b algorithm scope parser lexer target prerequisite rule \ - native context diagnostics cxx/target cxx/rule process timestamp path \ - utility} + native context search diagnostics cxx/target cxx/rule process timestamp \ + path utility} diff --git a/build/context b/build/context index 05f0094..c177603 100644 --- a/build/context +++ b/build/context @@ -34,19 +34,7 @@ namespace build // the work directory. // path - translate (const path&); - - // In addition to calling translate() above, this function also uses - // shorter notations such as ~/. - // - std::string - diagnostic_string (const path&); - - inline std::ostream& - operator<< (std::ostream& os, const path& p) - { - return os << diagnostic_string (p); - } + relative_work (const path&); } #endif // BUILD_CONTEXT diff --git a/build/context.cxx b/build/context.cxx index 4d1d1e4..79753ec 100644 --- a/build/context.cxx +++ b/build/context.cxx @@ -35,7 +35,7 @@ namespace build } path - translate (const path& p) + relative_work (const path& p) { if (p.sub (work)) return p.leaf (work); @@ -49,22 +49,4 @@ namespace build return p; } - - std::string - diagnostic_string (const path& p) - { - if (p.absolute ()) - { - path rp (translate (p)); - -#ifndef _WIN32 - if (rp.absolute () && rp.sub (home)) - return "~/" + rp.leaf (home).string (); -#endif - - return rp.string (); - } - - return p.string (); - } } diff --git a/build/cxx/rule.cxx b/build/cxx/rule.cxx index 1c7d992..b355542 100644 --- a/build/cxx/rule.cxx +++ b/build/cxx/rule.cxx @@ -35,15 +35,11 @@ namespace build // @@ TODO: // // - check prerequisites: single source file - // - check prerequisites: the rest are headers (issue warning at v=1?) - // - if path already assigned, verify extension + // - check prerequisites: the rest are headers (other ignorable?) + // - if path already assigned, verify extension? // // @@ Q: // - // - if there is no .cxx, are we going to check if the one derived - // from target exist or can be built? If we do that, then it - // probably makes sense to try other rules first (two passes). - // // - Wouldn't it make sense to cache source file? Careful: unloading // of dependency info. // @@ -70,25 +66,18 @@ namespace build if (o.path ().empty ()) o.path (o.dir / path (o.name + ".o")); - // Resolve prerequisite to target and match it to a rule. We need - // this in order to get the source file path for prerequisite - // injections. + // Search and match all the existing prerequisites. The injection + // code (below) takes care of the ones it is adding. // - prerequisite* sp (static_cast (v)); - cxx* st ( - dynamic_cast ( - sp->target != nullptr ? sp->target : &search (*sp))); + search_and_match (t); - if (st != nullptr) - { - if (st->recipe () || build::match (*st)) - { - // Don't bother if the file does not exist. - // - if (st->mtime () != timestamp_nonexistent) - inject_prerequisites (o, *st, sp->scope); - } - } + // Inject additional prerequisites. + // + auto& sp (*static_cast (v)); + auto& st (dynamic_cast (*sp.target)); + + if (st.mtime () != timestamp_nonexistent) + inject_prerequisites (o, st, sp.scope); return &update; } @@ -141,7 +130,8 @@ namespace build tracer trace ("cxx::compile::inject_prerequisites"); // We are using absolute source file path in order to get - // absolute paths in the result. + // absolute paths in the result. @@ We will also have to + // use absolute -I paths to guarantee that. // const char* args[] = { "g++-4.9", @@ -191,18 +181,12 @@ namespace build while (pos != l.size ()) { - path file (next (l, pos)); - file.normalize (); + path f (next (l, pos)); + f.normalize (); - level5 ([&]{trace << "prerequisite path: " << file.string ();}); + assert (f.absolute ()); // Logic below depends on this. - // If there is no extension (e.g., standard C++ headers), - // then assume it is a header. Otherwise, let the standard - // mechanism derive the type from the extension. - // - - // @@ TODO: - // + level5 ([&]{trace << "prerequisite path: " << f.string ();}); // Split the name into its directory part, the name part, and // extension. Here we can assume the name part is a valid @@ -212,27 +196,37 @@ namespace build // extension rather than NULL (which would signify that the // extension needs to be added). // - path d (file.directory ()); - string n (file.leaf ().base ().string ()); - const char* es (file.extension ()); + path d (f.directory ()); + string n (f.leaf ().base ().string ()); + const char* es (f.extension ()); const string* e (&extension_pool.find (es != nullptr ? es : "")); - // Find or insert. + // Find or insert prerequisite. + // + // If there is no extension (e.g., standard C++ headers), + // then assume it is a header. Otherwise, let the standard + // mechanism derive the type from the extension. @@ TODO. // prerequisite& p ( ds.prerequisites.insert ( hxx::static_type, move (d), move (n), e, ds, trace).first); - // Resolve to target so that we can assign its path. + o.prerequisites.push_back (p); + + // Resolve to target. // path_target& t ( dynamic_cast ( p.target != nullptr ? *p.target : search (p))); + // Assign path. + // if (t.path ().empty ()) - t.path (move (file)); + t.path (move (f)); - o.prerequisites.push_back (p); + // Match to a rule. + // + build::match (t); } } @@ -260,48 +254,16 @@ namespace build update (target& t) { obj& o (dynamic_cast (t)); - timestamp mt (o.mtime ()); - - bool u (mt == timestamp_nonexistent); - const cxx* s (nullptr); + cxx* s (update_prerequisites (o, o.mtime ())); - for (const prerequisite& p: t.prerequisites) - { - const target& pt (*p.target); - - // Assume all our prerequisites are mtime-based (checked in - // match()). - // - if (!u) - { - const auto& mtp (dynamic_cast (pt)); - timestamp mp (mtp.mtime ()); - - // What do we do if timestamps are equal? This can happen, for - // example, on filesystems that don't have subsecond resolution. - // There is not much we can do here except detect the case where - // the prerequisite was updated in this run which means the - // target must be out of date. - // - if (mt < mp || mt == mp && mtp.state () == target_state::updated) - u = true; - } - - if (s == nullptr) - s = dynamic_cast (&pt); - - if (u && s != nullptr) - break; - } - - if (!u) + if (s == nullptr) return target_state::uptodate; // Translate paths to relative (to working directory) ones. This // results in easier to read diagnostics. // - path ro (translate (o.path ())); - path rs (translate (s->path ())); + path ro (relative_work (o.path ())); + path rs (relative_work (s->path ())); const char* args[] = { "g++-4.9", @@ -323,7 +285,7 @@ namespace build process pr (args); if (!pr.wait ()) - return target_state::failed; + throw failed (); // Should we go to the filesystem and get the new mtime? We // know the file has been modified, so instead just use the @@ -344,7 +306,7 @@ namespace build if (e.child ()) exit (1); - return target_state::failed; + throw failed (); } } @@ -358,14 +320,14 @@ namespace build // @@ TODO: // // - check prerequisites: object files, libraries - // - if path already assigned, verify extension + // - if path already assigned, verify extension? // // @@ Q: // // - if there is no .o, are we going to check if the one derived - // from target exist or can be built? If we do that, then it - // probably makes sense to try other rules first (two passes). + // from target exist or can be built? A: No. // What if there is a library. Probably ok if .a, not if .so. + // (i.e., a utility library). // // Scan prerequisites and see if we can work with what we've got. @@ -374,7 +336,7 @@ namespace build for (prerequisite& p: t.prerequisites) { - if (p.type.id == typeid (cxx)) + if (p.type.id == typeid (cxx)) // @@ Should use is_a (add to p.type). { if (!seen_cxx) seen_cxx = true; @@ -396,8 +358,8 @@ namespace build } } - // We will only chain C source if there is also C++ source or we - // we explicitly asked to. + // We will only chain a C source if there is also a C++ source or we + // we explicitly told to. // if (seen_c && !seen_cxx && hint < "cxx") { @@ -420,20 +382,27 @@ namespace build if (e.path ().empty ()) e.path (e.dir / path (e.name)); - // Do rule chaining for C and C++ source files. - // - // @@ OPT: match() could indicate whether this is necesssary. + // Process prerequisited: do rule chaining for C and C++ source + // files as well as search and match. // for (auto& pr: t.prerequisites) { - prerequisite& cp (pr); + prerequisite& p (pr); + + if (p.type.id != typeid (c) && p.type.id != typeid (cxx)) + { + if (p.target == nullptr) + search (p); - if (cp.type.id != typeid (c) && cp.type.id != typeid (cxx)) + build::match (*p.target); continue; + } + + prerequisite& cp (p); // Come up with the obj{} prerequisite. The c(xx){} prerequisite // directory can be relative (to the scope) or absolute. If it is - // relative, then we use it as is. If it is absolute, then translate + // relative, then use it as is. If it is absolute, then translate // it to the corresponding directory under out_root. While the // c(xx){} directory is most likely under src_root, it is also // possible it is under out_root (e.g., generated source). @@ -444,10 +413,8 @@ namespace build else { if (!cp.dir.sub (src_root)) - { fail << "out of project prerequisite " << cp << info << "specify corresponding obj{} target explicitly"; - } d = out_root / cp.dir.leaf (src_root); } @@ -466,9 +433,19 @@ namespace build target& ot (search (op)); // If this target already exists, then it needs to be "compatible" - // with what we doing. + // with what we are doing here. // - bool add (true); + // This gets a bit tricky. We need to make sure the source files + // are the same which we can only do by comparing the targets to + // which they resolve. But we cannot search the ot's prerequisites + // -- only the rule that matches can. Note, however, that if all + // this works out, then our next step is to search and match the + // re-written prerequisite (which points to ot). If things don't + // work out, then we fail, in which case searching and matching + // speculatively doesn't really hurt. + // + // + prerequisite* cp1 (nullptr); for (prerequisite& p: ot.prerequisites) { // Ignore some known target types (headers). @@ -481,35 +458,35 @@ namespace build if (p.type.id == typeid (cxx)) { - // We need to make sure they are the same which we can only - // do by comparing the targets to which they resolve. - // - target* t (p.target != nullptr ? p.target : &search (p)); - target* ct (cp.target != nullptr ? cp.target : &search (cp)); - - if (t == ct) - { - add = false; - continue; // Check the rest of the prerequisites. - } + cp1 = &p; // Check the rest of the prerequisites. + continue; } - diag_record r; + fail << "synthesized target for prerequisite " << cp + << " would be incompatible with existing target " << ot << + info << "unknown existing prerequsite type " << p << + info << "specify corresponding obj{} target explicitly"; + } - r << fail << "synthesized target for prerequisite " << cp - << " would be incompatible with existing target " << ot; + if (cp1 != nullptr) + { + build::match (ot); // Now cp1 should be resolved. - if (p.type.id == typeid (cxx)) - r << info << "existing prerequsite " << p << " does not " - << "match " << cp; - else - r << info << "unknown existing prerequsite " << p; + if (cp.target == nullptr) + search (cp); // Our own prerequisite, so this is ok. - r << info << "specify corresponding obj{} target explicitly"; + if (cp.target != cp1->target) + fail << "synthesized target for prerequisite " << cp + << " would be incompatible with existing target " << ot << + info << "existing prerequsite " << *cp1 << " does not " + << "match " << cp << + info << "specify corresponding obj{} target explicitly"; } - - if (add) + else + { ot.prerequisites.push_back (cp); + build::match (ot); + } // Change the exe{} target's prerequsite from cxx{} to obj{}. // @@ -528,40 +505,14 @@ namespace build // exe& e (dynamic_cast (t)); - timestamp mt (e.mtime ()); - - bool u (mt == timestamp_nonexistent); - - for (const prerequisite& p: t.prerequisites) - { - const target& pt (*p.target); - // Assume all our prerequisites are mtime-based (checked in - // match()). - // - const auto& mtp (dynamic_cast (pt)); - timestamp mp (mtp.mtime ()); - - // What do we do if timestamps are equal? This can happen, for - // example, on filesystems that don't have subsecond resolution. - // There is not much we can do here except detect the case where - // the prerequisite was updated in this run which means the - // target must be out of date. - // - if (mt < mp || mt == mp && mtp.state () == target_state::updated) - { - u = true; - break; - } - } - - if (!u) + if (!update_prerequisites (e, e.mtime ())) return target_state::uptodate; // Translate paths to relative (to working directory) ones. This // results in easier to read diagnostics. // - path re (translate (e.path ())); + path re (relative_work (e.path ())); vector ro; vector args {"g++-4.9", "-std=c++14", "-g", "-o"}; @@ -571,7 +522,7 @@ namespace build for (const prerequisite& p: t.prerequisites) { const obj& o (dynamic_cast (*p.target)); - ro.push_back (translate (o.path ())); + ro.push_back (relative_work (o.path ())); args.push_back (ro.back ().string ().c_str ()); } @@ -587,7 +538,7 @@ namespace build process pr (args.data ()); if (!pr.wait ()) - return target_state::failed; + throw failed (); // Should we go to the filesystem and get the new mtime? We // know the file has been modified, so instead just use the @@ -608,7 +559,7 @@ namespace build if (e.child ()) exit (1); - return target_state::failed; + throw failed (); } } } diff --git a/build/cxx/target.cxx b/build/cxx/target.cxx index f57c963..ad676dd 100644 --- a/build/cxx/target.cxx +++ b/build/cxx/target.cxx @@ -10,22 +10,58 @@ namespace build { namespace cxx { - const target_type hxx::static_type { - typeid (hxx), "hxx", &file::static_type, &target_factory}; + const target_type hxx::static_type + { + typeid (hxx), + "hxx", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type ixx::static_type { - typeid (ixx), "ixx", &file::static_type, &target_factory}; + const target_type ixx::static_type + { + typeid (ixx), + "ixx", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type txx::static_type { - typeid (txx), "txx", &file::static_type, &target_factory}; + const target_type txx::static_type + { + typeid (txx), + "txx", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type cxx::static_type { - typeid (cxx), "cxx", &file::static_type, &target_factory}; + const target_type cxx::static_type + { + typeid (cxx), + "cxx", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type h::static_type { - typeid (h), "h", &file::static_type, &target_factory}; + const target_type h::static_type + { + typeid (h), + "h", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type c::static_type { - typeid (c), "c", &file::static_type, &target_factory}; + const target_type c::static_type + { + typeid (c), + "c", + &file::static_type, + &target_factory, + file::static_type.search + }; } } diff --git a/build/diagnostics b/build/diagnostics index 7e56fa3..e61295a 100644 --- a/build/diagnostics +++ b/build/diagnostics @@ -14,8 +14,27 @@ #include #include +#include + namespace build { + // Throw this exception to terminate the build. The handler should + // assume that the diagnostics has already been issued. + // + class failed: public std::exception {}; + + // In addition to calling relative_work(), this function also uses + // shorter notations such as ~/. + // + std::string + diag_relative_work (const path&); + + inline std::ostream& + operator<< (std::ostream& os, const path& p) + { + return os << diag_relative_work (p); + } + // Print process commmand line. // void @@ -27,11 +46,6 @@ namespace build print_process (args.data ()); } - // Throw this exception to terminate the build. The handler should - // assume that the diagnostics has already been issued. - // - class failed: public std::exception {}; - // Trace verbosity level. // // 1 - command lines to update explicit targets (e.g., .o) diff --git a/build/diagnostics.cxx b/build/diagnostics.cxx index 6b524a5..e2e8b95 100644 --- a/build/diagnostics.cxx +++ b/build/diagnostics.cxx @@ -6,12 +6,31 @@ #include +#include #include using namespace std; namespace build { + string + diag_relative_work (const path& p) + { + if (p.absolute ()) + { + path rp (relative_work (p)); + +#ifndef _WIN32 + if (rp.absolute () && rp.sub (home)) + return "~/" + rp.leaf (home).string (); +#endif + + return rp.string (); + } + + return p.string (); + } + void print_process (const char* const* args) { diff --git a/build/key-set b/build/key-set new file mode 100644 index 0000000..9cb7d6c --- /dev/null +++ b/build/key-set @@ -0,0 +1,41 @@ +// file : build/key_set -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef BUILD_KEY_SET +#define BUILD_KEY_SET + +namespace build +{ + // Google the "Emulating Boost.MultiIndex with Standard Containers" blog + // post for deatils. + // + + template + struct set_key + { + mutable const T* p; + + set_key (const T* v = 0): p (v) {} + bool operator< (const set_key& x) const {return *p < *x.p;} + }; + + template + struct map_iterator_adapter: I + { + typedef const typename I::value_type::second_type value_type; + typedef value_type* pointer; + typedef value_type& reference; + + map_iterator_adapter () {} + map_iterator_adapter (I i): I (i) {} + + map_iterator_adapter& + operator= (I i) {static_cast (*this) = i; return *this;} + + reference operator* () const {return I::operator* ().second;} + pointer operator-> () const {return &I::operator-> ()->second;} + }; +} + +#endif // BUILD_KEY_SET diff --git a/build/native.cxx b/build/native.cxx index 61ecb72..8d58e66 100644 --- a/build/native.cxx +++ b/build/native.cxx @@ -8,9 +8,21 @@ using namespace std; namespace build { - const target_type exe::static_type { - typeid (exe), "exe", &file::static_type, &target_factory}; + const target_type exe::static_type + { + typeid (exe), + "exe", + &file::static_type, + &target_factory, + file::static_type.search + }; - const target_type obj::static_type { - typeid (obj), "obj", &file::static_type, &target_factory}; + const target_type obj::static_type + { + typeid (obj), + "obj", + &file::static_type, + &target_factory, + file::static_type.search + }; } diff --git a/build/parser.cxx b/build/parser.cxx index f2b7a3f..5102c60 100644 --- a/build/parser.cxx +++ b/build/parser.cxx @@ -53,8 +53,8 @@ namespace build void parser:: parse (istream& is, const path& p, scope& s) { - string ds (diagnostic_string (p)); - path_ = &ds; + string rw (diag_relative_work (p)); + path_ = &rw; lexer l (is, p.string ()); lexer_ = &l; @@ -403,9 +403,9 @@ namespace build level4 ([&]{trace (t) << "entering " << p;}); - string ds (diagnostic_string (p)); + string rw (diag_relative_work (p)); const string* op (path_); - path_ = &ds; + path_ = &rw; lexer l (ifs, p.string ()); lexer* ol (lexer_); @@ -475,9 +475,9 @@ namespace build level4 ([&]{trace (t) << "entering " << p;}); - string ds (diagnostic_string (p)); + string rw (diag_relative_work (p)); const string* op (path_); - path_ = &ds; + path_ = &rw; lexer l (ifs, p.string ()); lexer* ol (lexer_); diff --git a/build/prerequisite.cxx b/build/prerequisite.cxx index 84fb869..debafe6 100644 --- a/build/prerequisite.cxx +++ b/build/prerequisite.cxx @@ -28,7 +28,7 @@ namespace build // if (!p.dir.absolute ()) { - string s (diagnostic_string (p.scope.path ())); + string s (diag_relative_work (p.scope.path ())); if (!s.empty ()) os << s << path::traits::directory_separator << ": "; @@ -38,7 +38,7 @@ namespace build // if (!p.dir.empty ()) { - string s (diagnostic_string (p.dir)); + string s (diag_relative_work (p.dir)); if (!s.empty ()) os << s << path::traits::directory_separator; diff --git a/build/rule.cxx b/build/rule.cxx index b00901e..2373033 100644 --- a/build/rule.cxx +++ b/build/rule.cxx @@ -6,6 +6,7 @@ #include // move() +#include #include using namespace std; @@ -21,21 +22,16 @@ namespace build { // @@ TODO: // - // - need to assign path somehow. Get (potentially several) - // extensions from target type? Maybe target type should - // generate a list of potential paths that we can try here. - // What if none of them exist, which one do we use? Should - // there be a default extension, perhaps configurable via - // a variable? + // - need to try all the target-type-specific extensions, just + // like search_existing_file(). // - path_target& pt (dynamic_cast (t)); if (pt.path ().empty ()) { path p (t.dir / path (pt.name)); - // @@ TMP: derive file name by appending target name as an extension? + // @@ TMP: target name as an extension. // const string& e (pt.ext != nullptr ? *pt.ext : pt.type ().name); @@ -45,6 +41,10 @@ namespace build p += e; } + // While strictly speaking we shouldn't do this in match(), + // no other rule should ever be ambiguous with this fallback + // one. + // pt.path (move (p)); } @@ -52,8 +52,12 @@ namespace build } recipe path_rule:: - select (target&, void*) const + select (target& t, void*) const { + // Search and match all the prerequisites. + // + search_and_match (t); + return &update; } @@ -62,38 +66,32 @@ namespace build { // Make sure the target is not older than any of its prerequisites. // - path_target& pt (dynamic_cast (t)); - timestamp mt (pt.mtime ()); + timestamp mt (dynamic_cast (t).mtime ()); for (const prerequisite& p: t.prerequisites) { - const target& pt (*p.target); // Should be resolved at this stage. + target& pt (*p.target); + target_state ts (update (pt)); - // If this is an mtime-based target, then simply compare timestamps. + // If this is an mtime-based target, then compare timestamps. // - if (auto mtp = dynamic_cast (&pt)) + if (auto mpt = dynamic_cast (&pt)) { - if (mt < mtp->mtime ()) - { - error << "no rule to update target " << t << - info << "prerequisite " << pt << " is ahead of " << t - << " by " << (mtp->mtime () - mt); + timestamp mp (mpt->mtime ()); - return target_state::failed; - } + if (mt < mp) + fail << "no recipe to update target " << t << + info << "prerequisite " << pt << " is ahead of " << t + << " by " << (mp - mt); } else { // Otherwise we assume the prerequisite is newer if it was updated. // - if (pt.state () == target_state::updated) - { - error << "no rule to update target " << t << + if (ts == target_state::updated) + fail << "no recipe to update target " << t << info << "prerequisite " << pt << " is ahead of " << t - << " because it was updated"; - - return target_state::failed; - } + << " because it was updated"; } } @@ -109,22 +107,18 @@ namespace build } recipe dir_rule:: - select (target&, void*) const + select (target& t, void*) const { + search_and_match (t); return &update; } target_state dir_rule:: update (target& t) { - for (const prerequisite& p: t.prerequisites) - { - auto ts (p.target->state ()); - - if (ts != target_state::uptodate) - return ts; // updated or failed - } - - return target_state::uptodate; + // Return updated if any of our prerequsites were updated and + // uptodate otherwise. + // + return update_prerequisites (t); } } diff --git a/build/search b/build/search new file mode 100644 index 0000000..e7d2acd --- /dev/null +++ b/build/search @@ -0,0 +1,31 @@ +// file : build/search -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef BUILD_SEARCH +#define BUILD_SEARCH + +#include + +namespace build +{ + class target; + class prerequisite; + + // Search for an existing target in this prerequisite's directory scope. + // + target* + search_existing_target (prerequisite&); + + // Search for an existing file in the specified list of search paths. + // + target* + search_existing_file (prerequisite&, const paths&); + + // Create a new target in this prerequisite's directory scope. + // + target& + create_new_target (prerequisite&); +} + +#endif // BUILD_SEARCH diff --git a/build/search.cxx b/build/search.cxx new file mode 100644 index 0000000..966f5f1 --- /dev/null +++ b/build/search.cxx @@ -0,0 +1,144 @@ +// file : build/search.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include // move +#include + +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace build +{ + target* + search_existing_target (prerequisite& p) + { + tracer trace ("search_existing_target"); + + assert (p.target == nullptr); + + // Look for an existing target in this prerequisite's directory scope. + // + path d; + if (p.dir.absolute ()) + d = p.dir; // Already normalized. + else + { + d = p.scope.path (); + + if (!p.dir.empty ()) + { + d /= p.dir; + d.normalize (); + } + } + + auto i (targets.find (p.type.id, d, p.name, p.ext, trace)); + + if (i == targets.end ()) + return 0; + + target& t (**i); + + level4 ([&]{trace << "existing target " << t << " for prerequsite " + << p;}); + + p.target = &t; + return &t; + } + + target* + search_existing_file (prerequisite& p, const paths& sp) + { + tracer trace ("search_existing_file"); + + assert (p.dir.relative ()); + + // Go over paths and extension looking for a file. + // + for (const path& d: sp) + { + path f (d / p.dir / path (p.name)); + + // @@ TMP: use target name as an extension. + // + const string& e (p.ext != nullptr ? *p.ext : p.type.name); + + if (!e.empty ()) + { + f += '.'; + f += e; + } + + timestamp mt (path_mtime (f)); + + if (mt == timestamp_nonexistent) + continue; + + level4 ([&]{trace << "found existing file " << f << " for prerequsite " + << p;}); + + // Find or insert. + // + auto r (targets.insert (p.type, f.directory (), p.name, p.ext, trace)); + + // Has to be a path_target. + // + path_target& t (dynamic_cast (r.first)); + + level4 ([&]{trace << (r.second ? "new" : "existing") << " target " + << t << " for prerequsite " << p;}); + + t.path (move (f)); + t.mtime (mt); + p.target = &t; + return &t; + } + + return nullptr; + } + + target& + create_new_target (prerequisite& p) + { + tracer trace ("search_new_target"); + + assert (p.target == nullptr); + + // We default to the target in this prerequisite's directory scope. + // + path d; + if (p.dir.absolute ()) + d = p.dir; // Already normalized. + else + { + d = p.scope.path (); + + if (!p.dir.empty ()) + { + d /= p.dir; + d.normalize (); + } + } + + // Find or insert. + // + auto r (targets.insert (p.type, move (d), p.name, p.ext, trace)); + assert (r.second); + + target& t (r.first); + + level4 ([&]{trace << "new target " << t << " for prerequsite " << p;}); + + p.target = &t; + return t; + } +} diff --git a/build/target b/build/target index be85a41..da5cf71 100644 --- a/build/target +++ b/build/target @@ -5,7 +5,6 @@ #ifndef BUILD_TARGET #define BUILD_TARGET -#include #include #include #include @@ -17,6 +16,7 @@ #include // move #include +#include #include #include #include // compare_*, extension_pool @@ -26,6 +26,9 @@ namespace build class target; enum class target_state {unknown, uptodate, updated, failed}; + + // Note: should throw rather than returning target_state::failed. + // typedef std::function recipe; struct target_type @@ -34,6 +37,7 @@ namespace build const char* name; const target_type* base; target* (*const factory) (path, std::string, const std::string*); + target* (*const search) (prerequisite&); }; inline std::ostream& @@ -91,33 +95,61 @@ namespace build std::ostream& operator<< (std::ostream&, const target&); - inline bool - operator< (const target& x, const target& y) + struct target_set { - std::type_index tx (typeid (x)), ty (typeid (y)); - - //@@ TODO: use compare() to compare once. - - // Unspecified and specified extension are assumed equal. The - // extension strings are from the pool, so we can just compare - // pointers. - // - return - (tx < ty) || - (tx == ty && x.name < y.name) || - (tx == ty && x.name == y.name && x.dir < y.dir) || - (tx == ty && x.name == y.name && x.dir == y.dir && - x.ext != nullptr && y.ext != nullptr && x.ext < y.ext); - } + struct key + { + mutable const std::type_index* type; + mutable const path* dir; + mutable const std::string* name; + mutable const std::string** ext; + + friend bool + operator< (const key& x, const key& y) + { + //@@ TODO: use compare() to compare once. + + // Unspecified and specified extension are assumed equal. The + // extension strings are from the pool, so we can just compare + // pointers. + // + return + (*x.type < *y.type) || + (*x.type == *y.type && *x.name < *y.name) || + (*x.type == *y.type && *x.name == *y.name && *x.dir < *y.dir) || + (*x.type == *y.type && *x.name == *y.name && *x.dir == *y.dir && + *x.ext != nullptr && *y.ext != nullptr && **x.ext < **y.ext); + } + }; + + typedef std::map> map; + typedef map_iterator_adapter iterator; + + iterator + find (const key& k, tracer& trace) const; + + iterator + find (const std::type_index& type, + const path& dir, + const std::string& name, + const std::string*& ext, + tracer& trace) const + { + return find (key {&type, &dir, &name, &ext}, trace); + } + + iterator begin () const {return map_.begin ();} + iterator end () const {return map_.end ();} - struct target_set: std::set, compare_pointer_target> - { std::pair insert (const target_type&, path dir, std::string name, const std::string* ext, tracer&); + + private: + map map_; }; extern target_set targets; @@ -172,7 +204,7 @@ namespace build mutable timestamp mtime_ {timestamp_unknown}; }; - // Filesystem path-bases target. + // Filesystem path-based target. // class path_target: public mtime_target { diff --git a/build/target.cxx b/build/target.cxx index 582ae4a..197770c 100644 --- a/build/target.cxx +++ b/build/target.cxx @@ -4,6 +4,8 @@ #include +#include +#include #include #include @@ -25,7 +27,7 @@ namespace build if (!t.dir.empty ()) { - string s (diagnostic_string (t.dir)); + string s (diag_relative_work (t.dir)); if (!s.empty ()) { @@ -46,46 +48,68 @@ namespace build return os; } + static target* + search_target (prerequisite& p) + { + // The default behavior is to look for an existing target in the + // prerequisite's directory scope. + // + return search_existing_target (p); + } + // target_set // auto target_set:: + find (const key& k, tracer& trace) const -> iterator + { + iterator i (map_.find (k)); + + if (i != end ()) + { + target& t (**i); + + // Update the extension if the existing target has it unspecified. + // + const string* ext (*k.ext); + if (t.ext != ext) + { + level4 ([&]{ + diag_record r (trace); + r << "assuming target " << t << " is the same as the one with "; + if (ext == nullptr) + r << "unspecified extension"; + else if (ext->empty ()) + r << "no extension"; + else + r << "extension " << *ext; + }); + + if (ext != nullptr) + t.ext = ext; + } + } + + return i; + } + + pair target_set:: insert (const target_type& tt, path dir, std::string name, const std::string* ext, - tracer& trace) -> pair + tracer& trace) { - //@@ OPT: would be nice to somehow first check if this target is - // already in the set before allocating a new instance. + iterator i (find (key {&tt.id, &dir, &name, &ext}, trace)); - // Find or insert. - // - auto r ( - emplace ( - unique_ptr (tt.factory (move (dir), move (name), ext)))); + if (i != end ()) + return pair (**i, false); - target& t (**r.first); + unique_ptr t (tt.factory (move (dir), move (name), ext)); + i = map_.emplace ( + make_pair (key {&tt.id, &t->dir, &t->name, &t->ext}, + move (t))).first; - // Update the extension if the existing target has it unspecified. - // - if (t.ext != ext) - { - level4 ([&]{ - diag_record r (trace); - r << "assuming target " << t << " is the same as the one with "; - if (ext == nullptr) - r << "unspecified extension"; - else if (ext->empty ()) - r << "no extension"; - else - r << "extension " << *ext; - }); - - if (ext != nullptr) - t.ext = ext; - } - - return pair (t, r.second); + return pair (**i, true); } target_set targets; @@ -101,18 +125,76 @@ namespace build return path_mtime (path_); } - const target_type target::static_type { - typeid (target), "target", nullptr, nullptr}; + // file target + // + + static target* + search_file (prerequisite& p) + { + // First see if there is an existing target. + // + if (target* t = search_existing_target (p)) + return t; - const target_type mtime_target::static_type { - typeid (mtime_target), "mtime_target", &target::static_type, nullptr}; + // Then look for an existing file in this target-type-specific + // list of paths (@@ TODO: comes from the variable). + // + if (p.dir.relative ()) + { + paths sp; + sp.push_back (src_out (p.scope.path ())); // src_base - const target_type path_target::static_type { - typeid (path_target), "path_target", &mtime_target::static_type, nullptr}; + return search_existing_file (p, sp); + } + else + return nullptr; + } - const target_type file::static_type { - typeid (file), "file", &path_target::static_type, &target_factory}; + // type info + // - const target_type dir::static_type { - typeid (dir), "dir", &target::static_type, &target_factory}; + const target_type target::static_type + { + typeid (target), + "target", + nullptr, + nullptr, + &search_target + }; + + const target_type mtime_target::static_type + { + typeid (mtime_target), + "mtime_target", + &target::static_type, + nullptr, + target::static_type.search + }; + + const target_type path_target::static_type + { + typeid (path_target), + "path_target", + &mtime_target::static_type, + nullptr, + mtime_target::static_type.search + }; + + const target_type file::static_type + { + typeid (file), + "file", + &path_target::static_type, + &target_factory, + &search_file + }; + + const target_type dir::static_type + { + typeid (dir), + "dir", + &target::static_type, + &target_factory, + target::static_type.search + }; } diff --git a/build/types b/build/types new file mode 100644 index 0000000..c191eec --- /dev/null +++ b/build/types @@ -0,0 +1,20 @@ +// file : build/types -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef BUILD_TYPES +#define BUILD_TYPES + +#include + +#include + +namespace build +{ + // Commonly-used types. + // + + typedef std::vector paths; +} + +#endif // BUILD_TYPES -- cgit v1.1