pkg/kernel/lib/type_propagation/type_propagation.dart

// 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_propagation;

import '../ast.dart';
import '../class_hierarchy.dart';
import '../core_types.dart';
import 'builder.dart';
import 'solver.dart';

/// High-level interface to type propagation.
///
/// This exposes inferred types as [InferredValue], context-insensitively at
/// the level of function boundaries.  The internal analysis results may be
/// more precise but their representation is private to the analysis, and
/// except for diagnostics, clients should only depend on the results exposed
/// by this interface.
//
// TODO(asgerf): Also expose return value of calls.
// TODO(asgerf): Should we expose the value of all expressions?
class TypePropagation {
  final Builder builder;
  final Solver solver;

  TypePropagation(Program program,
      {ClassHierarchy hierarchy, CoreTypes coreTypes})
      : this.withBuilder(
            new Builder(program, hierarchy: hierarchy, coreTypes: coreTypes));

  TypePropagation.withBuilder(Builder builder)
      : this.builder = builder,
        this.solver = new Solver(builder)..solve();

  InferredValue getFieldValue(Field node) {
    int variable = builder.global.fields[node];
    if (variable == null) return null;
    return solver.getValueInferredForVariable(variable);
  }

  InferredValue getReturnValue(FunctionNode node) {
    int variable = builder.global.returns[node];
    if (variable == null) return null;
    return solver.getValueInferredForVariable(variable);
  }

  InferredValue getParameterValue(VariableDeclaration node) {
    int variable = builder.global.parameters[node];
    if (variable == null) return null;
    return solver.getValueInferredForVariable(variable);
  }
}

enum BaseClassKind {
  None,
  Exact,
  Subclass,
  Subtype,
}

/// An abstract value inferred by type propagation.
///
/// Inferred values consist of two parts that each represent a set of values:
/// its base class and its bitmask.  The InferredValue object represents the
/// intersection of these two value sets.
class InferredValue extends Node {
  final Class baseClass;
  final BaseClassKind baseClassKind;

  /// A bitmask of the flags defined in [ValueBit], refining the set of values.
  ///
  /// These bits will always represent a subset of the values allowed by
  /// the base class.  For example, if the base class is "subclass of List",
  /// the bitmask cannot contain [ValueBit.string], as this would contradict the
  /// base class.
  ///
  /// The main use of the bitmask is to track nullability, and to preserve some
  /// particularly important bits of information in case the no useful base
  /// class could be found.
  final int valueBits;

  InferredValue(this.baseClass, this.baseClassKind,
      [this.valueBits = ValueBit.all]) {
    assert(baseClass != null || baseClassKind == BaseClassKind.None);
    assert(baseClass == null || baseClassKind != BaseClassKind.None);
  }

  InferredValue withBitmask(int newBitmask) {
    if (newBitmask == valueBits) return this;
    return new InferredValue(this.baseClass, this.baseClassKind, newBitmask);
  }

  static final InferredValue nothing =
      new InferredValue(null, BaseClassKind.None, 0);

  bool get canBeNull => valueBits & ValueBit.null_ != 0;
  bool get isAlwaysNull => baseClass == null && valueBits == ValueBit.null_;

  /// True if this represents no value at all.
  ///
  /// When this value is inferred for a variable, it implies that the
  /// surrounding code is unreachable.
  bool get isNothing => baseClass == null && valueBits == 0;

  /// True if the value must be null or a concrete instance of [baseClass].
  bool get isExact => baseClassKind == BaseClassKind.Exact;

  /// True if the value must be null or a subclass of [baseClass].
  bool get isSubclass => baseClassKind == BaseClassKind.Subclass;

  /// True if the value must be null or a subtype of [baseClass].
  bool get isSubtype => baseClassKind == BaseClassKind.Subtype;

  accept(Visitor v) => v.visitInferredValue(this);

  visitChildren(Visitor v) {
    baseClass?.acceptReference(v);
  }
}

/// Defines bits representing value sets for use in [InferredValue.valueBits].
///
/// The bitmask defines a partition of the entire value space, so every concrete
/// value corresponds to exactly one value bit.
class ValueBit {
  static const int null_ = 1 << 0;
  static const int integer = 1 << 1;
  static const int double_ = 1 << 2;
  static const int string = 1 << 3;

  /// Bit representing all values other than those above.
  ///
  /// This bit ensures that the bitmask represents a complete partition of the
  /// value space, allowing clients to reason about it as a closed union type.
  ///
  /// For example, if [integer] and [string] are the only bits that are set,
  /// it is safe to conclude that the value can *only* be an integer or string
  /// as all other potential values are ruled out.
  static const int other = 1 << 4;

  static const numberOfBits = 5;
  static const int all = (1 << numberOfBits) - 1;

  static const Map<int, String> names = const <int, String>{
    null_: 'null',
    integer: 'int',
    double_: 'double',
    string: 'string',
    other: 'other',
  };

  static String format(int bitmask) {
    if (bitmask == all) return '{*}';
    List<String> list = <String>[];
    for (int i = 0; i < numberOfBits; ++i) {
      if (bitmask & (1 << i) != 0) {
        list.add(names[1 << i] ?? '?');
      }
    }
    return '{${list.join(",")}}';
  }
}