// Copyright 2020 The Tint Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SRC_TINT_RESOLVER_RESOLVER_H_
#define SRC_TINT_RESOLVER_RESOLVER_H_

#include <memory>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "src/tint/builtin_table.h"
#include "src/tint/program_builder.h"
#include "src/tint/resolver/dependency_graph.h"
#include "src/tint/resolver/sem_helper.h"
#include "src/tint/resolver/validator.h"
#include "src/tint/scope_stack.h"
#include "src/tint/sem/binding_point.h"
#include "src/tint/sem/block_statement.h"
#include "src/tint/sem/constant.h"
#include "src/tint/sem/function.h"
#include "src/tint/sem/struct.h"
#include "src/tint/utils/unique_vector.h"

// Forward declarations
namespace tint::ast {
class IndexAccessorExpression;
class BinaryExpression;
class BitcastExpression;
class CallExpression;
class CallStatement;
class CaseStatement;
class ForLoopStatement;
class Function;
class IdentifierExpression;
class LoopStatement;
class MemberAccessorExpression;
class ReturnStatement;
class SwitchStatement;
class UnaryOpExpression;
class Variable;
}  // namespace tint::ast
namespace tint::sem {
class Array;
class Atomic;
class BlockStatement;
class Builtin;
class CaseStatement;
class ForLoopStatement;
class IfStatement;
class LoopStatement;
class Statement;
class SwitchStatement;
class TypeConstructor;
}  // namespace tint::sem

namespace tint::resolver {

/// Resolves types for all items in the given tint program
class Resolver {
  public:
    /// Constructor
    /// @param builder the program builder
    explicit Resolver(ProgramBuilder* builder);

    /// Destructor
    ~Resolver();

    /// @returns error messages from the resolver
    std::string error() const { return diagnostics_.str(); }

    /// @returns true if the resolver was successful
    bool Resolve();

    /// @param type the given type
    /// @returns true if the given type is a plain type
    bool IsPlain(const sem::Type* type) const { return validator_.IsPlain(type); }

    /// @param type the given type
    /// @returns true if the given type is a fixed-footprint type
    bool IsFixedFootprint(const sem::Type* type) const { return validator_.IsFixedFootprint(type); }

    /// @param type the given type
    /// @returns true if the given type is storable
    bool IsStorable(const sem::Type* type) const { return validator_.IsStorable(type); }

    /// @param type the given type
    /// @returns true if the given type is host-shareable
    bool IsHostShareable(const sem::Type* type) const { return validator_.IsHostShareable(type); }

    /// @returns the validator for testing
    const Validator* GetValidatorForTesting() const { return &validator_; }

  private:
    /// Describes the context in which a variable is declared
    enum class VariableKind { kParameter, kLocal, kGlobal };

    Validator::ValidTypeStorageLayouts valid_type_storage_layouts_;

    /// Structure holding semantic information about a block (i.e. scope), such as
    /// parent block and variables declared in the block.
    /// Used to validate variable scoping rules.
    struct BlockInfo {
        enum class Type { kGeneric, kLoop, kLoopContinuing, kSwitchCase };

        BlockInfo(const ast::BlockStatement* block, Type type, BlockInfo* parent);
        ~BlockInfo();

        template <typename Pred>
        BlockInfo* FindFirstParent(Pred&& pred) {
            BlockInfo* curr = this;
            while (curr && !pred(curr)) {
                curr = curr->parent;
            }
            return curr;
        }

        BlockInfo* FindFirstParent(BlockInfo::Type ty) {
            return FindFirstParent([ty](auto* block_info) { return block_info->type == ty; });
        }

        ast::BlockStatement const* const block;
        const Type type;
        BlockInfo* const parent;
        std::vector<const ast::Variable*> decls;

        // first_continue is set to the index of the first variable in decls
        // declared after the first continue statement in a loop block, if any.
        constexpr static size_t kNoContinue = size_t(~0);
        size_t first_continue = kNoContinue;
    };

    // Structure holding information for a TypeDecl
    struct TypeDeclInfo {
        ast::TypeDecl const* const ast;
        sem::Type* const sem;
    };

    /// Resolves the program, without creating final the semantic nodes.
    /// @returns true on success, false on error
    bool ResolveInternal();

    /// Creates the nodes and adds them to the sem::Info mappings of the
    /// ProgramBuilder.
    void CreateSemanticNodes() const;

    /// Retrieves information for the requested import.
    /// @param src the source of the import
    /// @param path the import path
    /// @param name the method name to get information on
    /// @param params the parameters to the method call
    /// @param id out parameter for the external call ID. Must not be a nullptr.
    /// @returns the return type of `name` in `path` or nullptr on error.
    sem::Type* GetImportData(const Source& src,
                             const std::string& path,
                             const std::string& name,
                             const ast::ExpressionList& params,
                             uint32_t* id);

    //////////////////////////////////////////////////////////////////////////////
    // AST and Type traversal methods
    //////////////////////////////////////////////////////////////////////////////

    // Expression resolving methods
    // Returns the semantic node pointer on success, nullptr on failure.
    sem::Expression* IndexAccessor(const ast::IndexAccessorExpression*);
    sem::Expression* Binary(const ast::BinaryExpression*);
    sem::Expression* Bitcast(const ast::BitcastExpression*);
    sem::Call* Call(const ast::CallExpression*);
    sem::Expression* Expression(const ast::Expression*);
    sem::Function* Function(const ast::Function*);
    sem::Call* FunctionCall(const ast::CallExpression*,
                            sem::Function* target,
                            const std::vector<const sem::Expression*> args,
                            sem::Behaviors arg_behaviors);
    sem::Expression* Identifier(const ast::IdentifierExpression*);
    sem::Call* BuiltinCall(const ast::CallExpression*,
                           sem::BuiltinType,
                           const std::vector<const sem::Expression*> args,
                           const std::vector<const sem::Type*> arg_tys);
    sem::Expression* Literal(const ast::LiteralExpression*);
    sem::Expression* MemberAccessor(const ast::MemberAccessorExpression*);
    sem::Call* TypeConversion(const ast::CallExpression* expr,
                              const sem::Type* ty,
                              const sem::Expression* arg,
                              const sem::Type* arg_ty);
    sem::Call* TypeConstructor(const ast::CallExpression* expr,
                               const sem::Type* ty,
                               const std::vector<const sem::Expression*> args,
                               const std::vector<const sem::Type*> arg_tys);
    sem::Expression* UnaryOp(const ast::UnaryOpExpression*);

    // Statement resolving methods
    // Each return true on success, false on failure.
    sem::Statement* AssignmentStatement(const ast::AssignmentStatement*);
    sem::BlockStatement* BlockStatement(const ast::BlockStatement*);
    sem::Statement* BreakStatement(const ast::BreakStatement*);
    sem::Statement* CallStatement(const ast::CallStatement*);
    sem::CaseStatement* CaseStatement(const ast::CaseStatement*);
    sem::Statement* CompoundAssignmentStatement(const ast::CompoundAssignmentStatement*);
    sem::Statement* ContinueStatement(const ast::ContinueStatement*);
    sem::Statement* DiscardStatement(const ast::DiscardStatement*);
    sem::Statement* FallthroughStatement(const ast::FallthroughStatement*);
    sem::ForLoopStatement* ForLoopStatement(const ast::ForLoopStatement*);
    sem::GlobalVariable* GlobalVariable(const ast::Variable*);
    sem::Statement* Parameter(const ast::Variable*);
    sem::IfStatement* IfStatement(const ast::IfStatement*);
    sem::Statement* IncrementDecrementStatement(const ast::IncrementDecrementStatement*);
    sem::LoopStatement* LoopStatement(const ast::LoopStatement*);
    sem::Statement* ReturnStatement(const ast::ReturnStatement*);
    sem::Statement* Statement(const ast::Statement*);
    sem::SwitchStatement* SwitchStatement(const ast::SwitchStatement* s);
    sem::Statement* VariableDeclStatement(const ast::VariableDeclStatement*);
    bool Statements(const ast::StatementList&);

    // Resolve the result type of a binary operator.
    // Returns nullptr if the types are not valid for this operator.
    const sem::Type* BinaryOpType(const sem::Type* lhs_ty,
                                  const sem::Type* rhs_ty,
                                  ast::BinaryOp op);

    /// Resolves the WorkgroupSize for the given function, assigning it to
    /// current_function_
    bool WorkgroupSize(const ast::Function*);

    /// @returns the sem::Type for the ast::Type `ty`, building it if it
    /// hasn't been constructed already. If an error is raised, nullptr is
    /// returned.
    /// @param ty the ast::Type
    sem::Type* Type(const ast::Type* ty);

    /// @param named_type the named type to resolve
    /// @returns the resolved semantic type
    sem::Type* TypeDecl(const ast::TypeDecl* named_type);

    /// Builds and returns the semantic information for the array `arr`.
    /// This method does not mark the ast::Array node, nor attach the generated
    /// semantic information to the AST node.
    /// @returns the semantic Array information, or nullptr if an error is
    /// raised.
    /// @param arr the Array to get semantic information for
    sem::Array* Array(const ast::Array* arr);

    /// Builds and returns the semantic information for the alias `alias`.
    /// This method does not mark the ast::Alias node, nor attach the generated
    /// semantic information to the AST node.
    /// @returns the aliased type, or nullptr if an error is raised.
    sem::Type* Alias(const ast::Alias* alias);

    /// Builds and returns the semantic information for the structure `str`.
    /// This method does not mark the ast::Struct node, nor attach the generated
    /// semantic information to the AST node.
    /// @returns the semantic Struct information, or nullptr if an error is
    /// raised.
    sem::Struct* Structure(const ast::Struct* str);

    /// @returns the semantic info for the variable `var`. If an error is
    /// raised, nullptr is returned.
    /// @note this method does not resolve the attributes as these are
    /// context-dependent (global, local, parameter)
    /// @param var the variable to create or return the `VariableInfo` for
    /// @param kind what kind of variable we are declaring
    /// @param index the index of the parameter, if this variable is a parameter
    sem::Variable* Variable(const ast::Variable* var, VariableKind kind, uint32_t index = 0);

    /// Records the storage class usage for the given type, and any transient
    /// dependencies of the type. Validates that the type can be used for the
    /// given storage class, erroring if it cannot.
    /// @param sc the storage class to apply to the type and transitent types
    /// @param ty the type to apply the storage class on
    /// @param usage the Source of the root variable declaration that uses the
    /// given type and storage class. Used for generating sensible error
    /// messages.
    /// @returns true on success, false on error
    bool ApplyStorageClassUsageToType(ast::StorageClass sc, sem::Type* ty, const Source& usage);

    /// @param storage_class the storage class
    /// @returns the default access control for the given storage class
    ast::Access DefaultAccessForStorageClass(ast::StorageClass storage_class);

    /// Allocate constant IDs for pipeline-overridable constants.
    void AllocateOverridableConstantIds();

    /// Set the shadowing information on variable declarations.
    /// @note this method must only be called after all semantic nodes are built.
    void SetShadows();
    /// StatementScope() does the following:
    /// * Creates the AST -> SEM mapping.
    /// * Assigns `sem` to #current_statement_
    /// * Assigns `sem` to #current_compound_statement_ if `sem` derives from
    ///   sem::CompoundStatement.
    /// * Assigns `sem` to #current_block_ if `sem` derives from
    ///   sem::BlockStatement.
    /// * Then calls `callback`.
    /// * Before returning #current_statement_, #current_compound_statement_, and
    ///   #current_block_ are restored to their original values.
    /// @returns `sem` if `callback` returns true, otherwise `nullptr`.
    template <typename SEM, typename F>
    SEM* StatementScope(const ast::Statement* ast, SEM* sem, F&& callback);

    /// Mark records that the given AST node has been visited, and asserts that
    /// the given node has not already been seen. Diamonds in the AST are
    /// illegal.
    /// @param node the AST node.
    /// @returns true on success, false on error
    bool Mark(const ast::Node* node);

    /// Adds the given error message to the diagnostics
    void AddError(const std::string& msg, const Source& source) const;

    /// Adds the given warning message to the diagnostics
    void AddWarning(const std::string& msg, const Source& source) const;

    /// Adds the given note message to the diagnostics
    void AddNote(const std::string& msg, const Source& source) const;

    //////////////////////////////////////////////////////////////////////////////
    /// Constant value evaluation methods
    //////////////////////////////////////////////////////////////////////////////
    /// Cast `Value` to `target_type`
    /// @return the casted value
    sem::Constant ConstantCast(const sem::Constant& value, const sem::Type* target_elem_type);

    sem::Constant EvaluateConstantValue(const ast::Expression* expr, const sem::Type* type);
    sem::Constant EvaluateConstantValue(const ast::LiteralExpression* literal,
                                        const sem::Type* type);
    sem::Constant EvaluateConstantValue(const ast::CallExpression* call, const sem::Type* type);

    /// @returns true if the symbol is the name of a builtin function.
    bool IsBuiltin(Symbol) const;

    /// @returns true if `expr` is the current CallStatement's CallExpression
    bool IsCallStatement(const ast::Expression* expr) const;

    struct TypeConversionSig {
        const sem::Type* target;
        const sem::Type* source;

        bool operator==(const TypeConversionSig&) const;

        /// Hasher provides a hash function for the TypeConversionSig
        struct Hasher {
            /// @param sig the TypeConversionSig to create a hash for
            /// @return the hash value
            std::size_t operator()(const TypeConversionSig& sig) const;
        };
    };

    struct TypeConstructorSig {
        const sem::Type* type;
        const std::vector<const sem::Type*> parameters;

        TypeConstructorSig(const sem::Type* ty, const std::vector<const sem::Type*> params);
        TypeConstructorSig(const TypeConstructorSig&);
        ~TypeConstructorSig();
        bool operator==(const TypeConstructorSig&) const;

        /// Hasher provides a hash function for the TypeConstructorSig
        struct Hasher {
            /// @param sig the TypeConstructorSig to create a hash for
            /// @return the hash value
            std::size_t operator()(const TypeConstructorSig& sig) const;
        };
    };

    ProgramBuilder* const builder_;
    diag::List& diagnostics_;
    std::unique_ptr<BuiltinTable> const builtin_table_;
    DependencyGraph dependencies_;
    SemHelper sem_;
    Validator validator_;
    std::vector<sem::Function*> entry_points_;
    std::unordered_map<const sem::Type*, const Source&> atomic_composite_info_;
    std::unordered_set<const ast::Node*> marked_;
    std::unordered_map<uint32_t, const sem::Variable*> constant_ids_;
    std::unordered_map<TypeConversionSig, sem::CallTarget*, TypeConversionSig::Hasher>
        type_conversions_;
    std::unordered_map<TypeConstructorSig, sem::CallTarget*, TypeConstructorSig::Hasher>
        type_ctors_;

    sem::Function* current_function_ = nullptr;
    sem::Statement* current_statement_ = nullptr;
    sem::CompoundStatement* current_compound_statement_ = nullptr;
    sem::BlockStatement* current_block_ = nullptr;
};

}  // namespace tint::resolver

#endif  // SRC_TINT_RESOLVER_RESOLVER_H_