From 7a528eab1561b0d0d4ec29f98355fe67025ea632 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 21 Nov 2016 11:56:00 +0200 Subject: Add support for derived-to-base function overload resolution --- build2/function | 31 +++-- build2/function.cxx | 258 +++++++++++++++++++++++++++-------------- build2/types | 4 +- build2/variable | 8 +- build2/variable.ixx | 7 +- unit-tests/function/call.test | 21 ++-- unit-tests/function/driver.cxx | 2 + 7 files changed, 220 insertions(+), 111 deletions(-) diff --git a/build2/function b/build2/function index bd91117..c5cde27 100644 --- a/build2/function +++ b/build2/function @@ -67,8 +67,9 @@ namespace build2 struct function_overload { - const char* name; // Set to point to key by insert() below. - const char* qual_name; // Qualified name, NULL if none. + const char* name; // Set to point to key by insert() below. + const char* alt_name; // Alternative name, NULL if none. This is the + // qualified name for unqualified or vice verse. // Arguments. // @@ -100,19 +101,19 @@ namespace build2 function_overload () = default; - function_overload (const char* qn, + function_overload (const char* an, size_t mi, size_t ma, types ts, function_impl* im) - : qual_name (qn), + : alt_name (an), arg_min (mi), arg_max (ma), arg_types (move (ts)), impl (im) {} template - function_overload (const char* qn, + function_overload (const char* an, size_t mi, size_t ma, types ts, function_impl* im, D d) - : function_overload (qn, mi, ma, move (ts), im) + : function_overload (an, mi, ma, move (ts), im) { // std::is_pod appears to be broken in VC15. // @@ -124,11 +125,15 @@ namespace build2 } }; + ostream& + operator<< (ostream&, const function_overload&); // Print signature. + class function_map { public: using map_type = std::unordered_multimap; using iterator = map_type::iterator; + using const_iterator = map_type::const_iterator; iterator insert (string name, function_overload); @@ -137,7 +142,19 @@ namespace build2 erase (iterator i) {map_.erase (i);} value - call (const string& name, vector_view args, const location&); + call (const string& name, vector_view args, const location&) const; + + iterator + begin () {return map_.begin ();} + + iterator + end () {return map_.end ();} + + const_iterator + begin () const {return map_.begin ();} + + const_iterator + end () const {return map_.end ();} private: map_type map_; diff --git a/build2/function.cxx b/build2/function.cxx index 91c5b3e..ec70529 100644 --- a/build2/function.cxx +++ b/build2/function.cxx @@ -4,10 +4,60 @@ #include +#include // strchr() + using namespace std; namespace build2 { + ostream& + operator<< (ostream& os, const function_overload& f) + { + os << f.name << '('; + + bool v (f.arg_max == function_overload::arg_variadic); + size_t n (v ? max (f.arg_min, f.arg_types.size ()): f.arg_max); + + // Handle variadic tail as the last pseudo-argument. + // + for (size_t i (0); i != n + (v ? 1 : 0); ++i) + { + if (i == f.arg_min) + os << (i != 0 ? " [" : "["); + + os << (i != 0 ? ", " : ""); + + if (i == n) // Variadic tail (last). + os << "..."; + else + { + // If count is greater than f.arg_typed, then we assume the rest are + // valid but untyped. + // + const optional t ( + i < f.arg_types.size () ? f.arg_types[i] : nullopt); + + os << (t ? (*t != nullptr ? (*t)->name : "") : ""); + } + } + + if (n + (v ? 1 : 0) > f.arg_min) + os << ']'; + + os << ')'; + + if (f.alt_name != nullptr) + { + auto k (strchr (f.alt_name, '.') == nullptr + ? "unqualified" + : "qualified"); + + os << ", " << k << " name " << f.alt_name; + } + + return os; + } + auto function_map:: insert (string name, function_overload f) -> iterator { @@ -24,7 +74,7 @@ namespace build2 } value function_map:: - call (const string& name, vector_view args, const location& loc) + call (const string& name, vector_view args, const location& loc) const { auto print_call = [&name, &args] (ostream& os) { @@ -39,113 +89,144 @@ namespace build2 os << ')'; }; - auto print_fovl = [&name] (ostream& os, const function_overload& f) - { - os << name << '('; + // Overload resolution. + // + // Ours is pretty simple: if all the arguments match exactly, then we have + // a perfect match. Otherwise, if any argument matches via the derived-to- + // base conversion, then we have an imperfect match. More than one perfect + // or imperfect match is ambiguous (i.e., we don't try to rank imperfect + // matches). + // + size_t count (args.size ()); + auto ip (map_.equal_range (name)); - bool v (f.arg_max == function_overload::arg_variadic); - size_t n (v ? max (f.arg_min, f.arg_types.size ()): f.arg_max); + // First look for a perfect match, then for imperfect. We do it this way + // to make sure we always stay small in the successful case. + // + small_vector r; - // Handle variadic tail as the last pseudo-argument. - // - for (size_t i (0); i != n + (v ? 1 : 0); ++i) + for (bool perf (true);; perf = false) + { + for (auto it (ip.first); it != ip.second; ++it) { - if (i == f.arg_min) - os << (i != 0 ? " [" : "["); + const function_overload& f (it->second); - os << (i != 0 ? ", " : ""); + // Argument count match. + // + if (count < f.arg_min || count > f.arg_max) + continue; - if (i == n) // Variadic tail (last). - os << "..."; - else + // Argument types match. + // { - // If count is greater than f.arg_typed, then we assume the rest are - // valid but untyped. - // - const optional t ( - i < f.arg_types.size () ? f.arg_types[i] : nullopt); + size_t i (0), n (min (count, f.arg_types.size ())); + for (; i != n; ++i) + { + if (!f.arg_types[i]) // Anytyped. + continue; - os << (t ? (*t != nullptr ? (*t)->name : "") : ""); - } - } + const value_type* at (args[i].type); + const value_type* ft (*f.arg_types[i]); - if (n + (v ? 1 : 0) > f.arg_min) - os << ']'; + if (at == ft) // Types match perfectly. + continue; - os << ')'; + if (!perf && at != nullptr && ft != nullptr) + { + while ((at = at->base) != nullptr && at != ft) ; - if (f.qual_name) - os << ", qualified name " << f.qual_name; - }; + if (at != nullptr) // Types match via derived-to-base. + continue; + } - // Overload resolution. - // - const function_overload* r (nullptr); + break; + } - size_t count (args.size ()); - auto ip (map_.equal_range (name)); + if (i != n) + continue; + } - for (auto it (ip.first); it != ip.second; ++it) - { - const function_overload& f (it->second); + r.push_back (&f); // Continue looking to detect ambiguities. + } - // Argument count match. - // - if (count < f.arg_min || count > f.arg_max) - continue; + if (!r.empty () || !perf) + break; + } - // Argument types match. - // + switch (r.size ()) + { + case 1: { - size_t i (0), n (min (count, f.arg_types.size ())); - for (; i != n; ++i) - if (f.arg_types[i] && *f.arg_types[i] != args[i].type) - break; - - if (i != n) - continue; + // Print the call location if the function fails. + // + auto g ( + make_exception_guard ( + [&loc, &print_call] () + { + if (verb != 0) + { + diag_record dr (info (loc)); + dr << "while calling "; print_call (dr.os); + } + })); + + auto f (r.back ()); + return f->impl (move (args), *f); } - - if (r != nullptr) + case 0: { - diag_record dr (fail (loc)); + // No match. + // + { + diag_record dr (error (loc)); - dr << "ambiguous call to "; print_call (dr.os); - dr << info << " candidate: "; print_fovl (dr.os, *r); - dr << info << " candidate: "; print_fovl (dr.os, f); - } + dr << "unmatched call to "; print_call (dr.os); - r = &f; // Continue looking to detect ambiguities. - } - - if (r == nullptr) - { - diag_record dr (fail (loc)); + for (auto i (ip.first); i != ip.second; ++i) + dr << info << "candidate: " << i->second; - dr << "unmatched call to "; print_call (dr.os); + // If this is an unqualified name, then also print qualified + // functions that end with this name. But skip functions that we + // have already printed in the previous loop. + // + if (name.find ('.') == string::npos) + { + size_t n (name.size ()); + + for (auto i (functions.begin ()); i != functions.end (); ++i) + { + const string& q (i->first); + const function_overload& f (i->second); + + if ((f.alt_name == nullptr || f.alt_name != name) && + q.size () > n) + { + size_t p (q.size () - n); + if (q[p - 1] == '.' && q.compare (p, n, name) == 0) + dr << info << "candidate: " << i->second; + } + } + } + } - for (auto it (ip.first); it != ip.second; ++it) + throw failed (); + } + default: { - const function_overload& f (it->second); + // Ambigous match. + // + { + diag_record dr (error (loc)); - dr << info << " candidate: "; print_fovl (dr.os, f); - } - } + dr << "ambiguous call to "; print_call (dr.os); - // Print the call location if the function fails. - // - auto g ( - make_exception_guard ( - [&loc, &print_call] () - { - if (verb != 0) - { - diag_record dr (info (loc)); - dr << "while calling "; print_call (dr.os); - } - })); + for (auto f: r) + dr << info << "candidate: " << *f; + } - return r->impl (move (args), *r); + throw failed (); + } + } } value function_family:: @@ -201,15 +282,16 @@ namespace build2 n.insert (0, qual); } - // First insert the qualified name and use its key for f.qual_name. + auto i (qn.empty () ? functions.end () : functions.insert (move (qn), f)); + auto j (functions.insert (move (n), move (f))); + + // If we have both, then set alternative names. // - if (!qn.empty ()) + if (i != functions.end ()) { - auto i (functions.insert (move (qn), f)); - f.qual_name = i->first.c_str (); + i->second.alt_name = j->first.c_str (); + j->second.alt_name = i->first.c_str (); } - - functions.insert (move (n), move (f)); } // Static-initialize the function map and populate with builtin functions. diff --git a/build2/types b/build2/types index 783aff0..b4488bb 100644 --- a/build2/types +++ b/build2/types @@ -30,6 +30,7 @@ #include #include #include +#include namespace build2 { @@ -56,7 +57,8 @@ namespace build2 using std::weak_ptr; using std::vector; - using butl::vector_view; // + using butl::vector_view; // + using butl::small_vector; // using strings = vector; using cstrings = vector; diff --git a/build2/variable b/build2/variable index a3f050d..4fd802f 100644 --- a/build2/variable +++ b/build2/variable @@ -30,10 +30,10 @@ namespace build2 const size_t size; // Type size in value::data_ (only used for PODs). // Base type, if any. We have very limited support for inheritance: a - // const value (but not non-const) can be cast to the base type. In - // particular, a derived/base value cannot be assigned to base/derived. - // If not NULL, then the cast function below is expected to return the - // base pointer if its second argument points to the base's value_type. + // value can be cast to the base type. In particular, a derived/base value + // cannot be assigned to base/derived. If not NULL, then the cast function + // below is expected to return the base pointer if its second argument + // points to the base's value_type. // const value_type* base; diff --git a/build2/variable.ixx b/build2/variable.ixx index 1e9dfe6..4d70685 100644 --- a/build2/variable.ixx +++ b/build2/variable.ixx @@ -136,10 +136,9 @@ namespace build2 inline T& cast (value& v) { - assert (v && v.type == &value_traits::value_type); - return *static_cast (v.type->cast == nullptr - ? static_cast (&v.data_) - : const_cast (v.type->cast (v, v.type))); + // Forward to const T&. + // + return const_cast (cast (static_cast (v))); } template diff --git a/unit-tests/function/call.test b/unit-tests/function/call.test index d459300..003a828 100644 --- a/unit-tests/function/call.test +++ b/unit-tests/function/call.test @@ -14,8 +14,15 @@ $* <'print $dummy.qual()' >'abc' : $* <'print $qual()' 2>>EOE != 0 buildfile:1:8: error: unmatched call to qual\() + info: candidate: dummy.qual\() EOE +: derived-base +: Test derived-to-base overload resolution +: +$* <'print $dummy.abs([dir_path] .)' >'false'; +$* <'print $dummy.abs([abs_dir_path] .)' >'true' + : variadic : # @@ TMP: add some args @@ -45,22 +52,22 @@ EOE : $* <'$dummy0(abc)' 2>>EOE != 0 buildfile:1:2: error: unmatched call to dummy0\() - info: candidate: dummy0\(), qualified name dummy.dummy0 + info: candidate: dummy0\(), qualified name dummy.dummy0 EOE : no-match-type : $* <'$dummy1([uint64] 123)' 2>>EOE != 0 buildfile:1:2: error: unmatched call to dummy1\(uint64) - info: candidate: dummy1\(string), qualified name dummy.dummy1 + info: candidate: dummy1\(string), qualified name dummy.dummy1 EOE : ambig : $* <'$ambig(abc)' 2>>EOE != 0 buildfile:1:2: error: ambiguous call to ambig\() - info: candidate: ambig\( [, uint64]), qualified name dummy.ambig - info: candidate: ambig\( [, string]), qualified name dummy.ambig + info: candidate: ambig\( [, uint64]), qualified name dummy.ambig + info: candidate: ambig\( [, string]), qualified name dummy.ambig EOE : optional-absent @@ -111,15 +118,15 @@ EOE : $* <'$ambig([bool] true)' 2>>EOE != 0 buildfile:1:2: error: unmatched call to ambig\(bool) - info: candidate: ambig\( [, uint64]), qualified name dummy.ambig - info: candidate: ambig\( [, string]), qualified name dummy.ambig + info: candidate: ambig\( [, uint64]), qualified name dummy.ambig + info: candidate: ambig\( [, string]), qualified name dummy.ambig EOE : print-fovl-variadic : $* <'$variadic(abc)' 2>>EOE != 0 buildfile:1:2: error: unmatched call to variadic\() - info: candidate: variadic\(bool [, ...]) + info: candidate: variadic\(bool [, ...]) EOE : member-function diff --git a/unit-tests/function/driver.cxx b/unit-tests/function/driver.cxx index ba51662..0708cea 100644 --- a/unit-tests/function/driver.cxx +++ b/unit-tests/function/driver.cxx @@ -47,6 +47,8 @@ namespace build2 f[".length"] = &string::size; // Member function. f[".type"] = &name::type; // Data member. + f[".abs"] = [](dir_path d) {return d.absolute ();}; + // Variadic function with first required argument of type bool. Returns // number of arguments passed. // -- cgit v1.1