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