// Copyright (c) 2017, 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 'dart:collection';

import 'package:collection/collection.dart';
import 'package:kernel/core_types.dart';
import 'package:kernel/kernel.dart' hide Pattern;

import 'constants.dart';

Never throwUnsupportedInvalidType(InvalidType type) => throw UnsupportedError(
    'Unsupported invalid type $type (${type.runtimeType}).');

Never throwUnsupportedAuxiliaryType(AuxiliaryType type) =>
    throw UnsupportedError(
        'Unsupported auxiliary type $type (${type.runtimeType}).');

Constructor? unnamedConstructor(Class c) =>
    c.constructors.firstWhereOrNull((c) => c.name.text == '');

/// Returns the enclosing library for reference [node].
Library getLibrary(NamedNode node) {
  for (TreeNode? n = node; n != null; n = n.parent) {
    if (n is Library) return n;
  }
  throw UnsupportedError('Could not find a containing library for $node');
}

final Pattern _syntheticTypeCharacters = RegExp('[&^#.|]');

String escapeIdentifier(String identifier) {
  // Remove the special characters used to encode mixin application class names
  // and extension method / parameter names which are legal in Kernel, but not
  // in JavaScript.
  //
  // Note, there is an implicit assumption here that we won't have
  // collisions since everything is mapped to \$.  That may work out fine given
  // how these are synthesized, but may need to revisit.
  return identifier.replaceAll(_syntheticTypeCharacters, r'$');
}

/// Returns the escaped name for class [node].
///
/// The caller of this function has to make sure that this name is unique in
/// the current scope.
String getLocalClassName(Class node) => escapeIdentifier(node.name);

/// Returns the escaped name for the type parameter [node].
String getTypeParameterName(
    /* TypeParameter | StructuralParameter */ Object node) {
  assert(node is TypeParameter || node is StructuralParameter);
  if (node is TypeParameter) {
    return escapeIdentifier(node.name!);
  } else {
    node as StructuralParameter;
    return escapeIdentifier(node.name!);
  }
}

String getTopLevelName(NamedNode n) {
  if (n is Procedure) return n.name.text;
  if (n is Class) return n.name;
  if (n is Typedef) return n.name;
  if (n is Field) return n.name.text;
  return n.reference.canonicalName!.name;
}

/// Given an annotated [node] and a [test] function, returns the first matching
/// constant valued annotation.
///
/// For example if we had the ClassDeclaration node for `FontElement`:
///
///    @js.JS('HTMLFontElement')
///    @deprecated
///    class FontElement { ... }
///
/// We could match `@deprecated` with a test function like:
///
///    (v) => v.type.name == 'Deprecated' && v.type.element.library.isDartCore
///
Expression? findAnnotation(TreeNode node, bool Function(Expression) test) {
  List<Expression> annotations;
  if (node is Class) {
    annotations = node.annotations;
  } else if (node is Typedef) {
    annotations = node.annotations;
  } else if (node is Procedure) {
    annotations = node.annotations;
  } else if (node is Member) {
    annotations = node.annotations;
  } else if (node is Library) {
    annotations = node.annotations;
  } else {
    return null;
  }
  return annotations.firstWhereOrNull(test);
}

/// Returns true if [value] represents an annotation for class [className] in
/// "dart:" library [libraryName].
bool isBuiltinAnnotation(
    Expression value, String libraryName, String className) {
  var c = getAnnotationClass(value);
  if (c != null && c.name == className) {
    var uri = c.enclosingLibrary.importUri;
    return uri.isScheme('dart') && uri.path == libraryName;
  }
  return false;
}

/// Gets the class of the instance referred to by metadata annotation [node].
///
/// For example:
///
/// - `@JS()` would return the "JS" class in "dart:_js_annotations".
/// - `@anonymous` would return the "_Anonymous" class in
/// "dart:_js_annotations".
///
/// This function works regardless of whether the CFE is evaluating constants,
/// or whether the constant is a field reference (such as "anonymous" above).
Class? getAnnotationClass(Expression node) {
  if (node is ConstantExpression) {
    var constant = node.constant;
    if (constant is InstanceConstant) return constant.classNode;
  } else if (node is ConstructorInvocation) {
    return node.target.enclosingClass;
  } else if (node is StaticGet) {
    var type = node.target.getterType;
    if (type is InterfaceType) return type.classNode;
  }
  return null;
}

/// Returns true if [name] is an operator method that is available on primitive
/// types (`int`, `double`, `num`, `String`, `bool`).
///
/// This does not include logical operators that cannot be user-defined
/// (`!`, `&&` and `||`).
bool isOperatorMethodName(String name) {
  switch (name) {
    case '==':
    case '~':
    case '^':
    case '|':
    case '&':
    case '>>':
    case '<<':
    case '>>>':
    case '+':
    case 'unary-':
    case '-':
    case '*':
    case '/':
    case '~/':
    case '>':
    case '<':
    case '>=':
    case '<=':
    case '%':
      return true;
  }
  return false;
}

bool isFromEnvironmentInvocation(CoreTypes coreTypes, StaticInvocation node) {
  var target = node.target;
  return node.isConst &&
      target.name.text == 'fromEnvironment' &&
      target.enclosingLibrary == coreTypes.coreLibrary;
}

List<Class> getSuperclasses(Class? c) {
  var result = <Class>[];
  var visited = HashSet<Class>();
  while (c != null && visited.add(c)) {
    for (var m = c.mixedInClass; m != null; m = m.mixedInClass) {
      result.add(m);
    }
    var superclass = c.superclass;
    if (superclass == null) break;
    result.add(superclass);
    c = superclass;
  }
  return result;
}

List<Class> getImmediateSuperclasses(Class c) {
  var result = <Class>[];
  var m = c.mixedInClass;
  if (m != null) result.add(m);
  var s = c.superclass;
  if (s != null) result.add(s);
  return result;
}

Expression? getInvocationReceiver(InvocationExpression node) {
  if (node is InstanceInvocation) {
    return node.receiver;
  } else if (node is DynamicInvocation) {
    return node.receiver;
  } else if (node is FunctionInvocation) {
    return node.receiver;
  } else if (node is LocalFunctionInvocation) {
    return VariableGet(node.variable);
  }
  return null;
}

bool isInlineJS(Member e) =>
    e is Procedure && _isProcedureFromForeignHelper('JS', e);

/// Returns `true` if [p] is the procedure named [name] from the
/// 'dart:_foreign_helper' library.
bool _isProcedureFromForeignHelper(String name, Procedure p) =>
    p.name.text == name &&
    p.enclosingLibrary.importUri.toString() == 'dart:_foreign_helper';

/// Whether the parameter [p] is covariant (either explicitly `covariant` or
/// implicitly due to generics) and needs a check for soundness.
bool isCovariantParameter(VariableDeclaration p) {
  return p.isCovariantByDeclaration || p.isCovariantByClass;
}

/// Whether the field [p] is covariant (either explicitly `covariant` or
/// implicitly due to generics) and needs a check for soundness.
bool isCovariantField(Field f) {
  return f.isCovariantByDeclaration || f.isCovariantByClass;
}

/// Returns true iff this factory constructor just throws [UnsupportedError]/
///
/// `dart:html` has many of these.
bool isUnsupportedFactoryConstructor(Procedure node) {
  if (node.name.isPrivate && node.enclosingLibrary.importUri.isScheme('dart')) {
    var body = node.function.body;
    if (body is Block) {
      var statements = body.statements;
      if (statements.length == 1) {
        var statement = statements[0];
        if (statement is ExpressionStatement) {
          var expr = statement.expression;
          if (expr is Throw) {
            var error = expr.expression;

            // HTML adds a lot of private constructors that are unreachable.
            // Skip these.
            return isBuiltinAnnotation(error, 'core', 'UnsupportedError');
          }
        }
      }
    }
  }
  return false;
}

/// Gets the real supertype of [c] and the list of [mixins] in reverse
/// application order (mixins will appear before ones they override).
///
/// This is used to ignore synthetic mixin application classes.
///
// TODO(jmesserly): consider replacing this with Kernel's mixin unrolling
Class getSuperclassAndMixins(Class c, List<Class> mixins) {
  assert(mixins.isEmpty);
  assert(c.superclass != null);

  var mixedInClass = c.mixedInClass;
  if (mixedInClass != null) mixins.add(mixedInClass);

  var sc = c.superclass!;
  for (; sc.isAnonymousMixin; sc = sc.superclass!) {
    mixedInClass = sc.mixedInClass;
    if (mixedInClass != null) mixins.add(sc.mixedInClass!);
  }
  return sc;
}

/// Returns true if a switch statement contains any continues with a label.
bool hasLabeledContinue(SwitchStatement node) {
  var visitor = LabelContinueFinder();
  node.accept(visitor);
  return visitor.found;
}

class LabelContinueFinder extends RecursiveVisitor {
  var found = false;

  void visit(Statement? s) {
    if (!found && s != null) s.accept(this);
  }

  @override
  void visitContinueSwitchStatement(ContinueSwitchStatement node) =>
      found = true;
}

/// Returns `true` if any of [n]s children are a [FunctionExpression] node.
bool containsFunctionExpression(Node n) {
  var visitor = _FunctionExpressionFinder.instance;
  visitor.found = false;
  n.accept(visitor);
  return visitor.found;
}

class _FunctionExpressionFinder extends RecursiveVisitor {
  var found = false;

  static final instance = _FunctionExpressionFinder();

  @override
  void visitFunctionExpression(FunctionExpression node) => found = true;
}

/// Whether [member] is declared native, as in:
///
///    void foo() native;
///
/// This syntax is only allowed in sdk libraries and native tests.
bool isNative(Member member) =>
    // The CFE represents `native` members with the `external` bit and with an
    // internal @ExternalName annotation as a marker.
    member.isExternal && member.annotations.any(_isNativeMarkerAnnotation);

bool _isNativeMarkerAnnotation(Expression annotation) {
  if (annotation is ConstantExpression) {
    var constant = annotation.constant;
    if (constant is InstanceConstant &&
        constant.classNode.name == 'ExternalName' &&
        _isDartInternal(constant.classNode.enclosingLibrary.importUri)) {
      return true;
    }
  }
  return false;
}

bool _isDartInternal(Uri uri) =>
    uri.isScheme('dart') && uri.path == '_internal';

/// Collects all `TypeParameter`s from the `TypeParameterType`s present in the
/// visited `DartType`.
class TypeParameterFinder extends RecursiveVisitor {
  final _found = <TypeParameter>{};
  static TypeParameterFinder? _instance;

  TypeParameterFinder._();
  factory TypeParameterFinder.instance() {
    if (_instance != null) return _instance!;
    return TypeParameterFinder._();
  }

  Set<TypeParameter> find(DartType type) {
    _found.clear();
    type.accept(this);
    return _found;
  }

  @override
  void visitTypeParameterType(TypeParameterType node) =>
      _found.add(node.parameter);
}

/// Collects [InterfaceType] nodes that appear in in a DartType.
class InterfaceTypeExtractor extends RecursiveVisitor {
  final Set<InterfaceType> _found = {};

  @override
  void visitInterfaceType(InterfaceType node) {
    _found.add(node);
    node.visitChildren(this);
  }

  /// Returns all [InterfaceType]s that appear in [type].
  Iterable<InterfaceType> extract(DartType type) {
    type.accept(this);
    return _found;
  }
}

/// Replaces [VariableGet] nodes with a different expression defined by a
/// replacement map.
class VariableGetReplacer extends Transformer {
  final Map<VariableDeclaration, Expression> _replacements;

  VariableGetReplacer(this._replacements);

  @override
  TreeNode visitVariableGet(VariableGet node) {
    var replacement = _replacements[node.variable];
    return replacement ?? node;
  }
}

/// Tests a [StaticInvocation] node to determine if it would be safe to inline.
///
/// Each static invocation should be inspected individually as this class only
/// inspects the body of a given invocation target, and does not recurse
/// transitively into the bodies of other invocations it finds.
///
/// The determination of what is safe to inline is specifically targeting simple
/// methods in the dart:_rti library and has not been validated to use as an
/// inliner for static methods from any other libraries. Instead of inlining by
/// introducing let variables that preserve the evaluation order of the call,
/// only code where it is safe to replace the argument of the call at the
/// place where it used is considered suitable.
///
/// The body of the target method may only contain simple expressions known to
/// have no side-effects like null, bool or string literals, constants, enum
/// values, and variable accesses. Additionally some static invocations from the
/// runtime libraries are permitted in the body when they have been manually
/// inspected for side effects and annotated as safe with
/// `@pragma('ddc:trust-inline`). After the last method argument has been used,
/// this restriction is weakened to allow any static invocations to appear.
class BasicInlineTester extends TreeVisitorDefault<bool> {
  /// The constants used to access constant evaluation for annotations.
  final DevCompilerConstants _constants;

  /// The order that the arguments are expected to used in the body of the
  /// function for it to be considered safe for inlining.
  ///
  /// This is essential to preserve the execution order of the expressions
  /// passed as arguments.
  List<VariableDeclaration>? _expectedArgumentOrder;

  /// The position in [_expectedArgumentOrder] to begin looking for the next
  /// used argument.
  int _nextArgIndex = 0;

  /// Returns `true` if uses of all the expected arguments have already been
  /// seen by the visitor.
  bool get _allArgumentsUsed => _nextArgIndex >= _expectedArgumentOrder!.length;

  BasicInlineTester(this._constants);

  /// Returns `true` when [possibleInline] is considered simple enough to
  /// be safe to inline.
  ///
  /// The considerations for inlining are designed specifically to target select
  /// invocations in the dart:_rti library.
  bool canInline(FunctionNode possibleInline) {
    if (possibleInline.namedParameters.isNotEmpty ||
        possibleInline.typeParameters.isNotEmpty ||
        possibleInline.positionalParameters.length !=
            possibleInline.requiredParameterCount) {
      // Only consider functions with required positional arguments.
      return false;
    }
    final body = possibleInline.body;
    // No code available here to inline.
    if (body == null) return false;

    _expectedArgumentOrder = possibleInline.positionalParameters;
    _nextArgIndex = 0;
    // Important to note that the static invocation being considered for inline
    // is not visited. Instead the body of the target function being invoked is
    // visited to determine if inlining is feasible. Any other static
    // invocations appearing within that body *will* be visited.
    final result = body.accept(this);
    // Avoid retaining any of the arguments after returning.
    _expectedArgumentOrder = null;
    return result;
  }

  /// Returns `true` when [node] is annotated with
  /// `@pragma('ddc:trust-inline`)`.
  bool _hasTrustInlinePragma(NamedNode node) {
    var annotation = findAnnotation(node, (e) {
      if (!isBuiltinAnnotation(e, 'core', 'pragma')) return false;
      var name = _constants.getFieldValueFromAnnotation(e, 'name') as String?;
      return name == 'ddc:trust-inline';
    });
    return annotation != null;
  }

  @override
  bool defaultTreeNode(Node _) => false;

  @override
  bool visitReturnStatement(ReturnStatement node) {
    var returnExpression = node.expression;
    return returnExpression == null ? false : returnExpression.accept(this);
  }

  @override
  bool visitBlock(Block node) {
    if (node.statements.length != 1) return false;
    return node.statements.single.accept(this);
  }

  @override
  bool visitStaticInvocation(StaticInvocation node) {
    // Reaching this visitor means that a static invocation appears in the body
    // of the function being evaluated for inlining.
    var positionalArgs = node.arguments.positional;
    if (isInlineJS(node.target)) {
      // Ensure JS expressions do not span multiple statements. Since these are
      // inlined elsewhere we don't want to accidentally combine multiple
      // Javascript statements into a position where they don't belong. Instead
      // of inspecting if it is valid, just reject any source templates that
      // contain ';' characters.
      var codeLiteral = positionalArgs[1];
      String? code;
      if (codeLiteral is StringLiteral) {
        code = codeLiteral.value;
      } else if (codeLiteral is ConstantExpression) {
        var constant = codeLiteral.constant;
        if (constant is StringConstant) {
          code = constant.value;
        }
      }
      if (code == null || code.contains(';')) return false;
    }
    // Inspect the arguments.
    for (var argument in positionalArgs) {
      if (!argument.accept(this)) return false;
    }
    // While all of the uses of the arguments are still being discovered,
    // only allow additional static invocations explicitly annotated as
    // trusted. This prevents inlining a static invocation that could
    // change the evaluation order of the expressions passed as arguments.
    // Example:
    // ```
    // echo(s) {
    //   print(s);
    //   return s;
    // }
    //
    // dangerous(arg1, arg2) {
    //   return fn(arg1, echo('third'), arg2);
    // }
    // ```
    // Calls to `dangerous()` should not be inlined without let variables
    // because the expression evaluation order would be disrupted:
    // ```
    // dangerous(echo('first'), echo('second'));
    //    |   |
    //    V   V
    // fn(echo('first'), echo('third'), echo('second')) // INVALID!
    return _allArgumentsUsed || _hasTrustInlinePragma(node.target);
  }

  @override
  bool visitBoolLiteral(BoolLiteral _) => true;

  @override
  bool visitNullLiteral(NullLiteral _) => true;

  @override
  bool visitStringLiteral(StringLiteral _) => true;

  @override
  bool visitConstantExpression(ConstantExpression _) => true;

  @override
  bool visitVariableGet(VariableGet node) {
    // The variable is an argument of the function to be inlined. Verify it
    // appears in an order consistent with the order the arguments appeared
    // in the call.
    final location =
        _expectedArgumentOrder!.indexOf(node.variable, _nextArgIndex);
    // Either the variable isn't one of the expected arguments at all, or it is
    // appearing out of the expected order.
    if (location == -1) return false;
    // Advance the start of the expected range past the variable just found to
    // ensure the variable can only be used once.
    _nextArgIndex = location + 1;
    return true;
  }

  @override
  bool visitField(Field node) => node.isEnumElement;

  @override
  bool visitStaticGet(StaticGet node) {
    return node.target.accept(this);
  }
}