Redo rule match/build logic

Now the rule is fully responsible for searching, matching, and building
of prerequisites.

22 files changed, 891 insertions, 416 deletions

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 <build/target>
+#include <build/timestamp>
+
 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 <typename T>
+  T*
+  update_prerequisites (target&, const timestamp&);
 }
 
+#include <build/algorithm.ixx>
+#include <build/algorithm.txx>
+
 #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 <build/target>
 #include <build/prerequisite>
 #include <build/rule>
+#include <build/search>
 #include <build/utility>
 #include <build/diagnostics>
 
@@ -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<const mtime_target*> (&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 <typename T>
+  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<const mtime_target*> (&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<T*> (&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 <build/native>
@@ -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<prerequisite*> (v));
-      cxx* st (
-        dynamic_cast<cxx*> (
-          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<prerequisite*> (v));
+      auto& st (dynamic_cast<cxx&> (*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<path_target&> (
                 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<obj&> (t));
-      timestamp mt (o.mtime ());
-
-      bool u (mt == timestamp_nonexistent);
-      const cxx* s (nullptr);
+      cxx* s (update_prerequisites<cxx> (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<const mtime_target&> (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<const cxx*> (&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<exe&> (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<const mtime_target&> (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<path> ro;
 
       vector<const char*> 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<const obj&> (*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<hxx>};
+    const target_type hxx::static_type
+    {
+      typeid (hxx),
+      "hxx",
+      &file::static_type,
+      &target_factory<hxx>,
+      file::static_type.search
+    };
 
-    const target_type ixx::static_type {
-      typeid (ixx), "ixx", &file::static_type, &target_factory<ixx>};
+    const target_type ixx::static_type
+    {
+      typeid (ixx),
+      "ixx",
+      &file::static_type,
+      &target_factory<ixx>,
+      file::static_type.search
+    };
 
-    const target_type txx::static_type {
-      typeid (txx), "txx", &file::static_type, &target_factory<txx>};
+    const target_type txx::static_type
+    {
+      typeid (txx),
+      "txx",
+      &file::static_type,
+      &target_factory<txx>,
+      file::static_type.search
+    };
 
-    const target_type cxx::static_type {
-      typeid (cxx), "cxx", &file::static_type, &target_factory<cxx>};
+    const target_type cxx::static_type
+    {
+      typeid (cxx),
+      "cxx",
+      &file::static_type,
+      &target_factory<cxx>,
+      file::static_type.search
+    };
 
-    const target_type h::static_type {
-      typeid (h), "h", &file::static_type, &target_factory<h>};
+    const target_type h::static_type
+    {
+      typeid (h),
+      "h",
+      &file::static_type,
+      &target_factory<h>,
+      file::static_type.search
+    };
 
-    const target_type c::static_type {
-      typeid (c), "c", &file::static_type, &target_factory<c>};
+    const target_type c::static_type
+    {
+      typeid (c),
+      "c",
+      &file::static_type,
+      &target_factory<c>,
+      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 <exception>
 #include <type_traits>
 
+#include <build/path>
+
 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 <iostream>
 
+#include <build/context>
 #include <build/utility>
 
 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 <typename T>
+  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 <typename I>
+  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<I&> (*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<exe>};
+  const target_type exe::static_type
+  {
+    typeid (exe),
+    "exe",
+    &file::static_type,
+    &target_factory<exe>,
+    file::static_type.search
+  };
 
-  const target_type obj::static_type {
-    typeid (obj), "obj", &file::static_type, &target_factory<obj>};
+  const target_type obj::static_type
+  {
+    typeid (obj),
+    "obj",
+    &file::static_type,
+    &target_factory<obj>,
+    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 <utility>  // move()
 
+#include <build/algorithm>
 #include <build/diagnostics>
 
 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<path_target&> (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<path_target&> (t));
-    timestamp mt (pt.mtime ());
+    timestamp mt (dynamic_cast<path_target&> (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<const mtime_target*> (&pt))
+      if (auto mpt = dynamic_cast<const mtime_target*> (&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 <build/types>
+
+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 <build/search>
+
+#include <utility>  // move
+#include <cassert>
+
+#include <build/path>
+#include <build/scope>
+#include <build/target>
+#include <build/prerequisite>
+#include <build/timestamp>
+#include <build/diagnostics>
+
+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<path_target&> (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 <set>
 #include <map>
 #include <string>
 #include <vector>
@@ -17,6 +16,7 @@
 #include <utility>    // move
 
 #include <build/path>
+#include <build/key-set>
 #include <build/timestamp>
 #include <build/prerequisite>
 #include <build/utility>       // 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<target_state (target&)> 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<key, std::unique_ptr<target>> map;
+    typedef map_iterator_adapter<map::const_iterator> 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<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&);
+
+  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 <build/target>
 
+#include <build/scope>
+#include <build/search>
 #include <build/context>
 #include <build/diagnostics>
 
@@ -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&, bool> target_set::
   insert (const target_type& tt,
           path dir,
           std::string name,
           const std::string* ext,
-          tracer& trace) -> pair<target&, bool>
+          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<target> (tt.factory (move (dir), move (name), ext))));
+    if (i != end ())
+      return pair<target&, bool> (**i, false);
 
-    target& t (**r.first);
+    unique_ptr<target> 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<target&, bool> (t, r.second);
+    return pair<target&, bool> (**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<file>};
+  // type info
+  //
 
-  const target_type dir::static_type {
-    typeid (dir), "dir", &target::static_type, &target_factory<dir>};
+  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<file>,
+    &search_file
+  };
+
+  const target_type dir::static_type
+  {
+    typeid (dir),
+    "dir",
+    &target::static_type,
+    &target_factory<dir>,
+    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 <vector>
+
+#include <build/path>
+
+namespace build
+{
+  // Commonly-used types.
+  //
+
+  typedef std::vector<path> paths;
+}
+
+#endif // BUILD_TYPES