Use variable_cache for target type/pattern-specific prepend/append

9 files changed, 227 insertions, 134 deletions

diff --git a/build2/scope.cxx b/build2/scope.cxx
index d7e9d8e..4449747 100644
--- a/build2/scope.cxx
+++ b/build2/scope.cxx
@@ -44,52 +44,58 @@ namespace build2
       //
       lookup stem (s->find_original (var, tt, tn, gt, gn, 2).first);
 
-      // Implementing proper caching is tricky so for now we are going to re-
-      // calculate the value every time. This is the same issue and the same
-      // planned solution as for the override cache (see below).
+      // Check the cache.
       //
-      // Note: very similar logic as in the override cache population code
-      // below.
-      //
-      // @@ MT
-      //
-      variable_map::value_data& cache (
-        s->target_vars.cache[make_tuple (&v, tt, *tn)]);
+      pair<value&, ulock> entry (
+        s->target_vars.cache.insert (
+          make_tuple (&v, tt, *tn),
+          stem,
+          static_cast<const variable_map::value_data&> (v).version));
 
-      // Un-typify the cache. This can be necessary, for example, if we are
-      // changing from one value-typed stem to another.
+      value& cv (entry.first);
+
+      // If cache miss/invalidation, update the value.
       //
-      if (!stem.defined () || cache.type != stem->type)
+      if (entry.second.owns_lock ())
       {
-        cache = nullptr;
-        cache.type = nullptr; // Un-typify.
-      }
+        // Un-typify the cache. This can be necessary, for example, if we are
+        // changing from one value-typed stem to another.
+        //
+        // Note: very similar logic as in the override cache population code
+        // below.
+        //
+        if (!stem.defined () || cv.type != stem->type)
+        {
+          cv = nullptr;
+          cv.type = nullptr; // Un-typify.
+        }
 
-      // Copy the stem.
-      //
-      if (stem.defined ())
-        cache = *stem;
+        // Copy the stem.
+        //
+        if (stem.defined ())
+          cv = *stem;
 
-      // Typify the cache value in case there is no stem (we still want to
-      // prepend/append things in type-aware way).
-      //
-      if (cache.type == nullptr && var.type != nullptr)
-        typify (cache, *var.type, &var);
+        // Typify the cache value in case there is no stem (we still want to
+        // prepend/append things in type-aware way).
+        //
+        if (cv.type == nullptr && var.type != nullptr)
+          typify (cv, *var.type, &var);
 
-      // Now prepend/append the value, unless it is NULL.
-      //
-      if (v)
-      {
-        if (v.extra == 1)
-          cache.prepend (names (cast<names> (v)), &var);
-        else
-          cache.append (names (cast<names> (v)), &var);
+        // Now prepend/append the value, unless it is NULL.
+        //
+        if (v)
+        {
+          if (v.extra == 1)
+            cv.prepend (names (cast<names> (v)), &var);
+          else
+            cv.append (names (cast<names> (v)), &var);
+        }
       }
 
       // Return cache as the resulting value but retain l.vars, so it looks as
       // if the value came from s->target_vars.
       //
-      l.value = &cache;
+      l.value = &cv;
     };
 
     for (const scope* s (this); s != nullptr; )
@@ -394,12 +400,14 @@ namespace build2
 
     // Check the cache.
     //
-    pair<value&, ulock> cache (
+    pair<value&, ulock> entry (
       inner_proj->override_cache.insert (
-        make_pair (&var, inner_vars), stem));
+        make_pair (&var, inner_vars),
+        stem,
+        0)); // Overrides are immutable.
 
-    value& cv (cache.first);
-    bool cl (cache.second.owns_lock ());
+    value& cv (entry.first);
+    bool cl (entry.second.owns_lock ());
 
     // If cache miss/invalidation, update the value.
     //
diff --git a/build2/variable b/build2/variable
index 35530ca..10f4ac9 100644
--- a/build2/variable
+++ b/build2/variable
@@ -1036,7 +1036,7 @@ namespace build2
       using value::value;
       using value::operator=;
 
-      size_t version = 0; // Incremented on each modification (override cache).
+      size_t version = 0; // Incremented on each modification (variable_cache).
       size_t generation;  // load_generation of this value (global state only).
     };
 
@@ -1167,6 +1167,57 @@ namespace build2
     map_type m_;
   };
 
+  // Value caching. Used for overrides as well as target type/pattern-specific
+  // append/prepend.
+  //
+  // In many places we assume that we can store a reference to the returned
+  // variable value (e.g., install::lookup_install()). As a result, in these
+  // cases where we calculate the value dynamically, we have to cache it
+  // (note, however, that if the value becomes stale, there is no guarantee
+  // the references remain valid).
+  //
+  // Note that since the cache can be modified on any lookup (including during
+  // the execute phase), it is protected by its own mutex shard (allocated in
+  // main()).
+  //
+  extern size_t variable_cache_mutex_shard_size;
+  extern unique_ptr<shared_mutex[]> variable_cache_mutex_shard;
+
+  template <typename K>
+  class variable_cache
+  {
+  public:
+    // If the returned unique lock is locked, then the value has been
+    // invalidated.
+    //
+    pair<value&, ulock>
+    insert (K, const lookup& stem, size_t version);
+
+  private:
+    struct entry_type
+    {
+      // Note: we use value_data instead of value since the result is often
+      // returned as lookup. We also maintain the version in case one cached
+      // value (e.g., override) is based on another (e.g., target
+      // type/pattern-specific prepend/append).
+      //
+      variable_map::value_data value;
+
+      size_t version = 0; // Version on which this value is based.
+
+      // Location of the stem as well as the version on which this cache
+      // value is based. Used to track the location and value of the stem
+      // for cache invalidation. NULL/0 means there is no stem.
+      //
+      const variable_map* stem_vars = nullptr;
+      size_t              stem_version = 0;
+    };
+
+    using map_type = std::map<K, entry_type>;
+
+    map_type m_;
+  };
+
   // Target type/pattern-specific variables.
   //
   class variable_pattern_map
@@ -1219,65 +1270,23 @@ namespace build2
     lookup
     find (const target_type&, const string& tname, const variable&) const;
 
-
+    // Prepend/append value cache.
     //
     // The key is the combination of the "original value identity" (as a
     // pointer to the value in one of the variable_pattern_map's) and the
     // "target identity" (as target type and target name). Note that while at
     // first it may seem like we don't need the target identity, we actually
-    // do since the stem may itself be target-type/pattern-specific.
-    //
-    // @@ MT
+    // do since the stem may itself be target-type/pattern-specific. See
+    // scope::find_original() for details.
     //
-    mutable std::map<tuple<const value*, const target_type*, string>,
-                     variable_map::value_data> cache;
+    mutable
+    variable_cache<tuple<const value*, const target_type*, string>>
+    cache;
 
   private:
     bool global_;
     map_type map_;
   };
-
-  // Value caching. Used for overrides as well as target type/pattern-specific
-  // append/prepend.
-  //
-  // In many places we assume that we can store a reference to the returned
-  // variable value (e.g., install::lookup_install()). As a result, in these
-  // cases where we calculate the value dynamically, we have to cache it
-  // (note, however, that if the value becomes stale, there is no guarantee
-  // the references remain valid).
-  //
-  template <typename K>
-  class variable_cache
-  {
-  public:
-    // If the returned unique lock is locked, then the value has been
-    // invalidated.
-    //
-    pair<value&, ulock>
-    insert (K, const lookup& stem);
-
-  private:
-    struct entry_type
-    {
-      build2::value value;
-
-      // Location of the stem as well as the version on which this cache
-      // value is based. Used to track the location and value of the stem
-      // for cache invalidation. NULL/0 means there is no stem.
-      //
-      const variable_map* stem_vars = nullptr;
-      size_t              stem_version = 0;
-    };
-
-    using map_type = std::map<K, entry_type>;
-
-    map_type m_;
-  };
-
-  // Allocated in main().
-  //
-  extern size_t variable_cache_mutex_shard_size;
-  extern unique_ptr<shared_mutex[]> variable_cache_mutex_shard;
 }
 
 #include <build2/variable.ixx>
diff --git a/build2/variable.txx b/build2/variable.txx
index 5b212f0..5a1b79c 100644
--- a/build2/variable.txx
+++ b/build2/variable.txx
@@ -557,13 +557,14 @@ namespace build2
   //
   template <typename K>
   pair<value&, ulock> variable_cache<K>::
-  insert (K k, const lookup& stem)
+  insert (K k, const lookup& stem, size_t ver)
   {
-    const variable_map* vars (stem.vars); // NULL if undefined.
-    size_t ver (
-      stem.defined ()
-      ? static_cast<const variable_map::value_data*> (stem.value)->version
-      : 0);
+    using value_data = variable_map::value_data;
+
+    const variable_map* svars (stem.vars); // NULL if undefined.
+    size_t sver (stem.defined ()
+                 ? static_cast<const value_data*> (stem.value)->version
+                 : 0);
 
     shared_mutex& m (
       variable_cache_mutex_shard[
@@ -576,9 +577,10 @@ namespace build2
 
     // Cache hit.
     //
-    if (i != m_.end ()              &&
-        i->second.stem_vars == vars &&
-        i->second.stem_version == ver)
+    if (i != m_.end ()               &&
+        i->second.version == ver     &&
+        i->second.stem_vars == svars &&
+        i->second.stem_version == sver)
       return pair<value&, ulock> (i->second.value, move (ul));
 
     // Relock for exclusive access. Note that it is entirely possible
@@ -593,30 +595,38 @@ namespace build2
     pair<typename map_type::iterator, bool> p (i, i == m_.end ());
 
     if (p.second)
-      p = m_.emplace (move (k), entry_type {value (nullptr), vars, ver});
+      p = m_.emplace (move (k),
+                      entry_type {value_data (nullptr), ver, svars, sver});
 
     entry_type& e (p.first->second);
 
-    // Cache miss.
-    //
     if (p.second)
-      ;
-    //
-    // Cache invalidation.
-    //
-    else if (e.stem_vars != vars || e.stem_version != ver)
     {
-      if (e.stem_vars != vars)
-        e.stem_vars = vars;
+      // Cache miss.
+      //
+      e.value.version++; // New value.
+    }
+    else if (e.version != ver     ||
+             e.stem_vars != svars ||
+             e.stem_version != sver)
+    {
+      // Cache invalidation.
+      //
+      assert (e.version <= ver);
+      e.version = ver;
+
+      if (e.stem_vars != svars)
+        e.stem_vars = svars;
       else
-        assert (e.stem_version <= ver);
+        assert (e.stem_version <= sver);
+
+      e.stem_version = sver;
 
-      e.stem_version = ver;
+      e.value.version++; // Value changed.
     }
-    //
-    // Cache hit.
-    //
     else
+      // Cache hit.
+      //
       ul.unlock ();
 
     return pair<value&, ulock> (e.value, move (ul));
diff --git a/old-tests/variable/override/cache b/old-tests/variable/override/cache
deleted file mode 100644
index 8378688..0000000
--- a/old-tests/variable/override/cache
+++ /dev/null
@@ -1,13 +0,0 @@
-x = [string] 0
-print $x
-
-x = [uint64] 1
-print $x
-
-y = 0
-print $y
-
-[uint64] y = [null]
-print $y
-
-./:
diff --git a/old-tests/variable/override/test.sh b/old-tests/variable/override/test.sh
index a8b08b2..710cf28 100755
--- a/old-tests/variable/override/test.sh
+++ b/old-tests/variable/override/test.sh
@@ -301,12 +301,3 @@ p     : PxsS
 p/d   : PxssS
 p/d/t : PxsssS
 EOF
-
-# Cache overwrite.
-#
-test --buildfile cache x+=01 y+=01 <<EOF
-001
-2
-0 01
-1
-EOF
diff --git a/tests/buildfile b/tests/buildfile
index 0384c45..4b5f149 100644
--- a/tests/buildfile
+++ b/tests/buildfile
@@ -3,5 +3,5 @@
 # license   : MIT; see accompanying LICENSE file
 
 ./: directive/ eval/ expansion/ function/ search/ test/ value/ \
-file{common.test}
+variable/ file{common.test}
 
diff --git a/tests/variable/buildfile b/tests/variable/buildfile
new file mode 100644
index 0000000..65a0791
--- /dev/null
+++ b/tests/variable/buildfile
@@ -0,0 +1,5 @@
+# file      : tests/variable/buildfile
+# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+./: override/
diff --git a/tests/variable/override/buildfile b/tests/variable/override/buildfile
new file mode 100644
index 0000000..5831ecd
--- /dev/null
+++ b/tests/variable/override/buildfile
@@ -0,0 +1,5 @@
+# file      : tests/variable/override/buildfile
+# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+./: test{testscript} $b
diff --git a/tests/variable/override/testscript b/tests/variable/override/testscript
new file mode 100644
index 0000000..9b8efdf
--- /dev/null
+++ b/tests/variable/override/testscript
@@ -0,0 +1,78 @@
+# file      : tests/variable/override/testscript
+# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+.include ../../common.test
+
+: cache-invalidation
+:
+{
+  : value-version
+  :
+  $* x+=01 y+=01 <<EOI >>EOO
+  x = [string] 0
+  print $x
+
+  x = [uint64] 1
+  print $x
+
+  y = 0
+  print $y
+
+  [uint64] y = [null]
+  print $y
+  EOI
+  001
+  2
+  0 01
+  1
+  EOO
+
+  : value-position
+  :
+  $* x+=01 <<EOI >>EOO
+  x = [string] 0
+
+  print $x
+  dir/:
+  {
+    print $x
+  }
+
+  dir/: x = [uint64] 1
+
+  print $x
+  dir/:
+  {
+    print $x
+  }
+
+  EOI
+  001
+  001
+  001
+  2
+  EOO
+}
+
+: override-cached
+: Test overriding cached target type/pattern-specific prepend/append
+:
+{
+  $* x+=X <<EOI >>EOO
+  x = 0
+  file{*}: x += a
+
+  print $(file{foo}:x)
+
+  x = 1                 # Should invalidate both caches.
+  print $(file{foo}:x)
+
+  file{*}: x += b       # Should invalidate both caches.
+  print $(file{foo}:x)
+  EOI
+  0 a X
+  1 a X
+  1 a b X
+  EOO
+}