Expand range of definitions that can be moved into stdlib (#1259)

The actual definitions that got moved into the stdlib here are pretty few:

* `clip()`
* `cross()`
* `dxx()`, `ddy()` etc.
* `degrees()`
* `distance()`
* `dot()`
* `faceforward()`

The meat of the change is infrastructure changes required to support these new declarations

* Generic versions of the standard operators (e.g., `operator+`) were added that are generic for a type `T` that implements the matching `__Builtin`-prefixed interface. An open question is whether we can now drop the non-generic versions in favor of just having these generic operators.

* A `__BuiltinLogicalType` interface was added to capture the commonality between integers and `bool`

* `__BuiltinArithmeticType` was extended so that implementations must support initialization from an `int`

* `__BuiltinFloatingPointType` was extended to require an accessor that returns the value of pi for the given type, and the concrete floating-point types were extended to provide definitions of this value.

* It turns out that our logic for checking if two functions have the same signature (and should thus count as redeclarations/redefinitions) wasn't taking generic constraints into account at all. That was fixed with a stopgap solution that checks if the generic constraints are pairwise identical, but I didn't implement the more "correct" fix that would require canonicalizing the constraints.

* When doing overload resolution and considering potential callees, logic was added so that a non-generic candidate should always be selected over a generic one (generally the Right Thing to do), and also so that a generic candidate with fewer parameters will be selected over one with more (an approximation of the much more complicated rule we'd ideally have).

* The formatting of declarations/overloads for "ambiguous overload" errors was fleshed out a bit to include more context (the "kind" of declaration where appropriate, the return type for function declarations) and to properly space thing when outputting specialization of operator overloads that end with `<` (so that we print `func < <int>(int, int)` instead of just `func <<int,int>(int,int)`).

* The core lookup routines were heavily refactored and reorganized to try to make them bottleneck more effectively so that all paths handle all the nuances of inheritance, extensions, etc.

* Because of the refactoring to lookup logic, the semantic checking logic related to checking if a type conforms to an interface was updated to be driven based on the `Type` that is supposed to be conforming, rather than a `DeclRef` to the type's declaration. This allows it to use the type-based lookup entry point and eliminates one special-case entry point for lookup.

In addition to the various core changes, this change also refactors some of the existing stdlib code to favor writing more things in actual Slang syntax, and less in C++ code that uses `StringBuilder` to construct the Slang syntax. There is a lot more that could be done along those lines, but even pushing this far is showing that the current approach that `slang-generate` takes for how to separate meta-level C++ and Slang code isn't really ideal, so a revamp of the generator code is probably needed before I continue pushing.

One surprising casualty of the refactoring of lookup is that we no longer have the `lookedUpDecls` field in `LookupResult`. That field probably didn't belong there anyway, but the role it served was important. The idea of `lookedUpDecls` was to avoid looking up in the same interface more than once in cases where a type might have a "diamond" inheritance pattern. Removing that field doesn't appear to affect correctness of any of our existing tests, but by adding a specific test for "diamond" inheritance I could see that the refactoring introduced a regression and made looking up a member inherited along multiple paths ambiguous.

Rather than add back `lookedUpDecls` I went for a simpler (but arguably even hackier) solution where when ranking candidates from a `LookupResult` we check for identical `DeclRef`s and arbitrarily favor one over the other. One complication that arises here is that when comparing `DeclRef`s inherited along different paths they might have a `ThisTypeSubstitution` for the same type, but with different subtype witnesses (because different inheritance paths could lead to different transitive subtype witnesses: e.g., `A : B : D` and `A : C : D`).

1 files changed, 218 insertions, 5 deletions

diff --git a/source/slang/slang-check-overload.cpp b/source/slang/slang-check-overload.cpp
index ace495512..41aa94a35 100644
--- a/source/slang/slang-check-overload.cpp
+++ b/source/slang/slang-check-overload.cpp
@@ -497,6 +497,33 @@ namespace Slang
         return false;
     }
 
+        /// If `declRef` representations a specialization of a generic, returns the number of specialized generic arguments.
+        /// Otherwise, returns zero.
+        ///
+    Int SemanticsVisitor::getSpecializedParamCount(DeclRef<Decl> const& declRef)
+    {
+        if(!declRef)
+            return 0;
+
+        // A specialization of a generic must point at the
+        // "inner" declaration of a generic. That means that
+        // the parent of the decl ref must be a generic.
+        //
+        auto parentGeneric = declRef.GetParent().as<GenericDecl>();
+        if(!parentGeneric)
+            return 0;
+        //
+        // Furthermore, the declaration we are considering
+        // must be the single "inner" declaration of the
+        // parent generic (and not somthing like a generic
+        // parameter).
+        //
+        if( parentGeneric.getDecl()->inner.Ptr() != declRef.getDecl())
+            return 0;
+
+        return CountParameters(parentGeneric).required;
+    }
+
     int SemanticsVisitor::CompareLookupResultItems(
         LookupResultItem const& left,
         LookupResultItem const& right)
@@ -534,6 +561,87 @@ namespace Slang
         return 0;
     }
 
+    int SemanticsVisitor::compareOverloadCandidateSpecificity(
+        LookupResultItem const& left,
+        LookupResultItem const& right)
+    {
+        // HACK: if both items refer to the same declaration,
+        // then arbitrarily pick one.
+        if(left.declRef.Equals(right.declRef))
+            return -1;
+
+        // There is a very general rule that we would like to enforce
+        // in principle:
+        //
+        // Given candidates A and B, if A being applicable to some
+        // arguments implies that B is also applicable, but not vice versa,
+        // then A is a more specific/specialized candidate than B.
+        //
+        // A number of conclusions follow from this general rule.
+        // For example, a non-generic declaration will always be
+        // more specific than a generic declaration that was specialized
+        // to matching types:
+        //
+        //      int doThing(int a);
+        //      T doThing<T>(T a);
+        //
+        // It is clear that if the non-generic `doThing` is applicable
+        // to an argument `x`, then `doThing<int>` is also applicable to
+        // `x`. However, knowing that the generic `doThing` was applicable
+        // to some `y` doesn't tell us that the non-generic `doThing` can
+        // be called on `y`, because `y` could have some type that can't
+        // convert to `int`.
+        //
+        // Similarly, a generic declaration with a subset of the parameters
+        // of another generic is always more specialized:
+        //
+        //      int doThing<T>(vector<T,3> value);
+        //      int doThing<T, let N : int>(vector<T,N> value);
+        //
+        // Here we know that both overloads can apply to `float3`, but only
+        // one can apply to `float4`, so the first overload is more
+        // specialized/specific.
+        //
+        // As a final example, a generic which places more constraints
+        // on its generic parameters is more specific, all other things
+        // being equal:
+        //
+        //      int doThing<T : IFoo>( T value );
+        //      int doThing<T>(T value);
+        //
+        // In this case we know that the first overload is applicable
+        // to a strict subset of the types that the second overload can
+        // apply to.
+        //
+        // The above rules represent the idealized principles we want
+        // to implement, but actually implementing that full check here
+        // could make overload resolution far more expensive.
+        //
+        // For now we are going to do something far simpler and hackier,
+        // which is to say that a candidate with more generic parameters
+        // is always preferred over one with fewer.
+        //
+        // TODO: We could extend this definition to account for constraints
+        // on generic parameters in the count, which would handle the
+        // need to prefer a more-constrained generic when possible.
+        //
+        // TODO: In the long run we should clearly replace this with
+        // the more general "does A being applicable imply B being applicable"
+        // test.
+        //
+        // TODO: The principle stated here doesn't take the actual
+        // arguments or their types into account, and it might be that
+        // in some cases disambiguation of which declaration should be
+        // preferred will depend on knowing the actual arguments.
+        //
+        auto leftSpecCount = getSpecializedParamCount(left.declRef);
+        auto rightSpecCount = getSpecializedParamCount(right.declRef);
+        if(leftSpecCount != rightSpecCount)
+            return int(leftSpecCount - rightSpecCount);
+
+        return 0;
+    }
+
     int SemanticsVisitor::CompareOverloadCandidates(
         OverloadCandidate*	left,
         OverloadCandidate*	right)
@@ -546,17 +654,66 @@ namespace Slang
         // the costs of their type conversion sequences
         if(left->status == OverloadCandidate::Status::Applicable)
         {
+            // If one candidate incurred less cost related to
+            // implicit conversion of arguments to matching
+            // parameter types, then we should prefer that
+            // candidate.
+            //
+            // TODO: This eventually should be refined into
+            // a test that checks conversion cost per-argument,
+            // and only considers a candidate "better" if it
+            // has lower cost for at least one argument, and
+            // does not have higher cost for any.
+            //
             if (left->conversionCostSum != right->conversionCostSum)
                 return left->conversionCostSum - right->conversionCostSum;
 
-            // If all conversion costs match, then we should consider
-            // whether one of the two items/declarations should be
-            // preferred based on grounds that have nothing to do
-            // with applicability or conversion costs.
+            // If both candidates appear to be equally good when it
+            // comes to the per-argument conversions required,
+            // then we have two other categories of criteria we
+            // can look at to disambiguate things:
+            //
+            // 1. We can look at how the lookup process found `left` and `right`
+            //    do decide which is a better match based purely on how "far away"
+            //    they are for lookup purposes. A canonincal example here would
+            //    be if one declaration shadows or overrides the other.
+            //
+            // 2. We can look at parameter lists of `left` and `right`, their types, etc.
+            //    do decide which is a better match based purely on structure.
+            //    Canonical examples in this case would be preferring a non-generic
+            //    candidate over a generic one, preferring a non-variadic candidate
+            //    over a variadic one, and preferring a candidate with fewer
+            //    default parameters over one with more.
+            //
+            // Deciding how to order/interleave these two categories of criteria
+            // is an important design decision.
+            //
+            // For example, consider:
+            //
+            //      float f(float x);
+            //
+            //      struct S
+            //      {
+            //          int f<T>(T x);
+            //
+            //          float g(float y) { return f(y); }
+            //      }
+            //
+            // In terms of structural/type matching, the global `f` is a more specialized
+            // candidate at the call site, while in terms of lookup/lexical crieteria
+            // the `S.f` declaration is better.
+            //
+            // For now we are considering lookup/overriding concerns first (so
+            // we would bias in favor of selecting `S.f` in the above example), and then
+            // structural/type concerns, but a more nuanced approach may be
+            // required in the future to better match programmer intuition.
             //
             auto itemDiff = CompareLookupResultItems(left->item, right->item);
             if(itemDiff)
                 return itemDiff;
+            auto specificityDiff = compareOverloadCandidateSpecificity(left->item, right->item);
+            if(specificityDiff)
+                return specificityDiff;
         }
 
         return 0;
@@ -988,6 +1145,22 @@ namespace Slang
         sb << val->ToString();
     }
 
+    static void formatDeclName(StringBuilder& sb, Decl* decl)
+    {
+        if(as<ConstructorDecl>(decl))
+        {
+            sb << "init";
+        }
+        else if(as<SubscriptDecl>(decl))
+        {
+            sb << "subscript";
+        }
+        else
+        {
+            sb << getText(decl->getName());
+        }
+    }
+
     void SemanticsVisitor::formatDeclPath(StringBuilder& sb, DeclRef<Decl> declRef)
     {
         // Find the parent declaration
@@ -1008,7 +1181,7 @@ namespace Slang
             sb << ".";
         }
 
-        sb << getText(declRef.GetName());
+        formatDeclName(sb, declRef.getDecl());
 
         // If the parent declaration is a generic, then we need to print out its
         // signature
@@ -1018,10 +1191,29 @@ namespace Slang
             SLANG_RELEASE_ASSERT(genSubst);
             SLANG_RELEASE_ASSERT(genSubst->genericDecl == parentGenericDeclRef.getDecl());
 
+            // If the name we printed previously was an operator
+            // that ends with `<`, then immediately printing the
+            // generic arguments inside `<...>` may cause it to
+            // be hard to parse the operator name visually.
+            //
+            // We thus include a space between the declaration name
+            // and its generic arguments in this case.
+            //
+            if(sb.endsWith("<")) sb << " ";
+
             sb << "<";
             bool first = true;
             for(auto arg : genSubst->args)
             {
+                // When printing the representation of a sepcialized
+                // generic declaration we don't want to include the
+                // argument values for subtype witnesses since these
+                // do not correspond to parameters of the generic
+                // as the user sees it.
+                //
+                if(as<Witness>(arg))
+                    continue;
+
                 if(!first) sb << ", ";
                 formatVal(sb, arg);
                 first = false;
@@ -1085,10 +1277,31 @@ namespace Slang
         }
     }
 
+    static void formatDeclKindPrefix(StringBuilder& sb, Decl* decl)
+    {
+        if(as<FuncDecl>(decl))
+        {
+            sb << "func ";
+        }
+    }
+
+    void SemanticsVisitor::formatDeclResultType(StringBuilder& sb, DeclRef<Decl> const& declRef)
+    {
+        if(as<ConstructorDecl>(declRef))
+        {}
+        else if(auto callableDeclRef = declRef.as<CallableDecl>())
+        {
+            sb << " -> ";
+            formatType(sb, GetResultType(callableDeclRef));
+        }
+    }
+
     void SemanticsVisitor::formatDeclSignature(StringBuilder& sb, DeclRef<Decl> declRef)
     {
+        formatDeclKindPrefix(sb, declRef.getDecl());
         formatDeclPath(sb, declRef);
         formatDeclParams(sb, declRef);
+        formatDeclResultType(sb, declRef);
     }
 
     String SemanticsVisitor::getDeclSignatureString(DeclRef<Decl> declRef)