From 0aa7a94e1032a96a2a72cb6a82824f9fe970d412 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Wed, 14 Dec 2022 14:18:44 +0200 Subject: Improve empty simple value to empty list of names reduction heuristics Specifically, do not reduce typed RHS empty simple values for prepend/append and additionally for assignment provided LHS is typed and is a container. --- libbuild2/adhoc-rule-buildscript.cxx | 2 +- libbuild2/buildspec.cxx | 4 +-- libbuild2/cc/pkgconfig.cxx | 2 +- libbuild2/config/init.cxx | 2 +- libbuild2/config/operation.cxx | 4 +-- libbuild2/dump.cxx | 2 +- libbuild2/file.cxx | 2 +- libbuild2/function.cxx | 2 +- libbuild2/function.test.cxx | 2 +- libbuild2/functions-builtin.cxx | 2 +- libbuild2/functions-regex.cxx | 2 +- libbuild2/parser.cxx | 62 ++++++++++++++++++++++++++---------- libbuild2/script/parser.cxx | 8 +++-- libbuild2/target.cxx | 2 +- libbuild2/variable.cxx | 41 ++++++++++++++++++------ libbuild2/variable.hxx | 28 ++++++++++------ libbuild2/variable.ixx | 11 ++++--- libbuild2/variable.txx | 25 +++++++++------ tests/value/reverse.testscript | 55 ++++++++++++++++++++++++++++++++ 19 files changed, 191 insertions(+), 67 deletions(-) diff --git a/libbuild2/adhoc-rule-buildscript.cxx b/libbuild2/adhoc-rule-buildscript.cxx index 2cec3f3..ce4ab8b 100644 --- a/libbuild2/adhoc-rule-buildscript.cxx +++ b/libbuild2/adhoc-rule-buildscript.cxx @@ -47,7 +47,7 @@ namespace build2 if (l) { storage.clear (); - names_view ns (reverse (*l, storage)); + names_view ns (reverse (*l, storage, true /* reduce */)); for (const name& n: ns) to_checksum (cs, n); diff --git a/libbuild2/buildspec.cxx b/libbuild2/buildspec.cxx index bd580ca..2eeaf31 100644 --- a/libbuild2/buildspec.cxx +++ b/libbuild2/buildspec.cxx @@ -53,7 +53,7 @@ namespace build2 if (v) { names storage; - os << reverse (v, storage); + os << reverse (v, storage, true /* reduce */); } else os << "[null]"; @@ -86,7 +86,7 @@ namespace build2 if (v) { names storage; - os << reverse (v, storage); + os << reverse (v, storage, true /* reduce */); } else os << "[null]"; diff --git a/libbuild2/cc/pkgconfig.cxx b/libbuild2/cc/pkgconfig.cxx index d659a2c..c41a182 100644 --- a/libbuild2/cc/pkgconfig.cxx +++ b/libbuild2/cc/pkgconfig.cxx @@ -1927,7 +1927,7 @@ namespace build2 const value& val (*b.val); names ns; - names_view nv (reverse (val, ns)); + names_view nv (reverse (val, ns, true /* reduce */)); os << *b.name << " ="; diff --git a/libbuild2/config/init.cxx b/libbuild2/config/init.cxx index 46239d8..d42bace 100644 --- a/libbuild2/config/init.cxx +++ b/libbuild2/config/init.cxx @@ -39,7 +39,7 @@ namespace build2 save_environment (const value& d, const value* b, names& storage) { if (b == nullptr) - return make_pair (reverse (d, storage), "="); + return make_pair (reverse (d, storage, true /* reduce */), "="); // The plan is to iterator over environment variables adding those that // are not in base to storage. There is, however, a complication: we may diff --git a/libbuild2/config/operation.cxx b/libbuild2/config/operation.cxx index 34ed402..9079bbf 100644 --- a/libbuild2/config/operation.cxx +++ b/libbuild2/config/operation.cxx @@ -181,7 +181,7 @@ namespace build2 if (v) { storage.clear (); - dr << "'" << reverse (v, storage) << "'"; + dr << "'" << reverse (v, storage, true /* reduce */) << "'"; } else dr << "[null]"; @@ -531,7 +531,7 @@ namespace build2 pair p ( sv.save != nullptr ? sv.save (v, base, storage) - : make_pair (reverse (v, storage), "=")); + : make_pair (reverse (v, storage, true /* reduce */), "=")); // Might becomes empty after a custom save function had at it. // diff --git a/libbuild2/dump.cxx b/libbuild2/dump.cxx index c28dd31..4ee75ee 100644 --- a/libbuild2/dump.cxx +++ b/libbuild2/dump.cxx @@ -49,7 +49,7 @@ namespace build2 if (v) { names storage; - os << (a ? " " : "") << reverse (v, storage); + os << (a ? " " : "") << reverse (v, storage, true /* reduce */); } } diff --git a/libbuild2/file.cxx b/libbuild2/file.cxx index bf50a25..acfb5d7 100644 --- a/libbuild2/file.cxx +++ b/libbuild2/file.cxx @@ -1706,7 +1706,7 @@ namespace build2 if (const value& v = *l) { storage.clear (); - auto ns (reverse (v, storage)); + auto ns (reverse (v, storage, true /* reduce */)); if (f == "multiline") { diff --git a/libbuild2/function.cxx b/libbuild2/function.cxx index ae69730..528b396 100644 --- a/libbuild2/function.cxx +++ b/libbuild2/function.cxx @@ -213,7 +213,7 @@ namespace build2 if (f->arg_types[i] && *f->arg_types[i] == nullptr && args[i].type != nullptr) - untypify (args[i]); + untypify (args[i], true /* reduce */); } } diff --git a/libbuild2/function.test.cxx b/libbuild2/function.test.cxx index 7ce7ad3..37ed5ff 100644 --- a/libbuild2/function.test.cxx +++ b/libbuild2/function.test.cxx @@ -115,7 +115,7 @@ namespace build2 else if (!a.empty ()) { names storage; - cout << reverse (a, storage); + cout << reverse (a, storage, true /* reduce */); } cout << endl; } diff --git a/libbuild2/functions-builtin.cxx b/libbuild2/functions-builtin.cxx index 6bf2264..378ffbc 100644 --- a/libbuild2/functions-builtin.cxx +++ b/libbuild2/functions-builtin.cxx @@ -83,7 +83,7 @@ namespace build2 if (v->null) return string (); - untypify (*v); // Reverse to names. + untypify (*v, true /* reduce */); // Reverse to names. ostringstream os; to_stream (os, diff --git a/libbuild2/functions-regex.cxx b/libbuild2/functions-regex.cxx index ca7e229..922be18 100644 --- a/libbuild2/functions-regex.cxx +++ b/libbuild2/functions-regex.cxx @@ -21,7 +21,7 @@ namespace build2 // Optimize for the string value type. // if (v.type != &value_traits::value_type) - untypify (v); + untypify (v, true /* reduce */); return convert (move (v)); } diff --git a/libbuild2/parser.cxx b/libbuild2/parser.cxx index 812f201..b118cee 100644 --- a/libbuild2/parser.cxx +++ b/libbuild2/parser.cxx @@ -44,7 +44,10 @@ namespace build2 { o << '='; names storage; - to_stream (o, reverse (a.value, storage), quote_mode::normal, '@'); + to_stream (o, + reverse (a.value, storage, true /* reduce */), + quote_mode::normal, + '@'); } return o; @@ -3692,7 +3695,7 @@ namespace build2 if (value v = parse_value_with_attributes (t, tt, pattern_mode::expand)) { names storage; - for (name& n: reverse (v, storage)) + for (name& n: reverse (v, storage, true /* reduce */)) { // @@ Could this be an out-qualified ad hoc import? // @@ -3762,7 +3765,12 @@ namespace build2 fail (l) << "null value in export"; if (val.type != nullptr) - untypify (val); + { + // While feels far-fetched, let's preserve empty typed values in the + // result. + // + untypify (val, false /* reduce */); + } export_value = move (val).as (); @@ -4446,7 +4454,11 @@ namespace build2 if (val && val.type != nullptr) { etype = val.type->element_type; - untypify (val); + + // Note that here we don't want to be reducing empty simple values to + // empty lists. + // + untypify (val, false /* reduce */); } if (tt != type::newline) @@ -4627,7 +4639,7 @@ namespace build2 if (value v = parse_value_with_attributes (t, tt, pattern_mode::expand)) { names storage; - cout << reverse (v, storage) << endl; + cout << reverse (v, storage, true /* reduce */) << endl; } else cout << "[null]" << endl; @@ -4660,7 +4672,7 @@ namespace build2 if (value v = parse_value_with_attributes (t, tt, pattern_mode::expand)) { names storage; - dr << reverse (v, storage); + dr << reverse (v, storage, true /* reduce */); } if (tt != type::eos) @@ -4843,7 +4855,12 @@ namespace build2 // We store prepend/append values untyped (similar to overrides). // if (rhs.type != nullptr && kind != type::assign) - untypify (rhs); + { + // Our heuristics for prepend/append of a typed value is to preserve + // empty (see apply_value_attributes() for details) so do not reduce. + // + untypify (rhs, false /* reduce */); + } if (p.second) { @@ -5152,6 +5169,13 @@ namespace build2 bool rhs_type (false); if (rhs.type != nullptr) { + // Our heuristics is to not reduce typed RHS empty simple values for + // prepend/append and additionally for assign provided LHS is a + // container. + // + bool reduce (kind == type::assign && + (type == nullptr || !type->container)); + // Only consider RHS type if there is no explicit or variable type. // if (type == nullptr) @@ -5162,7 +5186,7 @@ namespace build2 // Reduce this to the untyped value case for simplicity. // - untypify (rhs); + untypify (rhs, reduce); } if (kind == type::assign) @@ -6561,14 +6585,13 @@ namespace build2 if (!vnull) { if (vtype != nullptr) - untypify (rhs); + untypify (rhs, true /* reduce */); names& d (rhs.as ()); - // If the value is empty, then untypify() will (typically; no pun - // intended) represent it as an empty sequence of names rather than - // a sequence of one empty name. This is usually what we need (see - // simple_reverse() for details) but not in this case. + // If the value is empty, then we asked untypify() to reduce it to + // an empty sequence of names rather than a sequence of one empty + // name. // if (!d.empty ()) { @@ -7422,7 +7445,8 @@ namespace build2 fail (loc) << "null variable/function name"; names storage; - vector_view ns (reverse (v, storage)); // Movable. + vector_view ns ( + reverse (v, storage, true /* reduce */)); // Movable. size_t n (ns.size ()); // We cannot handle scope-qualification in the eval context as @@ -7643,7 +7667,7 @@ namespace build2 ? value (move (result_data)) : value (*result)); - untypify (val); + untypify (val, false /* reduce */); names& ns (val.as ()); @@ -7754,7 +7778,11 @@ namespace build2 fail (loc) << "no string conversion for " << t; result_data = move (p.first); - untypify (result_data); // Convert to untyped simple name. + + // Convert to untyped simple name reducing empty string to empty + // names as an optimization. + // + untypify (result_data, true /* reduce */); } if ((concat && vtype != nullptr) || // LHS typed. @@ -7855,7 +7883,7 @@ namespace build2 // @@ Could move if nv is result_data; see untypify(). // names nv_storage; - names_view nv (reverse (*result, nv_storage)); + names_view nv (reverse (*result, nv_storage, true /* reduce */)); count = splice_names ( loc, nv, move (nv_storage), ns, what, pairn, pp, dp, tp); diff --git a/libbuild2/script/parser.cxx b/libbuild2/script/parser.cxx index 88e2f06..0be22a6 100644 --- a/libbuild2/script/parser.cxx +++ b/libbuild2/script/parser.cxx @@ -1028,7 +1028,7 @@ namespace build2 storage.clear (); to_stream (os, - reverse (a.value, storage), + reverse (a.value, storage, true /* reduce */), quote_mode::normal, '@'); } @@ -2676,7 +2676,11 @@ namespace build2 if (val.type != nullptr) { etype = val.type->element_type; - untypify (val); + + // Note that here we don't want to be reducing empty simple + // values to empty lists. + // + untypify (val, false /* reduce */); } size_t fli (li); diff --git a/libbuild2/target.cxx b/libbuild2/target.cxx index 16aec49..6d083d9 100644 --- a/libbuild2/target.cxx +++ b/libbuild2/target.cxx @@ -605,7 +605,7 @@ namespace build2 // name)? But then again we don't expect many such overrides. Plus // will complicate the diagnostics below. // - ns = reverse (*l, storage); + ns = reverse (*l, storage, true /* reduce */); if (ns.size () == 1) { diff --git a/libbuild2/variable.cxx b/libbuild2/variable.cxx index 0017633..fefea98 100644 --- a/libbuild2/variable.cxx +++ b/libbuild2/variable.cxx @@ -377,7 +377,7 @@ namespace build2 } void - untypify (value& v) + untypify (value& v, bool reduce) { if (v.type == nullptr) return; @@ -389,7 +389,7 @@ namespace build2 } names ns; - names_view nv (v.type->reverse (v, ns)); + names_view nv (v.type->reverse (v, ns, reduce)); if (nv.empty () || nv.data () == ns.data ()) { @@ -493,6 +493,7 @@ namespace build2 type_name, sizeof (bool), nullptr, // No base. + false, // Not container. nullptr, // No element. nullptr, // No dtor (POD). nullptr, // No copy_ctor (POD). @@ -550,6 +551,7 @@ namespace build2 type_name, sizeof (int64_t), nullptr, // No base. + false, // Not container. nullptr, // No element. nullptr, // No dtor (POD). nullptr, // No copy_ctor (POD). @@ -607,6 +609,7 @@ namespace build2 type_name, sizeof (uint64_t), nullptr, // No base. + false, // Not container. nullptr, // No element. nullptr, // No dtor (POD). nullptr, // No copy_ctor (POD). @@ -701,6 +704,7 @@ namespace build2 type_name, sizeof (string), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -768,6 +772,7 @@ namespace build2 type_name, sizeof (path), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -835,6 +840,7 @@ namespace build2 sizeof (dir_path), &value_traits::value_type, // Base (assuming direct cast works for // both). + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -883,6 +889,7 @@ namespace build2 sizeof (abs_dir_path), &value_traits::value_type, // Base (assuming direct cast works // for both). + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -908,10 +915,10 @@ namespace build2 } static names_view - name_reverse (const value& v, names&) + name_reverse (const value& v, names&, bool reduce) { const name& n (v.as ()); - return n.empty () ? names_view (nullptr, 0) : names_view (&n, 1); + return reduce && n.empty () ? names_view (nullptr, 0) : names_view (&n, 1); } const char* const value_traits::type_name = "name"; @@ -921,6 +928,7 @@ namespace build2 type_name, sizeof (name), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -975,13 +983,13 @@ namespace build2 } static names_view - name_pair_reverse (const value& v, names& ns) + name_pair_reverse (const value& v, names& ns, bool reduce) { const name_pair& p (v.as ()); const name& f (p.first); const name& s (p.second); - if (f.empty () && s.empty ()) + if (reduce && f.empty () && s.empty ()) return names_view (nullptr, 0); if (f.empty ()) @@ -1003,6 +1011,7 @@ namespace build2 type_name, sizeof (name_pair), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -1133,10 +1142,14 @@ namespace build2 } static names_view - process_path_reverse (const value& v, names& s) + process_path_reverse (const value& v, names& s, bool) { const auto& x (v.as ()); + // Note that strictly speaking process_path doesn't have empty + // representation (see convert() above). Thus we always return reduced + // representation. + // if (!x.empty ()) { s.reserve (x.effect.empty () ? 1 : 2); @@ -1153,6 +1166,7 @@ namespace build2 type_name, sizeof (process_path), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &process_path_copy_ctor, @@ -1301,10 +1315,13 @@ namespace build2 } static names_view - process_path_ex_reverse (const value& v, names& s) + process_path_ex_reverse (const value& v, names& s, bool) { const auto& x (v.as ()); + // Note that process_path_ex only has reduced empty representation (see + // convert() above). + // if (!x.empty ()) { s.reserve ((x.effect.empty () ? 1 : 2) + @@ -1348,6 +1365,7 @@ namespace build2 sizeof (process_path_ex), &value_traits< // Base (assuming direct cast works process_path>::value_type, // for both). + false, // Not container. nullptr, // No element. &default_dtor, &process_path_ex_copy_ctor, @@ -1389,6 +1407,7 @@ namespace build2 type_name, sizeof (target_triplet), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -1433,6 +1452,7 @@ namespace build2 type_name, sizeof (project_name), nullptr, // No base. + false, // Not container. nullptr, // No element. &default_dtor, &default_copy_ctor, @@ -1544,7 +1564,7 @@ namespace build2 } static names_view - cmdline_reverse (const value& v, names&) + cmdline_reverse (const value& v, names&, bool) { const auto& x (v.as ()); return names_view (x.data (), x.size ()); @@ -1565,7 +1585,8 @@ namespace build2 type_name, sizeof (cmdline), nullptr, // No base. - &value_traits::value_type, + true, // Container. + &value_traits::value_type, // Element type. &default_dtor, &default_copy_ctor, &default_copy_assign, diff --git a/libbuild2/variable.hxx b/libbuild2/variable.hxx index 400aaf1..2942f1c 100644 --- a/libbuild2/variable.hxx +++ b/libbuild2/variable.hxx @@ -48,7 +48,11 @@ namespace build2 template const value_type* is_a () const; - // Element type, if this is a vector. + // True if the type is a container. + // + bool container; + + // Element type, if this is a container and the element type is named. // const value_type* element_type; @@ -75,9 +79,11 @@ namespace build2 void (*const prepend) (value&, names&&, const variable*); // Reverse the value back to a vector of names. Storage can be used by the - // implementation if necessary. Cannot be NULL. + // implementation if necessary. If reduce is true, then for an empty + // simple value return an empty list rather than a list of one empty name. + // Note that the value cannot be NULL. // - names_view (*const reverse) (const value&, names& storage); + names_view (*const reverse) (const value&, names& storage, bool reduce); // Cast value::data_ storage to value type so that the result can be // static_cast to const T*. If it is NULL, then cast data_ directly. Note @@ -363,8 +369,8 @@ namespace build2 // public: // Assign/append/prepend a typed value. For assign, LHS should be either - // of the same type or untyped. For append, LHS should be either of the - // same type or untyped and NULL. + // of the same type or untyped. For append/prepend, LHS should be either + // of the same type or untyped and NULL. // template value& operator= (T); template value& operator+= (T); @@ -497,18 +503,20 @@ namespace build2 typify_atomic (context&, value&, const value_type&, const variable*); // Remove value type from the value reversing it to names. This is similar - // to reverse() below except that it modifies the value itself. + // to reverse() below except that it modifies the value itself. Note that + // the reduce semantics applies to empty but not null. // - LIBBUILD2_SYMEXPORT void untypify (value&); + LIBBUILD2_SYMEXPORT void untypify (value&, bool reduce); // Reverse the value back to names. The value should not be NULL and storage - // should be empty. + // should be empty. If reduce is true, then for an empty simple value return + // an empty list rather than a list of one empty name. // vector_view - reverse (const value&, names& storage); + reverse (const value&, names& storage, bool reduce); vector_view - reverse (value&, names& storage); + reverse (value&, names& storage, bool reduce); // Variable lookup result, AKA, binding of a variable to a value. // diff --git a/libbuild2/variable.ixx b/libbuild2/variable.ixx index c9dfad4..c7b1f35 100644 --- a/libbuild2/variable.ixx +++ b/libbuild2/variable.ixx @@ -326,18 +326,21 @@ namespace build2 } inline vector_view - reverse (const value& v, names& storage) + reverse (const value& v, names& storage, bool reduce) { assert (v && storage.empty () && (v.type == nullptr || v.type->reverse != nullptr)); - return v.type == nullptr ? v.as () : v.type->reverse (v, storage); + + return v.type == nullptr + ? v.as () + : v.type->reverse (v, storage, reduce); } inline vector_view - reverse (value& v, names& storage) + reverse (value& v, names& storage, bool reduce) { - names_view cv (reverse (static_cast (v), storage)); + names_view cv (reverse (static_cast (v), storage, reduce)); return vector_view (const_cast (cv.data ()), cv.size ()); } diff --git a/libbuild2/variable.txx b/libbuild2/variable.txx index fda3486..2950ea0 100644 --- a/libbuild2/variable.txx +++ b/libbuild2/variable.txx @@ -229,13 +229,13 @@ namespace build2 template names_view - simple_reverse (const value& v, names& s) + simple_reverse (const value& v, names& s, bool reduce) { const T& x (v.as ()); - // Represent an empty simple value as empty name sequence rather than - // a single empty name. This way, for example, during serialization we - // end up with a much saner looking: + // Unless requested otherwise, represent an empty simple value as empty + // name sequence rather than a single empty name. This way, for example, + // during serialization we end up with a much saner looking: // // config.import.foo = // @@ -245,6 +245,8 @@ namespace build2 // if (!value_traits::empty (x)) s.emplace_back (value_traits::reverse (x)); + else if (!reduce) + s.push_back (name ()); return s; } @@ -590,7 +592,7 @@ namespace build2 template static names_view - vector_reverse (const value& v, names& s) + vector_reverse (const value& v, names& s, bool) { auto& vv (v.as> ()); s.reserve (vv.size ()); @@ -651,7 +653,8 @@ namespace build2 nullptr, // Patched above. sizeof (vector), nullptr, // No base. - &value_traits::value_type, + true, // Container. + &value_traits::value_type, // Element type. &default_dtor>, &default_copy_ctor>, &default_copy_assign>, @@ -702,7 +705,7 @@ namespace build2 template static names_view - pair_vector_reverse (const value& v, names& s) + pair_vector_reverse (const value& v, names& s, bool) { auto& vv (v.as>> ()); s.reserve (2 * vv.size ()); @@ -803,7 +806,8 @@ namespace build2 nullptr, // Patched above. sizeof (vector>), nullptr, // No base. - nullptr, // No element. + true, // Container. + nullptr, // No element (not named). &default_dtor>>, &default_copy_ctor>>, &default_copy_assign>>, @@ -882,7 +886,7 @@ namespace build2 template static names_view - map_reverse (const value& v, names& s) + map_reverse (const value& v, names& s, bool) { auto& vm (v.as> ()); s.reserve (2 * vm.size ()); @@ -983,7 +987,8 @@ namespace build2 nullptr, // Patched above. sizeof (map), nullptr, // No base. - nullptr, // No element. + true, // Container. + nullptr, // No element (not named). &default_dtor>, &default_copy_ctor>, &default_copy_assign>, diff --git a/tests/value/reverse.testscript b/tests/value/reverse.testscript index 9f73981..921d14b 100644 --- a/tests/value/reverse.testscript +++ b/tests/value/reverse.testscript @@ -89,3 +89,58 @@ EOO } } + +: reduce +: +: Test empty simple value reduction heuristics. +: +{ + : typed + : + $* <>"EOO" + x = [string] + n = [string,null] + y = [strings] $x + y += $x + y += $n + print $size($y) + + file{*}: y += $x + file{x}: + print $size($(file{x}: y)) + + for i: $x + print iteration + + print $null($x[0]) + EOI + 2 + 3 + iteration + false + EOO + + : untyped + : + $* <>"EOO" + x = + n = [null] + y = $x + y += $x + y += $n + print $size($y) + + file{*}: y += $x + file{x}: + print $size($(file{x}: y)) + + for i: $x + print iteration + + print $null($x[0]) + EOI + 0 + 0 + true + EOO +} -- cgit v1.1