// Copyright 2021 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.

#include "src/tint/builtin_table.h"

#include <algorithm>
#include <limits>
#include <unordered_map>
#include <utility>

#include "src/tint/program_builder.h"
#include "src/tint/sem/atomic_type.h"
#include "src/tint/sem/depth_multisampled_texture_type.h"
#include "src/tint/sem/depth_texture_type.h"
#include "src/tint/sem/external_texture_type.h"
#include "src/tint/sem/multisampled_texture_type.h"
#include "src/tint/sem/pipeline_stage_set.h"
#include "src/tint/sem/sampled_texture_type.h"
#include "src/tint/sem/storage_texture_type.h"
#include "src/tint/utils/hash.h"
#include "src/tint/utils/map.h"
#include "src/tint/utils/math.h"
#include "src/tint/utils/scoped_assignment.h"

namespace tint {
namespace {

// Forward declarations
struct OverloadInfo;
class Matchers;
class NumberMatcher;
class TypeMatcher;

/// A special type that matches all TypeMatchers
class Any : public Castable<Any, sem::Type> {
 public:
  Any() = default;
  ~Any() override = default;

  // Stub implementations for sem::Type conformance.
  size_t Hash() const override { return 0; }
  bool Equals(const sem::Type&) const override { return false; }

  std::string type_name() const override { return "<any>"; }
  std::string FriendlyName(const SymbolTable&) const override {
    return "<any>";
  }
};

/// Number is an 32 bit unsigned integer, which can be in one of three states:
/// * Invalid - Number has not been assigned a value
/// * Valid   - a fixed integer value
/// * Any     - matches any other non-invalid number
struct Number {
  static const Number any;
  static const Number invalid;

  /// Constructed as a valid number with the value v
  explicit Number(uint32_t v) : value_(v), state_(kValid) {}

  /// @returns the value of the number
  inline uint32_t Value() const { return value_; }

  /// @returns the true if the number is valid
  inline bool IsValid() const { return state_ == kValid; }

  /// @returns the true if the number is any
  inline bool IsAny() const { return state_ == kAny; }

  /// Assignment operator.
  /// The number becomes valid, with the value n
  inline Number& operator=(uint32_t n) {
    value_ = n;
    state_ = kValid;
    return *this;
  }

 private:
  enum State {
    kInvalid,
    kValid,
    kAny,
  };

  constexpr explicit Number(State state) : state_(state) {}

  uint32_t value_ = 0;
  State state_ = kInvalid;
};

const Number Number::any{Number::kAny};
const Number Number::invalid{Number::kInvalid};

/// ClosedState holds the state of the open / closed numbers and types.
/// Used by the MatchState.
class ClosedState {
 public:
  explicit ClosedState(ProgramBuilder& b) : builder(b) {}

  /// If the type with index `idx` is open, then it is closed with type `ty` and
  /// Type() returns true. If the type is closed, then `Type()` returns true iff
  /// it is equal to `ty`.
  bool Type(uint32_t idx, const sem::Type* ty) {
    auto res = types_.emplace(idx, ty);
    return res.second || res.first->second == ty;
  }

  /// If the number with index `idx` is open, then it is closed with number
  /// `number` and Num() returns true. If the number is closed, then `Num()`
  /// returns true iff it is equal to `ty`.
  bool Num(uint32_t idx, Number number) {
    auto res = numbers_.emplace(idx, number.Value());
    return res.second || res.first->second == number.Value();
  }

  /// Type returns the closed type with index `idx`.
  /// An ICE is raised if the type is not closed.
  const sem::Type* Type(uint32_t idx) const {
    auto it = types_.find(idx);
    if (it == types_.end()) {
      TINT_ICE(Resolver, builder.Diagnostics())
          << "type with index " << idx << " is not closed";
      return nullptr;
    }
    TINT_ASSERT(Resolver, it != types_.end());
    return it->second;
  }

  /// Type returns the number type with index `idx`.
  /// An ICE is raised if the number is not closed.
  Number Num(uint32_t idx) const {
    auto it = numbers_.find(idx);
    if (it == numbers_.end()) {
      TINT_ICE(Resolver, builder.Diagnostics())
          << "number with index " << idx << " is not closed";
      return Number::invalid;
    }
    return Number(it->second);
  }

 private:
  ProgramBuilder& builder;
  std::unordered_map<uint32_t, const sem::Type*> types_;
  std::unordered_map<uint32_t, uint32_t> numbers_;
};

/// Index type used for matcher indices
using MatcherIndex = uint8_t;

/// Index value used for open types / numbers that do not have a constraint
constexpr MatcherIndex kNoMatcher = std::numeric_limits<MatcherIndex>::max();

/// MatchState holds the state used to match an overload.
class MatchState {
 public:
  MatchState(ProgramBuilder& b,
             ClosedState& c,
             const Matchers& m,
             const OverloadInfo& o,
             MatcherIndex const* matcher_indices)
      : builder(b),
        closed(c),
        matchers(m),
        overload(o),
        matcher_indices_(matcher_indices) {}

  /// The program builder
  ProgramBuilder& builder;
  /// The open / closed types and numbers
  ClosedState& closed;
  /// The type and number matchers
  Matchers const& matchers;
  /// The current overload being evaluated
  OverloadInfo const& overload;

  /// Type uses the next TypeMatcher from the matcher indices to match the type
  /// `ty`. If the type matches, the canonical expected type is returned. If the
  /// type `ty` does not match, then nullptr is returned.
  /// @note: The matcher indices are progressed on calling.
  const sem::Type* Type(const sem::Type* ty);

  /// Num uses the next NumMatcher from the matcher indices to match the number
  /// `num`. If the number matches, the canonical expected number is returned.
  /// If the number `num` does not match, then an invalid number is returned.
  /// @note: The matcher indices are progressed on calling.
  Number Num(Number num);

  /// @returns a string representation of the next TypeMatcher from the matcher
  /// indices.
  /// @note: The matcher indices are progressed on calling.
  std::string TypeName();

  /// @returns a string representation of the next NumberMatcher from the
  /// matcher indices.
  /// @note: The matcher indices are progressed on calling.
  std::string NumName();

 private:
  MatcherIndex const* matcher_indices_ = nullptr;
};

/// A TypeMatcher is the interface used to match an type used as part of an
/// overload's parameter or return type.
class TypeMatcher {
 public:
  /// Destructor
  virtual ~TypeMatcher() = default;

  /// Checks whether the given type matches the matcher rules, and returns the
  /// expected, canonicalized type on success.
  /// Match may close open types and numbers in state.
  /// @param type the type to match
  /// @returns the canonicalized type on match, otherwise nullptr
  virtual const sem::Type* Match(MatchState& state,
                                 const sem::Type* type) const = 0;

  /// @return a string representation of the matcher. Used for printing error
  /// messages when no overload is found.
  virtual std::string String(MatchState& state) const = 0;
};

/// A NumberMatcher is the interface used to match a number or enumerator used
/// as part of an overload's parameter or return type.
class NumberMatcher {
 public:
  /// Destructor
  virtual ~NumberMatcher() = default;

  /// Checks whether the given number matches the matcher rules.
  /// Match may close open numbers in state.
  /// @param number the number to match
  /// @returns true if the argument type is as expected.
  virtual Number Match(MatchState& state, Number number) const = 0;

  /// @return a string representation of the matcher. Used for printing error
  /// messages when no overload is found.
  virtual std::string String(MatchState& state) const = 0;
};

/// OpenTypeMatcher is a Matcher for an open type.
/// The OpenTypeMatcher will match against any type (so long as it is consistent
/// across all uses in the overload)
class OpenTypeMatcher : public TypeMatcher {
 public:
  /// Constructor
  explicit OpenTypeMatcher(uint32_t index) : index_(index) {}

  const sem::Type* Match(MatchState& state,
                         const sem::Type* type) const override {
    if (type->Is<Any>()) {
      return state.closed.Type(index_);
    }
    return state.closed.Type(index_, type) ? type : nullptr;
  }

  std::string String(MatchState& state) const override;

 private:
  uint32_t index_;
};

/// OpenNumberMatcher is a Matcher for an open number.
/// The OpenNumberMatcher will match against any number (so long as it is
/// consistent for the overload)
class OpenNumberMatcher : public NumberMatcher {
 public:
  explicit OpenNumberMatcher(uint32_t index) : index_(index) {}

  Number Match(MatchState& state, Number number) const override {
    if (number.IsAny()) {
      return state.closed.Num(index_);
    }
    return state.closed.Num(index_, number) ? number : Number::invalid;
  }

  std::string String(MatchState& state) const override;

 private:
  uint32_t index_;
};

////////////////////////////////////////////////////////////////////////////////
// Binding functions for use in the generated builtin_table.inl
// TODO(bclayton): See if we can move more of this hand-rolled code to the
// template
////////////////////////////////////////////////////////////////////////////////
using TexelFormat = ast::TexelFormat;
using Access = ast::Access;
using StorageClass = ast::StorageClass;
using ParameterUsage = sem::ParameterUsage;
using PipelineStageSet = sem::PipelineStageSet;
using PipelineStage = ast::PipelineStage;

bool match_bool(const sem::Type* ty) {
  return ty->IsAnyOf<Any, sem::Bool>();
}

const sem::Bool* build_bool(MatchState& state) {
  return state.builder.create<sem::Bool>();
}

bool match_f32(const sem::Type* ty) {
  return ty->IsAnyOf<Any, sem::F32>();
}

const sem::I32* build_i32(MatchState& state) {
  return state.builder.create<sem::I32>();
}

bool match_i32(const sem::Type* ty) {
  return ty->IsAnyOf<Any, sem::I32>();
}

const sem::U32* build_u32(MatchState& state) {
  return state.builder.create<sem::U32>();
}

bool match_u32(const sem::Type* ty) {
  return ty->IsAnyOf<Any, sem::U32>();
}

const sem::F32* build_f32(MatchState& state) {
  return state.builder.create<sem::F32>();
}

bool match_vec(const sem::Type* ty, Number& N, const sem::Type*& T) {
  if (ty->Is<Any>()) {
    N = Number::any;
    T = ty;
    return true;
  }

  if (auto* v = ty->As<sem::Vector>()) {
    N = v->Width();
    T = v->type();
    return true;
  }
  return false;
}

const sem::Vector* build_vec(MatchState& state, Number N, const sem::Type* el) {
  return state.builder.create<sem::Vector>(el, N.Value());
}

template <int N>
bool match_vec(const sem::Type* ty, const sem::Type*& T) {
  if (ty->Is<Any>()) {
    T = ty;
    return true;
  }

  if (auto* v = ty->As<sem::Vector>()) {
    if (v->Width() == N) {
      T = v->type();
      return true;
    }
  }
  return false;
}

bool match_vec2(const sem::Type* ty, const sem::Type*& T) {
  return match_vec<2>(ty, T);
}

const sem::Vector* build_vec2(MatchState& state, const sem::Type* T) {
  return build_vec(state, Number(2), T);
}

bool match_vec3(const sem::Type* ty, const sem::Type*& T) {
  return match_vec<3>(ty, T);
}

const sem::Vector* build_vec3(MatchState& state, const sem::Type* T) {
  return build_vec(state, Number(3), T);
}

bool match_vec4(const sem::Type* ty, const sem::Type*& T) {
  return match_vec<4>(ty, T);
}

const sem::Vector* build_vec4(MatchState& state, const sem::Type* T) {
  return build_vec(state, Number(4), T);
}

bool match_mat(const sem::Type* ty, Number& M, Number& N, const sem::Type*& T) {
  if (ty->Is<Any>()) {
    M = Number::any;
    N = Number::any;
    T = ty;
    return true;
  }
  if (auto* m = ty->As<sem::Matrix>()) {
    M = m->columns();
    N = m->ColumnType()->Width();
    T = m->type();
    return true;
  }
  return false;
}

const sem::Matrix* build_mat(MatchState& state,
                             Number N,
                             Number M,
                             const sem::Type* T) {
  auto* column_type = state.builder.create<sem::Vector>(T, M.Value());
  return state.builder.create<sem::Matrix>(column_type, N.Value());
}

bool match_array(const sem::Type* ty, const sem::Type*& T) {
  if (ty->Is<Any>()) {
    T = ty;
    return true;
  }

  if (auto* a = ty->As<sem::Array>()) {
    if (a->Count() == 0) {
      T = a->ElemType();
      return true;
    }
  }
  return false;
}

const sem::Array* build_array(MatchState& state, const sem::Type* el) {
  return state.builder.create<sem::Array>(el,
                                          /* count */ 0u,
                                          /* align */ 0u,
                                          /* size */ 0u,
                                          /* stride */ 0u,
                                          /* stride_implicit */ 0u);
}

bool match_ptr(const sem::Type* ty, Number& S, const sem::Type*& T, Number& A) {
  if (ty->Is<Any>()) {
    S = Number::any;
    T = ty;
    A = Number::any;
    return true;
  }

  if (auto* p = ty->As<sem::Pointer>()) {
    S = Number(static_cast<uint32_t>(p->StorageClass()));
    T = p->StoreType();
    A = Number(static_cast<uint32_t>(p->Access()));
    return true;
  }
  return false;
}

const sem::Pointer* build_ptr(MatchState& state,
                              Number S,
                              const sem::Type* T,
                              Number& A) {
  return state.builder.create<sem::Pointer>(
      T, static_cast<ast::StorageClass>(S.Value()),
      static_cast<ast::Access>(A.Value()));
}

bool match_atomic(const sem::Type* ty, const sem::Type*& T) {
  if (ty->Is<Any>()) {
    T = ty;
    return true;
  }

  if (auto* a = ty->As<sem::Atomic>()) {
    T = a->Type();
    return true;
  }
  return false;
}

const sem::Atomic* build_atomic(MatchState& state, const sem::Type* T) {
  return state.builder.create<sem::Atomic>(T);
}

bool match_sampler(const sem::Type* ty) {
  if (ty->Is<Any>()) {
    return true;
  }
  return ty->Is([](const sem::Sampler* s) {
    return s->kind() == ast::SamplerKind::kSampler;
  });
}

const sem::Sampler* build_sampler(MatchState& state) {
  return state.builder.create<sem::Sampler>(ast::SamplerKind::kSampler);
}

bool match_sampler_comparison(const sem::Type* ty) {
  if (ty->Is<Any>()) {
    return true;
  }
  return ty->Is([](const sem::Sampler* s) {
    return s->kind() == ast::SamplerKind::kComparisonSampler;
  });
}

const sem::Sampler* build_sampler_comparison(MatchState& state) {
  return state.builder.create<sem::Sampler>(
      ast::SamplerKind::kComparisonSampler);
}

bool match_texture(const sem::Type* ty,
                   ast::TextureDimension dim,
                   const sem::Type*& T) {
  if (ty->Is<Any>()) {
    T = ty;
    return true;
  }
  if (auto* v = ty->As<sem::SampledTexture>()) {
    if (v->dim() == dim) {
      T = v->type();
      return true;
    }
  }
  return false;
}

#define JOIN(a, b) a##b

#define DECLARE_SAMPLED_TEXTURE(suffix, dim)                  \
  bool JOIN(match_texture_, suffix)(const sem::Type* ty,      \
                                    const sem::Type*& T) {    \
    return match_texture(ty, dim, T);                         \
  }                                                           \
  const sem::SampledTexture* JOIN(build_texture_, suffix)(    \
      MatchState & state, const sem::Type* T) {               \
    return state.builder.create<sem::SampledTexture>(dim, T); \
  }

DECLARE_SAMPLED_TEXTURE(1d, ast::TextureDimension::k1d)
DECLARE_SAMPLED_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_SAMPLED_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_SAMPLED_TEXTURE(3d, ast::TextureDimension::k3d)
DECLARE_SAMPLED_TEXTURE(cube, ast::TextureDimension::kCube)
DECLARE_SAMPLED_TEXTURE(cube_array, ast::TextureDimension::kCubeArray)
#undef DECLARE_SAMPLED_TEXTURE

bool match_texture_multisampled(const sem::Type* ty,
                                ast::TextureDimension dim,
                                const sem::Type*& T) {
  if (ty->Is<Any>()) {
    T = ty;
    return true;
  }
  if (auto* v = ty->As<sem::MultisampledTexture>()) {
    if (v->dim() == dim) {
      T = v->type();
      return true;
    }
  }
  return false;
}

#define DECLARE_MULTISAMPLED_TEXTURE(suffix, dim)                            \
  bool JOIN(match_texture_multisampled_, suffix)(const sem::Type* ty,        \
                                                 const sem::Type*& T) {      \
    return match_texture_multisampled(ty, dim, T);                           \
  }                                                                          \
  const sem::MultisampledTexture* JOIN(build_texture_multisampled_, suffix)( \
      MatchState & state, const sem::Type* T) {                              \
    return state.builder.create<sem::MultisampledTexture>(dim, T);           \
  }

DECLARE_MULTISAMPLED_TEXTURE(2d, ast::TextureDimension::k2d)
#undef DECLARE_MULTISAMPLED_TEXTURE

bool match_texture_depth(const sem::Type* ty, ast::TextureDimension dim) {
  if (ty->Is<Any>()) {
    return true;
  }
  return ty->Is([&](const sem::DepthTexture* t) { return t->dim() == dim; });
}

#define DECLARE_DEPTH_TEXTURE(suffix, dim)                       \
  bool JOIN(match_texture_depth_, suffix)(const sem::Type* ty) { \
    return match_texture_depth(ty, dim);                         \
  }                                                              \
  const sem::DepthTexture* JOIN(build_texture_depth_,            \
                                suffix)(MatchState & state) {    \
    return state.builder.create<sem::DepthTexture>(dim);         \
  }

DECLARE_DEPTH_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_DEPTH_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_DEPTH_TEXTURE(cube, ast::TextureDimension::kCube)
DECLARE_DEPTH_TEXTURE(cube_array, ast::TextureDimension::kCubeArray)
#undef DECLARE_DEPTH_TEXTURE

bool match_texture_depth_multisampled_2d(const sem::Type* ty) {
  if (ty->Is<Any>()) {
    return true;
  }
  return ty->Is([&](const sem::DepthMultisampledTexture* t) {
    return t->dim() == ast::TextureDimension::k2d;
  });
}

sem::DepthMultisampledTexture* build_texture_depth_multisampled_2d(
    MatchState& state) {
  return state.builder.create<sem::DepthMultisampledTexture>(
      ast::TextureDimension::k2d);
}

bool match_texture_storage(const sem::Type* ty,
                           ast::TextureDimension dim,
                           Number& F,
                           Number& A) {
  if (ty->Is<Any>()) {
    F = Number::any;
    A = Number::any;
    return true;
  }
  if (auto* v = ty->As<sem::StorageTexture>()) {
    if (v->dim() == dim) {
      F = Number(static_cast<uint32_t>(v->texel_format()));
      A = Number(static_cast<uint32_t>(v->access()));
      return true;
    }
  }
  return false;
}

#define DECLARE_STORAGE_TEXTURE(suffix, dim)                                  \
  bool JOIN(match_texture_storage_, suffix)(const sem::Type* ty, Number& F,   \
                                            Number& A) {                      \
    return match_texture_storage(ty, dim, F, A);                              \
  }                                                                           \
  const sem::StorageTexture* JOIN(build_texture_storage_, suffix)(            \
      MatchState & state, Number F, Number A) {                               \
    auto format = static_cast<TexelFormat>(F.Value());                        \
    auto access = static_cast<Access>(A.Value());                             \
    auto* T = sem::StorageTexture::SubtypeFor(format, state.builder.Types()); \
    return state.builder.create<sem::StorageTexture>(dim, format, access, T); \
  }

DECLARE_STORAGE_TEXTURE(1d, ast::TextureDimension::k1d)
DECLARE_STORAGE_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_STORAGE_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_STORAGE_TEXTURE(3d, ast::TextureDimension::k3d)
#undef DECLARE_STORAGE_TEXTURE

bool match_texture_external(const sem::Type* ty) {
  return ty->IsAnyOf<Any, sem::ExternalTexture>();
}

const sem::ExternalTexture* build_texture_external(MatchState& state) {
  return state.builder.create<sem::ExternalTexture>();
}

// Builtin types starting with a _ prefix cannot be declared in WGSL, so they
// can only be used as return types. Because of this, they must only match Any,
// which is used as the return type matcher.
bool match_modf_result(const sem::Type* ty) {
  return ty->Is<Any>();
}
bool match_modf_result_vec(const sem::Type* ty, Number& N) {
  if (!ty->Is<Any>()) {
    return false;
  }
  N = Number::any;
  return true;
}
bool match_frexp_result(const sem::Type* ty) {
  return ty->Is<Any>();
}
bool match_frexp_result_vec(const sem::Type* ty, Number& N) {
  if (!ty->Is<Any>()) {
    return false;
  }
  N = Number::any;
  return true;
}

struct NameAndType {
  std::string name;
  sem::Type* type;
};
const sem::Struct* build_struct(
    MatchState& state,
    std::string name,
    std::initializer_list<NameAndType> member_names_and_types) {
  uint32_t offset = 0;
  uint32_t max_align = 0;
  sem::StructMemberList members;
  for (auto& m : member_names_and_types) {
    uint32_t align = m.type->Align();
    uint32_t size = m.type->Size();
    offset = utils::RoundUp(align, offset);
    max_align = std::max(max_align, align);
    members.emplace_back(state.builder.create<sem::StructMember>(
        /* declaration */ nullptr,
        /* name */ state.builder.Sym(m.name),
        /* type */ m.type,
        /* index */ static_cast<uint32_t>(members.size()),
        /* offset */ offset,
        /* align */ align,
        /* size */ size));
    offset += size;
  }
  uint32_t size_without_padding = offset;
  uint32_t size_with_padding = utils::RoundUp(max_align, offset);
  return state.builder.create<sem::Struct>(
      /* declaration */ nullptr,
      /* name */ state.builder.Sym(name),
      /* members */ members,
      /* align */ max_align,
      /* size */ size_with_padding,
      /* size_no_padding */ size_without_padding);
}

const sem::Struct* build_modf_result(MatchState& state) {
  auto* f32 = state.builder.create<sem::F32>();
  return build_struct(state, "__modf_result", {{"fract", f32}, {"whole", f32}});
}
const sem::Struct* build_modf_result_vec(MatchState& state, Number& n) {
  auto* vec_f32 = state.builder.create<sem::Vector>(
      state.builder.create<sem::F32>(), n.Value());
  return build_struct(state, "__modf_result_vec" + std::to_string(n.Value()),
                      {{"fract", vec_f32}, {"whole", vec_f32}});
}
const sem::Struct* build_frexp_result(MatchState& state) {
  auto* f32 = state.builder.create<sem::F32>();
  auto* i32 = state.builder.create<sem::I32>();
  return build_struct(state, "__frexp_result", {{"sig", f32}, {"exp", i32}});
}
const sem::Struct* build_frexp_result_vec(MatchState& state, Number& n) {
  auto* vec_f32 = state.builder.create<sem::Vector>(
      state.builder.create<sem::F32>(), n.Value());
  auto* vec_i32 = state.builder.create<sem::Vector>(
      state.builder.create<sem::I32>(), n.Value());
  return build_struct(state, "__frexp_result_vec" + std::to_string(n.Value()),
                      {{"sig", vec_f32}, {"exp", vec_i32}});
}

/// ParameterInfo describes a parameter
struct ParameterInfo {
  /// The parameter usage (parameter name in definition file)
  const ParameterUsage usage;

  /// Pointer to a list of indices that are used to match the parameter type.
  /// The matcher indices index on Matchers::type and / or Matchers::number.
  /// These indices are consumed by the matchers themselves.
  /// The first index is always a TypeMatcher.
  MatcherIndex const* const matcher_indices;
};

/// OpenTypeInfo describes an open type
struct OpenTypeInfo {
  /// Name of the open type (e.g. 'T')
  const char* name;
  /// Optional type matcher constraint.
  /// Either an index in Matchers::type, or kNoMatcher
  const MatcherIndex matcher_index;
};

/// OpenNumberInfo describes an open number
struct OpenNumberInfo {
  /// Name of the open number (e.g. 'N')
  const char* name;
  /// Optional number matcher constraint.
  /// Either an index in Matchers::number, or kNoMatcher
  const MatcherIndex matcher_index;
};

/// OverloadInfo describes a single function overload
struct OverloadInfo {
  /// Total number of parameters for the overload
  const uint8_t num_parameters;
  /// Total number of open types for the overload
  const uint8_t num_open_types;
  /// Total number of open numbers for the overload
  const uint8_t num_open_numbers;
  /// Pointer to the first open type
  OpenTypeInfo const* const open_types;
  /// Pointer to the first open number
  OpenNumberInfo const* const open_numbers;
  /// Pointer to the first parameter
  ParameterInfo const* const parameters;
  /// Pointer to a list of matcher indices that index on Matchers::type and
  /// Matchers::number, used to build the return type. If the function has no
  /// return type then this is null
  MatcherIndex const* const return_matcher_indices;
  /// The pipeline stages that this overload can be used in
  PipelineStageSet supported_stages;
  /// True if the overload is marked as deprecated
  bool is_deprecated;
};

/// BuiltinInfo describes a builtin function
struct BuiltinInfo {
  /// Number of overloads of the builtin function
  const uint8_t num_overloads;
  /// Pointer to the start of the overloads for the function
  OverloadInfo const* const overloads;
};

#include "builtin_table.inl"

/// BuiltinPrototype describes a fully matched builtin function, which is
/// used as a lookup for building unique sem::Builtin instances.
struct BuiltinPrototype {
  /// Parameter describes a single parameter
  struct Parameter {
    /// Parameter type
    const sem::Type* const type;
    /// Parameter usage
    ParameterUsage const usage = ParameterUsage::kNone;
  };

  /// Hasher provides a hash function for the BuiltinPrototype
  struct Hasher {
    /// @param i the BuiltinPrototype to create a hash for
    /// @return the hash value
    inline std::size_t operator()(const BuiltinPrototype& i) const {
      size_t hash = utils::Hash(i.parameters.size());
      for (auto& p : i.parameters) {
        utils::HashCombine(&hash, p.type, p.usage);
      }
      return utils::Hash(hash, i.type, i.return_type, i.supported_stages,
                         i.is_deprecated);
    }
  };

  sem::BuiltinType type = sem::BuiltinType::kNone;
  std::vector<Parameter> parameters;
  sem::Type const* return_type = nullptr;
  PipelineStageSet supported_stages;
  bool is_deprecated = false;
};

/// Equality operator for BuiltinPrototype
bool operator==(const BuiltinPrototype& a, const BuiltinPrototype& b) {
  if (a.type != b.type || a.supported_stages != b.supported_stages ||
      a.return_type != b.return_type || a.is_deprecated != b.is_deprecated ||
      a.parameters.size() != b.parameters.size()) {
    return false;
  }
  for (size_t i = 0; i < a.parameters.size(); i++) {
    auto& pa = a.parameters[i];
    auto& pb = b.parameters[i];
    if (pa.type != pb.type || pa.usage != pb.usage) {
      return false;
    }
  }
  return true;
}

/// Impl is the private implementation of the BuiltinTable interface.
class Impl : public BuiltinTable {
 public:
  explicit Impl(ProgramBuilder& builder);

  const sem::Builtin* Lookup(sem::BuiltinType builtin_type,
                             const std::vector<const sem::Type*>& args,
                             const Source& source) override;

 private:
  const sem::Builtin* Match(sem::BuiltinType builtin_type,
                            const OverloadInfo& overload,
                            const std::vector<const sem::Type*>& args,
                            int& match_score);

  MatchState Match(ClosedState& closed,
                   const OverloadInfo& overload,
                   MatcherIndex const* matcher_indices) const;

  void PrintOverload(std::ostream& ss,
                     const OverloadInfo& overload,
                     sem::BuiltinType builtin_type) const;

  ProgramBuilder& builder;
  Matchers matchers;
  std::unordered_map<BuiltinPrototype, sem::Builtin*, BuiltinPrototype::Hasher>
      builtins;
};

/// @return a string representing a call to a builtin with the given argument
/// types.
std::string CallSignature(ProgramBuilder& builder,
                          sem::BuiltinType builtin_type,
                          const std::vector<const sem::Type*>& args) {
  std::stringstream ss;
  ss << sem::str(builtin_type) << "(";
  {
    bool first = true;
    for (auto* arg : args) {
      if (!first) {
        ss << ", ";
      }
      first = false;
      ss << arg->UnwrapRef()->FriendlyName(builder.Symbols());
    }
  }
  ss << ")";

  return ss.str();
}

std::string OpenTypeMatcher::String(MatchState& state) const {
  return state.overload.open_types[index_].name;
}

std::string OpenNumberMatcher::String(MatchState& state) const {
  return state.overload.open_numbers[index_].name;
}

Impl::Impl(ProgramBuilder& b) : builder(b) {}

const sem::Builtin* Impl::Lookup(sem::BuiltinType builtin_type,
                                 const std::vector<const sem::Type*>& args,
                                 const Source& source) {
  // Candidate holds information about a mismatched overload that could be what
  // the user intended to call.
  struct Candidate {
    const OverloadInfo* overload;
    int score;
  };

  // The list of failed matches that had promise.
  std::vector<Candidate> candidates;

  auto& builtin = kBuiltins[static_cast<uint32_t>(builtin_type)];
  for (uint32_t o = 0; o < builtin.num_overloads; o++) {
    int match_score = 1000;
    auto& overload = builtin.overloads[o];
    if (auto* match = Match(builtin_type, overload, args, match_score)) {
      return match;
    }
    if (match_score > 0) {
      candidates.emplace_back(Candidate{&overload, match_score});
    }
  }

  // Sort the candidates with the most promising first
  std::stable_sort(
      candidates.begin(), candidates.end(),
      [](const Candidate& a, const Candidate& b) { return a.score > b.score; });

  // Generate an error message
  std::stringstream ss;
  ss << "no matching call to " << CallSignature(builder, builtin_type, args)
     << std::endl;
  if (!candidates.empty()) {
    ss << std::endl;
    ss << candidates.size() << " candidate function"
       << (candidates.size() > 1 ? "s:" : ":") << std::endl;
    for (auto& candidate : candidates) {
      ss << "  ";
      PrintOverload(ss, *candidate.overload, builtin_type);
      ss << std::endl;
    }
  }
  builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source);
  return nullptr;
}

const sem::Builtin* Impl::Match(sem::BuiltinType builtin_type,
                                const OverloadInfo& overload,
                                const std::vector<const sem::Type*>& args,
                                int& match_score) {
  // Score wait for argument <-> parameter count matches / mismatches
  constexpr int kScorePerParamArgMismatch = -1;
  constexpr int kScorePerMatchedParam = 2;
  constexpr int kScorePerMatchedOpenType = 1;
  constexpr int kScorePerMatchedOpenNumber = 1;

  auto num_parameters = overload.num_parameters;
  auto num_arguments = static_cast<decltype(num_parameters)>(args.size());

  bool overload_matched = true;

  if (num_parameters != num_arguments) {
    match_score +=
        kScorePerParamArgMismatch * (std::max(num_parameters, num_arguments) -
                                     std::min(num_parameters, num_arguments));
    overload_matched = false;
  }

  ClosedState closed(builder);

  std::vector<BuiltinPrototype::Parameter> parameters;

  auto num_params = std::min(num_parameters, num_arguments);
  for (uint32_t p = 0; p < num_params; p++) {
    auto& parameter = overload.parameters[p];
    auto* indices = parameter.matcher_indices;
    auto* type = Match(closed, overload, indices).Type(args[p]->UnwrapRef());
    if (type) {
      parameters.emplace_back(
          BuiltinPrototype::Parameter{type, parameter.usage});
      match_score += kScorePerMatchedParam;
    } else {
      overload_matched = false;
    }
  }

  if (overload_matched) {
    // Check all constrained open types matched
    for (uint32_t ot = 0; ot < overload.num_open_types; ot++) {
      auto& open_type = overload.open_types[ot];
      if (open_type.matcher_index != kNoMatcher) {
        auto* index = &open_type.matcher_index;
        if (Match(closed, overload, index).Type(closed.Type(ot))) {
          match_score += kScorePerMatchedOpenType;
        } else {
          overload_matched = false;
        }
      }
    }
  }

  if (overload_matched) {
    // Check all constrained open numbers matched
    for (uint32_t on = 0; on < overload.num_open_numbers; on++) {
      auto& open_number = overload.open_numbers[on];
      if (open_number.matcher_index != kNoMatcher) {
        auto* index = &open_number.matcher_index;
        if (Match(closed, overload, index).Num(closed.Num(on)).IsValid()) {
          match_score += kScorePerMatchedOpenNumber;
        } else {
          overload_matched = false;
        }
      }
    }
  }

  if (!overload_matched) {
    return nullptr;
  }

  // Build the return type
  const sem::Type* return_type = nullptr;
  if (auto* indices = overload.return_matcher_indices) {
    Any any;
    return_type = Match(closed, overload, indices).Type(&any);
    if (!return_type) {
      std::stringstream ss;
      PrintOverload(ss, overload, builtin_type);
      TINT_ICE(Resolver, builder.Diagnostics())
          << "MatchState.Match() returned null for " << ss.str();
      return nullptr;
    }
  } else {
    return_type = builder.create<sem::Void>();
  }

  BuiltinPrototype builtin;
  builtin.type = builtin_type;
  builtin.return_type = return_type;
  builtin.parameters = std::move(parameters);
  builtin.supported_stages = overload.supported_stages;
  builtin.is_deprecated = overload.is_deprecated;

  // De-duplicate builtins that are identical.
  return utils::GetOrCreate(builtins, builtin, [&] {
    std::vector<sem::Parameter*> params;
    params.reserve(builtin.parameters.size());
    for (auto& p : builtin.parameters) {
      params.emplace_back(builder.create<sem::Parameter>(
          nullptr, static_cast<uint32_t>(params.size()), p.type,
          ast::StorageClass::kNone, ast::Access::kUndefined, p.usage));
    }
    return builder.create<sem::Builtin>(
        builtin.type, builtin.return_type, std::move(params),
        builtin.supported_stages, builtin.is_deprecated);
  });
}

MatchState Impl::Match(ClosedState& closed,
                       const OverloadInfo& overload,
                       MatcherIndex const* matcher_indices) const {
  return MatchState(builder, closed, matchers, overload, matcher_indices);
}

void Impl::PrintOverload(std::ostream& ss,
                         const OverloadInfo& overload,
                         sem::BuiltinType builtin_type) const {
  ClosedState closed(builder);

  ss << builtin_type << "(";
  for (uint32_t p = 0; p < overload.num_parameters; p++) {
    auto& parameter = overload.parameters[p];
    if (p > 0) {
      ss << ", ";
    }
    if (parameter.usage != ParameterUsage::kNone) {
      ss << sem::str(parameter.usage) << ": ";
    }
    auto* indices = parameter.matcher_indices;
    ss << Match(closed, overload, indices).TypeName();
  }
  ss << ")";
  if (overload.return_matcher_indices) {
    ss << " -> ";
    auto* indices = overload.return_matcher_indices;
    ss << Match(closed, overload, indices).TypeName();
  }

  bool first = true;
  auto separator = [&] {
    ss << (first ? "  where: " : ", ");
    first = false;
  };
  for (uint32_t i = 0; i < overload.num_open_types; i++) {
    auto& open_type = overload.open_types[i];
    if (open_type.matcher_index != kNoMatcher) {
      separator();
      ss << open_type.name;
      auto* index = &open_type.matcher_index;
      ss << " is " << Match(closed, overload, index).TypeName();
    }
  }
  for (uint32_t i = 0; i < overload.num_open_numbers; i++) {
    auto& open_number = overload.open_numbers[i];
    if (open_number.matcher_index != kNoMatcher) {
      separator();
      ss << open_number.name;
      auto* index = &open_number.matcher_index;
      ss << " is " << Match(closed, overload, index).NumName();
    }
  }
}

const sem::Type* MatchState::Type(const sem::Type* ty) {
  MatcherIndex matcher_index = *matcher_indices_++;
  auto* matcher = matchers.type[matcher_index];
  return matcher->Match(*this, ty);
}

Number MatchState::Num(Number number) {
  MatcherIndex matcher_index = *matcher_indices_++;
  auto* matcher = matchers.number[matcher_index];
  return matcher->Match(*this, number);
}

std::string MatchState::TypeName() {
  MatcherIndex matcher_index = *matcher_indices_++;
  auto* matcher = matchers.type[matcher_index];
  return matcher->String(*this);
}

std::string MatchState::NumName() {
  MatcherIndex matcher_index = *matcher_indices_++;
  auto* matcher = matchers.number[matcher_index];
  return matcher->String(*this);
}

}  // namespace

std::unique_ptr<BuiltinTable> BuiltinTable::Create(ProgramBuilder& builder) {
  return std::make_unique<Impl>(builder);
}

BuiltinTable::~BuiltinTable() = default;

/// TypeInfo for the Any type declared in the anonymous namespace above
TINT_INSTANTIATE_TYPEINFO(Any);

}  // namespace tint