Add support for prepend/append in target type/pattern-specific vars

Semantically, these are similar to variable overrides and are essentially
treated as "templates" that are applied on lookup to the "stem" value that is
specific to the target type/name. For example:

x = [string] a
file{f*}: x =+ b

sub/:
{
  file{*}: x += c

  print $(file{foo}:x)  # abc
  print $(file{bar}:x)  # ac
}

13 files changed, 371 insertions, 89 deletions

diff --git a/build2/dump.cxx b/build2/dump.cxx
index 9310405..08700fc 100644
--- a/build2/dump.cxx
+++ b/build2/dump.cxx
@@ -53,35 +53,51 @@ namespace build2
     }
   }
 
+  enum class variable_kind {scope, tt_pat, target};
+
   static void
   dump_variable (ostream& os,
                  const variable& var,
                  const lookup& org,
                  const scope& s,
-                 bool target)
+                 variable_kind k)
   {
-    if (var.type != nullptr)
-      os << '[' << var.type->name << "] ";
-
-    os << var.name << " = ";
-
-    // If this variable is overriden, print both the override and the
-    // original values.
+    // Target type/pattern-specific prepends/appends are kept untyped and not
+    // overriden.
     //
-    if (var.override != nullptr &&
-        var.name.rfind (".__override") == string::npos &&
-        var.name.rfind (".__suffix") == string::npos &&
-        var.name.rfind (".__prefix") == string::npos)
+    if (k == variable_kind::tt_pat && org->extra != 0)
     {
-      // The original is always from this scope/target, so depth is 1.
+      // @@ Might be useful to dump the cache.
       //
-      lookup l (s.find_override (var, make_pair (org, 1), target).first);
-      assert (l.defined ()); // We at least have  the original.
+      os << var.name << (org->extra == 1 ? " =+ " : " += ");
+    }
+    else
+    {
+      if (var.type != nullptr)
+        os << '[' << var.type->name << "] ";
 
-      if (org != l)
+      os << var.name << " = ";
+
+      // If this variable is overriden, print both the override and the
+      // original values.
+      //
+      if (var.override != nullptr &&
+          var.name.rfind (".__override") == string::npos &&
+          var.name.rfind (".__suffix") == string::npos &&
+          var.name.rfind (".__prefix") == string::npos)
       {
-        dump_value (os, *l, l->type != var.type);
-        os << " # original: ";
+        // The original is always from this scope/target, so depth is 1.
+        //
+        lookup l (
+          s.find_override (
+            var, make_pair (org, 1), k == variable_kind::target).first);
+        assert (l.defined ()); // We at least have the original.
+
+        if (org != l)
+        {
+          dump_value (os, *l, l->type != var.type);
+          os << " # original: ";
+        }
       }
     }
 
@@ -93,17 +109,19 @@ namespace build2
                   string& ind,
                   const variable_map& vars,
                   const scope& s,
-                  bool target)
+                  variable_kind k)
   {
     for (const auto& e: vars)
     {
       os << endl
          << ind;
 
-      dump_variable (os, e.first, lookup (&e.second, &vars), s, target);
+      dump_variable (os, e.first, lookup (&e.second, &vars), s, k);
     }
   }
 
+  // Dump target type/pattern-specific variables.
+  //
   static void
   dump_variables (ostream& os,
                   string& ind,
@@ -140,14 +158,14 @@ namespace build2
                          vars.begin ()->first,
                          lookup (&vars.begin ()->second, &vars),
                          s,
-                         false);
+                         variable_kind::tt_pat);
         }
         else
         {
           os << endl
              << ind << '{';
           ind += "  ";
-          dump_variables (os, ind, vars, s, false);
+          dump_variables (os, ind, vars, s, variable_kind::tt_pat);
           ind.resize (ind.size () - 2);
           os << endl
              << ind << '}';
@@ -216,7 +234,7 @@ namespace build2
       os << endl
          << ind << '{';
       ind += "  ";
-      dump_variables (os, ind, t.vars, s, true);
+      dump_variables (os, ind, t.vars, s, variable_kind::target);
       ind.resize (ind.size () - 2);
       os << endl
          << ind << '}';
@@ -262,7 +280,7 @@ namespace build2
       if (vb)
         os << endl;
 
-      dump_variables (os, ind, p.vars, p, false);
+      dump_variables (os, ind, p.vars, p, variable_kind::scope);
       vb = true;
     }
 
diff --git a/build2/parser.cxx b/build2/parser.cxx
index b85349b..e463f50 100644
--- a/build2/parser.cxx
+++ b/build2/parser.cxx
@@ -483,20 +483,89 @@ namespace build2
                   if (ti == nullptr)
                     fail (nloc) << "unknown target type " << n.type;
 
-                  if (att == type::prepend)
-                    fail (at) << "prepend to target type/pattern-specific "
-                              << "variable " << var.name;
-
-                  if (att == type::append)
-                    fail (at) << "append to target type/pattern-specific "
-                              << "variable " << var.name;
-
                   // Note: expanding the value in the context of the scope.
                   //
                   value rhs (variable_value (t, tt));
-                  value& lhs (
-                    scope_->target_vars[*ti][move (n.value)].assign (var));
-                  value_attributes (&var, lhs, move (rhs), type::assign);
+
+                  // Leave the value untyped unless we are assigning.
+                  //
+                  pair<reference_wrapper<value>, bool> p (
+                    scope_->target_vars[*ti][move (n.value)].insert (
+                      var, att == type::assign));
+
+                  value& lhs (p.first);
+
+                  // We store prepend/append values untyped (similar to
+                  // overrides).
+                  //
+                  if (p.second)
+                  {
+                    // Note: we are always using assign and we don't pass the
+                    // variable in case of prepend/append in order to keep the
+                    // value untyped.
+                    //
+                    value_attributes (att == type::assign ? &var : nullptr,
+                                      lhs,
+                                      move (rhs),
+                                      type::assign);
+
+                    // Map assignment type to value::extra constant.
+                    //
+                    lhs.extra =
+                      att == type::prepend ? 1 :
+                      att == type::append  ? 2 :
+                      0;
+                  }
+                  else
+                  {
+                    // Existing value. What happens next depends what we are
+                    // trying to do and what's already there.
+                    //
+                    // Assignment is the easy one: we simply overwrite what's
+                    // already there. Also, if we are appending/prepending to
+                    // a previously assigned value, then we simply append or
+                    // prepend normally.
+                    //
+                    if (att == type::assign || lhs.extra == 0)
+                    {
+                      // Above we instructed insert() not to type the value so
+                      // we have to compensate for that now.
+                      //
+                      if (att != type::assign)
+                      {
+                        if (var.type != nullptr && lhs.type != var.type)
+                          typify (lhs, *var.type, &var);
+                      }
+                      else
+                        lhs.extra = 0; // Change to assignment.
+
+                      value_attributes (&var, lhs, move (rhs), att);
+                    }
+                    else
+                    {
+                      // This is an append/prepent to a previously appended or
+                      // prepended value. We can handle it as long as things
+                      // are consistent.
+                      //
+                      if (att == type::prepend && lhs.extra == 2)
+                        fail (at) << "prepend to a previously appended target "
+                                  << "type/pattern-specific variable "
+                                  << var.name;
+
+                      if (att == type::append && lhs.extra == 1)
+                        fail (at) << "append to a previously prepended target "
+                                  << "type/pattern-specific variable "
+                                  << var.name;
+
+                      // Do untyped prepend/append.
+                      //
+                      value_attributes (nullptr, lhs, move (rhs), att);
+                    }
+                  }
+
+                  if (lhs.extra != 0 && lhs.type != nullptr)
+                    fail (at) << "typed prepend/append to target type/pattern-"
+                              << "specific variable " << var.name;
                 }
               }
 
@@ -1479,7 +1548,10 @@ namespace build2
     }
 
     if (null)
-      v = nullptr;
+    {
+      if (kind == token_type::assign) // Ignore for prepend/append.
+        v = nullptr;
+    }
     else
     {
       if (kind == token_type::assign)
diff --git a/build2/scope b/build2/scope
index b7c9aef..70eb73d 100644
--- a/build2/scope
+++ b/build2/scope
@@ -134,13 +134,15 @@ namespace build2
       return var.override == nullptr ? p : find_override (var, move (p));
     }
 
-    // Implementation details (used by scope target lookup).
+    // Implementation details (used by scope target lookup). The start_depth
+    // can be used to skip a number of initial lookups.
     //
     pair<lookup, size_t>
     find_original (
       const variable&,
       const target_type* tt = nullptr, const string* tn = nullptr,
-      const target_type* gt = nullptr, const string* gn = nullptr) const;
+      const target_type* gt = nullptr, const string* gn = nullptr,
+      size_t start_depth = 1) const;
 
     pair<lookup, size_t>
     find_override (const variable&,
diff --git a/build2/scope.cxx b/build2/scope.cxx
index 0ef8de6..885a8d2 100644
--- a/build2/scope.cxx
+++ b/build2/scope.cxx
@@ -15,38 +15,127 @@ namespace build2
   pair<lookup, size_t> scope::
   find_original (const variable& var,
                  const target_type* tt, const string* tn,
-                 const target_type* gt, const string* gn) const
+                 const target_type* gt, const string* gn,
+                 size_t start_d) const
   {
     size_t d (0);
 
+    // Process target type/pattern-specific prepend/append values.
+    //
+    auto pre_app = [&var] (lookup& l,
+                           const scope* s,
+                           const target_type* tt, const string* tn,
+                           const target_type* gt, const string* gn)
+    {
+      const value& v (*l);
+      assert ((v.extra == 1 || v.extra == 2) && v.type == nullptr);
+
+      // First we need to look for the stem value starting from the "next
+      // lookup point". That is, if we have the group, then from the
+      // s->target_vars (for the group), otherwise from s->vars, and then
+      // continuing looking in the outer scopes (for both target and group).
+      // Note that this may have to be repeated recursively, i.e., we may have
+      // prepents/appends in outer scopes. Also, if the value is for the
+      // group, then we shouldn't be looking for stem in the target's
+      // variables. In other words, once we "jump" to group, we stay there.
+      //
+      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).
+      //
+      // Note: very similar logic as in the override cache population code
+      // below.
+      //
+      // @@ MT
+      //
+      value& cache (s->target_vars.cache[make_tuple (&v, tt, *tn)]);
+
+      // Un-typify the cache. This can be necessary, for example, if we are
+      // changing from one value-typed stem to another.
+      //
+      if (!stem.defined () || cache.type != stem->type)
+      {
+        cache = nullptr;
+        cache.type = nullptr; // Un-typify.
+      }
+
+      // Copy the stem.
+      //
+      if (stem.defined ())
+        cache = *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);
+
+      // 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);
+      }
+
+      // 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;
+    };
+
     for (const scope* s (this); s != nullptr; )
     {
       if (tt != nullptr) // This started from the target.
       {
         bool f (!s->target_vars.empty ());
 
-        ++d;
-        if (f)
+        // Target.
+        //
+        if (++d >= start_d)
         {
-          lookup l (s->target_vars.find (*tt, *tn, var));
+          if (f)
+          {
+            lookup l (s->target_vars.find (*tt, *tn, var));
+
+            if (l.defined ())
+            {
+              if (l->extra != 0) // Prepend/append?
+                pre_app (l, s, tt, tn, gt, gn);
 
-          if (l.defined ())
-            return make_pair (move (l), d);
+              return make_pair (move (l), d);
+            }
+          }
         }
 
-        ++d;
-        if (f && gt != nullptr)
+        // Group.
+        //
+        if (++d >= start_d)
         {
-          lookup l (s->target_vars.find (*gt, *gn, var));
+          if (f && gt != nullptr)
+          {
+            lookup l (s->target_vars.find (*gt, *gn, var));
+
+            if (l.defined ())
+            {
+              if (l->extra != 0) // Prepend/append?
+                pre_app (l, s, gt, gn, nullptr, nullptr);
 
-          if (l.defined ())
-            return make_pair (move (l), d);
+              return make_pair (move (l), d);
+            }
+          }
         }
       }
 
-      ++d;
-      if (const value* v = s->vars.find (var))
-        return make_pair (lookup (v, &s->vars), d);
+      if (++d >= start_d)
+      {
+        if (const value* v = s->vars.find (var))
+          return make_pair (lookup (v, &s->vars), d);
+      }
 
       switch (var.visibility)
       {
@@ -302,6 +391,9 @@ namespace build2
     // If there is a stem, set it as the initial value of the cache.
     // Otherwise, start with a NULL value.
     //
+    // Note: very similar logic as in the target type/pattern specific cache
+    // population code above.
+    //
 
     // Un-typify the cache. This can be necessary, for example, if we are
     // changing from one value-typed stem to another.
diff --git a/build2/types b/build2/types
index 6fdea4e..fcfdcef 100644
--- a/build2/types
+++ b/build2/types
@@ -5,6 +5,7 @@
 #ifndef BUILD2_TYPES
 #define BUILD2_TYPES
 
+#include <tuple>
 #include <vector>
 #include <string>
 #include <memory>           // unique_ptr, shared_ptr
@@ -42,6 +43,7 @@ namespace build2
   using std::nullptr_t;
 
   using std::pair;
+  using std::tuple;
   using std::string;
   using std::function;
   using std::reference_wrapper;
diff --git a/build2/utility b/build2/utility
index a5c4407..29dca77 100644
--- a/build2/utility
+++ b/build2/utility
@@ -5,6 +5,7 @@
 #ifndef BUILD2_UTILITY
 #define BUILD2_UTILITY
 
+#include <tuple>    // make_tuple()
 #include <memory>   // make_shared()
 #include <string>   // to_string()
 #include <utility>  // move(), forward(), declval(), make_pair()
@@ -25,6 +26,7 @@ namespace build2
   using std::declval;
 
   using std::make_pair;
+  using std::make_tuple;
   using std::make_shared;
   using std::make_move_iterator;
   using std::to_string;
diff --git a/build2/variable b/build2/variable
index 5b9189c..cc99dc6 100644
--- a/build2/variable
+++ b/build2/variable
@@ -712,11 +712,13 @@ namespace build2
       return operator[] (var_pool.find (name));
     }
 
+    // If typed is false, leave the value untyped even if the variable is.
+    //
     const value*
-    find (const variable&) const;
+    find (const variable&, bool typed = true) const;
 
     value*
-    find (const variable&);
+    find (const variable&, bool typed = true);
 
     // Return a value suitable for assignment. See scope for details.
     //
@@ -737,15 +739,16 @@ namespace build2
     }
 
     // As above but also return an indication of whether the new value (which
-    // will be NULL) was actually inserted.
+    // will be NULL) was actually inserted. Similar to find(), if typed is
+    // false, leave the value untyped even if the variable is.
     //
     pair<reference_wrapper<value>, bool>
-    insert (const variable&);
+    insert (const variable&, bool typed = true);
 
     pair<reference_wrapper<value>, bool>
-    insert (const string& name)
+    insert (const string& name, bool typed = true)
     {
-      return insert (var_pool.find (name));
+      return insert (var_pool.find (name), typed);
     }
 
     pair<const_iterator, const_iterator>
@@ -773,11 +776,6 @@ namespace build2
 
   // Target type/pattern-specific variables.
   //
-  // @@ In quite a few places we assume that we can store a reference
-  //    to the returned value (e.g., install::lookup_install()). If
-  //    we "instantiate" the value on the fly, then we will need to
-  //    consider its lifetime.
-  //
   using variable_pattern_map = std::map<string, variable_map>;
   using variable_type_map_base = std::map<reference_wrapper<const target_type>,
                                           variable_pattern_map>;
@@ -786,6 +784,19 @@ namespace build2
   {
     lookup
     find (const target_type&, const string& tname, const variable&) const;
+
+    // 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 case
+    // of append/prepent where we calculate the value dynamically, we have to
+    // cache it.
+    //
+    // The key is the combination of the "original value idenity" (as a
+    // pointer to the value in variable_pattern_map) and the "target identity"
+    // (as target type and target name). The target name, unfortunately, has
+    // to be stored by value (maybe will pool them at some point).
+    //
+    mutable
+    std::map<tuple<const value*, const target_type*, string>, value> cache;
   };
 
   // Override cache.
diff --git a/build2/variable.cxx b/build2/variable.cxx
index 67efc95..58076d4 100644
--- a/build2/variable.cxx
+++ b/build2/variable.cxx
@@ -680,42 +680,42 @@ namespace build2
   // variable_map
   //
   const value* variable_map::
-  find (const variable& var) const
+  find (const variable& var, bool typed) const
   {
     auto i (m_.find (var));
     const value* r (i != m_.end () ? &i->second : nullptr);
 
     // First access after being assigned a type?
     //
-    if (r != nullptr && var.type != nullptr && r->type != var.type)
+    if (r != nullptr && typed && var.type != nullptr && r->type != var.type)
       typify (const_cast<value&> (*r), *var.type, &var);
 
     return  r;
   }
 
   value* variable_map::
-  find (const variable& var)
+  find (const variable& var, bool typed)
   {
     auto i (m_.find (var));
     value* r (i != m_.end () ? &i->second : nullptr);
 
     // First access after being assigned a type?
     //
-    if (r != nullptr && var.type != nullptr && r->type != var.type)
+    if (r != nullptr && typed && var.type != nullptr && r->type != var.type)
       typify (*r, *var.type, &var);
 
     return  r;
   }
 
   pair<reference_wrapper<value>, bool> variable_map::
-  insert (const variable& var)
+  insert (const variable& var, bool typed)
   {
-    auto r (m_.emplace (var, value (var.type)));
+    auto r (m_.emplace (var, value (typed ? var.type : nullptr)));
     value& v (r.first->second);
 
     // First access after being assigned a type?
     //
-    if (!r.second && var.type != nullptr && v.type != var.type)
+    if (typed && !r.second && var.type != nullptr && v.type != var.type)
       typify (v, *var.type, &var);
 
     return make_pair (reference_wrapper<value> (v), r.second);
@@ -772,13 +772,20 @@ namespace build2
             name.compare (nn - pn, pn, p, w, pn) != 0)
           continue;
 
+        //@@ TODO: should we detect ambiguity? 'foo-*' '*-foo' and 'foo-foo'?
+        //   Right now the last defined will be used.
+
         // Ok, this pattern matches. But is there a variable?
         //
-        if (const value* v = j->second.find (var))
+        // Since we store append/prepend values untyped, instruct find() not
+        // to automatically type it. And if it is assignment, then typify it
+        // ourselves.
+        //
+        if (const value* v = j->second.find (var, false))
         {
-          //@@ TODO: should we detect ambiguity? 'foo-*' '*-foo' and
-          //   'foo-foo'? Right now the last defined will be used.
-          //
+          if (v->extra == 0 && var.type != nullptr && v->type != var.type)
+            typify (const_cast<value&> (*v), *var.type, &var);
+
           return lookup (v, &j->second);
         }
       }
diff --git a/build2/variable.txx b/build2/variable.txx
index a3511d4..a86a936 100644
--- a/build2/variable.txx
+++ b/build2/variable.txx
@@ -54,13 +54,15 @@ namespace build2
       catch (const invalid_argument&) {} // Fall through.
     }
 
-    diag_record dr (error);
+    {
+      diag_record dr (error);
 
-    dr << "invalid " << value_traits<T>::value_type.name
-       << " value '" << ns << "'";
+      dr << "invalid " << value_traits<T>::value_type.name
+         << " value '" << ns << "'";
 
-    if (var != nullptr)
-      dr << " in variable " << var->name;
+      if (var != nullptr)
+        dr << " in variable " << var->name;
+    }
 
     throw failed ();
   }
@@ -84,13 +86,15 @@ namespace build2
       catch (const invalid_argument&) {} // Fall through.
     }
 
-    diag_record dr (error);
+    {
+      diag_record dr (error);
 
-    dr << "invalid " << value_traits<T>::value_type.name
-       << " value '" << ns << "'";
+      dr << "invalid " << value_traits<T>::value_type.name
+         << " value '" << ns << "'";
 
-    if (var != nullptr)
-      dr << " in variable " << var->name;
+      if (var != nullptr)
+        dr << " in variable " << var->name;
+    }
 
     throw failed ();
   }
@@ -114,13 +118,15 @@ namespace build2
       catch (const invalid_argument&) {} // Fall through.
     }
 
-    diag_record dr (error);
+    {
+      diag_record dr (error);
 
-    dr << "invalid " << value_traits<T>::value_type.name
-       << " value '" << ns << "'";
+      dr << "invalid " << value_traits<T>::value_type.name
+         << " value '" << ns << "'";
 
-    if (var != nullptr)
-      dr << " in variable " << var->name;
+      if (var != nullptr)
+        dr << " in variable " << var->name;
+    }
 
     throw failed ();
   }
diff --git a/tests/test.sh b/tests/test.sh
index ce115d5..b26dd3b 100755
--- a/tests/test.sh
+++ b/tests/test.sh
@@ -28,3 +28,4 @@ test "variable/override"
 test "variable/prepend"
 test "variable/qualified"
 test "variable/type"
+test "variable/type-pattern-append"
diff --git a/tests/variable/type-pattern-append/buildfile b/tests/variable/type-pattern-append/buildfile
new file mode 100644
index 0000000..a91b340
--- /dev/null
+++ b/tests/variable/type-pattern-append/buildfile
@@ -0,0 +1,59 @@
+# Typed append/prepend.
+#
+#dir{a*}: x += [bool] true
+#dir{p*}: x =+ [bool] true
+
+[string] typed = [null]
+dir{a*}: typed += abc    # ok
+dir{p*}: typed =+ abc    # ok
+
+# Prepend/append before/after assignment.
+#
+[string] x1 = [null]
+dir{*}: x1 += A
+dir{*}: x1 = b
+dir{*}: x1 += c
+dir{*}: x1 =+ a
+print $(dir{./}:x1)
+
+# Without stem, mixed prepend/append.
+#
+dir{*}: x2 += b
+dir{*}: x2 += c
+#dir{*}: x2 =+ a     # error
+print $(dir{./}:x2)
+
+dir{*}: x3 =+ b
+dir{*}: x3 =+ a
+#dir{*}: x3 += c     # error
+print $(dir{./}:x3)
+
+# With stem, typing.
+#
+x4 = a
+dir{*}: x4 += b
+dir{*}: x4 += c
+print $(dir{./}:x4)
+
+[string] x5 = b
+dir{*}: x5 =+ a
+x = $(dir{./}:x5)
+print $(dir{./}:x5)
+
+x6 = [string] a
+sub/:
+{
+  dir{*}: x6 += b
+  dir{*}: x6 += [null]
+  print $(dir{./}:x6)
+}
+
+x7 = [string] b
+dir{*}: x7 =+ a
+sub/:
+{
+  dir{*}: x7 += c
+  print $(dir{./}:x7)
+}
+
+./:
diff --git a/tests/variable/type-pattern-append/test.out b/tests/variable/type-pattern-append/test.out
new file mode 100644
index 0000000..e8e2242
--- /dev/null
+++ b/tests/variable/type-pattern-append/test.out
@@ -0,0 +1,7 @@
+abc
+b c
+a b
+a b c
+ab
+ab
+abc
diff --git a/tests/variable/type-pattern-append/test.sh b/tests/variable/type-pattern-append/test.sh
new file mode 100755
index 0000000..c745b76
--- /dev/null
+++ b/tests/variable/type-pattern-append/test.sh
@@ -0,0 +1,3 @@
+#!/bin/sh
+
+b -q | diff --strip-trailing-cr -u test.out -