// Copyright (c) 2018, 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.

import 'package:kernel/ast.dart' as ir;
import 'package:front_end/src/api_unstable/dart2js.dart' show Link;

import '../closure.dart';
import '../common.dart';
import '../common/names.dart';
import '../common_elements.dart' show JCommonElements, JElementEnvironment;
import '../constants/constant_system.dart';
import '../deferred_load.dart';
import '../diagnostics/diagnostic_listener.dart';
import '../elements/entities.dart';
import '../elements/entity_utils.dart' as utils;
import '../elements/names.dart';
import '../elements/types.dart';
import '../environment.dart';
import '../inferrer/abstract_value_domain.dart';
import '../js_emitter/sorter.dart';
import '../js_backend/annotations.dart';
import '../js_backend/allocator_analysis.dart';
import '../js_backend/backend_usage.dart';
import '../js_backend/constant_system_javascript.dart';
import '../js_backend/interceptor_data.dart';
import '../js_backend/native_data.dart';
import '../js_backend/no_such_method_registry.dart';
import '../js_backend/runtime_types.dart';
import '../js_model/locals.dart';
import '../ordered_typeset.dart';
import '../options.dart';
import '../serialization/serialization.dart';
import '../universe/class_hierarchy.dart';
import '../universe/class_set.dart';
import '../universe/function_set.dart' show FunctionSet;
import '../universe/selector.dart';
import '../world.dart';
import 'element_map.dart';
import 'element_map_impl.dart';
import 'locals.dart';

class JsClosedWorld implements JClosedWorld {
  static const String tag = 'closed-world';

  final NativeData nativeData;
  final InterceptorData interceptorData;
  final BackendUsage backendUsage;
  final NoSuchMethodData noSuchMethodData;

  FunctionSet _allFunctions;

  final Map<ClassEntity, Set<ClassEntity>> mixinUses;
  Map<ClassEntity, List<ClassEntity>> _liveMixinUses;

  final Map<ClassEntity, Set<ClassEntity>> typesImplementedBySubclasses;

  final Map<ClassEntity, Map<ClassEntity, bool>> _subtypeCoveredByCache =
      <ClassEntity, Map<ClassEntity, bool>>{};

  // TODO(johnniwinther): Can this be derived from [ClassSet]s?
  final Set<ClassEntity> implementedClasses;

  final Set<MemberEntity> liveInstanceMembers;

  /// Members that are written either directly or through a setter selector.
  final Set<MemberEntity> assignedInstanceMembers;

  final Set<ClassEntity> liveNativeClasses;

  final Set<MemberEntity> processedMembers;

  final ClassHierarchy classHierarchy;

  final JsKernelToElementMap elementMap;
  final RuntimeTypesNeed rtiNeed;
  AbstractValueDomain _abstractValueDomain;
  final JAllocatorAnalysis allocatorAnalysis;
  final AnnotationsData annotationsData;
  final GlobalLocalsMap globalLocalsMap;
  final ClosureData closureDataLookup;
  final OutputUnitData outputUnitData;
  Sorter _sorter;

  JsClosedWorld(
      this.elementMap,
      this.nativeData,
      this.interceptorData,
      this.backendUsage,
      this.rtiNeed,
      this.allocatorAnalysis,
      this.noSuchMethodData,
      this.implementedClasses,
      this.liveNativeClasses,
      this.liveInstanceMembers,
      this.assignedInstanceMembers,
      this.processedMembers,
      this.mixinUses,
      this.typesImplementedBySubclasses,
      this.classHierarchy,
      AbstractValueStrategy abstractValueStrategy,
      this.annotationsData,
      this.globalLocalsMap,
      this.closureDataLookup,
      this.outputUnitData) {
    _abstractValueDomain = abstractValueStrategy.createDomain(this);
  }

  /// Deserializes a [JsClosedWorld] object from [source].
  factory JsClosedWorld.readFromDataSource(
      CompilerOptions options,
      DiagnosticReporter reporter,
      Environment environment,
      AbstractValueStrategy abstractValueStrategy,
      ir.Component component,
      DataSource source) {
    source.begin(tag);

    JsKernelToElementMap elementMap =
        new JsKernelToElementMap.readFromDataSource(
            options, reporter, environment, component, source);
    GlobalLocalsMap globalLocalsMap =
        new GlobalLocalsMap.readFromDataSource(source);
    source.registerLocalLookup(new LocalLookupImpl(globalLocalsMap));
    ClassHierarchy classHierarchy = new ClassHierarchy.readFromDataSource(
        source, elementMap.commonElements);
    NativeData nativeData = new NativeData.readFromDataSource(
        source, elementMap.elementEnvironment);
    elementMap.nativeBasicData = nativeData;
    InterceptorData interceptorData = new InterceptorData.readFromDataSource(
        source, nativeData, elementMap.commonElements);
    BackendUsage backendUsage = new BackendUsage.readFromDataSource(source);
    RuntimeTypesNeed rtiNeed = new RuntimeTypesNeed.readFromDataSource(
        source, elementMap.elementEnvironment);
    JAllocatorAnalysis allocatorAnalysis =
        new JAllocatorAnalysis.readFromDataSource(source, options);
    NoSuchMethodData noSuchMethodData =
        new NoSuchMethodData.readFromDataSource(source);

    Set<ClassEntity> implementedClasses = source.readClasses().toSet();
    Set<ClassEntity> liveNativeClasses = source.readClasses().toSet();
    Set<MemberEntity> liveInstanceMembers = source.readMembers().toSet();
    Set<MemberEntity> assignedInstanceMembers = source.readMembers().toSet();
    Set<MemberEntity> processedMembers = source.readMembers().toSet();
    Map<ClassEntity, Set<ClassEntity>> mixinUses =
        source.readClassMap(() => source.readClasses().toSet());
    Map<ClassEntity, Set<ClassEntity>> typesImplementedBySubclasses =
        source.readClassMap(() => source.readClasses().toSet());

    AnnotationsData annotationsData =
        new AnnotationsData.readFromDataSource(source);

    ClosureData closureData =
        new ClosureData.readFromDataSource(elementMap, source);

    OutputUnitData outputUnitData =
        new OutputUnitData.readFromDataSource(source);

    source.end(tag);

    return new JsClosedWorld(
        elementMap,
        nativeData,
        interceptorData,
        backendUsage,
        rtiNeed,
        allocatorAnalysis,
        noSuchMethodData,
        implementedClasses,
        liveNativeClasses,
        liveInstanceMembers,
        assignedInstanceMembers,
        processedMembers,
        mixinUses,
        typesImplementedBySubclasses,
        classHierarchy,
        abstractValueStrategy,
        annotationsData,
        globalLocalsMap,
        closureData,
        outputUnitData);
  }

  /// Serializes this [JsClosedWorld] to [sink].
  void writeToDataSink(DataSink sink) {
    sink.begin(tag);
    elementMap.writeToDataSink(sink);
    globalLocalsMap.writeToDataSink(sink);

    classHierarchy.writeToDataSink(sink);
    nativeData.writeToDataSink(sink);
    interceptorData.writeToDataSink(sink);
    backendUsage.writeToDataSink(sink);
    rtiNeed.writeToDataSink(sink);
    allocatorAnalysis.writeToDataSink(sink);
    noSuchMethodData.writeToDataSink(sink);
    sink.writeClasses(implementedClasses);
    sink.writeClasses(liveNativeClasses);
    sink.writeMembers(liveInstanceMembers);
    sink.writeMembers(assignedInstanceMembers);
    sink.writeMembers(processedMembers);
    sink.writeClassMap(
        mixinUses, (Set<ClassEntity> set) => sink.writeClasses(set));
    sink.writeClassMap(typesImplementedBySubclasses,
        (Set<ClassEntity> set) => sink.writeClasses(set));
    annotationsData.writeToDataSink(sink);
    closureDataLookup.writeToDataSink(sink);
    outputUnitData.writeToDataSink(sink);
    sink.end(tag);
  }

  ConstantSystem get constantSystem => JavaScriptConstantSystem.only;

  JElementEnvironment get elementEnvironment => elementMap.elementEnvironment;

  JCommonElements get commonElements => elementMap.commonElements;

  DartTypes get dartTypes => elementMap.types;

  /// Returns `true` if [cls] is implemented by an instantiated class.
  bool isImplemented(ClassEntity cls) {
    return implementedClasses.contains(cls);
  }

  @override
  ClassEntity getLubOfInstantiatedSubclasses(ClassEntity cls) {
    if (nativeData.isJsInteropClass(cls)) {
      return commonElements.jsJavaScriptObjectClass;
    }
    ClassHierarchyNode hierarchy = classHierarchy.getClassHierarchyNode(cls);
    return hierarchy != null
        ? hierarchy.getLubOfInstantiatedSubclasses()
        : null;
  }

  @override
  ClassEntity getLubOfInstantiatedSubtypes(ClassEntity cls) {
    if (nativeData.isJsInteropClass(cls)) {
      return commonElements.jsJavaScriptObjectClass;
    }
    ClassSet classSet = classHierarchy.getClassSet(cls);
    return classSet != null ? classSet.getLubOfInstantiatedSubtypes() : null;
  }

  /// Returns `true` if [cls] is mixed into a live class.
  bool isUsedAsMixin(ClassEntity cls) {
    return !mixinUsesOf(cls).isEmpty;
  }

  /// Returns `true` if any live class that mixes in [cls] implements [type].
  bool hasAnySubclassOfMixinUseThatImplements(
      ClassEntity cls, ClassEntity type) {
    return mixinUsesOf(cls)
        .any((use) => hasAnySubclassThatImplements(use, type));
  }

  /// Returns `true` if every subtype of [x] is a subclass of [y] or a subclass
  /// of a mixin application of [y].
  bool everySubtypeIsSubclassOfOrMixinUseOf(ClassEntity x, ClassEntity y) {
    Map<ClassEntity, bool> secondMap =
        _subtypeCoveredByCache[x] ??= <ClassEntity, bool>{};
    return secondMap[y] ??= classHierarchy.subtypesOf(x).every(
        (ClassEntity cls) =>
            classHierarchy.isSubclassOf(cls, y) ||
            isSubclassOfMixinUseOf(cls, y));
  }

  /// Returns `true` if any subclass of [superclass] implements [type].
  bool hasAnySubclassThatImplements(ClassEntity superclass, ClassEntity type) {
    Set<ClassEntity> subclasses = typesImplementedBySubclasses[superclass];
    if (subclasses == null) return false;
    return subclasses.contains(type);
  }

  @override
  bool needsNoSuchMethod(
      ClassEntity base, Selector selector, ClassQuery query) {
    /// Returns `true` if subclasses in the [rootNode] tree needs noSuchMethod
    /// handling.
    bool subclassesNeedNoSuchMethod(ClassHierarchyNode rootNode) {
      if (!rootNode.isInstantiated) {
        // No subclass needs noSuchMethod handling since they are all
        // uninstantiated.
        return false;
      }
      ClassEntity rootClass = rootNode.cls;
      if (_hasConcreteMatch(rootClass, selector)) {
        // The root subclass has a concrete implementation so no subclass needs
        // noSuchMethod handling.
        return false;
      } else if (rootNode.isExplicitlyInstantiated) {
        // The root class need noSuchMethod handling.
        return true;
      }
      IterationStep result = rootNode.forEachSubclass((ClassEntity subclass) {
        if (_hasConcreteMatch(subclass, selector,
            stopAtSuperclass: rootClass)) {
          // Found a match - skip all subclasses.
          return IterationStep.SKIP_SUBCLASSES;
        } else {
          // Stop fast - we found a need for noSuchMethod handling.
          return IterationStep.STOP;
        }
      }, ClassHierarchyNode.EXPLICITLY_INSTANTIATED, strict: true);
      // We stopped fast so we need noSuchMethod handling.
      return result == IterationStep.STOP;
    }

    ClassSet classSet = classHierarchy.getClassSet(base);
    assert(classSet != null, failedAt(base, "No class set for $base."));
    ClassHierarchyNode node = classSet.node;
    if (query == ClassQuery.EXACT) {
      return node.isExplicitlyInstantiated &&
          !_hasConcreteMatch(base, selector);
    } else if (query == ClassQuery.SUBCLASS) {
      return subclassesNeedNoSuchMethod(node);
    } else {
      if (subclassesNeedNoSuchMethod(node)) return true;
      for (ClassHierarchyNode subtypeNode in classSet.subtypeNodes) {
        if (subclassesNeedNoSuchMethod(subtypeNode)) return true;
      }
      return false;
    }
  }

  /// Returns an iterable over the common supertypes of the [classes].
  Iterable<ClassEntity> commonSupertypesOf(Iterable<ClassEntity> classes) {
    Iterator<ClassEntity> iterator = classes.iterator;
    if (!iterator.moveNext()) return const <ClassEntity>[];

    ClassEntity cls = iterator.current;
    OrderedTypeSet typeSet = elementMap.getOrderedTypeSet(cls);
    if (!iterator.moveNext()) return typeSet.types.map((type) => type.element);

    int depth = typeSet.maxDepth;
    Link<OrderedTypeSet> otherTypeSets = const Link<OrderedTypeSet>();
    do {
      ClassEntity otherClass = iterator.current;
      OrderedTypeSet otherTypeSet = elementMap.getOrderedTypeSet(otherClass);
      otherTypeSets = otherTypeSets.prepend(otherTypeSet);
      if (otherTypeSet.maxDepth < depth) {
        depth = otherTypeSet.maxDepth;
      }
    } while (iterator.moveNext());

    List<ClassEntity> commonSupertypes = <ClassEntity>[];
    OUTER:
    for (Link<InterfaceType> link = typeSet[depth];
        link.head.element != commonElements.objectClass;
        link = link.tail) {
      ClassEntity cls = link.head.element;
      for (Link<OrderedTypeSet> link = otherTypeSets;
          !link.isEmpty;
          link = link.tail) {
        if (link.head.asInstanceOf(cls, elementMap.getHierarchyDepth(cls)) ==
            null) {
          continue OUTER;
        }
      }
      commonSupertypes.add(cls);
    }
    commonSupertypes.add(commonElements.objectClass);
    return commonSupertypes;
  }

  /// Returns an iterable over the live mixin applications that mixin [cls].
  Iterable<ClassEntity> mixinUsesOf(ClassEntity cls) {
    if (_liveMixinUses == null) {
      _liveMixinUses = new Map<ClassEntity, List<ClassEntity>>();
      for (ClassEntity mixin in mixinUses.keys) {
        List<ClassEntity> uses = <ClassEntity>[];

        void addLiveUse(ClassEntity mixinApplication) {
          if (classHierarchy.isInstantiated(mixinApplication)) {
            uses.add(mixinApplication);
          } else if (_isNamedMixinApplication(mixinApplication)) {
            Set<ClassEntity> next = mixinUses[mixinApplication];
            if (next != null) {
              next.forEach(addLiveUse);
            }
          }
        }

        mixinUses[mixin].forEach(addLiveUse);
        if (uses.isNotEmpty) {
          _liveMixinUses[mixin] = uses;
        }
      }
    }
    Iterable<ClassEntity> uses = _liveMixinUses[cls];
    return uses != null ? uses : const <ClassEntity>[];
  }

  /// Returns `true` if any live class that mixes in [mixin] is also a subclass
  /// of [superclass].
  bool hasAnySubclassThatMixes(ClassEntity superclass, ClassEntity mixin) {
    return mixinUsesOf(mixin).any((ClassEntity each) {
      return classHierarchy.isSubclassOf(each, superclass);
    });
  }

  /// Returns `true` if [cls] or any superclass mixes in [mixin].
  bool isSubclassOfMixinUseOf(ClassEntity cls, ClassEntity mixin) {
    if (isUsedAsMixin(mixin)) {
      ClassEntity current = cls;
      while (current != null) {
        ClassEntity currentMixin = elementMap.getAppliedMixin(current);
        if (currentMixin == mixin) return true;
        current = elementEnvironment.getSuperClass(current);
      }
    }
    return false;
  }

  void _ensureFunctionSet() {
    if (_allFunctions == null) {
      // [FunctionSet] is created lazily because it is not used when we switch
      // from a frontend to a backend model before inference.
      _allFunctions = new FunctionSet(liveInstanceMembers);
    }
  }

  /// Returns `true` if [selector] on [receiver] can hit a `call` method on a
  /// subclass of `Closure`.
  ///
  /// Every implementation of `Closure` has a 'call' method with its own
  /// signature so it cannot be modelled by a [FunctionEntity]. Also,
  /// call-methods for tear-off are not part of the element model.
  bool includesClosureCall(Selector selector, AbstractValue receiver) {
    return selector.name == Identifiers.call &&
        (receiver == null ||
            // TODO(johnniwinther): Should this have been `intersects` instead?
            abstractValueDomain
                .contains(receiver, abstractValueDomain.functionType)
                .isPotentiallyTrue);
  }

  AbstractValue computeReceiverType(Selector selector, AbstractValue receiver) {
    _ensureFunctionSet();
    if (includesClosureCall(selector, receiver)) {
      return abstractValueDomain.dynamicType;
    }
    return _allFunctions.receiverType(selector, receiver, abstractValueDomain);
  }

  Iterable<MemberEntity> locateMembers(
      Selector selector, AbstractValue receiver) {
    _ensureFunctionSet();
    return _allFunctions.filter(selector, receiver, abstractValueDomain);
  }

  bool hasAnyUserDefinedGetter(Selector selector, AbstractValue receiver) {
    _ensureFunctionSet();
    return _allFunctions
        .filter(selector, receiver, abstractValueDomain)
        .any((each) => each.isGetter);
  }

  MemberEntity locateSingleMember(Selector selector, AbstractValue receiver) {
    if (includesClosureCall(selector, receiver)) {
      return null;
    }
    receiver ??= abstractValueDomain.dynamicType;
    return abstractValueDomain.locateSingleMember(receiver, selector);
  }

  bool fieldNeverChanges(MemberEntity element) {
    if (!element.isField) return false;
    if (nativeData.isNativeMember(element)) {
      // Some native fields are views of data that may be changed by operations.
      // E.g. node.firstChild depends on parentNode.removeBefore(n1, n2).
      // TODO(sra): Refine the effect classification so that native effects are
      // distinct from ordinary Dart effects.
      return false;
    }

    if (!element.isAssignable) {
      return true;
    }
    if (element.isInstanceMember) {
      return !assignedInstanceMembers.contains(element);
    }
    return false;
  }

  @override
  Sorter get sorter {
    return _sorter ??= new KernelSorter(elementMap);
  }

  @override
  AbstractValueDomain get abstractValueDomain {
    return _abstractValueDomain;
  }

  @override
  bool hasElementIn(ClassEntity cls, Name name, Entity element) {
    while (cls != null) {
      MemberEntity member = elementEnvironment
          .lookupLocalClassMember(cls, name.text, setter: name.isSetter);
      if (member != null &&
          !member.isAbstract &&
          (!name.isPrivate || member.library == name.library)) {
        return member == element;
      }
      cls = elementEnvironment.getSuperClass(cls);
    }
    return false;
  }

  /// Returns whether a [selector] call on an instance of [cls]
  /// will hit a method at runtime, and not go through [noSuchMethod].
  bool _hasConcreteMatch(ClassEntity cls, Selector selector,
      {ClassEntity stopAtSuperclass}) {
    assert(classHierarchy.isInstantiated(cls),
        failedAt(cls, '$cls has not been instantiated.'));
    MemberEntity element = elementEnvironment
        .lookupClassMember(cls, selector.name, setter: selector.isSetter);
    if (element == null) return false;

    if (element.isAbstract) {
      ClassEntity enclosingClass = element.enclosingClass;
      return _hasConcreteMatch(
          elementEnvironment.getSuperClass(enclosingClass), selector);
    }
    return selector.appliesUnnamed(element);
  }

  bool _isNamedMixinApplication(ClassEntity cls) {
    return elementEnvironment.isMixinApplication(cls) &&
        !elementEnvironment.isUnnamedMixinApplication(cls);
  }
}

class KernelSorter implements Sorter {
  final JsToElementMap elementMap;

  KernelSorter(this.elementMap);

  int _compareLibraries(LibraryEntity a, LibraryEntity b) {
    return utils.compareLibrariesUris(a.canonicalUri, b.canonicalUri);
  }

  int _compareSourceSpans(Entity entity1, SourceSpan sourceSpan1,
      Entity entity2, SourceSpan sourceSpan2) {
    int r = utils.compareSourceUris(sourceSpan1.uri, sourceSpan2.uri);
    if (r != 0) return r;
    return utils.compareEntities(
        entity1, sourceSpan1.begin, null, entity2, sourceSpan2.begin, null);
  }

  @override
  Iterable<LibraryEntity> sortLibraries(Iterable<LibraryEntity> libraries) {
    return libraries.toList()..sort(_compareLibraries);
  }

  @override
  Iterable<T> sortMembers<T extends MemberEntity>(Iterable<T> members) {
    return members.toList()..sort(compareMembersByLocation);
  }

  @override
  Iterable<ClassEntity> sortClasses(Iterable<ClassEntity> classes) {
    List<ClassEntity> regularClasses = <ClassEntity>[];
    List<ClassEntity> unnamedMixins = <ClassEntity>[];
    for (ClassEntity cls in classes) {
      if (elementMap.elementEnvironment.isUnnamedMixinApplication(cls)) {
        unnamedMixins.add(cls);
      } else {
        regularClasses.add(cls);
      }
    }
    List<ClassEntity> sorted = <ClassEntity>[];
    regularClasses.sort(compareClassesByLocation);
    sorted.addAll(regularClasses);
    unnamedMixins.sort((a, b) {
      int result = _compareLibraries(a.library, b.library);
      if (result != 0) return result;
      result = a.name.compareTo(b.name);
      assert(result != 0,
          failedAt(a, "Multiple mixins named ${a.name}: $a vs $b."));
      return result;
    });
    sorted.addAll(unnamedMixins);
    return sorted;
  }

  @override
  Iterable<TypedefEntity> sortTypedefs(Iterable<TypedefEntity> typedefs) {
    // TODO(redemption): Support this.
    assert(typedefs.isEmpty);
    return typedefs;
  }

  @override
  int compareLibrariesByLocation(LibraryEntity a, LibraryEntity b) {
    return _compareLibraries(a, b);
  }

  @override
  int compareClassesByLocation(ClassEntity a, ClassEntity b) {
    int r = _compareLibraries(a.library, b.library);
    if (r != 0) return r;
    ClassDefinition definition1 = elementMap.getClassDefinition(a);
    ClassDefinition definition2 = elementMap.getClassDefinition(b);
    return _compareSourceSpans(
        a, definition1.location, b, definition2.location);
  }

  @override
  int compareTypedefsByLocation(TypedefEntity a, TypedefEntity b) {
    // TODO(redemption): Support this.
    failedAt(a, 'KernelSorter.compareTypedefsByLocation unimplemented');
    return 0;
  }

  @override
  int compareMembersByLocation(MemberEntity a, MemberEntity b) {
    int r = _compareLibraries(a.library, b.library);
    if (r != 0) return r;
    MemberDefinition definition1 = elementMap.getMemberDefinition(a);
    MemberDefinition definition2 = elementMap.getMemberDefinition(b);
    return _compareSourceSpans(
        a, definition1.location, b, definition2.location);
  }
}

/// [LocalLookup] implementation used to deserialize [JsClosedWorld].
class LocalLookupImpl implements LocalLookup {
  final GlobalLocalsMap _globalLocalsMap;

  LocalLookupImpl(this._globalLocalsMap);

  @override
  Local getLocalByIndex(MemberEntity memberContext, int index) {
    KernelToLocalsMapImpl map = _globalLocalsMap.getLocalsMap(memberContext);
    return map.getLocalByIndex(index);
  }
}