Bug 176333 – WSL overload resolution should not be cascading

• Component: WebGPU
• Status: RESOLVED FIXED

[Filip Pizlo]

Currently WSL resolves overloads by just proceeding through signatures in order, and returning the first one that matches.  That's pretty weird.  For example, it means that if someone uses #include as a mechanism of modularity, then the order in which things are included will determine what gets called.  This is in contrast to C++, which has fairly deterministic overload resolution rules that will often report overload ambiguity errors in cases where things would have gotten weird.  Also, regardless of what you think of cascading overload resolution versus C++ overload resolution, it is a goal of WSL to be similar to C++.  So, this implies having some deterministic rules like C++ does.

I propose the following.  When there are N matches where N is greater than 1, they are ranked according to how they used inferred type variables.  Those are type variables that were not defined by type arguments to the call.  The math for this will be done using rational numbers with bignum numerators and denominators for maximum determinism.  The ranking formula gives each parameter a point.  If the parameter does not mention any inferred type variables, it gets one point.  If it is nothing more than just a reference to a type variable and the type variable has no protocol, then it gets zero points.  In general, we give it points recursively, so that you get more than zero points if the type variable is mentioned in some context like T^ or Foo<T>.  For example:

    points(ptrType) = points(ptrType.elementType) * 3/4 + 1/4;

For type variables, we give 1/3 point if it mentions a protocol, and zero points otherwise.

This enables us to do overload resolution in obvious cases:

void foo(int); // Obviously more specific!
void foo<T>(T);

And give errors in cases that feel like they should get errors:

void foo<T>(int, T);
void foo<T>(T, int);

Cases that are more specific by having a more specific protocol will be resolved unambiguously:

void foo<T:numeric>(T); // More specific!
void foo<T>(T);

But we will give errors if things get any weirder:

void foo<T:numeric>(T);
void foo<T:primitive>(T);

This will be an error even though numeric is a more specific protocol than primitive. I think that's the right call just because if we make it any more complicated, then we make our lives a lot harder with probably not a whole lot of benefit for anybody.  I think that a lot of users would expect an error here.

[Filip Pizlo]

Oh and another thing: if you pass IntLiteral, then it should create one more point for itself, which is either 0 or 1 depending on whether it matches an actual int32.

This means that if we pass the literal 0 to:

void foo(int);
void foo(uint);

Then it will match the int.

But if you pass 0 to:

void foo(uint);
void foo(double);

Then you'll get an error.

[Filip Pizlo]

Actually, I really like the C++ approach, which as I understand it is checking if there is a signature whose types would be accepted by all other signatures but not the other way around.

[Filip Pizlo]

Created attachment 320202 [details]
the patch

[Filip Pizlo]

Created attachment 320223 [details]
work in progress

[Filip Pizlo]

Created attachment 320226 [details]
the patch

[Myles C. Maxfield]

Comment on attachment 320226 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=320226&action=review

Why no tests?

> Tools/WebGPUShadingLanguageRI/CallExpression.js:56
> +    becomeCast(returnType)

But isn't there still a CastExpression class? It doesn't look like you deleted it

> Tools/WebGPUShadingLanguageRI/Lexer.js:107
> +            if (/^(struct|protocol|typedef|if|else|enum|continue|break|switch|case|default|for|while|do|return|constant|device|threadgroup|thread|operator|null|true|false)$/.test(RegExp.lastMatch))

Doesn't this set RegExp.lastMatch? Why doesn't this break things?

> Tools/WebGPUShadingLanguageRI/NameResolver.js:121
> +            node.becomeCast(type);

But you don't know what |type| is! Won't this break if malformed content is provided?

> Tools/WebGPUShadingLanguageRI/Node.js:-32
> -        let memoTable = visitor._memoTable;
> -        if (memoTable.has(this))
> -            return memoTable.get(this);

👍

> Tools/WebGPUShadingLanguageRI/Test.js:100
>  

No new tests?

[Filip Pizlo]

(In reply to Myles C. Maxfield from comment #6)
> Comment on attachment 320226 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=320226&action=review
> 
> Why no tests?

The hard parts are handled by existing overload resolution scenarios.  Most of the code in this patch was for making TEST_doubleNot happy.

But, I added some new tests.

> 
> > Tools/WebGPUShadingLanguageRI/CallExpression.js:56
> > +    becomeCast(returnType)
> 
> But isn't there still a CastExpression class? It doesn't look like you
> deleted it

I meant to delete it.  I did remove it from All.js.  I fixed that locally.

> 
> > Tools/WebGPUShadingLanguageRI/Lexer.js:107
> > +            if (/^(struct|protocol|typedef|if|else|enum|continue|break|switch|case|default|for|while|do|return|constant|device|threadgroup|thread|operator|null|true|false)$/.test(RegExp.lastMatch))
> 
> Doesn't this set RegExp.lastMatch? Why doesn't this break things?

I think that lastMatch is set if there is a match.  If there isn't a match, it's not set, and we're OK.

> 
> > Tools/WebGPUShadingLanguageRI/NameResolver.js:121
> > +            node.becomeCast(type);
> 
> But you don't know what |type| is! Won't this break if malformed content is
> provided?

NameResolver just needs to know that there is a type by that name.  It knows this at this point.

Note that becomeCast turns this into a TypeRef that incorporates the CallExpression's type arguments.  Later, Checker will give you an error if that TypeRef is invalid for any reason.

> 
> > Tools/WebGPUShadingLanguageRI/Node.js:-32
> > -        let memoTable = visitor._memoTable;
> > -        if (memoTable.has(this))
> > -            return memoTable.get(this);
> 
> 👍
> 
> > Tools/WebGPUShadingLanguageRI/Test.js:100
> >  
> 
> No new tests?

[Filip Pizlo]

Created attachment 320327 [details]
the patch

Add more tests, address other feedback.

[Filip Pizlo]

Created attachment 320330 [details]
the patch

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/221837/webkit

[Radar WebKit Bug Importer]

<rdar://problem/34694207>

[Myles C. Maxfield]

Migrated to https://github.com/gpuweb/WHLSL/issues/153