pkg/compiler/lib/src/inferrer/types.dart

// Copyright (c) 2012, 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 types;

import 'package:kernel/ast.dart' as ir;
import '../common.dart' show failedAt, retainDataForTesting;
import '../common/metrics.dart' show Metrics;
import '../common/names.dart';
import '../common/tasks.dart' show CompilerTask;
import '../compiler.dart' show Compiler;
import '../elements/entities.dart';
import '../js_backend/inferred_data.dart';
import '../js_model/element_map.dart';
import '../inferrer/type_graph_inferrer.dart' show TypeGraphInferrer;
import '../serialization/serialization.dart';
import '../universe/selector.dart' show Selector;
import '../world.dart' show JClosedWorld;
import 'abstract_value_domain.dart';
import '../inferrer/inferrer_engine.dart';

/// Results about a single element (e.g. a method, parameter, or field)
/// produced by the global type-inference algorithm.
///
/// All queries in this class may contain results that assume whole-program
/// closed-world semantics. Any [TypeMask] for an element or node that we return
/// was inferred to be a "guaranteed type", that means, it is a type that we
/// can prove to be correct for all executions of the program.  A trivial
/// implementation would return false on all boolean properties (giving no
/// guarantees) and the `subclass of Object or null` type mask for the type
/// based queries (the runtime value could be anything).
abstract class GlobalTypeInferenceMemberResult {
  /// Deserializes a [GlobalTypeInferenceMemberResult] object from [source].
  factory GlobalTypeInferenceMemberResult.readFromDataSource(DataSource source,
          ir.Member context, AbstractValueDomain abstractValueDomain) =
      GlobalTypeInferenceMemberResultImpl.readFromDataSource;

  /// Serializes this [GlobalTypeInferenceMemberResult] to [sink].
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain);

  /// The inferred type when this result belongs to a field, null otherwise.
  AbstractValue get type;

  /// Whether the member associated with this result is only called once in one
  /// location in the entire program.
  bool get isCalledOnce;

  /// Whether the method element associated with this result always throws.
  bool get throwsAlways;

  /// The inferred return type when this result belongs to a function element.
  AbstractValue get returnType;

  /// Returns the receiver type of a node that is a property get, set, or method
  /// invocation.
  AbstractValue typeOfReceiver(ir.TreeNode node);

  /// Returns the type of the iterator in a [loop].
  AbstractValue typeOfIterator(ir.TreeNode node);

  /// Returns the type of the `moveNext` call of an iterator in a [loop].
  AbstractValue typeOfIteratorMoveNext(ir.TreeNode node);

  /// Returns the type of the `current` getter of an iterator in a [loop].
  AbstractValue typeOfIteratorCurrent(ir.TreeNode node);
}

/// Internal data used during type-inference to store intermediate results about
/// a single element.
abstract class GlobalTypeInferenceElementData {
  /// Deserializes a [GlobalTypeInferenceElementData] object from [source].
  factory GlobalTypeInferenceElementData.readFromDataSource(DataSource source,
          ir.Member context, AbstractValueDomain abstractValueDomain) =
      KernelGlobalTypeInferenceElementData.readFromDataSource;

  /// Serializes this [GlobalTypeInferenceElementData] to [sink].
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain);

  /// Compresses the inner representation by removing [AbstractValue] mappings
  /// to `null`. Returns the data object itself or `null` if the data object
  /// was empty after compression.
  GlobalTypeInferenceElementData compress();

  // TODO(johnniwinther): Remove this. Maybe split by access/invoke.
  AbstractValue typeOfReceiver(ir.TreeNode node);

  AbstractValue typeOfIterator(ir.TreeNode node);

  AbstractValue typeOfIteratorMoveNext(ir.TreeNode node);

  AbstractValue typeOfIteratorCurrent(ir.TreeNode node);
}

/// API to interact with the global type-inference engine.
abstract class TypesInferrer {
  GlobalTypeInferenceResults analyzeMain(FunctionEntity element);
}

/// Results produced by the global type-inference algorithm.
///
/// All queries in this class may contain results that assume whole-program
/// closed-world semantics. Any [AbstractValue] for an element or node that we
/// return was inferred to be a "guaranteed type", that means, it is a type that
/// we can prove to be correct for all executions of the program.
abstract class GlobalTypeInferenceResults {
  /// Deserializes a [GlobalTypeInferenceResults] object from [source].
  factory GlobalTypeInferenceResults.readFromDataSource(
      DataSource source,
      JsToElementMap elementMap,
      JClosedWorld closedWorld,
      InferredData inferredData) {
    bool isTrivial = source.readBool();
    if (isTrivial) {
      return new TrivialGlobalTypeInferenceResults(closedWorld);
    }
    return new GlobalTypeInferenceResultsImpl.readFromDataSource(
        source, elementMap, closedWorld, inferredData);
  }

  /// Serializes this [GlobalTypeInferenceResults] to [sink].
  void writeToDataSink(DataSink sink, JsToElementMap elementMap);

  JClosedWorld get closedWorld;

  InferredData get inferredData;

  GlobalTypeInferenceMemberResult resultOfMember(MemberEntity member);

  AbstractValue resultOfParameter(Local parameter);

  /// Returns the type of the result of applying [selector] to a receiver with
  /// the given [receiver] type.
  AbstractValue resultTypeOfSelector(Selector selector, AbstractValue receiver);

  /// Returns whether a fixed-length constructor call goes through a growable
  /// check.
  bool isFixedArrayCheckedForGrowable(ir.TreeNode node);

  /// Returns the type of a list new expression [node].  Returns `null` if
  /// [node] does not represent the construction of a new list.
  AbstractValue typeOfNewList(ir.TreeNode node);

  /// Returns the type of a list literal [node].
  AbstractValue typeOfListLiteral(ir.TreeNode node);
}

/// Global analysis that infers concrete types.
class GlobalTypeInferenceTask extends CompilerTask {
  // TODO(sigmund): rename at the same time as our benchmarking tools.
  @override
  final String name = 'Type inference';

  final Compiler compiler;

  /// The [TypeGraphInferrer] used by the global type inference. This should by
  /// accessed from outside this class for testing only.
  TypeGraphInferrer typesInferrerInternal;

  GlobalTypeInferenceResults resultsForTesting;

  Metrics _metrics;

  GlobalTypeInferenceTask(Compiler compiler)
      : compiler = compiler,
        super(compiler.measurer);

  @override
  Metrics get metrics => _metrics;

  /// Runs the global type-inference algorithm once.
  GlobalTypeInferenceResults runGlobalTypeInference(FunctionEntity mainElement,
      JClosedWorld closedWorld, InferredDataBuilder inferredDataBuilder) {
    return measure(() {
      GlobalTypeInferenceResults results;
      if (compiler.disableTypeInference) {
        results = new TrivialGlobalTypeInferenceResults(closedWorld);
        _metrics = Metrics.none();
      } else {
        typesInferrerInternal ??= compiler.backendStrategy
            .createTypesInferrer(closedWorld, inferredDataBuilder);
        results = typesInferrerInternal.analyzeMain(mainElement);
        _metrics = typesInferrerInternal.metrics;
      }
      closedWorld.noSuchMethodData.categorizeComplexImplementations(results);
      if (retainDataForTesting) {
        resultsForTesting = results;
      }
      return results;
    });
  }
}

class GlobalTypeInferenceResultsImpl implements GlobalTypeInferenceResults {
  /// Tag used for identifying serialized [GlobalTypeInferenceResults] objects
  /// in a debugging data stream.
  static const String tag = 'global-type-inference-results';

  @override
  final JClosedWorld closedWorld;
  @override
  final InferredData inferredData;
  final GlobalTypeInferenceMemberResult _deadFieldResult;
  final GlobalTypeInferenceMemberResult _deadMethodResult;
  final AbstractValue _trivialParameterResult;

  final Map<MemberEntity, GlobalTypeInferenceMemberResult> memberResults;
  final Map<Local, AbstractValue> parameterResults;
  final Set<ir.TreeNode> checkedForGrowableLists;
  final Set<Selector> returnsListElementTypeSet;
  final Map<ir.TreeNode, AbstractValue> _allocatedLists;

  GlobalTypeInferenceResultsImpl(
      this.closedWorld,
      this.inferredData,
      this.memberResults,
      this.parameterResults,
      this.checkedForGrowableLists,
      this.returnsListElementTypeSet,
      this._allocatedLists)
      : _deadFieldResult = new DeadFieldGlobalTypeInferenceResult(
            closedWorld.abstractValueDomain),
        _deadMethodResult = new DeadMethodGlobalTypeInferenceResult(
            closedWorld.abstractValueDomain),
        _trivialParameterResult = closedWorld.abstractValueDomain.dynamicType;

  factory GlobalTypeInferenceResultsImpl.readFromDataSource(
      DataSource source,
      JsToElementMap elementMap,
      JClosedWorld closedWorld,
      InferredData inferredData) {
    source.begin(tag);
    Map<MemberEntity, GlobalTypeInferenceMemberResult> memberResults =
        source.readMemberMap((MemberEntity member) =>
            new GlobalTypeInferenceMemberResult.readFromDataSource(
                source,
                elementMap.getMemberContextNode(member),
                closedWorld.abstractValueDomain));
    Map<Local, AbstractValue> parameterResults = source.readLocalMap(() =>
        closedWorld.abstractValueDomain
            .readAbstractValueFromDataSource(source));
    Set<ir.TreeNode> checkedForGrowableLists = source.readTreeNodes().toSet();
    Set<Selector> returnsListElementTypeSet =
        source.readList(() => new Selector.readFromDataSource(source)).toSet();
    Map<ir.TreeNode, AbstractValue> allocatedLists = source.readTreeNodeMap(
        () => closedWorld.abstractValueDomain
            .readAbstractValueFromDataSource(source));
    source.end(tag);
    return new GlobalTypeInferenceResultsImpl(
        closedWorld,
        inferredData,
        memberResults,
        parameterResults,
        checkedForGrowableLists,
        returnsListElementTypeSet,
        allocatedLists);
  }

  @override
  void writeToDataSink(DataSink sink, JsToElementMap elementMap) {
    sink.writeBool(false); // Is _not_ trivial.
    sink.begin(tag);
    sink.writeMemberMap(
        memberResults,
        (MemberEntity member, GlobalTypeInferenceMemberResult result) =>
            result.writeToDataSink(
                sink,
                elementMap.getMemberContextNode(member),
                closedWorld.abstractValueDomain));
    sink.writeLocalMap(
        parameterResults,
        (AbstractValue value) => closedWorld.abstractValueDomain
            .writeAbstractValueToDataSink(sink, value));
    sink.writeTreeNodes(checkedForGrowableLists);
    sink.writeList(returnsListElementTypeSet,
        (Selector selector) => selector.writeToDataSink(sink));
    sink.writeTreeNodeMap(
        _allocatedLists,
        (AbstractValue value) => closedWorld.abstractValueDomain
            .writeAbstractValueToDataSink(sink, value));
    sink.end(tag);
  }

  @override
  GlobalTypeInferenceMemberResult resultOfMember(MemberEntity member) {
    assert(
        member is! ConstructorBodyEntity,
        failedAt(
            member,
            "unexpected input: ConstructorBodyElements are created"
            " after global type inference, no data is avaiable for them."));
    // TODO(sigmund,johnniwinther): Make it an error to query for results that
    // don't exist..
    /*assert(memberResults.containsKey(member) || member is JSignatureMethod,
        "No inference result for member $member");*/
    return memberResults[member] ??
        (member is FunctionEntity ? _deadMethodResult : _deadFieldResult);
  }

  @override
  AbstractValue resultOfParameter(Local parameter) {
    // TODO(sigmund,johnniwinther): Make it an error to query for results that
    // don't exist.
    /*assert(parameterResults.containsKey(parameter),
        "No inference result for parameter $parameter");*/
    return parameterResults[parameter] ?? _trivialParameterResult;
  }

  @override
  AbstractValue resultTypeOfSelector(
      Selector selector, AbstractValue receiver) {
    AbstractValueDomain abstractValueDomain = closedWorld.abstractValueDomain;

    // Bailout for closure calls. We're not tracking types of closures.
    if (selector.isClosureCall) {
      // But if the receiver is not callable, the call will fail.
      if (abstractValueDomain.isEmpty(receiver).isDefinitelyTrue ||
          abstractValueDomain.isNull(receiver).isDefinitelyTrue) {
        return abstractValueDomain.emptyType;
      }
      return abstractValueDomain.dynamicType;
    }
    if (selector.isSetter || selector.isIndexSet) {
      return abstractValueDomain.dynamicType;
    }
    if (returnsListElementType(selector, receiver)) {
      return abstractValueDomain.getContainerElementType(receiver);
    }
    if (returnsMapValueType(selector, receiver)) {
      return abstractValueDomain.getMapValueType(receiver);
    }

    if (closedWorld.includesClosureCall(selector, receiver)) {
      return abstractValueDomain.dynamicType;
    } else {
      Iterable<MemberEntity> elements =
          closedWorld.locateMembers(selector, receiver);
      List<AbstractValue> types = <AbstractValue>[];
      for (MemberEntity element in elements) {
        AbstractValue type = typeOfMemberWithSelector(element, selector);
        types.add(type);
      }
      return abstractValueDomain.unionOfMany(types);
    }
  }

  bool returnsListElementType(Selector selector, AbstractValue mask) {
    return mask != null &&
        closedWorld.abstractValueDomain.isContainer(mask) &&
        returnsListElementTypeSet.contains(selector);
  }

  bool returnsMapValueType(Selector selector, AbstractValue mask) {
    return mask != null &&
        closedWorld.abstractValueDomain.isMap(mask) &&
        selector.isIndex;
  }

  AbstractValue typeOfMemberWithSelector(
      MemberEntity element, Selector selector) {
    if (element.name == Identifiers.noSuchMethod_ &&
        selector.name != element.name) {
      // An invocation can resolve to a [noSuchMethod], in which case
      // we get the return type of [noSuchMethod].
      return resultOfMember(element).returnType;
    } else if (selector.isGetter) {
      if (element.isFunction) {
        // [functionType] is null if the inferrer did not run.
        return closedWorld.abstractValueDomain.functionType;
      } else if (element.isField) {
        return resultOfMember(element).type;
      } else if (element.isGetter) {
        return resultOfMember(element).returnType;
      } else {
        assert(false, failedAt(element, "Unexpected member $element"));
        return closedWorld.abstractValueDomain.dynamicType;
      }
    } else if (element.isGetter || element.isField) {
      assert(selector.isCall || selector.isSetter);
      return closedWorld.abstractValueDomain.dynamicType;
    } else {
      return resultOfMember(element).returnType;
    }
  }

  /// Returns whether a fixed-length constructor call goes through a growable
  /// check.
  // TODO(sigmund): move into the result of the element containing such
  // constructor call.
  @override
  bool isFixedArrayCheckedForGrowable(ir.Node ctorCall) =>
      checkedForGrowableLists.contains(ctorCall);

  @override
  AbstractValue typeOfNewList(ir.Node node) => _allocatedLists[node];

  @override
  AbstractValue typeOfListLiteral(ir.Node node) => _allocatedLists[node];
}

class GlobalTypeInferenceMemberResultImpl
    implements GlobalTypeInferenceMemberResult {
  /// Tag used for identifying serialized [GlobalTypeInferenceMemberResult]
  /// objects in a debugging data stream.
  static const String tag = 'global-type-inference-member-result';

  final GlobalTypeInferenceElementData _data;
  @override
  final AbstractValue returnType;
  @override
  final AbstractValue type;
  @override
  final bool throwsAlways;
  @override
  final bool isCalledOnce;

  GlobalTypeInferenceMemberResultImpl(this._data, this.returnType, this.type,
      {this.throwsAlways, this.isCalledOnce});

  factory GlobalTypeInferenceMemberResultImpl.readFromDataSource(
      DataSource source,
      ir.Member context,
      AbstractValueDomain abstractValueDomain) {
    source.begin(tag);
    GlobalTypeInferenceElementData data = source.readValueOrNull(() {
      return new GlobalTypeInferenceElementData.readFromDataSource(
          source, context, abstractValueDomain);
    });
    AbstractValue returnType =
        abstractValueDomain.readAbstractValueFromDataSource(source);
    AbstractValue type =
        abstractValueDomain.readAbstractValueFromDataSource(source);
    bool throwsAlways = source.readBool();
    bool isCalledOnce = source.readBool();
    source.end(tag);
    return new GlobalTypeInferenceMemberResultImpl(data, returnType, type,
        throwsAlways: throwsAlways, isCalledOnce: isCalledOnce);
  }

  @override
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain) {
    sink.begin(tag);
    sink.writeValueOrNull(_data, (GlobalTypeInferenceElementData data) {
      data.writeToDataSink(sink, context, abstractValueDomain);
    });
    abstractValueDomain.writeAbstractValueToDataSink(sink, returnType);
    abstractValueDomain.writeAbstractValueToDataSink(sink, type);
    sink.writeBool(throwsAlways);
    sink.writeBool(isCalledOnce);
    sink.end(tag);
  }

  @override
  AbstractValue typeOfReceiver(ir.Node node) => _data?.typeOfReceiver(node);
  @override
  AbstractValue typeOfIterator(ir.Node node) => _data?.typeOfIterator(node);
  @override
  AbstractValue typeOfIteratorMoveNext(ir.Node node) =>
      _data?.typeOfIteratorMoveNext(node);
  @override
  AbstractValue typeOfIteratorCurrent(ir.Node node) =>
      _data?.typeOfIteratorCurrent(node);
}

class TrivialGlobalTypeInferenceResults implements GlobalTypeInferenceResults {
  @override
  final JClosedWorld closedWorld;
  final TrivialGlobalTypeInferenceMemberResult _trivialMemberResult;
  final AbstractValue _trivialParameterResult;
  @override
  final InferredData inferredData = new TrivialInferredData();

  TrivialGlobalTypeInferenceResults(this.closedWorld)
      : _trivialMemberResult = new TrivialGlobalTypeInferenceMemberResult(
            closedWorld.abstractValueDomain.dynamicType),
        _trivialParameterResult = closedWorld.abstractValueDomain.dynamicType;

  @override
  void writeToDataSink(DataSink sink, JsToElementMap elementMap) {
    sink.writeBool(true); // Is trivial.
  }

  @override
  bool isFixedArrayCheckedForGrowable(ir.Node node) => false;

  @override
  AbstractValue resultTypeOfSelector(Selector selector, AbstractValue mask) {
    return closedWorld.abstractValueDomain.dynamicType;
  }

  @override
  AbstractValue resultOfParameter(Local parameter) {
    return _trivialParameterResult;
  }

  @override
  GlobalTypeInferenceMemberResult resultOfMember(MemberEntity member) {
    return _trivialMemberResult;
  }

  @override
  AbstractValue typeOfListLiteral(ir.TreeNode node) => null;

  @override
  AbstractValue typeOfNewList(ir.TreeNode node) => null;
}

class TrivialGlobalTypeInferenceMemberResult
    implements GlobalTypeInferenceMemberResult {
  final AbstractValue dynamicType;

  TrivialGlobalTypeInferenceMemberResult(this.dynamicType);

  @override
  AbstractValue get type => dynamicType;

  @override
  AbstractValue get returnType => dynamicType;

  @override
  bool get throwsAlways => false;

  @override
  AbstractValue typeOfIteratorCurrent(ir.Node node) => null;

  @override
  AbstractValue typeOfIteratorMoveNext(ir.Node node) => null;

  @override
  AbstractValue typeOfIterator(ir.Node node) => null;

  @override
  AbstractValue typeOfReceiver(ir.Node node) => null;

  @override
  bool get isCalledOnce => false;

  @override
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain) {
    throw new UnsupportedError(
        "TrivialGlobalTypeInferenceMemberResult.writeToDataSink");
  }
}

class DeadFieldGlobalTypeInferenceResult
    implements GlobalTypeInferenceMemberResult {
  final AbstractValue dynamicType;
  final AbstractValue emptyType;

  DeadFieldGlobalTypeInferenceResult(AbstractValueDomain domain)
      : this.dynamicType = domain.dynamicType,
        this.emptyType = domain.emptyType;

  @override
  AbstractValue get type => emptyType;

  @override
  AbstractValue get returnType => dynamicType;

  @override
  bool get throwsAlways => false;

  @override
  AbstractValue typeOfIteratorCurrent(ir.Node node) => null;

  @override
  AbstractValue typeOfIteratorMoveNext(ir.Node node) => null;

  @override
  AbstractValue typeOfIterator(ir.Node node) => null;

  @override
  AbstractValue typeOfReceiver(ir.Node node) => null;

  @override
  bool get isCalledOnce => false;

  @override
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain) {
    throw new UnsupportedError(
        "DeadFieldGlobalTypeInferenceResult.writeToDataSink");
  }
}

class DeadMethodGlobalTypeInferenceResult
    implements GlobalTypeInferenceMemberResult {
  final AbstractValue emptyType;
  final AbstractValue functionType;

  DeadMethodGlobalTypeInferenceResult(AbstractValueDomain domain)
      : this.functionType = domain.functionType,
        this.emptyType = domain.emptyType;

  @override
  AbstractValue get type => functionType;

  @override
  AbstractValue get returnType => emptyType;

  @override
  bool get throwsAlways => false;

  @override
  AbstractValue typeOfIteratorCurrent(ir.Node node) => null;

  @override
  AbstractValue typeOfIteratorMoveNext(ir.Node node) => null;

  @override
  AbstractValue typeOfIterator(ir.Node node) => null;

  @override
  AbstractValue typeOfReceiver(ir.Node node) => null;

  @override
  bool get isCalledOnce => false;

  @override
  void writeToDataSink(DataSink sink, ir.Member context,
      AbstractValueDomain abstractValueDomain) {
    throw new UnsupportedError(
        "DeadFieldGlobalTypeInferenceResult.writeToDataSink");
  }
}