Title: [247549] trunk/Source/WebCore
- Revision
- 247549
- Author
- rmoris...@apple.com
- Date
- 2019-07-17 17:36:39 -0700 (Wed, 17 Jul 2019)
Log Message
[WHLSL] checkRecursiveType should not have exponential complexity.
https://bugs.webkit.org/show_bug.cgi?id=199835
Reviewed by Myles Maxfield.
The change is very similar to that in https://bugs.webkit.org/show_bug.cgi?id=199688.
Just keep track of which types have already been visited, and don't visit them again.
No new tests as there is no intended functional change.
* Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:
(WebCore::WHLSL::RecursiveTypeChecker::visit):
(WebCore::WHLSL::checkRecursiveTypes):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (247548 => 247549)
--- trunk/Source/WebCore/ChangeLog 2019-07-18 00:17:51 UTC (rev 247548)
+++ trunk/Source/WebCore/ChangeLog 2019-07-18 00:36:39 UTC (rev 247549)
@@ -1,3 +1,19 @@
+2019-07-17 Robin Morisset <rmoris...@apple.com>
+
+ [WHLSL] checkRecursiveType should not have exponential complexity.
+ https://bugs.webkit.org/show_bug.cgi?id=199835
+
+ Reviewed by Myles Maxfield.
+
+ The change is very similar to that in https://bugs.webkit.org/show_bug.cgi?id=199688.
+ Just keep track of which types have already been visited, and don't visit them again.
+
+ No new tests as there is no intended functional change.
+
+ * Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp:
+ (WebCore::WHLSL::RecursiveTypeChecker::visit):
+ (WebCore::WHLSL::checkRecursiveTypes):
+
2019-07-17 Carlos Eduardo Ramalho <cadubent...@gmail.com>
Add missing #include's
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp (247548 => 247549)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp 2019-07-18 00:17:51 UTC (rev 247548)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp 2019-07-18 00:36:39 UTC (rev 247549)
@@ -28,7 +28,6 @@
#if ENABLE(WEBGPU)
-#include "WHLSLScopedSetAdder.h"
#include "WHLSLStructureDefinition.h"
#include "WHLSLTypeDefinition.h"
#include "WHLSLTypeReference.h"
@@ -41,8 +40,6 @@
class RecursiveTypeChecker : public Visitor {
public:
- virtual ~RecursiveTypeChecker() = default;
-
void visit(AST::TypeDefinition&) override;
void visit(AST::StructureDefinition&) override;
void visit(AST::TypeReference&) override;
@@ -49,44 +46,55 @@
void visit(AST::ReferenceType&) override;
private:
- using Adder = ScopedSetAdder<AST::Type*>;
- HashSet<AST::Type*> m_types;
+ HashSet<AST::Type*> m_startedVisiting;
+ HashSet<AST::Type*> m_finishedVisiting;
};
+#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);
+
void RecursiveTypeChecker::visit(AST::TypeDefinition& typeDefinition)
{
- Adder adder(m_types, &typeDefinition);
- if (!adder.isNewEntry()) {
- setError();
- return;
- }
+ START_VISITING(&typeDefinition);
Visitor::visit(typeDefinition);
+
+ END_VISITING(&typeDefinition);
}
void RecursiveTypeChecker::visit(AST::StructureDefinition& structureDefinition)
{
- Adder adder(m_types, &structureDefinition);
- if (!adder.isNewEntry()) {
- setError();
- return;
- }
+ START_VISITING(&structureDefinition);
Visitor::visit(structureDefinition);
+
+ END_VISITING(&structureDefinition);
}
void RecursiveTypeChecker::visit(AST::TypeReference& typeReference)
{
- Adder adder(m_types, &typeReference);
- if (!adder.isNewEntry()) {
- setError();
- return;
- }
+ START_VISITING(&typeReference);
for (auto& typeArgument : typeReference.typeArguments())
checkErrorAndVisit(typeArgument);
if (typeReference.maybeResolvedType()) // FIXME: https://bugs.webkit.org/show_bug.cgi?id=198161 Shouldn't we know by now whether the type has been resolved or not?
checkErrorAndVisit(typeReference.resolvedType());
+
+ END_VISITING(&typeReference);
}
void RecursiveTypeChecker::visit(AST::ReferenceType&)
@@ -96,7 +104,10 @@
bool checkRecursiveTypes(Program& program)
{
RecursiveTypeChecker recursiveTypeChecker;
- recursiveTypeChecker.checkErrorAndVisit(program);
+ for (auto& typeDefinition : program.typeDefinitions())
+ recursiveTypeChecker.checkErrorAndVisit(typeDefinition);
+ for (auto& structureDefinition : program.structureDefinitions())
+ recursiveTypeChecker.checkErrorAndVisit(structureDefinition);
return !recursiveTypeChecker.error();
}
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
