<commit_before>// Copyright (c) 2016, 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 kernel.type_algebra;

import 'ast.dart';

/// Returns a type where all occurrences of the given type parameters have been
/// replaced with the corresponding types.
///
/// This will copy only the subterms of [type] that contain substituted
/// variables; all other [DartType] objects will be reused.
///
/// In particular, if no variables were substituted, this is guaranteed to
/// return the [type] instance (not a copy), so the caller may use [identical]
/// to efficiently check if a distinct type was created.
DartType substitute(DartType type, Map<TypeParameter, DartType> substitution) {
  if (substitution.isEmpty) return type;
  return Substitution.fromMap(substitution).substituteType(type);
}

/// Returns a mapping from the type parameters declared on the class of [type]
/// to the actual type arguments provided in [type].
///
/// This can be passed as argument to [substitute].
Map<TypeParameter, DartType> getSubstitutionMap(Supertype type) {
  return type.typeArguments.isEmpty
      ? const <TypeParameter, DartType>{}
      : new Map<TypeParameter, DartType>.fromIterables(
          type.classNode.typeParameters, type.typeArguments);
}

Map<TypeParameter, DartType> getUpperBoundSubstitutionMap(Class host) {
  if (host.typeParameters.isEmpty) return const <TypeParameter, DartType>{};
  var result = <TypeParameter, DartType>{};
  for (var parameter in host.typeParameters) {
    result[parameter] = const DynamicType();
  }
  for (var parameter in host.typeParameters) {
    result[parameter] = substitute(parameter.bound, result);
  }
  return result;
}

/// Like [substitute], except when a type in the [substitution] map references
/// another substituted type variable, the mapping for that type is recursively
/// inserted.
///
/// For example `Set<G>` substituted with `{T -> String, G -> List<T>}` results
/// in `Set<List<String>>`.
///
/// Returns `null` if the substitution map contains a cycle reachable from a
/// type variable in [type] (the resulting type would be infinite).
///
/// The [substitution] map will be mutated so that the right-hand sides may
/// be remapped to the deeply substituted type, but only for the keys that are
/// reachable from [type].
///
/// As with [substitute], this is guaranteed to return the same instance if no
/// substitution was performed.
DartType substituteDeep(
    DartType type, Map<TypeParameter, DartType> substitution) {
  if (substitution.isEmpty) return type;
  var substitutor = new _DeepTypeSubstitutor(substitution);
  var result = substitutor.visit(type);
  return substitutor.isInfinite ? null : result;
}

List<DartType> calculateBounds(
    List<TypeParameter> typeParameters, Class object) {
  var refinedBounds = new List<DartType>(typeParameters.length);
  var substitution = <TypeParameter, DartType>{};
  var substitutionToDynamic = <TypeParameter, DartType>{};

  for (int i = 0; i < typeParameters.length; i++) {
    DartType type = typeParameters[i].bound;
    if (type == null || type is InterfaceType && type.classNode == object) {
      type = const DynamicType();
    }

    refinedBounds[i] = type;
    substitution[typeParameters[i]] = type;
    substitutionToDynamic[typeParameters[i]] = const DynamicType();
  }

  var result = new List<DartType>(typeParameters.length);
  for (int i = 0; i < result.length; i++) {
    result[i] = substituteDeep(refinedBounds[i], substitution);
    if (result[i] == null) {
      result[i] = substitute(refinedBounds[i], substitutionToDynamic);
    }
  }
  return result;
}

DartType instantiateToBounds(DartType type, Class object) {
  if (type is InterfaceType) {
    for (var typeArgument in type.typeArguments) {
      // If at least one of the arguments is not dynamic, we assume that the
      // type is not raw and does not need instantiation of its type parameters
      // to their bounds.
      if (typeArgument is! DynamicType) {
        return type;
      }
    }
    return new InterfaceType.byReference(
        type.className, calculateBounds(type.classNode.typeParameters, object));
  }
  if (type is TypedefType) {
    for (var typeArgument in type.typeArguments) {
      if (typeArgument is! DynamicType) {
        return type;
      }
    }
    return new TypedefType.byReference(type.typedefReference,
        calculateBounds(type.typedefNode.typeParameters, object));
  }
  return type;
}

/// Returns true if [type] contains a reference to any of the given [variables].
///
/// It is an error to call this with a [type] that contains a [FunctionType]
/// that declares one of the parameters in [variables].
bool containsTypeVariable(DartType type, Set<TypeParameter> variables) {
  if (variables.isEmpty) return false;
  return new _OccurrenceVisitor(variables).visit(type);
}

/// Given a set of type variables, finds a substitution of those variables such
/// that the two given types becomes equal, or returns `null` if no such
/// substitution exists.
///
/// For example, unifying `List<T>` with `List<String>`, where `T` is a
/// quantified variable, yields the substitution `T = String`.
///
/// If successful, this equation holds:
///
///     substitute(type1, substitution) == substitute(type2, substitution)
///
/// The unification can fail for two reasons:
/// - incompatible types, e.g. `List<T>` cannot be unified with `Set<T>`.
/// - infinite types: e.g. `T` cannot be unified with `List<T>` because it
///   would create the infinite type `List<List<List<...>>>`.
Map<TypeParameter, DartType> unifyTypes(
    DartType type1, DartType type2, Set<TypeParameter> quantifiedVariables) {
  var unifier = new _TypeUnification(type1, type2, quantifiedVariables);
  return unifier.success ? unifier.substitution : null;
}

/// Generates a fresh copy of the given type parameters, with their bounds
/// substituted to reference the new parameters.
///
/// The returned object contains the fresh type parameter list as well as a
/// mapping to be used for replacing other types to use the new type parameters.
FreshTypeParameters getFreshTypeParameters(List<TypeParameter> typeParameters) {
  var freshParameters = new List<TypeParameter>.generate(
      typeParameters.length, (i) => new TypeParameter(typeParameters[i].name),
      growable: true);
  var map = <TypeParameter, DartType>{};
  for (int i = 0; i < typeParameters.length; ++i) {
    map[typeParameters[i]] = new TypeParameterType(freshParameters[i]);
    freshParameters[i].bound = substitute(typeParameters[i].bound, map);
  }
  return new FreshTypeParameters(freshParameters, Substitution.fromMap(map));
}

class FreshTypeParameters {
  final List<TypeParameter> freshTypeParameters;
  final Substitution substitution;

  FreshTypeParameters(this.freshTypeParameters, this.substitution);

  FunctionType applyToFunctionType(FunctionType type) => new FunctionType(
      type.positionalParameters.map(substitute).toList(),
      substitute(type.returnType),
      namedParameters: type.namedParameters.map(substituteNamed).toList(),
      typeParameters: freshTypeParameters,
      requiredParameterCount: type.requiredParameterCount,
      positionalParameterNames: type.positionalParameterNames,
      typedefReference: type.typedefReference);

  DartType substitute(DartType type) => substitution.substituteType(type);

  NamedType substituteNamed(NamedType type) =><commit_msg>Fix getFreshTypeParameters' handling of f-bounded types.<commit_after>// Copyright (c) 2016, 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 kernel.type_algebra;

import 'ast.dart';

/// Returns a type where all occurrences of the given type parameters have been
/// replaced with the corresponding types.
///
/// This will copy only the subterms of [type] that contain substituted
/// variables; all other [DartType] objects will be reused.
///
/// In particular, if no variables were substituted, this is guaranteed to
/// return the [type] instance (not a copy), so the caller may use [identical]
/// to efficiently check if a distinct type was created.
DartType substitute(DartType type, Map<TypeParameter, DartType> substitution) {
  if (substitution.isEmpty) return type;
  return Substitution.fromMap(substitution).substituteType(type);
}

/// Returns a mapping from the type parameters declared on the class of [type]
/// to the actual type arguments provided in [type].
///
/// This can be passed as argument to [substitute].
Map<TypeParameter, DartType> getSubstitutionMap(Supertype type) {
  return type.typeArguments.isEmpty
      ? const <TypeParameter, DartType>{}
      : new Map<TypeParameter, DartType>.fromIterables(
          type.classNode.typeParameters, type.typeArguments);
}

Map<TypeParameter, DartType> getUpperBoundSubstitutionMap(Class host) {
  if (host.typeParameters.isEmpty) return const <TypeParameter, DartType>{};
  var result = <TypeParameter, DartType>{};
  for (var parameter in host.typeParameters) {
    result[parameter] = const DynamicType();
  }
  for (var parameter in host.typeParameters) {
    result[parameter] = substitute(parameter.bound, result);
  }
  return result;
}

/// Like [substitute], except when a type in the [substitution] map references
/// another substituted type variable, the mapping for that type is recursively
/// inserted.
///
/// For example `Set<G>` substituted with `{T -> String, G -> List<T>}` results
/// in `Set<List<String>>`.
///
/// Returns `null` if the substitution map contains a cycle reachable from a
/// type variable in [type] (the resulting type would be infinite).
///
/// The [substitution] map will be mutated so that the right-hand sides may
/// be remapped to the deeply substituted type, but only for the keys that are
/// reachable from [type].
///
/// As with [substitute], this is guaranteed to return the same instance if no
/// substitution was performed.
DartType substituteDeep(
    DartType type, Map<TypeParameter, DartType> substitution) {
  if (substitution.isEmpty) return type;
  var substitutor = new _DeepTypeSubstitutor(substitution);
  var result = substitutor.visit(type);
  return substitutor.isInfinite ? null : result;
}

List<DartType> calculateBounds(
    List<TypeParameter> typeParameters, Class object) {
  var refinedBounds = new List<DartType>(typeParameters.length);
  var substitution = <TypeParameter, DartType>{};
  var substitutionToDynamic = <TypeParameter, DartType>{};

  for (int i = 0; i < typeParameters.length; i++) {
    DartType type = typeParameters[i].bound;
    if (type == null || type is InterfaceType && type.classNode == object) {
      type = const DynamicType();
    }

    refinedBounds[i] = type;
    substitution[typeParameters[i]] = type;
    substitutionToDynamic[typeParameters[i]] = const DynamicType();
  }

  var result = new List<DartType>(typeParameters.length);
  for (int i = 0; i < result.length; i++) {
    result[i] = substituteDeep(refinedBounds[i], substitution);
    if (result[i] == null) {
      result[i] = substitute(refinedBounds[i], substitutionToDynamic);
    }
  }
  return result;
}

DartType instantiateToBounds(DartType type, Class object) {
  if (type is InterfaceType) {
    for (var typeArgument in type.typeArguments) {
      // If at least one of the arguments is not dynamic, we assume that the
      // type is not raw and does not need instantiation of its type parameters
      // to their bounds.
      if (typeArgument is! DynamicType) {
        return type;
      }
    }
    return new InterfaceType.byReference(
        type.className, calculateBounds(type.classNode.typeParameters, object));
  }
  if (type is TypedefType) {
    for (var typeArgument in type.typeArguments) {
      if (typeArgument is! DynamicType) {
        return type;
      }
    }
    return new TypedefType.byReference(type.typedefReference,
        calculateBounds(type.typedefNode.typeParameters, object));
  }
  return type;
}

/// Returns true if [type] contains a reference to any of the given [variables].
///
/// It is an error to call this with a [type] that contains a [FunctionType]
/// that declares one of the parameters in [variables].
bool containsTypeVariable(DartType type, Set<TypeParameter> variables) {
  if (variables.isEmpty) return false;
  return new _OccurrenceVisitor(variables).visit(type);
}

/// Given a set of type variables, finds a substitution of those variables such
/// that the two given types becomes equal, or returns `null` if no such
/// substitution exists.
///
/// For example, unifying `List<T>` with `List<String>`, where `T` is a
/// quantified variable, yields the substitution `T = String`.
///
/// If successful, this equation holds:
///
///     substitute(type1, substitution) == substitute(type2, substitution)
///
/// The unification can fail for two reasons:
/// - incompatible types, e.g. `List<T>` cannot be unified with `Set<T>`.
/// - infinite types: e.g. `T` cannot be unified with `List<T>` because it
///   would create the infinite type `List<List<List<...>>>`.
Map<TypeParameter, DartType> unifyTypes(
    DartType type1, DartType type2, Set<TypeParameter> quantifiedVariables) {
  var unifier = new _TypeUnification(type1, type2, quantifiedVariables);
  return unifier.success ? unifier.substitution : null;
}

/// Generates a fresh copy of the given type parameters, with their bounds
/// substituted to reference the new parameters.
///
/// The returned object contains the fresh type parameter list as well as a
/// mapping to be used for replacing other types to use the new type parameters.
FreshTypeParameters getFreshTypeParameters(List<TypeParameter> typeParameters) {
  var freshParameters = new List<TypeParameter>.generate(
      typeParameters.length, (i) => new TypeParameter(typeParameters[i].name),
      growable: true);
  var map = <TypeParameter, DartType>{};
  for (int i = 0; i < typeParameters.length; ++i) {
    map[typeParameters[i]] = new TypeParameterType(freshParameters[i]);
  }
  for (int i = 0; i < typeParameters.length; ++i) {
    freshParameters[i].bound = substitute(typeParameters[i].bound, map);
  }
  return new FreshTypeParameters(freshParameters, Substitution.fromMap(map));
}

class FreshTypeParameters {
  final List<TypeParameter> freshTypeParameters;
  final Substitution substitution;

  FreshTypeParameters(this.freshTypeParameters, this.substitution);

  FunctionType applyToFunctionType(FunctionType type) => new FunctionType(
      type.positionalParameters.map(substitute).toList(),
      substitute(type.returnType),
      namedParameters: type.namedParameters.map(substituteNamed).toList(),
      typeParameters: freshTypeParameters,
      requiredParameterCount: type.requiredParameterCount,
      positionalParameterNames: type.positionalParameterNames,
      typedefReference: type.typedefReference);

  DartType substitute(DartType type) => substitution.substituteType(type);

  NamedType substituteNamed(NamedType type) =>
{'fraction_non_alphanumeric': 0.108868581947275, 'fraction_numerical': 0.001775031227401223, 'mean_word_length': 3.994090610636901, 'pattern_counts': {'":': 0, '<': 76, '<?xml version=': 0, '>': 81, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4018598', 'n_tokens_mistral': 4306, 'n_tokens_neox': 4086, 'n_words': 1484}