// Copyright (c) 2014, 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 analyzer2dart.treeShaker;

import 'dart:collection';

import 'package:analyzer/analyzer.dart';
import 'package:analyzer/src/generated/element.dart';
import 'package:analyzer/src/generated/source.dart';
import 'package:analyzer/src/generated/resolver.dart';
import 'package:compiler/src/universe/universe.dart';

import 'closed_world.dart';
import 'util.dart';
import 'semantic_visitor.dart';
import 'identifier_semantics.dart';

/**
 * The result of performing local reachability analysis on a method.
 */
class MethodAnalysis {
  /**
   * The AST for the method.
   */
  final Declaration declaration;

  /**
   * The functions statically called by the method.
   */
  final List<ExecutableElement> calls = <ExecutableElement>[];

  /**
   * The fields and top-level variables statically accessed by the method.
   */
  // TODO(johnniwinther): Should we split this into reads and writes?
  final List<PropertyInducingElement> accesses = <PropertyInducingElement>[];

  /**
   * The selectors used by the method to perform dynamic invocation.
   */
  final List<Selector> invokes = <Selector>[];

  /**
   * The classes that are instantiated by the method.
   */
  // TODO(johnniwinther,paulberry): Register instantiated types.
  // TODO(johnniwinther,paulberry): Register checked types from is/as checks,
  // catch clauses and (checked) type annotations.
  final List<ClassElement> instantiates = <ClassElement>[];

  MethodAnalysis(this.declaration);
}

/**
 * The result of performing local reachability analysis on a class.
 *
 * TODO(paulberry): Do we need to do any other analysis of classes?  (For
 * example, detect annotations that are relevant to mirrors, detect that a
 * class might be used for custom HTML elements, or collect inherited and
 * mixed-in classes).
 */
class ClassAnalysis {
  /**
   * The AST for the class.
   */
  final ClassDeclaration declaration;

  ClassAnalysis(this.declaration);
}

/**
 * This class is responsible for performing local analysis of the source code
 * to provide the information needed to do tree shaking.
 */
class LocalReachabilityComputer {
  /**
   * Perform local reachability analysis of [method].
   */
  MethodAnalysis analyzeMethod(ExecutableElement method) {
    Declaration declaration = method.node;
    MethodAnalysis analysis = new MethodAnalysis(declaration);
    if (declaration != null) {
      declaration.accept(new TreeShakingVisitor(analysis));
    } else if (method is ConstructorElement) {
      // This constructor has no associated declaration in the AST.  Either it
      // is a default constructor for an ordinary class, or it's a synthetic
      // constructor associated with a mixin.  For now we assume it's a default
      // constructor, in which case all we need to do is record the class as
      // being instantiated by this method.  TODO(paulberry): handle the
      // mixin case.
      ClassElement instantiatedClass = method.enclosingElement;
      analysis.instantiates.add(instantiatedClass);
      if (instantiatedClass.supertype != null) {
        ClassElement superClass = instantiatedClass.supertype.element;
        ConstructorElement superConstructor = superClass.unnamedConstructor;
        if (superConstructor != null) {
          // TODO(johnniwinther): Register instantiated type and selector.
          analysis.calls.add(superConstructor);
        }
      }
    } else {
      // This is an executable element with no associated declaration in the
      // AST, and it's not a constructor.  TODO(paulberry): can this ever
      // happen?
      throw new UnimplementedError();
    }
    return analysis;
  }

  /**
   * Perform local reachability analysis of [classElement].
   */
  ClassAnalysis analyzeClass(ClassElement classElement) {
    return new ClassAnalysis(classElement.node);
  }

  /**
   * Determine which members of [classElement] are matched by the given
   * [selector].
   *
   * [methods] is populated with all the class methods which are matched by the
   * selector, [accessors] with all the getters and setters which are matched
   * by the selector, and [fields] with all the fields which are matched by the
   * selector.
   */
  void getMatchingClassMembers(ClassElement classElement, Selector selector,
      List<MethodElement> methods, List<PropertyAccessorElement> accessors,
      List<PropertyInducingElement> fields) {
    // TODO(paulberry): should we walk through superclasses and mixins as well
    // here?  Or would it be better to make [TreeShaker] responsible for those
    // relationships (since they are non-local)?  Consider making use of
    // InheritanceManager to do this.
    for (MethodElement method in classElement.methods) {
      // TODO(paulberry): account for arity and named arguments when matching
      // the selector against the method.
      if (selector.name == method.name) {
        methods.add(method);
      }
    }
    if (selector.kind == SelectorKind.GETTER) {
      for (PropertyAccessorElement accessor in classElement.accessors) {
        if (accessor.isGetter && selector.name == accessor.name) {
          if (accessor.isSynthetic) {
            // This accessor is implied by the corresponding field declaration.
            fields.add(accessor.variable);
          } else {
            accessors.add(accessor);
          }
        }
      }
    } else if (selector.kind == SelectorKind.SETTER) {
      // accessor.name uses the convention that setter names end in '='.
      String selectorNameWithEquals = '${selector.name}=';
      for (PropertyAccessorElement accessor in classElement.accessors) {
        if (accessor.isSetter && selectorNameWithEquals == accessor.name) {
          if (accessor.isSynthetic) {
            // This accessor is implied by the corresponding field declaration.
            // TODO(paulberry): should we distinguish reads and writes?
            fields.add(accessor.variable);
          } else {
            accessors.add(accessor);
          }
        }
      }
    }
  }
}

/**
 * This class is responsible for driving the tree shaking process, and
 * and performing the global inferences necessary to determine which methods
 * in the source program are reachable.  It makes use of
 * [LocalReachabilityComputer] to do local analysis of individual classes and
 * methods.
 */
class TreeShaker {
  List<Element> _queue = <Element>[];
  Set<Element> _alreadyEnqueued = new HashSet<Element>();
  ClosedWorld _world;
  Set<Selector> _selectors = new HashSet<Selector>();
  final LocalReachabilityComputer _localComputer =
      new LocalReachabilityComputer();

  TreeShaker(TypeProvider typeProvider, FunctionElement mainFunction)
      : _world = new ClosedWorld(typeProvider, mainFunction);

  void _addElement(Element element) {
    if (_alreadyEnqueued.add(element)) {
      _queue.add(element);
    }
  }

  void _addSelector(Selector selector) {
    if (_selectors.add(selector)) {
      // New selector, so match it against all class methods.
      _world.instantiatedClasses.forEach((ClassElement element, AstNode node) {
        _matchClassToSelector(element, selector);
      });
    }
  }

  void _matchClassToSelector(ClassElement classElement, Selector selector) {
    List<MethodElement> methods = <MethodElement>[];
    List<PropertyAccessorElement> accessors = <PropertyAccessorElement>[];
    List<PropertyInducingElement> fields = <PropertyInducingElement>[];
    _localComputer.getMatchingClassMembers(
        classElement,
        selector,
        methods,
        accessors,
        fields);
    methods.forEach(_addElement);
    accessors.forEach(_addElement);
    fields.forEach(_addElement);
  }

  ClosedWorld shake() {
    _addElement(_world.mainFunction);
    while (_queue.isNotEmpty) {
      Element element = _queue.removeLast();
      if (element is ExecutableElement) {
        MethodAnalysis analysis = _localComputer.analyzeMethod(element);
        _world.executableElements[element] = analysis.declaration;
        analysis.calls.forEach(_addElement);
        analysis.invokes.forEach(_addSelector);
        analysis.instantiates.forEach(_addElement);
        analysis.accesses.forEach(_addElement);
      } else if (element is ClassElement) {
        ClassAnalysis analysis = _localComputer.analyzeClass(element);
        _world.instantiatedClasses[element] = analysis.declaration;
        for (Selector selector in _selectors) {
          _matchClassToSelector(element, selector);
        }
      } else if (element is FieldElement) {
        VariableDeclaration declaration = element.node;
        _world.fields[element] = declaration;
      } else if (element is TopLevelVariableElement) {
        VariableDeclaration declaration = element.node;
        _world.variables[element] = declaration;
      } else {
        throw new Exception(
            'Unexpected element type while tree shaking: '
                '$element (${element.runtimeType})');
      }
    }
    return _world;
  }
}

class TreeShakingVisitor extends SemanticVisitor {
  final MethodAnalysis analysis;

  TreeShakingVisitor(this.analysis);

  Source get currentSource => analysis.declaration.element.source;

  @override
  void visitInstanceCreationExpression(InstanceCreationExpression node) {
    ConstructorElement staticElement = node.staticElement;
    if (staticElement != null) {
      analysis.calls.add(staticElement);
    } else {
      // TODO(paulberry): deal with this situation.  This can happen, for
      // example, in the case "main() => new Unresolved();" (which is a
      // warning, not an error).
    }
    super.visitInstanceCreationExpression(node);
  }

  @override
  void visitDynamicInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    analysis.invokes.add(createSelectorFromMethodInvocation(
        node.argumentList, node.methodName.name));
  }

  @override
  void visitLocalFunctionInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitLocalVariableInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitParameterInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitStaticFieldInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    // Invocation of a static field.
    analysis.accesses.add(semantics.element);
    analysis.invokes.add(createSelectorFromMethodInvocation(
        node.argumentList, 'call'));
  }

  @override
  void visitStaticMethodInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    analysis.calls.add(semantics.element);
  }

  @override
  void visitStaticPropertyInvocation(MethodInvocation node,
      AccessSemantics semantics) {
    // Invocation of a property.  TODO(paulberry): handle this.
    super.visitStaticPropertyInvocation(node, semantics);
  }

  void handleDynamicAccess(AccessSemantics semantics) {
    if (semantics.isRead) {
      analysis.invokes.add(
          new Selector.getter(semantics.identifier.name, null));
    }
    if (semantics.isWrite) {
      // Selector.setter constructor uses the convention that setter names
      // don't end in '='.
      analysis.invokes.add(
          new Selector.setter(semantics.identifier.name, null));
    }
  }

  @override
  void visitDynamicAccess(AstNode node, AccessSemantics semantics) {
    handleDynamicAccess(semantics);
  }

  @override
  void visitLocalFunctionAccess(AstNode node, AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitLocalVariableAccess(AstNode node, AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitParameterAccess(AstNode node, AccessSemantics semantics) {
    // Locals don't need to be tree shaken.
  }

  @override
  void visitStaticFieldAccess(AstNode node, AccessSemantics semantics) {
    analysis.accesses.add(semantics.element);
  }

  @override
  void visitStaticMethodAccess(AstNode node, AccessSemantics semantics) {
    // Method tear-off.  TODO(paulberry): implement.
    super.visitStaticMethodAccess(node, semantics);
  }

  @override
  void visitStaticPropertyAccess(AstNode node, AccessSemantics semantics) {
    // TODO(paulberry): implement.
    super.visitStaticPropertyAccess(node, semantics);
  }

  @override
  void visitConstructorDeclaration(ConstructorDeclaration node) {
    // TODO(paulberry): handle parameter list.
    node.initializers.accept(this);
    node.body.accept(this);
    if (node.factoryKeyword == null) {
      // This is a generative constructor.  Figure out if it is redirecting.
      // If it isn't, then the constructor instantiates the class so we need to
      // add the class to analysis.instantiates.  (If it is redirecting, then
      // we don't need to, because the redirected-to constructor will take care
      // of that).
      if (node.initializers.length != 1 || node.initializers[0] is! RedirectingConstructorInvocation) {
        ClassElement classElement = node.element.enclosingElement;
        analysis.instantiates.add(node.element.enclosingElement);
        if (!node.initializers.any((i) => i is SuperConstructorInvocation)) {
          if (classElement.supertype != null) {
            ClassElement superClass = classElement.supertype.element;
            ConstructorElement superConstructor = superClass.unnamedConstructor;
            if (superConstructor != null) {
              // TODO(johnniwinther): Register instantiated type and selector.
              analysis.calls.add(superConstructor);
            }
          }
        }
      }
    } else if (node.redirectedConstructor != null) {
      if (node.redirectedConstructor.staticElement == null) {
        // Factory constructor redirects to a non-existent constructor.
        // TODO(paulberry): handle this.
        throw new UnimplementedError();
      } else {
        analysis.calls.add(node.redirectedConstructor.staticElement);
      }
    }
  }

  @override
  void
      visitRedirectingConstructorInvocation(RedirectingConstructorInvocation node) {
    // Note: we don't have to worry about node.staticElement being
    // null, because that would have been detected by the analyzer and
    // reported as a compile time error.
    analysis.calls.add(node.staticElement);
  }

  @override
  void handleAssignmentExpression(AssignmentExpression node) {
    // Don't special-case assignment expressions.
  }
}