Implement rule ambiguity detection

Also establish the infrastructure for rule hinting

6 files changed, 111 insertions, 21 deletions

diff --git a/build/algorithm.cxx b/build/algorithm.cxx
index 1d7f215..a4160ef 100644
--- a/build/algorithm.cxx
+++ b/build/algorithm.cxx
@@ -84,29 +84,116 @@ namespace build
          tt != nullptr && !t.recipe ();
          tt = tt->base)
     {
-      for (auto rs (rules.equal_range (tt->id));
-           rs.first != rs.second;
-           ++rs.first)
+      auto i (rules.find (tt->id));
+
+      if (i == rules.end ()) // No rules registered for this target type.
+        continue;
+
+      const auto& rules (i->second); // Name map.
+
+      string hint; // @@ TODO
+      bool single;
+
+      auto rs (hint.empty ()
+               ? make_pair (rules.begin (), rules.end ())
+               : rules.find (hint));
+
+      for (auto i (rs.first); i != rs.second;)
       {
-        const rule& ru (rs.first->second);
+        const string& n (i->first);
+        const rule& ru (i->second);
 
-        recipe re;
+        if (i++ == rs.first)
+          single = (i == rs.second);
 
+        recipe re;
+        string h (hint);
         {
           auto g (
             make_exception_guard (
-              [] (target& t)
+              [] (target& t, const string& n)
               {
-                cerr << "info: while matching a rule for target " << t << endl;
+                cerr << "info: while matching rule " << n
+                     << " for target " << t << endl;
               },
-              t));
+              t, n));
 
-          re = ru.match (t);
+          // If the rule matches, then it updates the hint with the one we
+          // need to use when checking for ambiguity.
+          //
+          re = ru.match (t, single, h);
         }
 
         if (re)
         {
           t.recipe (re);
+
+          // If the returned hint is more "general" than what we had,
+          // then narrow it back down.
+          //
+          if (h < hint)
+            h = hint;
+
+          // Do the ambiguity test unless it is an unambiguous match (the
+          // hint is the rule's full name).
+          //
+          if (h == n)
+            break;
+
+          auto rs1 (h == hint
+                    ? make_pair (i, rs.second) // Continue iterating.
+                    : rules.find (h));
+
+          bool ambig (false);
+
+          // See if any other rules match.
+          //
+          for (auto i (rs1.first); i != rs1.second; ++i)
+          {
+            const string& n1 (i->first);
+            const rule& ru1 (i->second);
+
+            string h1 (h);
+            {
+              auto g (
+                make_exception_guard (
+                  [] (target& t, const string& n1)
+                  {
+                    cerr << "info: while matching rule " << n1
+                         << " for target " << t << endl;
+                  },
+                  t, n1));
+
+              re = ru1.match (t, false, h1);
+            }
+
+            if (re)
+            {
+              // A subsequent rule cannot return a more specific hint.
+              // Remember, the hint returning mechanism is here to
+              // indicate that only a class of rules that perform a
+              // similar rule chaining transformation may apply (e.g.,
+              // cxx.gnu and cxx.clang).
+              //
+              assert (h1 <= h);
+
+              if (!ambig)
+              {
+                cerr << "error: multiple rules matching target " << t << endl;
+                cerr << "info: rule " << n << " matches" << endl;
+                ambig = true;
+              }
+
+              cerr << "info: rule " << n1 << " also matches" << endl;
+            }
+          }
+
+          if (ambig)
+          {
+            cerr << "info: use rule hint to disambiguate this match" << endl;
+            throw error ();
+          }
+
           break;
         }
       }
diff --git a/build/b.cxx b/build/b.cxx
index ad68e21..5135761 100644
--- a/build/b.cxx
+++ b/build/b.cxx
@@ -257,13 +257,13 @@ main (int argc, char* argv[])
   // Register rules.
   //
   cxx::link cxx_link;
-  rules.emplace (typeid (exe), cxx_link);
+  rules[typeid (exe)].emplace ("cxx.gnu.link", cxx_link);
 
   cxx::compile cxx_compile;
-  rules.emplace (typeid (obj), cxx_compile);
+  rules[typeid (obj)].emplace ("cxx.gnu.compile", cxx_compile);
 
   default_path_rule path_exists;
-  rules.emplace (typeid (path_target), path_exists);
+  rules[typeid (path_target)].emplace ("", path_exists);
 
   // Build.
   //
diff --git a/build/cxx/rule b/build/cxx/rule
index 99e688d..8924c7c 100644
--- a/build/cxx/rule
+++ b/build/cxx/rule
@@ -23,7 +23,7 @@ namespace build
     {
     public:
       virtual recipe
-      match (target&) const;
+      match (target&, bool single, std::string& hint) const;
 
       static target_state
       update (target&);
@@ -37,7 +37,7 @@ namespace build
     {
     public:
       virtual recipe
-      match (target&) const;
+      match (target&, bool single, std::string& hint) const;
 
       static target_state
       update (target&);
diff --git a/build/cxx/rule.cxx b/build/cxx/rule.cxx
index c6ceb1a..3a97576 100644
--- a/build/cxx/rule.cxx
+++ b/build/cxx/rule.cxx
@@ -28,7 +28,7 @@ namespace build
     // compile
     //
     recipe compile::
-    match (target& t) const
+    match (target& t, bool single, std::string& hint) const
     {
       tracer tr ("cxx::compile::match");
 
@@ -375,7 +375,7 @@ namespace build
     // link
     //
     recipe link::
-    match (target& t) const
+    match (target& t, bool single, std::string& hint) const
     {
       // @@ TODO:
       //
diff --git a/build/rule b/build/rule
index 6bb58fe..91ef0ca 100644
--- a/build/rule
+++ b/build/rule
@@ -5,11 +5,13 @@
 #ifndef BUILD_RULE
 #define BUILD_RULE
 
+#include <string>
 #include <typeindex>
 #include <functional>     // reference_wrapper
 #include <unordered_map>
 
 #include <build/target>
+#include <build/prefix_map>
 
 namespace build
 {
@@ -17,11 +19,12 @@ namespace build
   {
   public:
     virtual recipe
-    match (target&) const = 0;
+    match (target&, bool single, std::string& hint) const = 0;
   };
 
-  typedef std::unordered_multimap<std::type_index,
-                                  std::reference_wrapper<rule>> rule_map;
+  typedef std::unordered_map<
+    std::type_index,
+    prefix_multimap<std::string, std::reference_wrapper<rule>, '.'>> rule_map;
 
   extern rule_map rules;
 
@@ -29,7 +32,7 @@ namespace build
   {
   public:
     virtual recipe
-    match (target&) const;
+    match (target&, bool single, std::string& hint) const;
 
     static target_state
     update (target&);
diff --git a/build/rule.cxx b/build/rule.cxx
index b1730e1..c116538 100644
--- a/build/rule.cxx
+++ b/build/rule.cxx
@@ -15,7 +15,7 @@ namespace build
   // default_path_rule
   //
   recipe default_path_rule::
-  match (target& t) const
+  match (target& t, bool, std::string&) const
   {
     // @@ TODO:
     //