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

// Copyright (c) 2013, 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 locals_handler;

import 'dart:collection' show IterableMixin;
import 'package:kernel/ast.dart' as ir;
import '../elements/entities.dart';
import '../elements/types.dart';
import '../ir/util.dart';
import '../util/util.dart';
import 'inferrer_engine.dart';
import 'type_graph_nodes.dart';

/// A variable scope holds types for variables. It has a link to a
/// parent scope, but never changes the types in that parent. Instead,
/// updates to locals of a parent scope are put in the current scope.
/// The inferrer makes sure updates get merged into the parent scope,
/// once the control flow block has been visited.
class VariableScope {
  /// The number of parent scopes of this scope.
  ///
  /// This is used for computing common parents efficiently.
  final int _level;

  Map<Local, TypeInformation> variables;

  /// The parent of this scope. Null for the root scope.
  final VariableScope parent;

  /// The [ir.Node] that created this scope.
  final ir.Node tryBlock;

  final VariableScope copyOf;

  VariableScope({this.parent})
      : this.variables = null,
        this.copyOf = null,
        this.tryBlock = null,
        _level = (parent?._level ?? -1) + 1;

  VariableScope.tryBlock(this.tryBlock, {this.parent})
      : this.variables = null,
        this.copyOf = null,
        _level = (parent?._level ?? -1) + 1 {
    assert(tryBlock is ir.TryCatch || tryBlock is ir.TryFinally,
        "Unexpected block $tryBlock for VariableScope.tryBlock");
  }

  VariableScope.deepCopyOf(VariableScope other)
      : variables = other.variables == null
            ? null
            : new Map<Local, TypeInformation>.from(other.variables),
        tryBlock = other.tryBlock,
        copyOf = other.copyOf ?? other,
        _level = other._level,
        parent = other.parent == null
            ? null
            : new VariableScope.deepCopyOf(other.parent);

  /// `true` if this scope is for a try block.
  bool get isTry => tryBlock != null;

  /// Returns the [VariableScope] that defines the identity of this scope.
  ///
  /// If this scope is a copy of another scope, the identity is the identity
  /// of the other scope, otherwise the identity is the scope itself.
  VariableScope get identity => copyOf ?? this;

  /// Returns the common parent between this and [other] based on [identity].
  VariableScope commonParent(VariableScope other) {
    if (identity == other.identity) {
      return identity;
    } else if (_level > other._level) {
      return parent.commonParent(other);
    } else if (_level < other._level) {
      return commonParent(other.parent);
    } else if (_level > 0) {
      return parent.commonParent(other.parent);
    } else {
      return null;
    }
  }

  TypeInformation operator [](Local variable) {
    TypeInformation result;
    if (variables == null || (result = variables[variable]) == null) {
      return parent == null ? null : parent[variable];
    }
    return result;
  }

  void operator []=(Local variable, TypeInformation mask) {
    assert(mask != null);
    if (variables == null) {
      variables = new Map<Local, TypeInformation>();
    }
    variables[variable] = mask;
  }

  /// Calls [f] for all variables in this and parent scopes until and including
  /// [scope]. [f] is called at most once for each variable.
  void forEachLocalUntilScope(
      VariableScope scope, void f(Local variable, TypeInformation type)) {
    _forEachLocalUntilScope(scope, f, new Setlet<Local>(), this);
  }

  void _forEachLocalUntilScope(
      VariableScope scope,
      void f(Local variable, TypeInformation type),
      Setlet<Local> seenLocals,
      VariableScope origin) {
    if (variables != null) {
      variables.forEach((variable, type) {
        if (seenLocals.contains(variable)) return;
        seenLocals.add(variable);
        f(variable, type);
      });
    }
    if (scope?.identity == identity) {
      return;
    }
    if (parent != null) {
      parent._forEachLocalUntilScope(scope, f, seenLocals, origin);
    } else {
      assert(
          scope == null,
          "Scope not found: \n"
          "origin=${origin.toStructuredText('')}\n"
          "scope=${scope.toStructuredText('')}");
    }
  }

  void forEachLocal(void f(Local variable, TypeInformation type)) {
    forEachLocalUntilScope(null, f);
  }

  bool updates(Local variable) {
    if (variables == null) return false;
    return variables.containsKey(variable);
  }

  String toStructuredText(String indent) {
    StringBuffer sb = new StringBuffer();
    _toStructuredText(sb, indent);
    return sb.toString();
  }

  void _toStructuredText(StringBuffer sb, String indent) {
    sb.write('VariableScope($hashCode) [');
    sb.write('\n${indent}  level:$_level');
    if (copyOf != null) {
      sb.write('\n${indent}  copyOf:VariableScope(${copyOf.hashCode})');
    }
    if (tryBlock != null) {
      sb.write('\n${indent}  tryBlock: ${nodeToDebugString(tryBlock)}');
    }
    if (variables != null) {
      sb.write('\n${indent}  variables:');
      variables.forEach((Local local, TypeInformation type) {
        sb.write('\n${indent}    $local: ');
        sb.write(type.toStructuredText('${indent}      '));
      });
    }
    if (parent != null) {
      sb.write('\n${indent}  parent:');
      parent._toStructuredText(sb, '${indent}     ');
    }
    sb.write(']');
  }

  @override
  String toString() {
    String rest = parent == null ? "null" : parent.toString();
    return '{$variables} $rest';
  }
}

/// Tracks initializers via initializations and assignments.
class FieldInitializationScope {
  Map<FieldEntity, TypeInformation> fields;
  bool isThisExposed;

  /// `true` when control flow prevents accumulating definite assignments,
  /// e.g. an early return or caught exception.
  bool isIndefinite;

  FieldInitializationScope()
      : isThisExposed = false,
        isIndefinite = false;

  FieldInitializationScope.internalFrom(FieldInitializationScope other)
      : isThisExposed = other.isThisExposed,
        isIndefinite = other.isIndefinite;

  factory FieldInitializationScope.from(FieldInitializationScope other) {
    if (other == null) return null;
    return new FieldInitializationScope.internalFrom(other);
  }

  void updateField(FieldEntity field, TypeInformation type) {
    if (isThisExposed) return;
    if (isIndefinite) return;
    fields ??= new Map<FieldEntity, TypeInformation>();
    fields[field] = type;
  }

  TypeInformation readField(FieldEntity field) {
    return fields == null ? null : fields[field];
  }

  void forEach(void f(FieldEntity element, TypeInformation type)) {
    fields?.forEach(f);
  }

  /// Returns the join between [thenScope] and [elseScope] which models the
  /// flow through either [thenScope] or [elseScope].
  FieldInitializationScope mergeDiamondFlow(InferrerEngine inferrer,
      FieldInitializationScope thenScope, FieldInitializationScope elseScope) {
    assert(elseScope != null);

    // Quick bailout check. If [isThisExposed] or [isIndefinite] is true, we
    // know the code following won'TypeInformation do anything.
    if (isThisExposed) return this;
    if (isIndefinite) return this;

    FieldInitializationScope otherScope =
        elseScope.fields == null ? this : elseScope;

    thenScope.forEach((FieldEntity field, TypeInformation type) {
      TypeInformation otherType = otherScope.readField(field);
      if (otherType == null) return;
      updateField(field, inferrer.types.allocateDiamondPhi(type, otherType));
    });

    isThisExposed = thenScope.isThisExposed || elseScope.isThisExposed;
    isIndefinite = thenScope.isIndefinite || elseScope.isIndefinite;
    return this;
  }
}

/// Placeholder for inferred arguments types on sends.
class ArgumentsTypes extends IterableMixin<TypeInformation> {
  final List<TypeInformation> positional;
  final Map<String, TypeInformation> named;
  ArgumentsTypes(this.positional, named)
      : this.named = (named == null || named.isEmpty) ? const {} : named {
    assert(this.positional.every((TypeInformation type) => type != null));
    assert(this.named.values.every((TypeInformation type) => type != null));
  }

  ArgumentsTypes.empty()
      : positional = const [],
        named = const {};

  @override
  int get length => positional.length + named.length;

  @override
  Iterator<TypeInformation> get iterator => new ArgumentsTypesIterator(this);

  @override
  String toString() => "{ positional = $positional, named = $named }";

  @override
  bool operator ==(other) {
    if (positional.length != other.positional.length) return false;
    if (named.length != other.named.length) return false;
    for (int i = 0; i < positional.length; i++) {
      if (positional[i] != other.positional[i]) return false;
    }
    var result = true;
    named.forEach((name, type) {
      if (other.named[name] != type) result = false;
    });
    return result;
  }

  @override
  int get hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode');

  bool hasNoArguments() => positional.isEmpty && named.isEmpty;

  @override
  void forEach(void f(TypeInformation type)) {
    positional.forEach(f);
    named.values.forEach(f);
  }

  @override
  bool every(bool f(TypeInformation type)) {
    return positional.every(f) && named.values.every(f);
  }

  @override
  bool contains(Object type) {
    return positional.contains(type) || named.containsValue(type);
  }
}

class ArgumentsTypesIterator implements Iterator<TypeInformation> {
  final Iterator<TypeInformation> positional;
  final Iterator<TypeInformation> named;
  bool _iteratePositional = true;

  ArgumentsTypesIterator(ArgumentsTypes iteratee)
      : positional = iteratee.positional.iterator,
        named = iteratee.named.values.iterator;

  Iterator<TypeInformation> get _currentIterator =>
      _iteratePositional ? positional : named;

  @override
  TypeInformation get current => _currentIterator.current;

  @override
  bool moveNext() {
    if (_iteratePositional && positional.moveNext()) {
      return true;
    }
    _iteratePositional = false;
    return named.moveNext();
  }
}

/// Placeholder for inferred types of local variables.
class LocalsHandler {
  final VariableScope _locals;

  LocalsHandler() : _locals = new VariableScope();

  LocalsHandler.from(LocalsHandler other)
      : _locals = new VariableScope(parent: other._locals);

  LocalsHandler.tryBlock(LocalsHandler other, ir.TreeNode block)
      : _locals = new VariableScope.tryBlock(block, parent: other._locals);

  LocalsHandler.deepCopyOf(LocalsHandler other)
      : _locals = new VariableScope.deepCopyOf(other._locals);

  TypeInformation use(InferrerEngine inferrer, Local local) {
    return _locals[local];
  }

  void update(InferrerEngine inferrer, Local local, TypeInformation type,
      ir.Node node, DartType staticType, LocalsHandler tryBlock) {
    if (tryBlock != null) {
      // We don't know if an assignment in a try block
      // will be executed, so all assignments in that block are
      // potential types after we have left it. We update the parent
      // of the try block so that, at exit of the try block, we get
      // the right phi for it.
      TypeInformation existing = tryBlock._locals.parent[local];
      if (existing != null) {
        TypeInformation phiType = inferrer.types.allocatePhi(
            tryBlock._locals.tryBlock, local, existing,
            isTry: tryBlock._locals.isTry);
        TypeInformation inputType =
            inferrer.types.addPhiInput(local, phiType, type);
        tryBlock._locals.parent[local] = inputType;
      }
      // Update the current handler unconditionally with the new
      // type.
      _locals[local] = type;
    } else {
      _locals[local] = type;
    }
  }

  /// Returns the join between this locals handler and [other] which models the
  /// flow through either this or [other].
  ///
  /// If [inPlace] is `true`, the variable types in this locals handler are
  /// replaced by the variables types in [other]. Otherwise the variable types
  /// from both are merged with a phi type.
  LocalsHandler mergeFlow(InferrerEngine inferrer, LocalsHandler other,
      {bool inPlace: false}) {
    VariableScope common = _locals.commonParent(other._locals);
    assert(
        common != null,
        "No common parent for\n"
        "1:${_locals.toStructuredText('  ')}\n"
        "2:${other._locals.toStructuredText('  ')}");
    assert(
        common == _locals || _locals.variables == null,
        "Non-empty common parent for\n"
        "1:${common.toStructuredText('  ')}\n"
        "2:${_locals.toStructuredText('  ')}");
    other._locals.forEachLocalUntilScope(common,
        (Local local, TypeInformation type) {
      TypeInformation myType = _locals[local];
      if (myType == null) return; // Variable is only defined in [other].
      if (type == myType) return;
      _locals[local] =
          inPlace ? type : inferrer.types.allocateDiamondPhi(myType, type);
    });
    return this;
  }

  /// Returns the join between [thenBranch] and [elseBranch] which models the
  /// flow through either [thenBranch] or [elseBranch].
  LocalsHandler mergeDiamondFlow(InferrerEngine inferrer,
      LocalsHandler thenBranch, LocalsHandler elseBranch) {
    assert(elseBranch != null);

    void mergeLocal(Local local) {
      TypeInformation myType = _locals[local];
      if (myType == null) return;
      TypeInformation elseType = elseBranch._locals[local];
      TypeInformation thenType = thenBranch._locals[local];
      if (thenType == elseType) {
        _locals[local] = thenType;
      } else {
        _locals[local] = inferrer.types.allocateDiamondPhi(thenType, elseType);
      }
    }

    VariableScope common = _locals.commonParent(thenBranch._locals);
    assert(
        common != null,
        "No common parent for\n"
        "1:${_locals.toStructuredText('  ')}\n"
        "2:${thenBranch._locals.toStructuredText('  ')}");
    assert(
        _locals.commonParent(elseBranch._locals) == common,
        "Diff common parent for\n"
        "1:${common.toStructuredText('  ')}\n2:"
        "${_locals.commonParent(elseBranch._locals)?.toStructuredText('  ')}");
    assert(
        common == _locals || _locals.variables == null,
        "Non-empty common parent for\n"
        "common:${common.toStructuredText('  ')}\n"
        "1:${_locals.toStructuredText('  ')}\n"
        "2:${thenBranch._locals.toStructuredText('  ')}");
    thenBranch._locals.forEachLocalUntilScope(common, (Local local, _) {
      mergeLocal(local);
    });
    elseBranch._locals.forEachLocalUntilScope(common, (Local local, _) {
      // Discard locals we already processed when iterating over
      // [thenBranch]'s locals.
      if (!thenBranch._locals.updates(local)) mergeLocal(local);
    });
    return this;
  }

  /// Merge all [LocalsHandler] in [handlers] into [:this:].
  ///
  /// If [keepOwnLocals] is true, the types of locals in this
  /// [LocalsHandler] are being used in the merge. [keepOwnLocals]
  /// should be true if this [LocalsHandler], the dominator of
  /// all [handlers], also directly flows into the join point,
  /// that is the code after all [handlers]. For example, consider:
  ///
  /// [: switch (...) {
  ///      case 1: ...; break;
  ///    }
  /// :]
  ///
  /// The [LocalsHandler] at entry of the switch also flows into the
  /// exit of the switch, because there is no default case. So the
  /// types of locals at entry of the switch have to take part to the
  /// merge.
  ///
  /// The above situation is also true for labeled statements like
  ///
  /// [: L: {
  ///      if (...) break;
  ///      ...
  ///    }
  /// :]
  ///
  /// where [:this:] is the [LocalsHandler] for the paths through the
  /// labeled statement that do not break out.
  LocalsHandler mergeAfterBreaks(
      InferrerEngine inferrer, Iterable<LocalsHandler> handlers,
      {bool keepOwnLocals: true}) {
    ir.Node tryBlock = _locals.tryBlock;
    // Use a separate locals handler to perform the merge in, so that Phi
    // creation does not invalidate previous type knowledge while we might
    // still look it up.
    VariableScope merged = tryBlock != null
        ? new VariableScope.tryBlock(tryBlock, parent: _locals)
        : new VariableScope(parent: _locals);
    Set<Local> seenLocals = new Setlet<Local>();
    // Merge all other handlers.
    for (LocalsHandler handler in handlers) {
      VariableScope common = _locals.commonParent(handler._locals);
      assert(
          common != null,
          "No common parent for\n"
          "1:${_locals.toStructuredText('  ')}\n"
          "2:${handler._locals.toStructuredText('  ')}");
      assert(
          common == _locals || _locals.variables == null,
          "Non-empty common parent for\n"
          "common:${common.toStructuredText('  ')}\n"
          "1:${_locals.toStructuredText('  ')}\n"
          "2:${handler._locals.toStructuredText('  ')}");
      handler._locals.forEachLocalUntilScope(common, (local, otherType) {
        TypeInformation myType = merged[local];
        if (myType == null) return;
        TypeInformation newType;
        if (!seenLocals.contains(local)) {
          newType = inferrer.types.allocatePhi(
              merged.tryBlock, local, otherType,
              isTry: merged.isTry);
          seenLocals.add(local);
        } else {
          newType = inferrer.types.addPhiInput(local, myType, otherType);
        }
        if (newType != myType) {
          merged[local] = newType;
        }
      });
    }
    // If we want to keep own locals, we merge [seenLocals] from [this] into
    // [merged] to update the Phi nodes with original values.
    if (keepOwnLocals) {
      for (Local variable in seenLocals) {
        TypeInformation originalType = _locals[variable];
        if (originalType != null) {
          merged[variable] = inferrer.types
              .addPhiInput(variable, merged[variable], originalType);
        }
      }
    }
    // Clean up Phi nodes with single input and store back result into
    // actual locals handler.
    merged.forEachLocalUntilScope(merged,
        (Local variable, TypeInformation type) {
      _locals[variable] = inferrer.types.simplifyPhi(tryBlock, variable, type);
    });
    return this;
  }

  /// Merge all [LocalsHandler] in [handlers] into this handler.
  /// Returns whether a local in this handler has changed.
  bool mergeAll(InferrerEngine inferrer, Iterable<LocalsHandler> handlers) {
    bool changed = false;
    handlers.forEach((LocalsHandler other) {
      VariableScope common = _locals.commonParent(other._locals);
      assert(
          common != null,
          "No common parent for\n"
          "1:${_locals.toStructuredText('  ')}\n"
          "2:${other._locals.toStructuredText('  ')}");
      assert(
          common == _locals || _locals.variables == null,
          "Non-empty common parent for\n"
          "common:${common.toStructuredText('  ')}\n"
          "1:${_locals.toStructuredText('  ')}\n"
          "2:${other._locals.toStructuredText('  ')}");
      other._locals.forEachLocalUntilScope(common, (local, otherType) {
        TypeInformation myType = _locals[local];
        if (myType == null) return;
        TypeInformation newType =
            inferrer.types.addPhiInput(local, myType, otherType);
        if (newType != myType) {
          changed = true;
          _locals[local] = newType;
        }
      });
    });
    return changed;
  }

  void startLoop(InferrerEngine inferrer, ir.Node loop) {
    _locals.forEachLocal((Local variable, TypeInformation type) {
      TypeInformation newType =
          inferrer.types.allocateLoopPhi(loop, variable, type, isTry: false);
      if (newType != type) {
        _locals[variable] = newType;
      }
    });
  }

  void endLoop(InferrerEngine inferrer, ir.Node loop) {
    _locals.forEachLocal((Local variable, TypeInformation type) {
      TypeInformation newType =
          inferrer.types.simplifyPhi(loop, variable, type);
      if (newType != type) {
        _locals[variable] = newType;
      }
    });
  }

  String toStructuredText(String indent) {
    StringBuffer sb = new StringBuffer();
    _toStructuredText(sb, indent);
    return sb.toString();
  }

  void _toStructuredText(StringBuffer sb, String indent) {
    sb.write('LocalsHandler($hashCode) [');
    sb.write('\n${indent}  locals:');
    _locals._toStructuredText(sb, '${indent}    ');
    sb.write('\n]');
  }

  @override
  String toString() {
    StringBuffer sb = new StringBuffer();
    sb.write('LocalsHandler(');
    sb.write('locals=$_locals');
    sb.write(')');
    return sb.toString();
  }
}