pkg/vm/lib/bytecode/recursive_types_validator.dart

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

library vm.bytecode.recursive_types_validator;

import 'package:kernel/ast.dart' hide MapEntry;
import 'package:kernel/type_algebra.dart' show Substitution;

import 'generics.dart'
    show flattenInstantiatorTypeArguments, hasFreeTypeParameters;

/// Detect recursive types and validates that finalized (flattened)
/// representation of generic types is valid (finite).
class RecursiveTypesValidator {
  final Set<DartType> _validatedTypes = <DartType>{};
  final Set<DartType> _recursiveTypes = <DartType>{};
  final Set<Class> _validatedClases = <Class>{};

  /// Validates [type].
  void validateType(DartType type) {
    if (!isValidated(type)) {
      final visitor = new _RecursiveTypesVisitor(this);
      visitor.visit(type);
      _validatedTypes.addAll(visitor.validated);
      _recursiveTypes.addAll(visitor.recursive);
    }
  }

  bool isValidated(DartType type) => _validatedTypes.contains(type);

  /// Returns true if [type] is recursive.
  /// Should be called only after validating [type].
  bool isRecursive(DartType type) {
    assert(isValidated(type));
    return _recursiveTypes.contains(type);
  }

  void validateClass(Class cls) {
    if (_validatedClases.add(cls)) {
      try {
        validateType(cls.thisType);
      } on IllegalRecursiveTypeException catch (e) {
        _validatedClases.remove(cls);
        throw e;
      }
    }
  }
}

class IllegalRecursiveTypeException {
  final DartType type;
  IllegalRecursiveTypeException(this.type);
}

class _RecursiveTypesVisitor extends DartTypeVisitor<void> {
  final RecursiveTypesValidator validator;
  final Set<DartType> validated = <DartType>{};
  final Set<DartType> recursive = <DartType>{};
  final Set<DartType> _visited = new Set<DartType>();
  final List<DartType> _stack = <DartType>[];

  _RecursiveTypesVisitor(this.validator);

  void visit(DartType type) {
    if (validator.isValidated(type)) {
      return;
    }

    if (!_visited.add(type)) {
      final int start = _stack.lastIndexOf(type);
      _verifyRecursiveType(start, type);
      for (int i = start; i < _stack.length; ++i) {
        recursive.add(_stack[i]);
      }
      return;
    }

    _stack.add(type);

    type.accept(this);

    _stack.removeLast();
    _visited.remove(type);

    validated.add(type);
  }

  @override
  void defaultDartType(DartType node) =>
      throw 'Unexpected type ${node.runtimeType} $node';

  @override
  void visitInvalidType(InvalidType node) {}

  @override
  void visitDynamicType(DynamicType node) {}

  @override
  void visitVoidType(VoidType node) {}

  @override
  void visitBottomType(BottomType node) {}

  @override
  void visitTypeParameterType(TypeParameterType node) {}

  @override
  void visitInterfaceType(InterfaceType node) {
    // Validate class declaration type separately
    // to avoid failures due to types in the current _stack.
    validator.validateClass(node.classNode);

    for (var typeArg in node.typeArguments) {
      visit(typeArg);
    }
    final flatTypeArgs =
        flattenInstantiatorTypeArguments(node.classNode, node.typeArguments);
    for (var typeArg in flatTypeArgs.getRange(
        0, flatTypeArgs.length - node.typeArguments.length)) {
      visit(typeArg);
    }
  }

  @override
  void visitTypedefType(TypedefType node) => visit(node.unalias);

  @override
  void visitFunctionType(FunctionType node) {
    for (var p in node.positionalParameters) {
      visit(p);
    }
    for (var p in node.namedParameters) {
      visit(p.type);
    }
    visit(node.returnType);
  }

  void _verifyRecursiveType(int start, DartType type) {
    if (type is InterfaceType) {
      if (!hasFreeTypeParameters(type.typeArguments)) {
        return;
      }

      for (int i = start + 1; i < _stack.length; ++i) {
        final other = _stack[i];
        if (other is InterfaceType &&
            other.classNode == type.classNode &&
            hasFreeTypeParameters(other.typeArguments)) {
          if (!listEquals(_eraseTypeParameters(type.typeArguments),
              _eraseTypeParameters(other.typeArguments))) {
            throw IllegalRecursiveTypeException(type);
          }
        }
      }
    } else {
      throw 'Unexpected recursive type ${type.runtimeType} $type';
    }
  }

  List<DartType> _eraseTypeParameters(List<DartType> typeArgs) {
    return typeArgs
        .map((DartType t) =>
            const _EraseTypeParametersToDynamic().substituteType(t))
        .toList();
  }
}

class _EraseTypeParametersToDynamic extends Substitution {
  const _EraseTypeParametersToDynamic();

  DartType getSubstitute(TypeParameter parameter, bool upperBound) {
    return const DynamicType();
  }
}