Implement rule chaining for cxx::link

16 files changed, 384 insertions, 219 deletions

diff --git a/build/algorithm b/build/algorithm
index b67eb1a..a3b0db9 100644
--- a/build/algorithm
+++ b/build/algorithm
@@ -10,7 +10,7 @@ namespace build
   class target;
   class prerequisite;
 
-  target*
+  target&
   search (prerequisite&);
 
   bool
diff --git a/build/algorithm.cxx b/build/algorithm.cxx
index a4160ef..af0e3f3 100644
--- a/build/algorithm.cxx
+++ b/build/algorithm.cxx
@@ -20,7 +20,7 @@ using namespace std;
 
 namespace build
 {
-  target*
+  target&
   search (prerequisite& p)
   {
     tracer tr ("search");
@@ -38,41 +38,16 @@ namespace build
       d.normalize ();
     }
 
-    //@@ TODO: would be nice to first check if this target is
-    //   already in the set before allocating a new instance.
-
     // Find or insert.
     //
-    auto r (
-      targets.emplace (
-        unique_ptr<target> (p.type.factory (move (d), p.name, p.ext))));
-
-    target& t (**r.first);
+    auto r (targets.insert (p.type, move (d), p.name, p.ext, tr));
 
     trace (4, [&]{
-        tr << (r.second ? "new" : "existing") << " target " << t
+        tr << (r.second ? "new" : "existing") << " target " << r.first
            << " for prerequsite " << p;});
 
-    // Update extension if the existing target has it unspecified.
-    //
-    if (t.ext != p.ext)
-    {
-      trace (4, [&]{
-          tracer::record r (tr);
-          r << "assuming target " << t << " is the same as the one with ";
-          if (p.ext == nullptr)
-            r << "unspecified extension";
-          else if (p.ext->empty ())
-            r << "no extension";
-          else
-            r << "extension " << *p.ext;
-        });
-
-      if (p.ext != nullptr)
-        t.ext = p.ext;
-    }
-
-    return (p.target = &t);
+    p.target = &r.first;
+    return r.first;
   }
 
   bool
@@ -92,22 +67,17 @@ namespace build
       const auto& rules (i->second); // Name map.
 
       string hint; // @@ TODO
-      bool single;
 
       auto rs (hint.empty ()
                ? make_pair (rules.begin (), rules.end ())
                : rules.find (hint));
 
-      for (auto i (rs.first); i != rs.second;)
+      for (auto i (rs.first); i != rs.second; ++i)
       {
         const string& n (i->first);
         const rule& ru (i->second);
 
-        if (i++ == rs.first)
-          single = (i == rs.second);
-
-        recipe re;
-        string h (hint);
+        void* m;
         {
           auto g (
             make_exception_guard (
@@ -118,42 +88,21 @@ namespace build
               },
               t, n));
 
-          // If the rule matches, then it updates the hint with the one we
-          // need to use when checking for ambiguity.
-          //
-          re = ru.match (t, single, h);
+          m = ru.match (t, hint);
         }
 
-        if (re)
+        if (m != nullptr)
         {
-          t.recipe (re);
-
-          // If the returned hint is more "general" than what we had,
-          // then narrow it back down.
-          //
-          if (h < hint)
-            h = hint;
-
-          // Do the ambiguity test unless it is an unambiguous match (the
-          // hint is the rule's full name).
+          // Do the ambiguity test.
           //
-          if (h == n)
-            break;
-
-          auto rs1 (h == hint
-                    ? make_pair (i, rs.second) // Continue iterating.
-                    : rules.find (h));
-
           bool ambig (false);
 
-          // See if any other rules match.
-          //
-          for (auto i (rs1.first); i != rs1.second; ++i)
+          for (++i; i != rs.second; ++i)
           {
             const string& n1 (i->first);
             const rule& ru1 (i->second);
 
-            string h1 (h);
+            void* m1;
             {
               auto g (
                 make_exception_guard (
@@ -164,19 +113,11 @@ namespace build
                   },
                   t, n1));
 
-              re = ru1.match (t, false, h1);
+              m1 = ru1.match (t, hint);
             }
 
-            if (re)
+            if (m1 != nullptr)
             {
-              // A subsequent rule cannot return a more specific hint.
-              // Remember, the hint returning mechanism is here to
-              // indicate that only a class of rules that perform a
-              // similar rule chaining transformation may apply (e.g.,
-              // cxx.gnu and cxx.clang).
-              //
-              assert (h1 <= h);
-
               if (!ambig)
               {
                 cerr << "error: multiple rules matching target " << t << endl;
@@ -194,6 +135,7 @@ namespace build
             throw error ();
           }
 
+          t.recipe (ru.select (t, m));
           break;
         }
       }
diff --git a/build/b.cxx b/build/b.cxx
index 5135761..14b23fc 100644
--- a/build/b.cxx
+++ b/build/b.cxx
@@ -159,6 +159,9 @@ main (int argc, char* argv[])
   target_types.insert (exe::static_type);
   target_types.insert (obj::static_type);
 
+  target_types.insert (cxx::h::static_type);
+  target_types.insert (cxx::c::static_type);
+
   target_types.insert (cxx::cxx::static_type);
   target_types.insert (cxx::hxx::static_type);
   target_types.insert (cxx::ixx::static_type);
diff --git a/build/buildfile b/build/buildfile
index 73f2e91..3575baa 100644
--- a/build/buildfile
+++ b/build/buildfile
@@ -1,22 +1,4 @@
-exe{b1}: obj{b algorithm scope parser lexer trace target prerequisite rule \
+exe{b1}: cxx{b algorithm scope parser lexer trace target prerequisite rule \
   native context diagnostics cxx/target cxx/rule process timestamp path \
   utility}
 
-obj{b}: cxx{b}
-obj{algorithm}: cxx{algorithm}
-obj{scope}: cxx{scope}
-obj{parser}: cxx{parser}
-obj{lexer}: cxx{lexer}
-obj{trace}: cxx{trace}
-obj{target}: cxx{target}
-obj{prerequisite}: cxx{prerequisite}
-obj{rule}: cxx{rule}
-obj{native}: cxx{native}
-obj{context}: cxx{context}
-obj{diagnostics}: cxx{diagnostics}
-obj{cxx/target}: cxx{cxx/target}
-obj{cxx/rule}: cxx{cxx/rule}
-obj{process}: cxx{process}
-obj{timestamp}: cxx{timestamp}
-obj{path}: cxx{path}
-obj{utility}: cxx{utility}
diff --git a/build/cxx/rule b/build/cxx/rule
index 8924c7c..cf9ee51 100644
--- a/build/cxx/rule
+++ b/build/cxx/rule
@@ -22,8 +22,11 @@ namespace build
     class compile: public rule
     {
     public:
+      virtual void*
+      match (target&, const std::string& hint) const;
+
       virtual recipe
-      match (target&, bool single, std::string& hint) const;
+      select (target&, void*) const;
 
       static target_state
       update (target&);
@@ -36,8 +39,11 @@ namespace build
     class link: public rule
     {
     public:
+      virtual void*
+      match (target&, const std::string& hint) const;
+
       virtual recipe
-      match (target&, bool single, std::string& hint) const;
+      select (target&, void*) const;
 
       static target_state
       update (target&);
diff --git a/build/cxx/rule.cxx b/build/cxx/rule.cxx
index 3a97576..c9dd7d6 100644
--- a/build/cxx/rule.cxx
+++ b/build/cxx/rule.cxx
@@ -4,10 +4,11 @@
 
 #include <build/cxx/rule>
 
-#include <cstddef>  // size_t
-#include <cstdlib>  // exit
 #include <string>
 #include <vector>
+#include <cstddef>  // size_t
+#include <cstdlib>  // exit
+#include <utility>  // move()
 #include <iostream>
 
 #include <ext/stdio_filebuf.h>
@@ -27,8 +28,8 @@ namespace build
   {
     // compile
     //
-    recipe compile::
-    match (target& t, bool single, std::string& hint) const
+    void* compile::
+    match (target& t, const string&) const
     {
       tracer tr ("cxx::compile::match");
 
@@ -48,24 +49,21 @@ namespace build
       //   of dependency info.
       //
 
-      // See if we have a source file.
+      // See if we have a C++ source file.
       //
-      prerequisite* sp (nullptr);
       for (prerequisite& p: t.prerequisites)
       {
         if (p.type.id == typeid (cxx))
-        {
-          sp = &p;
-          break;
-        }
+          return &p;
       }
 
-      if (sp == nullptr)
-      {
-        trace (3, [&]{tr << "no c++ source file for target " << t;});
-        return recipe ();
-      }
+      trace (3, [&]{tr << "no c++ source file for target " << t;});
+      return nullptr;
+    }
 
+    recipe compile::
+    select (target& t, void* v) const
+    {
       // Derive object file name from target name.
       //
       obj& o (dynamic_cast<obj&> (t));
@@ -77,9 +75,10 @@ namespace build
       // this in order to get the source file path for prerequisite
       // injections.
       //
+      prerequisite* sp (static_cast<prerequisite*> (v));
       cxx* st (
         dynamic_cast<cxx*> (
-          sp->target != nullptr ? sp->target : search (*sp)));
+          sp->target != nullptr ? sp->target : &search (*sp)));
 
       if (st != nullptr)
       {
@@ -92,7 +91,7 @@ namespace build
         }
       }
 
-      return recipe (&update);
+      return &update;
     }
 
     // Return the next make prerequisite starting from the specified
@@ -222,37 +221,18 @@ namespace build
 
             // Find or insert.
             //
-            auto r (ds.prerequisites.emplace (
-                      hxx::static_type, move (d), move (n), e, ds));
-
-            auto& p (const_cast<prerequisite&> (*r.first));
-
-            // Update extension if the existing prerequisite has it
-            // unspecified.
-            //
-            if (p.ext != e)
-            {
-              trace (4, [&]{
-                  tracer::record r (tr);
-                  r << "assuming prerequisite " << p << " is the same as the "
-                    << "one with ";
-                  if (e->empty ())
-                    r << "no extension";
-                  else
-                    r << "extension " << *e;
-                });
-
-              p.ext = e;
-            }
+            prerequisite& p (
+              ds.prerequisites.insert (
+                hxx::static_type, move (d), move (n), e, ds, tr).first);
 
             // Resolve to target so that we can assign its path.
             //
             path_target& t (
               dynamic_cast<path_target&> (
-                p.target != nullptr ? *p.target : *search (p)));
+                p.target != nullptr ? *p.target : search (p)));
 
             if (t.path ().empty ())
-              t.path (file);
+              t.path (move (file));
 
             o.prerequisites.push_back (p);
           }
@@ -374,9 +354,11 @@ namespace build
 
     // link
     //
-    recipe link::
-    match (target& t, bool single, std::string& hint) const
+    void* link::
+    match (target& t, const string& hint) const
     {
+      tracer tr ("cxx::link::match");
+
       // @@ TODO:
       //
       // - check prerequisites: object files, libraries
@@ -387,23 +369,53 @@ namespace build
       // - 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).
-      //   What if there is a library. Probably ok if .a, not is .so.
+      //   What if there is a library. Probably ok if .a, not if .so.
       //
 
-      // See if we have at least one object file.
+      // Scan prerequisites and see if we can work with what we've got.
       //
-      prerequisite* op (nullptr);
+      bool seen_cxx (false), seen_c (false), seen_obj (false);
+
       for (prerequisite& p: t.prerequisites)
       {
-        if (p.type.id == typeid (obj))
+        if (p.type.id == typeid (cxx))
         {
-          op = &p;
-          break;
+          if (!seen_cxx)
+            seen_cxx = true;
+        }
+        else if (p.type.id == typeid (c))
+        {
+          if (!seen_c)
+            seen_c = true;
+        }
+        else if (p.type.id == typeid (obj))
+        {
+          if (!seen_obj)
+            seen_obj = true;
+        }
+        else
+        {
+          trace (3, [&]{tr << "unexpected prerequisite type " << p.type;});
+          return nullptr;
         }
       }
 
-      if (op == nullptr)
-        return recipe ();
+      // We will only chain C source if there is also C++ source or we
+      // we explicitly asked to.
+      //
+      if (seen_c && !seen_cxx && hint < "cxx")
+      {
+        trace (3, [&]{tr << "c prerequisite(s) without c++ or hint";});
+        return nullptr;
+      }
+
+      return seen_cxx || seen_c || seen_obj ? &t : nullptr;
+    }
+
+    recipe link::
+    select (target& t, void*) const
+    {
+      tracer tr ("cxx::link::select");
 
       // Derive executable file name from target name.
       //
@@ -412,7 +424,102 @@ namespace build
       if (e.path ().empty ())
         e.path (e.directory / path (e.name));
 
-      return recipe (&update);
+      // Do rule chaining for C and C++ source files.
+      //
+      // @@ OPT: match() could indicate whether this is necesssary.
+      //
+      for (auto& pr: t.prerequisites)
+      {
+        prerequisite& cp (pr);
+
+        if (cp.type.id != typeid (c) && cp.type.id != typeid (cxx))
+          continue;
+
+        // 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
+        // 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).
+        //
+        path d;
+        if (cp.directory.relative () || cp.directory.sub (out_root))
+          d = cp.directory;
+        else
+        {
+          if (!cp.directory.sub (src_root))
+          {
+            cerr << "error: out of project prerequisite " << cp << endl;
+            cerr << "info: specify corresponding obj{} target explicitly"
+                 << endl;
+            throw error ();
+          }
+
+          d = out_root / cp.directory.leaf (src_root);
+        }
+
+        prerequisite& op (
+          cp.scope.prerequisites.insert (
+            obj::static_type, move (d), cp.name, nullptr, cp.scope, tr).first);
+
+        // Resolve this prerequisite to target.
+        //
+        target& ot (search (op));
+
+        // If this target already exists, then it needs to be "compatible"
+        // with what we doing.
+        //
+        bool add (true);
+        for (prerequisite& p: ot.prerequisites)
+        {
+          // Ignore some known target types (headers).
+          //
+          if (p.type.id == typeid (h) ||
+              cp.type.id == typeid (cxx) && (p.type.id == typeid (hxx) ||
+                                             p.type.id == typeid (ixx) ||
+                                             p.type.id == typeid (txx)))
+            continue;
+
+          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.
+            }
+          }
+
+          cerr << "error: synthesized target for prerequisite " << cp
+               << " would be incompatible with existing target " << ot
+               << endl;
+
+          if (p.type.id == typeid (cxx))
+            cerr << "info: existing prerequsite " << p << " does not "
+                 << "match " << cp << endl;
+          else
+            cerr << "info: unknown existing prerequsite " << p << endl;
+
+          cerr << "info: specify corresponding obj{} target explicitly"
+               << endl;
+
+          throw error ();
+        }
+
+        if (add)
+          ot.prerequisites.push_back (cp);
+
+        // Change the exe{} target's prerequsite from cxx{} to obj{}.
+        //
+        pr = op;
+      }
+
+      return &update;
     }
 
     target_state link::
diff --git a/build/cxx/target b/build/cxx/target
index 37b093b..39ebdd3 100644
--- a/build/cxx/target
+++ b/build/cxx/target
@@ -50,6 +50,28 @@ namespace build
       virtual const target_type& type () const {return static_type;}
       static const target_type static_type;
     };
+
+    //@@ TMP
+    //
+    class h: public file
+    {
+    public:
+      using file::file;
+
+    public:
+      virtual const target_type& type () const {return static_type;}
+      static const target_type static_type;
+    };
+
+    class c: public file
+    {
+    public:
+      using file::file;
+
+    public:
+      virtual const target_type& type () const {return static_type;}
+      static const target_type static_type;
+    };
   }
 }
 
diff --git a/build/cxx/target.cxx b/build/cxx/target.cxx
index c4502b4..f57c963 100644
--- a/build/cxx/target.cxx
+++ b/build/cxx/target.cxx
@@ -21,5 +21,11 @@ namespace build
 
     const target_type cxx::static_type {
       typeid (cxx), "cxx", &file::static_type, &target_factory<cxx>};
+
+    const target_type h::static_type {
+      typeid (h), "h", &file::static_type, &target_factory<h>};
+
+    const target_type c::static_type {
+      typeid (c), "c", &file::static_type, &target_factory<c>};
   }
 }
diff --git a/build/parser.cxx b/build/parser.cxx
index 77571fb..1927ebf 100644
--- a/build/parser.cxx
+++ b/build/parser.cxx
@@ -128,35 +128,11 @@ namespace build
               }
             }
 
-            //cout << "prerequisite " << tt << " " << n << " " << d << endl;
-
             // Find or insert.
             //
-            auto r (scope_->prerequisites.emplace (
-                      ti, move (d), move (n), e, *scope_));
-
-            auto& p (const_cast<prerequisite&> (*r.first));
-
-            // Update extension if the existing prerequisite has it
-            // unspecified.
-            //
-            if (p.ext != e)
-            {
-              trace (4, [&]{
-                  tracer::record r (tr);
-                  r << "assuming prerequisite " << p << " is the same as the "
-                    << "one with ";
-                  if (e == nullptr)
-                    r << "unspecified extension";
-                  else if (e->empty ())
-                    r << "no extension";
-                  else
-                    r << "extension " << *e;
-                });
-
-              if (e != nullptr)
-                p.ext = e;
-            }
+            prerequisite& p (
+              scope_->prerequisites.insert (
+                ti, move (d), move (n), e, *scope_, tr).first);
 
             ps.push_back (p);
           }
@@ -217,40 +193,11 @@ namespace build
 
             const target_type& ti (i->second);
 
-            //@@ TODO would be nice to first check if this target is
-            //   already in the set before allocating a new instance.
-
-            //cout << "target " << tt << " " << n << " " << d << endl;
-
             // Find or insert.
             //
-            auto r (
-              targets.emplace (
-                unique_ptr<target> (ti.factory (move (d), move (n), e))));
-
-            target& t (**r.first);
-
-            // Update extension if the existing target has it unspecified.
-            //
-            if (t.ext != e)
-            {
-              trace (4, [&]{
-                  tracer::record r (tr);
-                  r << "assuming target " << t << " is the same as the "
-                    << "one with ";
-                  if (e == nullptr)
-                    r << "unspecified extension";
-                  else if (e->empty ())
-                    r << "no extension";
-                  else
-                    r << "extension " << *e;
-                });
-
-              if (e != nullptr)
-                t.ext = e;
-            }
+            target& t (targets.insert (ti, move (d), move (n), e, tr).first);
 
-            t.prerequisites = ps; //@@ TODO: move if last target.
+            t.prerequisites = ps; //@@ OPT: move if last target.
 
             if (default_target == nullptr)
               default_target = &t;
diff --git a/build/path b/build/path
index dbd048d..49d543c 100644
--- a/build/path
+++ b/build/path
@@ -304,6 +304,12 @@ namespace build
       return basic_path (path_ + s);
     }
 
+    basic_path
+    operator+ (C c) const
+    {
+      return basic_path (path_ + c);
+    }
+
     basic_path&
     operator+= (string_type const& s)
     {
@@ -311,6 +317,13 @@ namespace build
       return *this;
     }
 
+    basic_path&
+    operator+= (C c)
+    {
+      path_ += c;
+      return *this;
+    }
+
     // Note that comparison is case-insensitive if the filesystem is
     // not case-sensitive (e.g., Windows).
     //
diff --git a/build/prerequisite b/build/prerequisite
index 6c9c171..a14621f 100644
--- a/build/prerequisite
+++ b/build/prerequisite
@@ -19,6 +19,7 @@ namespace build
   class scope;
   class target;
   class target_type;
+  class tracer;
 
   class prerequisite
   {
@@ -50,7 +51,16 @@ namespace build
   bool
   operator< (const prerequisite&, const prerequisite&);
 
-  typedef std::set<prerequisite> prerequisite_set;
+  struct prerequisite_set: std::set<prerequisite>
+  {
+    std::pair<prerequisite&, bool>
+    insert (const target_type&,
+            path dir,
+            std::string name,
+            const std::string* ext,
+            scope&,
+            tracer&);
+  };
 }
 
 #endif // BUILD_PREREQUISITE
diff --git a/build/prerequisite.cxx b/build/prerequisite.cxx
index 370f5d0..f5461ef 100644
--- a/build/prerequisite.cxx
+++ b/build/prerequisite.cxx
@@ -9,6 +9,7 @@
 #include <build/scope>
 #include <build/target> // target_type
 #include <build/context>
+#include <build/diagnostics>
 
 using namespace std;
 
@@ -72,4 +73,45 @@ namespace build
        x.directory == y.directory &&
        x.ext != nullptr && y.ext != nullptr && x.ext < y.ext);
   }
+
+  // prerequisite_set
+  //
+  auto prerequisite_set::
+  insert (const target_type& tt,
+          path dir,
+          std::string name,
+          const std::string* ext,
+          scope& s,
+          tracer& tr) -> pair<prerequisite&, bool>
+  {
+    //@@ OPT: would be nice to somehow first check if this prerequisite is
+    //   already in the set before allocating a new instance.
+
+    // Find or insert.
+    //
+    auto r (emplace (tt, move (dir), move (name), ext, s));
+    prerequisite& p (const_cast<prerequisite&> (*r.first));
+
+    // Update extension if the existing prerequisite has it unspecified.
+    //
+    if (p.ext != ext)
+    {
+      trace (4, [&]{
+          tracer::record r (tr);
+          r << "assuming prerequisite " << p << " 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)
+        p.ext = ext;
+    }
+
+    return pair<prerequisite&, bool> (p, r.second);
+  }
 }
diff --git a/build/rule b/build/rule
index 91ef0ca..325204f 100644
--- a/build/rule
+++ b/build/rule
@@ -18,8 +18,11 @@ namespace build
   class rule
   {
   public:
+    virtual void*
+    match (target&, const std::string& hint) const = 0;
+
     virtual recipe
-    match (target&, bool single, std::string& hint) const = 0;
+    select (target&, void*) const = 0;
   };
 
   typedef std::unordered_map<
@@ -31,8 +34,11 @@ namespace build
   class default_path_rule: public rule
   {
   public:
+    virtual void*
+    match (target&, const std::string& hint) const;
+
     virtual recipe
-    match (target&, bool single, std::string& hint) const;
+    select (target&, void*) const;
 
     static target_state
     update (target&);
diff --git a/build/rule.cxx b/build/rule.cxx
index c116538..b73b053 100644
--- a/build/rule.cxx
+++ b/build/rule.cxx
@@ -4,6 +4,7 @@
 
 #include <build/rule>
 
+#include <utility>  // move()
 #include <iostream>
 
 using namespace std;
@@ -14,24 +15,45 @@ namespace build
 
   // default_path_rule
   //
-  recipe default_path_rule::
-  match (target& t, bool, std::string&) const
+  void* default_path_rule::
+  match (target& t, const string&) const
   {
     // @@ 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?
     //
 
     path_target& pt (dynamic_cast<path_target&> (t));
 
-    // @@ TMP: derive file name by appending target name as an extension.
-    //
     if (pt.path ().empty ())
-      pt.path (t.directory / path (pt.name + '.' + pt.type ().name));
+    {
+      path p (t.directory / path (pt.name));
+
+      // @@ TMP: derive file name by appending target name as an extension?
+      //
+      const string& e (pt.ext != nullptr ? *pt.ext : pt.type ().name);
+
+      if (!e.empty ())
+      {
+        p += '.';
+        p += e;
+      }
+
+      pt.path (move (p));
+    }
 
-    return pt.mtime () != timestamp_nonexistent ? &update : nullptr;
+    return pt.mtime () != timestamp_nonexistent ? &t : nullptr;
+  }
+
+  recipe default_path_rule::
+  select (target&, void*) const
+  {
+    return &update;
   }
 
   target_state default_path_rule::
diff --git a/build/target b/build/target
index 508aedb..f57e8cc 100644
--- a/build/target
+++ b/build/target
@@ -12,7 +12,7 @@
 #include <memory>     // unique_ptr
 #include <functional> // function, reference_wrapper
 #include <typeindex>
-#include <iosfwd>
+#include <ostream>
 #include <cassert>
 #include <utility>    // move
 
@@ -36,6 +36,12 @@ namespace build
     target* (*const factory) (path, std::string, const std::string*);
   };
 
+  inline std::ostream&
+  operator<< (std::ostream& os, const target_type& tt)
+  {
+    return os << tt.name;
+  }
+
   class target
   {
   public:
@@ -104,7 +110,16 @@ namespace build
        x.ext != nullptr && y.ext != nullptr && x.ext < y.ext);
   }
 
-  typedef std::set<std::unique_ptr<target>, compare_pointer_target> target_set;
+  struct target_set: std::set<std::unique_ptr<target>, compare_pointer_target>
+  {
+    std::pair<target&, bool>
+    insert (const target_type&,
+            path dir,
+            std::string name,
+            const std::string* ext,
+            tracer&);
+  };
+
   extern target_set targets;
   extern target* default_target;
 
@@ -170,7 +185,7 @@ namespace build
     path () const {return path_;}
 
     void
-    path (path_type p) {assert (path_.empty ()); path_ = p;}
+    path (path_type p) {assert (path_.empty ()); path_ = std::move (p);}
 
   protected:
     virtual timestamp
diff --git a/build/target.cxx b/build/target.cxx
index 61423db..b20f53b 100644
--- a/build/target.cxx
+++ b/build/target.cxx
@@ -4,9 +4,8 @@
 
 #include <build/target>
 
-#include <ostream>
-
 #include <build/context>
+#include <build/diagnostics>
 
 using namespace std;
 
@@ -37,7 +36,50 @@ namespace build
     return os;
   }
 
+  // target_set
+  //
+  auto target_set::
+  insert (const target_type& tt,
+          path dir,
+          std::string name,
+          const std::string* ext,
+          tracer& tr) -> pair<target&, bool>
+  {
+    //@@ OPT: would be nice to somehow first check if this target is
+    //   already in the set before allocating a new instance.
+
+    // Find or insert.
+    //
+    auto r (
+      emplace (
+        unique_ptr<target> (tt.factory (move (dir), move (name), ext))));
+
+    target& t (**r.first);
+
+    // Update the extension if the existing target has it unspecified.
+    //
+    if (t.ext != ext)
+    {
+      trace (4, [&]{
+          tracer::record r (tr);
+          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<target&, bool> (t, r.second);
+  }
+
   target_set targets;
+
   target* default_target = nullptr;
   target_type_map target_types;