Bug 199726 – [WHLSL] Desugar for loops and while loops

• Component: WebGPU
• Status: RESOLVED WONTFIX

[Robin Morisset]

There are a few rules in the spec that we can use to simplify our handling of for and while loops:
  for (X ; e1 ; e2) s -> { X; for (; e1 ; e2) s }
  for (; ; e2) s -> for (; true ; e2) s
  for (; e1 ;) s -> for (; e1 ; null) s
  for (;;) s -> for(; true ; null) s
  while (e) s -> for (; e ;) s
This can let us remove while loops altogether, as well as massively simplify the handling of for loops.

Relatedly, I realize while looking at this that the name resolver creates new name contexts for branches and loops.
This is unnecessary: the spec is such that the only place where we need new name contexts is when dealing with blocks.
In practice it won't change anything, since the only way that a variable declaration can happen is when contained in a block (so "if (foo()) x = 42;" is invalid)

[Robin Morisset]

Created attachment 373983 [details]
Patch

Sorry for the mess that is this patch, it really should have been 3 different patches, but I accidentally completely mingled them.
It is thankfully still pretty small, and the parts are related (desugaring loops, no longer treating loops/branches as new scopes, fixing a checker bug that was revealed by the for-loop-desugaring).

[Myles C. Maxfield]

Comment on attachment 373983 [details]
Patch

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

> Source/WebCore/ChangeLog:8
> +        This patch makes loops behave a lot more similarly to the spec.

Is there a behavior change or a performance change? Is it easier to hack on them if they are closer? Is it easier to have confidence that our implementation matches the spec? What is the purpose of this change?

> Source/WebCore/ChangeLog:11
> +        by putting any initializer in a block around the loop, putting true in the condition if there is none, and putting any litteral in the increment if there is none.

And nothing happens with do-while loops, I guess?

> Source/WebCore/ChangeLog:14
> +        Debugging this patch revealed an unrelated bug in the Checker where it crashed on CommaExpressions of length 0, and the parser uses those for bare ;.
> +        So I also added a small fix for this.

This is a little scary. I wouldn't expect this to work. How do you type check an empty comma expression? We type check from the leaves up to the root, but an empty comma expression would be a leaf with no type. It seems to me like having an empty comma expression should remain an error.

> Source/WebCore/ChangeLog:18
> +        Finally, while updating the NameResolver for the new structure of loops I realized that it was needlessly generating extra NameContext.
> +        They are not expected by the spec, that forbids naked variable declarations outside of blocks anyway.
> +        So I removed this unnecessary work, and fixed the parser to correctly forbid such naked variable declarations.

Is this tested?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1200
> +    auto increment = makeUniqueRef<AST::BooleanLiteral>(*origin, true); // FIXME: NullLiteral would make more sense, but is buggy right now. Anything side-effect free is fine.

Is it buggy?

Instead of dumping unnecessary expressions in the for loop, why don't we just make the increment nullable? Dumping a "true" in there seems worse.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1260
> +auto Parser::parseStatement(bool allowVariableDeclarations) -> Expected<UniqueRef<AST::Statement>, Error>

I don't see this ever called with allowVariableDeclarations set to "true". Does it need to exist?

[Robin Morisset]

Comment on attachment 373983 [details]
Patch

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

>> Source/WebCore/ChangeLog:8
>> +        This patch makes loops behave a lot more similarly to the spec.
> 
> Is there a behavior change or a performance change? Is it easier to hack on them if they are closer? Is it easier to have confidence that our implementation matches the spec? What is the purpose of this change?

It mostly increases confidence that our implementation matches the spec. It also makes the implementation simpler, and should have a tiny performance win.

>> Source/WebCore/ChangeLog:11
>> +        by putting any initializer in a block around the loop, putting true in the condition if there is none, and putting any litteral in the increment if there is none.
> 
> And nothing happens with do-while loops, I guess?

Right, do-while loops are not desugarable to for loops.

>> Source/WebCore/ChangeLog:14
>> +        So I also added a small fix for this.
> 
> This is a little scary. I wouldn't expect this to work. How do you type check an empty comma expression? We type check from the leaves up to the root, but an empty comma expression would be a leaf with no type. It seems to me like having an empty comma expression should remain an error.

I simply type check them to type void. I've since realized that I can keep empty comma expressions an error, and instead make ";" generate an empty block. It is both closer to spec, and more obviously correct. I will do this change.

>> Source/WebCore/ChangeLog:18
>> +        So I removed this unnecessary work, and fixed the parser to correctly forbid such naked variable declarations.
> 
> Is this tested?

Yes, I verified it does not break any test, but you are right that I should also add a test that naked variable declarations are properly rejected. Will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1200
>> +    auto increment = makeUniqueRef<AST::BooleanLiteral>(*origin, true); // FIXME: NullLiteral would make more sense, but is buggy right now. Anything side-effect free is fine.
> 
> Is it buggy?
> 
> Instead of dumping unnecessary expressions in the for loop, why don't we just make the increment nullable? Dumping a "true" in there seems worse.

NullLiteral is currently buggy yes. It should be fixed, but this patch is already big enough.

Keeping the increment nullable would work, but it means an extra null check everywhere we touch the loop, and nasty bugs if we forget it anywhere. Making both the increment and the condition non-nullable is just a simplification.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1260
>> +auto Parser::parseStatement(bool allowVariableDeclarations) -> Expected<UniqueRef<AST::Statement>, Error>
> 
> I don't see this ever called with allowVariableDeclarations set to "true". Does it need to exist?

It is used in parseBlockBody (see line 1066).

[Robin Morisset]

Created attachment 374159 [details]
Patch

I've added back a test that parser correctly rejects lone variable declarations.
I've also changed the fix of bare ";", so that the parser now generates an empty block, as per the spec.

[Myles C. Maxfield]

Comment on attachment 373983 [details]
Patch

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

>>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1200
>>> +    auto increment = makeUniqueRef<AST::BooleanLiteral>(*origin, true); // FIXME: NullLiteral would make more sense, but is buggy right now. Anything side-effect free is fine.
>> 
>> Is it buggy?
>> 
>> Instead of dumping unnecessary expressions in the for loop, why don't we just make the increment nullable? Dumping a "true" in there seems worse.
> 
> NullLiteral is currently buggy yes. It should be fixed, but this patch is already big enough.
> 
> Keeping the increment nullable would work, but it means an extra null check everywhere we touch the loop, and nasty bugs if we forget it anywhere. Making both the increment and the condition non-nullable is just a simplification.

WebKit usually uses the style that all pointers are nullable, which means all pointers mechanically have to go through null checks whenever they're used. Therefore, forgetting the null checks should be obvious and clearly wrong.

I actually think that sticking in a "true" makes the code less simple, rather than more simple. It's unclear where that true came from and what it means. Debugging the "true" is more difficult than debugging a null pointer.

[Robin Morisset]

(In reply to Myles C. Maxfield from comment #5)
> Comment on attachment 373983 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=373983&action=review
> 
> >>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp:1200
> >>> +    auto increment = makeUniqueRef<AST::BooleanLiteral>(*origin, true); // FIXME: NullLiteral would make more sense, but is buggy right now. Anything side-effect free is fine.
> >> 
> >> Is it buggy?
> >> 
> >> Instead of dumping unnecessary expressions in the for loop, why don't we just make the increment nullable? Dumping a "true" in there seems worse.
> > 
> > NullLiteral is currently buggy yes. It should be fixed, but this patch is already big enough.
> > 
> > Keeping the increment nullable would work, but it means an extra null check everywhere we touch the loop, and nasty bugs if we forget it anywhere. Making both the increment and the condition non-nullable is just a simplification.
> 
> WebKit usually uses the style that all pointers are nullable, which means
> all pointers mechanically have to go through null checks whenever they're
> used. Therefore, forgetting the null checks should be obvious and clearly
> wrong.
> 
> I actually think that sticking in a "true" makes the code less simple,
> rather than more simple. It's unclear where that true came from and what it
> means. Debugging the "true" is more difficult than debugging a null pointer.

I agree that debugging missing null pointer checks should be fairly easy. But with putting a constant in there still seems even simpler. More importantly, it keeps the compiler in sync with the spec, and doing it the other way (making the increment optional in the spec) would be significantly more work, and I would risk missing cases.

[WebKit Commit Bot]

Comment on attachment 374159 [details]
Patch

Clearing flags on attachment: 374159

Committed r247493: <https://trac.webkit.org/changeset/247493>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/53168644>

[Robin Morisset]

*** Bug 198445 has been marked as a duplicate of this bug. ***

[Truitt Savell]

The new test webgpu/whlsl-for-loop.html

added in https://trac.webkit.org/changeset/247493/webkit

began failing on Mojave.

History:
https://webkit-test-results.webkit.org/dashboards/flakiness_dashboard.html#showAllRuns=true&tests=webgpu%2Fwhlsl-for-loop.html

Diff:
--- /Volumes/Data/slave/mojave-release-tests-wk2/build/layout-test-results/webgpu/whlsl-for-loop-expected.txt
+++ /Volumes/Data/slave/mojave-release-tests-wk2/build/layout-test-results/webgpu/whlsl-for-loop-actual.txt
@@ -1,3 +1,3 @@
 
-PASS forLoop 
+FAIL forLoop assert_equals: expected 3 but got 0

[WebKit Commit Bot]

Re-opened since this is blocked by bug 199841

[Myles C. Maxfield]

WHLSL is no longer relevant.