Add support for derived-to-base function overload resolution

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 <typename D>
-    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<string, function_overload>;
     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<value> args, const location&);
+    call (const string& name, vector_view<value> 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 <build2/function>
 
+#include <cstring> // 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<const value_type*> t (
+          i < f.arg_types.size () ? f.arg_types[i] : nullopt);
+
+        os << (t ? (*t != nullptr ? (*t)->name : "<untyped>") : "<anytype>");
+      }
+    }
+
+    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<value> args, const location& loc)
+  call (const string& name, vector_view<value> 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<const function_overload*, 1> 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<const value_type*> 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 : "<untyped>") : "<anytype>");
-        }
-      }
+            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 <butl/optional>
 #include <butl/timestamp>
 #include <butl/vector-view>
+#include <butl/small-vector>
 
 namespace build2
 {
@@ -56,7 +57,8 @@ namespace build2
   using std::weak_ptr;
 
   using std::vector;
-  using butl::vector_view; // <butl/vector-view>
+  using butl::vector_view;  // <butl/vector-view>
+  using butl::small_vector; // <butl/small-vector>
 
   using strings = vector<string>;
   using cstrings = vector<const char*>;
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<T>::value_type);
-    return *static_cast<T*> (v.type->cast == nullptr
-                             ? static_cast<void*> (&v.data_)
-                             : const_cast<void*> (v.type->cast (v, v.type)));
+    // Forward to const T&.
+    //
+    return const_cast<T&> (cast<T> (static_cast <const value&> (v)));
   }
 
   template <typename T>
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\(<untyped>)
-  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\(<untyped>)
-  info:  candidate: ambig\(<untyped> [, uint64]), qualified name dummy.ambig
-  info:  candidate: ambig\(<untyped> [, string]), qualified name dummy.ambig
+  info: candidate: ambig\(<untyped> [, uint64]), qualified name dummy.ambig
+  info: candidate: ambig\(<untyped> [, 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\(<untyped> [, uint64]), qualified name dummy.ambig
-  info:  candidate: ambig\(<untyped> [, string]), qualified name dummy.ambig
+  info: candidate: ambig\(<untyped> [, uint64]), qualified name dummy.ambig
+  info: candidate: ambig\(<untyped> [, string]), qualified name dummy.ambig
 EOE
 
 : print-fovl-variadic
 :
 $* <'$variadic(abc)' 2>>EOE != 0
 buildfile:1:2: error: unmatched call to variadic\(<untyped>)
-  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.
     //