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

import 'package:kernel/ast.dart'
    show
        BottomType,
        DartType,
        DartTypeVisitor,
        DynamicType,
        FunctionType,
        InterfaceType,
        InvalidType,
        NamedType,
        TypeParameter,
        TypeParameterType,
        TypedefType,
        Variance,
        VoidType;

import 'package:kernel/type_algebra.dart' show containsTypeVariable;

import 'package:kernel/util/graph.dart' show Graph, computeStrongComponents;

import '../builder/builder.dart';

import 'kernel_builder.dart'
    show
        ClassBuilder,
        FormalParameterBuilder,
        FunctionTypeBuilder,
        NamedTypeBuilder,
        TypeAliasBuilder,
        TypeBuilder,
        TypeDeclarationBuilder,
        TypeVariableBuilder;

import '../dill/dill_class_builder.dart' show DillClassBuilder;

import '../dill/dill_type_alias_builder.dart' show DillTypeAliasBuilder;

import '../fasta_codes.dart'
    show
        LocatedMessage,
        templateBoundIssueViaCycleNonSimplicity,
        templateBoundIssueViaLoopNonSimplicity,
        templateBoundIssueViaRawTypeWithNonSimpleBounds,
        templateNonSimpleBoundViaReference,
        templateNonSimpleBoundViaVariable;

export 'package:kernel/ast.dart' show Variance;

// Computes the variance of a variable in a type.  The function can be run
// before the types are resolved to compute variances of typedefs' type
// variables.  For that case if the type has its declaration set to null and its
// name matches that of the variable, it's interpreted as an occurrence of a
// type variable.
int computeVariance(TypeVariableBuilder variable, TypeBuilder type) {
  if (type is NamedTypeBuilder) {
    TypeDeclarationBuilder declaration = type.declaration;
    if (declaration == null || declaration is TypeVariableBuilder) {
      if (type.name == variable.name) {
        return Variance.covariant;
      } else {
        return Variance.unrelated;
      }
    } else {
      if (declaration is ClassBuilder) {
        int result = Variance.unrelated;
        if (type.arguments != null) {
          for (TypeBuilder argument in type.arguments) {
            result = Variance.meet(result, computeVariance(variable, argument));
          }
        }
        return result;
      } else if (declaration is TypeAliasBuilder) {
        int result = Variance.unrelated;
        if (type.arguments != null) {
          for (int i = 0; i < type.arguments.length; ++i) {
            result = Variance.meet(
                result,
                Variance.combine(
                    computeVariance(variable, type.arguments[i]),
                    computeVariance(
                        declaration.typeVariables[i], declaration.type)));
          }
        }
        return result;
      }
    }
  } else if (type is FunctionTypeBuilder) {
    int result = Variance.unrelated;
    if (type.returnType != null) {
      result =
          Variance.meet(result, computeVariance(variable, type.returnType));
    }
    if (type.typeVariables != null) {
      for (TypeVariableBuilder typeVariable in type.typeVariables) {
        // If [variable] is referenced in the bound at all, it makes the
        // variance of [variable] in the entire type invariant.  The invocation
        // of [computeVariance] below is made to simply figure out if [variable]
        // occurs in the bound.
        if (typeVariable.bound != null &&
            computeVariance(variable, typeVariable.bound) !=
                Variance.unrelated) {
          result = Variance.invariant;
        }
      }
    }
    if (type.formals != null) {
      for (FormalParameterBuilder formal in type.formals) {
        result = Variance.meet(
            result,
            Variance.combine(Variance.contravariant,
                computeVariance(variable, formal.type)));
      }
    }
    return result;
  }
  return Variance.unrelated;
}

/// Combines syntactic nullabilities on types for performing type substitution.
///
/// The syntactic substitution should preserve a `?` if it was either on the
/// type parameter occurrence or on the type argument replacing it.
NullabilityBuilder combineNullabilityBuildersForSubstitution(
    NullabilityBuilder a, NullabilityBuilder b) {
  assert(
      (identical(a, const NullabilityBuilder.nullable()) ||
              identical(a, const NullabilityBuilder.omitted())) &&
          (identical(b, const NullabilityBuilder.nullable()) ||
              identical(b, const NullabilityBuilder.omitted())),
      "Both arguments to combineNullabilityBuildersForSubstitution "
      "should be identical to either 'const NullabilityBuilder.nullable()' or "
      "'const NullabilityBuilder.omitted()'.");

  if (identical(a, const NullabilityBuilder.nullable()) ||
      identical(b, const NullabilityBuilder.nullable())) {
    return const NullabilityBuilder.nullable();
  }

  return const NullabilityBuilder.omitted();
}

TypeBuilder substituteRange(
    TypeBuilder type,
    Map<TypeVariableBuilder, TypeBuilder> upperSubstitution,
    Map<TypeVariableBuilder, TypeBuilder> lowerSubstitution,
    List<TypeBuilder> unboundTypes,
    List<TypeVariableBuilder> unboundTypeVariables,
    {final int variance = Variance.covariant}) {
  if (type is NamedTypeBuilder) {
    if (type.declaration is TypeVariableBuilder) {
      if (variance == Variance.contravariant) {
        TypeBuilder replacement = lowerSubstitution[type.declaration];
        if (replacement != null) {
          return replacement.withNullabilityBuilder(
              combineNullabilityBuildersForSubstitution(
                  replacement.nullabilityBuilder, type.nullabilityBuilder));
        }
        return type;
      }
      TypeBuilder replacement = upperSubstitution[type.declaration];
      if (replacement != null) {
        return replacement.withNullabilityBuilder(
            combineNullabilityBuildersForSubstitution(
                replacement.nullabilityBuilder, type.nullabilityBuilder));
      }
      return type;
    }
    if (type.arguments == null || type.arguments.length == 0) {
      return type;
    }
    List<TypeBuilder> arguments;
    TypeDeclarationBuilder declaration = type.declaration;
    if (declaration == null) {
      assert(unboundTypes != null,
          "Can not handle unbound named type builders without `unboundTypes`.");
      assert(
          unboundTypeVariables != null,
          "Can not handle unbound named type builders without "
          "`unboundTypeVariables`.");
      assert(
          identical(upperSubstitution, lowerSubstitution),
          "Can only handle unbound named type builders identical "
          "`upperSubstitution` and `lowerSubstitution`.");
      for (int i = 0; i < type.arguments.length; ++i) {
        TypeBuilder substitutedArgument = substituteRange(
            type.arguments[i],
            upperSubstitution,
            lowerSubstitution,
            unboundTypes,
            unboundTypeVariables,
            variance: variance);
        if (substitutedArgument != type.arguments[i]) {
          arguments ??= type.arguments.toList();
          arguments[i] = substitutedArgument;
        }
      }
    } else if (declaration is ClassBuilder) {
      for (int i = 0; i < type.arguments.length; ++i) {
        TypeBuilder substitutedArgument = substituteRange(
            type.arguments[i],
            upperSubstitution,
            lowerSubstitution,
            unboundTypes,
            unboundTypeVariables,
            variance: variance);
        if (substitutedArgument != type.arguments[i]) {
          arguments ??= type.arguments.toList();
          arguments[i] = substitutedArgument;
        }
      }
    } else if (declaration is TypeAliasBuilder) {
      for (int i = 0; i < type.arguments.length; ++i) {
        TypeVariableBuilder variable = declaration.typeVariables[i];
        TypeBuilder substitutedArgument = substituteRange(
            type.arguments[i],
            upperSubstitution,
            lowerSubstitution,
            unboundTypes,
            unboundTypeVariables,
            variance: Variance.combine(variance, variable.variance));
        if (substitutedArgument != type.arguments[i]) {
          arguments ??= type.arguments.toList();
          arguments[i] = substitutedArgument;
        }
      }
    } else if (declaration is InvalidTypeBuilder) {
      // Don't substitute.
    } else {
      assert(false, "Unexpected named type builder declaration: $declaration.");
    }
    if (arguments != null) {
      NamedTypeBuilder newTypeBuilder =
          new NamedTypeBuilder(type.name, type.nullabilityBuilder, arguments);
      if (declaration != null) {
        newTypeBuilder.bind(declaration);
      } else {
        unboundTypes.add(newTypeBuilder);
      }
      return newTypeBuilder;
    }
    return type;
  } else if (type is FunctionTypeBuilder) {
    List<TypeVariableBuilder> variables;
    if (type.typeVariables != null) {
      variables = new List<TypeVariableBuilder>(type.typeVariables.length);
    }
    List<FormalParameterBuilder> formals;
    if (type.formals != null) {
      formals = new List<FormalParameterBuilder>(type.formals.length);
    }
    TypeBuilder returnType;
    bool changed = false;

    Map<TypeVariableBuilder, TypeBuilder> functionTypeUpperSubstitution;
    Map<TypeVariableBuilder, TypeBuilder> functionTypeLowerSubstitution;
    if (type.typeVariables != null) {
      for (int i = 0; i < variables.length; i++) {
        TypeVariableBuilder variable = type.typeVariables[i];
        TypeBuilder bound = substituteRange(variable.bound, upperSubstitution,
            lowerSubstitution, unboundTypes, unboundTypeVariables,
            variance: Variance.invariant);
        if (bound != variable.bound) {
          TypeVariableBuilder newTypeVariableBuilder = variables[i] =
              new TypeVariableBuilder(
                  variable.name, variable.parent, variable.charOffset,
                  bound: bound);
          unboundTypeVariables.add(newTypeVariableBuilder);
          if (functionTypeUpperSubstitution == null) {
            functionTypeUpperSubstitution = {}..addAll(upperSubstitution);
            functionTypeLowerSubstitution = {}..addAll(lowerSubstitution);
          }
          functionTypeUpperSubstitution[variable] =
              functionTypeLowerSubstitution[variable] =
                  new NamedTypeBuilder.fromTypeDeclarationBuilder(
                      newTypeVariableBuilder,
                      const NullabilityBuilder.omitted());
          changed = true;
        } else {
          variables[i] = variable;
        }
      }
    }
    if (type.formals != null) {
      for (int i = 0; i < formals.length; i++) {
        FormalParameterBuilder formal = type.formals[i];
        TypeBuilder parameterType = substituteRange(
            formal.type,
            functionTypeUpperSubstitution ?? upperSubstitution,
            functionTypeLowerSubstitution ?? lowerSubstitution,
            unboundTypes,
            unboundTypeVariables,
            variance: Variance.combine(variance, Variance.contravariant));
        if (parameterType != formal.type) {
          formals[i] = new FormalParameterBuilder(
              formal.metadata,
              formal.modifiers,
              parameterType,
              formal.name,
              formal.parent,
              formal.charOffset,
              formal.fileUri);
          changed = true;
        } else {
          formals[i] = formal;
        }
      }
    }
    returnType = substituteRange(
        type.returnType,
        functionTypeUpperSubstitution ?? upperSubstitution,
        functionTypeLowerSubstitution ?? lowerSubstitution,
        unboundTypes,
        unboundTypeVariables,
        variance: variance);
    changed = changed || returnType != type.returnType;

    if (changed) {
      return new FunctionTypeBuilder(
          returnType, variables, formals, type.nullabilityBuilder);
    }
    return type;
  }
  return type;
}

TypeBuilder substitute(
    TypeBuilder type, Map<TypeVariableBuilder, TypeBuilder> substitution,
    {List<TypeBuilder> unboundTypes,
    List<TypeVariableBuilder> unboundTypeVariables}) {
  return substituteRange(
      type, substitution, substitution, unboundTypes, unboundTypeVariables,
      variance: Variance.covariant);
}

/// Calculates bounds to be provided as type arguments in place of missing type
/// arguments on raw types with the given type parameters.
///
/// See the [description]
/// (https://github.com/dart-lang/sdk/blob/master/docs/language/informal/instantiate-to-bound.md)
/// of the algorithm for details.
List<TypeBuilder> calculateBounds(List<TypeVariableBuilder> variables,
    TypeBuilder dynamicType, TypeBuilder bottomType, ClassBuilder objectClass) {
  List<TypeBuilder> bounds = new List<TypeBuilder>(variables.length);

  for (int i = 0; i < variables.length; i++) {
    bounds[i] = variables[i].bound ?? dynamicType;
  }

  TypeVariablesGraph graph = new TypeVariablesGraph(variables, bounds);
  List<List<int>> stronglyConnected = computeStrongComponents(graph);
  for (List<int> component in stronglyConnected) {
    Map<TypeVariableBuilder, TypeBuilder> dynamicSubstitution =
        <TypeVariableBuilder, TypeBuilder>{};
    Map<TypeVariableBuilder, TypeBuilder> nullSubstitution =
        <TypeVariableBuilder, TypeBuilder>{};
    for (int variableIndex in component) {
      dynamicSubstitution[variables[variableIndex]] = dynamicType;
      nullSubstitution[variables[variableIndex]] = bottomType;
    }
    for (int variableIndex in component) {
      TypeVariableBuilder variable = variables[variableIndex];
      bounds[variableIndex] = substituteRange(bounds[variableIndex],
          dynamicSubstitution, nullSubstitution, null, null,
          variance: variable.variance);
    }
  }

  for (int i = 0; i < variables.length; i++) {
    Map<TypeVariableBuilder, TypeBuilder> substitution =
        <TypeVariableBuilder, TypeBuilder>{};
    Map<TypeVariableBuilder, TypeBuilder> nullSubstitution =
        <TypeVariableBuilder, TypeBuilder>{};
    substitution[variables[i]] = bounds[i];
    nullSubstitution[variables[i]] = bottomType;
    for (int j = 0; j < variables.length; j++) {
      TypeVariableBuilder variable = variables[j];
      bounds[j] = substituteRange(
          bounds[j], substitution, nullSubstitution, null, null,
          variance: variable.variance);
    }
  }

  return bounds;
}

/// Graph of mutual dependencies of type variables from the same declaration.
/// Type variables are represented by their indices in the corresponding
/// declaration.
class TypeVariablesGraph implements Graph<int> {
  List<int> vertices;
  List<TypeVariableBuilder> variables;
  List<TypeBuilder> bounds;

  // `edges[i]` is the list of indices of type variables that reference the type
  // variable with the index `i` in their bounds.
  List<List<int>> edges;

  TypeVariablesGraph(this.variables, this.bounds) {
    assert(variables.length == bounds.length);

    vertices = new List<int>(variables.length);
    Map<TypeVariableBuilder, int> variableIndices =
        <TypeVariableBuilder, int>{};
    edges = new List<List<int>>(variables.length);
    for (int i = 0; i < vertices.length; i++) {
      vertices[i] = i;
      variableIndices[variables[i]] = i;
      edges[i] = <int>[];
    }

    void collectReferencesFrom(int index, TypeBuilder type) {
      if (type is NamedTypeBuilder) {
        if (type.declaration is TypeVariableBuilder &&
            this.variables.contains(type.declaration)) {
          edges[variableIndices[type.declaration]].add(index);
        }
        if (type.arguments != null) {
          for (TypeBuilder argument in type.arguments) {
            collectReferencesFrom(index, argument);
          }
        }
      } else if (type is FunctionTypeBuilder) {
        if (type.typeVariables != null) {
          for (TypeVariableBuilder typeVariable in type.typeVariables) {
            collectReferencesFrom(index, typeVariable.bound);
          }
        }
        if (type.formals != null) {
          for (FormalParameterBuilder parameter in type.formals) {
            collectReferencesFrom(index, parameter.type);
          }
        }
        collectReferencesFrom(index, type.returnType);
      }
    }

    for (int i = 0; i < vertices.length; i++) {
      collectReferencesFrom(i, bounds[i]);
    }
  }

  /// Returns indices of type variables that depend on the type variable with
  /// [index].
  Iterable<int> neighborsOf(int index) {
    return edges[index];
  }
}

/// Finds all type builders for [variable] in [type].
///
/// Returns list of the found type builders.
List<NamedTypeBuilder> findVariableUsesInType(
  TypeVariableBuilder variable,
  TypeBuilder type,
) {
  List<NamedTypeBuilder> uses = <NamedTypeBuilder>[];
  if (type is NamedTypeBuilder) {
    if (type.declaration == variable) {
      uses.add(type);
    } else {
      if (type.arguments != null) {
        for (TypeBuilder argument in type.arguments) {
          uses.addAll(findVariableUsesInType(variable, argument));
        }
      }
    }
  } else if (type is FunctionTypeBuilder) {
    uses.addAll(findVariableUsesInType(variable, type.returnType));
    if (type.typeVariables != null) {
      for (TypeVariableBuilder dependentVariable in type.typeVariables) {
        if (dependentVariable.bound != null) {
          uses.addAll(
              findVariableUsesInType(variable, dependentVariable.bound));
        }
        if (dependentVariable.defaultType != null) {
          uses.addAll(
              findVariableUsesInType(variable, dependentVariable.defaultType));
        }
      }
    }
    if (type.formals != null) {
      for (FormalParameterBuilder formal in type.formals) {
        uses.addAll(findVariableUsesInType(variable, formal.type));
      }
    }
  }
  return uses;
}

/// Finds those of [variables] that reference other [variables] in their bounds.
///
/// Returns flattened list of pairs.  The first element in the pair is the type
/// variable builder from [variables] that references other [variables] in its
/// bound.  The second element in the pair is the list of found references
/// represented as type builders.
List<Object> findInboundReferences(List<TypeVariableBuilder> variables) {
  List<Object> variablesAndDependencies = <Object>[];
  for (TypeVariableBuilder dependent in variables) {
    List<NamedTypeBuilder> dependencies = <NamedTypeBuilder>[];
    for (TypeVariableBuilder dependence in variables) {
      List<NamedTypeBuilder> uses =
          findVariableUsesInType(dependence, dependent.bound);
      if (uses.length != 0) {
        dependencies.addAll(uses);
      }
    }
    if (dependencies.length != 0) {
      variablesAndDependencies.add(dependent);
      variablesAndDependencies.add(dependencies);
    }
  }
  return variablesAndDependencies;
}

/// Finds raw generic types in [type] with inbound references in type variables.
///
/// Returns flattened list of pairs.  The first element in the pair is the found
/// raw generic type.  The second element in the pair is the list of type
/// variables of that type with inbound references in the format specified in
/// [findInboundReferences].
List<Object> findRawTypesWithInboundReferences(TypeBuilder type) {
  List<Object> typesAndDependencies = <Object>[];
  if (type is NamedTypeBuilder) {
    if (type.arguments == null) {
      TypeDeclarationBuilder declaration = type.declaration;
      if (declaration is DillClassBuilder) {
        bool hasInbound = false;
        List<TypeParameter> typeParameters = declaration.cls.typeParameters;
        for (int i = 0; i < typeParameters.length && !hasInbound; ++i) {
          if (containsTypeVariable(
              typeParameters[i].bound, typeParameters.toSet())) {
            hasInbound = true;
          }
        }
        if (hasInbound) {
          typesAndDependencies.add(type);
          typesAndDependencies.add(const <Object>[]);
        }
      } else if (declaration is DillTypeAliasBuilder) {
        bool hasInbound = false;
        List<TypeParameter> typeParameters = declaration.typedef.typeParameters;
        for (int i = 0; i < typeParameters.length && !hasInbound; ++i) {
          if (containsTypeVariable(
              typeParameters[i].bound, typeParameters.toSet())) {
            hasInbound = true;
          }
        }
        if (hasInbound) {
          typesAndDependencies.add(type);
          typesAndDependencies.add(const <Object>[]);
        }
      } else if (declaration is ClassBuilder &&
          declaration.typeVariables != null) {
        List<Object> dependencies =
            findInboundReferences(declaration.typeVariables);
        if (dependencies.length != 0) {
          typesAndDependencies.add(type);
          typesAndDependencies.add(dependencies);
        }
      } else if (declaration is TypeAliasBuilder) {
        if (declaration.typeVariables != null) {
          List<Object> dependencies =
              findInboundReferences(declaration.typeVariables);
          if (dependencies.length != 0) {
            typesAndDependencies.add(type);
            typesAndDependencies.add(dependencies);
          }
        }
        if (declaration.type is FunctionTypeBuilder) {
          FunctionTypeBuilder type = declaration.type;
          if (type.typeVariables != null) {
            List<Object> dependencies =
                findInboundReferences(type.typeVariables);
            if (dependencies.length != 0) {
              typesAndDependencies.add(type);
              typesAndDependencies.add(dependencies);
            }
          }
        }
      }
    } else {
      for (TypeBuilder argument in type.arguments) {
        typesAndDependencies
            .addAll(findRawTypesWithInboundReferences(argument));
      }
    }
  } else if (type is FunctionTypeBuilder) {
    typesAndDependencies
        .addAll(findRawTypesWithInboundReferences(type.returnType));
    if (type.typeVariables != null) {
      for (TypeVariableBuilder variable in type.typeVariables) {
        if (variable.bound != null) {
          typesAndDependencies
              .addAll(findRawTypesWithInboundReferences(variable.bound));
        }
        if (variable.defaultType != null) {
          typesAndDependencies
              .addAll(findRawTypesWithInboundReferences(variable.defaultType));
        }
      }
    }
    if (type.formals != null) {
      for (FormalParameterBuilder formal in type.formals) {
        typesAndDependencies
            .addAll(findRawTypesWithInboundReferences(formal.type));
      }
    }
  }
  return typesAndDependencies;
}

/// Finds issues by raw generic types with inbound references in type variables.
///
/// Returns flattened list of triplets.  The first element of the triplet is the
/// [TypeDeclarationBuilder] for the type variable from [variables] that has raw
/// generic types with inbound references in its bound.  The second element of
/// the triplet is the error message.  The third element is the context.
List<Object> getInboundReferenceIssues(List<TypeVariableBuilder> variables) {
  List<Object> issues = <Object>[];
  for (TypeVariableBuilder variable in variables) {
    if (variable.bound != null) {
      List<Object> rawTypesAndMutualDependencies =
          findRawTypesWithInboundReferences(variable.bound);
      for (int i = 0; i < rawTypesAndMutualDependencies.length; i += 2) {
        NamedTypeBuilder type = rawTypesAndMutualDependencies[i];
        List<Object> variablesAndDependencies =
            rawTypesAndMutualDependencies[i + 1];
        for (int j = 0; j < variablesAndDependencies.length; j += 2) {
          TypeVariableBuilder dependent = variablesAndDependencies[j];
          List<NamedTypeBuilder> dependencies = variablesAndDependencies[j + 1];
          for (NamedTypeBuilder dependency in dependencies) {
            issues.add(variable);
            issues.add(templateBoundIssueViaRawTypeWithNonSimpleBounds
                .withArguments(type.declaration.name));
            issues.add(<LocatedMessage>[
              templateNonSimpleBoundViaVariable
                  .withArguments(dependency.declaration.name)
                  .withLocation(dependent.fileUri, dependent.charOffset,
                      dependent.name.length)
            ]);
          }
        }
        if (variablesAndDependencies.length == 0) {
          // The inbound references are in a compiled declaration in a .dill.
          issues.add(variable);
          issues.add(templateBoundIssueViaRawTypeWithNonSimpleBounds
              .withArguments(type.declaration.name));
          issues.add(const <LocatedMessage>[]);
        }
      }
    }
  }
  return issues;
}

/// Finds raw type paths starting from those in [start] and ending with [end].
///
/// Returns list of found paths.  Each path is represented as a list of
/// alternating builders of the raw generic types from the path and builders of
/// type variables of the immediately preceding types that contain the reference
/// to the next raw generic type in the path.  The list ends with the type
/// builder for [end].
///
/// The reason for putting the type variables into the paths as well as for
/// using type for [start], and not the corresponding type declaration,
/// is better error reporting.
List<List<Object>> findRawTypePathsToDeclaration(
    TypeBuilder start, TypeDeclarationBuilder end,
    [Set<TypeDeclarationBuilder> visited]) {
  visited ??= new Set<TypeDeclarationBuilder>.identity();
  List<List<Object>> paths = <List<Object>>[];
  if (start is NamedTypeBuilder) {
    TypeDeclarationBuilder declaration = start.declaration;
    if (start.arguments == null) {
      if (start.declaration == end) {
        paths.add(<Object>[start]);
      } else if (visited.add(start.declaration)) {
        if (declaration is ClassBuilder && declaration.typeVariables != null) {
          for (TypeVariableBuilder variable in declaration.typeVariables) {
            if (variable.bound != null) {
              for (List<Object> path in findRawTypePathsToDeclaration(
                  variable.bound, end, visited)) {
                paths.add(<Object>[start, variable]..addAll(path));
              }
            }
          }
        } else if (declaration is TypeAliasBuilder) {
          if (declaration.typeVariables != null) {
            for (TypeVariableBuilder variable in declaration.typeVariables) {
              if (variable.bound != null) {
                for (List<Object> dependencyPath
                    in findRawTypePathsToDeclaration(
                        variable.bound, end, visited)) {
                  paths.add(<Object>[start, variable]..addAll(dependencyPath));
                }
              }
            }
          }
          if (declaration.type is FunctionTypeBuilder) {
            FunctionTypeBuilder type = declaration.type;
            if (type.typeVariables != null) {
              for (TypeVariableBuilder variable in type.typeVariables) {
                if (variable.bound != null) {
                  for (List<Object> dependencyPath
                      in findRawTypePathsToDeclaration(
                          variable.bound, end, visited)) {
                    paths
                        .add(<Object>[start, variable]..addAll(dependencyPath));
                  }
                }
              }
            }
          }
        }
        visited.remove(start.declaration);
      }
    } else {
      for (TypeBuilder argument in start.arguments) {
        paths.addAll(findRawTypePathsToDeclaration(argument, end, visited));
      }
    }
  } else if (start is FunctionTypeBuilder) {
    paths.addAll(findRawTypePathsToDeclaration(start.returnType, end, visited));
    if (start.typeVariables != null) {
      for (TypeVariableBuilder variable in start.typeVariables) {
        if (variable.bound != null) {
          paths.addAll(
              findRawTypePathsToDeclaration(variable.bound, end, visited));
        }
        if (variable.defaultType != null) {
          paths.addAll(findRawTypePathsToDeclaration(
              variable.defaultType, end, visited));
        }
      }
    }
    if (start.formals != null) {
      for (FormalParameterBuilder formal in start.formals) {
        paths.addAll(findRawTypePathsToDeclaration(formal.type, end, visited));
      }
    }
  }
  return paths;
}

/// Finds raw generic type cycles ending and starting with [declaration].
///
/// Returns list of found cycles.  Each cycle is represented as a list of
/// alternating raw generic types from the cycle and type variables of the
/// immediately preceding type that reference the next type in the cycle.  The
/// cycle starts with a type variable from [declaration] and ends with a type
/// that has [declaration] as its declaration.
///
/// The reason for putting the type variables into the cycles is better error
/// reporting.
List<List<Object>> findRawTypeCycles(TypeDeclarationBuilder declaration) {
  List<List<Object>> cycles = <List<Object>>[];
  if (declaration is ClassBuilder && declaration.typeVariables != null) {
    for (TypeVariableBuilder variable in declaration.typeVariables) {
      if (variable.bound != null) {
        for (List<Object> path
            in findRawTypePathsToDeclaration(variable.bound, declaration)) {
          cycles.add(<Object>[variable]..addAll(path));
        }
      }
    }
  } else if (declaration is TypeAliasBuilder) {
    if (declaration.typeVariables != null) {
      for (TypeVariableBuilder variable in declaration.typeVariables) {
        if (variable.bound != null) {
          for (List<Object> dependencyPath
              in findRawTypePathsToDeclaration(variable.bound, declaration)) {
            cycles.add(<Object>[variable]..addAll(dependencyPath));
          }
        }
      }
    }
    if (declaration.type is FunctionTypeBuilder) {
      FunctionTypeBuilder type = declaration.type;
      if (type.typeVariables != null) {
        for (TypeVariableBuilder variable in type.typeVariables) {
          if (variable.bound != null) {
            for (List<Object> dependencyPath
                in findRawTypePathsToDeclaration(variable.bound, declaration)) {
              cycles.add(<Object>[variable]..addAll(dependencyPath));
            }
          }
        }
      }
    }
  }
  return cycles;
}

/// Converts raw generic type [cycles] for [declaration] into reportable issues.
///
/// The [cycles] are expected to be in the format specified for the return value
/// of [findRawTypeCycles].
///
/// Returns flattened list of triplets.  The first element of the triplet is the
/// [TypeDeclarationBuilder] for the type variable from [variables] that has raw
/// generic types with inbound references in its bound.  The second element of
/// the triplet is the error message.  The third element is the context.
List<Object> convertRawTypeCyclesIntoIssues(
    TypeDeclarationBuilder declaration, List<List<Object>> cycles) {
  List<Object> issues = <Object>[];
  for (List<Object> cycle in cycles) {
    if (cycle.length == 2) {
      // Loop.
      TypeVariableBuilder variable = cycle[0];
      NamedTypeBuilder type = cycle[1];
      issues.add(variable);
      issues.add(templateBoundIssueViaLoopNonSimplicity
          .withArguments(type.declaration.name));
      issues.add(null); // Context.
    } else {
      List<LocatedMessage> context = <LocatedMessage>[];
      for (int i = 0; i < cycle.length; i += 2) {
        TypeVariableBuilder variable = cycle[i];
        NamedTypeBuilder type = cycle[i + 1];
        context.add(templateNonSimpleBoundViaReference
            .withArguments(type.declaration.name)
            .withLocation(
                variable.fileUri, variable.charOffset, variable.name.length));
      }
      NamedTypeBuilder firstEncounteredType = cycle[1];

      issues.add(declaration);
      issues.add(templateBoundIssueViaCycleNonSimplicity.withArguments(
          declaration.name, firstEncounteredType.declaration.name));
      issues.add(context);
    }
  }
  return issues;
}

/// Finds non-simplicity issues for the given set of [variables].
///
/// The issues are those caused by raw types with inbound references in the
/// bounds of their type variables.
///
/// Returns flattened list of triplets, each triplet representing an issue.  The
/// first element in the triplet is the type declaration that has the issue.
/// The second element in the triplet is the error message.  The third element
/// in the triplet is the context.
List<Object> getNonSimplicityIssuesForTypeVariables(
    List<TypeVariableBuilder> variables) {
  if (variables == null) return <Object>[];
  return getInboundReferenceIssues(variables);
}

/// Finds non-simplicity issues for the given [declaration].
///
/// The issues are those caused by raw types with inbound references in the
/// bounds of type variables from [declaration] and by cycles of raw types
/// containing [declaration].
///
/// Returns flattened list of triplets, each triplet representing an issue.  The
/// first element in the triplet is the type declaration that has the issue.
/// The second element in the triplet is the error message.  The third element
/// in the triplet is the context.
List<Object> getNonSimplicityIssuesForDeclaration(
    TypeDeclarationBuilder declaration,
    {bool performErrorRecovery: true}) {
  List<Object> issues = <Object>[];
  if (declaration is ClassBuilder && declaration.typeVariables != null) {
    issues.addAll(getInboundReferenceIssues(declaration.typeVariables));
  } else if (declaration is TypeAliasBuilder &&
      declaration.typeVariables != null) {
    issues.addAll(getInboundReferenceIssues(declaration.typeVariables));
  }
  List<List<Object>> cyclesToReport = <List<Object>>[];
  for (List<Object> cycle in findRawTypeCycles(declaration)) {
    // To avoid reporting the same error for each element of the cycle, we only
    // do so if it comes the first in the lexicographical order.  Note that
    // one-element cycles shouldn't be checked, as they are loops.
    if (cycle.length == 2) {
      cyclesToReport.add(cycle);
    } else {
      String declarationPathAndName =
          "${declaration.fileUri}:${declaration.name}";
      String lexMinPathAndName = null;
      for (int i = 1; i < cycle.length; i += 2) {
        NamedTypeBuilder type = cycle[i];
        String pathAndName =
            "${type.declaration.fileUri}:${type.declaration.name}";
        if (lexMinPathAndName == null ||
            lexMinPathAndName.compareTo(pathAndName) > 0) {
          lexMinPathAndName = pathAndName;
        }
      }
      if (declarationPathAndName == lexMinPathAndName) {
        cyclesToReport.add(cycle);
      }
    }
  }
  List<Object> rawTypeCyclesAsIssues =
      convertRawTypeCyclesIntoIssues(declaration, cyclesToReport);
  issues.addAll(rawTypeCyclesAsIssues);

  if (performErrorRecovery) {
    breakCycles(cyclesToReport);
  }

  return issues;
}

/// Break raw generic type [cycles] as error recovery.
///
/// The [cycles] are expected to be in the format specified for the return value
/// of [findRawTypeCycles].
void breakCycles(List<List<Object>> cycles) {
  for (List<Object> cycle in cycles) {
    TypeVariableBuilder variable = cycle[0];
    variable.bound = null;
  }
}

void findGenericFunctionTypes(TypeBuilder type, {List<TypeBuilder> result}) {
  result ??= <TypeBuilder>[];
  if (type is FunctionTypeBuilder) {
    if (type.typeVariables != null && type.typeVariables.length > 0) {
      result.add(type);

      for (TypeVariableBuilder typeVariable in type.typeVariables) {
        findGenericFunctionTypes(typeVariable.bound, result: result);
        findGenericFunctionTypes(typeVariable.defaultType, result: result);
      }
    }
    findGenericFunctionTypes(type.returnType, result: result);
    if (type.formals != null) {
      for (FormalParameterBuilder formal in type.formals) {
        findGenericFunctionTypes(formal.type, result: result);
      }
    }
  } else if (type is NamedTypeBuilder && type.arguments != null) {
    for (TypeBuilder argument in type.arguments) {
      findGenericFunctionTypes(argument, result: result);
    }
  }
}

/// Returns true if [type] contains any type variables whatsoever. This should
/// only be used for working around transitional issues.
// TODO(ahe): Remove this method.
bool hasAnyTypeVariables(DartType type) {
  return type.accept(const TypeVariableSearch());
}

/// Don't use this directly, use [hasAnyTypeVariables] instead. But don't use
/// that either.
// TODO(ahe): Remove this class.
class TypeVariableSearch implements DartTypeVisitor<bool> {
  const TypeVariableSearch();

  bool defaultDartType(DartType node) => throw "unsupported";

  bool anyTypeVariables(List<DartType> types) {
    for (DartType type in types) {
      if (type.accept(this)) return true;
    }
    return false;
  }

  bool visitInvalidType(InvalidType node) => false;

  bool visitDynamicType(DynamicType node) => false;

  bool visitVoidType(VoidType node) => false;

  bool visitBottomType(BottomType node) => false;

  bool visitInterfaceType(InterfaceType node) {
    return anyTypeVariables(node.typeArguments);
  }

  bool visitFunctionType(FunctionType node) {
    if (anyTypeVariables(node.positionalParameters)) return true;
    for (TypeParameter variable in node.typeParameters) {
      if (variable.bound.accept(this)) return true;
    }
    for (NamedType type in node.namedParameters) {
      if (type.type.accept(this)) return true;
    }
    return false;
  }

  bool visitTypeParameterType(TypeParameterType node) => true;

  bool visitTypedefType(TypedefType node) {
    return anyTypeVariables(node.typeArguments);
  }
}