| // 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. |
| |
| package com.google.dart.compiler.resolver; |
| |
| import com.google.common.annotations.VisibleForTesting; |
| import com.google.dart.compiler.ast.DartNode; |
| import com.google.dart.compiler.ast.DartObsoleteMetadata; |
| import com.google.dart.compiler.ast.Modifiers; |
| import com.google.dart.compiler.common.SourceInfo; |
| import com.google.dart.compiler.type.Type; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| |
| /** |
| * A more efficient version of {@link com.google.common.collect.Multimap} specifically for |
| * {@link NodeElement} |
| */ |
| @VisibleForTesting |
| public class ElementMap { |
| |
| /** |
| * A synthetic place holder for an element where the name given to the element map does not match |
| * the value returned by {@link NodeElement#getName()} or where there are multiple elements associated |
| * with the same name. |
| */ |
| static class ElementHolder implements NodeElement { |
| private static final String INTERNAL_ONLY_ERROR = |
| "ElementHolder should not be accessed outside this class"; |
| |
| final String name; |
| final NodeElement element; |
| ElementHolder nextHolder; |
| |
| ElementHolder(String name, NodeElement element) { |
| this.name = name; |
| this.element = element; |
| } |
| |
| @Override |
| public SourceInfo getNameLocation() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public EnclosingElement getEnclosingElement() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public ElementKind getKind() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public DartObsoleteMetadata getMetadata() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public Modifiers getModifiers() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public String getName() { |
| return name; |
| } |
| |
| @Override |
| public DartNode getNode() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public String getOriginalName() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public Type getType() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public boolean isDynamic() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| @Override |
| public SourceInfo getSourceInfo() { |
| throw new AssertionError(INTERNAL_ONLY_ERROR); |
| } |
| |
| } |
| |
| // Array indexed by hashed name ... length is always power of 2 |
| private NodeElement[] elements; |
| private List<NodeElement> ordered = new ArrayList<NodeElement>(); |
| |
| @VisibleForTesting |
| public ElementMap() { |
| clear(); |
| } |
| |
| /** |
| * Associate the specified element with the specified name. If the element is already associated |
| * with that name, do not associate it again. |
| */ |
| @VisibleForTesting |
| public void add(String name, NodeElement element) { |
| |
| // Most of the time name equals getName() thus holder == element |
| NodeElement newHolder; |
| if (name.equals(element.getName())) { |
| newHolder = element; |
| } else { |
| newHolder = new ElementHolder(name, element); |
| } |
| |
| // 75% fill rate which anecdotal evidence claims is a good threshold for growing |
| if ((elements.length >> 2) * 3 <= size()) { |
| grow(); |
| } |
| int index = internalAdd(newHolder); |
| if (index == -1) { |
| ordered.add(element); |
| return; |
| } |
| |
| // Handle existing element with the same name |
| NodeElement existingHolder = elements[index]; |
| if (existingHolder == element) { |
| return; |
| } |
| if (!(existingHolder instanceof ElementHolder)) { |
| existingHolder = new ElementHolder(name, existingHolder); |
| elements[index] = existingHolder; |
| } |
| |
| // Check the list for a duplicate element entry, and append if none found |
| ElementHolder holder = (ElementHolder) existingHolder; |
| while (true) { |
| if (holder.element == element) { |
| return; |
| } |
| if (holder.nextHolder == null) { |
| holder.nextHolder = new ElementHolder(name, element); |
| ordered.add(element); |
| return; |
| } |
| holder = holder.nextHolder; |
| } |
| } |
| |
| void clear() { |
| elements = new NodeElement[16]; |
| ordered.clear(); |
| } |
| |
| /** |
| * Answer the element last associated with the specified name. |
| * |
| * @return the element or <code>null</code> if none |
| */ |
| @VisibleForTesting |
| public NodeElement get(String name) { |
| NodeElement element = internalGet(name); |
| if (element instanceof ElementHolder) { |
| return ((ElementHolder) element).element; |
| } else { |
| return element; |
| } |
| } |
| |
| /** |
| * Answer the element associated with the specified name and kind |
| * |
| * @return the element of that kind or <code>null</code> if none |
| */ |
| @VisibleForTesting |
| public NodeElement get(String name, ElementKind kind) { |
| NodeElement element = internalGet(name); |
| if (element instanceof ElementHolder) { |
| ElementHolder holder = (ElementHolder) element; |
| while (true) { |
| element = holder.element; |
| if (ElementKind.of(element).equals(kind)) { |
| return element; |
| } |
| holder = holder.nextHolder; |
| if (holder == null) { |
| break; |
| } |
| } |
| } else { |
| if (ElementKind.of(element).equals(kind)) { |
| return element; |
| } |
| } |
| return null; |
| } |
| |
| @VisibleForTesting |
| public boolean isEmpty() { |
| return ordered.isEmpty(); |
| } |
| |
| @VisibleForTesting |
| public int size() { |
| return ordered.size(); |
| } |
| |
| @VisibleForTesting |
| public List<NodeElement> values() { |
| return ordered; |
| } |
| |
| private void grow() { |
| NodeElement[] old = elements; |
| elements = new NodeElement[elements.length << 2]; |
| for (NodeElement element : old) { |
| if (element != null) { |
| if (internalAdd(element) != -1) { |
| // Every element in the array should have a unique name, so there should not be any collision |
| throw new RuntimeException("Failed to grow: " + element.getName()); |
| } |
| } |
| } |
| } |
| |
| /** |
| * If an element with the given name does not exist in the array, then add the element and return |
| * -1 otherwise nothing is added and the index of the existing element returned. |
| */ |
| private int internalAdd(NodeElement element) { |
| String name = element.getName(); |
| int mask = elements.length - 1; |
| int probe = name.hashCode() & mask; |
| for (int i = probe; i < probe + mask + 1; i++) { |
| int index = i & mask; |
| NodeElement current = elements[index]; |
| if (current == null) { |
| elements[index] = element; |
| return -1; |
| } |
| if (current.getName().equals(name)) { |
| return index; |
| } |
| } |
| throw new AssertionError("overfilled array"); |
| } |
| |
| private NodeElement internalGet(String name) { |
| NodeElement element; |
| int mask = elements.length - 1; |
| int probe = name.hashCode() & mask; |
| for (int i = probe; i < probe + mask + 1; i++) { |
| element = elements[i & mask]; |
| if (element == null || element.getName().equals(name)) { |
| return element; |
| } |
| } |
| throw new AssertionError("overfilled array"); |
| } |
| } |