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

library fasta.class_hierarchy_builder;

import 'package:kernel/ast.dart'
    show Library, Member, Name, Procedure, ProcedureKind;

import 'package:kernel/class_hierarchy.dart' show ClassHierarchy;

import '../messages.dart'
    show
        LocatedMessage,
        messageDeclaredMemberConflictsWithInheritedMember,
        messageDeclaredMemberConflictsWithInheritedMemberCause,
        messageInheritedMembersConflict,
        messageInheritedMembersConflictCause1,
        messageInheritedMembersConflictCause2,
        templateMissingImplementationCause,
        templateMissingImplementationNotAbstract;

import '../names.dart' show noSuchMethodName;

import '../scope.dart' show Scope;

import 'kernel_builder.dart'
    show
        Declaration,
        LibraryBuilder,
        KernelClassBuilder,
        KernelNamedTypeBuilder,
        KernelTypeBuilder;

int compareDeclarations(Declaration a, Declaration b) {
  return ClassHierarchy.compareMembers(a.target, b.target);
}

ProcedureKind memberKind(Member member) {
  return member is Procedure ? member.kind : null;
}

bool isNameVisibleIn(
    Name name, LibraryBuilder<KernelTypeBuilder, Library> library) {
  return !name.isPrivate || name.library == library.target;
}

class ClassHierarchyBuilder {
  final Map<KernelClassBuilder, ClassHierarchyNode> nodes =
      <KernelClassBuilder, ClassHierarchyNode>{};

  final KernelClassBuilder objectClass;

  bool hasNoSuchMethod = false;

  int abstractMemberCount = 0;

  ClassHierarchyBuilder(this.objectClass);

  Declaration handleOverride(KernelClassBuilder cls, Declaration member,
      Declaration superMember, MergeKind mergeKind) {
    if (member.next != null || superMember.next != null) {
      // Don't check overrides involving duplicated members.
      return member;
    }
    Member target = member.target;
    Member superTarget = superMember.target;
    if ((memberKind(target) ?? ProcedureKind.Getter) !=
        (memberKind(superTarget) ?? ProcedureKind.Getter)) {
      String name = member.fullNameForErrors;
      if (mergeKind == MergeKind.interfaces) {
        cls.addProblem(messageInheritedMembersConflict, cls.charOffset,
            cls.fullNameForErrors.length,
            context: <LocatedMessage>[
              messageInheritedMembersConflictCause1.withLocation(
                  member.fileUri, member.charOffset, name.length),
              messageInheritedMembersConflictCause2.withLocation(
                  superMember.fileUri, superMember.charOffset, name.length),
            ]);
      } else {
        cls.addProblem(messageDeclaredMemberConflictsWithInheritedMember,
            member.charOffset, name.length,
            context: <LocatedMessage>[
              messageDeclaredMemberConflictsWithInheritedMemberCause
                  .withLocation(
                      superMember.fileUri, superMember.charOffset, name.length)
            ]);
      }
    }
    if (target.name == noSuchMethodName && !target.isAbstract) {
      hasNoSuchMethod = true;
    }
    Declaration result = member;
    if (mergeKind == MergeKind.interfaces) {
      // TODO(ahe): Combine the signatures of member and superMember.
    } else if (target.isAbstract) {
      if (!superTarget.isAbstract) {
        // An abstract method doesn't override an implemention inherited from a
        // superclass.
        result = superMember;
      } else {
        abstractMemberCount++;
      }
    }
    return result;
  }

  void handleNewMember(Declaration member, MergeKind mergeKind) {
    Member target = member.target;
    if (mergeKind == MergeKind.superclass && target.isAbstract) {
      abstractMemberCount++;
    }
  }

  void handleInheritance(
      KernelClassBuilder cls, Declaration member, MergeKind mergeKind) {
    Member target = member.target;
    if (mergeKind == MergeKind.superclass && target.isAbstract) {
      if (isNameVisibleIn(target.name, cls.library)) {
        abstractMemberCount++;
      }
    }
    if (member.parent != objectClass &&
        target.name == noSuchMethodName &&
        !target.isAbstract) {
      hasNoSuchMethod = true;
    }
  }

  void add(KernelClassBuilder cls) {
    if (cls.isPatch) {
      // TODO(ahe): What about patch classes. Have we injected patched members
      // into the class-builder's scope?
      return;
    }
    ClassHierarchyNode supernode;
    if (objectClass != cls) {
      supernode = getNode(cls.supertype);
      if (supernode == null) {
        supernode = nodes[objectClass];
        if (supernode == null) {
          add(objectClass);
          supernode = nodes[objectClass];
        }
      }
      assert(supernode != null);
    }

    Scope scope = cls.scope;
    if (cls.isMixinApplication) {
      Declaration mixin = getDeclaration(cls.mixedInType);
      if (mixin is KernelClassBuilder) {
        scope = mixin.scope;
      }
    }
    List<Declaration> sortedLocals =
        new List<Declaration>.from(scope.local.values)
          ..sort(compareDeclarations);
    List<Declaration> sortedSetters =
        new List<Declaration>.from(scope.setters.values)
          ..sort(compareDeclarations);
    List<Declaration> allMembers;
    List<Declaration> allSetters;
    List<Declaration> interfaceMembers;
    List<Declaration> interfaceSetters;
    if (supernode == null) {
      // This should be Object.
      interfaceMembers = allMembers = sortedLocals;
      interfaceSetters = allSetters = sortedSetters;
    } else {
      allMembers = merge(
          cls, sortedLocals, supernode.classMembers, MergeKind.superclass);
      allSetters = merge(
          cls, sortedSetters, supernode.classSetters, MergeKind.superclass);
      List<KernelTypeBuilder> interfaces = cls.interfaces;
      if (interfaces != null) {
        MergeResult result = mergeInterfaces(cls, supernode, interfaces);
        interfaceMembers = result.mergedMembers;
        interfaceSetters = result.mergedSetters;
      } else {
        interfaceMembers = allMembers;
        interfaceSetters = allSetters;
      }
    }
    nodes[cls] = new ClassHierarchyNode(
        cls, scope, allMembers, allSetters, interfaceMembers, interfaceSetters);
    mergeAccessors(cls, allMembers, allSetters);

    if (abstractMemberCount != 0 && !cls.isAbstract) {
      if (!hasNoSuchMethod) {
        reportMissingMembers(cls, allMembers, allSetters);
      }
      installNsmHandlers(cls);
    }
    hasNoSuchMethod = false;
    abstractMemberCount = 0;
  }

  MergeResult mergeInterfaces(KernelClassBuilder cls,
      ClassHierarchyNode supernode, List<KernelTypeBuilder> interfaces) {
    List<List<Declaration>> memberLists =
        List<List<Declaration>>(interfaces.length + 1);
    List<List<Declaration>> setterLists =
        List<List<Declaration>>(interfaces.length + 1);
    memberLists[0] = supernode.interfaceMembers;
    setterLists[0] = supernode.interfaceSetters;
    for (int i = 0; i < interfaces.length; i++) {
      ClassHierarchyNode interfaceNode = getNode(interfaces[i]);
      if (interfaceNode == null) {
        memberLists[i + 1] = <Declaration>[];
        setterLists[i + 1] = <Declaration>[];
      } else {
        memberLists[i + 1] = interfaceNode.interfaceMembers;
        setterLists[i + 1] = interfaceNode.interfaceSetters;
      }
    }
    return new MergeResult(
        mergeLists(cls, memberLists), mergeLists(cls, setterLists));
  }

  List<Declaration> mergeLists(
      KernelClassBuilder cls, List<List<Declaration>> input) {
    // This is a k-way merge sort (where k is `input.length + 1`). We merge the
    // lists pairwise, which reduces the number of lists to merge by half on
    // each iteration. Consequently, we perform O(log k) merges.
    while (input.length > 1) {
      List<List<Declaration>> output = <List<Declaration>>[];
      for (int i = 0; i < input.length - 1; i += 2) {
        output.add(merge(cls, input[i], input[i + 1], MergeKind.interfaces));
      }
      if (input.length.isOdd) {
        output.add(input.last);
      }
      input = output;
    }
    return input.single;
  }

  /// Merge [and check] accessors. This entails removing setters corresponding
  /// to fields, and checking that setters don't override regular methods.
  void mergeAccessors(KernelClassBuilder cls, List<Declaration> allMembers,
      List<Declaration> allSetters) {
    List<Declaration> overriddenSetters;
    int i = 0;
    int j = 0;
    while (i < allMembers.length && j < allSetters.length) {
      Declaration member = allMembers[i];
      Declaration setter = allSetters[j];
      final int compare = compareDeclarations(member, setter);
      if (compare == 0) {
        if (member.isField) {
          // TODO(ahe): What happens if we have both a field and a setter
          // declared in the same class?
          if (!member.isFinal && !member.isConst) {
            // The field overrides the setter.
            (overriddenSetters ??= <Declaration>[]).add(setter);
            Member target = setter.target;
            if (target.isAbstract) {
              abstractMemberCount--;
            }
          }
        } else if (!member.isGetter) {
          String name = member.fullNameForErrors;
          cls.library.addProblem(
              messageDeclaredMemberConflictsWithInheritedMember,
              member.charOffset,
              name.length,
              member.fileUri,
              context: <LocatedMessage>[
                messageDeclaredMemberConflictsWithInheritedMemberCause
                    .withLocation(
                        setter.fileUri, setter.charOffset, name.length)
              ]);
        }
        i++;
        j++;
      } else if (compare < 0) {
        i++;
      } else {
        j++;
      }
    }
    // One of of the two lists is now exhausted. What remains in the other list
    // cannot be a conflict.

    if (overriddenSetters != null) {
      // Remove [overriddenSetters] from [allSetters] by copying [allSetters]
      // to itself.
      int i = 0;
      int j = 0;
      int storeIndex = 0;
      while (i < allSetters.length && j < overriddenSetters.length) {
        if (allSetters[i] == overriddenSetters[j]) {
          i++;
          j++;
        } else {
          allSetters[storeIndex++] = allSetters[i++];
        }
      }
      while (i < allSetters.length) {
        allSetters[storeIndex++] = allSetters[i++];
      }
      allSetters.length = storeIndex;
    }
  }

  void reportMissingMembers(KernelClassBuilder cls,
      List<Declaration> allMembers, List<Declaration> allSetters) {
    List<LocatedMessage> context = <LocatedMessage>[];
    List<String> missingNames = <String>[];
    for (int j = 0; j < 2; j++) {
      List<Declaration> members = j == 0 ? allMembers : allSetters;
      for (int i = 0; i < members.length; i++) {
        Declaration declaration = members[i];
        Member target = declaration.target;
        if (target.isAbstract && isNameVisibleIn(target.name, cls.library)) {
          String name = declaration.fullNameForErrors;
          String parentName = declaration.parent.fullNameForErrors;
          String displayName =
              declaration.isSetter ? "$parentName.$name=" : "$parentName.$name";
          missingNames.add(displayName);
          context.add(templateMissingImplementationCause
              .withArguments(displayName)
              .withLocation(
                  declaration.fileUri, declaration.charOffset, name.length));
        }
      }
    }
    cls.addProblem(
        templateMissingImplementationNotAbstract.withArguments(
            cls.fullNameForErrors, missingNames),
        cls.charOffset,
        cls.fullNameForErrors.length,
        context: context);
  }

  void installNsmHandlers(KernelClassBuilder cls) {
    // TOOD(ahe): Implement this.
  }

  ClassHierarchyNode getNode(KernelTypeBuilder type) {
    if (type is KernelNamedTypeBuilder) {
      Declaration declaration = type.declaration;
      if (declaration is KernelClassBuilder) {
        ClassHierarchyNode node = nodes[declaration];
        if (node == null && declaration is KernelClassBuilder) {
          add(declaration);
          node = nodes[declaration];
        }
        return node;
      }
    }
    return null;
  }

  Declaration getDeclaration(KernelTypeBuilder type) {
    return type is KernelNamedTypeBuilder ? type.declaration : null;
  }

  List<Declaration> merge(
      KernelClassBuilder cls,
      List<Declaration> localMembers,
      List<Declaration> superMembers,
      MergeKind mergeKind) {
    final List<Declaration> mergedMembers = new List<Declaration>.filled(
        localMembers.length + superMembers.length, null,
        growable: true);

    int mergedMemberCount = 0;

    int i = 0;
    int j = 0;
    while (i < localMembers.length && j < superMembers.length) {
      final Declaration localMember = localMembers[i];
      final Declaration superMember = superMembers[j];
      final int compare = compareDeclarations(localMember, superMember);
      if (compare == 0) {
        mergedMembers[mergedMemberCount++] =
            handleOverride(cls, localMember, superMember, mergeKind);
        i++;
        j++;
      } else if (compare < 0) {
        handleNewMember(localMember, mergeKind);
        mergedMembers[mergedMemberCount++] = localMember;
        i++;
      } else {
        handleInheritance(cls, superMember, mergeKind);
        mergedMembers[mergedMemberCount++] = superMember;
        j++;
      }
    }
    while (i < localMembers.length) {
      final Declaration localMember = localMembers[i];
      handleNewMember(localMember, mergeKind);
      mergedMembers[mergedMemberCount++] = localMember;
      i++;
    }
    while (j < superMembers.length) {
      final Declaration superMember = superMembers[j];
      handleInheritance(cls, superMember, mergeKind);
      mergedMembers[mergedMemberCount++] = superMember;
      j++;
    }
    return mergedMembers..length = mergedMemberCount;
  }
}

class ClassHierarchyNode {
  /// The class corresponding to this hierarchy node.
  final KernelClassBuilder cls;

  /// The local members of [cls]. For regular classes, this is simply
  /// `cls.scope`, but for mixin-applications this is the mixed-in type's
  /// scope. The members are sorted in order of declaration.
  // TODO(ahe): Do we need to copy the scope from the mixed-in type to remove
  // static members?
  final Scope localMembers;

  /// All the members of this class including [classMembers] of its
  /// superclasses. The members are sorted by [compareDeclarations].
  final List<Declaration> classMembers;

  /// Similar to [classMembers] but for setters.
  final List<Declaration> classSetters;

  /// All the interface members of this class including [interfaceMembers] of
  /// its supertypes. The members are sorted by [compareDeclarations].
  ///
  /// In addition to the members of [classMembers] this also contains members
  /// from interfaces.
  final List<Declaration> interfaceMembers;

  /// Similar to [interfaceMembers] but for setters.
  final List<Declaration> interfaceSetters;

  ClassHierarchyNode(this.cls, this.localMembers, this.classMembers,
      this.classSetters, this.interfaceMembers, this.interfaceSetters);
}

class MergeResult {
  final List<Declaration> mergedMembers;

  final List<Declaration> mergedSetters;

  MergeResult(this.mergedMembers, this.mergedSetters);
}

enum MergeKind {
  /// Merging superclass members with the current class.
  superclass,

  /// Merging two interfaces.
  interfaces,

  /// Merging class members with interface members.
  supertypes,
}