[4.0] Implement version 400 function-overloading disambiguation algorithm

[johnkslang]

Currently, only the pre-version 400 function-overloading algorithm is present. Version 400 and above should be using the second-generation algorithm.

[johnkslang]

FYI, this is specified in section 6.1 of GLSL as the following, and I know it is possible to implement this as a two-pass linear algorithm across the set of choices.

When function calls are resolved, an exact type match for all the arguments is sought. If an exact match is found, all other functions are ignored, and the exact match is used. If no exact match is found, then the implicit conversions in section 4.1.10 “Implicit Conversions” will be applied to find a match. Mismatched types on input parameters (in or inout or default) must have a conversion from the calling argument type to the formal parameter type. Mismatched types on output parameters (out or inout) must have a conversion from the formal parameter type to the calling argument type.

If implicit conversions can be used to find more than one matching function, a single best-matching
function is sought. To determine a best match, the conversions between calling argument and formal
parameter types are compared for each function argument and pair of matching functions. After these comparisons are performed, each pair of matching functions are compared. A function declaration A is considered a better match than function declaration B if

• for at least one function argument, the conversion for that argument in A is better than the
  corresponding conversion in B; and
• there is no function argument for which the conversion in B is better than the corresponding
  conversion in A.

If a single function declaration is considered a better match than every other matching function
declaration, it will be used. Otherwise, a compile-time semantic error for an ambiguous overloaded
function call occurs.

To determine whether the conversion for a single argument in one match is better than that for another match, the following rules are applied, in order:

1. An exact match is better than a match involving any implicit conversion.
2. A match involving an implicit conversion from float to double is better than a match involving any other implicit conversion.
3. A match involving an implicit conversion from either int or uint to float is better than a match involving an implicit conversion from either int or uint to double.

If none of the rules above apply to a particular pair of conversions, neither conversion is considered better than the other.

[johnkslang]

Here is a high-level design for a generic selector, which I believe can be used by both GLSL and HLSL, and probably other more C++-like languages too.

Generic Selector

This would live in place usable by multiple languages, e.g. ParseContextBase, or just on it's own, taking a parse context or symbol table as needed to operate.

Assumptions

• There is no exact match, so a selection algorithm needs to run. That is, the language-specific handler should should check for exact match first, to decide what to do, before calling this selector.

Input

• list of candidate signatures to select from
• list of calling argument types, and whether they are in, out, or both
• a predicate function convertible(A, B) that says whether or not type A can implicitly convert to type B (it includes the case of what the calling language would consider a matching type with no conversion needed)
• a predicate function better(A, B1, B2) that says whether or not a conversion from A -> B2 is considered better than a conversion from A -> B1

Output

• best matching candidate (or none, if no viable candidates found)
• whether there was a tie for the best match (ambiguous overload selection, caller's choice for how to report)

Operation

1. Prune the input list of candidates down to a list of viable candidates, where each viable candidate has
   • at least as many parameters as there are calling arguments, with any remainding parameters being optional or having default values
   • each parameter is true under convertible(A, B), where A is the calling type for in and B is the formal type, and in addition, for out B is the calling type and A is the formal type
2. If there are no viable candidates, return with no match.
3. If there is only one viable candidate, it is the best match.
4. If there are multiple viable candidates, select the first viable candidate as the incumbent. Compare the incumbent to the next viable candidate, and if that candidate is better (bullets below), make it the incumbent. Repeat, with a linear walk through the viable candidate list. The final incumbent will be returned as the best match. A viable candidate is better than the incumbent if
   • it has a function argument with a better(...) conversion than the incumbent, for all directions needed by in and out
   • the incumbent has no argument with a better(...) conversion then the candidate, for either in or out (as needed)
5. Check for ambiguity by comparing the best match against all other viable candidates. If any other viable candidate has a function argument with a better(...) conversion than the best candidate (for either in or out directions), return that there was a tie for best.

Note there were three linear passes to find the best.

GLSL

• use a convertible() predicate that reflects the GLSL conversion DAG of int -> uint -> float -> double, and requires matching scalar/vector sizes, matching array sizes, structs, etc.
• use a better() predicate that is basically "float to double" beats others, and "uint/int to float" beats "uint/int to double"

HLSL

• use a convertible() predicate that allows all bool/int/uint/float/double conversions, as well as scalar -> vector under smearing and big-vector -> small-vector under truncation
• use a better() predicate that says int <-> uint and float -> double (basic-type promotion) beats everything, int/uint -> float beats int/uint -> double (basic-type conversion beats conversion + promotion), keeping vector/scalar shape the same beats smearing/truncating; generally, shorter promotion/conversion chain beats longer conversion chain

[dankbaker]

I think this will work for HLSL, I suspect the right thing to do will be take the function which has the minimum best of each individual argument rather then the sum of them, but that's just a guess.

I think it's fine for SVSL (Spir-V Shading Language) to issue an ambiguous error in cases where HLSL would have picked one. It's pretty easy to add some explicit casts to fix those cases, and it's probably whacky code anyway.

[johnkslang]

@dneto0 Have any (or know where to get some) input on how well this generalizes to C++ rules?

[dneto0]

I haven't worked on a C++ front end, but a good reference would be
http://en.cppreference.com/w/cpp/language/overload_resolution

See the section "Best viable function", especially paragraph 2 beginning with "F1 is determined to be a better funtion than F2...". That rule looks very similar in spirit to the GLSL rules stated above, by checking for one better argument and no argument being worse. So at first blush your algorithm looks like a good framework.

The next place I'd look after that is the C++ standard itself.

[johnkslang]

Thanks @dneto0, I analyzed/compared with this result:

• it is the same, once subsetted to what exists in the shading languages
• they call "viable candidate" what I called "candidate", I updated to match this terminology
• for the better predicate, got the generalization that conversion can be looked at as multiple steps (e.g., in HLSL, int -> double4 is conversion+promotion+smear) and then a shorter such chain beats a longer chain

Generally, for all languages better works as

• basic-type promotion is better than basic-type conversion
• shorter chains of promotion/conversion beat longer chains (it's only HLSL though that includes shape changing in the chain)

[johnkslang]

it is the same

Actually, I should say my algorithm would get the correct result for C++, as neither C++ nor GLSL are giving an algorithm, but rather a description of what is correct. The descriptions are O(V^2), for V being number of viable candidates, whereas the algorithm I'm proposing is O(C), for C being number of candidates.

[johnkslang]

This is implemented for the generic selector and the GLSL #version 400 predicates in https://github.com/KhronosGroup/glslang/tree/overloaded-400 (last commit there) if anyone wants to check it out or comment. Will pull into master in a few days.

[johnkslang]

This is completed with commit fcc0aa3.