text: //
  // Copyright 2019 WebAssembly Community Group participants
  //
  // 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 "wasp/valid/match.h"
  
  #include <cassert>
  
  #include "wasp/valid/valid_ctx.h"
  
  namespace wasp::valid {
  
  auto CanonicalizeToRefType(const binary::ReferenceType& type)
      -> binary::RefType {
    binary::ReferenceType canon = Canonicalize(type);
    assert(canon.is_ref());
    return canon.ref();
  }
  
  /// IsSame ///
  
  bool IsSame(ValidCtx& ctx,
              const binary::HeapType& expected,
              const binary::HeapType& actual) {
    if (expected.is_heap_kind() && actual.is_heap_kind()) {
      return expected.heap_kind().value() == actual.heap_kind().value();
    } else if (expected.is_index() && actual.is_index()) {
      Index expected_index = expected.index().value();
      Index actual_index = actual.index().value();
      if (expected_index == actual_index) {
        return true;
      }
  
      auto is_same_opt = ctx.same_types.Get(expected_index, actual_index);
      if (is_same_opt) {
        return *is_same_opt;
      }
  
      // Assume that they are the same and check that everything still is valid.
      ctx.same_types.Assume(expected_index, actual_index);
      bool is_same =
          IsSame(ctx, ctx.types[expected_index], ctx.types[actual_index]);
      ctx.same_types.Resolve(expected_index, actual_index, is_same);
      return is_same;
    }
    return false;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::RefType& expected,
              const binary::RefType& actual) {
    return IsSame(ctx, expected.heap_type, actual.heap_type) &&
           expected.null == actual.null;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::ReferenceType& expected,
              const binary::ReferenceType& actual) {
    // Canonicalize in case one of the types is "ref null X" and the other is
    // "Xref".
    return IsSame(ctx, CanonicalizeToRefType(expected),
                  CanonicalizeToRefType(actual));
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::Rtt& expected,
              const binary::Rtt& actual) {
    return expected.depth.value() == actual.depth.value() &&
           IsSame(ctx, expected.type, actual.type);
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::ValueType& expected,
              const binary::ValueType& actual) {
    if (expected.is_numeric_type() && actual.is_numeric_type()) {
      return expected.numeric_type().value() == actual.numeric_type().value();
    } else if (expected.is_reference_type() && actual.is_reference_type()) {
      return IsSame(ctx, expected.reference_type(), actual.reference_type());
    } else if (expected.is_rtt() && actual.is_rtt()) {
      return IsSame(ctx, expected.rtt(), actual.rtt());
    }
    return false;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::ValueTypeList& expected,
              const binary::ValueTypeList& actual) {
    if (expected.size() != actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsSame(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::FunctionType& expected,
              const binary::FunctionType& actual) {
    return IsSame(ctx, expected.param_types, actual.param_types) &&
           IsSame(ctx, expected.result_types, actual.result_types);
  }
  
  bool IsSame(ValidCtx& ctx, const StackType& expected, const StackType& actual) {
    // One of the types is "any" (i.e. universal supertype or subtype), or the
    // value types are the same.
    return expected.is_any() || actual.is_any() ||
           IsSame(ctx, expected.value_type(), actual.value_type());
  }
  
  bool IsSame(ValidCtx& ctx, StackTypeSpan expected, StackTypeSpan actual) {
    if (expected.size() != actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsSame(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::StorageType& expected,
              const binary::StorageType& actual) {
    if (expected.is_value_type() && actual.is_value_type()) {
      return IsSame(ctx, expected.value_type(), actual.value_type());
    } else if (expected.is_packed_type() && actual.is_packed_type()) {
      return expected.packed_type().value() == actual.packed_type().value();
    }
    return false;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::FieldType& expected,
              const binary::FieldType& actual) {
    return IsSame(ctx, expected.type, actual.type) &&
           expected.mut.value() == actual.mut.value();
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::FieldTypeList& expected,
              const binary::FieldTypeList& actual) {
    if (expected.size() != actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsSame(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::StructType& expected,
              const binary::StructType& actual) {
    return IsSame(ctx, expected.fields, actual.fields);
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::ArrayType& expected,
              const binary::ArrayType& actual) {
    return IsSame(ctx, expected.field, actual.field);
  }
  
  bool IsSame(ValidCtx& ctx,
              const binary::DefinedType& expected,
              const binary::DefinedType& actual) {
    if (expected.is_function_type() && actual.is_function_type()) {
      return IsSame(ctx, expected.function_type(), actual.function_type());
    } else if (expected.is_struct_type() && actual.is_struct_type()) {
      return IsSame(ctx, expected.struct_type(), actual.struct_type());
    } else if (expected.is_array_type() && actual.is_array_type()) {
      return IsSame(ctx, expected.array_type(), actual.array_type());
    }
    return false;
  }
  
  /// IsMatch ///
  
  bool IsMatch(ValidCtx& ctx,
               const binary::HeapType& expected,
               const binary::HeapType& actual) {
    // `any` is a supertype of all types.
    if (expected.is_heap_kind(HeapKind::Any)) {
      return true;
    }
  
    // `func` is a supertype of all function types.
    if (expected.is_heap_kind(HeapKind::Func) && actual.is_index() &&
        ctx.IsFunctionType(actual.index())) {
      return true;
    }
  
    // `eq` is a supertype of all i31, or any non-function defined type.
    if (expected.is_heap_kind(HeapKind::Eq)) {
      if (actual.is_heap_kind(HeapKind::I31)) {
        return true;
      } else if (actual.is_index() && (ctx.IsStructType(actual.index()) ||
                                       ctx.IsArrayType(actual.index()))) {
        return true;
      }
    }
  
    if (expected.is_index() && actual.is_index()) {
      Index expected_index = expected.index().value();
      Index actual_index = actual.index().value();
      if (expected_index == actual_index) {
        return true;
      }
  
      // Check whether heap types match, but make sure to handle recursive
      // structures. This is the same logic used in IsSame(HeapType, HeapType).
  
      auto is_match_opt = ctx.match_types.Get(expected_index, actual_index);
      if (is_match_opt) {
        return *is_match_opt;
      }
  
      // Assume that they match and check that everything still is valid.
      ctx.match_types.Assume(expected_index, actual_index);
      bool is_match =
          IsMatch(ctx, ctx.types[expected_index], ctx.types[actual_index]);
      ctx.match_types.Resolve(expected_index, actual_index, is_match);
      return is_match;
    }
  
    return IsSame(ctx, expected, actual);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::RefType& expected,
               const binary::RefType& actual) {
    // "ref null 0" is a supertype of "ref 0"
    if (expected.null == Null::No && actual.null == Null::Yes) {
      return false;
    }
    return IsMatch(ctx, expected.heap_type.value(), actual.heap_type);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::ReferenceType& expected,
               const binary::ReferenceType& actual) {
    // Canonicalize in case one of the types is "ref null X" and the other is
    // "Xref".
    return IsMatch(ctx, CanonicalizeToRefType(expected),
                   CanonicalizeToRefType(actual));
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::Rtt& expected,
               const binary::Rtt& actual) {
    // Rtt's don't have any subtyping, aside from rtt <: any. However, unlike
    // IsSame(Rtt, Rtt) we consider two Rtts to match even if their depths don't
    // match. This is because for nearly all instructions, the depth is not used
    // in static validation.
    return IsSame(ctx, expected.type, actual.type);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::ValueType& expected,
               const binary::ValueType& actual) {
    if (expected.is_numeric_type() && actual.is_numeric_type()) {
      return expected.numeric_type().value() == actual.numeric_type().value();
    } else if (expected.is_reference_type() && actual.is_reference_type()) {
      return IsMatch(ctx, expected.reference_type(), actual.reference_type());
    } else if (expected.is_rtt() && actual.is_rtt()) {
      return IsMatch(ctx, expected.rtt(), actual.rtt());
    }
    return false;
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::ValueTypeList& expected,
               const binary::ValueTypeList& actual) {
    if (expected.size() != actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsMatch(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsMatch(ValidCtx& ctx,
               const StackType& expected,
               const StackType& actual) {
    // One of the types is "any" (i.e. universal supertype or subtype), or the
    // value types match.
    return expected.is_any() || actual.is_any() ||
           IsMatch(ctx, expected.value_type(), actual.value_type());
  }
  
  bool IsMatch(ValidCtx& ctx, StackTypeSpan expected, StackTypeSpan actual) {
    if (expected.size() != actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsMatch(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::StorageType& expected,
               const binary::StorageType& actual) {
    if (expected.is_value_type() && actual.is_value_type()) {
      return IsMatch(ctx, expected.value_type(), actual.value_type());
    } else if (expected.is_packed_type() && actual.is_packed_type()) {
      return expected.packed_type().value() == actual.packed_type().value();
    }
    return false;
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::FieldType& expected,
               const binary::FieldType& actual) {
    // Only const fields are covariant.
    if (expected.mut == Mutability::Const && actual.mut == Mutability::Const) {
      return IsMatch(ctx, expected.type, actual.type);
    }
    return IsSame(ctx, expected, actual);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::FieldTypeList& expected,
               const binary::FieldTypeList& actual) {
    // A longer list of fields is a subtype of a shorter list, as long as the
    // types match.
    if (expected.size() > actual.size()) {
      return false;
    }
  
    for (auto eiter = expected.begin(), lend = expected.end(),
              aiter = actual.begin();
         eiter != lend; ++eiter, ++aiter) {
      if (!IsMatch(ctx, *eiter, *aiter)) {
        return false;
      }
    }
    return true;
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::FunctionType& expected,
               const binary::FunctionType& actual) {
    // Function types have no subtyping, so just check if they are equivalent.
    return IsSame(ctx, expected, actual);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::StructType& expected,
               const binary::StructType& actual) {
    return IsMatch(ctx, expected.fields, actual.fields);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::ArrayType& expected,
               const binary::ArrayType& actual) {
    return IsMatch(ctx, expected.field, actual.field);
  }
  
  bool IsMatch(ValidCtx& ctx,
               const binary::DefinedType& expected,
               const binary::DefinedType& actual) {
    if (expected.is_function_type() && actual.is_function_type()) {
      return IsSame(ctx, expected.function_type(), actual.function_type());
    } else if (expected.is_struct_type() && actual.is_struct_type()) {
      return IsMatch(ctx, expected.struct_type(), actual.struct_type());
    } else if (expected.is_array_type() && actual.is_array_type()) {
      return IsMatch(ctx, expected.array_type(), actual.array_type());
    }
    return false;
  }
  
  }  // namespace wasp::valid
  