sdk/lib/_internal/compiler/implementation/universe/function_set.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.

part of universe;

// TODO(kasperl): This actually holds getters and setters just fine
// too and stricly they aren't functions. Maybe this needs a better
// name -- something like ElementSet seems a bit too generic.
class FunctionSet {
  final Compiler compiler;
  final Map<SourceString, FunctionSetNode> nodes =
      new Map<SourceString, FunctionSetNode>();
  FunctionSet(this.compiler);

  FunctionSetNode newNode(SourceString name)
      => new FunctionSetNode(name);

  void add(Element element) {
    assert(element.isInstanceMember());
    assert(!element.isAbstract(compiler));
    SourceString name = element.name;
    FunctionSetNode node = nodes.putIfAbsent(name, () => newNode(name));
    node.add(element);
  }

  void remove(Element element) {
    assert(element.isInstanceMember());
    assert(!element.isAbstract(compiler));
    SourceString name = element.name;
    FunctionSetNode node = nodes[name];
    if (node != null) {
      node.remove(element);
    }
  }

  bool contains(Element element) {
    assert(element.isInstanceMember());
    assert(!element.isAbstract(compiler));
    SourceString name = element.name;
    FunctionSetNode node = nodes[name];
    return (node != null)
        ? node.contains(element)
        : false;
  }

  /**
   * Returns an object that allows iterating over all the functions
   * that may be invoked with the given [selector].
   */
  Iterable<Element> filter(Selector selector) {
    return query(selector).functions;
  }

  TypeMask receiverType(Selector selector) {
    return query(selector).computeMask(compiler);
  }

  FunctionSetQuery query(Selector selector) {
    SourceString name = selector.name;
    FunctionSetNode node = nodes[name];
    FunctionSetNode noSuchMethods = nodes[Compiler.NO_SUCH_METHOD];
    if (node != null) {
      return node.query(selector, compiler, noSuchMethods);
    }
    // If there is no method that matches [selector] we know we can
    // only hit [:noSuchMethod:].
    if (noSuchMethods == null) return const FunctionSetQuery(const <Element>[]);
    selector = (selector.mask == null)
        ? compiler.noSuchMethodSelector
        : new TypedSelector(selector.mask, compiler.noSuchMethodSelector);

    return noSuchMethods.query(selector, compiler, null);
  }

  void forEach(Function action) {
    nodes.forEach((SourceString name, FunctionSetNode node) {
      node.forEach(action);
    });
  }
}


class FunctionSetNode {
  final SourceString name;
  final Map<Selector, FunctionSetQuery> cache =
      new Map<Selector, FunctionSetQuery>();

  // Initially, we keep the elements in a list because it is more
  // compact than a hash set. Once we get enough elements, we change
  // the representation to be a set to get faster contains checks.
  static const int MAX_ELEMENTS_IN_LIST = 8;
  var elements = <Element>[];
  bool isList = true;

  FunctionSetNode(this.name);

  void add(Element element) {
    assert(element.name == name);
    // We try to avoid clearing the cache unless we have to. For that
    // reason we keep the explicit contains check even though the add
    // method ends up doing the work again (for sets).
    if (!elements.contains(element)) {
      if (isList && elements.length >= MAX_ELEMENTS_IN_LIST) {
        elements = elements.toSet();
        isList = false;
      }
      elements.add(element);
      if (!cache.isEmpty) cache.clear();
    }
  }

  void remove(Element element) {
    assert(element.name == name);
    if (isList) {
      List list = elements;
      int index = list.indexOf(element);
      if (index < 0) return;
      Element last = list.removeLast();
      if (index != list.length) {
        list[index] = last;
      }
      if (!cache.isEmpty) cache.clear();
    } else {
      Set set = elements;
      if (set.remove(element)) {
        // To avoid wobbling between the two representations, we do
        // not transition back to the list representation even if we
        // end up with few enough elements at this point.
        if (!cache.isEmpty) cache.clear();
      }
    }
  }

  bool contains(Element element) {
    assert(element.name == name);
    return elements.contains(element);
  }

  void forEach(Function action) {
    elements.forEach(action);
  }

  TypeMask getNonNullTypeMaskOfSelector(Selector selector, Compiler compiler) {
    // TODO(ngeoffray): We should probably change untyped selector
    // to always be a subclass of Object.
    return selector.mask != null
        ? selector.mask
        : new TypeMask.subclass(compiler.objectClass.rawType);
    }

  FunctionSetQuery query(Selector selector,
                         Compiler compiler,
                         FunctionSetNode noSuchMethods) {
    assert(selector.name == name);
    FunctionSetQuery result = cache[selector];
    if (result != null) return result;
    Set<Element> functions;
    for (Element element in elements) {
      if (selector.appliesUnnamed(element, compiler)) {
        if (functions == null) {
          // Defer the allocation of the functions set until we are
          // sure we need it. This allows us to return immutable empty
          // lists when the filtering produced no results.
          functions = new Set<Element>();
        }
        functions.add(element);
      }
    }

    TypeMask mask = getNonNullTypeMaskOfSelector(selector, compiler);
    // If we cannot ensure a method will be found at runtime, we also
    // add [noSuchMethod] implementations that apply to [mask] as
    // potential targets.
    if (noSuchMethods != null
        && mask.needsNoSuchMethodHandling(selector, compiler)) {
      FunctionSetQuery noSuchMethodQuery = noSuchMethods.query(
          new TypedSelector(mask, compiler.noSuchMethodSelector),
          compiler,
          null);
      if (!noSuchMethodQuery.functions.isEmpty) {
        if (functions == null) {
          functions = new Set<Element>.from(noSuchMethodQuery.functions);
        } else {
          functions.addAll(noSuchMethodQuery.functions);
        }
      }
    }
    cache[selector] = result = (functions != null)
        ? newQuery(functions, selector, compiler)
        : const FunctionSetQuery(const <Element>[]);
    return result;
  }

  FunctionSetQuery newQuery(Iterable<Element> functions,
                            Selector selector,
                            Compiler compiler) {
    return new FullFunctionSetQuery(functions);
  }
}

class FunctionSetQuery {
  final Iterable<Element> functions;
  TypeMask computeMask(Compiler compiler) => const TypeMask.nonNullEmpty();
  const FunctionSetQuery(this.functions);
}

class FullFunctionSetQuery extends FunctionSetQuery {
  TypeMask _mask;

  /**
   * Compute the type of all potential receivers of this function set.
   */
  TypeMask computeMask(Compiler compiler) {
    if (_mask != null) return _mask;
    return _mask = new TypeMask.unionOf(functions
        .expand((element) {
          ClassElement cls = element.getEnclosingClass();
          return compiler.world.isUsedAsMixin(cls)
              ? ([cls]..addAll(compiler.world.mixinUses[cls]))
              : [cls];
        })
        .map((cls) {
          if (compiler.backend.isNullImplementation(cls)) {
            return const TypeMask.empty();
          }
          return compiler.world.hasSubclasses(cls)
              ? new TypeMask.nonNullSubclass(cls.rawType)
              : new TypeMask.nonNullExact(cls.rawType);
        }),
        compiler);
  }

  FullFunctionSetQuery(functions) : super(functions);
}