// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#include "vm/class_finalizer.h"

#include "vm/compiler/jit/compiler.h"
#include "vm/flags.h"
#include "vm/hash_table.h"
#include "vm/heap/heap.h"
#include "vm/isolate.h"
#include "vm/kernel_loader.h"
#include "vm/log.h"
#include "vm/longjump.h"
#include "vm/object_store.h"
#include "vm/program_visitor.h"
#include "vm/runtime_entry.h"
#include "vm/symbols.h"
#include "vm/timeline.h"
#include "vm/type_table.h"
#include "vm/type_testing_stubs.h"

namespace dart {

DEFINE_FLAG(bool, print_classes, false, "Prints details about loaded classes.");
DEFINE_FLAG(bool, trace_class_finalization, false, "Trace class finalization.");
DEFINE_FLAG(bool, trace_type_finalization, false, "Trace type finalization.");

bool ClassFinalizer::AllClassesFinalized() {
  ObjectStore* object_store = Isolate::Current()->object_store();
  const GrowableObjectArray& classes =
      GrowableObjectArray::Handle(object_store->pending_classes());
  return classes.Length() == 0;
}

// Removes optimized code once we load more classes, since CHA based
// optimizations may have become invalid.
// Only methods which owner classes where subclasses can be invalid.
// TODO(srdjan): Be even more precise by recording the exact CHA optimization.
static void RemoveCHAOptimizedCode(
    const Class& subclass,
    const GrowableArray<intptr_t>& added_subclass_to_cids) {
  ASSERT(FLAG_use_cha_deopt);
  if (added_subclass_to_cids.is_empty()) {
    return;
  }
  // Switch all functions' code to unoptimized.
  const ClassTable& class_table = *Isolate::Current()->class_table();
  Class& cls = Class::Handle();
  for (intptr_t i = 0; i < added_subclass_to_cids.length(); i++) {
    intptr_t cid = added_subclass_to_cids[i];
    cls = class_table.At(cid);
    ASSERT(!cls.IsNull());
    cls.DisableCHAOptimizedCode(subclass);
  }
}

void AddSuperType(const AbstractType& type,
                  GrowableArray<intptr_t>* finalized_super_classes) {
  ASSERT(type.HasTypeClass());
  ASSERT(!type.IsDynamicType());
  if (type.IsObjectType()) {
    return;
  }
  const Class& cls = Class::Handle(type.type_class());
  ASSERT(cls.is_finalized());
  const intptr_t cid = cls.id();
  for (intptr_t i = 0; i < finalized_super_classes->length(); i++) {
    if ((*finalized_super_classes)[i] == cid) {
      // Already added.
      return;
    }
  }
  finalized_super_classes->Add(cid);
  const AbstractType& super_type = AbstractType::Handle(cls.super_type());
  AddSuperType(super_type, finalized_super_classes);
}

// Use array instead of set since we expect very few subclassed classes
// to occur.
static void CollectFinalizedSuperClasses(
    const Class& cls_,
    GrowableArray<intptr_t>* finalized_super_classes) {
  Class& cls = Class::Handle(cls_.raw());
  AbstractType& super_type = Type::Handle();
  super_type = cls.super_type();
  if (!super_type.IsNull()) {
    if (super_type.HasTypeClass()) {
      cls ^= super_type.type_class();
      if (cls.is_finalized()) {
        AddSuperType(super_type, finalized_super_classes);
      }
    }
  }
}

class InterfaceFinder {
 public:
  InterfaceFinder(Zone* zone,
                  ClassTable* class_table,
                  GrowableArray<intptr_t>* cids)
      : class_table_(class_table),
        array_handles_(zone),
        class_handles_(zone),
        type_handles_(zone),
        cids_(cids) {}

  void FindAllInterfaces(const Class& klass) {
    // The class is implementing it's own interface.
    cids_->Add(klass.id());

    ScopedHandle<Array> array(&array_handles_);
    ScopedHandle<Class> interface_class(&class_handles_);
    ScopedHandle<Class> current_class(&class_handles_);
    ScopedHandle<AbstractType> type(&type_handles_);

    *current_class = klass.raw();
    while (true) {
      // We don't care about top types.
      const intptr_t cid = current_class->id();
      if (cid == kObjectCid || cid == kDynamicCid || cid == kVoidCid) {
        break;
      }

      // The class is implementing it's directly declared implemented
      // interfaces.
      *array = klass.interfaces();
      if (!array->IsNull()) {
        for (intptr_t i = 0; i < array->Length(); ++i) {
          *type ^= array->At(i);
          *interface_class ^= class_table_->At(type->type_class_id());
          FindAllInterfaces(*interface_class);
        }
      }

      // The class is implementing it's super type's interfaces.
      *type = current_class->super_type();
      if (type->IsNull()) break;
      *current_class = class_table_->At(type->type_class_id());
    }
  }

 private:
  ClassTable* class_table_;
  ReusableHandleStack<Array> array_handles_;
  ReusableHandleStack<Class> class_handles_;
  ReusableHandleStack<AbstractType> type_handles_;
  GrowableArray<intptr_t>* cids_;
};

static void CollectImmediateSuperInterfaces(const Class& cls,
                                            GrowableArray<intptr_t>* cids) {
  const Array& interfaces = Array::Handle(cls.interfaces());
  Class& ifc = Class::Handle();
  AbstractType& type = AbstractType::Handle();
  for (intptr_t i = 0; i < interfaces.Length(); ++i) {
    type ^= interfaces.At(i);
    if (!type.HasTypeClass()) continue;
    ifc ^= type.type_class();
    for (intptr_t j = 0; j < cids->length(); ++j) {
      if ((*cids)[j] == ifc.id()) {
        // Already added.
        return;
      }
    }
    cids->Add(ifc.id());
  }
}

// Processing ObjectStore::pending_classes_ occurs:
// a) when bootstrap process completes (VerifyBootstrapClasses).
// b) after the user classes are loaded (dart_api).
bool ClassFinalizer::ProcessPendingClasses() {
  Thread* thread = Thread::Current();
  NOT_IN_PRODUCT(TimelineDurationScope tds(thread, Timeline::GetIsolateStream(),
                                           "ProcessPendingClasses"));
  Isolate* isolate = thread->isolate();
  ASSERT(isolate != NULL);
  HANDLESCOPE(thread);
  ObjectStore* object_store = isolate->object_store();
  const Error& error = Error::Handle(thread->zone(), thread->sticky_error());
  if (!error.IsNull()) {
    return false;
  }
  if (AllClassesFinalized()) {
    return true;
  }

  LongJumpScope jump;
  if (setjmp(*jump.Set()) == 0) {
    GrowableObjectArray& class_array = GrowableObjectArray::Handle();
    class_array = object_store->pending_classes();
    ASSERT(!class_array.IsNull());
    Class& cls = Class::Handle();
    // First check all superclasses.
    for (intptr_t i = 0; i < class_array.Length(); i++) {
      cls ^= class_array.At(i);
      GrowableArray<intptr_t> visited_interfaces;
      CheckSuperTypeAndInterfaces(cls, &visited_interfaces);
    }
    // Finalize all classes.
    for (intptr_t i = 0; i < class_array.Length(); i++) {
      cls ^= class_array.At(i);
      FinalizeTypesInClass(cls);
    }

    if (FLAG_print_classes) {
      for (intptr_t i = 0; i < class_array.Length(); i++) {
        cls ^= class_array.At(i);
        PrintClassInformation(cls);
      }
    }
    // Clear pending classes array.
    class_array = GrowableObjectArray::New();
    object_store->set_pending_classes(class_array);
    VerifyImplicitFieldOffsets();  // Verification after an error may fail.

    return true;
  } else {
    return false;
  }
  UNREACHABLE();
  return true;
}

#if !defined(DART_PRECOMPILED_RUNTIME)
void ClassFinalizer::VerifyBootstrapClasses() {
  if (FLAG_trace_class_finalization) {
    OS::PrintErr("VerifyBootstrapClasses START.\n");
  }
  ObjectStore* object_store = Isolate::Current()->object_store();

  Class& cls = Class::Handle();
#if defined(DEBUG)
  // Basic checking.
  cls = object_store->object_class();
  ASSERT(Instance::InstanceSize() == cls.instance_size());
  cls = object_store->integer_implementation_class();
  ASSERT(Integer::InstanceSize() == cls.instance_size());
  cls = object_store->smi_class();
  ASSERT(Smi::InstanceSize() == cls.instance_size());
  cls = object_store->mint_class();
  ASSERT(Mint::InstanceSize() == cls.instance_size());
  cls = object_store->one_byte_string_class();
  ASSERT(OneByteString::InstanceSize() == cls.instance_size());
  cls = object_store->two_byte_string_class();
  ASSERT(TwoByteString::InstanceSize() == cls.instance_size());
  cls = object_store->external_one_byte_string_class();
  ASSERT(ExternalOneByteString::InstanceSize() == cls.instance_size());
  cls = object_store->external_two_byte_string_class();
  ASSERT(ExternalTwoByteString::InstanceSize() == cls.instance_size());
  cls = object_store->double_class();
  ASSERT(Double::InstanceSize() == cls.instance_size());
  cls = object_store->bool_class();
  ASSERT(Bool::InstanceSize() == cls.instance_size());
  cls = object_store->array_class();
  ASSERT(Array::InstanceSize() == cls.instance_size());
  cls = object_store->immutable_array_class();
  ASSERT(ImmutableArray::InstanceSize() == cls.instance_size());
  cls = object_store->weak_property_class();
  ASSERT(WeakProperty::InstanceSize() == cls.instance_size());
  cls = object_store->linked_hash_map_class();
  ASSERT(LinkedHashMap::InstanceSize() == cls.instance_size());
#endif  // defined(DEBUG)

  // Remember the currently pending classes.
  const GrowableObjectArray& class_array =
      GrowableObjectArray::Handle(object_store->pending_classes());
  for (intptr_t i = 0; i < class_array.Length(); i++) {
    // TODO(iposva): Add real checks.
    cls ^= class_array.At(i);
    if (cls.is_finalized() || cls.is_prefinalized()) {
      // Pre-finalized bootstrap classes must not define any fields.
      ASSERT(!cls.HasInstanceFields());
    }
  }

  // Finalize type hierarchy for types that aren't pre-finalized
  // by Object::Init().
  if (!ProcessPendingClasses()) {
    // TODO(srdjan): Exit like a real VM instead.
    const Error& err = Error::Handle(Thread::Current()->sticky_error());
    OS::PrintErr("Could not verify bootstrap classes : %s\n",
                 err.ToErrorCString());
    OS::Exit(255);
  }
  if (FLAG_trace_class_finalization) {
    OS::PrintErr("VerifyBootstrapClasses END.\n");
  }
  Isolate::Current()->heap()->Verify();
}
#endif  // !defined(DART_PRECOMPILED_RUNTIME)

void ClassFinalizer::FinalizeTypeParameters(const Class& cls,
                                            PendingTypes* pending_types) {
  if (FLAG_trace_type_finalization) {
    THR_Print("Finalizing type parameters of '%s'\n",
              String::Handle(cls.Name()).ToCString());
  }
  // The type parameter bounds are not finalized here.
  const TypeArguments& type_parameters =
      TypeArguments::Handle(cls.type_parameters());
  if (!type_parameters.IsNull()) {
    TypeParameter& type_parameter = TypeParameter::Handle();
    const intptr_t num_types = type_parameters.Length();
    for (intptr_t i = 0; i < num_types; i++) {
      type_parameter ^= type_parameters.TypeAt(i);
      type_parameter ^=
          FinalizeType(cls, type_parameter, kFinalize, pending_types);
      type_parameters.SetTypeAt(i, type_parameter);
    }
  }
}

// This function reports a compilation error if the recursive 'type' T being
// finalized is a non-contractive type, i.e. if the induced type set S of P is
// not finite, where P is the instantiation of T with its own type parameters.
// The induced type set S consists of the super types of any type in S as well
// as the type arguments of any parameterized type in S.
// The Dart Language Specification does not disallow the declaration and use of
// non-contractive types (this may change). They are nevertheless disallowed
// as an implementation restriction in the VM since they cause divergence.
// A non-contractive type can be detected by looking at the queue of types
// pending finalization that are mutually recursive with the checked type.
void ClassFinalizer::CheckRecursiveType(const Class& cls,
                                        const AbstractType& type,
                                        PendingTypes* pending_types) {
  ASSERT(pending_types != NULL);
  Zone* zone = Thread::Current()->zone();
  if (FLAG_trace_type_finalization) {
    THR_Print("Checking recursive type '%s': %s\n",
              String::Handle(type.Name()).ToCString(), type.ToCString());
  }
  const Class& type_cls = Class::Handle(zone, type.type_class());
  const TypeArguments& arguments =
      TypeArguments::Handle(zone, type.arguments());
  // A type can only be recursive via its type arguments.
  if (arguments.IsNull()) {
    // However, Kernel does not keep the relation between a function type and
    // its declaring typedef. Therefore, a typedef-declared function type may
    // refer to the still unfinalized typedef via a type in its signature.
    ASSERT(type.IsFunctionType());
    return;
  }
  const intptr_t num_type_args = arguments.Length();
  ASSERT(num_type_args > 0);
  ASSERT(num_type_args == type_cls.NumTypeArguments());
  const intptr_t num_type_params = type_cls.NumTypeParameters();
  const intptr_t first_type_param = num_type_args - num_type_params;
  // If the type is not generic (num_type_params == 0) or if its type parameters
  // are instantiated, no divergence can occur. Note that if the type parameters
  // are null, i.e. if the generic type is raw, they are considered
  // instantiated and no divergence can occur.
  if ((num_type_params == 0) ||
      arguments.IsSubvectorInstantiated(first_type_param, num_type_params)) {
    return;
  }
  // Consider mutually recursive and uninstantiated types pending finalization
  // with the same type class and report an error if they are not equal in their
  // raw form, i.e. where each class type parameter is substituted with dynamic.
  // This test eliminates divergent types without restricting recursive types
  // typically found in the wild.
  TypeArguments& pending_arguments = TypeArguments::Handle(zone);
  const intptr_t num_pending_types = pending_types->length();
  for (intptr_t i = num_pending_types - 1; i >= 0; i--) {
    const AbstractType& pending_type = pending_types->At(i);
    if (FLAG_trace_type_finalization) {
      THR_Print("  Comparing with pending type '%s': %s\n",
                String::Handle(pending_type.Name()).ToCString(),
                pending_type.ToCString());
    }
    if ((pending_type.raw() != type.raw()) && pending_type.IsType() &&
        (pending_type.type_class() == type_cls.raw())) {
      pending_arguments = pending_type.arguments();
      if (!pending_arguments.IsSubvectorEquivalent(arguments, first_type_param,
                                                   num_type_params) &&
          !pending_arguments.IsSubvectorInstantiated(first_type_param,
                                                     num_type_params)) {
        const TypeArguments& instantiated_arguments = TypeArguments::Handle(
            zone, arguments.InstantiateFrom(Object::null_type_arguments(),
                                            Object::null_type_arguments(),
                                            kNoneFree, NULL, Heap::kNew));
        const TypeArguments& instantiated_pending_arguments =
            TypeArguments::Handle(zone, pending_arguments.InstantiateFrom(
                                            Object::null_type_arguments(),
                                            Object::null_type_arguments(),
                                            kNoneFree, NULL, Heap::kNew));
        if (!instantiated_pending_arguments.IsSubvectorEquivalent(
                instantiated_arguments, first_type_param, num_type_params)) {
          const String& type_name = String::Handle(zone, type.Name());
          ReportError(cls, type.token_pos(), "illegal recursive type '%s'",
                      type_name.ToCString());
        }
      }
    }
  }
}

// Expand the type arguments of the given type and finalize its full type
// argument vector. Return the number of type arguments (0 for a raw type).
intptr_t ClassFinalizer::ExpandAndFinalizeTypeArguments(
    const Class& cls,
    const AbstractType& type,
    PendingTypes* pending_types) {
  Zone* zone = Thread::Current()->zone();
  // The type class does not need to be finalized in order to finalize the type.
  // Also, the type parameters of the type class must be finalized.
  Class& type_class = Class::Handle(zone, type.type_class());
  if (!type_class.is_type_finalized()) {
    FinalizeTypeParameters(type_class, pending_types);
  }

  // The finalized type argument vector needs num_type_arguments types.
  const intptr_t num_type_arguments = type_class.NumTypeArguments();
  // The class has num_type_parameters type parameters.
  const intptr_t num_type_parameters = type_class.NumTypeParameters();

  // Initialize the type argument vector.
  // Check the number of parsed type arguments, if any.
  // Specifying no type arguments indicates a raw type, which is not an error.
  // However, type parameter bounds are checked below, even for a raw type.
  TypeArguments& arguments = TypeArguments::Handle(zone, type.arguments());
  if (!arguments.IsNull() && (arguments.Length() != num_type_parameters)) {
    // Make the type raw and continue without reporting any error.
    // A static warning should have been reported.
    // TODO(regis): Check if this is dead code.
    arguments = TypeArguments::null();
    type.set_arguments(arguments);
  }

  // Mark the type as being finalized in order to detect self reference and
  // postpone bound checking (if required) until after all types in the graph of
  // mutually recursive types are finalized.
  type.SetIsBeingFinalized();
  ASSERT(pending_types != NULL);
  pending_types->Add(type);

  // The full type argument vector consists of the type arguments of the
  // super types of type_class, which are initialized from the parsed
  // type arguments, followed by the parsed type arguments.
  TypeArguments& full_arguments = TypeArguments::Handle(zone);
  if (num_type_arguments > 0) {
    // If no type arguments were parsed and if the super types do not prepend
    // type arguments to the vector, we can leave the vector as null.
    if (!arguments.IsNull() || (num_type_arguments > num_type_parameters)) {
      full_arguments = TypeArguments::New(num_type_arguments);
      // Copy the parsed type arguments at the correct offset in the full type
      // argument vector.
      const intptr_t offset = num_type_arguments - num_type_parameters;
      AbstractType& type_arg = AbstractType::Handle(zone, Type::DynamicType());
      // Leave the temporary type arguments at indices [0..offset[ as null.
      for (intptr_t i = 0; i < num_type_parameters; i++) {
        // If no type parameters were provided, a raw type is desired, so we
        // create a vector of dynamic.
        if (!arguments.IsNull()) {
          type_arg = arguments.TypeAt(i);
          // The parsed type_arg may or may not be finalized.
        }
        full_arguments.SetTypeAt(offset + i, type_arg);
      }
      // Replace the compile-time argument vector (of length zero or
      // num_type_parameters) of this type being finalized with the still
      // unfinalized run-time argument vector (of length num_type_arguments).
      // This type being finalized may be recursively reached via bounds
      // checking or type arguments of its super type.
      type.set_arguments(full_arguments);
      // Finalize the current type arguments of the type, which are still the
      // parsed type arguments.
      if (!arguments.IsNull()) {
        for (intptr_t i = 0; i < num_type_parameters; i++) {
          type_arg = full_arguments.TypeAt(offset + i);
          ASSERT(!type_arg.IsBeingFinalized());
          type_arg = FinalizeType(cls, type_arg, kFinalize, pending_types);
          if (type_arg.IsFunctionType()) {
            const Function& signature_function =
                Function::Handle(zone, Type::Cast(type_arg).signature());
            if (signature_function.IsGeneric()) {
              const String& type_arg_name =
                  String::Handle(zone, type_arg.UserVisibleName());
              const String& type_name =
                  String::Handle(zone, type.UserVisibleName());
              ReportError(cls, type_arg.token_pos(),
                          "generic function type '%s' not allowed as type "
                          "argument of type '%s'",
                          type_arg_name.ToCString(), type_name.ToCString());
            }
          }
          full_arguments.SetTypeAt(offset + i, type_arg);
        }
      }
      if (offset > 0) {
        TrailPtr instantiation_trail = new Trail(zone, 4);
        FinalizeTypeArguments(type_class, full_arguments, offset, pending_types,
                              instantiation_trail);
      }
      if (full_arguments.IsRaw(0, num_type_arguments)) {
        // The parameterized_type is raw. Set its argument vector to null, which
        // is more efficient in type tests.
        full_arguments = TypeArguments::null();
      }
      type.set_arguments(full_arguments);
    } else {
      ASSERT(full_arguments.IsNull());  // Use null vector for raw type.
    }
  }

  ASSERT(full_arguments.IsNull() ||
         !full_arguments.IsRaw(0, num_type_arguments));
  return full_arguments.IsNull() ? 0 : full_arguments.Length();
}

// Finalize the type argument vector 'arguments' of the type defined by the
// class 'cls' parameterized with the type arguments 'cls_args'.
// The vector 'cls_args' is already initialized as a subvector at the correct
// position in the passed in 'arguments' vector.
// The subvector 'cls_args' has length cls.NumTypeParameters() and starts at
// offset cls.NumTypeArguments() - cls.NumTypeParameters() of the 'arguments'
// vector.
// The type argument vector of cls may overlap the type argument vector of its
// super class. In case of an overlap, the overlapped type arguments of the
// super class are already initialized. The still uninitialized ones have an
// offset smaller than 'num_uninitialized_arguments'.
// Example 1 (without overlap):
//   Declared: class C<K, V> extends B<V> { ... }
//             class B<T> extends A<int> { ... }
//   Input:    C<String, double> expressed as
//             cls = C, arguments = [dynamic, dynamic, String, double],
//             num_uninitialized_arguments = 2,
//             i.e. cls_args = [String, double], offset = 2, length = 2.
//   Output:   arguments = [int, double, String, double]
// Example 2 (with overlap):
//   Declared: class C<K, V> extends B<K> { ... }
//             class B<T> extends A<int> { ... }
//   Input:    C<String, double> expressed as
//             cls = C, arguments = [dynamic, String, double],
//             num_uninitialized_arguments = 1,
//             i.e. cls_args = [String, double], offset = 1, length = 2.
//   Output:   arguments = [int, String, double]
//
// It is too early to canonicalize the type arguments of the vector, because
// several type argument vectors may be mutually recursive and finalized at the
// same time. Canonicalization happens when pending types are processed.
// The trail is required to correctly instantiate a recursive type argument
// of the super type.
void ClassFinalizer::FinalizeTypeArguments(const Class& cls,
                                           const TypeArguments& arguments,
                                           intptr_t num_uninitialized_arguments,
                                           PendingTypes* pending_types,
                                           TrailPtr instantiation_trail) {
  ASSERT(arguments.Length() >= cls.NumTypeArguments());
  if (!cls.is_type_finalized()) {
    FinalizeTypeParameters(cls, pending_types);
  }
  AbstractType& super_type = AbstractType::Handle(cls.super_type());
  if (!super_type.IsNull()) {
    const Class& super_class = Class::Handle(super_type.type_class());
    const intptr_t num_super_type_params = super_class.NumTypeParameters();
    const intptr_t num_super_type_args = super_class.NumTypeArguments();
    ASSERT(num_super_type_args ==
           (cls.NumTypeArguments() - cls.NumOwnTypeArguments()));
    if (!super_type.IsFinalized() && !super_type.IsBeingFinalized()) {
      super_type ^= FinalizeType(cls, super_type, kFinalize, pending_types);
      cls.set_super_type(super_type);
    }
    TypeArguments& super_type_args =
        TypeArguments::Handle(super_type.arguments());
    // Offset of super type's type parameters in cls' type argument vector.
    const intptr_t super_offset = num_super_type_args - num_super_type_params;
    // If the super type is raw (i.e. super_type_args is null), set to dynamic.
    AbstractType& super_type_arg = AbstractType::Handle(Type::DynamicType());
    for (intptr_t i = super_offset; i < num_uninitialized_arguments; i++) {
      if (!super_type_args.IsNull()) {
        super_type_arg = super_type_args.TypeAt(i);
        if (!super_type_arg.IsTypeRef()) {
          if (super_type_arg.IsBeingFinalized()) {
            ASSERT(super_type_arg.IsType());
            CheckRecursiveType(cls, super_type_arg, pending_types);
            if (FLAG_trace_type_finalization) {
              THR_Print("Creating TypeRef '%s': '%s'\n",
                        String::Handle(super_type_arg.Name()).ToCString(),
                        super_type_arg.ToCString());
            }
            super_type_arg = TypeRef::New(super_type_arg);
            super_type_args.SetTypeAt(i, super_type_arg);
          } else {
            if (!super_type_arg.IsFinalized()) {
              super_type_arg ^=
                  FinalizeType(cls, super_type_arg, kFinalize, pending_types);
              super_type_args.SetTypeAt(i, super_type_arg);
              // Note that super_type_arg may still not be finalized here, in
              // which case it is a TypeRef to a legal recursive type.
            }
          }
        }
        // Instantiate super_type_arg with the current argument vector.
        if (!super_type_arg.IsInstantiated()) {
          if (FLAG_trace_type_finalization && super_type_arg.IsTypeRef()) {
            AbstractType& ref_type =
                AbstractType::Handle(TypeRef::Cast(super_type_arg).type());
            THR_Print(
                "Instantiating TypeRef '%s': '%s'\n"
                "  instantiator: '%s'\n",
                String::Handle(super_type_arg.Name()).ToCString(),
                ref_type.ToCString(), arguments.ToCString());
          }
          // In the typical case of an F-bounded type, the instantiation of the
          // super_type_arg from arguments is a fixpoint. Take the shortcut.
          // Example: class B<T>; class D<T> extends B<D<T>>;
          // While finalizing D<T>, the super type arg D<T> (a typeref) gets
          // instantiated from vector [T], yielding itself.
          if (super_type_arg.IsTypeRef() &&
              (super_type_arg.arguments() == arguments.raw())) {
            ASSERT(super_type_arg.IsBeingFinalized());
            arguments.SetTypeAt(i, super_type_arg);
            continue;
          }
          super_type_arg = super_type_arg.InstantiateFrom(
              arguments, Object::null_type_arguments(), kNoneFree,
              instantiation_trail, Heap::kOld);
          if (super_type_arg.IsBeingFinalized()) {
            // The super_type_arg was instantiated from a type being finalized.
            // We need to finish finalizing its type arguments.
            ASSERT(super_type_arg.IsTypeRef());
            AbstractType& ref_super_type_arg =
                AbstractType::Handle(TypeRef::Cast(super_type_arg).type());
            if (FLAG_trace_type_finalization) {
              THR_Print("Instantiated TypeRef '%s': '%s'\n",
                        String::Handle(super_type_arg.Name()).ToCString(),
                        ref_super_type_arg.ToCString());
            }
            CheckRecursiveType(cls, ref_super_type_arg, pending_types);
            pending_types->Add(ref_super_type_arg);
            const Class& super_cls =
                Class::Handle(ref_super_type_arg.type_class());
            const TypeArguments& super_args =
                TypeArguments::Handle(ref_super_type_arg.arguments());
            // Mark as finalized before finalizing to avoid cycles.
            ref_super_type_arg.SetIsFinalized();
            // Although the instantiator is different between cls and super_cls,
            // we still need to pass the current instantiation trail as to avoid
            // divergence. Finalizing the type arguments of super_cls may indeed
            // recursively require instantiating the same type_refs already
            // present in the trail (see issue #29949).
            FinalizeTypeArguments(
                super_cls, super_args,
                super_cls.NumTypeArguments() - super_cls.NumTypeParameters(),
                pending_types, instantiation_trail);
            if (FLAG_trace_type_finalization) {
              THR_Print("Finalized instantiated TypeRef '%s': '%s'\n",
                        String::Handle(super_type_arg.Name()).ToCString(),
                        ref_super_type_arg.ToCString());
            }
          }
        }
      }
      arguments.SetTypeAt(i, super_type_arg);
    }
    FinalizeTypeArguments(super_class, arguments, super_offset, pending_types,
                          instantiation_trail);
  }
}

RawAbstractType* ClassFinalizer::FinalizeType(const Class& cls,
                                              const AbstractType& type,
                                              FinalizationKind finalization,
                                              PendingTypes* pending_types) {
  // Only the 'root' type of the graph can be canonicalized, after all depending
  // types have been bound checked.
  ASSERT((pending_types == NULL) || (finalization < kCanonicalize));
  if (type.IsFinalized()) {
    // Ensure type is canonical if canonicalization is requested.
    if ((finalization >= kCanonicalize) && !type.IsCanonical() &&
        type.IsType()) {
      return type.Canonicalize();
    }
    return type.raw();
  }
  ASSERT(finalization >= kFinalize);

  if (type.IsTypeRef()) {
    // The referenced type will be finalized later by the code that set the
    // is_being_finalized mark bit.
    return type.raw();
  }

  // Recursive types must be processed in FinalizeTypeArguments() and cannot be
  // encountered here.
  ASSERT(!type.IsBeingFinalized());

  Zone* zone = Thread::Current()->zone();

  if (FLAG_trace_type_finalization) {
    THR_Print("Finalizing type '%s' for class '%s'\n",
              String::Handle(zone, type.Name()).ToCString(),
              String::Handle(zone, cls.Name()).ToCString());
  }

  if (type.IsTypeParameter()) {
    const TypeParameter& type_parameter = TypeParameter::Cast(type);
    const Class& parameterized_class =
        Class::Handle(zone, type_parameter.parameterized_class());
    intptr_t offset;
    if (!parameterized_class.IsNull()) {
      // The index must reflect the position of this type parameter in the type
      // arguments vector of its parameterized class. The offset to add is the
      // number of type arguments in the super type, which is equal to the
      // difference in number of type arguments and type parameters of the
      // parameterized class.
      offset = parameterized_class.NumTypeArguments() -
               parameterized_class.NumTypeParameters();
    } else {
      const Function& function =
          Function::Handle(zone, type_parameter.parameterized_function());
      ASSERT(!function.IsNull());
      offset = function.NumParentTypeParameters();
    }
    type_parameter.set_index(type_parameter.index() + offset);
    type_parameter.SetIsFinalized();

    if (FLAG_trace_type_finalization) {
      THR_Print("Done finalizing type parameter '%s' with index %" Pd "\n",
                String::Handle(zone, type_parameter.name()).ToCString(),
                type_parameter.index());
    }

    // We do not canonicalize type parameters.
    return type_parameter.raw();
  }

  // At this point, we can only have a Type.
  ASSERT(type.IsType());

  // This type is the root type of the type graph if no pending types queue is
  // allocated yet.
  const bool is_root_type = pending_types == NULL;
  if (is_root_type) {
    pending_types = new PendingTypes(zone, 4);
  }

  const intptr_t num_expanded_type_arguments =
      ExpandAndFinalizeTypeArguments(cls, type, pending_types);

  // Self referencing types may get finalized indirectly.
  if (!type.IsFinalized()) {
    // If the type is a function type, we also need to finalize the types in its
    // signature, i.e. finalize the result type and parameter types of the
    // signature function of this function type.
    // We do this after marking this type as finalized in order to allow a
    // typedef function type to refer to itself via its parameter types and
    // result type.
    if (type.IsFunctionType()) {
      const Type& fun_type = Type::Cast(type);
      const Class& scope_class = Class::Handle(zone, fun_type.type_class());
      if (scope_class.IsTypedefClass()) {
        Function& signature =
            Function::Handle(zone, scope_class.signature_function());
        if (!scope_class.is_type_finalized()) {
          FinalizeSignature(scope_class, signature, finalization);
        }
        // If the function type is a generic typedef, instantiate its signature
        // from its type arguments.
        // Example: typedef F<T> = S Function<S>(T x) has uninstantiated
        // signature (T x) => S.
        // The instantiated signature of F(int) becomes (int x) => S.
        // Note that after this step, the signature of the function type is not
        // identical to the canonical signature of the typedef class anymore.
        if (scope_class.IsGeneric() && !signature.HasInstantiatedSignature()) {
          if (FLAG_trace_type_finalization) {
            THR_Print("Instantiating signature '%s' of typedef '%s'\n",
                      String::Handle(zone, signature.Signature()).ToCString(),
                      String::Handle(zone, fun_type.Name()).ToCString());
          }
          const TypeArguments& instantiator_type_arguments =
              TypeArguments::Handle(zone, fun_type.arguments());
          signature = signature.InstantiateSignatureFrom(
              instantiator_type_arguments, Object::null_type_arguments(),
              kNoneFree, Heap::kOld);
          // Note that if instantiator_type_arguments contains type parameters,
          // as in F<K>, the signature is still uninstantiated (the typedef type
          // parameters were substituted in the signature with typedef type
          // arguments). Note also that the function type parameters were not
          // modified.
          FinalizeSignature(scope_class, signature, finalization);
        }
        fun_type.set_signature(signature);
      } else {
        FinalizeSignature(cls, Function::Handle(zone, fun_type.signature()),
                          finalization);
      }
    }

    if (FLAG_trace_type_finalization) {
      THR_Print("Marking type '%s' as finalized for class '%s'\n",
                String::Handle(zone, type.Name()).ToCString(),
                String::Handle(zone, cls.Name()).ToCString());
    }
    // Mark the type as finalized.
    type.SetIsFinalized();
  }

  if (FLAG_trace_type_finalization) {
    THR_Print("Done finalizing type '%s' with %" Pd " type args: %s\n",
              String::Handle(zone, type.Name()).ToCString(),
              num_expanded_type_arguments, type.ToCString());
  }

  if (finalization >= kCanonicalize) {
    if (FLAG_trace_type_finalization) {
      THR_Print("Canonicalizing type '%s'\n",
                String::Handle(zone, type.Name()).ToCString());
      AbstractType& canonical_type =
          AbstractType::Handle(zone, type.Canonicalize());
      THR_Print("Done canonicalizing type '%s'\n",
                String::Handle(zone, canonical_type.Name()).ToCString());
      return canonical_type.raw();
    }
    return type.Canonicalize();
  } else {
    return type.raw();
  }
}

void ClassFinalizer::FinalizeSignature(const Class& cls,
                                       const Function& function,
                                       FinalizationKind finalization) {
  AbstractType& type = AbstractType::Handle();
  AbstractType& finalized_type = AbstractType::Handle();
  // Finalize function type parameters and their upper bounds.
  const intptr_t num_parent_type_params = function.NumParentTypeParameters();
  const intptr_t num_type_params = function.NumTypeParameters();
  if (num_type_params > 0) {
    TypeParameter& type_param = TypeParameter::Handle();
    const TypeArguments& type_params =
        TypeArguments::Handle(function.type_parameters());
    for (intptr_t i = 0; i < num_type_params; i++) {
      type_param ^= type_params.TypeAt(i);
      if (!type_param.IsFinalized()) {
        type_param.set_index(num_parent_type_params + i);
        type_param.SetIsFinalized();
      }
      type = type_param.bound();
      finalized_type = FinalizeType(cls, type, finalization);
      if (finalized_type.raw() != type.raw()) {
        type_param.set_bound(finalized_type);
      }
    }
  }
  // Finalize result type.
  type = function.result_type();
  finalized_type = FinalizeType(cls, type, finalization);
  // The result type may be malformed or malbounded.
  if (finalized_type.raw() != type.raw()) {
    function.set_result_type(finalized_type);
  }
  // Finalize formal parameter types.
  const intptr_t num_parameters = function.NumParameters();
  for (intptr_t i = 0; i < num_parameters; i++) {
    type = function.ParameterTypeAt(i);
    finalized_type = FinalizeType(cls, type, finalization);
    // The parameter type may be malformed or malbounded.
    if (type.raw() != finalized_type.raw()) {
      function.SetParameterTypeAt(i, finalized_type);
    }
  }
}

// Finalize the upper bounds of the type parameters of class cls.
void ClassFinalizer::FinalizeUpperBounds(const Class& cls,
                                         FinalizationKind finalization) {
  const intptr_t num_type_params = cls.NumTypeParameters();
  TypeParameter& type_param = TypeParameter::Handle();
  AbstractType& bound = AbstractType::Handle();
  const TypeArguments& type_params =
      TypeArguments::Handle(cls.type_parameters());
  ASSERT((type_params.IsNull() && (num_type_params == 0)) ||
         (type_params.Length() == num_type_params));
  for (intptr_t i = 0; i < num_type_params; i++) {
    type_param ^= type_params.TypeAt(i);
    bound = type_param.bound();
    if (bound.IsFunctionType()) {
      const Function& signature_function =
          Function::Handle(Type::Cast(bound).signature());
      if (signature_function.IsGeneric()) {
        const String& bound_name = String::Handle(bound.UserVisibleName());
        const String& type_param_name = String::Handle(type_param.name());
        ReportError(cls, bound.token_pos(),
                    "generic function type '%s' not allowed as bound of "
                    "class type parameter '%s'",
                    bound_name.ToCString(), type_param_name.ToCString());
      }
    }
    // Bound may be finalized, but not canonical yet.
    if (bound.IsCanonical() || bound.IsBeingFinalized()) {
      // A bound involved in F-bounded quantification may form a cycle.
      continue;
    }
    bound = FinalizeType(cls, bound, finalization);
    type_param.set_bound(bound);
  }
}

#if defined(TARGET_ARCH_X64)
static bool IsPotentialExactGeneric(const AbstractType& type) {
  // TODO(dartbug.com/34170) Investigate supporting this for fields with types
  // that depend on type parameters of the enclosing class.
  if (type.IsType() && !type.IsFunctionType() && !type.IsDartFunctionType() &&
      type.IsInstantiated()) {
    const Class& cls = Class::Handle(type.type_class());
    return cls.IsGeneric() && !cls.IsFutureOrClass();
  }

  return false;
}
#else
// TODO(dartbug.com/34170) Support other architectures.
static bool IsPotentialExactGeneric(const AbstractType& type) {
  return false;
}
#endif

void ClassFinalizer::FinalizeMemberTypes(const Class& cls) {
  // Note that getters and setters are explicitly listed as such in the list of
  // functions of a class, so we do not need to consider fields as implicitly
  // generating getters and setters.
  // Most overriding conflicts are only static warnings, i.e. they are not
  // reported as compile-time errors by the vm.
  // Static warning examples are:
  // - a static getter 'v' conflicting with an inherited instance setter 'v='.
  // - a static setter 'v=' conflicting with an inherited instance member 'v'.
  // - an instance member 'v' conflicting with an accessible static member 'v'
  //   or 'v=' of a super class (except that an instance method 'v' does not
  //   conflict with an accessible static setter 'v=' of a super class).
  // The compile-time errors we report are:
  // - a static member 'v' conflicting with an inherited instance member 'v'.
  // - a static setter 'v=' conflicting with an inherited instance setter 'v='.
  // - an instance method conflicting with an inherited instance field or
  //   instance getter.
  // - an instance field or instance getter conflicting with an inherited
  //   instance method.

  // Finalize type of fields and check for conflicts in super classes.
  Isolate* isolate = Isolate::Current();
  Zone* zone = Thread::Current()->zone();
  Array& array = Array::Handle(zone, cls.fields());
  Field& field = Field::Handle(zone);
  AbstractType& type = AbstractType::Handle(zone);
  const intptr_t num_fields = array.Length();
  const bool track_exactness = isolate->use_field_guards();
  for (intptr_t i = 0; i < num_fields; i++) {
    field ^= array.At(i);
    type = field.type();
    type = FinalizeType(cls, type);
    field.SetFieldType(type);
    if (track_exactness && IsPotentialExactGeneric(type)) {
      field.set_static_type_exactness_state(
          StaticTypeExactnessState::Unitialized());
    }
  }
  // Finalize function signatures and check for conflicts in super classes and
  // interfaces.
  array = cls.functions();
  Function& function = Function::Handle(zone);
  const intptr_t num_functions = array.Length();
  for (intptr_t i = 0; i < num_functions; i++) {
    function ^= array.At(i);
    FinalizeSignature(cls, function);
    if (function.IsSetterFunction() || function.IsImplicitSetterFunction()) {
      continue;
    }
    if (function.is_static()) {
      if (function.IsRedirectingFactory()) {
        Type& type = Type::Handle(zone, function.RedirectionType());
        type ^= FinalizeType(cls, type);
        function.SetRedirectionType(type);
      }
    }
  }
}

void ClassFinalizer::FinalizeTypesInClass(const Class& cls) {
  Thread* thread = Thread::Current();
  HANDLESCOPE(thread);
  if (cls.is_type_finalized()) {
    return;
  }
  if (FLAG_trace_class_finalization) {
    THR_Print("Finalize types in %s\n", cls.ToCString());
  }
  if (!IsSuperCycleFree(cls)) {
    const String& name = String::Handle(cls.Name());
    ReportError(cls, cls.token_pos(),
                "class '%s' has a cycle in its superclass relationship",
                name.ToCString());
  }
  // Finalize super class.
  Class& super_class = Class::Handle(cls.SuperClass());
  if (!super_class.IsNull()) {
    FinalizeTypesInClass(super_class);
  }
  // Finalize type parameters before finalizing the super type.
  FinalizeTypeParameters(cls);  // May change super type while applying mixin.
  super_class = cls.SuperClass();  // Get again possibly changed super class.
  ASSERT(super_class.IsNull() || super_class.is_type_finalized());
  FinalizeUpperBounds(cls);
  // Finalize super type.
  AbstractType& super_type = AbstractType::Handle(cls.super_type());
  if (!super_type.IsNull()) {
    super_type = FinalizeType(cls, super_type);
    cls.set_super_type(super_type);
  }
  if (cls.IsTypedefClass()) {
    Function& signature = Function::Handle(cls.signature_function());
    Type& type = Type::Handle(signature.SignatureType());
    ASSERT(type.signature() == signature.raw());
    ASSERT(type.type_class() == cls.raw());

    // Check for illegal self references.
    GrowableArray<intptr_t> visited_aliases;
    if (!IsTypedefCycleFree(cls, type, &visited_aliases)) {
      const String& name = String::Handle(cls.Name());
      ReportError(cls, cls.token_pos(),
                  "typedef '%s' illegally refers to itself", name.ToCString());
    }
    cls.set_is_type_finalized();

    // Finalize the result and parameter types of the signature
    // function of this typedef class.
    FinalizeSignature(cls, signature);  // Does not modify signature type.
    ASSERT(signature.SignatureType() == type.raw());

    // Finalize the signature type of this typedef.
    type ^= FinalizeType(cls, type);
    ASSERT(type.type_class() == cls.raw());

    // If a different canonical signature type is returned, update the signature
    // function of the typedef.
    signature = type.signature();
    signature.SetSignatureType(type);
    cls.set_signature_function(signature);

    // Closure instances do not refer to this typedef as their class, so there
    // is no need to add this typedef class to the subclasses of _Closure.
    ASSERT(super_type.IsNull() || super_type.IsObjectType());

    return;
  }

  // Finalize interface types (but not necessarily interface classes).
  Array& interface_types = Array::Handle(cls.interfaces());
  AbstractType& interface_type = AbstractType::Handle();
  AbstractType& seen_interf = AbstractType::Handle();
  for (intptr_t i = 0; i < interface_types.Length(); i++) {
    interface_type ^= interface_types.At(i);
    interface_type = FinalizeType(cls, interface_type);
    interface_types.SetAt(i, interface_type);

    // Check whether the interface is duplicated. We need to wait with
    // this check until the super type and interface types are finalized,
    // so that we can use Type::Equals() for the test.
    // TODO(regis): This restriction about duplicated interfaces may get lifted.
    ASSERT(interface_type.IsFinalized());
    ASSERT(super_type.IsNull() || super_type.IsFinalized());
    if (!super_type.IsNull() && interface_type.Equals(super_type)) {
      ReportError(cls, cls.token_pos(),
                  "super type '%s' may not be listed in "
                  "implements clause of class '%s'",
                  String::Handle(super_type.Name()).ToCString(),
                  String::Handle(cls.Name()).ToCString());
    }
    for (intptr_t j = 0; j < i; j++) {
      seen_interf ^= interface_types.At(j);
      if (interface_type.Equals(seen_interf)) {
        ReportError(cls, cls.token_pos(),
                    "interface '%s' appears twice in "
                    "implements clause of class '%s'",
                    String::Handle(interface_type.Name()).ToCString(),
                    String::Handle(cls.Name()).ToCString());
      }
    }
  }
  cls.set_is_type_finalized();

  // Add this class to the direct subclasses of the superclass, unless the
  // superclass is Object.
  if (!super_type.IsNull() && !super_type.IsObjectType()) {
    ASSERT(!super_class.IsNull());
    super_class.AddDirectSubclass(cls);
  }

  // Add this class as an implementor to the implemented interface's type
  // classes.
  Zone* zone = thread->zone();
  auto& interface_class = Class::Handle(zone);
  for (intptr_t i = 0; i < interface_types.Length(); ++i) {
    interface_type ^= interface_types.At(i);
    interface_class = interface_type.type_class();
    interface_class.AddDirectImplementor(cls);
  }

  if (FLAG_use_cha_deopt) {
    // Invalidate all CHA code which depends on knowing the implementors of any
    // of the interfaces implemented by this new class.
    ClassTable* class_table = thread->isolate()->class_table();
    GrowableArray<intptr_t> cids;
    InterfaceFinder finder(zone, class_table, &cids);
    finder.FindAllInterfaces(cls);
    for (intptr_t j = 0; j < cids.length(); ++j) {
      interface_class = class_table->At(cids[j]);
      interface_class.DisableCHAImplementorUsers();
    }
  }

  // A top level class is loaded eagerly so just finalize it.
  if (cls.IsTopLevel()) {
    FinalizeClass(cls);
  }
}

void ClassFinalizer::FinalizeClass(const Class& cls) {
  Thread* thread = Thread::Current();
  HANDLESCOPE(thread);
  ASSERT(cls.is_type_finalized());
  if (cls.is_finalized()) {
    return;
  }
  if (FLAG_trace_class_finalization) {
    THR_Print("Finalize %s\n", cls.ToCString());
  }

#if !defined(PRODUCT)
  TimelineDurationScope tds(thread, Timeline::GetCompilerStream(),
                            "ClassFinalizer::FinalizeClass");
#endif  // !defined(PRODUCT)

#if !defined(DART_PRECOMPILED_RUNTIME)
  // If loading from a kernel, make sure that the class is fully loaded.
  // Top level classes are always fully loaded.
  if (!cls.IsTopLevel() && cls.kernel_offset() > 0) {
    kernel::KernelLoader::FinishLoading(cls);
    if (cls.is_finalized()) {
      return;
    }
  }
#endif  // !defined(DART_PRECOMPILED_RUNTIME)

  if (cls.is_patch()) {
    // The fields and functions of a patch class are copied to the
    // patched class after parsing. There is nothing to finalize.
    ASSERT(Array::Handle(cls.functions()).Length() == 0);
    ASSERT(Array::Handle(cls.fields()).Length() == 0);
    cls.set_is_finalized();
    return;
  }
  // Ensure super class is finalized.
  const Class& super = Class::Handle(cls.SuperClass());
  if (!super.IsNull()) {
    FinalizeClass(super);
  }
  // Mark as loaded and finalized.
  cls.Finalize();
  // Every class should have at least a constructor, unless it is a top level
  // class or a typedef class. The Kernel frontend does not create an implicit
  // constructor for abstract classes.
  // Moreover, Dart 2 precompiler (TFA) can tree shake all members if unused.
  ASSERT(FLAG_precompiled_mode || cls.IsTopLevel() || cls.IsTypedefClass() ||
         cls.is_abstract() || (Array::Handle(cls.functions()).Length() > 0));
  FinalizeMemberTypes(cls);
  // Run additional checks after all types are finalized.
  if (cls.is_const()) {
    CheckForLegalConstClass(cls);
  }
  if (FLAG_use_cha_deopt) {
    GrowableArray<intptr_t> cids;
    CollectFinalizedSuperClasses(cls, &cids);
    CollectImmediateSuperInterfaces(cls, &cids);
    RemoveCHAOptimizedCode(cls, cids);
  }

  if (cls.is_enum_class()) {
    AllocateEnumValues(cls);
  }
}

static void AddRelatedClassesToList(
    const Class& cls,
    GrowableHandlePtrArray<const Class>* load_class_list,
    GrowableHandlePtrArray<const Class>* load_patchclass_list) {
  Zone* zone = Thread::Current()->zone();
  Class& load_class = Class::Handle(zone);
  AbstractType& interface_type = Type::Handle(zone);
  Array& interfaces = Array::Handle(zone);

  // Add all the interfaces implemented by the class that have not been
  // already loaded to the load list. Mark the interface as loading so that
  // we don't recursively add it back into the list.
  interfaces ^= cls.interfaces();
  for (intptr_t i = 0; i < interfaces.Length(); i++) {
    interface_type ^= interfaces.At(i);
    load_class ^= interface_type.type_class();
    if (!load_class.is_finalized() &&
        !load_class.is_marked_for_lazy_loading()) {
      load_class_list->Add(load_class);
      load_class.set_is_marked_for_lazy_loading();
    }
  }

  // Walk up the super_class chain and add these classes to the list if they
  // have not been already added to the load class list. Mark the class as
  // loading so that we don't recursively add it back into the list.
  load_class ^= cls.SuperClass();
  while (!load_class.IsNull()) {
    if (!load_class.is_finalized() &&
        !load_class.is_marked_for_lazy_loading()) {
      load_class_list->Add(load_class);
      load_class.set_is_marked_for_lazy_loading();
    }
    load_class ^= load_class.SuperClass();
  }

  // Add patch classes if they exist to the load patchclass list if they have
  // not already been loaded and patched. Mark the class as loading so that
  // we don't recursively add it back into the list.
  load_class ^= cls.GetPatchClass();
  if (!load_class.IsNull()) {
    if (!load_class.is_finalized() &&
        !load_class.is_marked_for_lazy_loading()) {
      load_patchclass_list->Add(load_class);
      load_class.set_is_marked_for_lazy_loading();
    }
  }
}

RawError* ClassFinalizer::LoadClassMembers(const Class& cls) {
  ASSERT(Thread::Current()->IsMutatorThread());
  // If class is a top level class it is already loaded.
  if (cls.IsTopLevel()) {
    return Error::null();
  }
  // If the class is already marked for loading return immediately.
  if (cls.is_marked_for_lazy_loading()) {
    return Error::null();
  }
  // If the class is a typedef class there is no need to try and
  // compile it. Just finalize it directly.
  if (cls.IsTypedefClass()) {
#if defined(DEBUG)
    const Class& closure_cls =
        Class::Handle(Isolate::Current()->object_store()->closure_class());
    ASSERT(closure_cls.is_finalized());
#endif
    LongJumpScope jump;
    if (setjmp(*jump.Set()) == 0) {
      ClassFinalizer::FinalizeClass(cls);
      return Error::null();
    } else {
      return Thread::Current()->StealStickyError();
    }
  }

  Thread* const thread = Thread::Current();
  StackZone zone(thread);
#if !defined(PRODUCT)
  VMTagScope tagScope(thread, VMTag::kClassLoadingTagId);
  TimelineDurationScope tds(thread, Timeline::GetCompilerStream(),
                            "ClassLoading");
  if (tds.enabled()) {
    tds.SetNumArguments(1);
    tds.CopyArgument(0, "class", cls.ToCString());
  }
#endif  // !defined(PRODUCT)

  // We remember all the classes that are being lazy loaded in these lists.
  // This also allows us to reset the marked_for_loading state in case we see
  // an error.
  GrowableHandlePtrArray<const Class> load_class_list(thread->zone(), 4);
  GrowableHandlePtrArray<const Class> load_patchclass_list(thread->zone(), 4);

  // Load the class and all the interfaces it implements and super classes.
  LongJumpScope jump;
  if (setjmp(*jump.Set()) == 0) {
    if (FLAG_trace_class_finalization) {
      THR_Print("Lazy Loading Class '%s'\n", cls.ToCString());
    }

    // Add the primary class which needs to be load to the load list.
    // Mark the class as loading so that we don't recursively add the same
    // class back into the list.
    load_class_list.Add(cls);
    cls.set_is_marked_for_lazy_loading();

    // Add all super classes, interface classes and patch class if one
    // exists to the corresponding lists.
    // NOTE: The load_class_list array keeps growing as more classes are added
    // to it by AddRelatedClassesToList. It is not OK to hoist
    // load_class_list.Length() into a local variable and iterate using the
    // local variable.
    for (intptr_t i = 0; i < load_class_list.length(); i++) {
      AddRelatedClassesToList(load_class_list.At(i), &load_class_list,
                              &load_patchclass_list);
    }

    // Finish lazy loading of these classes and finialize them.
    for (intptr_t i = (load_class_list.length() - 1); i >= 0; i--) {
      const Class& load_class = load_class_list.At(i);
      ASSERT(!load_class.IsNull());
      ClassFinalizer::FinalizeClass(load_class);
      load_class.reset_is_marked_for_lazy_loading();
    }
    for (intptr_t i = (load_patchclass_list.length() - 1); i >= 0; i--) {
      const Class& load_class = load_patchclass_list.At(i);
      ASSERT(!load_class.IsNull());
      ClassFinalizer::FinalizeClass(load_class);
      load_class.reset_is_marked_for_lazy_loading();
    }

    return Error::null();
  } else {
    // Reset the marked for parsing flags.
    for (intptr_t i = 0; i < load_class_list.length(); i++) {
      const Class& load_class = load_class_list.At(i);
      if (load_class.is_marked_for_lazy_loading()) {
        load_class.reset_is_marked_for_lazy_loading();
      }
    }
    for (intptr_t i = 0; i < load_patchclass_list.length(); i++) {
      const Class& load_class = load_patchclass_list.At(i);
      if (load_class.is_marked_for_lazy_loading()) {
        load_class.reset_is_marked_for_lazy_loading();
      }
    }

    return Thread::Current()->StealStickyError();
  }
}

// Allocate instances for each enumeration value, and populate the
// static field 'values'.
// By allocating the instances programmatically, we save an implicit final
// getter function object for each enumeration value and for the
// values field. We also don't have to generate the code for these getters
// from thin air (no source code is available).
void ClassFinalizer::AllocateEnumValues(const Class& enum_cls) {
  Thread* thread = Thread::Current();
  Zone* zone = thread->zone();

  const Field& index_field =
      Field::Handle(zone, enum_cls.LookupInstanceField(Symbols::Index()));
  ASSERT(!index_field.IsNull());

  const Field& name_field = Field::Handle(
      zone, enum_cls.LookupInstanceFieldAllowPrivate(Symbols::_name()));
  ASSERT(!name_field.IsNull());

  const String& enum_name = String::Handle(zone, enum_cls.ScrubbedName());

  const Array& fields = Array::Handle(zone, enum_cls.fields());
  Field& field = Field::Handle(zone);
  Instance& enum_value = Instance::Handle(zone);
  String& enum_ident = String::Handle(zone);

  enum_ident =
      Symbols::FromConcat(thread, Symbols::_DeletedEnumPrefix(), enum_name);
  enum_value = Instance::New(enum_cls, Heap::kOld);
  enum_value.SetField(index_field, Smi::Handle(zone, Smi::New(-1)));
  enum_value.SetField(name_field, enum_ident);
  const char* error_msg = NULL;
  enum_value = enum_value.CheckAndCanonicalize(thread, &error_msg);
  ASSERT(!enum_value.IsNull());
  ASSERT(enum_value.IsCanonical());
  const Field& sentinel = Field::Handle(
      zone, enum_cls.LookupStaticField(Symbols::_DeletedEnumSentinel()));
  ASSERT(!sentinel.IsNull());
  sentinel.SetStaticValue(enum_value, true);
  sentinel.RecordStore(enum_value);

  if (enum_cls.kernel_offset() > 0) {
    Error& error = Error::Handle(zone);
    for (intptr_t i = 0; i < fields.Length(); i++) {
      field = Field::RawCast(fields.At(i));
      if (!field.is_static() || !field.is_const() ||
          (sentinel.raw() == field.raw())) {
        continue;
      }
      // The eager evaluation of the enum values is required for hot-reload (see
      // commit e3ecc87).
      if (!FLAG_precompiled_mode) {
        if (field.IsUninitialized()) {
          error = field.EvaluateInitializer();
          if (!error.IsNull()) {
            ReportError(error);
          }
        }
      }
    }
  } else {
    const String& name_prefix =
        String::Handle(String::Concat(enum_name, Symbols::Dot()));
    Instance& ordinal_value = Instance::Handle(zone);
    Array& values_list = Array::Handle(zone);
    const Field& values_field =
        Field::Handle(zone, enum_cls.LookupStaticField(Symbols::Values()));
    ASSERT(!values_field.IsNull());
    ASSERT(Instance::Handle(zone, values_field.StaticValue()).IsArray());
    values_list = Array::RawCast(values_field.StaticValue());
    const Array& fields = Array::Handle(zone, enum_cls.fields());
    for (intptr_t i = 0; i < fields.Length(); i++) {
      field = Field::RawCast(fields.At(i));
      if (!field.is_static()) continue;
      ordinal_value = field.StaticValue();
      // The static fields that need to be initialized with enum instances
      // contain the smi value of the ordinal number, which was stored in
      // the field by the parser. Other fields contain non-smi values.
      if (!ordinal_value.IsSmi()) continue;
      enum_ident = field.name();
      // Construct the string returned by toString.
      ASSERT(!enum_ident.IsNull());
      // For the user-visible name of the enumeration value, we need to
      // unmangle private names.
      if (enum_ident.CharAt(0) == '_') {
        enum_ident = String::ScrubName(enum_ident);
      }
      enum_ident = Symbols::FromConcat(thread, name_prefix, enum_ident);
      enum_value = Instance::New(enum_cls, Heap::kOld);
      enum_value.SetField(index_field, ordinal_value);
      enum_value.SetField(name_field, enum_ident);
      enum_value = enum_value.CheckAndCanonicalize(thread, &error_msg);
      ASSERT(!enum_value.IsNull());
      ASSERT(enum_value.IsCanonical());
      field.SetStaticValue(enum_value, true);
      field.RecordStore(enum_value);
      intptr_t ord = Smi::Cast(ordinal_value).Value();
      ASSERT(ord < values_list.Length());
      values_list.SetAt(ord, enum_value);
    }
    values_list.MakeImmutable();
    values_list ^= values_list.CheckAndCanonicalize(thread, &error_msg);
    ASSERT(!values_list.IsNull());
  }
}

bool ClassFinalizer::IsSuperCycleFree(const Class& cls) {
  Class& test1 = Class::Handle(cls.raw());
  Class& test2 = Class::Handle(cls.SuperClass());
  // A finalized class has been checked for cycles.
  // Using the hare and tortoise algorithm for locating cycles.
  while (!test1.is_type_finalized() && !test2.IsNull() &&
         !test2.is_type_finalized()) {
    if (test1.raw() == test2.raw()) {
      // Found a cycle.
      return false;
    }
    test1 = test1.SuperClass();
    test2 = test2.SuperClass();
    if (!test2.IsNull()) {
      test2 = test2.SuperClass();
    }
  }
  // No cycles.
  return true;
}

// Returns false if a function type alias illegally refers to itself.
bool ClassFinalizer::IsTypedefCycleFree(const Class& cls,
                                        const AbstractType& type,
                                        GrowableArray<intptr_t>* visited) {
  ASSERT(visited != NULL);
  bool checking_typedef = false;
  if (type.IsType()) {
    AbstractType& other_type = AbstractType::Handle();
    if (type.IsFunctionType()) {
      const Class& scope_class = Class::Handle(type.type_class());
      const Function& signature_function =
          Function::Handle(Type::Cast(type).signature());
      // The signature function of this function type may be a local signature
      // function used in a formal parameter type of the typedef signature, but
      // not the typedef signature function itself, thus not qualifying as an
      // illegal self reference.
      if (!scope_class.is_type_finalized() && scope_class.IsTypedefClass() &&
          (scope_class.signature_function() == signature_function.raw())) {
        checking_typedef = true;
        const intptr_t scope_class_id = scope_class.id();
        ASSERT(visited != NULL);
        for (intptr_t i = 0; i < visited->length(); i++) {
          if ((*visited)[i] == scope_class_id) {
            // We have already visited alias 'scope_class'. We found a cycle.
            return false;
          }
        }
        visited->Add(scope_class_id);
      }
      // Check the bounds of this function type.
      const intptr_t num_type_params = scope_class.NumTypeParameters();
      TypeParameter& type_param = TypeParameter::Handle();
      const TypeArguments& type_params =
          TypeArguments::Handle(scope_class.type_parameters());
      ASSERT((type_params.IsNull() && (num_type_params == 0)) ||
             (type_params.Length() == num_type_params));
      for (intptr_t i = 0; i < num_type_params; i++) {
        type_param ^= type_params.TypeAt(i);
        other_type = type_param.bound();
        if (!IsTypedefCycleFree(cls, other_type, visited)) {
          return false;
        }
      }
      // Check the result type of the signature of this function type.
      other_type = signature_function.result_type();
      if (!IsTypedefCycleFree(cls, other_type, visited)) {
        return false;
      }
      // Check the parameter types of the signature of this function type.
      const intptr_t num_parameters = signature_function.NumParameters();
      for (intptr_t i = 0; i < num_parameters; i++) {
        other_type = signature_function.ParameterTypeAt(i);
        if (!IsTypedefCycleFree(cls, other_type, visited)) {
          return false;
        }
      }
    }
    const TypeArguments& type_args = TypeArguments::Handle(type.arguments());
    if (!type_args.IsNull()) {
      for (intptr_t i = 0; i < type_args.Length(); i++) {
        other_type = type_args.TypeAt(i);
        if (!IsTypedefCycleFree(cls, other_type, visited)) {
          return false;
        }
      }
    }
    if (checking_typedef) {
      visited->RemoveLast();
    }
  }
  return true;
}

// For a class used as an interface marks this class and all its superclasses
// implemented.
//
// Does not mark its interfaces implemented because those would already be
// marked as such.
static void MarkImplemented(Zone* zone, const Class& iface) {
  if (iface.is_implemented()) {
    return;
  }

  Class& cls = Class::Handle(zone, iface.raw());
  AbstractType& type = AbstractType::Handle(zone);

  while (!cls.is_implemented()) {
    cls.set_is_implemented();

    type = cls.super_type();
    if (type.IsNull() || type.IsObjectType()) {
      break;
    }
    cls = type.type_class();
  }
}

// Recursively walks the graph of explicitly declared super type and
// interfaces.
// Reports an error if there is a cycle in the graph. We detect cycles by
// remembering interfaces we've visited in each path through the
// graph. If we visit an interface a second time on a given path,
// we found a loop.
void ClassFinalizer::CheckSuperTypeAndInterfaces(
    const Class& cls,
    GrowableArray<intptr_t>* visited) {
  if (cls.is_cycle_free()) {
    return;
  }
  ASSERT(visited != NULL);
  if (FLAG_trace_class_finalization) {
    THR_Print("Checking super and interfaces: %s\n", cls.ToCString());
  }
  Zone* zone = Thread::Current()->zone();
  const intptr_t cls_index = cls.id();
  for (intptr_t i = 0; i < visited->length(); i++) {
    if ((*visited)[i] == cls_index) {
      // We have already visited class 'cls'. We found a cycle.
      const String& class_name = String::Handle(zone, cls.Name());
      ReportError(cls, cls.token_pos(), "cyclic reference found for class '%s'",
                  class_name.ToCString());
    }
  }

  // If the class/interface has no explicit super class/interfaces, we are done.
  AbstractType& super_type = AbstractType::Handle(zone, cls.super_type());
  Array& super_interfaces = Array::Handle(zone, cls.interfaces());
  if ((super_type.IsNull() || super_type.IsObjectType()) &&
      (super_interfaces.Length() == 0)) {
    cls.set_is_cycle_free();
    return;
  }

  // If cls belongs to core lib or is a synthetic class which could belong to
  // the core library, the restrictions about allowed interfaces are lifted.
  const bool exempt_from_hierarchy_restrictions =
      cls.library() == Library::CoreLibrary() ||
      String::Handle(cls.Name()).Equals(Symbols::DebugClassName());

  // Check the super type and interfaces of cls.
  visited->Add(cls_index);
  AbstractType& interface = AbstractType::Handle(zone);
  Class& interface_class = Class::Handle(zone);

  // Check super type. Failures lead to a longjmp.
  if (super_type.IsDynamicType()) {
    ReportError(cls, cls.token_pos(), "class '%s' may not extend 'dynamic'",
                String::Handle(zone, cls.Name()).ToCString());
  }
  interface_class = super_type.type_class();
  if (interface_class.IsTypedefClass()) {
    ReportError(cls, cls.token_pos(),
                "class '%s' may not extend function type alias '%s'",
                String::Handle(zone, cls.Name()).ToCString(),
                String::Handle(zone, super_type.UserVisibleName()).ToCString());
  }
  if (interface_class.is_enum_class()) {
    ReportError(cls, cls.token_pos(), "class '%s' may not extend enum '%s'",
                String::Handle(zone, cls.Name()).ToCString(),
                String::Handle(zone, interface_class.Name()).ToCString());
  }

  // If cls belongs to core lib or to core lib's implementation, restrictions
  // about allowed interfaces are lifted.
  if (!exempt_from_hierarchy_restrictions) {
    // Prevent extending core implementation classes.
    bool is_error = false;
    switch (interface_class.id()) {
      case kNumberCid:
      case kIntegerCid:  // Class Integer, not int.
      case kSmiCid:
      case kMintCid:
      case kDoubleCid:  // Class Double, not double.
      case kOneByteStringCid:
      case kTwoByteStringCid:
      case kExternalOneByteStringCid:
      case kExternalTwoByteStringCid:
      case kBoolCid:
      case kNullCid:
      case kArrayCid:
      case kImmutableArrayCid:
      case kGrowableObjectArrayCid:
#define DO_NOT_EXTEND_TYPED_DATA_CLASSES(clazz)                                \
  case kTypedData##clazz##Cid:                                                 \
  case kTypedData##clazz##ViewCid:                                             \
  case kExternalTypedData##clazz##Cid:
        CLASS_LIST_TYPED_DATA(DO_NOT_EXTEND_TYPED_DATA_CLASSES)
#undef DO_NOT_EXTEND_TYPED_DATA_CLASSES
      case kByteDataViewCid:
      case kWeakPropertyCid:
        is_error = true;
        break;
      default: {
        // Special case: classes for which we don't have a known class id.
        if (super_type.IsDoubleType() || super_type.IsIntType() ||
            super_type.IsStringType()) {
          is_error = true;
        }
        break;
      }
    }
    if (is_error) {
      const String& interface_name =
          String::Handle(zone, interface_class.Name());
      ReportError(cls, cls.token_pos(), "'%s' is not allowed to extend '%s'",
                  String::Handle(zone, cls.Name()).ToCString(),
                  interface_name.ToCString());
    }
  }
  // Now check the super interfaces of the super type.
  CheckSuperTypeAndInterfaces(interface_class, visited);

  // Check interfaces. Failures lead to a longjmp.
  for (intptr_t i = 0; i < super_interfaces.Length(); i++) {
    interface ^= super_interfaces.At(i);
    ASSERT(!interface.IsTypeParameter());  // Should be detected by parser.
    if (interface.IsDynamicType()) {
      ReportError(cls, cls.token_pos(),
                  "'dynamic' may not be used as interface");
    }
    interface_class = interface.type_class();
    if (interface_class.IsTypedefClass()) {
      const String& interface_name =
          String::Handle(zone, interface_class.Name());
      ReportError(cls, cls.token_pos(),
                  "function type alias '%s' may not be used as interface",
                  interface_name.ToCString());
    }
    if (interface_class.is_enum_class()) {
      const String& interface_name =
          String::Handle(zone, interface_class.Name());
      ReportError(cls, cls.token_pos(),
                  "enum '%s' may not be used as interface",
                  interface_name.ToCString());
    }
    // Verify that unless cls belongs to core lib, it cannot extend, implement,
    // or mixin any of Null, bool, num, int, double, String, dynamic.
    if (!exempt_from_hierarchy_restrictions) {
      if (interface.IsBoolType() || interface.IsNullType() ||
          interface.IsNumberType() || interface.IsIntType() ||
          interface.IsDoubleType() || interface.IsStringType() ||
          interface.IsDynamicType()) {
        const String& interface_name =
            String::Handle(zone, interface_class.Name());
        ReportError(cls, cls.token_pos(),
                    "'%s' is not allowed to extend or implement '%s'",
                    String::Handle(zone, cls.Name()).ToCString(),
                    interface_name.ToCString());
      }
    }

    // Now check the super interfaces.
    CheckSuperTypeAndInterfaces(interface_class, visited);
    MarkImplemented(zone, interface_class);
  }
  visited->RemoveLast();
  cls.set_is_cycle_free();
}

// A class is marked as constant if it has one constant constructor.
// A constant class can only have final instance fields.
// Note: we must check for cycles before checking for const properties.
void ClassFinalizer::CheckForLegalConstClass(const Class& cls) {
  ASSERT(cls.is_const());
  const Array& fields_array = Array::Handle(cls.fields());
  intptr_t len = fields_array.Length();
  Field& field = Field::Handle();
  for (intptr_t i = 0; i < len; i++) {
    field ^= fields_array.At(i);
    if (!field.is_static() && !field.is_final()) {
      const String& class_name = String::Handle(cls.Name());
      const String& field_name = String::Handle(field.name());
      ReportError(cls, field.token_pos(),
                  "const class '%s' has non-final field '%s'",
                  class_name.ToCString(), field_name.ToCString());
    }
  }
}

void ClassFinalizer::PrintClassInformation(const Class& cls) {
  Thread* thread = Thread::Current();
  HANDLESCOPE(thread);
  const String& class_name = String::Handle(cls.Name());
  THR_Print("class '%s'", class_name.ToCString());
  const Library& library = Library::Handle(cls.library());
  if (!library.IsNull()) {
    THR_Print(" library '%s%s':\n", String::Handle(library.url()).ToCString(),
              String::Handle(library.private_key()).ToCString());
  } else {
    THR_Print(" (null library):\n");
  }
  const AbstractType& super_type = AbstractType::Handle(cls.super_type());
  if (super_type.IsNull()) {
    THR_Print("  Super: NULL");
  } else {
    const String& super_name = String::Handle(super_type.Name());
    THR_Print("  Super: %s", super_name.ToCString());
  }
  const Array& interfaces_array = Array::Handle(cls.interfaces());
  if (interfaces_array.Length() > 0) {
    THR_Print("; interfaces: ");
    AbstractType& interface = AbstractType::Handle();
    intptr_t len = interfaces_array.Length();
    for (intptr_t i = 0; i < len; i++) {
      interface ^= interfaces_array.At(i);
      THR_Print("  %s ", interface.ToCString());
    }
  }
  THR_Print("\n");
  const Array& functions_array = Array::Handle(cls.functions());
  Function& function = Function::Handle();
  intptr_t len = functions_array.Length();
  for (intptr_t i = 0; i < len; i++) {
    function ^= functions_array.At(i);
    THR_Print("  %s\n", function.ToCString());
  }
  const Array& fields_array = Array::Handle(cls.fields());
  Field& field = Field::Handle();
  len = fields_array.Length();
  for (intptr_t i = 0; i < len; i++) {
    field ^= fields_array.At(i);
    THR_Print("  %s\n", field.ToCString());
  }
}

void ClassFinalizer::ReportError(const Error& error) {
  Report::LongJump(error);
  UNREACHABLE();
}

void ClassFinalizer::ReportErrors(const Error& prev_error,
                                  const Class& cls,
                                  TokenPosition token_pos,
                                  const char* format,
                                  ...) {
  va_list args;
  va_start(args, format);
  const Script& script = Script::Handle(cls.script());
  Report::LongJumpV(prev_error, script, token_pos, format, args);
  va_end(args);
  UNREACHABLE();
}

void ClassFinalizer::ReportError(const Class& cls,
                                 TokenPosition token_pos,
                                 const char* format,
                                 ...) {
  va_list args;
  va_start(args, format);
  const Script& script = Script::Handle(cls.script());
  Report::MessageV(Report::kError, script, token_pos, Report::AtLocation,
                   format, args);
  va_end(args);
  UNREACHABLE();
}

void ClassFinalizer::VerifyImplicitFieldOffsets() {
#ifdef DEBUG
  Thread* thread = Thread::Current();
  Isolate* isolate = thread->isolate();

  if (isolate->obfuscate()) {
    // Field names are obfuscated.
    return;
  }

  Zone* zone = thread->zone();
  const ClassTable& class_table = *(isolate->class_table());
  Class& cls = Class::Handle(zone);
  Array& fields_array = Array::Handle(zone);
  Field& field = Field::Handle(zone);
  String& name = String::Handle(zone);
  String& expected_name = String::Handle(zone);
  Error& error = Error::Handle(zone);

  // First verify field offsets of all the TypedDataView classes.
  for (intptr_t cid = kTypedDataInt8ArrayViewCid;
       cid <= kTypedDataFloat32x4ArrayViewCid; cid++) {
    cls = class_table.At(cid);  // Get the TypedDataView class.
    error = cls.EnsureIsFinalized(thread);
    ASSERT(error.IsNull());
    cls = cls.SuperClass();  // Get it's super class '_TypedListView'.
    cls = cls.SuperClass();
    fields_array ^= cls.fields();
    ASSERT(fields_array.Length() == TypedDataView::NumberOfFields());
    field ^= fields_array.At(0);
    ASSERT(field.Offset() == TypedDataView::data_offset());
    name ^= field.name();
    expected_name ^= String::New("_typedData");
    ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
    field ^= fields_array.At(1);
    ASSERT(field.Offset() == TypedDataView::offset_in_bytes_offset());
    name ^= field.name();
    ASSERT(name.Equals("offsetInBytes"));
    field ^= fields_array.At(2);
    ASSERT(field.Offset() == TypedDataView::length_offset());
    name ^= field.name();
    ASSERT(name.Equals("length"));
  }

  // Now verify field offsets of '_ByteDataView' class.
  cls = class_table.At(kByteDataViewCid);
  error = cls.EnsureIsFinalized(thread);
  ASSERT(error.IsNull());
  fields_array ^= cls.fields();
  ASSERT(fields_array.Length() == TypedDataView::NumberOfFields());
  field ^= fields_array.At(0);
  ASSERT(field.Offset() == TypedDataView::data_offset());
  name ^= field.name();
  expected_name ^= String::New("_typedData");
  ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
  field ^= fields_array.At(1);
  ASSERT(field.Offset() == TypedDataView::offset_in_bytes_offset());
  name ^= field.name();
  expected_name ^= String::New("_offset");
  ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
  field ^= fields_array.At(2);
  ASSERT(field.Offset() == TypedDataView::length_offset());
  name ^= field.name();
  ASSERT(name.Equals("length"));

  // Now verify field offsets of '_ByteBuffer' class.
  cls = class_table.At(kByteBufferCid);
  error = cls.EnsureIsFinalized(thread);
  ASSERT(error.IsNull());
  fields_array ^= cls.fields();
  ASSERT(fields_array.Length() == ByteBuffer::NumberOfFields());
  field ^= fields_array.At(0);
  ASSERT(field.Offset() == ByteBuffer::data_offset());
  name ^= field.name();
  expected_name ^= String::New("_data");
  ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
#endif
}

void ClassFinalizer::SortClasses() {
  Thread* T = Thread::Current();
  Zone* Z = T->zone();
  Isolate* I = T->isolate();
  ClassTable* table = I->class_table();
  intptr_t num_cids = table->NumCids();
  intptr_t* old_to_new_cid = new intptr_t[num_cids];
  for (intptr_t cid = 0; cid < kNumPredefinedCids; cid++) {
    old_to_new_cid[cid] = cid;  // The predefined classes cannot change cids.
  }
  for (intptr_t cid = kNumPredefinedCids; cid < num_cids; cid++) {
    old_to_new_cid[cid] = -1;
  }

  intptr_t next_new_cid = kNumPredefinedCids;
  GrowableArray<intptr_t> dfs_stack;
  Class& cls = Class::Handle(Z);
  GrowableObjectArray& subclasses = GrowableObjectArray::Handle(Z);

  // Object doesn't use its subclasses list.
  for (intptr_t cid = kNumPredefinedCids; cid < num_cids; cid++) {
    if (!table->HasValidClassAt(cid)) {
      continue;
    }
    cls = table->At(cid);
    if (cls.is_patch()) {
      continue;
    }
    if (cls.SuperClass() == I->object_store()->object_class()) {
      dfs_stack.Add(cid);
    }
  }

  while (dfs_stack.length() > 0) {
    intptr_t cid = dfs_stack.RemoveLast();
    ASSERT(table->HasValidClassAt(cid));
    cls = table->At(cid);
    ASSERT(!cls.IsNull());
    if (old_to_new_cid[cid] == -1) {
      old_to_new_cid[cid] = next_new_cid++;
      if (FLAG_trace_class_finalization) {
        THR_Print("%" Pd ": %s, was %" Pd "\n", old_to_new_cid[cid],
                  cls.ToCString(), cid);
      }
    }
    subclasses = cls.direct_subclasses();
    if (!subclasses.IsNull()) {
      for (intptr_t i = 0; i < subclasses.Length(); i++) {
        cls ^= subclasses.At(i);
        ASSERT(!cls.IsNull());
        dfs_stack.Add(cls.id());
      }
    }
  }

  // Top-level classes, typedefs, patch classes, etc.
  for (intptr_t cid = kNumPredefinedCids; cid < num_cids; cid++) {
    if (old_to_new_cid[cid] == -1) {
      old_to_new_cid[cid] = next_new_cid++;
      if (FLAG_trace_class_finalization && table->HasValidClassAt(cid)) {
        cls = table->At(cid);
        THR_Print("%" Pd ": %s, was %" Pd "\n", old_to_new_cid[cid],
                  cls.ToCString(), cid);
      }
    }
  }
  ASSERT(next_new_cid == num_cids);

  RemapClassIds(old_to_new_cid);
  delete[] old_to_new_cid;
  RehashTypes();  // Types use cid's as part of their hashes.
}

class CidRewriteVisitor : public ObjectVisitor {
 public:
  explicit CidRewriteVisitor(intptr_t* old_to_new_cids)
      : old_to_new_cids_(old_to_new_cids) {}

  intptr_t Map(intptr_t cid) {
    ASSERT(cid != -1);
    return old_to_new_cids_[cid];
  }

  void VisitObject(RawObject* obj) {
    if (obj->IsClass()) {
      RawClass* cls = Class::RawCast(obj);
      cls->ptr()->id_ = Map(cls->ptr()->id_);
    } else if (obj->IsField()) {
      RawField* field = Field::RawCast(obj);
      field->ptr()->guarded_cid_ = Map(field->ptr()->guarded_cid_);
      field->ptr()->is_nullable_ = Map(field->ptr()->is_nullable_);
    } else if (obj->IsTypeParameter()) {
      RawTypeParameter* param = TypeParameter::RawCast(obj);
      param->ptr()->parameterized_class_id_ =
          Map(param->ptr()->parameterized_class_id_);
    } else if (obj->IsType()) {
      RawType* type = Type::RawCast(obj);
      RawObject* id = type->ptr()->type_class_id_;
      if (!id->IsHeapObject()) {
        type->ptr()->type_class_id_ =
            Smi::New(Map(Smi::Value(Smi::RawCast(id))));
      }
    } else {
      intptr_t old_cid = obj->GetClassId();
      intptr_t new_cid = Map(old_cid);
      if (old_cid != new_cid) {
        // Don't touch objects that are unchanged. In particular, Instructions,
        // which are write-protected.
        obj->SetClassId(new_cid);
      }
    }
  }

 private:
  intptr_t* old_to_new_cids_;
};

void ClassFinalizer::RemapClassIds(intptr_t* old_to_new_cid) {
  Thread* T = Thread::Current();
  Isolate* I = T->isolate();

  // Code, ICData, allocation stubs have now-invalid cids.
  ClearAllCode();

  {
    HeapIterationScope his(T);
    I->set_remapping_cids(true);

    // Update the class table. Do it before rewriting cids in headers, as the
    // heap walkers load an object's size *after* calling the visitor.
    I->class_table()->Remap(old_to_new_cid);

    // Rewrite cids in headers and cids in Classes, Fields, Types and
    // TypeParameters.
    {
      CidRewriteVisitor visitor(old_to_new_cid);
      I->heap()->VisitObjects(&visitor);
    }
    I->set_remapping_cids(false);
  }

#if defined(DEBUG)
  I->class_table()->Validate();
  I->heap()->Verify();
#endif
}

// Clears the cached canonicalized hash codes for all instances which directly
// (or indirectly) depend on class ids.
//
// In the Dart VM heap the following instances directly use cids for the
// computation of canonical hash codes:
//
//    * RawType (due to RawType::type_class_id_)
//    * RawTypeParameter (due to RawTypeParameter::parameterized_class_id_)
//
// The following instances use cids for the computation of canonical hash codes
// indirectly:
//
//    * RawTypeRef (due to RawTypeRef::type_->type_class_id)
//    * RawType (due to RawType::signature_'s result/parameter types)
//    * RawTypeArguments (due to type references)
//    * RawInstance (due to instance fields)
//    * RawArray (due to type arguments & array entries)
//
// Caching of the canonical hash codes happens for:
//
//    * RawType::hash_
//    * RawTypeParameter::hash_
//    * RawTypeArguments::hash_
//
// No caching of canonical hash codes (i.e. it gets re-computed every time)
// happens for:
//
//    * RawTypeRef (computed via RawTypeRef::type_->type_class_id)
//    * RawInstance (computed via size & fields)
//    * RawArray (computed via type arguments & array entries)
//
// Usages of canonical hash codes are:
//
//   * ObjectStore::canonical_types()
//   * ObjectStore::canonical_type_arguments()
//   * Class::constants()
//
class ClearTypeHashVisitor : public ObjectVisitor {
 public:
  explicit ClearTypeHashVisitor(Zone* zone)
      : type_param_(TypeParameter::Handle(zone)),
        type_(Type::Handle(zone)),
        type_args_(TypeArguments::Handle(zone)) {}

  void VisitObject(RawObject* obj) {
    if (obj->IsTypeParameter()) {
      type_param_ ^= obj;
      type_param_.SetHash(0);
    } else if (obj->IsType()) {
      type_ ^= obj;
      type_.SetHash(0);
    } else if (obj->IsTypeArguments()) {
      type_args_ ^= obj;
      type_args_.SetHash(0);
    }
  }

 private:
  TypeParameter& type_param_;
  Type& type_;
  TypeArguments& type_args_;
};

void ClassFinalizer::RehashTypes() {
  Thread* T = Thread::Current();
  Zone* Z = T->zone();
  Isolate* I = T->isolate();

  // Clear all cached hash values.
  {
    HeapIterationScope his(T);
    ClearTypeHashVisitor visitor(Z);
    I->heap()->VisitObjects(&visitor);
  }

  // Rehash the canonical Types table.
  ObjectStore* object_store = I->object_store();
  GrowableObjectArray& types =
      GrowableObjectArray::Handle(Z, GrowableObjectArray::New());
  Array& types_array = Array::Handle(Z);
  Type& type = Type::Handle(Z);
  {
    CanonicalTypeSet types_table(Z, object_store->canonical_types());
    types_array = HashTables::ToArray(types_table, false);
    for (intptr_t i = 0; i < types_array.Length(); i++) {
      type ^= types_array.At(i);
      types.Add(type);
    }
    types_table.Release();
  }

  intptr_t dict_size = Utils::RoundUpToPowerOfTwo(types.Length() * 4 / 3);
  types_array = HashTables::New<CanonicalTypeSet>(dict_size, Heap::kOld);
  CanonicalTypeSet types_table(Z, types_array.raw());
  for (intptr_t i = 0; i < types.Length(); i++) {
    type ^= types.At(i);
    bool present = types_table.Insert(type);
    ASSERT(!present || type.IsRecursive());
  }
  object_store->set_canonical_types(types_table.Release());

  // Rehash the canonical TypeArguments table.
  Array& typeargs_array = Array::Handle(Z);
  GrowableObjectArray& typeargs =
      GrowableObjectArray::Handle(Z, GrowableObjectArray::New());
  TypeArguments& typearg = TypeArguments::Handle(Z);
  {
    CanonicalTypeArgumentsSet typeargs_table(
        Z, object_store->canonical_type_arguments());
    typeargs_array = HashTables::ToArray(typeargs_table, false);
    for (intptr_t i = 0; i < typeargs_array.Length(); i++) {
      typearg ^= typeargs_array.At(i);
      typeargs.Add(typearg);
    }
    typeargs_table.Release();
  }

  // The canonical constant tables use canonical hashcodes which can change
  // due to cid-renumbering.
  I->RehashConstants();

  dict_size = Utils::RoundUpToPowerOfTwo(typeargs.Length() * 4 / 3);
  typeargs_array =
      HashTables::New<CanonicalTypeArgumentsSet>(dict_size, Heap::kOld);
  CanonicalTypeArgumentsSet typeargs_table(Z, typeargs_array.raw());
  for (intptr_t i = 0; i < typeargs.Length(); i++) {
    typearg ^= typeargs.At(i);
    bool present = typeargs_table.Insert(typearg);
    ASSERT(!present || typearg.IsRecursive());
  }
  object_store->set_canonical_type_arguments(typeargs_table.Release());
}

void ClassFinalizer::ClearAllCode(bool including_nonchanging_cids) {
  class ClearCodeFunctionVisitor : public FunctionVisitor {
    void Visit(const Function& function) {
      function.ClearCode();
      function.ClearICDataArray();
    }
  };
  ClearCodeFunctionVisitor function_visitor;
  ProgramVisitor::VisitFunctions(&function_visitor);

  class ClearCodeClassVisitor : public ClassVisitor {
   public:
    explicit ClearCodeClassVisitor(bool force) : force_(force) {}

    void Visit(const Class& cls) {
      if (force_ || cls.id() >= kNumPredefinedCids) {
        cls.DisableAllocationStub();
      }
    }

   private:
    bool force_;
  };
  ClearCodeClassVisitor class_visitor(including_nonchanging_cids);
  ProgramVisitor::VisitClasses(&class_visitor);

  // Apart from normal function code and allocation stubs we have two global
  // code objects to clear.
  if (including_nonchanging_cids) {
    auto thread = Thread::Current();
    auto object_store = thread->isolate()->object_store();
    auto& null_code = Code::Handle(thread->zone());
    object_store->set_build_method_extractor_code(null_code);

    auto& miss_function = Function::Handle(
        thread->zone(), object_store->megamorphic_miss_function());
    miss_function.ClearCode();
    object_store->SetMegamorphicMissHandler(null_code, miss_function);
  }
}

}  // namespace dart