1.1 --- a/lookup/src/main/java/org/openide/util/lookup/InheritanceTree.java Wed Jan 27 17:46:23 2010 -0500
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1276 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 1997-2009 Sun Microsystems, Inc. All rights reserved.
1.8 - *
1.9 - * The contents of this file are subject to the terms of either the GNU
1.10 - * General Public License Version 2 only ("GPL") or the Common
1.11 - * Development and Distribution License("CDDL") (collectively, the
1.12 - * "License"). You may not use this file except in compliance with the
1.13 - * License. You can obtain a copy of the License at
1.14 - * http://www.netbeans.org/cddl-gplv2.html
1.15 - * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
1.16 - * specific language governing permissions and limitations under the
1.17 - * License. When distributing the software, include this License Header
1.18 - * Notice in each file and include the License file at
1.19 - * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
1.20 - * particular file as subject to the "Classpath" exception as provided
1.21 - * by Sun in the GPL Version 2 section of the License file that
1.22 - * accompanied this code. If applicable, add the following below the
1.23 - * License Header, with the fields enclosed by brackets [] replaced by
1.24 - * your own identifying information:
1.25 - * "Portions Copyrighted [year] [name of copyright owner]"
1.26 - *
1.27 - * Contributor(s):
1.28 - *
1.29 - * The Original Software is NetBeans. The Initial Developer of the Original
1.30 - * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
1.31 - * Microsystems, Inc. All Rights Reserved.
1.32 - *
1.33 - * If you wish your version of this file to be governed by only the CDDL
1.34 - * or only the GPL Version 2, indicate your decision by adding
1.35 - * "[Contributor] elects to include this software in this distribution
1.36 - * under the [CDDL or GPL Version 2] license." If you do not indicate a
1.37 - * single choice of license, a recipient has the option to distribute
1.38 - * your version of this file under either the CDDL, the GPL Version 2 or
1.39 - * to extend the choice of license to its licensees as provided above.
1.40 - * However, if you add GPL Version 2 code and therefore, elected the GPL
1.41 - * Version 2 license, then the option applies only if the new code is
1.42 - * made subject to such option by the copyright holder.
1.43 - */
1.44 -package org.openide.util.lookup;
1.45 -
1.46 -import org.openide.util.Lookup;
1.47 -import org.openide.util.lookup.AbstractLookup.Pair;
1.48 -import org.openide.util.lookup.AbstractLookup.ReferenceIterator;
1.49 -import org.openide.util.lookup.AbstractLookup.ReferenceToResult;
1.50 -
1.51 -import java.io.*;
1.52 -
1.53 -import java.lang.ref.WeakReference;
1.54 -
1.55 -import java.util.*;
1.56 -
1.57 -
1.58 -/** A tree to represent classes with inheritance. Description of the
1.59 - * data structure by Petr Nejedly:
1.60 - * <P>
1.61 - * So pretend I'm Lookup implementation. I've got a bunch of Items (e.g.
1.62 - * setPairs() method),
1.63 - * didn't do anything on them yet (no startup penalty) so I know nothing
1.64 - * about them.
1.65 - * Then I'll be asked for all instances implementing given interface or a
1.66 - * class. I surely need
1.67 - * to check all the Items now, as I don't know anything abou them. I surely
1.68 - * don't want to call
1.69 - * Item.getClass() as it will dismiss the whole effort. So all I have is
1.70 - * Item.instanceOf()
1.71 - * and I'll call it on every Item. I'll cache results, so the next time
1.72 - * you'll ask me for
1.73 - * the same interface/class, I'll answer immediatelly. But what if you ask
1.74 - * me for another
1.75 - * interface/class? I'll have to scan all Items for it again, unless I can
1.76 - * be sure some
1.77 - * of them can't implement it. The only source of this knowledge are the
1.78 - * previous questions
1.79 - * and my rulings on them. Here the algorithm have to be split into two
1.80 - * paths. If you
1.81 - * previously asked me for interfaces only, I'll have no hint for
1.82 - * subsequent queries,
1.83 - * but if you asked me for a class in history, and then for another class
1.84 - * and these classes
1.85 - * are not in inheritance relation (I can check hierarchy of lookup
1.86 - * arguments, because
1.87 - * they are already resolved/loaded) I can tell that those returned in
1.88 - * previous query can't
1.89 - * implement the newly asked class (they are in different hierarchy branch)
1.90 - * and I need to
1.91 - * ask less Items.
1.92 - * <P>
1.93 - * So if we use mostly classes for asking for services (and it is a trend
1.94 - * to use
1.95 - * abstract classes for this purpose in IDE anyway), this could be usable.
1.96 - * <P>
1.97 - * The data structure for separating the Items based on previous queries is
1.98 - * simple
1.99 - * tree, with every node tagged with one class. The tree's root is,
1.100 - * naturally,
1.101 - * java.lang.Object, is marked invited and initially contains all the
1.102 - * Items.
1.103 - * For every class query, the missing part of class hierarchy tree is
1.104 - * created,
1.105 - * the node of the class looked up is marked as invited and all Items from
1.106 - * nearest
1.107 - * invited parent (sperclass) are dragged to this node. The result are then
1.108 - * all
1.109 - * Items from this node and all the nodes deeper in hierarchy. Because it
1.110 - * may
1.111 - * be too complicated to walk through the children nodes, the results could
1.112 - * be
1.113 - * cached in the map.
1.114 - * For interface lookup, there is a little hint in reality (interfaces
1.115 - * and superinterfaces), but it would be harder to exploit it, so we could
1.116 - * fall-back
1.117 - * to walking through all the Items and cache results.
1.118 - *
1.119 - *
1.120 - * @author Jaroslav Tulach
1.121 - */
1.122 -final class InheritanceTree extends Object
1.123 -implements Serializable, AbstractLookup.Storage<ArrayList<Class>> {
1.124 - private static final long serialVersionUID = 1L;
1.125 -
1.126 - /** the root item (represents Object) */
1.127 - private transient Node object;
1.128 -
1.129 - /** Map of queried interfaces.
1.130 - * <p>Type: <code>Map<Class, (Collection<AbstractLookup.Pair> | AbstractLookup.Pair)></code>
1.131 - */
1.132 - private transient Map<Class,Object> interfaces;
1.133 -
1.134 - /** Map (Class, ReferenceToResult) of all listeners that are waiting in
1.135 - * changes in class Class
1.136 - */
1.137 - private transient Map<Class,ReferenceToResult> reg;
1.138 -
1.139 - /** Constructor
1.140 - */
1.141 - public InheritanceTree() {
1.142 - object = new Node(java.lang.Object.class);
1.143 - }
1.144 -
1.145 - private void writeObject(ObjectOutputStream oos) throws IOException {
1.146 - oos.writeObject(object);
1.147 -
1.148 - if (interfaces != null) {
1.149 - Iterator it = interfaces.entrySet().iterator();
1.150 -
1.151 - while (it.hasNext()) {
1.152 - Map.Entry e = (Map.Entry) it.next();
1.153 - Class c = (Class) e.getKey();
1.154 - oos.writeObject(c.getName());
1.155 -
1.156 - Object o = e.getValue();
1.157 -
1.158 - if (!(o instanceof Collection) && !(o instanceof AbstractLookup.Pair)) {
1.159 - throw new ClassCastException(String.valueOf(o));
1.160 - }
1.161 -
1.162 - oos.writeObject(o);
1.163 - }
1.164 - }
1.165 -
1.166 - oos.writeObject(null);
1.167 - }
1.168 -
1.169 - private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {
1.170 - object = (Node) ois.readObject();
1.171 - interfaces = new WeakHashMap<Class,Object>();
1.172 -
1.173 - String clazz;
1.174 - ClassLoader l = Lookup.getDefault().lookup(ClassLoader.class);
1.175 -
1.176 - while ((clazz = (String) ois.readObject()) != null) {
1.177 - Object o = ois.readObject();
1.178 -
1.179 - if (!(o instanceof Collection) && !(o instanceof AbstractLookup.Pair)) {
1.180 - throw new ClassCastException(String.valueOf(o));
1.181 - }
1.182 -
1.183 - Class c = Class.forName(clazz, false, l);
1.184 - interfaces.put(c, o);
1.185 - }
1.186 - }
1.187 -
1.188 - /** Adds an item into the tree.
1.189 - * @param item to add
1.190 - * @return true if the Item has been added for the first time or false if some other
1.191 - * item equal to this one already existed in the lookup
1.192 - */
1.193 - public boolean add(AbstractLookup.Pair<?> item, ArrayList<Class> affected) {
1.194 - Node node = registerClass(object, item);
1.195 -
1.196 - affected.add(node.getType());
1.197 -
1.198 - if (node.assignItem(this, item)) {
1.199 - // this is the first item added to n.items
1.200 - // ok, we have to test interfaces too
1.201 - } else {
1.202 - // equal item is already there => stop processing
1.203 - return false;
1.204 - }
1.205 -
1.206 - boolean registeredAsInterface = registerInterface(item, affected);
1.207 -
1.208 - return registeredAsInterface;
1.209 - }
1.210 -
1.211 - /** Removes an item.
1.212 - */
1.213 - public void remove(AbstractLookup.Pair item, ArrayList<Class> affected) {
1.214 - Node n = removeClass(object, item);
1.215 -
1.216 - if (n != null) {
1.217 - affected.add(n.getType());
1.218 - }
1.219 -
1.220 - removeInterface(item, affected);
1.221 - }
1.222 -
1.223 - /** Removes all items that are not present in the provided collection.
1.224 - * @param retain collection of Pairs to keep them in
1.225 - * @param notify set of Classes that has possibly changed
1.226 - */
1.227 - public void retainAll(Map retain, ArrayList<Class> notify) {
1.228 - retainAllInterface(retain, notify);
1.229 - retainAllClasses(object, retain, notify);
1.230 - }
1.231 -
1.232 - /** Queries for instances of given class.
1.233 - * @param clazz the class to check
1.234 - * @return enumeration of Item
1.235 - * @see #unsorted
1.236 - */
1.237 - @SuppressWarnings("unchecked")
1.238 - public <T> Enumeration<Pair<T>> lookup(Class<T> clazz) {
1.239 - if ((clazz != null) && clazz.isInterface()) {
1.240 - return (Enumeration)searchInterface(clazz);
1.241 - } else {
1.242 - return (Enumeration)searchClass(object, clazz);
1.243 - }
1.244 - }
1.245 -
1.246 - /** A method to check whether the enumeration returned from
1.247 - * lookup method is sorted or is not
1.248 - * @param en enumeration to check
1.249 - * @return true if it is unsorted and needs to be sorted to find
1.250 - * pair with smallest index
1.251 - */
1.252 - public static boolean unsorted(Enumeration en) {
1.253 - return en instanceof NeedsSortEnum;
1.254 - }
1.255 -
1.256 - /** Prints debug messages.
1.257 - * @param out stream to output to
1.258 - * @param instances print also instances of the
1.259 - */
1.260 - public void print(java.io.PrintStream out, boolean instances) {
1.261 - printNode(object, "", out, instances); // NOI18N
1.262 - }
1.263 -
1.264 - //
1.265 - // methods to work on classes which are not interfaces
1.266 - //
1.267 -
1.268 - /** Searches the subtree and register the item where necessary.
1.269 - * @return the node that should contain the item
1.270 - */
1.271 - private static Node registerClass(Node n, AbstractLookup.Pair item) {
1.272 - if (!n.accepts(item)) {
1.273 - return null;
1.274 - }
1.275 -
1.276 - if (n.children != null) {
1.277 - Iterator it = n.children.iterator();
1.278 -
1.279 - for (;;) {
1.280 - Node ch = extractNode(it);
1.281 -
1.282 - if (ch == null) {
1.283 - break;
1.284 - }
1.285 -
1.286 - Node result = registerClass(ch, item);
1.287 -
1.288 - if (result != null) {
1.289 - // it is in subclass, in case of classes, it cannot
1.290 - // be any other class
1.291 - return result;
1.292 - }
1.293 - }
1.294 - }
1.295 -
1.296 - // ok, nobody of our subclasses wants the class, I'll take it
1.297 - return n;
1.298 - }
1.299 -
1.300 - /** Removes the item from the tree of objects.
1.301 - * @return most narrow class that this item was removed from
1.302 - */
1.303 - private static Node removeClass(Node n, AbstractLookup.Pair item) {
1.304 - if (!n.accepts(item)) {
1.305 - return null;
1.306 - }
1.307 -
1.308 - if ((n.items != null) && n.items.remove(item)) {
1.309 - // this node really contains the item
1.310 - return n;
1.311 - }
1.312 -
1.313 - if (n.children != null) {
1.314 - Iterator it = n.children.iterator();
1.315 -
1.316 - for (;;) {
1.317 - Node ch = extractNode(it);
1.318 -
1.319 - if (ch == null) {
1.320 - break;
1.321 - }
1.322 -
1.323 - Node result = removeClass(ch, item);
1.324 -
1.325 - // If the children node was emptied, remove it if possible.
1.326 - if (((ch.items == null) || ch.items.isEmpty()) && ((ch.children == null) || ch.children.isEmpty())) {
1.327 - it.remove();
1.328 - }
1.329 -
1.330 - if (result != null) {
1.331 - // it is in subclass, in case of classes, it cannot
1.332 - // be any other class
1.333 - return result;
1.334 - }
1.335 - }
1.336 - }
1.337 -
1.338 - // nobody found
1.339 - return null;
1.340 - }
1.341 -
1.342 - /** Finds a node that represents a class.
1.343 - * @param n node to search from
1.344 - * @param clazz the clazz to find
1.345 - * @return node that represents clazz in the tree or null if the clazz is not
1.346 - * represented under the node n
1.347 - */
1.348 - private Node classToNode(final Node n, final Class<?> clazz) {
1.349 - if (!n.accepts(clazz)) {
1.350 - // nothing from us
1.351 - return null;
1.352 - }
1.353 -
1.354 - if (n.getType() == clazz) {
1.355 - // we have found what we need
1.356 - return n;
1.357 - }
1.358 -
1.359 - if (n.children != null) {
1.360 - // have to proceed to children
1.361 - Iterator it = n.children.iterator();
1.362 -
1.363 - for (;;) {
1.364 - final Node ch = extractNode(it);
1.365 -
1.366 - if (ch == null) {
1.367 - break;
1.368 - }
1.369 -
1.370 - Node found = classToNode(ch, clazz);
1.371 -
1.372 - if ((found != null) && ch.deserialized()) {
1.373 - class VerifyJob implements AbstractLookup.ISE.Job {
1.374 - private AbstractLookup.Pair<?>[] pairs;
1.375 - private boolean[] answers;
1.376 -
1.377 - public VerifyJob(Collection<Pair> items) {
1.378 - if (items != null) {
1.379 - pairs = items.toArray(new AbstractLookup.Pair[0]);
1.380 - }
1.381 - }
1.382 -
1.383 - public void before() {
1.384 - // make sure the node is converted into deserialized state
1.385 - ch.deserialized();
1.386 -
1.387 - if (pairs != null) {
1.388 - answers = new boolean[pairs.length];
1.389 -
1.390 - for (int i = 0; i < pairs.length; i++) {
1.391 - answers[i] = pairs[i].instanceOf(clazz);
1.392 - }
1.393 - }
1.394 - }
1.395 -
1.396 - public void inside() {
1.397 - if (pairs != null) {
1.398 - for (int i = 0; i < pairs.length; i++) {
1.399 - if (answers[i]) {
1.400 - ch.assignItem(InheritanceTree.this, pairs[i]);
1.401 - n.items.remove(pairs[i]);
1.402 - }
1.403 - }
1.404 - }
1.405 -
1.406 - if (n.children != null) {
1.407 - // consolidate all nodes that represent the same class
1.408 - HashMap<Class,Node> nodes = new HashMap<Class,Node>(n.children.size() * 3);
1.409 -
1.410 - Iterator child = n.children.iterator();
1.411 -
1.412 - while (child.hasNext()) {
1.413 - Node node = extractNode(child);
1.414 - if (node == null) {
1.415 - continue;
1.416 - }
1.417 - Node prev = nodes.put(node.getType(), node);
1.418 -
1.419 - if (prev != null) {
1.420 - child.remove();
1.421 - nodes.put(node.getType(), prev);
1.422 -
1.423 - // mark as being deserialized
1.424 - prev.markDeserialized();
1.425 -
1.426 - if (prev.children == null) {
1.427 - prev.children = node.children;
1.428 - } else {
1.429 - if (node.children != null) {
1.430 - prev.children.addAll(node.children);
1.431 - }
1.432 - }
1.433 -
1.434 - if (node.items != null) {
1.435 - Iterator items = node.items.iterator();
1.436 -
1.437 - while (items.hasNext()) {
1.438 - AbstractLookup.Pair item = (AbstractLookup.Pair) items.next();
1.439 - prev.assignItem(InheritanceTree.this, item);
1.440 - }
1.441 - }
1.442 - }
1.443 - }
1.444 - }
1.445 - }
1.446 - }
1.447 -
1.448 - VerifyJob verify = new VerifyJob(n.items);
1.449 -
1.450 - try {
1.451 - verify.before();
1.452 - } catch (AbstractLookup.ISE ex) {
1.453 - // mark deserialized again
1.454 - ch.markDeserialized();
1.455 - ex.registerJob(verify);
1.456 - throw ex;
1.457 - }
1.458 -
1.459 - verify.inside();
1.460 -
1.461 - found = classToNode(ch, clazz);
1.462 - }
1.463 -
1.464 - if (found != null) {
1.465 - // class found in one of subnodes
1.466 - return found;
1.467 - }
1.468 - }
1.469 - }
1.470 -
1.471 - class TwoJobs implements AbstractLookup.ISE.Job {
1.472 - private AbstractLookup.Pair[] pairs;
1.473 - private boolean[] answers;
1.474 - private Node newNode;
1.475 -
1.476 - public void before() {
1.477 - // have to create new subnode and possibly reparent one of my own
1.478 - // but all changes can be done only if we will not be interrupted from
1.479 - // outside - e.g. instanceOf methods will not throw exception
1.480 - // first of all let's compute the answers to method instanceOf
1.481 - AbstractLookup.Pair[] arr = null;
1.482 - boolean[] boolArr = null;
1.483 -
1.484 - if (n.items != null) {
1.485 - arr = new AbstractLookup.Pair[n.items.size()];
1.486 - boolArr = new boolean[n.items.size()];
1.487 -
1.488 - int i = 0;
1.489 - Iterator<Pair> it = n.items.iterator();
1.490 -
1.491 - while (it.hasNext()) {
1.492 - AbstractLookup.Pair<?> item = it.next();
1.493 - arr[i] = item;
1.494 - boolArr[i] = item.instanceOf(clazz);
1.495 - i++;
1.496 - }
1.497 - }
1.498 -
1.499 - pairs = arr;
1.500 - answers = boolArr;
1.501 - }
1.502 -
1.503 - public void inside() {
1.504 - // test if the query has not chagned since
1.505 - if (pairs != null) {
1.506 - if (!Arrays.equals(n.items.toArray(), pairs)) {
1.507 - // ok, let try once more
1.508 - return;
1.509 - }
1.510 - }
1.511 -
1.512 - internal();
1.513 - }
1.514 -
1.515 - public void internal() {
1.516 - ArrayList<Node> reparent = null;
1.517 -
1.518 - if (n.children == null) {
1.519 - n.children = new ArrayList<Node>();
1.520 - } else {
1.521 - // scan thru all my nodes if some of them are not a subclass
1.522 - // of clazz => then they would need to become child of newNode
1.523 - Iterator it = n.children.iterator();
1.524 -
1.525 - for (;;) {
1.526 - Node r = extractNode(it);
1.527 -
1.528 - if (r == null) {
1.529 - break;
1.530 - }
1.531 -
1.532 - if (clazz.isAssignableFrom(r.getType())) {
1.533 - if (reparent == null) {
1.534 - reparent = new ArrayList<Node>();
1.535 - }
1.536 -
1.537 - reparent.add(r);
1.538 - it.remove();
1.539 - }
1.540 - }
1.541 - }
1.542 -
1.543 - newNode = new Node(clazz);
1.544 - n.children.add(newNode);
1.545 -
1.546 - if (reparent != null) {
1.547 - // reassing reparent node as a child of newNode
1.548 - newNode.children = reparent;
1.549 - }
1.550 -
1.551 - // now take all my items that are instances of that class and
1.552 - // reasign them
1.553 - if (n.items != null) {
1.554 - Iterator it = n.items.iterator();
1.555 - int i = 0;
1.556 -
1.557 - while (it.hasNext()) {
1.558 - AbstractLookup.Pair item = (AbstractLookup.Pair) it.next();
1.559 -
1.560 - if (answers[i]) { // answers[i] is precomputed value of item.instanceOf (clazz))
1.561 - it.remove();
1.562 - newNode.assignItem(InheritanceTree.this, pairs[i]);
1.563 - }
1.564 -
1.565 - i++;
1.566 - }
1.567 - }
1.568 - }
1.569 - }
1.570 -
1.571 - TwoJobs j = new TwoJobs();
1.572 -
1.573 - try {
1.574 - j.before();
1.575 - } catch (AbstractLookup.ISE ex) {
1.576 - // ok, it is not possible to call instanceOf now, let's
1.577 - // schedule it for later
1.578 - // so register recovery job
1.579 - ex.registerJob(j);
1.580 - throw ex;
1.581 - }
1.582 -
1.583 - j.internal();
1.584 -
1.585 - // newNode represents my clazz
1.586 - return j.newNode;
1.587 - }
1.588 -
1.589 - /** Search for a requested class.
1.590 - * @return enumeration of Pair
1.591 - */
1.592 - private Enumeration<Pair> searchClass(Node n, Class<?> clazz) {
1.593 - if (clazz != null) {
1.594 - n = classToNode(n, clazz);
1.595 - }
1.596 -
1.597 - if (n == null) {
1.598 - // not for us
1.599 - return emptyEn();
1.600 - } else {
1.601 - return nodeToEnum(n);
1.602 - }
1.603 - }
1.604 -
1.605 - /** Retains all classes. Removes nodes which items and children are emptied, works
1.606 - * recursivelly from specified root node.
1.607 - * @param node root node from which to start to process the tree
1.608 - * @param retain a map from (Item, AbstractLookup.Info) that describes which items to retain
1.609 - * and witch integer to assign them
1.610 - * @param notify collection of classes will be changed
1.611 - * @return <code>true<code> if some items were changed and node items and children are emptied,
1.612 - * those nodes, excluding root, will be removed from tree */
1.613 - private boolean retainAllClasses(Node node, Map retain, Collection<Class> notify) {
1.614 - boolean retained = false;
1.615 -
1.616 - if ((node.items != null) && (retain != null)) {
1.617 - Iterator<Pair> it = node.items.iterator();
1.618 -
1.619 - while (it.hasNext()) {
1.620 - AbstractLookup.Pair<?> item = it.next();
1.621 - AbstractLookup.Info n = (AbstractLookup.Info) retain.remove(item);
1.622 -
1.623 - if (n == null) {
1.624 - // remove this item, it should not be there
1.625 - it.remove();
1.626 - retained = true;
1.627 - } else {
1.628 - // change the index
1.629 - if (item.getIndex() != n.index) {
1.630 - item.setIndex(null, n.index);
1.631 -
1.632 - // notify.addAll ((ArrayList)n.transaction);
1.633 - }
1.634 - }
1.635 - }
1.636 -
1.637 - if (retained && (notify != null)) {
1.638 - // type of this node has been changed
1.639 - notify.add(node.getType());
1.640 - }
1.641 - }
1.642 -
1.643 - if (node.children != null) {
1.644 - for (Iterator it = node.children.iterator();;) {
1.645 - Node ch = extractNode(it);
1.646 -
1.647 - if (ch == null) {
1.648 - break;
1.649 - }
1.650 -
1.651 - boolean result = retainAllClasses(ch, retain, notify);
1.652 -
1.653 - if (result) {
1.654 - // The children node was emptied and has no children -> remove it.
1.655 - it.remove();
1.656 - }
1.657 - }
1.658 - }
1.659 -
1.660 - return retained && node.items.isEmpty() && ((node.children == null) || node.children.isEmpty());
1.661 - }
1.662 -
1.663 - /** A method that creates enumeration of all items under given node.
1.664 - *
1.665 - * @param n node to create enumeration for
1.666 - * @return enumeration of Pairs
1.667 - */
1.668 - private static Enumeration<Pair> nodeToEnum(Node n) {
1.669 - if (n.children == null) {
1.670 - // create a simple enumeration because we do not have children
1.671 - Enumeration<Pair> e;
1.672 - if (n.items == null) {
1.673 - e = emptyEn();
1.674 - } else {
1.675 - e = Collections.enumeration(n.items);
1.676 - }
1.677 - return e;
1.678 - }
1.679 -
1.680 - // create enumeration of Items
1.681 - return new NeedsSortEnum(n);
1.682 - }
1.683 -
1.684 - //
1.685 - // Methods to work on interfaces
1.686 - //
1.687 -
1.688 - /** Registers an item with interfaces.
1.689 - * @param item item to register
1.690 - * @param affected list of classes that were affected
1.691 - * @return false if similar item has already been registered
1.692 - */
1.693 - @SuppressWarnings("unchecked")
1.694 - private boolean registerInterface(AbstractLookup.Pair<?> item, Collection<Class> affected) {
1.695 - if (interfaces == null) {
1.696 - return true;
1.697 - }
1.698 -
1.699 - Iterator<Map.Entry<Class,Object>> it = interfaces.entrySet().iterator();
1.700 -
1.701 - while (it.hasNext()) {
1.702 - Map.Entry<Class,Object> entry = it.next();
1.703 - Class<?> iface = entry.getKey();
1.704 -
1.705 - if (item.instanceOf(iface)) {
1.706 - Object value = entry.getValue();
1.707 -
1.708 - if (value instanceof Collection) {
1.709 - Collection<Object> set = (Collection<Object>) value;
1.710 -
1.711 - if (!set.add(item)) {
1.712 - // item is already there, probably (if everything is correct) is registered in
1.713 - // all other ifaces too, so stop additional testing
1.714 - return false;
1.715 - }
1.716 - } else {
1.717 - // there is just one pair right now
1.718 - if (value.equals(item)) {
1.719 - // item is there => stop processing (same as above)
1.720 - return false;
1.721 - }
1.722 -
1.723 - // otherwise replace the single item with ArrayList
1.724 - ArrayList<Object> ll = new ArrayList<Object>(3);
1.725 - ll.add(value);
1.726 - ll.add(item);
1.727 - entry.setValue(ll);
1.728 - }
1.729 -
1.730 - affected.add(iface);
1.731 - }
1.732 - }
1.733 -
1.734 - return true;
1.735 - }
1.736 -
1.737 - /** Removes interface.
1.738 - * @param item item to register
1.739 - * @param affected list of classes that were affected
1.740 - */
1.741 - @SuppressWarnings("unchecked")
1.742 - private void removeInterface(AbstractLookup.Pair item, Collection affected) {
1.743 - if (interfaces == null) {
1.744 - return;
1.745 - }
1.746 -
1.747 - Iterator it = interfaces.entrySet().iterator();
1.748 -
1.749 - while (it.hasNext()) {
1.750 - Map.Entry entry = (Map.Entry) it.next();
1.751 - Object value = entry.getValue();
1.752 -
1.753 - if (value instanceof Collection) {
1.754 - Collection set = (Collection) value;
1.755 -
1.756 - if (set.remove(item)) {
1.757 - if (set.size() == 1) {
1.758 - // if there is just one item remaining change to single item mode
1.759 - entry.setValue(set.iterator().next());
1.760 - }
1.761 -
1.762 - // adds the Class the item was register to into affected
1.763 - affected.add(entry.getKey());
1.764 - }
1.765 - } else {
1.766 - // single item value
1.767 - if (value.equals(item)) {
1.768 - // Emptied -> remove.
1.769 - it.remove();
1.770 -
1.771 - affected.add(entry.getKey());
1.772 - }
1.773 - }
1.774 - }
1.775 - }
1.776 -
1.777 - /** Retains some items.
1.778 - * @param retainItems items to retain and their mapping to index numbers
1.779 - * (AbstractLookup.Pair -> AbstractLookup.Info)
1.780 - * @param affected list of classes that were affected
1.781 - */
1.782 - @SuppressWarnings("unchecked")
1.783 - private void retainAllInterface(Map retainItems, Collection affected) {
1.784 - if (interfaces == null) {
1.785 - return;
1.786 - }
1.787 -
1.788 - Iterator it = interfaces.entrySet().iterator();
1.789 -
1.790 - while (it.hasNext()) {
1.791 - Map.Entry entry = (Map.Entry) it.next();
1.792 - Object value = entry.getValue();
1.793 -
1.794 - HashMap<?,?> retain = new HashMap(retainItems);
1.795 -
1.796 - Iterator elems;
1.797 - boolean multi = value instanceof Collection;
1.798 -
1.799 - if (multi) {
1.800 - // collection mode
1.801 - elems = ((Collection) value).iterator();
1.802 - } else {
1.803 - // single item mode
1.804 - elems = Collections.singleton(value).iterator();
1.805 - }
1.806 -
1.807 - boolean changed = false;
1.808 - boolean reordered = false;
1.809 -
1.810 - while (elems.hasNext()) {
1.811 - AbstractLookup.Pair p = (AbstractLookup.Pair) elems.next();
1.812 -
1.813 - AbstractLookup.Info n = (AbstractLookup.Info) retain.remove(p);
1.814 -
1.815 - if (n == null) {
1.816 - if (multi) {
1.817 - // remove it
1.818 - elems.remove();
1.819 - }
1.820 -
1.821 - changed = true;
1.822 - } else {
1.823 - if (p.getIndex() != n.index) {
1.824 - // improve the index
1.825 - p.setIndex(null, n.index);
1.826 -
1.827 - // affected.addAll ((ArrayList)n.transaction);
1.828 - reordered = true;
1.829 - }
1.830 - }
1.831 - }
1.832 -
1.833 - if (reordered && value instanceof List) {
1.834 - // if reordered, than update the order in the collection
1.835 - List l = (List) value;
1.836 - Collections.sort(l, ALPairComparator.DEFAULT);
1.837 - }
1.838 -
1.839 - if (changed) {
1.840 - if (multi) {
1.841 - Collection c = (Collection) value;
1.842 -
1.843 - if (c.size() == 1) {
1.844 - // back to single item mode
1.845 - entry.setValue(c.iterator().next());
1.846 - }
1.847 - } else {
1.848 - // remove in single mode => remove completely
1.849 - it.remove();
1.850 - }
1.851 -
1.852 - // adds the Class the item was register to into affected
1.853 - affected.add(entry.getKey());
1.854 - }
1.855 - }
1.856 - }
1.857 -
1.858 - /** Searches for a clazz between interfaces.
1.859 - * @param clazz class to search for
1.860 - * @return enumeration of Items
1.861 - */
1.862 - @SuppressWarnings("unchecked")
1.863 - private Enumeration<Pair> searchInterface(final Class<?> clazz) {
1.864 - if (interfaces == null) {
1.865 - // first call for interface, only initialize
1.866 - interfaces = new WeakHashMap();
1.867 - }
1.868 -
1.869 - Object obj = interfaces.get(clazz);
1.870 -
1.871 - if (obj == null) {
1.872 - // set of items
1.873 - AbstractLookup.Pair one = null;
1.874 - ArrayList items = null;
1.875 -
1.876 - Enumeration en = lookup(Object.class);
1.877 -
1.878 - while (en.hasMoreElements()) {
1.879 - AbstractLookup.Pair it = (AbstractLookup.Pair) en.nextElement();
1.880 -
1.881 - if (it.instanceOf(clazz)) {
1.882 - // ok, this item implements given clazz
1.883 - if (one == null) {
1.884 - one = it;
1.885 - } else {
1.886 - if (items == null) {
1.887 - items = new ArrayList(3);
1.888 - items.add(one);
1.889 - }
1.890 -
1.891 - items.add(it);
1.892 - }
1.893 - }
1.894 - }
1.895 -
1.896 - if ((items == null) && (one != null)) {
1.897 - // single item mode
1.898 - interfaces.put(clazz, one);
1.899 -
1.900 - return singletonEn(one);
1.901 - } else {
1.902 - if (items == null) {
1.903 - items = new ArrayList(2);
1.904 - }
1.905 -
1.906 - interfaces.put(clazz, items);
1.907 -
1.908 - return Collections.enumeration(items);
1.909 - }
1.910 - } else {
1.911 - if (obj instanceof Collection) {
1.912 - return Collections.enumeration((Collection) obj);
1.913 - } else {
1.914 - // single item mode
1.915 - return singletonEn((Pair)obj);
1.916 - }
1.917 - }
1.918 - }
1.919 -
1.920 - /** Extracts a node from an iterator, returning null if no next element found
1.921 - */
1.922 - private static Node extractNode(Iterator it) {
1.923 - while (it.hasNext()) {
1.924 - Node n = (Node) it.next();
1.925 -
1.926 - if (n.get() == null) {
1.927 - it.remove();
1.928 - } else {
1.929 - return n;
1.930 - }
1.931 - }
1.932 -
1.933 - return null;
1.934 - }
1.935 -
1.936 - /** Prints debug info about the node.
1.937 - * @param n node to print
1.938 - * @param sp spaces to add
1.939 - * @param out where
1.940 - * @param instances print also instances
1.941 - */
1.942 - private static void printNode(Node n, String sp, java.io.PrintStream out, boolean instances) {
1.943 - int i;
1.944 - Iterator it;
1.945 -
1.946 - Class type = n.getType();
1.947 -
1.948 - out.print(sp);
1.949 - out.println("Node for: " + type + "\t" + ((type == null) ? null : type.getClassLoader())); // NOI18N
1.950 -
1.951 - if (n.items != null) {
1.952 - i = 0;
1.953 - it = new ArrayList<Pair>(n.items).iterator();
1.954 -
1.955 - while (it.hasNext()) {
1.956 - AbstractLookup.Pair p = (AbstractLookup.Pair) it.next();
1.957 - out.print(sp);
1.958 - out.print(" item (" + i++ + "): ");
1.959 - out.print(p); // NOI18N
1.960 - out.print(" id: " + Integer.toHexString(System.identityHashCode(p))); // NOI18N
1.961 - out.print(" index: "); // NOI18N
1.962 - out.print(p.getIndex());
1.963 -
1.964 - if (instances) {
1.965 - out.print(" I: " + p.getInstance());
1.966 - }
1.967 -
1.968 - out.println();
1.969 - }
1.970 - }
1.971 -
1.972 - if (n.children != null) {
1.973 - i = 0;
1.974 - it = n.children.iterator();
1.975 -
1.976 - while (it.hasNext()) {
1.977 - Node ch = (Node) it.next();
1.978 - printNode(ch, sp + " ", out, instances); // NOI18N
1.979 - }
1.980 - }
1.981 - }
1.982 -
1.983 - public ReferenceToResult registerReferenceToResult(ReferenceToResult<?> newRef) {
1.984 - if (reg == null) {
1.985 - reg = new HashMap<Class,ReferenceToResult>();
1.986 - }
1.987 -
1.988 - Class<? extends Object> clazz = newRef.template.getType();
1.989 -
1.990 - // initialize the data structures if not yet
1.991 - lookup(clazz);
1.992 -
1.993 - // newRef will be the new head of the list
1.994 - return reg.put(clazz, newRef);
1.995 - }
1.996 -
1.997 - public ReferenceToResult cleanUpResult(Lookup.Template templ) {
1.998 - collectListeners(null, templ.getType());
1.999 -
1.1000 - return (reg == null) ? null : reg.get(templ.getType());
1.1001 - }
1.1002 -
1.1003 - public ArrayList<Class> beginTransaction(int ensure) {
1.1004 - return new ArrayList<Class>();
1.1005 - }
1.1006 -
1.1007 - public void endTransaction(ArrayList<Class> list, Set<AbstractLookup.R> allAffectedResults) {
1.1008 - if (list.size() == 1) {
1.1009 - // probably the most common case
1.1010 - collectListeners(allAffectedResults, list.get(0));
1.1011 - } else {
1.1012 - Iterator it = list.iterator();
1.1013 -
1.1014 - while (it.hasNext()) {
1.1015 - collectListeners(allAffectedResults, (Class) it.next());
1.1016 - }
1.1017 - }
1.1018 - }
1.1019 -
1.1020 - /** Notifies all listeners that are interested in changes in this class.
1.1021 - * Should be called from synchronized places.
1.1022 - * @param allAffectedResults adds Results into this set
1.1023 - * @param c the class that has changed
1.1024 - */
1.1025 - private void collectListeners(Set<AbstractLookup.R> allAffectedResults, Class c) {
1.1026 - if (reg == null) {
1.1027 - return;
1.1028 - }
1.1029 -
1.1030 - while (c != null) {
1.1031 - ReferenceToResult first = reg.get(c);
1.1032 - ReferenceIterator it = new ReferenceIterator(first);
1.1033 -
1.1034 - while (it.next()) {
1.1035 - AbstractLookup.R result = it.current().getResult();
1.1036 -
1.1037 - if (allAffectedResults != null) {
1.1038 - // add result
1.1039 - allAffectedResults.add(result);
1.1040 - }
1.1041 - }
1.1042 -
1.1043 - if (first != it.first()) {
1.1044 - if (it.first() == null) {
1.1045 - // we do not need have more results on this object
1.1046 - reg.remove(c);
1.1047 - } else {
1.1048 - // move the head of the list
1.1049 - reg.put(c, it.first());
1.1050 - }
1.1051 - }
1.1052 -
1.1053 - c = c.getSuperclass();
1.1054 - }
1.1055 -
1.1056 - if (reg.isEmpty()) {
1.1057 - // clean up the list of all results if we do not need them anymore
1.1058 - reg = null;
1.1059 - }
1.1060 - }
1.1061 -
1.1062 - /** Node in the tree.
1.1063 - */
1.1064 - static final class Node extends WeakReference<Class> implements Serializable {
1.1065 - static final long serialVersionUID = 3L;
1.1066 -
1.1067 - /** children nodes */
1.1068 - public ArrayList<Node> children;
1.1069 -
1.1070 - /** list of items assigned to this node (suspect to be subclasses) */
1.1071 - public Collection<Pair> items;
1.1072 -
1.1073 - /** Constructor.
1.1074 - */
1.1075 - public Node(Class clazz) {
1.1076 - super(clazz);
1.1077 - }
1.1078 -
1.1079 - /** Returns true if the object was deserialized also clears the serialized flag.
1.1080 - * @return true if so.
1.1081 - */
1.1082 - public boolean deserialized() {
1.1083 - if ((items == null) || items instanceof LinkedHashSet) {
1.1084 - return false;
1.1085 - }
1.1086 -
1.1087 - if (items.isEmpty()) {
1.1088 - items = null;
1.1089 - } else {
1.1090 - items = new LinkedHashSet<Pair>(items);
1.1091 - }
1.1092 -
1.1093 - return true;
1.1094 - }
1.1095 -
1.1096 - /** Marks this item as being deserialized.
1.1097 - */
1.1098 - public void markDeserialized() {
1.1099 - if (items == null || items == Collections.EMPTY_LIST) {
1.1100 - items = Collections.emptyList();
1.1101 - } else {
1.1102 - items = Collections.synchronizedCollection(items);
1.1103 - }
1.1104 - }
1.1105 -
1.1106 - /** Getter for the type associated with this node.
1.1107 - */
1.1108 - public Class<?> getType() {
1.1109 - Class<?> c = get();
1.1110 -
1.1111 - // if garbage collected, then return a garbage
1.1112 - return (c == null) ? Void.TYPE : c;
1.1113 - }
1.1114 -
1.1115 - /** Checks whether a node can represent an class.
1.1116 - */
1.1117 - public boolean accepts(Class<?> clazz) {
1.1118 - if (getType() == Object.class) {
1.1119 - return true;
1.1120 - }
1.1121 -
1.1122 - return getType().isAssignableFrom(clazz);
1.1123 - }
1.1124 -
1.1125 - /** Checks whether item is instance of this node.
1.1126 - */
1.1127 - public boolean accepts(AbstractLookup.Pair<?> item) {
1.1128 - if (getType() == Object.class) {
1.1129 - // Object.class
1.1130 - return true;
1.1131 - }
1.1132 -
1.1133 - return item.instanceOf(getType());
1.1134 - }
1.1135 -
1.1136 - /** Assings an item to this node.
1.1137 - * @param item the item
1.1138 - * @return true if item has been added as new
1.1139 - */
1.1140 - public boolean assignItem(InheritanceTree tree, AbstractLookup.Pair<?> item) {
1.1141 - if ((items == null) || (items == Collections.EMPTY_LIST)) {
1.1142 - items = new LinkedHashSet<Pair>();
1.1143 - items.add(item);
1.1144 -
1.1145 - return true;
1.1146 - }
1.1147 -
1.1148 - if (items.contains(item)) {
1.1149 - Iterator<Pair> it = items.iterator();
1.1150 - Pair old;
1.1151 - for (;;) {
1.1152 - old = it.next();
1.1153 - if (item.equals(old)) {
1.1154 - break;
1.1155 - }
1.1156 - }
1.1157 -
1.1158 - if (old != item) {
1.1159 - // replace the items there
1.1160 - item.setIndex(tree, old.getIndex());
1.1161 - }
1.1162 -
1.1163 - it.remove();
1.1164 - items.add(item);
1.1165 -
1.1166 - return false;
1.1167 - }
1.1168 -
1.1169 - items.add(item);
1.1170 -
1.1171 - return true;
1.1172 - }
1.1173 -
1.1174 - private Object writeReplace() {
1.1175 - return new R(this);
1.1176 - }
1.1177 -
1.1178 - @Override
1.1179 - public String toString() {
1.1180 - return "Node for " + get();
1.1181 - }
1.1182 - }
1.1183 - // End of class Node.
1.1184 -
1.1185 - private static final class R implements Serializable {
1.1186 - static final long serialVersionUID = 1L;
1.1187 - private static ClassLoader l;
1.1188 - private String clazzName;
1.1189 - private transient Class<?> clazz;
1.1190 - private ArrayList<Node> children;
1.1191 - private Collection<Pair> items;
1.1192 -
1.1193 - public R(Node n) {
1.1194 - this.clazzName = n.getType().getName();
1.1195 - this.children = n.children;
1.1196 -
1.1197 - if (n.items instanceof LinkedHashSet || (n.items == null)) {
1.1198 - this.items = n.items;
1.1199 - } else {
1.1200 - this.items = new LinkedHashSet<Pair>(n.items);
1.1201 - }
1.1202 - }
1.1203 -
1.1204 - private void readObject(ObjectInputStream ois)
1.1205 - throws IOException, ClassNotFoundException {
1.1206 - ois.defaultReadObject();
1.1207 -
1.1208 - if (l == null) {
1.1209 - l = Lookup.getDefault().lookup(ClassLoader.class);
1.1210 - }
1.1211 -
1.1212 - clazz = Class.forName(clazzName, false, l);
1.1213 - }
1.1214 -
1.1215 - private Object readResolve() throws ObjectStreamException {
1.1216 - Node n = new Node(clazz);
1.1217 - n.children = children;
1.1218 - n.items = items;
1.1219 - n.markDeserialized();
1.1220 -
1.1221 - return n;
1.1222 - }
1.1223 - }
1.1224 - // end of R
1.1225 -
1.1226 - static Enumeration<Object> arrayEn(Object[] object) {
1.1227 - return Collections.enumeration(Arrays.asList(object));
1.1228 - }
1.1229 - static <T> Enumeration<T> singletonEn(T object) {
1.1230 - return Collections.enumeration(Collections.singleton(object));
1.1231 - }
1.1232 - static <T> Enumeration<T> emptyEn() {
1.1233 - return Collections.enumeration(Collections.<T>emptyList());
1.1234 - }
1.1235 -
1.1236 - /** Just a marker class to be able to do instanceof and find out
1.1237 - * that this enumeration is not sorted
1.1238 - */
1.1239 - private static final class NeedsSortEnum extends LinkedList<Node>
1.1240 - implements Enumeration<Pair> {
1.1241 - private Enumeration<Pair> en;
1.1242 -
1.1243 - public NeedsSortEnum(Node n) {
1.1244 - add(n);
1.1245 - }
1.1246 -
1.1247 - private boolean ensureNext() {
1.1248 - for (;;) {
1.1249 - if (en != null && en.hasMoreElements()) {
1.1250 - return true;
1.1251 - }
1.1252 - if (isEmpty()) {
1.1253 - return false;
1.1254 - }
1.1255 -
1.1256 - Node n2 = poll();
1.1257 - if (n2.children != null) {
1.1258 - addAll(n2.children);
1.1259 - }
1.1260 -
1.1261 - if (n2.items != null && !n2.items.isEmpty()) {
1.1262 - en = Collections.enumeration(n2.items);
1.1263 - }
1.1264 - }
1.1265 - }
1.1266 -
1.1267 - public boolean hasMoreElements() {
1.1268 - return ensureNext();
1.1269 - }
1.1270 -
1.1271 - public Pair nextElement() {
1.1272 - if (!ensureNext()) {
1.1273 - throw new NoSuchElementException();
1.1274 - }
1.1275 - return en.nextElement();
1.1276 - }
1.1277 - }
1.1278 - // end of NeedsSortEnum
1.1279 -}