Use hash map/set for targets/prerequisites to resolve key change issue

7 files changed, 127 insertions, 38 deletions

diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx
index ce25acf..1b19fe5 100644
--- a/build2/algorithm.cxx
+++ b/build2/algorithm.cxx
@@ -21,8 +21,8 @@ namespace build2
   target&
   search (const prerequisite_key& pk)
   {
-    // If this is a project-qualified prerequisite, then this
-    // is import's business.
+    // If this is a project-qualified prerequisite, then this is import's
+    // business.
     //
     if (pk.proj != nullptr)
       return import (pk);
diff --git a/build2/config/operation.cxx b/build2/config/operation.cxx
index 1c395d2..fe36034 100644
--- a/build2/config/operation.cxx
+++ b/build2/config/operation.cxx
@@ -4,6 +4,7 @@
 
 #include <build2/config/operation>
 
+#include <set>
 #include <fstream>
 
 #include <butl/filesystem>
diff --git a/build2/prerequisite b/build2/prerequisite
index f316fb5..7c913f3 100644
--- a/build2/prerequisite
+++ b/build2/prerequisite
@@ -5,7 +5,8 @@
 #ifndef BUILD2_PREREQUISITE
 #define BUILD2_PREREQUISITE
 
-#include <set>
+#include <functional> // hash
+#include <unordered_set>
 
 #include <build2/types>
 #include <build2/utility>
@@ -32,18 +33,50 @@ namespace build2
   };
 
   inline bool
-  operator< (const prerequisite_key& x, const prerequisite_key& y)
+  operator== (const prerequisite_key& x, const prerequisite_key& y)
   {
     assert (x.scope == y.scope);
 
     // Can compare project name pointers since they are from project_name_pool.
     //
-    return x.proj < y.proj || (x.proj == y.proj && x.tk < y.tk);
+    return x.proj == y.proj && x.tk == y.tk;
+  }
+
+  inline bool
+  operator!= (const prerequisite_key& x, const prerequisite_key& y)
+  {
+    return !(x == y);
   }
 
   ostream&
   operator<< (ostream&, const prerequisite_key&);
+}
 
+
+namespace std
+{
+  // Note that we ignore the extension when calculating the hash because of
+  // its special "unspecified" logic (see target_key::operator==).
+  //
+  template <>
+  struct hash<build2::prerequisite_key>
+  {
+    using argument_type = build2::prerequisite_key;
+    using result_type = size_t;
+
+    size_t
+    operator() (const build2::prerequisite_key& k) const noexcept
+    {
+      // Can hash project name pointers since they are from project_name_pool.
+      //
+      return build2::combine_hash (hash<const string*> () (k.proj),
+                                   hash<build2::target_key> () (k.tk));
+    }
+  };
+}
+
+namespace build2
+{
   class prerequisite
   {
   public:
@@ -100,9 +133,15 @@ namespace build2
   };
 
   inline bool
-  operator< (const prerequisite& x, const prerequisite& y)
+  operator== (const prerequisite& x, const prerequisite& y)
   {
-    return x.key () < y.key ();
+    return x.key () == y.key ();
+  }
+
+  inline bool
+  operator!= (const prerequisite& x, const prerequisite& y)
+  {
+    return !(x == y);
   }
 
   inline ostream&
@@ -111,9 +150,33 @@ namespace build2
     return os << p.key ();
   }
 
+}
+
+namespace std
+{
+  template <>
+  struct hash<build2::prerequisite>
+  {
+    using argument_type = build2::prerequisite;
+    using result_type = size_t;
+
+    size_t
+    operator() (const build2::prerequisite& p) const noexcept
+    {
+      return hash<build2::prerequisite_key> () (p.key ());
+    }
+  };
+}
+
+namespace build2
+{
   // Set of prerequisites in a scope.
   //
-  struct prerequisite_set: std::set<prerequisite>
+  // Similar to targets, specified and unspecified extensions are considered
+  // equal and we may update the extension in the existing entry. To make
+  // this work we use a hash set.
+  //
+  struct prerequisite_set: std::unordered_set<prerequisite>
   {
     pair<prerequisite&, bool>
     insert (const string* proj,
diff --git a/build2/prerequisite.cxx b/build2/prerequisite.cxx
index 4adfc92..d2f80cf 100644
--- a/build2/prerequisite.cxx
+++ b/build2/prerequisite.cxx
@@ -59,7 +59,8 @@ namespace build2
           tracer& trace) -> pair<prerequisite&, bool>
   {
     //@@ OPT: would be nice to somehow first check if this prerequisite is
-    //   already in the set before allocating a new instance.
+    //   already in the set before allocating a new instance. Something with
+    //   bounds and insert hints?
 
     // Find or insert.
     //
@@ -68,8 +69,6 @@ namespace build2
 
     // Update extension if the existing prerequisite has it unspecified.
     //
-    // @@ Changing the key!
-    //
     if (p.ext != ext)
     {
       l5 ([&]{
diff --git a/build2/target b/build2/target
index 9061e2d..ac67ff8 100644
--- a/build2/target
+++ b/build2/target
@@ -5,9 +5,9 @@
 #ifndef BUILD2_TARGET
 #define BUILD2_TARGET
 
-#include <map>
 #include <iterator>     // tags, etc.
 #include <type_traits>
+#include <unordered_map>
 
 #include <butl/multi-index> // map_iterator_adapter
 
@@ -779,13 +779,18 @@ namespace build2
       a, reverse_iterate (group_prerequisites (t)), members);
   }
 
-  //
+  // A target with an unspecified extension is considered equal to the one
+  // with the specified one. And when we find a target with an unspecified
+  // extension via a key with the specified one, we update the extension,
+  // essentially modifying the map's key. To make this work we use a hash
+  // map. The key's hash ignores the extension, so the hash will stay stable
+  // across extension updates.
   //
   struct target_set
   {
-    // @@ When we update ext in key, don't we change it? I think we do.
+    // @@ Why do we dynalloc target?
     //
-    typedef std::map<target_key, unique_ptr<target>> map;
+    typedef std::unordered_map<target_key, unique_ptr<target>> map;
     typedef butl::map_iterator_adapter<map::const_iterator> iterator;
 
     iterator
diff --git a/build2/target-key b/build2/target-key
index 2c0d0f2..c911a1f 100644
--- a/build2/target-key
+++ b/build2/target-key
@@ -6,6 +6,7 @@
 #define BUILD2_TARGET_KEY
 
 #include <map>
+#include <functional> // hash
 
 #include <butl/utility> // compare_c_string
 
@@ -25,30 +26,26 @@ namespace build2
     const dir_path* const dir; // Can be relative if part of prerequisite_key.
     const dir_path* const out; // Can be relative if part of prerequisite_key.
     const string* const  name;
-    const string* const& ext;
-
-    friend bool
-    operator< (const target_key& x, const target_key& y)
-    {
-      const target_type* xt (x.type);
-      const target_type* yt (y.type);
-
-      int t, n, d, o;
-
-      // Unspecified and specified extension are assumed equal. The
-      // extension strings are from the pool, so we can just compare
-      // pointers.
-      //
-      return
-        ((t = xt < yt ? -1 : xt > yt ? 1 : 0) < 0) ||
-        (t == 0 && (n = x.name->compare (*y.name)) < 0) ||
-        (t == 0 &&  n == 0 && (d = x.dir->compare (*y.dir)) < 0) ||
-        (t == 0 &&  n == 0 &&  d == 0 && (o = x.out->compare (*y.out)) < 0) ||
-        (t == 0 &&  n == 0 &&  d == 0 &&  o == 0 &&
-         x.ext != nullptr && y.ext != nullptr && *x.ext < *y.ext);
-    }
+    const string* const& ext; //@@ Iffy, whan happens when move/copy?
   };
 
+  inline bool
+  operator== (const target_key& x, const target_key& y)
+  {
+    // 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.dir == *y.dir &&
+      *x.out == *y.out &&
+      *x.name == *y.name &&
+      (x.ext == nullptr || y.ext == nullptr || x.ext == y.ext);
+  }
+
+  inline bool
+  operator!= (const target_key& x, const target_key& y) {return !(x == y);}
+
   // If the target type has a custom print function, call that. Otherwise,
   // call to_stream() with the current stream verbosity as a third argument.
   // Both are defined in target.cxx.
@@ -60,4 +57,27 @@ namespace build2
   to_stream (ostream&, const target_key&, uint16_t ext_verb);
 }
 
+namespace std
+{
+  // Note that we ignore the extension when calculating the hash because of
+  // its special "unspecified" logic (see operator== above).
+  //
+  template <>
+  struct hash<build2::target_key>
+  {
+    using argument_type = build2::target_key;
+    using result_type = size_t;
+
+    size_t
+    operator() (const build2::target_key& k) const noexcept
+    {
+      return build2::combine_hash (
+        hash<const build2::target_type*> () (k.type),
+        hash<build2::dir_path> () (*k.dir),
+        hash<build2::dir_path> () (*k.out),
+        hash<string> () (*k.name));
+    }
+  };
+}
+
 #endif // BUILD2_TARGET_KEY
diff --git a/build2/utility b/build2/utility
index e433b5a..e7674c0 100644
--- a/build2/utility
+++ b/build2/utility
@@ -11,7 +11,7 @@
 #include <cassert>  // assert()
 #include <iterator> // make_move_iterator()
 
-#include <butl/utility> // reverse_iterate()
+#include <butl/utility> // combine_hash(), reverse_iterate()
 
 #include <exception>     // uncaught_exception()
 #include <unordered_set>
@@ -31,6 +31,7 @@ namespace build2
 
   // <butl/utility>
   //
+  using butl::combine_hash;
   using butl::reverse_iterate;
 
   // Basic string utilities.