Initial support for loading dependency info from buildfiles

Also a new iteration on the overall architecture. Now, for the first time,
build can read the buildfile and build itself.

g++-4.9 -std=c++14 -g -I.. -o bd bd.cxx algorithm.cxx scope.cxx parser.cxx lexer.cxx target.cxx prerequisite.cxx rule.cxx native.cxx cxx/target.cxx cxx/rule.cxx process.cxx timestamp.cxx path.cxx

g++-4.9 -std=c++14 -g -I../../.. -o driver driver.cxx ../../../build/lexer.cxx

g++-4.9 -std=c++14 -g -I../../.. -o driver driver.cxx ../../../build/lexer.cxx ../../../build/parser.cxx ../../../build/scope.cxx ../../../build/target.cxx ../../../build/native.cxx ../../../build/prerequisite.cxx ../../../build/path.cxx ../../../build/timestamp.cxx

22 files changed, 783 insertions, 185 deletions

diff --git a/build/algorithm b/build/algorithm
new file mode 100644
index 0000000..b67eb1a
--- /dev/null
+++ b/build/algorithm
@@ -0,0 +1,20 @@
+// file      : build/algorithm -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD_ALGORITHM
+#define BUILD_ALGORITHM
+
+namespace build
+{
+  class target;
+  class prerequisite;
+
+  target*
+  search (prerequisite&);
+
+  bool
+  match (target&);
+}
+
+#endif // BUILD_ALGORITHM
diff --git a/build/algorithm.cxx b/build/algorithm.cxx
new file mode 100644
index 0000000..fac0bf6
--- /dev/null
+++ b/build/algorithm.cxx
@@ -0,0 +1,93 @@
+// file      : build/algorithm.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <build/algorithm>
+
+#include <memory>   // unique_ptr
+#include <utility>  // move
+#include <cassert>
+#include <iostream>
+
+#include <build/path>
+#include <build/scope>
+#include <build/target>
+#include <build/prerequisite>
+#include <build/rule>
+#include <build/diagnostics>
+
+using namespace std;
+
+namespace build
+{
+  target*
+  search (prerequisite& p)
+  {
+    assert (p.target == nullptr);
+
+    //@@ TODO for now we just default to the directory scope.
+    //
+    path d;
+    if (p.directory.absolute ())
+      d = p.directory; // Already normalized.
+    else
+    {
+      d = p.scope.path () / p.directory;
+      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 (p.name, move (d)))));
+
+    //if (r.second)
+    //  cout << "new target for prerequsite " << p << " " << d << endl;
+
+    return (p.target = r.first->get ());
+  }
+
+  bool
+  match (target& t)
+  {
+    assert (!t.recipe ());
+
+    for (auto tt (&t.type ());
+         tt != nullptr && !t.recipe ();
+         tt = tt->base)
+    {
+      for (auto rs (rules.equal_range (tt->id));
+           rs.first != rs.second;
+           ++rs.first)
+      {
+        const rule& ru (rs.first->second);
+
+        recipe re;
+
+        {
+          auto g (
+            make_exception_guard (
+              [] (target& t)
+              {
+                cerr << "info: while matching a rule for target " << t << endl;
+              },
+              t));
+
+          re = ru.match (t);
+        }
+
+        if (re)
+        {
+          t.recipe (re);
+          break;
+        }
+      }
+    }
+
+    return bool (t.recipe ());
+  }
+}
diff --git a/build/bd.cxx b/build/bd.cxx
index 82d283c..66130b2 100644
--- a/build/bd.cxx
+++ b/build/bd.cxx
@@ -11,8 +11,11 @@
 #include <typeinfo>
 #include <system_error>
 
+#include <build/scope>
 #include <build/target>
+#include <build/prerequisite>
 #include <build/rule>
+#include <build/algorithm>
 #include <build/process>
 #include <build/diagnostics>
 
@@ -24,7 +27,7 @@ using namespace std;
 namespace build
 {
   bool
-  match (target& t)
+  match_recursive (target& t)
   {
     // Because we match the target first and then prerequisites,
     // any additional dependency information injected by the rule
@@ -32,48 +35,23 @@ namespace build
     //
     if (!t.recipe ())
     {
-      for (auto ti (&t.type_id ());
-           ti != nullptr && !t.recipe ();
-           ti = ti->base)
-      {
-        for (auto rs (rules.equal_range (ti->id));
-             rs.first != rs.second;
-             ++rs.first)
-        {
-          const rule& ru (rs.first->second);
-
-          recipe re;
-
-          {
-            auto g (
-              make_exception_guard (
-                [] (target& t)
-                {
-                  cerr << "info: while matching a rule for target " << t << endl;
-                },
-                t));
-
-            re = ru.match (t);
-          }
-
-          if (re)
-          {
-            t.recipe (re);
-            break;
-          }
-        }
-      }
-
-      if (!t.recipe ())
+      if (!match (t))
       {
         cerr << "error: no rule to update target " << t << endl;
         return false;
       }
     }
 
-    for (target& p: t.prerequisites ())
+    for (prerequisite& p: t.prerequisites)
     {
-      if (!match (p))
+      // 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))
       {
         cerr << "info: required by " << t << endl;
         return false;
@@ -90,11 +68,13 @@ namespace build
 
     target_state ts;
 
-    for (target& p: t.prerequisites ())
+    for (prerequisite& p: t.prerequisites)
     {
-      if (p.state () == target_state::unknown)
+      target& pt (*p.target);
+
+      if (pt.state () == target_state::unknown)
       {
-        p.state ((ts = update (p)));
+        pt.state ((ts = update (pt)));
 
         if (ts == target_state::failed)
           return ts;
@@ -119,6 +99,25 @@ namespace build
     t.state (ts);
     return ts;
   }
+
+  void
+  dump ()
+  {
+    for (const auto& pt: targets)
+    {
+      target& t (*pt);
+
+      cout << t << ':';
+
+      for (const auto& p: t.prerequisites)
+      {
+        cout << ' ' << p;
+      }
+
+      cout << endl;
+    }
+  }
+
 }
 
 #include <build/native>
@@ -136,6 +135,18 @@ main (int argc, char* argv[])
   //
   tzset ();
 
+  // Register target types.
+  //
+  target_types.insert (file::static_type);
+
+  target_types.insert (exe::static_type);
+  target_types.insert (obj::static_type);
+
+  target_types.insert (cxx::cxx::static_type);
+  target_types.insert (cxx::hxx::static_type);
+  target_types.insert (cxx::ixx::static_type);
+  target_types.insert (cxx::txx::static_type);
+
   // Parse buildfile.
   //
   path bf ("buildfile");
@@ -148,11 +159,11 @@ main (int argc, char* argv[])
   }
 
   ifs.exceptions (ifstream::failbit | ifstream::badbit);
-  parser p;
+  parser p (cerr);
 
   try
   {
-    p.parse (ifs, bf);
+    p.parse (ifs, bf, scopes[path::current ()]);
   }
   catch (const lexer_error&)
   {
@@ -168,8 +179,7 @@ main (int argc, char* argv[])
     return 1;
   }
 
-  return 0;
-
+  dump ();
 
   // Register rules.
   //
@@ -182,38 +192,35 @@ main (int argc, char* argv[])
   default_path_rule path_exists;
   rules.emplace (typeid (path_target), path_exists);
 
+  // Build.
   //
-  //
-  using namespace build::cxx;
-
-  exe bd ("bd");
-  obj bd_o ("bd");
-  bd.prerequisite (bd_o);
-
-  cxx::cxx bd_cxx ("bd");
-  bd_cxx.path (path ("bd.cxx"));
-
-  bd_o.prerequisite (bd_cxx);
+  if (default_target == nullptr)
+  {
+    cerr << "error: no default target" << endl;
+    return 1;
+  }
 
-  //
-  //
   try
   {
-    if (!match (bd))
+    target& d (*default_target);
+
+    if (!match_recursive (d))
       return 1; // Diagnostics has already been issued.
 
-    switch (update (bd))
+    //dump ();
+
+    switch (update (d))
     {
     case target_state::uptodate:
       {
-        cerr << "info: target " << bd << " is up to date" << endl;
+        cerr << "info: target " << d << " is up to date" << endl;
         break;
       }
     case target_state::updated:
       break;
     case target_state::failed:
       {
-        cerr << "error: failed to update target " << bd << endl;
+        cerr << "error: failed to update target " << d << endl;
         return 1;
       }
     case target_state::unknown:
diff --git a/build/buildfile b/build/buildfile
index ceed236..4e9aaa2 100644
--- a/build/buildfile
+++ b/build/buildfile
@@ -1 +1,17 @@
-exe{bd}: obj{bd target}
+exe{bd}: obj{bd algorithm scope parser lexer target prerequisite rule \
+  native cxx/target cxx/rule process timestamp path}
+
+obj{bd}: cxx{bd}
+obj{algorithm}: cxx{algorithm}
+obj{scope}: cxx{scope}
+obj{parser}: cxx{parser}
+obj{lexer}: cxx{lexer}
+obj{target}: cxx{target}
+obj{prerequisite}: cxx{prerequisite}
+obj{rule}: cxx{rule}
+obj{native}: cxx{native}
+obj{cxx/target}: cxx{cxx/target}
+obj{cxx/rule}: cxx{cxx/rule}
+obj{process}: cxx{process}
+obj{timestamp}: cxx{timestamp}
+obj{path}: cxx{path}
diff --git a/build/cxx/rule b/build/cxx/rule
index 4900180..99e688d 100644
--- a/build/cxx/rule
+++ b/build/cxx/rule
@@ -12,12 +12,13 @@
 
 namespace build
 {
+  class scope;
+
   namespace cxx
   {
     // @@ Can't we do match(obj&) and then registration code extracts
     // that. And no virtuals.
     //
-
     class compile: public rule
     {
     public:
@@ -29,7 +30,7 @@ namespace build
 
     private:
       void
-      inject_prerequisites (obj&, const cxx&) const;
+      inject_prerequisites (obj&, const cxx&, scope&) const;
     };
 
     class link: public rule
diff --git a/build/cxx/rule.cxx b/build/cxx/rule.cxx
index ccc9bb5..3cab2d4 100644
--- a/build/cxx/rule.cxx
+++ b/build/cxx/rule.cxx
@@ -12,6 +12,8 @@
 
 #include <ext/stdio_filebuf.h>
 
+#include <build/scope>
+#include <build/algorithm>
 #include <build/process>
 #include <build/timestamp>
 #include <build/diagnostics>
@@ -45,26 +47,47 @@ namespace build
 
       // See if we have a source file.
       //
-      const cxx* s (nullptr);
-      for (const target& p: t.prerequisites ())
+      prerequisite* sp (nullptr);
+      for (prerequisite& p: t.prerequisites)
       {
-        if ((s = dynamic_cast<const cxx*> (&p)) != nullptr)
+        if (p.type.id == typeid (cxx))
+        {
+          sp = &p;
           break;
+        }
       }
 
-      if (s == nullptr)
+      if (sp == nullptr)
+      {
+        cout << "no source file" << endl;
         return recipe ();
+      }
 
       // Derive object file name from target name.
       //
       obj& o (dynamic_cast<obj&> (t));
 
       if (o.path ().empty ())
-        o.path (path (o.name () + ".o"));
+        o.path (o.directory / path (o.name + ".o"));
 
-      // Inject additional prerequisites.
+      // Resolve prerequisite to target and match it to a rule. We need
+      // this in order to get the source file path for prerequisite
+      // injections.
       //
-      inject_prerequisites (o, *s);
+      cxx* st (
+        dynamic_cast<cxx*> (
+          sp->target != nullptr ? sp->target : search (*sp)));
+
+      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);
+        }
+      }
 
       return recipe (&update);
     }
@@ -112,13 +135,13 @@ namespace build
     }
 
     void compile::
-    inject_prerequisites (obj& o, const cxx& s) const
+    inject_prerequisites (obj& o, const cxx& s, scope& ds) const
     {
       const char* args[] = {
         "g++-4.9",
         "-std=c++14",
         "-I..",
-        "-M",
+        "-MM",      //@@ TMP -M
         "-MG",      // Treat missing headers as generated.
         "-MQ", "*", // Quoted target (older version can't handle empty name).
         s.path ().string ().c_str (),
@@ -142,7 +165,7 @@ namespace build
             throw error ();
           }
 
-          size_t p (0);
+          size_t pos (0);
 
           if (first)
           {
@@ -153,28 +176,47 @@ namespace build
               break;
 
             assert (l[0] == '*' && l[1] == ':' && l[2] == ' ');
-            next (l, (p = 3)); // Skip the source file.
+            next (l, (pos = 3)); // Skip the source file.
 
             first = false;
           }
 
-          while (p != l.size ())
+          while (pos != l.size ())
           {
-            path d (next (l, p));
+            path file (next (l, pos));
+            file.normalize ();
 
-            // If there is no extension (e.g., std C++ headers), then
-            // assume it is a header. Otherwise, let the normall
-            // mechanism to figure the type from the extension.
+            // 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:
             //
-            // - memory leak
 
-            hxx& h (*new hxx (d.leaf ().base ().string ()));
-            h.path (d);
+            // Split the name into its directory part and the name part.
+            // Here we assume the name part is a valid filesystem name.
+            //
+            path d (file.directory ());
+            string n (file.leaf ().base ().string ());
+
+            // Find or insert.
+            //
+            auto r (ds.prerequisites.emplace (
+                      hxx::static_type, move (n), move (d), ds));
+
+            auto& p (const_cast<prerequisite&> (*r.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)));
 
-            o.prerequisite (h);
+            if (t.path ().empty ())
+              t.path (file);
+
+            o.prerequisites.push_back (p);
           }
         }
 
@@ -208,14 +250,16 @@ namespace build
       bool u (mt == timestamp_nonexistent);
       const cxx* s (nullptr);
 
-      for (const target& p: t.prerequisites ())
+      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&> (p));
+          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
@@ -229,7 +273,7 @@ namespace build
         }
 
         if (s == nullptr)
-          s = dynamic_cast<const cxx*> (&p);
+          s = dynamic_cast<const cxx*> (&pt);
 
         if (u && s != nullptr)
           break;
@@ -241,6 +285,7 @@ namespace build
       const char* args[] = {
         "g++-4.9",
         "-std=c++14",
+        "-g",
         "-I..",
         "-c",
         "-o", o.path ().string ().c_str (),
@@ -300,14 +345,17 @@ namespace build
 
       // See if we have at least one object file.
       //
-      const obj* o (nullptr);
-      for (const target& p: t.prerequisites ())
+      prerequisite* op (nullptr);
+      for (prerequisite& p: t.prerequisites)
       {
-        if ((o = dynamic_cast<const obj*> (&p)) != nullptr)
+        if (p.type.id == typeid (obj))
+        {
+          op = &p;
           break;
+        }
       }
 
-      if (o == nullptr)
+      if (op == nullptr)
         return recipe ();
 
       // Derive executable file name from target name.
@@ -315,7 +363,7 @@ namespace build
       exe& e (dynamic_cast<exe&> (t));
 
       if (e.path ().empty ())
-        e.path (path (e.name ()));
+        e.path (e.directory / path (e.name));
 
       return recipe (&update);
     }
@@ -333,12 +381,14 @@ namespace build
 
       bool u (mt == timestamp_nonexistent);
 
-      for (const target& p: t.prerequisites ())
+      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&> (p));
+        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
@@ -357,13 +407,13 @@ namespace build
       if (!u)
         return target_state::uptodate;
 
-      vector<const char*> args {"g++-4.9", "-std=c++14", "-o"};
+      vector<const char*> args {"g++-4.9", "-std=c++14", "-g", "-o"};
 
       args.push_back (e.path ().string ().c_str ());
 
-      for (const target& p: t.prerequisites ())
+      for (const prerequisite& p: t.prerequisites)
       {
-        const obj& o (dynamic_cast<const obj&> (p));
+        const obj& o (dynamic_cast<const obj&> (*p.target));
         args.push_back (o.path ().string ().c_str ());
       }
 
diff --git a/build/cxx/target b/build/cxx/target
index fe17c36..37b093b 100644
--- a/build/cxx/target
+++ b/build/cxx/target
@@ -16,8 +16,9 @@ namespace build
     public:
       using file::file;
 
-    public: virtual const type_info& type_id () const {return ti_;}
-    protected: static const type_info ti_;
+    public:
+      virtual const target_type& type () const {return static_type;}
+      static const target_type static_type;
     };
 
     class ixx: public file
@@ -25,8 +26,9 @@ namespace build
     public:
       using file::file;
 
-    public: virtual const type_info& type_id () const {return ti_;}
-    protected: static const type_info ti_;
+    public:
+      virtual const target_type& type () const {return static_type;}
+      static const target_type static_type;
     };
 
     class txx: public file
@@ -34,8 +36,9 @@ namespace build
     public:
       using file::file;
 
-    public: virtual const type_info& type_id () const {return ti_;}
-    protected: static const type_info ti_;
+    public:
+      virtual const target_type& type () const {return static_type;}
+      static const target_type static_type;
     };
 
     class cxx: public file
@@ -43,8 +46,9 @@ namespace build
     public:
       using file::file;
 
-    public: virtual const type_info& type_id () const {return ti_;}
-    protected: static const type_info ti_;
+    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 7171e30..c4502b4 100644
--- a/build/cxx/target.cxx
+++ b/build/cxx/target.cxx
@@ -10,11 +10,16 @@ namespace build
 {
   namespace cxx
   {
-    using type_info = target::type_info;
+    const target_type hxx::static_type {
+      typeid (hxx), "hxx", &file::static_type, &target_factory<hxx>};
 
-    const type_info hxx::ti_ {typeid (hxx), "hxx", &file::ti_};
-    const type_info ixx::ti_ {typeid (ixx), "ixx", &file::ti_};
-    const type_info txx::ti_ {typeid (txx), "txx", &file::ti_};
-    const type_info cxx::ti_ {typeid (cxx), "cxx", &file::ti_};
+    const target_type ixx::static_type {
+      typeid (ixx), "ixx", &file::static_type, &target_factory<ixx>};
+
+    const target_type txx::static_type {
+      typeid (txx), "txx", &file::static_type, &target_factory<txx>};
+
+    const target_type cxx::static_type {
+      typeid (cxx), "cxx", &file::static_type, &target_factory<cxx>};
   }
 }
diff --git a/build/native b/build/native
index 29ad653..6107705 100644
--- a/build/native
+++ b/build/native
@@ -14,8 +14,9 @@ namespace build
   public:
     using file::file;
 
-  public: virtual const type_info& type_id () const {return ti_;}
-  protected: static const type_info ti_;
+  public:
+    virtual const target_type& type () const {return static_type;}
+    static const target_type static_type;
   };
 
   class obj: public file
@@ -23,8 +24,9 @@ namespace build
   public:
     using file::file;
 
-  public: virtual const type_info& type_id () const {return ti_;}
-  protected: static const type_info ti_;
+  public:
+    virtual const target_type& type () const {return static_type;}
+    static const target_type static_type;
   };
 }
 
diff --git a/build/native.cxx b/build/native.cxx
index 6130578..61ecb72 100644
--- a/build/native.cxx
+++ b/build/native.cxx
@@ -8,8 +8,9 @@ using namespace std;
 
 namespace build
 {
-  using type_info = target::type_info;
+  const target_type exe::static_type {
+    typeid (exe), "exe", &file::static_type, &target_factory<exe>};
 
-  const type_info exe::ti_ {typeid (exe), "exe", &file::ti_};
-  const type_info obj::ti_ {typeid (obj), "obj", &file::ti_};
+  const target_type obj::static_type {
+    typeid (obj), "obj", &file::static_type, &target_factory<obj>};
 }
diff --git a/build/parser b/build/parser
index c487015..e8e7314 100644
--- a/build/parser
+++ b/build/parser
@@ -8,12 +8,16 @@
 #include <string>
 #include <vector>
 #include <iosfwd>
+#include <utility>   // std::move
 #include <exception>
 
+
 #include <build/path>
 
 namespace build
 {
+  class scope;
+
   class token;
   enum class token_type;
   class lexer;
@@ -28,12 +32,21 @@ namespace build
     parser (std::ostream& diag): diag_ (diag) {}
 
     void
-    parse (std::istream&, const path&);
+    parse (std::istream&, const path&, scope&);
 
     // Recursive descent parser.
     //
   private:
-    typedef std::vector<std::string> names;
+    struct name_type
+    {
+      name_type (std::string t, std::string n)
+          : type (std::move (t)), name (std::move (n)) {}
+
+      std::string type; // Empty if untyped.
+      std::string name;
+    };
+
+    typedef std::vector<name_type> names;
 
     void
     parse_clause (token&, token_type&);
@@ -42,12 +55,12 @@ namespace build
     parse_names (token& t, token_type& tt)
     {
       names ns;
-      parse_names (t, tt, ns);
+      parse_names (t, tt, ns, nullptr);
       return ns;
     }
 
     void
-    parse_names (token&, token_type&, names&);
+    parse_names (token&, token_type&, names&, const std::string* type);
 
     // Utilities.
     //
@@ -63,6 +76,7 @@ namespace build
 
     lexer* lexer_;
     const path* path_;
+    scope* scope_;
   };
 }
 
diff --git a/build/parser.cxx b/build/parser.cxx
index 348d285..e300201 100644
--- a/build/parser.cxx
+++ b/build/parser.cxx
@@ -4,11 +4,16 @@
 
 #include <build/parser>
 
+#include <memory>   // unique_ptr
 #include <iostream>
 
 #include <build/token>
 #include <build/lexer>
 
+#include <build/scope>
+#include <build/target>
+#include <build/prerequisite>
+
 using namespace std;
 
 namespace build
@@ -21,11 +26,12 @@ namespace build
   typedef token_type type;
 
   void parser::
-  parse (istream& is, const path& p)
+  parse (istream& is, const path& p, scope& s)
   {
     lexer l (is, p.string (), diag_);
     lexer_ = &l;
     path_ = &p;
+    scope_ = &s;
 
     token t (type::eos, 0, 0);
     type tt;
@@ -50,7 +56,7 @@ namespace build
       if (tt != type::name && tt != type::lcbrace)
         break; // Something else. Let our caller handle that.
 
-      names ns (parse_names (t, tt));
+      names tns (parse_names (t, tt));
 
       if (tt == type::colon)
       {
@@ -60,7 +66,127 @@ namespace build
         //
         if (tt == type::name || tt == type::lcbrace)
         {
-          names ns (parse_names (t, tt));
+          names pns (parse_names (t, tt));
+
+          // Prepare the prerequisite list.
+          //
+          target::prerequisites_type ps;
+          ps.reserve (pns.size ());
+
+          for (auto& pn: pns)
+          {
+            // Resolve prerequisite type.
+            //
+            //@@ TODO: derive type from extension, factor to common function
+            //
+            const char* tt (pn.type.empty () ? "file" : pn.type.c_str ());
+
+            auto i (target_types.find (tt));
+
+            if (i == target_types.end ())
+            {
+              //@@ TODO name (or better yet, type) location
+
+              error (t) << "unknown prerequisite type '" << tt << "'" << endl;
+              throw parser_error ();
+            }
+
+            const target_type& ti (i->second);
+
+            // We need to split the name into its directory part (if any)
+            // and the name part. We cannot assume the name part is a
+            // valid filesystem name so we will have to do the splitting
+            // manually.
+            //
+            path d;
+            string n;
+
+            {
+              path::size_type i (path::traits::rfind_separator (pn.name));
+
+              if (i == string::npos)
+                n = move (pn.name); // NOTE: steal!
+              else
+              {
+                d = path (pn.name, i);
+                n.assign (pn.name, i + 1, string::npos);
+                d.normalize ();
+              }
+            }
+
+            //cout << "prerequisite " << tt << " " << n << " " << d << endl;
+
+            // Find or insert.
+            //
+            auto r (scope_->prerequisites.emplace (
+                      ti, move (n), move (d), *scope_));
+
+            ps.push_back (const_cast<prerequisite&> (*r.first));
+          }
+
+          for (auto& tn: tns)
+          {
+            path d;
+            string n;
+
+            // The same deal as in handling prerequisites above.
+            //
+            {
+              path::size_type i (path::traits::rfind_separator (tn.name));
+
+              if (i == string::npos)
+              {
+                d = scope_->path (); // Already normalized.
+                n = move (tn.name); // NOTE: steal!
+              }
+              else
+              {
+                d = path (tn.name, i);
+                n.assign (tn.name, i + 1, string::npos);
+
+                if (d.relative ())
+                  d = scope_->path () / d;
+
+                d.normalize ();
+              }
+            }
+
+            // Resolve target type.
+            //
+            //@@ TODO: derive type from extension
+            //
+            const char* tt (tn.type.empty () ? "file" : tn.type.c_str ());
+
+            auto i (target_types.find (tt));
+
+            if (i == target_types.end ())
+            {
+              //@@ TODO name (or better yet, type) location
+
+              error (t) << "unknown target type '" << tt << "'" << endl;
+              throw parser_error ();
+            }
+
+            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 (n), move (d)))));
+
+            target& t (**r.first);
+
+            t.prerequisites = ps; //@@ TODO: move is last target.
+
+            if (default_target == nullptr)
+              default_target = &t;
+          }
 
           if (tt == type::newline)
             next (t, tt);
@@ -88,14 +214,14 @@ namespace build
             }
 
             // See if this is a directory or target scope. Different
-            // things can appear inside depending on which it is.
+            // things can appear inside depending on which one it is.
             //
             bool dir (false);
-            for (const auto& n: ns)
+            for (const auto& n: tns)
             {
-              if (n.back () == '/')
+              if (n.type.empty () && n.name.back () == '/')
               {
-                if (ns.size () != 1)
+                if (tns.size () != 1)
                 {
                   // @@ TODO: point to name.
                   //
@@ -110,9 +236,21 @@ namespace build
             next (t, tt);
 
             if (dir)
+            {
+              scope& prev (*scope_);
+              path p (tns[0].name);
+
+              if (p.relative ())
+                p = prev.path () / p;
+
+              scope_ = &scopes[p];
+
               // A directory scope can contain anything that a top level can.
               //
               parse_clause (t, tt);
+
+              scope_ = &prev;
+            }
             else
             {
               // @@ TODO: target scope.
@@ -151,7 +289,7 @@ namespace build
   }
 
   void parser::
-  parse_names (token& t, type& tt, names& ns)
+  parse_names (token& t, type& tt, names& ns, const string* tp)
   {
     for (bool first (true);; first = false)
     {
@@ -160,7 +298,7 @@ namespace build
       if (tt == type::lcbrace)
       {
         next (t, tt);
-        parse_names (t, tt, ns);
+        parse_names (t, tt, ns, tp);
 
         if (tt != type::rcbrace)
         {
@@ -176,20 +314,20 @@ namespace build
       //
       if (tt == type::name)
       {
-        string name (t.name ());
+        string name (t.name ()); //@@ move?
 
         // See if this is a type name, that is, it is followed by '{'.
         //
         if (next (t, tt) == type::lcbrace)
         {
-          //cout << "type: " << name << endl;
+          if (tp != nullptr)
+          {
+            error (t) << "nested type name '" << name << "'" << endl;
+            throw parser_error ();
+          }
 
-          //@@ TODO:
-          //
-          //   - detect nested typed name groups, e.g., 'cxx{hxx{foo}}'.
-          //
           next (t, tt);
-          parse_names (t, tt, ns);
+          parse_names (t, tt, ns, &name);
 
           if (tt != type::rcbrace)
           {
@@ -201,9 +339,7 @@ namespace build
           continue;
         }
 
-        // This is a target, directory, or variable name.
-        //cout << "name: " << name << endl;
-        ns.push_back (name);
+        ns.emplace_back ((tp != nullptr ? *tp : string ()), move (name));
         continue;
       }
 
diff --git a/build/path b/build/path
index 97fb154..bdb9b72 100644
--- a/build/path
+++ b/build/path
@@ -7,6 +7,7 @@
 
 #include <string>
 #include <ostream>
+#include <utility> // move
 #include <exception>
 
 namespace build
@@ -168,8 +169,14 @@ namespace build
     }
 
     explicit
-    basic_path (string_type const& s)
-        : path_ (s)
+    basic_path (string_type s)
+        : path_ (std::move (s))
+    {
+      init ();
+    }
+
+    basic_path (const string_type& s, size_type n)
+        : path_ (s, 0, n)
     {
       init ();
     }
diff --git a/build/prerequisite b/build/prerequisite
new file mode 100644
index 0000000..e58532d
--- /dev/null
+++ b/build/prerequisite
@@ -0,0 +1,53 @@
+// file      : build/prerequisite -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD_PREREQUISITE
+#define BUILD_PREREQUISITE
+
+#include <set>
+#include <string>
+#include <iosfwd>
+#include <utility>    // move
+#include <typeindex>
+
+#include <build/path>
+
+namespace build
+{
+  class scope;
+  class target;
+  class target_type;
+
+  class prerequisite
+  {
+  public:
+    typedef build::target target_type;
+    typedef build::target_type target_type_type;
+    typedef build::scope scope_type;
+
+    prerequisite (const target_type_type& t,
+                  std::string n,
+                  path d,
+                  scope_type& s)
+        : type (t), name (std::move (n)), directory (std::move (d)),
+          scope (s), target (0) {}
+
+  public:
+    const target_type_type& type;
+    const std::string name;
+    const path directory; // Normalized absolute or relative (to scope).
+    scope_type& scope;
+    target_type* target; // NULL if not yet resolved.
+  };
+
+  std::ostream&
+  operator<< (std::ostream&, const prerequisite&);
+
+  bool
+  operator< (const prerequisite&, const prerequisite&);
+
+  typedef std::set<prerequisite> prerequisite_set;
+}
+
+#endif // BUILD_PREREQUISITE
diff --git a/build/prerequisite.cxx b/build/prerequisite.cxx
new file mode 100644
index 0000000..8153a6c
--- /dev/null
+++ b/build/prerequisite.cxx
@@ -0,0 +1,32 @@
+// file      : build/prerequisite.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <build/prerequisite>
+
+#include <ostream>
+
+#include <build/target> // target_type
+
+using namespace std;
+
+namespace build
+{
+  ostream&
+  operator<< (ostream& os, const prerequisite& p)
+  {
+    // @@ TODO: need to come up with a relative (to current) path.
+
+    return os << p.type.name << '{' << p.name << '}';
+  }
+
+  bool
+  operator< (const prerequisite& x, const prerequisite& y)
+  {
+    return
+      (x.type.id < y.type.id) ||
+      (x.type.id == y.type.id && x.name < y.name) ||
+      (x.type.id == y.type.id && x.name == y.name &&
+       x.directory < y.directory);
+  }
+}
diff --git a/build/rule.cxx b/build/rule.cxx
index fe4c4b2..b1730e1 100644
--- a/build/rule.cxx
+++ b/build/rule.cxx
@@ -26,6 +26,11 @@ namespace build
 
     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));
+
     return pt.mtime () != timestamp_nonexistent ? &update : nullptr;
   }
 
@@ -37,16 +42,18 @@ namespace build
     path_target& pt (dynamic_cast<path_target&> (t));
     timestamp mt (pt.mtime ());
 
-    for (const target& p: t.prerequisites ())
+    for (const prerequisite& p: t.prerequisites)
     {
+      const target& pt (*p.target); // Should be resolved at this stage.
+
       // If this is an mtime-based target, then simply compare timestamps.
       //
-      if (auto mtp = dynamic_cast<const mtime_target*> (&p))
+      if (auto mtp = dynamic_cast<const mtime_target*> (&pt))
       {
         if (mt < mtp->mtime ())
         {
           cerr << "error: no rule to update target " << t << endl
-               << "info: prerequisite " << p << " is ahead of " << t <<
+               << "info: prerequisite " << pt << " is ahead of " << t <<
             " by " << (mtp->mtime () - mt) << endl;
 
           return target_state::failed;
@@ -56,10 +63,10 @@ namespace build
       {
         // Otherwise we assume the prerequisite is newer if it was updated.
         //
-        if (p.state () == target_state::updated)
+        if (pt.state () == target_state::updated)
         {
           cerr << "error: no rule to update target " << t << endl
-               << "info: prerequisite " << p << " is ahead of " << t <<
+               << "info: prerequisite " << pt << " is ahead of " << t <<
             " because it was updated" << endl;
 
           return target_state::failed;
diff --git a/build/scope b/build/scope
new file mode 100644
index 0000000..760fc03
--- /dev/null
+++ b/build/scope
@@ -0,0 +1,59 @@
+// file      : build/scope -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD_SCOPE
+#define BUILD_SCOPE
+
+#include <map>
+
+#include <build/path>
+#include <build/prerequisite>
+
+namespace build
+{
+  class scope
+  {
+  public:
+    typedef build::path path_type;
+
+    const path_type&
+    path () const {return i_->first;} // Absolute and normalized.
+
+  private:
+    friend class scope_map;
+
+    typedef std::map<path_type, scope>::const_iterator iterator;
+
+    scope () = default;
+
+    void
+    init (const iterator& i) {i_ = i;}
+
+  public:
+    prerequisite_set prerequisites;
+
+  private:
+    iterator i_;
+  };
+
+  class scope_map: std::map<path, scope>
+  {
+  public:
+    scope&
+    operator[] (const path& k)
+    {
+      auto i (emplace (k, scope ()));
+      auto& r (i.first->second);
+
+      if (i.second)
+        r.init (i.first);
+
+      return r;
+    }
+  };
+
+  extern scope_map scopes;
+}
+
+#endif // BUILD_SCOPE
diff --git a/build/scope.cxx b/build/scope.cxx
new file mode 100644
index 0000000..0f99b0e
--- /dev/null
+++ b/build/scope.cxx
@@ -0,0 +1,12 @@
+// file      : build/scope.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <build/scope>
+
+using namespace std;
+
+namespace build
+{
+  scope_map scopes;
+}
diff --git a/build/target b/build/target
index 01cddc4..a381fd0 100644
--- a/build/target
+++ b/build/target
@@ -5,8 +5,11 @@
 #ifndef BUILD_TARGET
 #define BUILD_TARGET
 
+#include <set>
+#include <map>
 #include <string>
 #include <vector>
+#include <memory>     // unique_ptr
 #include <functional> // function, reference_wrapper
 #include <typeindex>
 #include <iosfwd>
@@ -15,6 +18,8 @@
 
 #include <build/path>
 #include <build/timestamp>
+#include <build/prerequisite>
+#include <build/utility>       // compare_c_string, compare_pointer_target
 
 namespace build
 {
@@ -23,24 +28,29 @@ namespace build
   enum class target_state {unknown, uptodate, updated, failed};
   typedef std::function<target_state (target&)> recipe;
 
-  typedef std::vector<std::reference_wrapper<target>> targets;
+  struct target_type
+  {
+    std::type_index id;
+    const char* name;
+    const target_type* base;
+    target* (*const factory) (std::string, path);
+  };
 
   class target
   {
   public:
-    target (std::string n): name_ (std::move (n)) {}
-
-    const std::string&
-    name () const {return name_;}
+    target (std::string n, path d)
+        : name (std::move (n)), directory (std::move (d)) {}
 
-    const targets&
-    prerequisites () const {return prerequisites_;}
+    const std::string name;
+    const path directory; // Absolute and normalized.
 
-    targets&
-    prerequisites () {return prerequisites_;}
+  public:
+    typedef
+    std::vector<std::reference_wrapper<prerequisite>>
+    prerequisites_type;
 
-    void
-    prerequisite (target& t) {prerequisites_.push_back (t);}
+    prerequisites_type prerequisites;
 
   public:
     typedef build::recipe recipe_type;
@@ -63,22 +73,10 @@ namespace build
     target& operator= (const target&) = delete;
 
   public:
-    struct type_info
-    {
-      std::type_index id;
-      const char* name;
-      const type_info* base;
-    };
-
-    virtual const type_info&
-    type_id () const = 0;
-
-  protected:
-    static const type_info ti_;
+    virtual const target_type& type () const = 0;
+    static const target_type static_type;
 
   private:
-    std::string name_;
-    targets prerequisites_;
     recipe_type recipe_;
     target_state state_ {target_state::unknown};
   };
@@ -86,6 +84,40 @@ namespace build
   std::ostream&
   operator<< (std::ostream&, const target&);
 
+  inline bool
+  operator< (const target& x, const target& y)
+  {
+    std::type_index tx (typeid (x)), ty (typeid (y));
+
+    return
+      (tx < ty) ||
+      (tx == ty && x.name < y.name) ||
+      (tx == ty && x.name == y.name && x.directory < y.directory);
+  }
+
+  typedef std::set<std::unique_ptr<target>, compare_pointer_target> target_set;
+  extern target_set targets;
+  extern target* default_target;
+
+  class target_type_map: public std::map<
+    const char*,
+    std::reference_wrapper<const target_type>,
+    compare_c_string>
+  {
+  public:
+    void
+    insert (const target_type& tt) {emplace (tt.name, tt);}
+  };
+
+  extern target_type_map target_types;
+
+  template <typename T>
+  target*
+  target_factory (std::string n, path d)
+  {
+    return new T (std::move (n), std::move (d));
+  }
+
   // Modification time-based target.
   //
   class mtime_target: public target
@@ -109,7 +141,8 @@ namespace build
     virtual timestamp
     load_mtime () const = 0;
 
-  protected: static const type_info ti_;
+  public:
+    static const target_type static_type;
 
   private:
     mutable timestamp mtime_ {timestamp_unknown};
@@ -134,7 +167,8 @@ namespace build
     virtual timestamp
     load_mtime () const;
 
-  protected: static const type_info ti_;
+  public:
+    static const target_type static_type;
 
   private:
     path_type path_;
@@ -147,8 +181,9 @@ namespace build
   public:
     using path_target::path_target;
 
-  public: virtual const type_info& type_id () const {return ti_;}
-  protected: static const type_info ti_;
+  public:
+    virtual const target_type& type () const {return static_type;}
+    static const target_type static_type;
   };
 }
 
diff --git a/build/target.cxx b/build/target.cxx
index e3e3d4d..8314ba4 100644
--- a/build/target.cxx
+++ b/build/target.cxx
@@ -15,9 +15,15 @@ namespace build
   ostream&
   operator<< (ostream& os, const target& t)
   {
-    return os << t.type_id ().name << '{' << t.name () << '}';
+    // @@ TODO: need to come up with a relative (to current) path.
+
+    return os << t.type ().name << '{' << t.name << '}';
   }
 
+  target_set targets;
+  target* default_target = nullptr;
+  target_type_map target_types;
+
   // path_target
   //
   timestamp path_target::
@@ -27,12 +33,15 @@ namespace build
     return path_mtime (path_);
   }
 
-  using type_info = target::type_info;
+  const target_type target::static_type {
+    typeid (target), "target", nullptr, nullptr};
+
+  const target_type mtime_target::static_type {
+    typeid (mtime_target), "mtime_target", &target::static_type, nullptr};
+
+  const target_type path_target::static_type {
+    typeid (path_target), "path_target", &mtime_target::static_type, nullptr};
 
-  const type_info target::ti_ {typeid (target), "target", nullptr};
-  const type_info mtime_target::ti_ {
-    typeid (mtime_target), "mtime_target", &target::ti_};
-  const type_info path_target::ti_ {
-    typeid (path_target), "path_target", &mtime_target::ti_};
-  const type_info file::ti_ {typeid (file), "file", &path_target::ti_};
+  const target_type file::static_type {
+    typeid (file), "file", &path_target::static_type, &target_factory<file>};
 }
diff --git a/build/utility b/build/utility
new file mode 100644
index 0000000..bef6335
--- /dev/null
+++ b/build/utility
@@ -0,0 +1,27 @@
+// file      : build/utility -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD_UTILITY
+#define BUILD_UTILITY
+
+#include <cstring> // strcmp
+
+namespace build
+{
+  struct compare_c_string
+  {
+    bool operator() (const char* x, const char* y) const
+    {
+      return std::strcmp (x, y) < 0;
+    }
+  };
+
+  struct compare_pointer_target
+  {
+    template <typename P>
+    bool operator() (const P& x, const P& y) const {return *x < *y;}
+  };
+}
+
+#endif // BUILD_UTILITY
diff --git a/tests/build/parser/driver.cxx b/tests/build/parser/driver.cxx
index 0b83cb0..a8c8fc9 100644
--- a/tests/build/parser/driver.cxx
+++ b/tests/build/parser/driver.cxx
@@ -7,6 +7,10 @@
 #include <iostream>
 
 #include <build/path>
+#include <build/scope>
+#include <build/target>
+#include <build/native>
+
 #include <build/lexer>
 #include <build/parser>
 
@@ -19,6 +23,10 @@ parse (const char*);
 int
 main ()
 {
+  target_types.insert (file::static_type);
+  target_types.insert (exe::static_type);
+  target_types.insert (obj::static_type);
+
   assert (parse (""));
   assert (parse ("foo:"));
   assert (parse ("foo bar:"));
@@ -36,7 +44,7 @@ main ()
   assert (parse ("exe{foo bar}:"));
   assert (parse ("{exe{foo bar}}:"));
   assert (parse ("exe{{foo bar} fox}:"));
-  assert (parse ("exe{foo}: obj{bar baz} biz.o lib{fox}"));
+  assert (parse ("exe{foo}: obj{bar baz} biz.o file{fox}"));
 
   assert (!parse (":"));
   assert (!parse ("foo"));
@@ -77,7 +85,7 @@ parse (const char* s)
 
   try
   {
-    p.parse (is, path ());
+    p.parse (is, path (), scopes[path::current ()]);
   }
   catch (const parser_error&)
   {