Consider the case where you have: typedef A1 = X1; typedef A2 = X1; ... typedef An = X1; typedef X1 = X2; typedef X2 = X3; typedef X3 = X4; ... typedef XnMinusOne = Xn; typedef Xn = int; Currently we will go n times through the entire chain X1 -> X2 -> ... -> Xn -> int So our total runtime will be in n^2, while the program size is only proportional to n. This is easy to fix, just do a proper DFS, not revisiting parts of the graph we've already explored. Note: this is basically the same problem, and the same solution, as https://bugs.webkit.org/show_bug.cgi?id=199688.
Created attachment 374240 [details] Patch
Attachment 374240 [details] did not pass style-queue: ERROR: Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:107: Missing space around : in range-based for statement [whitespace/colon] [4] ERROR: Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:109: Missing space around : in range-based for statement [whitespace/colon] [4] Total errors found: 2 in 2 files If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 374246 [details] Patch
Attachment 374246 [details] did not pass style-queue: ERROR: Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:107: Missing space around : in range-based for statement [whitespace/colon] [4] ERROR: Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:109: Missing space around : in range-based for statement [whitespace/colon] [4] Total errors found: 2 in 2 files If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 374246 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=374246&action=review > Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:68 > +#define START_VISITING(t) \ > +do { \ > + if (m_finishedVisiting.contains(t)) \ > + return; \ > + auto resultStartedVisiting = m_startedVisiting.add(t); \ > + if (!resultStartedVisiting.isNewEntry) { \ > + setError(); \ > + return; \ > + } \ > +} while (false); > + > +#define END_VISITING(t) \ > +do { \ > + auto resultFinishedVisiting = m_finishedVisiting.add(t); \ > + ASSERT_UNUSED(resultFinishedVisiting, resultFinishedVisiting.isNewEntry); \ > +} while (false); Can we make this general so we can share it with RecursionChecker? And maybe put it in ScopedSetAdder.h? Also, can we use templates instead of preprocessor macros?
Comment on attachment 374246 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=374246&action=review > Source/WebCore/ChangeLog:3 > + [WHLSL] checkRecursiveType should not have quadratic complexity. I think it's exponential, not quadratic
Comment on attachment 374246 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=374246&action=review > Source/WebCore/ChangeLog:8 > + The change is very similar to that in https://bugs.webkit.org/show_bug.cgi?id=199698. I don't think this is the right URL
As noted by Myles, the worst case is actually exponential: struct A1 { A2 x; A2 y; } struct A2 { A3 x; A3 y; } ... struct AnMinusOne { An x; An y; } typedef An = int; would traverse An 2^n times.
(In reply to Myles C. Maxfield from comment #7) > Comment on attachment 374246 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=374246&action=review > > > Source/WebCore/ChangeLog:8 > > + The change is very similar to that in https://bugs.webkit.org/show_bug.cgi?id=199698. > > I don't think this is the right URL Thanks, the right URL is actually https://bugs.webkit.org/show_bug.cgi?id=199688. I will fix the Changelog.
Created attachment 374253 [details] Patch
(In reply to Myles C. Maxfield from comment #5) > Comment on attachment 374246 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=374246&action=review > > > Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:68 > > +#define START_VISITING(t) \ > > +do { \ > > + if (m_finishedVisiting.contains(t)) \ > > + return; \ > > + auto resultStartedVisiting = m_startedVisiting.add(t); \ > > + if (!resultStartedVisiting.isNewEntry) { \ > > + setError(); \ > > + return; \ > > + } \ > > +} while (false); > > + > > +#define END_VISITING(t) \ > > +do { \ > > + auto resultFinishedVisiting = m_finishedVisiting.add(t); \ > > + ASSERT_UNUSED(resultFinishedVisiting, resultFinishedVisiting.isNewEntry); \ > > +} while (false); > > Can we make this general so we can share it with RecursionChecker? And maybe > put it in ScopedSetAdder.h? > > Also, can we use templates instead of preprocessor macros? It is not obvious how to make it both clean and not use preprocessor macros because it needs to be able to return early. One option would be to make it a higher-order function that takes a lambda that would contain the actual body of the function. I thought it was more effort than it was worth (and likely even less readable than macros), but I can do the change. What do you think should be done? This, something else, or just keep the macros?
Comment on attachment 374253 [details] Patch Myles said ok offline to landing this patch.
The commit-queue encountered the following flaky tests while processing attachment 374253 [details]: http/tests/IndexedDB/collect-IDB-objects.https.html bug 199881 (author: youennf@gmail.com) The commit-queue is continuing to process your patch.
The commit-queue encountered the following flaky tests while processing attachment 374253 [details]: The commit-queue is continuing to process your patch.
Comment on attachment 374253 [details] Patch Rejecting attachment 374253 [details] from commit-queue. New failing tests: storage/indexeddb/dont-wedge.html Full output: https://webkit-queues.webkit.org/results/12760805
Created attachment 374329 [details] Archive of layout-test-results from webkit-cq-01 for mac-highsierra The attached test failures were seen while running run-webkit-tests on the commit-queue. Bot: webkit-cq-01 Port: mac-highsierra Platform: Mac OS X 10.13.6
Comment on attachment 374253 [details] Patch Let's try again, I don't see how I can have caused a bug in IndexedDB.
Comment on attachment 374253 [details] Patch Clearing flags on attachment: 374253 Committed r247549: <https://trac.webkit.org/changeset/247549>
All reviewed patches have been landed. Closing bug.
<rdar://problem/53230131>
This broke my build: In file included from /Volumes/Data/Development/system/webkit/OpenSource/WebKitBuild/Release-iphoneos/DerivedSources/WebCore/unified-sources/UnifiedSource164.cpp:1: ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:107:40: error: member access into incomplete type 'WebCore::WHLSL::Program' for (auto& typeDefinition : program.typeDefinitions()) ^ In file included from /Volumes/Data/Development/system/webkit/OpenSource/WebKitBuild/Release-iphoneos/DerivedSources/WebCore/unified-sources/UnifiedSource164.cpp:1: In file included from ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:27: ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.h:35:7: note: forward declaration of 'WebCore::WHLSL::Program' class Program; ^
Build fix in https://trac.webkit.org/r247553
(In reply to Simon Fraser (smfr) from comment #21) > This broke my build: > > In file included from > /Volumes/Data/Development/system/webkit/OpenSource/WebKitBuild/Release- > iphoneos/DerivedSources/WebCore/unified-sources/UnifiedSource164.cpp:1: > ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:107:40: error: member > access into incomplete type 'WebCore::WHLSL::Program' > for (auto& typeDefinition : program.typeDefinitions()) > ^ > In file included from > /Volumes/Data/Development/system/webkit/OpenSource/WebKitBuild/Release- > iphoneos/DerivedSources/WebCore/unified-sources/UnifiedSource164.cpp:1: > In file included from > ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:27: > ./Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.h:35:7: note: forward > declaration of 'WebCore::WHLSL::Program' > class Program; > ^ Sorry for this mistake, for some reason it worked fine for me and the commit queue. Thank you for the build fix.