[WHLSL] Implement the Type Checker
authormmaxfield@apple.com <mmaxfield@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Jan 2019 06:01:44 +0000 (06:01 +0000)
committermmaxfield@apple.com <mmaxfield@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Jan 2019 06:01:44 +0000 (06:01 +0000)
https://bugs.webkit.org/show_bug.cgi?id=193080

Reviewed by Dean Jackson.

This is a translation of https://github.com/gpuweb/WHLSL/blob/master/Source/Checker.mjs into C++.

The Checker passes types between nested expressions. An inner expression figures out what type it is, and
passes that information up to an outer expression. This is done via reading/writing into a HashMap,
because all the type information needs to be saved so that the Metal codegen can emit the correct types.

These types can have two forms: A regular type (like "int[]") or a ResolvableType. ResolvableTypes
represent literals, since a literal needs to know its context before it knows what type it should be. So,
if you have a function like "void foo(int x)" and you have a call like "foo(3)", the 3's ResolvableType
gets passed to the CallExpression, which then unifies it with the function's parameter type, thereby
resolving the 3 to be an int.

There are a few examples where multiple expressions will have the same type: "return (foo, 3)." If those
types are regular types, then it's no problem; we can just clone() the type and stick both in the HashMap.
However, if the type is a ResolvableType, an outer expression will only resolve that type once, so the two
ResolvableTypes can't be distinct. The Checker solves this problem by making a reference-counted wrapper
around ResolvableTypes and using that in the HashMap instead.

Once all the ResolvableTypes have been resolved, a second pass runs through the entire HashMap and assigns
the known types to all the expressions. LValues and their associated address spaces are held in a parallel
HashMap, and are assigned to the expression at the same time. The type is an Optional<AddressSpace> because
address spaces are only relevant if the value is an lvalue; if it's nullopt then that means the expression
is an rvalue.

No new tests because it isn't hooked up yet. Not enough of the compiler exists to have any meaningful sort
of test. When enough of the compiler is present, I'll port the reference implementation's test suite.

* Modules/webgpu/WHLSL/WHLSLChecker.cpp: Added.
(WebCore::WHLSL::resolveWithOperatorAnderIndexer):
(WebCore::WHLSL::resolveWithOperatorLength):
(WebCore::WHLSL::resolveWithReferenceComparator):
(WebCore::WHLSL::resolveByInstantiation):
(WebCore::WHLSL::checkSemantics):
(WebCore::WHLSL::checkOperatorOverload):
(WebCore::WHLSL::Checker::Checker):
(WebCore::WHLSL::Checker::visit):
(WebCore::WHLSL::Checker::assignTypes):
(WebCore::WHLSL::Checker::checkShaderType):
(WebCore::WHLSL::matchAndCommit):
(WebCore::WHLSL::Checker::recurseAndGetInfo):
(WebCore::WHLSL::Checker::getInfo):
(WebCore::WHLSL::Checker::assignType):
(WebCore::WHLSL::Checker::forwardType):
(WebCore::WHLSL::getUnnamedType):
(WebCore::WHLSL::Checker::finishVisitingPropertyAccess):
(WebCore::WHLSL::Checker::recurseAndWrapBaseType):
(WebCore::WHLSL::Checker::isBoolType):
(WebCore::WHLSL::Checker::recurseAndRequireBoolType):
(WebCore::WHLSL::check):
* Modules/webgpu/WHLSL/WHLSLChecker.h: Added.
* Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp: Added.
(WebCore::WHLSL::Gatherer::Gatherer):
(WebCore::WHLSL::Gatherer::reset):
(WebCore::WHLSL::Gatherer::takeEntryPointItems):
(WebCore::WHLSL::Gatherer::visit):
(WebCore::WHLSL::gatherEntryPointItems):
* Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.h: Added.
(WebCore::WHLSL::EntryPointItem::EntryPointItem):
* Sources.txt:
* WebCore.xcodeproj/project.pbxproj:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@239975 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.cpp [new file with mode: 0644]
Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.h [new file with mode: 0644]
Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp [new file with mode: 0644]
Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.h [new file with mode: 0644]
Source/WebCore/Sources.txt
Source/WebCore/WebCore.xcodeproj/project.pbxproj

index b0e3929..ad82af5 100644 (file)
@@ -1,3 +1,71 @@
+2019-01-14  Myles C. Maxfield  <mmaxfield@apple.com>
+
+        [WHLSL] Implement the Type Checker
+        https://bugs.webkit.org/show_bug.cgi?id=193080
+
+        Reviewed by Dean Jackson.
+
+        This is a translation of https://github.com/gpuweb/WHLSL/blob/master/Source/Checker.mjs into C++.
+
+        The Checker passes types between nested expressions. An inner expression figures out what type it is, and
+        passes that information up to an outer expression. This is done via reading/writing into a HashMap,
+        because all the type information needs to be saved so that the Metal codegen can emit the correct types.
+
+        These types can have two forms: A regular type (like "int[]") or a ResolvableType. ResolvableTypes
+        represent literals, since a literal needs to know its context before it knows what type it should be. So,
+        if you have a function like "void foo(int x)" and you have a call like "foo(3)", the 3's ResolvableType
+        gets passed to the CallExpression, which then unifies it with the function's parameter type, thereby
+        resolving the 3 to be an int.
+
+        There are a few examples where multiple expressions will have the same type: "return (foo, 3)." If those
+        types are regular types, then it's no problem; we can just clone() the type and stick both in the HashMap.
+        However, if the type is a ResolvableType, an outer expression will only resolve that type once, so the two
+        ResolvableTypes can't be distinct. The Checker solves this problem by making a reference-counted wrapper
+        around ResolvableTypes and using that in the HashMap instead.
+
+        Once all the ResolvableTypes have been resolved, a second pass runs through the entire HashMap and assigns
+        the known types to all the expressions. LValues and their associated address spaces are held in a parallel
+        HashMap, and are assigned to the expression at the same time. The type is an Optional<AddressSpace> because
+        address spaces are only relevant if the value is an lvalue; if it's nullopt then that means the expression
+        is an rvalue.
+
+        No new tests because it isn't hooked up yet. Not enough of the compiler exists to have any meaningful sort
+        of test. When enough of the compiler is present, I'll port the reference implementation's test suite.
+
+        * Modules/webgpu/WHLSL/WHLSLChecker.cpp: Added.
+        (WebCore::WHLSL::resolveWithOperatorAnderIndexer):
+        (WebCore::WHLSL::resolveWithOperatorLength):
+        (WebCore::WHLSL::resolveWithReferenceComparator):
+        (WebCore::WHLSL::resolveByInstantiation):
+        (WebCore::WHLSL::checkSemantics):
+        (WebCore::WHLSL::checkOperatorOverload):
+        (WebCore::WHLSL::Checker::Checker):
+        (WebCore::WHLSL::Checker::visit):
+        (WebCore::WHLSL::Checker::assignTypes):
+        (WebCore::WHLSL::Checker::checkShaderType):
+        (WebCore::WHLSL::matchAndCommit):
+        (WebCore::WHLSL::Checker::recurseAndGetInfo):
+        (WebCore::WHLSL::Checker::getInfo):
+        (WebCore::WHLSL::Checker::assignType):
+        (WebCore::WHLSL::Checker::forwardType):
+        (WebCore::WHLSL::getUnnamedType):
+        (WebCore::WHLSL::Checker::finishVisitingPropertyAccess):
+        (WebCore::WHLSL::Checker::recurseAndWrapBaseType):
+        (WebCore::WHLSL::Checker::isBoolType):
+        (WebCore::WHLSL::Checker::recurseAndRequireBoolType):
+        (WebCore::WHLSL::check):
+        * Modules/webgpu/WHLSL/WHLSLChecker.h: Added.
+        * Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp: Added.
+        (WebCore::WHLSL::Gatherer::Gatherer):
+        (WebCore::WHLSL::Gatherer::reset):
+        (WebCore::WHLSL::Gatherer::takeEntryPointItems):
+        (WebCore::WHLSL::Gatherer::visit):
+        (WebCore::WHLSL::gatherEntryPointItems):
+        * Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.h: Added.
+        (WebCore::WHLSL::EntryPointItem::EntryPointItem):
+        * Sources.txt:
+        * WebCore.xcodeproj/project.pbxproj:
+
 2019-01-14  Alex Christensen  <achristensen@webkit.org>
 
         Split headerValueForVary into specialized functions for NetworkProcess and WebProcess/WebKitLegacy
diff --git a/Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.cpp b/Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.cpp
new file mode 100644 (file)
index 0000000..9f59089
--- /dev/null
@@ -0,0 +1,1479 @@
+/*
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "WHLSLChecker.h"
+
+#if ENABLE(WEBGPU)
+
+#include "WHLSLArrayReferenceType.h"
+#include "WHLSLArrayType.h"
+#include "WHLSLAssignmentExpression.h"
+#include "WHLSLCallExpression.h"
+#include "WHLSLCommaExpression.h"
+#include "WHLSLDereferenceExpression.h"
+#include "WHLSLDoWhileLoop.h"
+#include "WHLSLDotExpression.h"
+#include "WHLSLForLoop.h"
+#include "WHLSLGatherEntryPointItems.h"
+#include "WHLSLIfStatement.h"
+#include "WHLSLIndexExpression.h"
+#include "WHLSLInferTypes.h"
+#include "WHLSLLogicalExpression.h"
+#include "WHLSLLogicalNotExpression.h"
+#include "WHLSLMakeArrayReferenceExpression.h"
+#include "WHLSLMakePointerExpression.h"
+#include "WHLSLPointerType.h"
+#include "WHLSLProgram.h"
+#include "WHLSLReadModifyWriteExpression.h"
+#include "WHLSLResolvableType.h"
+#include "WHLSLResolveOverloadImpl.h"
+#include "WHLSLResolvingType.h"
+#include "WHLSLReturn.h"
+#include "WHLSLSwitchStatement.h"
+#include "WHLSLTernaryExpression.h"
+#include "WHLSLVisitor.h"
+#include "WHLSLWhileLoop.h"
+#include <wtf/HashMap.h>
+#include <wtf/HashSet.h>
+#include <wtf/Ref.h>
+#include <wtf/Vector.h>
+#include <wtf/text/WTFString.h>
+
+namespace WebCore {
+
+namespace WHLSL {
+
+class PODChecker : public Visitor {
+public:
+    PODChecker() = default;
+
+    virtual ~PODChecker() = default;
+
+    void visit(AST::EnumerationDefinition& enumerationDefinition) override
+    {
+        Visitor::visit(enumerationDefinition);
+    }
+
+    void visit(AST::NativeTypeDeclaration& nativeTypeDeclaration) override
+    {
+        if (!nativeTypeDeclaration.isNumber()
+            && !nativeTypeDeclaration.isVector()
+            && !nativeTypeDeclaration.isMatrix())
+            setError();
+    }
+
+    void visit(AST::StructureDefinition& structureDefinition) override
+    {
+        Visitor::visit(structureDefinition);
+    }
+
+    void visit(AST::TypeDefinition& typeDefinition) override
+    {
+        Visitor::visit(typeDefinition);
+    }
+
+    void visit(AST::ArrayType& arrayType) override
+    {
+        Visitor::visit(arrayType);
+    }
+
+    void visit(AST::PointerType&) override
+    {
+        setError();
+    }
+
+    void visit(AST::ArrayReferenceType&) override
+    {
+        setError();
+    }
+
+    void visit(AST::TypeReference& typeReference) override
+    {
+        ASSERT(typeReference.resolvedType());
+        checkErrorAndVisit(*typeReference.resolvedType());
+    }
+};
+
+static AST::NativeFunctionDeclaration resolveWithOperatorAnderIndexer(AST::CallExpression& callExpression, AST::ArrayReferenceType& firstArgument, const Intrinsics& intrinsics)
+{
+    const bool isRestricted = false;
+    const bool isOperator = true;
+    auto returnType = makeUniqueRef<AST::PointerType>(Lexer::Token(callExpression.origin()), firstArgument.addressSpace(), firstArgument.elementType().clone());
+    AST::VariableDeclarations parameters;
+    parameters.append(AST::VariableDeclaration(Lexer::Token(callExpression.origin()), AST::Qualifiers(), { firstArgument.clone() }, String(), WTF::nullopt, WTF::nullopt));
+    parameters.append(AST::VariableDeclaration(Lexer::Token(callExpression.origin()), AST::Qualifiers(), { AST::TypeReference::wrap(Lexer::Token(callExpression.origin()), intrinsics.uintType()) }, String(), WTF::nullopt, WTF::nullopt));
+    return AST::NativeFunctionDeclaration(AST::FunctionDeclaration(Lexer::Token(callExpression.origin()), AST::AttributeBlock(), WTF::nullopt, WTFMove(returnType), String("operator&[]", String::ConstructFromLiteral), WTFMove(parameters), WTF::nullopt, isOperator), isRestricted);
+}
+
+static AST::NativeFunctionDeclaration resolveWithOperatorLength(AST::CallExpression& callExpression, AST::UnnamedType& firstArgument, const Intrinsics& intrinsics)
+{
+    const bool isRestricted = false;
+    const bool isOperator = true;
+    auto returnType = AST::TypeReference::wrap(Lexer::Token(callExpression.origin()), intrinsics.uintType());
+    AST::VariableDeclarations parameters;
+    parameters.append(AST::VariableDeclaration(Lexer::Token(callExpression.origin()), AST::Qualifiers(), { firstArgument.clone() }, String(), WTF::nullopt, WTF::nullopt));
+    return AST::NativeFunctionDeclaration(AST::FunctionDeclaration(Lexer::Token(callExpression.origin()), AST::AttributeBlock(), WTF::nullopt, WTFMove(returnType), String("operator.length", String::ConstructFromLiteral), WTFMove(parameters), WTF::nullopt, isOperator), isRestricted);
+}
+
+static AST::NativeFunctionDeclaration resolveWithReferenceComparator(AST::CallExpression& callExpression, ResolvingType& firstArgument, ResolvingType& secondArgument, const Intrinsics& intrinsics)
+{
+    const bool isRestricted = false;
+    const bool isOperator = true;
+    auto returnType = AST::TypeReference::wrap(Lexer::Token(callExpression.origin()), intrinsics.boolType());
+    auto argumentType = WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& unnamedType) -> UniqueRef<AST::UnnamedType> {
+        return unnamedType->clone();
+    }, [&](Ref<ResolvableTypeReference>&) -> UniqueRef<AST::UnnamedType> {
+        return WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& unnamedType) -> UniqueRef<AST::UnnamedType> {
+            return unnamedType->clone();
+        }, [&](Ref<ResolvableTypeReference>&) -> UniqueRef<AST::UnnamedType> {
+            // We encountered "null == null".
+            // The type isn't observable, so we can pick whatever we want.
+            // FIXME: This can probably be generalized, using the "preferred type" infrastructure used by generic literals
+            return AST::TypeReference::wrap(Lexer::Token(callExpression.origin()), intrinsics.intType());
+        }), secondArgument);
+    }), firstArgument);
+    AST::VariableDeclarations parameters;
+    parameters.append(AST::VariableDeclaration(Lexer::Token(callExpression.origin()), AST::Qualifiers(), { argumentType->clone() }, String(), WTF::nullopt, WTF::nullopt));
+    parameters.append(AST::VariableDeclaration(Lexer::Token(callExpression.origin()), AST::Qualifiers(), { WTFMove(argumentType) }, String(), WTF::nullopt, WTF::nullopt));
+    return AST::NativeFunctionDeclaration(AST::FunctionDeclaration(Lexer::Token(callExpression.origin()), AST::AttributeBlock(), WTF::nullopt, WTFMove(returnType), String("operator==", String::ConstructFromLiteral), WTFMove(parameters), WTF::nullopt, isOperator), isRestricted);
+}
+
+static Optional<AST::NativeFunctionDeclaration> resolveByInstantiation(AST::CallExpression& callExpression, const Vector<std::reference_wrapper<ResolvingType>>& types, const Intrinsics& intrinsics)
+{
+    if (callExpression.name() == "operator&[]" && types.size() == 2) {
+        auto* firstArgumentArrayRef = WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& unnamedType) -> AST::ArrayReferenceType* {
+            if (is<AST::ArrayReferenceType>(static_cast<AST::UnnamedType&>(unnamedType)))
+                return &downcast<AST::ArrayReferenceType>(static_cast<AST::UnnamedType&>(unnamedType));
+            return nullptr;
+        }, [](Ref<ResolvableTypeReference>&) -> AST::ArrayReferenceType* {
+            return nullptr;
+        }), types[0].get());
+        bool secondArgumentIsUint = WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& unnamedType) -> bool {
+            return matches(unnamedType, intrinsics.uintType());
+        }, [&](Ref<ResolvableTypeReference>& resolvableTypeReference) -> bool {
+            return resolvableTypeReference->resolvableType().canResolve(intrinsics.uintType());
+        }), types[1].get());
+        if (firstArgumentArrayRef && secondArgumentIsUint)
+            return resolveWithOperatorAnderIndexer(callExpression, *firstArgumentArrayRef, intrinsics);
+    } else if (callExpression.name() == "operator.length" && types.size() == 1) {
+        auto* firstArgumentReference = WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& unnamedType) -> AST::UnnamedType* {
+            if (is<AST::ArrayReferenceType>(static_cast<AST::UnnamedType&>(unnamedType)) || is<AST::ArrayType>(static_cast<AST::UnnamedType&>(unnamedType)))
+                return &unnamedType;
+            return nullptr;
+        }, [](Ref<ResolvableTypeReference>&) -> AST::UnnamedType* {
+            return nullptr;
+        }), types[0].get());
+        if (firstArgumentReference)
+            return resolveWithOperatorLength(callExpression, *firstArgumentReference, intrinsics);
+    } else if (callExpression.name() == "operator==" && types.size() == 2) {
+        auto isAcceptable = [](ResolvingType& resolvingType) -> bool {
+            return WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& unnamedType) -> bool {
+                return is<AST::ReferenceType>(static_cast<AST::UnnamedType&>(unnamedType));
+            }, [](Ref<ResolvableTypeReference>& resolvableTypeReference) -> bool {
+                return is<AST::NullLiteralType>(resolvableTypeReference->resolvableType());
+            }), resolvingType);
+        };
+        if (isAcceptable(types[0].get()) && isAcceptable(types[1].get()))
+            return resolveWithReferenceComparator(callExpression, types[0].get(), types[1].get(), intrinsics);
+    }
+    return WTF::nullopt;
+}
+
+static bool checkSemantics(Vector<EntryPointItem>& inputItems, Vector<EntryPointItem>& outputItems, const Optional<AST::EntryPointType>& entryPointType, const Intrinsics& intrinsics)
+{
+    {
+        auto checkDuplicateSemantics = [&](const Vector<EntryPointItem>& items) -> bool {
+            for (size_t i = 0; i < items.size(); ++i) {
+                for (size_t j = i + 1; j < items.size(); ++j) {
+                    if (items[i].semantic == items[j].semantic)
+                        return false;
+                }
+            }
+            return true;
+        };
+        if (!checkDuplicateSemantics(inputItems))
+            return false;
+        if (!checkDuplicateSemantics(outputItems))
+            return false;
+    }
+
+    {
+        auto checkSemanticTypes = [&](const Vector<EntryPointItem>& items) -> bool {
+            for (auto& item : items) {
+                auto acceptable = WTF::visit(WTF::makeVisitor([&](const AST::BaseSemantic& semantic) -> bool {
+                    return semantic.isAcceptableType(item.unnamedType, intrinsics);
+                }), item.semantic);
+                if (!acceptable)
+                    return false;
+            }
+            return true;
+        };
+        if (!checkSemanticTypes(inputItems))
+            return false;
+        if (!checkSemanticTypes(outputItems))
+            return false;
+    }
+
+    {
+        auto checkSemanticForShaderType = [&](const Vector<EntryPointItem>& items, AST::BaseSemantic::ShaderItemDirection direction) -> bool {
+            for (auto& item : items) {
+                auto acceptable = WTF::visit(WTF::makeVisitor([&](const AST::BaseSemantic& semantic) -> bool {
+                    return semantic.isAcceptableForShaderItemDirection(direction, entryPointType);
+                }), item.semantic);
+                if (!acceptable)
+                    return false;
+            }
+            return true;
+        };
+        if (!checkSemanticForShaderType(inputItems, AST::BaseSemantic::ShaderItemDirection::Input))
+            return false;
+        if (!checkSemanticForShaderType(outputItems, AST::BaseSemantic::ShaderItemDirection::Output))
+            return false;
+    }
+
+    {
+        auto checkPODData = [&](const Vector<EntryPointItem>& items) -> bool {
+            for (auto& item : items) {
+                PODChecker podChecker;
+                if (is<AST::PointerType>(item.unnamedType))
+                    podChecker.checkErrorAndVisit(downcast<AST::PointerType>(item.unnamedType).elementType());
+                else if (is<AST::ArrayReferenceType>(item.unnamedType))
+                    podChecker.checkErrorAndVisit(downcast<AST::ArrayReferenceType>(item.unnamedType).elementType());
+                else if (is<AST::ArrayType>(item.unnamedType))
+                    podChecker.checkErrorAndVisit(downcast<AST::ArrayType>(item.unnamedType).type());
+                else
+                    continue;
+                if (podChecker.error())
+                    return false;
+            }
+            return true;
+        };
+        if (!checkPODData(inputItems))
+            return false;
+        if (!checkPODData(outputItems))
+            return false;
+    }
+
+    return true;
+}
+
+static bool checkOperatorOverload(const AST::FunctionDefinition& functionDefinition, const Intrinsics& intrinsics, NameContext& nameContext)
+{
+    enum class CheckKind {
+        Index,
+        Dot
+    };
+
+    auto checkGetter = [&](CheckKind kind) -> bool {
+        size_t numExpectedParameters = kind == CheckKind::Index ? 2 : 1;
+        if (functionDefinition.parameters().size() != numExpectedParameters)
+            return false;
+        auto& firstParameterUnifyNode = (*functionDefinition.parameters()[0].type())->unifyNode();
+        if (is<AST::UnnamedType>(firstParameterUnifyNode)) {
+            auto& unnamedType = downcast<AST::UnnamedType>(firstParameterUnifyNode);
+            if (is<AST::PointerType>(unnamedType) || is<AST::ArrayReferenceType>(unnamedType) || is<AST::ArrayType>(unnamedType))
+                return false;
+        }
+        if (kind == CheckKind::Index) {
+            auto& secondParameterUnifyNode = (*functionDefinition.parameters()[1].type())->unifyNode();
+            if (!is<AST::NamedType>(secondParameterUnifyNode))
+                return false;
+            auto& namedType = downcast<AST::NamedType>(secondParameterUnifyNode);
+            if (!is<AST::NativeTypeDeclaration>(namedType))
+                return false;
+            auto& nativeTypeDeclaration = downcast<AST::NativeTypeDeclaration>(namedType);
+            if (!nativeTypeDeclaration.isInt())
+                return false;
+        }
+        return true;
+    };
+
+    auto checkSetter = [&](CheckKind kind) -> bool {
+        size_t numExpectedParameters = kind == CheckKind::Index ? 3 : 2;
+        if (functionDefinition.parameters().size() != numExpectedParameters)
+            return false;
+        auto& firstArgumentUnifyNode = (*functionDefinition.parameters()[0].type())->unifyNode();
+        if (is<AST::UnnamedType>(firstArgumentUnifyNode)) {
+            auto& unnamedType = downcast<AST::UnnamedType>(firstArgumentUnifyNode);
+            if (is<AST::PointerType>(unnamedType) || is<AST::ArrayReferenceType>(unnamedType) || is<AST::ArrayType>(unnamedType))
+                return false;
+        }
+        if (kind == CheckKind::Index) {
+            auto& secondParameterUnifyNode = (*functionDefinition.parameters()[1].type())->unifyNode();
+            if (!is<AST::NamedType>(secondParameterUnifyNode))
+                return false;
+            auto& namedType = downcast<AST::NamedType>(secondParameterUnifyNode);
+            if (!is<AST::NativeTypeDeclaration>(namedType))
+                return false;
+            auto& nativeTypeDeclaration = downcast<AST::NativeTypeDeclaration>(namedType);
+            if (!nativeTypeDeclaration.isInt())
+                return false;
+        }
+        if (!matches(functionDefinition.type(), *functionDefinition.parameters()[0].type()))
+            return false;
+        auto& valueType = *functionDefinition.parameters()[numExpectedParameters - 1].type();
+        auto getterName = functionDefinition.name().substring(0, functionDefinition.name().length() - 1);
+        auto* getterFuncs = nameContext.getFunctions(getterName);
+        if (!getterFuncs)
+            return false;
+        Vector<ResolvingType> argumentTypes;
+        Vector<std::reference_wrapper<ResolvingType>> argumentTypeReferences;
+        for (size_t i = 0; i < numExpectedParameters - 1; ++i)
+            argumentTypes.append((*functionDefinition.parameters()[0].type())->clone());
+        for (auto& argumentType : argumentTypes)
+            argumentTypeReferences.append(argumentType);
+        Optional<std::reference_wrapper<AST::NamedType>> castReturnType;
+        auto* overload = resolveFunctionOverloadImpl(*getterFuncs, argumentTypeReferences, castReturnType);
+        if (!overload)
+            return false;
+        auto& resultType = overload->type();
+        return matches(resultType, valueType);
+    };
+
+    auto checkAnder = [&](CheckKind kind) -> bool {
+        size_t numExpectedParameters = kind == CheckKind::Index ? 2 : 1;
+        if (functionDefinition.parameters().size() != numExpectedParameters)
+            return false;
+        {
+            auto& unifyNode = functionDefinition.type().unifyNode();
+            if (!is<AST::UnnamedType>(unifyNode))
+                return false;
+            auto& unnamedType = downcast<AST::UnnamedType>(unifyNode);
+            if (!is<AST::PointerType>(unnamedType))
+                return false;
+        }
+        {
+            auto& unifyNode = (*functionDefinition.parameters()[0].type())->unifyNode();
+            if (!is<AST::UnnamedType>(unifyNode))
+                return false;
+            auto& unnamedType = downcast<AST::UnnamedType>(unifyNode);
+            return is<AST::PointerType>(unnamedType) || is<AST::ArrayReferenceType>(unnamedType);
+        }
+    };
+
+    if (!functionDefinition.isOperator())
+        return true;
+    if (functionDefinition.isCast())
+        return true;
+    if (functionDefinition.name() == "operator++" || functionDefinition.name() == "operator--") {
+        return functionDefinition.parameters().size() == 1
+            && matches(*functionDefinition.parameters()[0].type(), functionDefinition.type());
+    }
+    if (functionDefinition.name() == "operator+" || functionDefinition.name() == "operator-")
+        return functionDefinition.parameters().size() == 1 || functionDefinition.parameters().size() == 2;
+    if (functionDefinition.name() == "operator*"
+        || functionDefinition.name() == "operator/"
+        || functionDefinition.name() == "operator%"
+        || functionDefinition.name() == "operator&"
+        || functionDefinition.name() == "operator|"
+        || functionDefinition.name() == "operator^"
+        || functionDefinition.name() == "operator<<"
+        || functionDefinition.name() == "opreator>>")
+        return functionDefinition.parameters().size() == 2;
+    if (functionDefinition.name() == "operator~")
+        return functionDefinition.parameters().size() == 1;
+    if (functionDefinition.name() == "operator=="
+        || functionDefinition.name() == "operator<"
+        || functionDefinition.name() == "operator<="
+        || functionDefinition.name() == "operator>"
+        || functionDefinition.name() == "operator>=") {
+        return functionDefinition.parameters().size() == 2
+            && matches(functionDefinition.type(), intrinsics.boolType());
+    }
+    if (functionDefinition.name() == "operator[]")
+        return checkGetter(CheckKind::Index);
+    if (functionDefinition.name() == "operator[]=")
+        return checkSetter(CheckKind::Index);
+    if (functionDefinition.name() == "operator&[]")
+        return checkAnder(CheckKind::Index);
+    if (functionDefinition.name().startsWith("operator.")) {
+        if (functionDefinition.name().endsWith("="))
+            return checkSetter(CheckKind::Dot);
+        return checkGetter(CheckKind::Dot);
+    }
+    if (functionDefinition.name().startsWith("operator&."))
+        return checkAnder(CheckKind::Dot);
+    return false;
+}
+
+class Checker : public Visitor {
+public:
+    Checker(const Intrinsics& intrinsics, Program& program)
+        : m_intrinsics(intrinsics)
+        , m_program(program)
+    {
+    }
+
+    ~Checker() = default;
+
+    void visit(Program&) override;
+
+    bool assignTypes();
+
+private:
+    bool checkShaderType(const AST::FunctionDefinition&);
+    void finishVisitingPropertyAccess(AST::PropertyAccessExpression&, AST::UnnamedType& wrappedBaseType, AST::UnnamedType* extraArgumentType = nullptr);
+    bool isBoolType(ResolvingType&);
+    struct RecurseInfo {
+        ResolvingType& resolvingType;
+        Optional<AST::AddressSpace>& addressSpace;
+    };
+    Optional<RecurseInfo> recurseAndGetInfo(AST::Expression&, bool requiresLValue = false);
+    Optional<RecurseInfo> getInfo(AST::Expression&, bool requiresLValue = false);
+    Optional<UniqueRef<AST::UnnamedType>> recurseAndWrapBaseType(AST::PropertyAccessExpression&);
+    bool recurseAndRequireBoolType(AST::Expression&);
+    void assignType(AST::Expression&, UniqueRef<AST::UnnamedType>&&, Optional<AST::AddressSpace> = WTF::nullopt);
+    void assignType(AST::Expression&, Ref<ResolvableTypeReference>&&, Optional<AST::AddressSpace> = WTF::nullopt);
+    void forwardType(AST::Expression&, ResolvingType&, Optional<AST::AddressSpace> = WTF::nullopt);
+
+    void visit(AST::FunctionDefinition&) override;
+    void visit(AST::EnumerationDefinition&) override;
+    void visit(AST::TypeReference&) override;
+    void visit(AST::VariableDeclaration&) override;
+    void visit(AST::AssignmentExpression&) override;
+    void visit(AST::ReadModifyWriteExpression&) override;
+    void visit(AST::DereferenceExpression&) override;
+    void visit(AST::MakePointerExpression&) override;
+    void visit(AST::MakeArrayReferenceExpression&) override;
+    void visit(AST::DotExpression&) override;
+    void visit(AST::IndexExpression&) override;
+    void visit(AST::VariableReference&) override;
+    void visit(AST::Return&) override;
+    void visit(AST::PointerType&) override;
+    void visit(AST::ArrayReferenceType&) override;
+    void visit(AST::IntegerLiteral&) override;
+    void visit(AST::UnsignedIntegerLiteral&) override;
+    void visit(AST::FloatLiteral&) override;
+    void visit(AST::NullLiteral&) override;
+    void visit(AST::BooleanLiteral&) override;
+    void visit(AST::EnumerationMemberLiteral&) override;
+    void visit(AST::LogicalNotExpression&) override;
+    void visit(AST::LogicalExpression&) override;
+    void visit(AST::IfStatement&) override;
+    void visit(AST::WhileLoop&) override;
+    void visit(AST::DoWhileLoop&) override;
+    void visit(AST::ForLoop&) override;
+    void visit(AST::SwitchStatement&) override;
+    void visit(AST::CommaExpression&) override;
+    void visit(AST::TernaryExpression&) override;
+    void visit(AST::CallExpression&) override;
+
+    HashMap<AST::Expression*, ResolvingType> m_typeMap;
+    HashMap<AST::Expression*, Optional<AST::AddressSpace>> m_addressSpaceMap;
+    HashSet<String> m_vertexEntryPoints;
+    HashSet<String> m_fragmentEntryPoints;
+    HashSet<String> m_computeEntryPoints;
+    const Intrinsics& m_intrinsics;
+    Program& m_program;
+};
+
+void Checker::visit(Program& program)
+{
+    // These visiting functions might add new global statements, so don't use foreach syntax.
+    for (size_t i = 0; i < program.typeDefinitions().size(); ++i)
+        checkErrorAndVisit(program.typeDefinitions()[i]);
+    for (size_t i = 0; i < program.structureDefinitions().size(); ++i)
+        checkErrorAndVisit(program.structureDefinitions()[i]);
+    for (size_t i = 0; i < program.enumerationDefinitions().size(); ++i)
+        checkErrorAndVisit(program.enumerationDefinitions()[i]);
+    for (size_t i = 0; i < program.nativeTypeDeclarations().size(); ++i)
+        checkErrorAndVisit(program.nativeTypeDeclarations()[i]);
+
+    for (size_t i = 0; i < program.functionDefinitions().size(); ++i)
+        checkErrorAndVisit(program.functionDefinitions()[i]);
+    for (size_t i = 0; i < program.nativeFunctionDeclarations().size(); ++i)
+        checkErrorAndVisit(program.nativeFunctionDeclarations()[i]);
+}
+
+bool Checker::assignTypes()
+{
+    for (auto& keyValuePair : m_typeMap) {
+        auto success = WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& unnamedType) -> bool {
+            keyValuePair.key->setType(unnamedType->clone());
+            return true;
+        }, [&](Ref<ResolvableTypeReference>& resolvableTypeReference) -> bool {
+            if (!resolvableTypeReference->resolvableType().resolvedType()) {
+                // FIXME: Instead of trying to commit, it might be better to just return an error instead.
+                if (!static_cast<bool>(commit(resolvableTypeReference->resolvableType())))
+                    return false;
+            }
+            keyValuePair.key->setType(resolvableTypeReference->resolvableType().resolvedType()->clone());
+            return true;
+        }), keyValuePair.value);
+        if (!success)
+            return false;
+    }
+
+    for (auto& keyValuePair : m_addressSpaceMap)
+        keyValuePair.key->setAddressSpace(keyValuePair.value);
+    return true;
+}
+
+bool Checker::checkShaderType(const AST::FunctionDefinition& functionDefinition)
+{
+    switch (*functionDefinition.entryPointType()) {
+    case AST::EntryPointType::Vertex:
+        return !m_vertexEntryPoints.add(functionDefinition.name()).isNewEntry;
+    case AST::EntryPointType::Fragment:
+        return !m_fragmentEntryPoints.add(functionDefinition.name()).isNewEntry;
+    case AST::EntryPointType::Compute:
+        return !m_computeEntryPoints.add(functionDefinition.name()).isNewEntry;
+    }
+}
+
+void Checker::visit(AST::FunctionDefinition& functionDefinition)
+{
+    if (functionDefinition.entryPointType()) {
+        if (!checkShaderType(functionDefinition)) {
+            setError();
+            return;
+        }
+        auto entryPointItems = gatherEntryPointItems(m_intrinsics, functionDefinition);
+        if (!entryPointItems) {
+            setError();
+            return;
+        }
+        if (!checkSemantics(entryPointItems->inputs, entryPointItems->outputs, functionDefinition.entryPointType(), m_intrinsics)) {
+            setError();
+            return;
+        }
+    }
+    if (!checkOperatorOverload(functionDefinition, m_intrinsics, m_program.nameContext())) {
+        setError();
+        return;
+    }
+
+    checkErrorAndVisit(functionDefinition);
+}
+
+static Optional<UniqueRef<AST::UnnamedType>> matchAndCommit(ResolvingType& left, ResolvingType& right)
+{
+    return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& left) -> Optional<UniqueRef<AST::UnnamedType>> {
+        return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& right) -> Optional<UniqueRef<AST::UnnamedType>> {
+            if (matches(left, right))
+                return left->clone();
+            return WTF::nullopt;
+        }, [&](Ref<ResolvableTypeReference>& right) -> Optional<UniqueRef<AST::UnnamedType>> {
+            return matchAndCommit(left, right->resolvableType());
+        }), right);
+    }, [&](Ref<ResolvableTypeReference>& left) -> Optional<UniqueRef<AST::UnnamedType>> {
+        return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& right) -> Optional<UniqueRef<AST::UnnamedType>> {
+            return matchAndCommit(right, left->resolvableType());
+        }, [&](Ref<ResolvableTypeReference>& right) -> Optional<UniqueRef<AST::UnnamedType>> {
+            return matchAndCommit(left->resolvableType(), right->resolvableType());
+        }), right);
+    }), left);
+}
+
+static Optional<UniqueRef<AST::UnnamedType>> matchAndCommit(ResolvingType& resolvingType, AST::UnnamedType& unnamedType)
+{
+    return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& resolvingType) -> Optional<UniqueRef<AST::UnnamedType>> {
+        if (matches(unnamedType, resolvingType))
+            return unnamedType.clone();
+        return WTF::nullopt;
+    }, [&](Ref<ResolvableTypeReference>& resolvingType) -> Optional<UniqueRef<AST::UnnamedType>> {
+        return matchAndCommit(unnamedType, resolvingType->resolvableType());
+    }), resolvingType);
+}
+
+static Optional<UniqueRef<AST::UnnamedType>> matchAndCommit(ResolvingType& resolvingType, AST::NamedType& namedType)
+{
+    return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& resolvingType) -> Optional<UniqueRef<AST::UnnamedType>> {
+        if (matches(resolvingType, namedType))
+            return resolvingType->clone();
+        return WTF::nullopt;
+    }, [&](Ref<ResolvableTypeReference>& resolvingType) -> Optional<UniqueRef<AST::UnnamedType>> {
+        return matchAndCommit(namedType, resolvingType->resolvableType());
+    }), resolvingType);
+}
+
+void Checker::visit(AST::EnumerationDefinition& enumerationDefinition)
+{
+    auto* baseType = ([&]() -> AST::NativeTypeDeclaration* {
+        checkErrorAndVisit(enumerationDefinition.type());
+        auto& baseType = enumerationDefinition.type().unifyNode();
+        if (!is<AST::UnnamedType>(baseType))
+            return nullptr;
+        auto& unnamedBase = downcast<AST::UnnamedType>(baseType);
+        if (!is<AST::TypeReference>(unnamedBase))
+            return nullptr;
+        auto& typeReferenceBase = downcast<AST::TypeReference>(unnamedBase);
+        ASSERT(typeReferenceBase.resolvedType());
+        if (!is<AST::NativeTypeDeclaration>(*typeReferenceBase.resolvedType()))
+            return nullptr;
+        auto& nativeTypeDeclaration = downcast<AST::NativeTypeDeclaration>(*typeReferenceBase.resolvedType());
+        if (!nativeTypeDeclaration.isInt())
+            return nullptr;
+        return &nativeTypeDeclaration;
+    })();
+    if (!baseType) {
+        setError();
+        return;
+    }
+
+    auto enumerationMembers = enumerationDefinition.enumerationMembers();
+
+    for (auto& member : enumerationMembers) {
+        if (!member.get().value())
+            continue;
+
+        bool success = false;
+        member.get().value()->visit(WTF::makeVisitor([&](AST::Expression& value) {
+            auto valueInfo = recurseAndGetInfo(value);
+            if (!valueInfo)
+                return;
+            success = static_cast<bool>(matchAndCommit(valueInfo->resolvingType, *baseType));
+        }));
+        if (!success) {
+            setError();
+            return;
+        }
+    }
+
+    int64_t nextValue = 0;
+    for (auto& member : enumerationMembers) {
+        if (member.get().value()) {
+            int64_t value;
+            member.get().value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& integerLiteral) {
+                value = integerLiteral.valueForSelectedType();
+            }, [&](AST::UnsignedIntegerLiteral& unsignedIntegerLiteral) {
+                value = unsignedIntegerLiteral.valueForSelectedType();
+            }, [&](auto&) {
+                ASSERT_NOT_REACHED();
+            }));
+            nextValue = baseType->successor()(value);
+        } else {
+            if (nextValue > std::numeric_limits<int>::max()) {
+                ASSERT(nextValue <= std::numeric_limits<unsigned>::max());
+                member.get().setValue(AST::ConstantExpression(AST::UnsignedIntegerLiteral(Lexer::Token(member.get().origin()), static_cast<unsigned>(nextValue))));
+            }
+            ASSERT(nextValue >= std::numeric_limits<int>::min());
+            member.get().setValue(AST::ConstantExpression(AST::IntegerLiteral(Lexer::Token(member.get().origin()), static_cast<int>(nextValue))));
+            nextValue = baseType->successor()(nextValue);
+        }
+    }
+
+    auto getValue = [&](AST::EnumerationMember& member) -> int64_t {
+        int64_t value;
+        ASSERT(member.value());
+        member.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& integerLiteral) {
+            value = integerLiteral.value();
+        }, [&](AST::UnsignedIntegerLiteral& unsignedIntegerLiteral) {
+            value = unsignedIntegerLiteral.value();
+        }, [&](auto&) {
+            ASSERT_NOT_REACHED();
+        }));
+        return value;
+    };
+
+    for (size_t i = 0; i < enumerationMembers.size(); ++i) {
+        auto value = getValue(enumerationMembers[i].get());
+        for (size_t j = i + 1; j < enumerationMembers.size(); ++j) {
+            auto otherValue = getValue(enumerationMembers[j].get());
+            if (value == otherValue) {
+                setError();
+                return;
+            }
+        }
+    }
+
+    bool foundZero = false;
+    for (auto& member : enumerationMembers) {
+        if (!getValue(member.get())) {
+            foundZero = true;
+            break;
+        }
+    }
+    if (!foundZero) {
+        setError();
+        return;
+    }
+}
+
+void Checker::visit(AST::TypeReference& typeReference)
+{
+    ASSERT(typeReference.resolvedType());
+
+    checkErrorAndVisit(typeReference);
+}
+
+auto Checker::recurseAndGetInfo(AST::Expression& expression, bool requiresLValue) -> Optional<RecurseInfo>
+{
+    checkErrorAndVisit(expression);
+    if (!error())
+        return WTF::nullopt;
+    return getInfo(expression, requiresLValue);
+}
+
+auto Checker::getInfo(AST::Expression& expression, bool requiresLValue) -> Optional<RecurseInfo>
+{
+    auto typeIterator = m_typeMap.find(&expression);
+    ASSERT(typeIterator != m_typeMap.end());
+
+    auto addressSpaceIterator = m_addressSpaceMap.find(&expression);
+    ASSERT(addressSpaceIterator != m_addressSpaceMap.end());
+    if (requiresLValue && !addressSpaceIterator->value) {
+        setError();
+        return WTF::nullopt;
+    }
+    return {{ typeIterator->value, addressSpaceIterator->value }};
+}
+
+void Checker::visit(AST::VariableDeclaration& variableDeclaration)
+{
+    // ReadModifyWriteExpressions are the only place where anonymous variables exist,
+    // and that doesn't recurse on the anonymous variables, so we can assume the variable has a type.
+    checkErrorAndVisit(*variableDeclaration.type());
+    if (variableDeclaration.initializer()) {
+        auto& lhsType = *variableDeclaration.type();
+        auto initializerInfo = recurseAndGetInfo(*variableDeclaration.initializer());
+        if (!initializerInfo)
+            return;
+        if (!matchAndCommit(initializerInfo->resolvingType, lhsType)) {
+            setError();
+            return;
+        }
+    }
+}
+
+void Checker::assignType(AST::Expression& expression, UniqueRef<AST::UnnamedType>&& unnamedType, Optional<AST::AddressSpace> addressSpace)
+{
+    auto addResult = m_typeMap.add(&expression, WTFMove(unnamedType));
+    ASSERT_UNUSED(addResult, addResult.isNewEntry);
+    auto addressSpaceAddResult = m_addressSpaceMap.add(&expression, addressSpace);
+    ASSERT_UNUSED(addressSpaceAddResult, addressSpaceAddResult.isNewEntry);
+}
+
+void Checker::assignType(AST::Expression& expression, Ref<ResolvableTypeReference>&& resolvableTypeReference, Optional<AST::AddressSpace> addressSpace)
+{
+    auto addResult = m_typeMap.add(&expression, WTFMove(resolvableTypeReference));
+    ASSERT_UNUSED(addResult, addResult.isNewEntry);
+    auto addressSpaceAddResult = m_addressSpaceMap.add(&expression, addressSpace);
+    ASSERT_UNUSED(addressSpaceAddResult, addressSpaceAddResult.isNewEntry);
+}
+
+void Checker::visit(AST::AssignmentExpression& assignmentExpression)
+{
+    auto leftInfo = recurseAndGetInfo(assignmentExpression.left(), true);
+    if (!leftInfo)
+        return;
+
+    auto rightInfo = recurseAndGetInfo(assignmentExpression.right());
+    if (!rightInfo)
+        return;
+
+    auto resultType = matchAndCommit(leftInfo->resolvingType, rightInfo->resolvingType);
+    if (!resultType) {
+        setError();
+        return;
+    }
+
+    assignType(assignmentExpression, WTFMove(*resultType));
+}
+
+void Checker::forwardType(AST::Expression& expression, ResolvingType& resolvingType, Optional<AST::AddressSpace> addressSpace)
+{
+    WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& result) {
+        auto addResult = m_typeMap.add(&expression, result->clone());
+        ASSERT_UNUSED(addResult, addResult.isNewEntry);
+    }, [&](Ref<ResolvableTypeReference>& result) {
+        auto addResult = m_typeMap.add(&expression, result.copyRef());
+        ASSERT_UNUSED(addResult, addResult.isNewEntry);
+    }), resolvingType);
+    auto addressSpaceAddResult = m_addressSpaceMap.add(&expression, addressSpace);
+    ASSERT_UNUSED(addressSpaceAddResult, addressSpaceAddResult.isNewEntry);
+}
+
+void Checker::visit(AST::ReadModifyWriteExpression& readModifyWriteExpression)
+{
+    auto lValueInfo = recurseAndGetInfo(readModifyWriteExpression.lValue(), true);
+    if (!lValueInfo)
+        return;
+
+    // FIXME: Figure out what to do with the ReadModifyWriteExpression's AnonymousVariables.
+
+    auto newValueInfo = recurseAndGetInfo(*readModifyWriteExpression.newValueExpression());
+    if (!newValueInfo)
+        return;
+
+    if (!matchAndCommit(lValueInfo->resolvingType, newValueInfo->resolvingType)) {
+        setError();
+        return;
+    }
+
+    auto resultInfo = recurseAndGetInfo(*readModifyWriteExpression.resultExpression());
+    if (!resultInfo)
+        return;
+
+    forwardType(readModifyWriteExpression, resultInfo->resolvingType);
+}
+
+static AST::UnnamedType* getUnnamedType(ResolvingType& resolvingType)
+{
+    return WTF::visit(WTF::makeVisitor([](UniqueRef<AST::UnnamedType>& type) -> AST::UnnamedType* {
+        return &type;
+    }, [](Ref<ResolvableTypeReference>& type) -> AST::UnnamedType* {
+        // FIXME: If the type isn't committed, should we just commit() it now?
+        return type->resolvableType().resolvedType();
+    }), resolvingType);
+}
+
+void Checker::visit(AST::DereferenceExpression& dereferenceExpression)
+{
+    auto pointerInfo = recurseAndGetInfo(dereferenceExpression.pointer());
+    if (!pointerInfo)
+        return;
+
+    auto* unnamedType = getUnnamedType(pointerInfo->resolvingType);
+
+    auto* pointerType = ([&](AST::UnnamedType* unnamedType) -> AST::PointerType* {
+        if (!unnamedType)
+            return nullptr;
+        auto& unifyNode = unnamedType->unifyNode();
+        if (!is<AST::UnnamedType>(unifyNode))
+            return nullptr;
+        auto& unnamedUnifyType = downcast<AST::UnnamedType>(unifyNode);
+        if (!is<AST::PointerType>(unnamedUnifyType))
+            return nullptr;
+        return &downcast<AST::PointerType>(unnamedUnifyType);
+    })(unnamedType);
+    if (!pointerType) {
+        setError();
+        return;
+    }
+
+    assignType(dereferenceExpression, pointerType->clone(), pointerType->addressSpace());
+}
+
+void Checker::visit(AST::MakePointerExpression& makePointerExpression)
+{
+    auto lValueInfo = recurseAndGetInfo(makePointerExpression.lValue(), true);
+    if (!lValueInfo)
+        return;
+
+    auto* lValueType = getUnnamedType(lValueInfo->resolvingType);
+    if (!lValueType) {
+        setError();
+        return;
+    }
+
+    assignType(makePointerExpression, makeUniqueRef<AST::PointerType>(Lexer::Token(makePointerExpression.origin()), *lValueInfo->addressSpace, lValueType->clone()));
+}
+
+void Checker::visit(AST::MakeArrayReferenceExpression& makeArrayReferenceExpression)
+{
+    auto lValueInfo = recurseAndGetInfo(makeArrayReferenceExpression.lValue());
+    if (!lValueInfo)
+        return;
+
+    auto* lValueType = getUnnamedType(lValueInfo->resolvingType);
+    if (!lValueType) {
+        setError();
+        return;
+    }
+
+    auto& unifyNode = lValueType->unifyNode();
+    if (is<AST::UnnamedType>(unifyNode)) {
+        auto& unnamedType = downcast<AST::UnnamedType>(unifyNode);
+        if (is<AST::PointerType>(unnamedType)) {
+            auto& pointerType = downcast<AST::PointerType>(unnamedType);
+            // FIXME: Save the fact that we're not targetting the item; we're targetting the item's inner element.
+            assignType(makeArrayReferenceExpression, makeUniqueRef<AST::ArrayReferenceType>(Lexer::Token(makeArrayReferenceExpression.origin()), pointerType.addressSpace(), pointerType.elementType().clone()));
+            return;
+        }
+
+        if (!lValueInfo->addressSpace) {
+            setError();
+            return;
+        }
+
+        if (is<AST::ArrayType>(unnamedType)) {
+            auto& arrayType = downcast<AST::ArrayType>(unnamedType);
+            // FIXME: Save the number of elements.
+            assignType(makeArrayReferenceExpression, makeUniqueRef<AST::ArrayReferenceType>(Lexer::Token(makeArrayReferenceExpression.origin()), *lValueInfo->addressSpace, arrayType.type().clone()));
+            return;
+        }
+    }
+
+    if (!lValueInfo->addressSpace) {
+        setError();
+        return;
+    }
+
+    assignType(makeArrayReferenceExpression, makeUniqueRef<AST::ArrayReferenceType>(Lexer::Token(makeArrayReferenceExpression.origin()), *lValueInfo->addressSpace, lValueType->clone()));
+}
+
+void Checker::finishVisitingPropertyAccess(AST::PropertyAccessExpression& propertyAccessExpression, AST::UnnamedType& wrappedBaseType, AST::UnnamedType* extraArgumentType)
+{
+    Optional<std::reference_wrapper<AST::NamedType>> castReturnType;
+    using OverloadResolution = std::tuple<AST::FunctionDeclaration*, AST::UnnamedType*>;
+
+    AST::FunctionDeclaration* getFunction;
+    AST::UnnamedType* getReturnType;
+    std::tie(getFunction, getReturnType) = ([&]() -> OverloadResolution {
+        ResolvingType getArgumentType1(wrappedBaseType.clone());
+        Optional<ResolvingType> getArgumentType2;
+        if (extraArgumentType)
+            getArgumentType2 = ResolvingType(extraArgumentType->clone());
+
+        Vector<std::reference_wrapper<ResolvingType>> getArgumentTypes;
+        getArgumentTypes.append(getArgumentType1);
+        if (getArgumentType2)
+            getArgumentTypes.append(*getArgumentType2);
+
+        auto* getFunction = resolveFunctionOverloadImpl(propertyAccessExpression.possibleGetOverloads(), getArgumentTypes, castReturnType);
+        if (!getFunction)
+            return std::make_pair(nullptr, nullptr);
+        return std::make_pair(getFunction, &getFunction->type());
+    })();
+
+    AST::FunctionDeclaration* andFunction;
+    AST::UnnamedType* andReturnType;
+    std::tie(andFunction, andReturnType) = ([&]() -> OverloadResolution {
+        auto computeAndArgumentType = [&](AST::UnnamedType& unnamedType) -> Optional<ResolvingType> {
+            if (is<AST::ArrayReferenceType>(unnamedType))
+                return { unnamedType.clone() };
+            if (is<AST::ArrayType>(unnamedType))
+                return { makeUniqueRef<AST::ArrayReferenceType>(Lexer::Token(propertyAccessExpression.origin()), AST::AddressSpace::Thread, downcast<AST::ArrayType>(unnamedType).type().clone()) };
+            if (is<AST::PointerType>(unnamedType))
+                return WTF::nullopt;
+            return { makeUniqueRef<AST::PointerType>(Lexer::Token(propertyAccessExpression.origin()), AST::AddressSpace::Thread, downcast<AST::ArrayType>(unnamedType).type().clone()) };
+        };
+        auto computeAndReturnType = [&](AST::UnnamedType& unnamedType) -> AST::UnnamedType* {
+            if (is<AST::PointerType>(unnamedType))
+                return &downcast<AST::PointerType>(unnamedType).elementType();
+            return nullptr;
+        };
+
+        auto andArgumentType1 = computeAndArgumentType(wrappedBaseType);
+        if (!andArgumentType1)
+            return std::make_pair(nullptr, nullptr);
+        Optional<ResolvingType> andArgumentType2;
+        if (extraArgumentType)
+            andArgumentType2 = ResolvingType(extraArgumentType->clone());
+
+        Vector<std::reference_wrapper<ResolvingType>> andArgumentTypes;
+        andArgumentTypes.append(*andArgumentType1);
+        if (andArgumentType2)
+            andArgumentTypes.append(*andArgumentType2);
+
+        auto* andFunction = resolveFunctionOverloadImpl(propertyAccessExpression.possibleAndOverloads(), andArgumentTypes, castReturnType);
+        if (!andFunction)
+            return std::make_pair(nullptr, nullptr);
+        return std::make_pair(andFunction, computeAndReturnType(andFunction->type()));
+    })();
+
+    if (!getReturnType && !andReturnType) {
+        setError();
+        return;
+    }
+
+    if (getReturnType && andReturnType && !matches(*getReturnType, *andReturnType)) {
+        setError();
+        return;
+    }
+
+    AST::FunctionDeclaration* setFunction;
+    AST::UnnamedType* setReturnType;
+    std::tie(setFunction, setReturnType) = ([&]() -> OverloadResolution {
+        ResolvingType setArgument1Type(wrappedBaseType.clone());
+        Optional<ResolvingType> setArgumentType2;
+        if (extraArgumentType)
+            setArgumentType2 = ResolvingType(extraArgumentType->clone());
+        ResolvingType setArgument3Type(getReturnType ? getReturnType->clone() : andReturnType->clone());
+
+        Vector<std::reference_wrapper<ResolvingType>> setArgumentTypes;
+        setArgumentTypes.append(setArgument1Type);
+        if (setArgumentType2)
+            setArgumentTypes.append(*setArgumentType2);
+        setArgumentTypes.append(setArgument3Type);
+
+        auto* setFunction = resolveFunctionOverloadImpl(propertyAccessExpression.possibleSetOverloads(), setArgumentTypes, castReturnType);
+        if (!setFunction)
+            return std::make_pair(nullptr, nullptr);
+        return std::make_pair(setFunction, &setFunction->type());
+    })();
+
+    if (setFunction) {
+        if (!matches(setFunction->type(), wrappedBaseType)) {
+            setError();
+            return;
+        }
+    }
+
+    Optional<AST::AddressSpace> addressSpace;
+    if (getReturnType || andReturnType) {
+        // FIXME: The reference compiler has "else if (!node.base.isLValue && !baseType.isArrayRef)",
+        // but I don't understand why it exists. I haven't written it here, and I'll investigate
+        // if we can remove it from the reference compiler.
+        if (is<AST::ReferenceType>(wrappedBaseType))
+            addressSpace = downcast<AST::ReferenceType>(wrappedBaseType).addressSpace();
+        else {
+            auto addressSpaceIterator = m_addressSpaceMap.find(&propertyAccessExpression.base());
+            ASSERT(addressSpaceIterator != m_addressSpaceMap.end());
+            if (addressSpaceIterator->value)
+                addressSpace = *addressSpaceIterator->value;
+            else {
+                setError();
+                return;
+            }
+        }
+    }
+
+    // FIXME: Generate the call expressions
+
+    assignType(propertyAccessExpression, getReturnType ? getReturnType->clone() : andReturnType->clone(), addressSpace);
+}
+
+Optional<UniqueRef<AST::UnnamedType>> Checker::recurseAndWrapBaseType(AST::PropertyAccessExpression& propertyAccessExpression)
+{
+    auto baseInfo = recurseAndGetInfo(propertyAccessExpression.base());
+    if (!baseInfo)
+        return WTF::nullopt;
+
+    auto* baseType = getUnnamedType(baseInfo->resolvingType);
+    if (!baseType) {
+        setError();
+        return WTF::nullopt;
+    }
+    auto& baseUnifyNode = baseType->unifyNode();
+    if (is<AST::UnnamedType>(baseUnifyNode))
+        return downcast<AST::UnnamedType>(baseUnifyNode).clone();
+    ASSERT(is<AST::NamedType>(baseUnifyNode));
+    return { AST::TypeReference::wrap(Lexer::Token(propertyAccessExpression.origin()), downcast<AST::NamedType>(baseUnifyNode)) };
+}
+
+void Checker::visit(AST::DotExpression& dotExpression)
+{
+    auto baseType = recurseAndWrapBaseType(dotExpression);
+    if (!baseType)
+        return;
+
+    finishVisitingPropertyAccess(dotExpression, *baseType);
+}
+
+void Checker::visit(AST::IndexExpression& indexExpression)
+{
+    auto baseType = recurseAndWrapBaseType(indexExpression);
+    if (!baseType)
+        return;
+
+    auto indexInfo = recurseAndGetInfo(indexExpression.indexExpression());
+    if (!indexInfo)
+        return;
+    auto indexExpressionType = getUnnamedType(indexInfo->resolvingType);
+    if (!indexExpressionType) {
+        setError();
+        return;
+    }
+
+    finishVisitingPropertyAccess(indexExpression, WTFMove(*baseType), indexExpressionType);
+}
+
+void Checker::visit(AST::VariableReference& variableReference)
+{
+    ASSERT(variableReference.variable());
+    ASSERT(variableReference.variable()->type());
+    
+    Optional<AST::AddressSpace> addressSpace;
+    if (!variableReference.variable()->isAnonymous())
+        addressSpace = AST::AddressSpace::Thread;
+    assignType(variableReference, variableReference.variable()->type()->clone(), addressSpace);
+}
+
+void Checker::visit(AST::Return& returnStatement)
+{
+    ASSERT(returnStatement.function());
+    if (returnStatement.value()) {
+        auto valueInfo = recurseAndGetInfo(*returnStatement.value());
+        if (!valueInfo)
+            return;
+        if (!matchAndCommit(valueInfo->resolvingType, returnStatement.function()->type()))
+            setError();
+        return;
+    }
+
+    if (!matches(returnStatement.function()->type(), m_intrinsics.voidType()))
+        setError();
+}
+
+void Checker::visit(AST::PointerType&)
+{
+    // Following pointer types can cause infinite loops because of data structures
+    // like linked lists.
+    // FIXME: Make sure this function should be empty
+}
+
+void Checker::visit(AST::ArrayReferenceType&)
+{
+    // Following array reference types can cause infinite loops because of data
+    // structures like linked lists.
+    // FIXME: Make sure this function should be empty
+}
+
+void Checker::visit(AST::IntegerLiteral& integerLiteral)
+{
+    assignType(integerLiteral, adoptRef(*new ResolvableTypeReference(integerLiteral.type())));
+}
+
+void Checker::visit(AST::UnsignedIntegerLiteral& unsignedIntegerLiteral)
+{
+    assignType(unsignedIntegerLiteral, adoptRef(*new ResolvableTypeReference(unsignedIntegerLiteral.type())));
+}
+
+void Checker::visit(AST::FloatLiteral& floatLiteral)
+{
+    assignType(floatLiteral, adoptRef(*new ResolvableTypeReference(floatLiteral.type())));
+}
+
+void Checker::visit(AST::NullLiteral& nullLiteral)
+{
+    assignType(nullLiteral, adoptRef(*new ResolvableTypeReference(nullLiteral.type())));
+}
+
+void Checker::visit(AST::BooleanLiteral& booleanLiteral)
+{
+    assignType(booleanLiteral, AST::TypeReference::wrap(Lexer::Token(booleanLiteral.origin()), m_intrinsics.boolType()));
+}
+
+void Checker::visit(AST::EnumerationMemberLiteral& enumerationMemberLiteral)
+{
+    ASSERT(enumerationMemberLiteral.enumerationDefinition());
+    auto& enumerationDefinition = *enumerationMemberLiteral.enumerationDefinition();
+    assignType(enumerationMemberLiteral, AST::TypeReference::wrap(Lexer::Token(enumerationMemberLiteral.origin()), enumerationDefinition));
+}
+
+bool Checker::isBoolType(ResolvingType& resolvingType)
+{
+    return WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::UnnamedType>& left) -> bool {
+        return matches(left, m_intrinsics.boolType());
+    }, [&](Ref<ResolvableTypeReference>& left) -> bool {
+        return static_cast<bool>(matchAndCommit(m_intrinsics.boolType(), left->resolvableType()));
+    }), resolvingType);
+}
+
+bool Checker::recurseAndRequireBoolType(AST::Expression& expression)
+{
+    auto expressionInfo = recurseAndGetInfo(expression);
+    if (!expressionInfo)
+        return false;
+    if (!isBoolType(expressionInfo->resolvingType)) {
+        setError();
+        return false;
+    }
+    return true;
+}
+
+void Checker::visit(AST::LogicalNotExpression& logicalNotExpression)
+{
+    if (!recurseAndRequireBoolType(logicalNotExpression.operand()))
+        return;
+    assignType(logicalNotExpression, AST::TypeReference::wrap(Lexer::Token(logicalNotExpression.origin()), m_intrinsics.boolType()));
+}
+
+void Checker::visit(AST::LogicalExpression& logicalExpression)
+{
+    if (!recurseAndRequireBoolType(logicalExpression.left()))
+        return;
+    if (!recurseAndRequireBoolType(logicalExpression.right()))
+        return;
+    assignType(logicalExpression, AST::TypeReference::wrap(Lexer::Token(logicalExpression.origin()), m_intrinsics.boolType()));
+}
+
+void Checker::visit(AST::IfStatement& ifStatement)
+{
+    if (!recurseAndRequireBoolType(ifStatement.conditional()))
+        return;
+    checkErrorAndVisit(ifStatement.body());
+    if (ifStatement.elseBody())
+        checkErrorAndVisit(*ifStatement.elseBody());
+}
+
+void Checker::visit(AST::WhileLoop& whileLoop)
+{
+    if (!recurseAndRequireBoolType(whileLoop.conditional()))
+        return;
+    checkErrorAndVisit(whileLoop.body());
+}
+
+void Checker::visit(AST::DoWhileLoop& doWhileLoop)
+{
+    checkErrorAndVisit(doWhileLoop.body());
+    recurseAndRequireBoolType(doWhileLoop.conditional());
+}
+
+void Checker::visit(AST::ForLoop& forLoop)
+{
+    WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) {
+        checkErrorAndVisit(variableDeclarationsStatement);
+    }, [&](UniqueRef<AST::Expression>& expression) {
+        checkErrorAndVisit(expression);
+    }), forLoop.initialization());
+    if (error())
+        return;
+    if (forLoop.condition()) {
+        if (!recurseAndRequireBoolType(*forLoop.condition()))
+            return;
+    }
+    if (forLoop.increment())
+        checkErrorAndVisit(*forLoop.increment());
+    checkErrorAndVisit(forLoop.body());
+}
+
+void Checker::visit(AST::SwitchStatement& switchStatement)
+{
+    auto* valueType = ([&]() -> AST::NamedType* {
+        auto valueInfo = recurseAndGetInfo(switchStatement.value());
+        if (!valueInfo)
+            return nullptr;
+        auto* valueType = getUnnamedType(valueInfo->resolvingType);
+        if (!valueType)
+            return nullptr;
+        auto& valueUnifyNode = valueType->unifyNode();
+        if (!is<AST::NamedType>(valueUnifyNode))
+            return nullptr;
+        auto& valueNamedUnifyNode = downcast<AST::NamedType>(valueUnifyNode);
+        if (!(is<AST::NativeTypeDeclaration>(valueNamedUnifyNode) && downcast<AST::NativeTypeDeclaration>(valueNamedUnifyNode).isInt())
+            && !is<AST::EnumerationDefinition>(valueNamedUnifyNode))
+            return nullptr;
+        return &valueNamedUnifyNode;
+    })();
+    if (!valueType) {
+        setError();
+        return;
+    }
+
+    bool hasDefault = false;
+    for (auto& switchCase : switchStatement.switchCases()) {
+        checkErrorAndVisit(switchCase.block());
+        if (!switchCase.value()) {
+            hasDefault = true;
+            continue;
+        }
+        bool success;
+        switchCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& integerLiteral) {
+            success = static_cast<bool>(matchAndCommit(*valueType, integerLiteral.type()));
+        }, [&](AST::UnsignedIntegerLiteral& unsignedIntegerLiteral) {
+            success = static_cast<bool>(matchAndCommit(*valueType, unsignedIntegerLiteral.type()));
+        }, [&](AST::FloatLiteral& floatLiteral) {
+            success = static_cast<bool>(matchAndCommit(*valueType, floatLiteral.type()));
+        }, [&](AST::NullLiteral& nullLiteral) {
+            success = static_cast<bool>(matchAndCommit(*valueType, nullLiteral.type()));
+        }, [&](AST::BooleanLiteral&) {
+            success = matches(*valueType, m_intrinsics.boolType());
+        }, [&](AST::EnumerationMemberLiteral& enumerationMemberLiteral) {
+            ASSERT(enumerationMemberLiteral.enumerationDefinition());
+            success = matches(*valueType, *enumerationMemberLiteral.enumerationDefinition());
+        }));
+        if (!success) {
+            setError();
+            return;
+        }
+    }
+
+    for (size_t i = 0; i < switchStatement.switchCases().size(); ++i) {
+        auto& firstCase = switchStatement.switchCases()[i];
+        for (size_t j = i + 1; j < switchStatement.switchCases().size(); ++j) {
+            auto& secondCase = switchStatement.switchCases()[j];
+            
+            if (static_cast<bool>(firstCase.value()) != static_cast<bool>(secondCase.value()))
+                continue;
+
+            if (!static_cast<bool>(firstCase.value())) {
+                setError();
+                return;
+            }
+
+            bool success = true;
+            firstCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& firstIntegerLiteral) {
+                secondCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& secondIntegerLiteral) {
+                    success = firstIntegerLiteral.value() != secondIntegerLiteral.value();
+                }, [&](AST::UnsignedIntegerLiteral& secondUnsignedIntegerLiteral) {
+                    success = static_cast<int64_t>(firstIntegerLiteral.value()) != static_cast<int64_t>(secondUnsignedIntegerLiteral.value());
+                }, [](auto&) {
+                }));
+            }, [&](AST::UnsignedIntegerLiteral& firstUnsignedIntegerLiteral) {
+                secondCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& secondIntegerLiteral) {
+                    success = static_cast<int64_t>(firstUnsignedIntegerLiteral.value()) != static_cast<int64_t>(secondIntegerLiteral.value());
+                }, [&](AST::UnsignedIntegerLiteral& secondUnsignedIntegerLiteral) {
+                    success = firstUnsignedIntegerLiteral.value() != secondUnsignedIntegerLiteral.value();
+                }, [](auto&) {
+                }));
+            }, [&](AST::EnumerationMemberLiteral& firstEnumerationMemberLiteral) {
+                secondCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral&) {
+                }, [&](AST::EnumerationMemberLiteral& secondEnumerationMemberLiteral) {
+                    ASSERT(firstEnumerationMemberLiteral.enumerationMember());
+                    ASSERT(secondEnumerationMemberLiteral.enumerationMember());
+                    success = firstEnumerationMemberLiteral.enumerationMember() != secondEnumerationMemberLiteral.enumerationMember();
+                }, [](auto&) {
+                }));
+            }, [](auto&) {
+            }));
+        }
+    }
+
+    if (!hasDefault) {
+        if (is<AST::NativeTypeDeclaration>(*valueType)) {
+            HashSet<int64_t> values;
+            bool zeroValueExists;
+            for (auto& switchCase : switchStatement.switchCases()) {
+                int64_t value;
+                switchCase.value()->visit(WTF::makeVisitor([&](AST::IntegerLiteral& integerLiteral) {
+                    value = integerLiteral.valueForSelectedType();
+                }, [&](AST::UnsignedIntegerLiteral& unsignedIntegerLiteral) {
+                    value = unsignedIntegerLiteral.valueForSelectedType();
+                }, [](auto&) {
+                    ASSERT_NOT_REACHED();
+                }));
+                if (!value)
+                    zeroValueExists = true;
+                else
+                    values.add(value);
+            }
+            bool success = true;
+            downcast<AST::NativeTypeDeclaration>(*valueType).iterateAllValues([&](int64_t value) -> bool {
+                if (!value) {
+                    if (!zeroValueExists) {
+                        success = false;
+                        return true;
+                    }
+                    return false;
+                }
+                if (!values.contains(value)) {
+                    success = false;
+                    return true;
+                }
+                return false;
+            });
+            if (!success) {
+                setError();
+                return;
+            }
+        } else {
+            ASSERT(is<AST::EnumerationDefinition>(*valueType));
+            HashSet<AST::EnumerationMember*> values;
+            for (auto& switchCase : switchStatement.switchCases()) {
+                switchCase.value()->visit(WTF::makeVisitor([&](AST::EnumerationMemberLiteral& enumerationMemberLiteral) {
+                    ASSERT(enumerationMemberLiteral.enumerationMember());
+                    values.add(enumerationMemberLiteral.enumerationMember());
+                }, [](auto&) {
+                    ASSERT_NOT_REACHED();
+                }));
+            }
+            for (auto& enumerationMember : downcast<AST::EnumerationDefinition>(*valueType).enumerationMembers()) {
+                if (!values.contains(&enumerationMember.get())) {
+                    setError();
+                    return;
+                }
+            }
+        }
+    }
+}
+
+void Checker::visit(AST::CommaExpression& commaExpression)
+{
+    ASSERT(commaExpression.list().size() > 0);
+    Visitor::visit(commaExpression);
+    if (error())
+        return;
+    auto lastInfo = getInfo(commaExpression.list().last());
+    forwardType(commaExpression, lastInfo->resolvingType);
+}
+
+void Checker::visit(AST::TernaryExpression& ternaryExpression)
+{
+    auto predicateInfo = recurseAndRequireBoolType(ternaryExpression.predicate());
+    if (!predicateInfo)
+        return;
+
+    auto bodyInfo = recurseAndGetInfo(ternaryExpression.bodyExpression());
+    auto elseInfo = recurseAndGetInfo(ternaryExpression.elseExpression());
+    
+    auto resultType = matchAndCommit(bodyInfo->resolvingType, elseInfo->resolvingType);
+    if (!resultType) {
+        setError();
+        return;
+    }
+
+    assignType(ternaryExpression, WTFMove(*resultType));
+}
+
+void Checker::visit(AST::CallExpression& callExpression)
+{
+    Vector<std::reference_wrapper<ResolvingType>> types;
+    types.reserveInitialCapacity(callExpression.arguments().size());
+    for (auto& argument : callExpression.arguments()) {
+        auto argumentInfo = recurseAndGetInfo(argument);
+        if (!argumentInfo)
+            return;
+        types.uncheckedAppend(argumentInfo->resolvingType);
+    }
+    if (callExpression.castReturnType()) {
+        checkErrorAndVisit(callExpression.castReturnType()->get());
+        if (error())
+            return;
+    }
+
+    ASSERT(callExpression.hasOverloads());
+    auto* function = resolveFunctionOverloadImpl(*callExpression.overloads(), types, callExpression.castReturnType());
+    if (!function) {
+        if (auto newFunction = resolveByInstantiation(callExpression, types, m_intrinsics)) {
+            m_program.append(WTFMove(*newFunction));
+            function = &m_program.nativeFunctionDeclarations().last();
+        }
+    }
+
+    if (!function) {
+        setError();
+        return;
+    }
+
+    for (size_t i = 0; i < function->parameters().size(); ++i) {
+        if (!matchAndCommit(types[i].get(), *function->parameters()[i].type())) {
+            setError();
+            return;
+        }
+    }
+
+    callExpression.setFunction(*function);
+
+    assignType(callExpression, function->type().clone());
+}
+
+bool check(Program& program)
+{
+    Checker checker(program.intrinsics(), program);
+    checker.checkErrorAndVisit(program);
+    if (checker.error())
+        return false;
+    return checker.assignTypes();
+}
+
+}
+
+}
+
+#endif
diff --git a/Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.h b/Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.h
new file mode 100644 (file)
index 0000000..f6f0857
--- /dev/null
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(WEBGPU)
+
+namespace WebCore {
+
+namespace WHLSL {
+
+class Program;
+
+bool check(Program&);
+
+}
+
+}
+
+#endif
diff --git a/Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp b/Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp
new file mode 100644 (file)
index 0000000..5bd54c9
--- /dev/null
@@ -0,0 +1,184 @@
+/*
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "WHLSLGatherEntryPointItems.h"
+
+#if ENABLE(WEBGPU)
+
+#include "WHLSLArrayReferenceType.h"
+#include "WHLSLArrayType.h"
+#include "WHLSLFunctionDefinition.h"
+#include "WHLSLInferTypes.h"
+#include "WHLSLIntrinsics.h"
+#include "WHLSLPointerType.h"
+#include "WHLSLStructureDefinition.h"
+#include "WHLSLTypeDefinition.h"
+#include "WHLSLTypeReference.h"
+#include "WHLSLVariableDeclaration.h"
+#include "WHLSLVisitor.h"
+#include <wtf/Optional.h>
+
+namespace WebCore {
+
+namespace WHLSL {
+
+class Gatherer : public Visitor {
+public:
+    Gatherer(const Intrinsics& intrinsics, AST::Semantic* semantic = nullptr)
+        : m_intrinsics(intrinsics)
+        , m_currentSemantic(semantic)
+    {
+    }
+
+    virtual ~Gatherer() = default;
+
+    void reset()
+    {
+        m_currentSemantic = nullptr;
+    }
+
+    Vector<EntryPointItem>&& takeEntryPointItems()
+    {
+        return WTFMove(m_entryPointItems);
+    }
+
+    void visit(AST::EnumerationDefinition&)
+    {
+        if (!m_currentSemantic) {
+            setError();
+            return;
+        }
+        m_entryPointItems.append(EntryPointItem(m_typeReferences.last().get(), *m_currentSemantic));
+    }
+
+    void visit(AST::NativeTypeDeclaration& nativeTypeDeclaration)
+    {
+        if (!m_currentSemantic) {
+            setError();
+            return;
+        }
+        if (matches(nativeTypeDeclaration, m_intrinsics.voidType())) {
+            setError();
+            return;
+        }
+
+        m_entryPointItems.append(EntryPointItem(m_typeReferences.last().get(), *m_currentSemantic));
+    }
+
+    void visit(AST::StructureDefinition& structureDefinition)
+    {
+        if (m_currentSemantic) {
+            setError();
+            return;
+        }
+
+        for (auto& structureElement : structureDefinition.structureElements()) {
+            if (structureElement.semantic())
+                m_currentSemantic = &*structureElement.semantic();
+            checkErrorAndVisit(structureElement);
+        }
+    }
+
+    void visit(AST::TypeDefinition& typeDefinition)
+    {
+        checkErrorAndVisit(typeDefinition.type());
+    }
+
+    void visit(AST::TypeReference& typeReference)
+    {
+        ASSERT(typeReference.resolvedType());
+        m_typeReferences.append(typeReference);
+        auto depth = m_typeReferences.size();
+        checkErrorAndVisit(*typeReference.resolvedType());
+        ASSERT_UNUSED(depth, m_typeReferences.size() == depth);
+    }
+
+    void visit(AST::PointerType& pointerType)
+    {
+        if (!m_currentSemantic) {
+            setError();
+            return;
+        }
+        m_entryPointItems.append(EntryPointItem(pointerType, *m_currentSemantic));
+    }
+
+    void visit(AST::ArrayReferenceType& arrayReferenceType)
+    {
+        if (!m_currentSemantic) {
+            setError();
+            return;
+        }
+        m_entryPointItems.append(EntryPointItem(arrayReferenceType, *m_currentSemantic));
+    }
+
+    void visit(AST::ArrayType& arrayType)
+    {
+        if (!m_currentSemantic) {
+            setError();
+            return;
+        }
+        m_entryPointItems.append(EntryPointItem(arrayType, *m_currentSemantic));
+    }
+
+    void visit(AST::VariableDeclaration& variableDeclaration)
+    {
+        ASSERT(!m_currentSemantic);
+        if (variableDeclaration.semantic())
+            m_currentSemantic = &*variableDeclaration.semantic();
+        if (variableDeclaration.type())
+            checkErrorAndVisit(*variableDeclaration.type());
+    }
+
+private:
+    const Intrinsics& m_intrinsics;
+    AST::Semantic* m_currentSemantic { nullptr };
+    Vector<std::reference_wrapper<AST::TypeReference>> m_typeReferences;
+    Vector<EntryPointItem> m_entryPointItems;
+};
+
+Optional<EntryPointItems> gatherEntryPointItems(const Intrinsics& intrinsics, AST::FunctionDefinition& functionDefinition)
+{
+    ASSERT(functionDefinition.entryPointType());
+    Gatherer inputGatherer(intrinsics);
+    for (auto& parameter : functionDefinition.parameters()) {
+        inputGatherer.reset();
+        inputGatherer.checkErrorAndVisit(parameter);
+        if (inputGatherer.error())
+            return WTF::nullopt;
+    }
+    Gatherer outputGatherer(intrinsics, functionDefinition.semantic() ? &*functionDefinition.semantic() : nullptr);
+    outputGatherer.checkErrorAndVisit(functionDefinition.type());
+    if (outputGatherer.error())
+        return WTF::nullopt;
+
+    return {{ inputGatherer.takeEntryPointItems(), outputGatherer.takeEntryPointItems() }};
+}
+
+}
+
+}
+
+#endif
diff --git a/Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.h b/Source/WebCore/Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.h
new file mode 100644 (file)
index 0000000..9d4f7dd
--- /dev/null
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(WEBGPU)
+
+#include "WHLSLSemantic.h"
+#include <wtf/Optional.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace WHLSL {
+
+namespace AST {
+
+class FunctionDefinition;
+
+}
+
+class Intrinsics;
+class UnnamedType;
+
+struct EntryPointItem {
+    EntryPointItem(AST::UnnamedType& unnamedType, AST::Semantic& semantic)
+        : unnamedType(unnamedType)
+        , semantic(semantic)
+    {
+    }
+
+    AST::UnnamedType& unnamedType;
+    AST::Semantic& semantic;
+};
+
+struct EntryPointItems {
+    Vector<EntryPointItem> inputs;
+    Vector<EntryPointItem> outputs;
+};
+
+Optional<EntryPointItems> gatherEntryPointItems(const Intrinsics&, AST::FunctionDefinition&);
+
+}
+
+}
+
+#endif
index 0d25635..63f0961 100644 (file)
@@ -309,6 +309,8 @@ Modules/webgpu/DOMWindowWebGPU.cpp
 Modules/webgpu/WHLSL/WHLSLInferTypes.cpp
 Modules/webgpu/WHLSL/WHLSLLexer.cpp
 Modules/webgpu/WHLSL/WHLSLParser.cpp
+Modules/webgpu/WHLSL/WHLSLChecker.cpp
+Modules/webgpu/WHLSL/WHLSLGatherEntryPointItems.cpp
 Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp
 Modules/webgpu/WHLSL/WHLSLRecursiveTypeChecker.cpp
 Modules/webgpu/WHLSL/WHLSLSynthesizeArrayOperatorLength.cpp
index f2f515a..93a4a53 100644 (file)
                1C66260F1C6E7CA600AB527C /* FontFace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontFace.h; sourceTree = "<group>"; };
                1C81B9560E97330800266E07 /* InspectorController.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InspectorController.h; sourceTree = "<group>"; };
                1C81B9570E97330800266E07 /* InspectorController.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InspectorController.cpp; sourceTree = "<group>"; };
+               1C840B9721EC400700D0500D /* WHLSLChecker.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WHLSLChecker.h; sourceTree = "<group>"; };
+               1C840B9921EC400800D0500D /* WHLSLGatherEntryPointItems.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = WHLSLGatherEntryPointItems.cpp; sourceTree = "<group>"; };
+               1C840B9A21EC400900D0500D /* WHLSLGatherEntryPointItems.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WHLSLGatherEntryPointItems.h; sourceTree = "<group>"; };
+               1C840B9B21EC400900D0500D /* WHLSLChecker.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = WHLSLChecker.cpp; sourceTree = "<group>"; };
                1C81B9580E97330800266E07 /* InspectorClient.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InspectorClient.h; sourceTree = "<group>"; };
                1C840B7D21EBE0B800D0500D /* WHLSLEntryPointType.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WHLSLEntryPointType.h; sourceTree = "<group>"; };
                1C840B9021EC30F900D0500D /* WHLSLAddressSpace.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WHLSLAddressSpace.h; sourceTree = "<group>"; };
                                C21BF6F121CD898D00227979 /* AST */,
                                C234A9B221E92C1F003C984D /* WHLSLCheckDuplicateFunctions.cpp */,
                                C234A9AE21E92C1A003C984D /* WHLSLCheckDuplicateFunctions.h */,
+                               1C840B9B21EC400900D0500D /* WHLSLChecker.cpp */,
+                               1C840B9721EC400700D0500D /* WHLSLChecker.h */,
+                               1C840B9921EC400800D0500D /* WHLSLGatherEntryPointItems.cpp */,
+                               1C840B9A21EC400900D0500D /* WHLSLGatherEntryPointItems.h */,
                                C234A99A21E90F56003C984D /* WHLSLInferTypes.cpp */,
                                C234A99B21E90F57003C984D /* WHLSLInferTypes.h */,
                                C234A9B721E92CC1003C984D /* WHLSLIntrinsics.cpp */,