Add string_map buildfile value type

This exposes the std::map<std::string,std::string> type to buildfiles.

New functions:

  $size(<string-map>)
  $keys(<string-map>)

Subscript can be used to lookup a value by key. The result is [null] if
there is no value associated with the specified key. For example:

map = [string_map] a@1 b@2 c@3

b = ($map[b])  # 2

if ($map[z] == [null])
  ...

Note that append (+=) is overriding (like std::map::insert_or_assign())
while prepend (=+) is not (like std::map::insert()). In a sense, whatever
appears last (from left to right) is kept, which is consistent with what
we expect to happen when specifying the same key repeatedly in a literal
representation. For example:

map = [string_map] a@0 b@2 a@1  # a@1 b@2
map += b@0 c@3                  # a@1 b@0 c@3
map =+ b@1 d@4                  # a@1 b@0 c@3 d@4

Example of iteration:

map = [string_map] a@1 b@2 c@3
for p: $map
{
  k = $first($p)
  v = $second($p)
}

While the subscript is mapped to key lookup only, index-based access can be
implemented (with a bit of overhead) using the $keys() function:

map = [string_map] a@1 b@2 c@3
keys = $keys($m)
for i: $integer_sequence(0, $size($keys))
{
  k = ($keys[$i])
  v = ($map[$k])
}

Also, this commit changes the naming of other template-based value types (not
exposed as buildfile value types) to use C++ template id-like names (e.g.,
map<string,optional<bool>>).

8 files changed, 238 insertions, 48 deletions

diff --git a/libbuild2/functions-string.cxx b/libbuild2/functions-string.cxx
index 8e5a315..b332efa 100644
--- a/libbuild2/functions-string.cxx
+++ b/libbuild2/functions-string.cxx
@@ -119,14 +119,16 @@ namespace build2
     };
 
     // $size(<strings>)
+    // $size(<string-map>)
     // $size(<string>)
     //
-    // First form: return the number of elements in the sequence.
+    // First two forms: return the number of elements in the sequence.
     //
-    // Second form: return the number of characters (bytes) in the string.
+    // Third form: return the number of characters (bytes) in the string.
     //
-    f["size"] += [] (strings v) {return v.size ();};
-    f["size"] += [] (string v) {return v.size ();};
+    f["size"] += [] (strings v)             {return v.size ();};
+    f["size"] += [] (map<string, string> v) {return v.size ();};
+    f["size"] += [] (string v)              {return v.size ();};
 
     // $sort(<strings> [, <flags>])
     //
@@ -204,6 +206,21 @@ namespace build2
       return find_index (vs, move (v), move (fs));
     };
 
+    // $keys(<string-map>)
+    //
+    // Return the list of keys in a string map.
+    //
+    // Note that the result is sorted in ascending order.
+    //
+    f["keys"] += [](map<string, string> v)
+    {
+      strings r;
+      r.reserve (v.size ());
+      for (pair<const string, string>& p: v)
+        r.push_back (p.first); // @@ PERF: use C++17 map::extract() to steal.
+      return r;
+    };
+
     // String-specific overloads from builtins.
     //
     function_family b (m, "builtin");
diff --git a/libbuild2/parser.cxx b/libbuild2/parser.cxx
index 6ccae8a..b68f009 100644
--- a/libbuild2/parser.cxx
+++ b/libbuild2/parser.cxx
@@ -6090,7 +6090,8 @@ namespace build2
           if (n[4] == 's' &&
               n[5] == '\0') return &value_traits<paths>::value_type;
         }
-        else if (n == "project_name") return &value_traits<project_name>::value_type;
+        else if (n == "project_name")
+          return &value_traits<project_name>::value_type;
         break;
       }
     case 's':
@@ -6100,12 +6101,15 @@ namespace build2
           if (n[6] == '\0') return &value_traits<string>::value_type;
           if (n[6] == 's' &&
               n[7] == '\0') return &value_traits<strings>::value_type;
+          if (n == "string_map")
+            return &value_traits<map<string,string>>::value_type;
         }
         break;
       }
     case 't':
       {
-        if (n == "target_triplet") return &value_traits<target_triplet>::value_type;
+        if (n == "target_triplet")
+          return &value_traits<target_triplet>::value_type;
         break;
       }
     case 'u':
@@ -8972,7 +8976,7 @@ namespace build2
               result = &result_data;
             }
 
-            // See if we have another subscript.
+            // See if we have chained subscript.
             //
             enable_subscript ();
             tt = peek ();
diff --git a/libbuild2/variable.cxx b/libbuild2/variable.cxx
index 6cdf3ee..40eeccd 100644
--- a/libbuild2/variable.cxx
+++ b/libbuild2/variable.cxx
@@ -1994,7 +1994,7 @@ namespace build2
     {
       // Seeing that we are reversing for consumption, it feels natural to
       // reverse JSON null to our [null] rather than empty. This, in
-      // particular, helps nested subscript.
+      // particular, helps chained subscript.
       //
 #if 0
     case json_type::null:               r = value (names {});          break;
@@ -2085,7 +2085,7 @@ namespace build2
              ? json_subscript_impl (val, val_data, i, n, index).first
              : value ());
 
-    // Typify null values so that we get called for nested subscripts.
+    // Typify null values so that we get called for chained subscripts.
     //
     if (r.null)
       r.type = &value_traits<json_value>::value_type;
diff --git a/libbuild2/variable.hxx b/libbuild2/variable.hxx
index 6b0b30e..d67098e 100644
--- a/libbuild2/variable.hxx
+++ b/libbuild2/variable.hxx
@@ -111,11 +111,11 @@ namespace build2
     //
     // Note: should normally be consistent with iterate.
     //
-    value (*const subscript) (const value& val,
-                              value* val_data,
-                              value&& subscript,
-                              const location& sloc,
-                              const location& bloc);
+    value (*/*const*/ subscript) (const value& val,
+                                  value* val_data,
+                                  value&& subscript,
+                                  const location& sloc,
+                                  const location& bloc);
 
     // Custom iteration function. It should invoked the specified function for
     // each element in order. If NULL, then the generic implementation is
@@ -1181,8 +1181,11 @@ namespace build2
   //
   // Either K or V can be optional<T> making the key or value optional.
   //
-  // Note that append/+= is non-overriding (like insert()) while prepend/=+
-  // is (like insert_or_assign()).
+  // Note that append/+= is overriding (like insert_or_assign()) while
+  // prepend/=+ is not (like insert()). In a sense, whatever appears last
+  // (from left to right) is kept, which is consistent with what we expect to
+  // happen when specifying the same key repeatedly in a representation (e.g.,
+  // a@0 a@1).
   //
   template <typename K, typename V>
   struct map_value_type;
diff --git a/libbuild2/variable.txx b/libbuild2/variable.txx
index bc4132f..485f9dc 100644
--- a/libbuild2/variable.txx
+++ b/libbuild2/variable.txx
@@ -591,7 +591,7 @@ namespace build2
   }
 
   template <typename T>
-  static names_view
+  names_view
   vector_reverse (const value& v, names& s, bool)
   {
     auto& vv (v.as<vector<T>> ());
@@ -604,7 +604,7 @@ namespace build2
   }
 
   template <typename T>
-  static int
+  int
   vector_compare (const value& l, const value& r)
   {
     auto& lv (l.as<vector<T>> ());
@@ -637,6 +637,8 @@ namespace build2
     vector_value_type (value_type&& v)
         : value_type (move (v))
     {
+      // Note: vector<T> always has a convenience alias.
+      //
       type_name  = value_traits<T>::type_name;
       type_name += 's';
       name = type_name.c_str ();
@@ -706,7 +708,7 @@ namespace build2
   }
 
   template <typename K, typename V>
-  static names_view
+  names_view
   pair_vector_reverse (const value& v, names& s, bool)
   {
     auto& vv (v.as<vector<pair<K, V>>> ());
@@ -719,7 +721,7 @@ namespace build2
   }
 
   template <typename K, typename V>
-  static int
+  int
   pair_vector_compare (const value& l, const value& r)
   {
     auto& lv (l.as<vector<pair<K, V>>> ());
@@ -754,10 +756,13 @@ namespace build2
     pair_vector_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = value_traits<K>::type_name;
-      type_name += '_';
+      // vector<pair<K,V>>
+      //
+      type_name  = "vector<pair<";
+      type_name += value_traits<K>::type_name;
+      type_name += ',';
       type_name += value_traits<V>::type_name;
-      type_name += "_pair_vector";
+      type_name += ">>";
       name = type_name.c_str ();
     }
   };
@@ -773,10 +778,13 @@ namespace build2
     pair_vector_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = value_traits<K>::type_name;
-      type_name += "_optional_";
+      // vector<pair<K,optional<V>>>
+      //
+      type_name  = "vector<pair<";
+      type_name += value_traits<K>::type_name;
+      type_name += ",optional<";
       type_name += value_traits<V>::type_name;
-      type_name += "_pair_vector";
+      type_name += ">>>";
       name = type_name.c_str ();
     }
   };
@@ -789,11 +797,13 @@ namespace build2
     pair_vector_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = "optional_";
+      // vector<pair<optional<K>,V>>
+      //
+      type_name  = "vector<pair<optional<";
       type_name += value_traits<K>::type_name;
-      type_name += '_';
+      type_name += ">,";
       type_name += value_traits<V>::type_name;
-      type_name += "_pair_vector";
+      type_name += ">>";
       name = type_name.c_str ();
     }
   };
@@ -847,7 +857,9 @@ namespace build2
                       "element",
                       var));
 
-      p.emplace (move (v.first), move (v.second));
+      // Poor man's emplace_or_assign().
+      //
+      p.emplace (move (v.first), V ()).first->second = move (v.second);
     }
   }
 
@@ -872,9 +884,7 @@ namespace build2
                       "element",
                       var));
 
-      // Poor man's emplace_or_assign().
-      //
-      p.emplace (move (v.first), V ()).first->second = move (v.second);
+      p.emplace (move (v.first), move (v.second));
     }
   }
 
@@ -889,7 +899,7 @@ namespace build2
   }
 
   template <typename K, typename V>
-  static names_view
+  names_view
   map_reverse (const value& v, names& s, bool)
   {
     auto& vm (v.as<map<K, V>> ());
@@ -902,7 +912,7 @@ namespace build2
   }
 
   template <typename K, typename V>
-  static int
+  int
   map_compare (const value& l, const value& r)
   {
     auto& lm (l.as<map<K, V>> ());
@@ -926,6 +936,59 @@ namespace build2
     return 0;
   }
 
+  // Note that unlike json_value, we don't provide index support for maps.
+  // There are two reasons for this: Firstly, consider map<uint64_t,...>.
+  // Secondly, even something like map<string,...> may contain integers as
+  // keys (in JSON, there is a strong convention for object member names not
+  // to be integers). Instead, we provide the $keys() function which allows
+  // one to implement an index-based access with a bit of overhead, if needed.
+  //
+  template <typename K, typename V>
+  value
+  map_subscript (const value& val, value* val_data,
+                 value&& sub,
+                 const location& sloc,
+                 const location& bloc)
+  {
+    // Process subscript even if the value is null to make sure it is valid.
+    //
+    K k;
+    try
+    {
+      k = convert<K> (move (sub));
+    }
+    catch (const invalid_argument& e)
+    {
+      fail (sloc) << "invalid " << value_traits<map<K, V>>::value_type.name
+                  << " value subscript: " << e <<
+        info (bloc) << "use the '\\[' escape sequence if this is a "
+                    << "wildcard pattern";
+    }
+
+    value r;
+    if (!val.null)
+    {
+      const auto& m (val.as<map<K, V>> ());
+      auto i (m.find (k));
+      if (i != m.end ())
+      {
+        // Steal the value if possible.
+        //
+        r = (&val == val_data
+             ? V (move (const_cast<V&> (i->second)))
+             : V (i->second));
+      }
+    }
+
+    // Typify null values so that type-specific subscript (e.g., for
+    // json_value) gets called for chained subscripts.
+    //
+    if (r.null)
+      r.type = &value_traits<V>::value_type;
+
+    return r;
+  }
+
   // Make sure these are static-initialized together. Failed that VC will make
   // sure it's done in the wrong order.
   //
@@ -937,11 +1000,15 @@ namespace build2
     map_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = value_traits<K>::type_name;
-      type_name += '_';
+      // map<K,V>
+      //
+      type_name  = "map<";
+      type_name += value_traits<K>::type_name;
+      type_name += ',';
       type_name += value_traits<V>::type_name;
-      type_name += "_map";
+      type_name += '>';
       name = type_name.c_str ();
+      subscript = &map_subscript<K, V>;
     }
   };
 
@@ -956,11 +1023,15 @@ namespace build2
     map_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = value_traits<K>::type_name;
-      type_name += "_optional_";
+      // map<K,optional<V>>
+      //
+      type_name  = "map<";
+      type_name += value_traits<K>::type_name;
+      type_name += ",optional<";
       type_name += value_traits<V>::type_name;
-      type_name += "_map";
+      type_name += ">>";
       name = type_name.c_str ();
+      // @@ TODO: subscript
     }
   };
 
@@ -972,18 +1043,38 @@ namespace build2
     map_value_type (value_type&& v)
         : value_type (move (v))
     {
-      type_name  = "optional_";
+      // map<optional<K>,V>
+      //
+      type_name  = "map<optional<";
       type_name += value_traits<K>::type_name;
-      type_name += '_';
+      type_name += ">,";
       type_name += value_traits<V>::type_name;
-      type_name += "_map";
+      type_name += '>';
       name = type_name.c_str ();
+      // @@ TODO: subscript
+    }
+  };
+
+  // Convenience aliases for certain map<T,T> cases.
+  //
+  template <>
+  struct map_value_type<string, string>: value_type
+  {
+    map_value_type (value_type&& v)
+        : value_type (move (v))
+    {
+      name = "string_map";
+      subscript = &map_subscript<string, string>;
     }
   };
 
   template <typename K, typename V>
   const map<K, V> value_traits<map<K, V>>::empty_instance;
 
+  // Note that custom iteration would be better (more efficient, return typed
+  // value), but we don't yet have pair<> as value type so we let the generic
+  // implementation return an untyped pair.
+  //
   template <typename K, typename V>
   const map_value_type<K, V>
   value_traits<map<K, V>>::value_type = build2::value_type // VC14 wants =
@@ -992,7 +1083,7 @@ namespace build2
     sizeof (map<K, V>),
     nullptr,             // No base.
     true,                // Container.
-    nullptr,             // No element (not named).
+    nullptr,             // No element (pair<> not a value type yet).
     &default_dtor<map<K, V>>,
     &default_copy_ctor<map<K, V>>,
     &default_copy_assign<map<K, V>>,
@@ -1003,7 +1094,7 @@ namespace build2
     nullptr,             // No cast (cast data_ directly).
     &map_compare<K, V>,
     &default_empty<map<K, V>>,
-    nullptr,             // Subscript.
+    nullptr,             // Subscript (patched in by map_value_type above).
     nullptr              // Iterate.
   };
 
diff --git a/tests/function/string/testscript b/tests/function/string/testscript
index 364ce42..a363cc3 100644
--- a/tests/function/string/testscript
+++ b/tests/function/string/testscript
@@ -43,8 +43,10 @@
 : size
 :
 {
-  $* <'print $size([string] abc)' >'3' : basics
-  $* <'print $size([string] )'    >'0' : zero
+  $* <'print $size([string] abc)'             >'3' : basics
+  $* <'print $size([string] )'                >'0' : zero
+  $* <'print $size([strings] a b c)'          >'3' : strings
+  $* <'print $size([string_map] a@1 b@2 c@3)' >'3' : string_map
 }
 
 : find
@@ -62,3 +64,7 @@
   $* <'print $find_index([strings] x y z, Y)'        >'3' : basics-false
   $* <'print $find_index([strings] x y z, Y, icase)' >'1' : icase
 }
+
+: keys
+:
+$* <'print $keys([string_map] a@1 b@2 c@3)' >'a b c'
diff --git a/tests/type/map/buildfile b/tests/type/map/buildfile
new file mode 100644
index 0000000..7f2cdcf
--- /dev/null
+++ b/tests/type/map/buildfile
@@ -0,0 +1,4 @@
+# file      : tests/type/map/buildfile
+# license   : MIT; see accompanying LICENSE file
+
+./: testscript $b
diff --git a/tests/type/map/testscript b/tests/type/map/testscript
new file mode 100644
index 0000000..7b90ddd
--- /dev/null
+++ b/tests/type/map/testscript
@@ -0,0 +1,65 @@
+# file      : tests/type/map/testscript
+# license   : MIT; see accompanying LICENSE file
+
+# See also tests in function/*/ (size(), keys()).
+
+.include ../../common.testscript
+
+: basics
+:
+$* <<EOI >>EOO
+m = [string_map] a@0 b@2 a@1
+print $m
+m += c@3 b@0
+print $m
+m =+ d@4 b@1
+print $m
+EOI
+a@1 b@2
+a@1 b@0 c@3
+a@1 b@0 c@3 d@4
+EOO
+
+: type
+:
+$* <<EOI >>EOO
+m = [string_map]
+print $type($m)
+EOI
+string_map
+EOO
+
+: subscript
+:
+$* <<EOI >>EOO
+m = [string_map] a@1 b@2 c@3
+print ($m[b])
+print ($m[z])
+EOI
+2
+[null]
+EOO
+
+: iteration
+:
+$* <<EOI >>EOO
+for p: [string_map] a@1 b@2 c@3
+  print $first($p) $second($p)
+EOI
+a 1
+b 2
+c 3
+EOO
+
+: iteration-index
+:
+$* <<EOI >>EOO
+m = [string_map] a@1 b@2 c@3
+k = $keys($m)
+for i: $integer_sequence(0, $size($k))
+  print $i ($k[$i]) ($m[($k[$i])]) # @@ TMP: nested subscript
+EOI
+0 a 1
+1 b 2
+2 c 3
+EOO