// Copyright (c) 2019, 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:analyzer/dart/element/element.dart';
import 'package:analyzer/dart/element/type.dart';

/// Computes the variance of the [typeParameter] in the [type].
int computeVariance(TypeParameterElement typeParameter, DartType type) {
  if (type is TypeParameterType) {
    if (type.element == typeParameter) {
      return Variance.covariant;
    } else {
      return Variance.unrelated;
    }
  } else if (type is InterfaceType) {
    var result = Variance.unrelated;
    for (var argument in type.typeArguments) {
      result = Variance.meet(
        result,
        computeVariance(typeParameter, argument),
      );
    }
    return result;
  } else if (type is FunctionType) {
    var result = computeVariance(typeParameter, type.returnType);

    for (var parameter in type.typeFormals) {
      // If [parameter] is referenced in the bound at all, it makes the
      // variance of [parameter] in the entire type invariant.  The invocation
      // of [computeVariance] below is made to simply figure out if [variable]
      // occurs in the bound.
      var bound = parameter.bound;
      if (bound != null &&
          computeVariance(typeParameter, bound) != Variance.unrelated) {
        result = Variance.invariant;
      }
    }

    for (var parameter in type.parameters) {
      result = Variance.meet(
        result,
        Variance.combine(
          Variance.contravariant,
          computeVariance(typeParameter, parameter.type),
        ),
      );
    }
    return result;
  }
  return Variance.unrelated;
}

/// Value set for variance of a type parameter `X` in a type `T`.
class Variance {
  /// Used when `X` does not occur free in `T`.
  static const int unrelated = 0;

  /// Used when `X` occurs free in `T`, and `U <: V` implies `[U/X]T <: [V/X]T`.
  static const int covariant = 1;

  /// Used when `X` occurs free in `T`, and `U <: V` implies `[V/X]T <: [U/X]T`.
  static const int contravariant = 2;

  /// Used when there exists a pair `U` and `V` such that `U <: V`, but
  /// `[U/X]T` and `[V/X]T` are incomparable.
  static const int invariant = 3;

  /// Combines variances of `X` in `T` and `Y` in `S` into variance of `X` in
  /// `[Y/T]S`.
  ///
  /// Consider the following examples:
  ///
  /// * variance of `X` in `Function(X)` is [contravariant], variance of `Y`
  /// in `List<Y>` is [covariant], so variance of `X` in `List<Function(X)>` is
  /// [contravariant];
  ///
  /// * variance of `X` in `List<X>` is [covariant], variance of `Y` in
  /// `Function(Y)` is [contravariant], so variance of `X` in
  /// `Function(List<X>)` is [contravariant];
  ///
  /// * variance of `X` in `Function(X)` is [contravariant], variance of `Y` in
  /// `Function(Y)` is [contravariant], so variance of `X` in
  /// `Function(Function(X))` is [covariant];
  ///
  /// * let the following be declared:
  ///
  ///     typedef F<Z> = Function();
  ///
  /// then variance of `X` in `F<X>` is [unrelated], variance of `Y` in
  /// `List<Y>` is [covariant], so variance of `X` in `List<F<X>>` is
  /// [unrelated];
  ///
  /// * let the following be declared:
  ///
  ///     typedef G<Z> = Z Function(Z);
  ///
  /// then variance of `X` in `List<X>` is [covariant], variance of `Y` in
  /// `G<Y>` is [invariant], so variance of `X` in `G<List<X>>` is [invariant].
  static int combine(int a, int b) {
    if (a == unrelated || b == unrelated) return unrelated;
    if (a == invariant || b == invariant) return invariant;
    return a == b ? covariant : contravariant;
  }

  /// Variance values form a lattice where [unrelated] is the top, [invariant]
  /// is the bottom, and [covariant] and [contravariant] are incomparable.
  /// [meet] calculates the meet of two elements of such lattice.  It can be
  /// used, for example, to calculate the variance of a typedef type parameter
  /// if it's encountered on the RHS of the typedef multiple times.
  static int meet(int a, int b) => a | b;
}