blob: 8808c681185fd31e58750578cab562a1d4744543 [file] [log] [blame]
// 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 =[node];
if (variable == null) return null;
return solver.getValueInferredForVariable(variable);
InferredValue getReturnValue(FunctionNode node) {
int variable =[node];
if (variable == null) return null;
return solver.getValueInferredForVariable(variable);
InferredValue getParameterValue(VariableDeclaration node) {
int variable =[node];
if (variable == null) return null;
return solver.getValueInferredForVariable(variable);
enum BaseClassKind {
/// 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 Reference baseClassReference;
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(Class baseClass, BaseClassKind baseClassKind,
[int valueBits = ValueBit.all])
: this.byReference(baseClass?.reference, baseClassKind, valueBits);
this.baseClassReference, this.baseClassKind, this.valueBits) {
assert(baseClass != null || baseClassKind == BaseClassKind.None);
assert(baseClass == null || baseClassKind != BaseClassKind.None);
Class get baseClass => baseClassReference?.asClass;
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) {
/// 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(",")}}';