1/* 2 * Copyright 2016 Google Inc. All Rights Reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.turbine.binder.lookup; 18 19import com.google.common.base.Splitter; 20import com.google.common.collect.ImmutableList; 21import com.google.turbine.binder.sym.ClassSymbol; 22import java.util.HashMap; 23import java.util.Iterator; 24import java.util.Map; 25import java.util.Objects; 26import javax.annotation.Nullable; 27 28/** 29 * An index of canonical type names. 30 * 31 * <p>Used to resolve top-level qualified type names in the classpath, and the sources being 32 * compiled. Also provides lookup scopes for individual packages. 33 * 34 * <p>Only top-level classes are stored. Nested type names can't usually be assumed to be canonical 35 * (the qualifier may inherited the named type, rather than declaring it directly), so nested types 36 * are resolved separately with appropriate handling of non-canonical names. For bytecode we may end 37 * up storing desugared nested classes (e.g. {@code Map$Entry}), but we can't tell until the class 38 * file has been read and we have access to the InnerClasses attribtue. 39 * 40 * <p>Qualified names are represented internally as a tree, where each package name part or class 41 * name is a node. 42 */ 43public class TopLevelIndex implements Scope { 44 45 /** A class symbol or package. */ 46 public static class Node { 47 48 public Node lookup(String bit) { 49 return children.get(bit); 50 } 51 52 @Nullable private final ClassSymbol sym; 53 54 // TODO(cushon): the set of children is typically going to be small, consider optimizing this 55 // to use a denser representation where appropriate. 56 private final Map<String, Node> children = new HashMap<>(); 57 58 Node(ClassSymbol sym) { 59 this.sym = sym; 60 } 61 62 /** 63 * Add a child with the given simple name. The given symbol will be null if a package is being 64 * inserted. 65 * 66 * @return {@code null} if an existing symbol with the same name has already been inserted. 67 */ 68 private Node insert(String name, ClassSymbol sym) { 69 Node child; 70 if (children.containsKey(name)) { 71 child = children.get(name); 72 if (child.sym != null) { 73 return null; 74 } 75 } else { 76 child = new Node(sym); 77 children.put(name, child); 78 } 79 return child; 80 } 81 } 82 83 /** A builder for {@link TopLevelIndex}es. */ 84 public static class Builder { 85 86 public TopLevelIndex build() { 87 // Freeze the index. The immutability of nodes is enforced by making insert private, doing 88 // a deep copy here isn't necessary. 89 return new TopLevelIndex(root); 90 } 91 92 /** The root of the lookup tree, effectively the package node of the default package. */ 93 final Node root = new Node(null); 94 95 /** Inserts a {@link ClassSymbol} into the index, creating any needed packages. */ 96 public boolean insert(ClassSymbol sym) { 97 Iterator<String> it = Splitter.on('/').split(sym.toString()).iterator(); 98 Node curr = root; 99 while (it.hasNext()) { 100 String simpleName = it.next(); 101 // if this is the last simple name in the qualified name of the top-level class being 102 // inserted, we are creating a node for the class symbol 103 ClassSymbol nodeSym = it.hasNext() ? null : sym; 104 curr = curr.insert(simpleName, nodeSym); 105 // If we've already inserted something with the current name (either a package or another 106 // symbol), bail out. When inserting elements from the classpath, this results in the 107 // expected first-match-wins semantics. 108 if (curr == null || !Objects.equals(curr.sym, nodeSym)) { 109 return false; 110 } 111 } 112 return true; 113 } 114 } 115 116 /** Returns a builder for {@link TopLevelIndex}es. */ 117 public static Builder builder() { 118 return new Builder(); 119 } 120 121 private TopLevelIndex(Node root) { 122 this.root = root; 123 } 124 125 final Node root; 126 127 /** Looks up top-level qualified type names. */ 128 @Override 129 @Nullable 130 public LookupResult lookup(LookupKey lookupKey) { 131 Node curr = root; 132 while (true) { 133 curr = curr.lookup(lookupKey.first()); 134 if (curr == null) { 135 return null; 136 } 137 if (curr.sym != null) { 138 return new LookupResult(curr.sym, lookupKey); 139 } 140 if (!lookupKey.hasNext()) { 141 return null; 142 } 143 lookupKey = lookupKey.rest(); 144 } 145 } 146 147 /** Returns a {@link Scope} that performs lookups in the given qualified package name. */ 148 public Scope lookupPackage(ImmutableList<String> packagename) { 149 Node curr = root; 150 for (String bit : packagename) { 151 curr = curr.lookup(bit); 152 if (curr == null || curr.sym != null) { 153 return null; 154 } 155 } 156 return new PackageIndex(curr); 157 } 158 159 static class PackageIndex implements Scope { 160 161 private final Node node; 162 163 public PackageIndex(Node node) { 164 this.node = node; 165 } 166 167 @Override 168 public LookupResult lookup(LookupKey lookupKey) { 169 Node result = node.children.get(lookupKey.first()); 170 if (result != null && result.sym != null) { 171 return new LookupResult(result.sym, lookupKey); 172 } 173 return null; 174 } 175 } 176} 177