yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/YangInstanceIdentifier.java

   1 /*
   2  * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.data.api;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.annotations.Beta;
  15 import com.google.common.cache.CacheBuilder;
  16 import com.google.common.cache.CacheLoader;
  17 import com.google.common.cache.LoadingCache;
  18 import com.google.common.collect.ImmutableList;
  19 import com.google.common.collect.ImmutableMap;
  20 import com.google.common.collect.ImmutableSet;
  21 import com.google.common.collect.Iterables;
  22 import com.google.common.collect.Sets;
  23 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  24 import java.io.Serializable;
  25 import java.lang.reflect.Array;
  26 import java.util.AbstractMap.SimpleImmutableEntry;
  27 import java.util.ArrayList;
  28 import java.util.Arrays;
  29 import java.util.Collection;
  30 import java.util.Deque;
  31 import java.util.Iterator;
  32 import java.util.List;
  33 import java.util.Map;
  34 import java.util.Map.Entry;
  35 import java.util.Objects;
  36 import java.util.Optional;
  37 import java.util.Set;
  38 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  39 import java.util.function.Function;
  40 import org.eclipse.jdt.annotation.NonNull;
  41 import org.eclipse.jdt.annotation.Nullable;
  42 import org.opendaylight.yangtools.concepts.Builder;
  43 import org.opendaylight.yangtools.concepts.Immutable;
  44 import org.opendaylight.yangtools.concepts.Path;
  45 import org.opendaylight.yangtools.util.HashCodeBuilder;
  46 import org.opendaylight.yangtools.util.ImmutableOffsetMap;
  47 import org.opendaylight.yangtools.util.SharedSingletonMap;
  48 import org.opendaylight.yangtools.util.SingletonSet;
  49 import org.opendaylight.yangtools.yang.common.QName;
  50 import org.opendaylight.yangtools.yang.common.QNameModule;
  51 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetEntryNode;
  52
  53 /**
  54  * Unique identifier of a particular node instance in the data tree.
  55  *
  56  * <p>
  57  * Java representation of YANG Built-in type <code>instance-identifier</code>,
  58  * which conceptually is XPath expression minimized to uniquely identify element
  59  * in data tree which conforms to constraints maintained by YANG Model,
  60  * effectively this makes Instance Identifier a path to element in data tree.
  61  *
  62  * <p>
  63  * Constraints put in YANG specification on instance-identifier allowed it to be
  64  * effectively represented in Java and it's evaluation does not require
  65  * full-blown XPath processor.
  66  *
  67  * <p>
  68  * <h3>Path Arguments</h3>
  69  * Path to the node represented in instance identifier consists of
  70  * {@link PathArgument} which carries necessary information to uniquely identify
  71  * node on particular level in the subtree.
  72  *
  73  * <ul>
  74  * <li>{@link NodeIdentifier} - Identifier of node, which has cardinality
  75  * <code>0..1</code> in particular subtree in data tree.</li>
  76  * <li>{@link NodeIdentifierWithPredicates} - Identifier of node (list item),
  77  * which has cardinality <code>0..n</code>.</li>
  78  * <li>{@link NodeWithValue} - Identifier of instance <code>leaf</code> node or
  79  * <code>leaf-list</code> node.</li>
  80  * <li>{@link AugmentationIdentifier} - Identifier of instance of
  81  * <code>augmentation</code> node.</li>
  82  * </ul>
  83  *
  84  * @see <a href="http://tools.ietf.org/html/rfc6020#section-9.13">RFC6020</a>
  85  */
  86 // FIXME: 4.0.0: this concept needs to be moved to yang-common, as parser components need the ability to refer
  87 //               to data nodes -- most notably XPath expressions and {@code default} statement arguments need to be able
  88 //               to represent these.
  89 // FIXME: FixedYangInstanceIdentifier needs YangInstanceIdentifier initialized, but that includes initializing
  90 //        this field. Figure out a way out of this pickle.
  91 @SuppressFBWarnings("IC_SUPERCLASS_USES_SUBCLASS_DURING_INITIALIZATION")
  92 public abstract class YangInstanceIdentifier implements Path<YangInstanceIdentifier>, Immutable, Serializable {
  93     /**
  94      * An empty {@link YangInstanceIdentifier}. It corresponds to the path of the conceptual root of the YANG namespace.
  95      */
  96     public static final @NonNull YangInstanceIdentifier EMPTY = FixedYangInstanceIdentifier.EMPTY_INSTANCE;
  97
  98     private static final AtomicReferenceFieldUpdater<YangInstanceIdentifier, String> TOSTRINGCACHE_UPDATER =
  99             AtomicReferenceFieldUpdater.newUpdater(YangInstanceIdentifier.class, String.class, "toStringCache");
 100     private static final long serialVersionUID = 4L;
 101
 102     private final int hash;
 103     private transient volatile String toStringCache = null;
 104
 105     // Package-private to prevent outside subclassing
 106     YangInstanceIdentifier(final int hash) {
 107         this.hash = hash;
 108     }
 109
 110     abstract @NonNull YangInstanceIdentifier createRelativeIdentifier(int skipFromRoot);
 111
 112     abstract @Nullable Collection<PathArgument> tryPathArguments();
 113
 114     abstract @Nullable Collection<PathArgument> tryReversePathArguments();
 115
 116     /**
 117      * Check if this instance identifier has empty path arguments, e.g. it is
 118      * empty and corresponds to {@link #EMPTY}.
 119      *
 120      * @return True if this instance identifier is empty, false otherwise.
 121      */
 122     public abstract boolean isEmpty();
 123
 124     /**
 125      * Return an optimized version of this identifier, useful when the identifier
 126      * will be used very frequently.
 127      *
 128      * @return A optimized equivalent instance.
 129      */
 130     @Beta
 131     public abstract @NonNull YangInstanceIdentifier toOptimized();
 132
 133     /**
 134      * Return the conceptual parent {@link YangInstanceIdentifier}, which has
 135      * one item less in {@link #getPathArguments()}.
 136      *
 137      * @return Parent {@link YangInstanceIdentifier}, or null if this object is {@link #EMPTY}.
 138      */
 139     public abstract @Nullable YangInstanceIdentifier getParent();
 140
 141     /**
 142      * Return the ancestor {@link YangInstanceIdentifier} with a particular depth, e.g. number of path arguments.
 143      *
 144      * @param depth Ancestor depth
 145      * @return Ancestor {@link YangInstanceIdentifier}
 146      * @throws IllegalArgumentException if the specified depth is negative or is greater than the depth of this object.
 147      */
 148     public abstract @NonNull YangInstanceIdentifier getAncestor(int depth);
 149
 150     /**
 151      * Returns an ordered iteration of path arguments.
 152      *
 153      * @return Immutable iteration of path arguments.
 154      */
 155     public abstract @NonNull List<PathArgument> getPathArguments();
 156
 157     /**
 158      * Returns an iterable of path arguments in reverse order. This is useful
 159      * when walking up a tree organized this way.
 160      *
 161      * @return Immutable iterable of path arguments in reverse order.
 162      */
 163     public abstract @NonNull List<PathArgument> getReversePathArguments();
 164
 165     /**
 166      * Returns the last PathArgument. This is equivalent of iterating
 167      * to the last element of the iterable returned by {@link #getPathArguments()}.
 168      *
 169      * @return The last past argument, or null if there are no PathArguments.
 170      */
 171     public abstract PathArgument getLastPathArgument();
 172
 173     public static @NonNull YangInstanceIdentifier create(final Iterable<? extends PathArgument> path) {
 174         if (Iterables.isEmpty(path)) {
 175             return EMPTY;
 176         }
 177
 178         final HashCodeBuilder<PathArgument> hash = new HashCodeBuilder<>();
 179         for (PathArgument a : path) {
 180             hash.addArgument(a);
 181         }
 182
 183         return FixedYangInstanceIdentifier.create(path, hash.build());
 184     }
 185
 186     public static @NonNull YangInstanceIdentifier create(final PathArgument... path) {
 187         // We are forcing a copy, since we cannot trust the user
 188         return create(Arrays.asList(path));
 189     }
 190
 191     /**
 192      * Create a {@link YangInstanceIdentifier} by taking a snapshot of provided path and iterating it backwards.
 193      *
 194      * @param pathTowardsRoot Path towards root
 195      * @return A {@link YangInstanceIdentifier} instance
 196      * @throws NullPointerException if {@code pathTowardsRoot} or any of its members is null
 197      */
 198     public static @NonNull YangInstanceIdentifier createReverse(final Deque<PathArgument> pathTowardsRoot) {
 199         final ImmutableList.Builder<PathArgument> builder = ImmutableList.builderWithExpectedSize(
 200             pathTowardsRoot.size());
 201         pathTowardsRoot.descendingIterator().forEachRemaining(builder::add);
 202         return YangInstanceIdentifier.create(builder.build());
 203     }
 204
 205     /**
 206      * Create a {@link YangInstanceIdentifier} by walking specified stack backwards and extracting path components
 207      * from it.
 208      *
 209      * @param stackTowardsRoot Stack towards root,
 210      * @return A {@link YangInstanceIdentifier} instance
 211      * @throws NullPointerException if {@code pathTowardsRoot} is null
 212      */
 213     public static <T> @NonNull YangInstanceIdentifier createReverse(final Deque<? extends T> stackTowardsRoot,
 214             final Function<T, PathArgument> function) {
 215         final ImmutableList.Builder<PathArgument> builder = ImmutableList.builderWithExpectedSize(
 216             stackTowardsRoot.size());
 217         final Iterator<? extends T> it = stackTowardsRoot.descendingIterator();
 218         while (it.hasNext()) {
 219             builder.add(function.apply(it.next()));
 220         }
 221         return YangInstanceIdentifier.create(builder.build());
 222     }
 223
 224     boolean pathArgumentsEqual(final YangInstanceIdentifier other) {
 225         return Iterables.elementsEqual(getPathArguments(), other.getPathArguments());
 226     }
 227
 228     @Override
 229     public boolean equals(final Object obj) {
 230         if (this == obj) {
 231             return true;
 232         }
 233         if (!(obj instanceof YangInstanceIdentifier)) {
 234             return false;
 235         }
 236         YangInstanceIdentifier other = (YangInstanceIdentifier) obj;
 237         if (this.hashCode() != obj.hashCode()) {
 238             return false;
 239         }
 240
 241         return pathArgumentsEqual(other);
 242     }
 243
 244     /**
 245      * Constructs a new Instance Identifier with new {@link NodeIdentifier} added to the end of path arguments.
 246      *
 247      * @param name QName of {@link NodeIdentifier}
 248      * @return Instance Identifier with additional path argument added to the end.
 249      */
 250     public final @NonNull YangInstanceIdentifier node(final QName name) {
 251         return node(new NodeIdentifier(name));
 252     }
 253
 254     /**
 255      * Constructs a new Instance Identifier with new {@link PathArgument} added to the end of path arguments.
 256      *
 257      * @param arg Path argument which should be added to the end
 258      * @return Instance Identifier with additional path argument added to the end.
 259      */
 260     public final @NonNull YangInstanceIdentifier node(final PathArgument arg) {
 261         return new StackedYangInstanceIdentifier(this, arg, HashCodeBuilder.nextHashCode(hash, arg));
 262     }
 263
 264     /**
 265      * Get the relative path from an ancestor. This method attempts to perform
 266      * the reverse of concatenating a base (ancestor) and a path.
 267      *
 268      * @param ancestor
 269      *            Ancestor against which the relative path should be calculated
 270      * @return This object's relative path from parent, or Optional.absent() if
 271      *         the specified parent is not in fact an ancestor of this object.
 272      */
 273     public Optional<YangInstanceIdentifier> relativeTo(final YangInstanceIdentifier ancestor) {
 274         if (this == ancestor) {
 275             return Optional.of(EMPTY);
 276         }
 277         if (ancestor.isEmpty()) {
 278             return Optional.of(this);
 279         }
 280
 281         final Iterator<PathArgument> lit = getPathArguments().iterator();
 282         final Iterator<PathArgument> oit = ancestor.getPathArguments().iterator();
 283         int common = 0;
 284
 285         while (oit.hasNext()) {
 286             // Ancestor is not really an ancestor
 287             if (!lit.hasNext() || !lit.next().equals(oit.next())) {
 288                 return Optional.empty();
 289             }
 290
 291             ++common;
 292         }
 293
 294         if (common == 0) {
 295             return Optional.of(this);
 296         }
 297         if (!lit.hasNext()) {
 298             return Optional.of(EMPTY);
 299         }
 300
 301         return Optional.of(createRelativeIdentifier(common));
 302     }
 303
 304     @Override
 305     public final boolean contains(final YangInstanceIdentifier other) {
 306         if (this == other) {
 307             return true;
 308         }
 309
 310         checkArgument(other != null, "other should not be null");
 311         final Iterator<PathArgument> lit = getPathArguments().iterator();
 312         final Iterator<PathArgument> oit = other.getPathArguments().iterator();
 313
 314         while (lit.hasNext()) {
 315             if (!oit.hasNext()) {
 316                 return false;
 317             }
 318
 319             if (!lit.next().equals(oit.next())) {
 320                 return false;
 321             }
 322         }
 323
 324         return true;
 325     }
 326
 327     @Override
 328     public final String toString() {
 329         /*
 330          * The toStringCache is safe, since the object contract requires
 331          * immutability of the object and all objects referenced from this
 332          * object.
 333          * Used lists, maps are immutable. Path Arguments (elements) are also
 334          * immutable, since the PathArgument contract requires immutability.
 335          * The cache is thread-safe - if multiple computations occurs at the
 336          * same time, cache will be overwritten with same result.
 337          */
 338         String ret = toStringCache;
 339         if (ret == null) {
 340             final StringBuilder builder = new StringBuilder("/");
 341             PathArgument prev = null;
 342             for (PathArgument argument : getPathArguments()) {
 343                 if (prev != null) {
 344                     builder.append('/');
 345                 }
 346                 builder.append(argument.toRelativeString(prev));
 347                 prev = argument;
 348             }
 349
 350             ret = builder.toString();
 351             TOSTRINGCACHE_UPDATER.lazySet(this, ret);
 352         }
 353         return ret;
 354     }
 355
 356     @Override
 357     public final int hashCode() {
 358         /*
 359          * The caching is safe, since the object contract requires
 360          * immutability of the object and all objects referenced from this
 361          * object.
 362          * Used lists, maps are immutable. Path Arguments (elements) are also
 363          * immutable, since the PathArgument contract requires immutability.
 364          */
 365         return hash;
 366     }
 367
 368     @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
 369             justification = "https://github.com/spotbugs/spotbugs/issues/811")
 370     private static int hashCode(final Object value) {
 371         if (value == null) {
 372             return 0;
 373         }
 374
 375         if (byte[].class.equals(value.getClass())) {
 376             return Arrays.hashCode((byte[]) value);
 377         }
 378
 379         if (value.getClass().isArray()) {
 380             int hash = 0;
 381             int length = Array.getLength(value);
 382             for (int i = 0; i < length; i++) {
 383                 hash += Objects.hashCode(Array.get(value, i));
 384             }
 385
 386             return hash;
 387         }
 388
 389         return Objects.hashCode(value);
 390     }
 391
 392     final Object writeReplace() {
 393         return new YIDv1(this);
 394     }
 395
 396     // Static factories & helpers
 397
 398     /**
 399      * Returns a new InstanceIdentifier with only one path argument of type {@link NodeIdentifier} with supplied
 400      * QName.
 401      *
 402      * @param name QName of first node identifier
 403      * @return Instance Identifier with only one path argument of type {@link NodeIdentifier}
 404      */
 405     public static @NonNull YangInstanceIdentifier of(final QName name) {
 406         return create(new NodeIdentifier(name));
 407     }
 408
 409     /**
 410      * Returns new builder for InstanceIdentifier with empty path arguments.
 411      *
 412      * @return new builder for InstanceIdentifier with empty path arguments.
 413      */
 414     public static @NonNull InstanceIdentifierBuilder builder() {
 415         return new YangInstanceIdentifierBuilder();
 416     }
 417
 418     /**
 419      * Returns new builder for InstanceIdentifier with path arguments copied from original instance identifier.
 420      *
 421      * @param origin InstanceIdentifier from which path arguments are copied.
 422      * @return new builder for InstanceIdentifier with path arguments copied from original instance identifier.
 423      */
 424     public static @NonNull InstanceIdentifierBuilder builder(final YangInstanceIdentifier origin) {
 425         return new YangInstanceIdentifierBuilder(origin.getPathArguments(), origin.hashCode());
 426     }
 427
 428     /**
 429      * Path argument / component of InstanceIdentifier.
 430      * Path argument uniquely identifies node in data tree on particular
 431      * level.
 432      *
 433      * <p>
 434      * This interface itself is used as common parent for actual
 435      * path arguments types and should not be implemented by user code.
 436      *
 437      * <p>
 438      * Path arguments SHOULD contain only minimum of information
 439      * required to uniquely identify node on particular subtree level.
 440      *
 441      * <p>
 442      * For actual path arguments types see:
 443      * <ul>
 444      * <li>{@link NodeIdentifier} - Identifier of container or leaf
 445      * <li>{@link NodeIdentifierWithPredicates} - Identifier of list entries, which have key defined
 446      * <li>{@link AugmentationIdentifier} - Identifier of augmentation
 447      * <li>{@link NodeWithValue} - Identifier of leaf-list entry
 448      * </ul>
 449      */
 450     public interface PathArgument extends Comparable<PathArgument>, Immutable, Serializable {
 451         /**
 452          * Returns unique QName of data node as defined in YANG Schema, if available.
 453          *
 454          * @return Node type
 455          * @throws UnsupportedOperationException if node type is not applicable, for example in case of an augmentation.
 456          */
 457         @NonNull QName getNodeType();
 458
 459         /**
 460          * Return the string representation of this object for use in context
 461          * provided by a previous object. This method can be implemented in
 462          * terms of {@link #toString()}, but implementations are encourage to
 463          * reuse any context already emitted by the previous object.
 464          *
 465          * @param previous Previous path argument
 466          * @return String representation
 467          */
 468         @NonNull String toRelativeString(PathArgument previous);
 469     }
 470
 471     private abstract static class AbstractPathArgument implements PathArgument {
 472         private static final long serialVersionUID = -4546547994250849340L;
 473         private final @NonNull QName nodeType;
 474         private transient volatile int hashValue;
 475
 476         protected AbstractPathArgument(final QName nodeType) {
 477             this.nodeType = requireNonNull(nodeType);
 478         }
 479
 480         @Override
 481         public final QName getNodeType() {
 482             return nodeType;
 483         }
 484
 485         @Override
 486         @SuppressWarnings("checkstyle:parameterName")
 487         public int compareTo(final PathArgument o) {
 488             return nodeType.compareTo(o.getNodeType());
 489         }
 490
 491         protected int hashCodeImpl() {
 492             return 31 + getNodeType().hashCode();
 493         }
 494
 495         @Override
 496         public final int hashCode() {
 497             int local;
 498             return (local = hashValue) != 0 ? local : (hashValue = hashCodeImpl());
 499         }
 500
 501         @Override
 502         public boolean equals(final Object obj) {
 503             if (this == obj) {
 504                 return true;
 505             }
 506             if (obj == null || this.getClass() != obj.getClass()) {
 507                 return false;
 508             }
 509
 510             return getNodeType().equals(((AbstractPathArgument)obj).getNodeType());
 511         }
 512
 513         @Override
 514         public String toString() {
 515             return getNodeType().toString();
 516         }
 517
 518         @Override
 519         public String toRelativeString(final PathArgument previous) {
 520             if (previous instanceof AbstractPathArgument) {
 521                 final QNameModule mod = previous.getNodeType().getModule();
 522                 if (getNodeType().getModule().equals(mod)) {
 523                     return getNodeType().getLocalName();
 524                 }
 525             }
 526
 527             return getNodeType().toString();
 528         }
 529
 530         abstract Object writeReplace();
 531     }
 532
 533     /**
 534      * Simple path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.ContainerNode} or
 535      * {@link org.opendaylight.yangtools.yang.data.api.schema.LeafNode} leaf in particular subtree.
 536      */
 537     public static final class NodeIdentifier extends AbstractPathArgument {
 538         private static final long serialVersionUID = -2255888212390871347L;
 539         private static final LoadingCache<QName, NodeIdentifier> CACHE = CacheBuilder.newBuilder().weakValues()
 540                 .build(new CacheLoader<QName, NodeIdentifier>() {
 541                     @Override
 542                     public NodeIdentifier load(final QName key) {
 543                         return new NodeIdentifier(key);
 544                     }
 545                 });
 546
 547         public NodeIdentifier(final QName node) {
 548             super(node);
 549         }
 550
 551         /**
 552          * Return a NodeIdentifier for a particular QName. Unlike the constructor, this factory method uses a global
 553          * instance cache, resulting in object reuse for equal inputs.
 554          *
 555          * @param node Node's QName
 556          * @return A {@link NodeIdentifier}
 557          */
 558         public static @NonNull NodeIdentifier create(final QName node) {
 559             return CACHE.getUnchecked(node);
 560         }
 561
 562         @Override
 563         Object writeReplace() {
 564             return new NIv1(this);
 565         }
 566     }
 567
 568     /**
 569      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode} leaf
 570      * overall data tree.
 571      */
 572     public abstract static class NodeIdentifierWithPredicates extends AbstractPathArgument {
 573         private static final class Singleton extends NodeIdentifierWithPredicates {
 574             private static final long serialVersionUID = 1L;
 575
 576             private final @NonNull QName key;
 577             private final @NonNull Object value;
 578
 579             Singleton(final QName node, final QName key, final Object value) {
 580                 super(node);
 581                 this.key = requireNonNull(key);
 582                 this.value = requireNonNull(value);
 583             }
 584
 585             @Override
 586             public SingletonSet<Entry<QName, Object>> entrySet() {
 587                 return SingletonSet.of(new SimpleImmutableEntry<>(key, value));
 588             }
 589
 590             @Override
 591             public SingletonSet<QName> keySet() {
 592                 return SingletonSet.of(key);
 593             }
 594
 595             @Override
 596             public SingletonSet<Object> values() {
 597                 return SingletonSet.of(value);
 598             }
 599
 600             @Override
 601             public int size() {
 602                 return 1;
 603             }
 604
 605             @Override
 606             public ImmutableMap<QName, Object> asMap() {
 607                 return ImmutableMap.of(key, value);
 608             }
 609
 610             @Override
 611             boolean equalMapping(final NodeIdentifierWithPredicates other) {
 612                 final Singleton single = (Singleton) other;
 613                 return key.equals(single.key) && Objects.deepEquals(value, single.value);
 614             }
 615
 616             @Override
 617             Object keyValue(final QName qname) {
 618                 return key.equals(qname) ? value : null;
 619             }
 620         }
 621
 622         private static final class Regular extends NodeIdentifierWithPredicates {
 623             private static final long serialVersionUID = 1L;
 624
 625             private final @NonNull Map<QName, Object> keyValues;
 626
 627             Regular(final QName node, final Map<QName, Object> keyValues) {
 628                 super(node);
 629                 this.keyValues = requireNonNull(keyValues);
 630             }
 631
 632             @Override
 633             public Set<Entry<QName, Object>> entrySet() {
 634                 return keyValues.entrySet();
 635             }
 636
 637             @Override
 638             public Set<QName> keySet() {
 639                 return keyValues.keySet();
 640             }
 641
 642             @Override
 643             public Collection<Object> values() {
 644                 return keyValues.values();
 645             }
 646
 647             @Override
 648             public int size() {
 649                 return keyValues.size();
 650             }
 651
 652             @Override
 653             public Map<QName, Object> asMap() {
 654                 return keyValues;
 655             }
 656
 657             @Override
 658             Object keyValue(final QName qname) {
 659                 return keyValues.get(qname);
 660             }
 661
 662             @Override
 663             boolean equalMapping(final NodeIdentifierWithPredicates other) {
 664                 final Map<QName, Object> otherKeyValues = ((Regular) other).keyValues;
 665                 // TODO: benchmark to see if just calling equals() on the two maps is not faster
 666                 if (keyValues == otherKeyValues) {
 667                     return true;
 668                 }
 669                 if (keyValues.size() != otherKeyValues.size()) {
 670                     return false;
 671                 }
 672
 673                 for (Entry<QName, Object> entry : entrySet()) {
 674                     final Object otherValue = otherKeyValues.get(entry.getKey());
 675                     if (otherValue == null || !Objects.deepEquals(entry.getValue(), otherValue)) {
 676                         return false;
 677                     }
 678                 }
 679
 680                 return true;
 681             }
 682         }
 683
 684         private static final long serialVersionUID = -4787195606494761540L;
 685
 686         NodeIdentifierWithPredicates(final QName node) {
 687             super(node);
 688         }
 689
 690         public static @NonNull NodeIdentifierWithPredicates of(final QName node) {
 691             return new Regular(node, ImmutableMap.of());
 692         }
 693
 694         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final QName key, final Object value) {
 695             return new Singleton(node, key, value);
 696         }
 697
 698         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final Entry<QName, Object> entry) {
 699             return of(node, entry.getKey(), entry.getValue());
 700         }
 701
 702         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final Map<QName, Object> keyValues) {
 703             return keyValues.size() == 1 ? of(keyValues, node)
 704                     // Retains ImmutableMap for empty maps. For larger sizes uses a shared key set.
 705                     : new Regular(node, ImmutableOffsetMap.unorderedCopyOf(keyValues));
 706         }
 707
 708         public static @NonNull NodeIdentifierWithPredicates of(final QName node,
 709                 final ImmutableOffsetMap<QName, Object> keyValues) {
 710             return keyValues.size() == 1 ? of(keyValues, node) : new Regular(node, keyValues);
 711         }
 712
 713         @Deprecated
 714         public static @NonNull NodeIdentifierWithPredicates of(final QName node,
 715                 final SharedSingletonMap<QName, Object> keyValues) {
 716             return of(node, keyValues.getEntry());
 717         }
 718
 719         private static @NonNull NodeIdentifierWithPredicates of(final Map<QName, Object> keyValues, final QName node) {
 720             return of(node, keyValues.entrySet().iterator().next());
 721         }
 722
 723         /**
 724          * Return the set of predicates keys and values. Keys are guaranteeed to be unique.
 725          *
 726          * @return Predicate set.
 727          */
 728         @Beta
 729         public abstract @NonNull Set<Entry<QName, Object>> entrySet();
 730
 731         /**
 732          * Return the predicate key in the iteration order of {@link #entrySet()}.
 733          *
 734          * @return Predicate values.
 735          */
 736         @Beta
 737         public abstract @NonNull Set<QName> keySet();
 738
 739         /**
 740          * Return the predicate values in the iteration order of {@link #entrySet()}.
 741          *
 742          * @return Predicate values.
 743          */
 744         @Beta
 745         public abstract @NonNull Collection<Object> values();
 746
 747         @Beta
 748         public final @Nullable Object getValue(final QName key) {
 749             return keyValue(requireNonNull(key));
 750         }
 751
 752         @Beta
 753         public final <T> @Nullable T getValue(final QName key, final Class<T> valueClass) {
 754             return valueClass.cast(getValue(key));
 755         }
 756
 757         /**
 758          * Return the number of predicates present.
 759          *
 760          * @return The number of predicates present.
 761          */
 762         @Beta
 763         public abstract int size();
 764
 765         /**
 766          * A Map-like view of this identifier's predicates. The view is expected to be stable and effectively-immutable.
 767          *
 768          * @return Map of predicates.
 769          * @deprecated This method in a provisional one. It can be used in the code base, but users requiring it should
 770          *             contact <a href="mailto:yangtools-dev@lists.opendaylight.org">yangtools-dev</a> for migration
 771          *             guidelines. Callers are strongly encouraged to explore {@link #entrySet()}, {@link #size()},
 772          *             {@link #values()} and {@link #keySet()} as an alternative.
 773          */
 774         @Beta
 775         @Deprecated
 776         // FIXME: 4.0.0: evaluate the real usefulness of this. The problem here is Map.hashCode() and Map.equals(),
 777         //               which limits our options.
 778         public abstract @NonNull Map<QName, Object> asMap();
 779
 780         @Override
 781         protected final int hashCodeImpl() {
 782             int result = 31 * super.hashCodeImpl();
 783             for (Entry<QName, Object> entry : entrySet()) {
 784                 result += entry.getKey().hashCode() + YangInstanceIdentifier.hashCode(entry.getValue());
 785             }
 786             return result;
 787         }
 788
 789         @Override
 790         @SuppressWarnings("checkstyle:equalsHashCode")
 791         public final boolean equals(final Object obj) {
 792             return super.equals(obj) && equalMapping((NodeIdentifierWithPredicates) obj);
 793         }
 794
 795         abstract boolean equalMapping(NodeIdentifierWithPredicates other);
 796
 797         abstract @Nullable Object keyValue(@NonNull QName qname);
 798
 799         @Override
 800         public final String toString() {
 801             return super.toString() + '[' + asMap() + ']';
 802         }
 803
 804         @Override
 805         public final String toRelativeString(final PathArgument previous) {
 806             return super.toRelativeString(previous) + '[' + asMap() + ']';
 807         }
 808
 809         @Override
 810         final Object writeReplace() {
 811             return new NIPv2(this);
 812         }
 813     }
 814
 815     /**
 816      * Simple path argument identifying a {@link LeafSetEntryNode} leaf
 817      * overall data tree.
 818      */
 819     public static final class NodeWithValue<T> extends AbstractPathArgument {
 820         private static final long serialVersionUID = -3637456085341738431L;
 821
 822         private final T value;
 823
 824         public NodeWithValue(final QName node, final T value) {
 825             super(node);
 826             this.value = value;
 827         }
 828
 829         public T getValue() {
 830             return value;
 831         }
 832
 833         @Override
 834         protected int hashCodeImpl() {
 835             final int prime = 31;
 836             int result = super.hashCodeImpl();
 837             result = prime * result + YangInstanceIdentifier.hashCode(value);
 838             return result;
 839         }
 840
 841         @Override
 842         @SuppressWarnings("checkstyle:equalsHashCode")
 843         public boolean equals(final Object obj) {
 844             if (!super.equals(obj)) {
 845                 return false;
 846             }
 847             final NodeWithValue<?> other = (NodeWithValue<?>) obj;
 848             return Objects.deepEquals(value, other.value);
 849         }
 850
 851         @Override
 852         public String toString() {
 853             return super.toString() + '[' + value + ']';
 854         }
 855
 856         @Override
 857         public String toRelativeString(final PathArgument previous) {
 858             return super.toRelativeString(previous) + '[' + value + ']';
 859         }
 860
 861         @Override
 862         Object writeReplace() {
 863             return new NIVv1(this);
 864         }
 865     }
 866
 867     /**
 868      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode}
 869      * node in particular subtree.
 870      *
 871      * <p>
 872      * Augmentation is uniquely identified by set of all possible child nodes.
 873      * This is possible
 874      * to identify instance of augmentation,
 875      * since RFC6020 states that <code>augment</code> that augment
 876      * statement must not add multiple nodes from same namespace
 877      * / module to the target node.
 878      *
 879      * @see <a href="http://tools.ietf.org/html/rfc6020#section-7.15">RFC6020</a>
 880      */
 881     public static final class AugmentationIdentifier implements PathArgument {
 882         private static final long serialVersionUID = -8122335594681936939L;
 883
 884         private static final LoadingCache<ImmutableSet<QName>, AugmentationIdentifier> CACHE = CacheBuilder.newBuilder()
 885                 .weakValues().build(new CacheLoader<ImmutableSet<QName>, AugmentationIdentifier>() {
 886                     @Override
 887                     public AugmentationIdentifier load(final ImmutableSet<QName> key) {
 888                         return new AugmentationIdentifier(key);
 889                     }
 890                 });
 891
 892         private final @NonNull ImmutableSet<QName> childNames;
 893
 894         @Override
 895         public QName getNodeType() {
 896             // This should rather throw exception than return always null
 897             throw new UnsupportedOperationException("Augmentation node has no QName");
 898         }
 899
 900         /**
 901          * Construct new augmentation identifier using supplied set of possible
 902          * child nodes.
 903          *
 904          * @param childNames
 905          *            Set of possible child nodes.
 906          */
 907         public AugmentationIdentifier(final ImmutableSet<QName> childNames) {
 908             this.childNames = requireNonNull(childNames);
 909         }
 910
 911         /**
 912          * Construct new augmentation identifier using supplied set of possible
 913          * child nodes.
 914          *
 915          * @param childNames
 916          *            Set of possible child nodes.
 917          */
 918         public AugmentationIdentifier(final Set<QName> childNames) {
 919             this.childNames = ImmutableSet.copyOf(childNames);
 920         }
 921
 922         /**
 923          * Return an AugmentationIdentifier for a particular set of QNames. Unlike the constructor, this factory method
 924          * uses a global instance cache, resulting in object reuse for equal inputs.
 925          *
 926          * @param childNames Set of possible child nodes
 927          * @return An {@link AugmentationIdentifier}
 928          */
 929         public static @NonNull AugmentationIdentifier create(final ImmutableSet<QName> childNames) {
 930             return CACHE.getUnchecked(childNames);
 931         }
 932
 933         /**
 934          * Return an AugmentationIdentifier for a particular set of QNames. Unlike the constructor, this factory method
 935          * uses a global instance cache, resulting in object reuse for equal inputs.
 936          *
 937          * @param childNames Set of possible child nodes
 938          * @return An {@link AugmentationIdentifier}
 939          */
 940         public static @NonNull AugmentationIdentifier create(final Set<QName> childNames) {
 941             final AugmentationIdentifier existing = CACHE.getIfPresent(childNames);
 942             return existing != null ? existing : create(ImmutableSet.copyOf(childNames));
 943         }
 944
 945         /**
 946          * Returns set of all possible child nodes.
 947          *
 948          * @return set of all possible child nodes.
 949          */
 950         public @NonNull Set<QName> getPossibleChildNames() {
 951             return childNames;
 952         }
 953
 954         @Override
 955         public String toString() {
 956             return "AugmentationIdentifier{" + "childNames=" + childNames + '}';
 957         }
 958
 959         @Override
 960         public String toRelativeString(final PathArgument previous) {
 961             return toString();
 962         }
 963
 964         @Override
 965         public boolean equals(final Object obj) {
 966             if (this == obj) {
 967                 return true;
 968             }
 969             if (!(obj instanceof AugmentationIdentifier)) {
 970                 return false;
 971             }
 972
 973             AugmentationIdentifier that = (AugmentationIdentifier) obj;
 974             return childNames.equals(that.childNames);
 975         }
 976
 977         @Override
 978         public int hashCode() {
 979             return childNames.hashCode();
 980         }
 981
 982         @Override
 983         @SuppressWarnings("checkstyle:parameterName")
 984         public int compareTo(final PathArgument o) {
 985             if (!(o instanceof AugmentationIdentifier)) {
 986                 return -1;
 987             }
 988             AugmentationIdentifier other = (AugmentationIdentifier) o;
 989             Set<QName> otherChildNames = other.getPossibleChildNames();
 990             int thisSize = childNames.size();
 991             int otherSize = otherChildNames.size();
 992             if (thisSize == otherSize) {
 993                 // Quick Set-based comparison
 994                 if (childNames.equals(otherChildNames)) {
 995                     return 0;
 996                 }
 997
 998                 // We already know the sets are not equal, but have equal size, hence the sets differ in their elements,
 999                 // but potentially share a common set of elements. The most consistent way of comparing them is using
1000                 // total ordering defined by QName's compareTo. Hence convert both sets to lists ordered
1001                 // by QName.compareTo() and decide on the first differing element.
1002                 final List<QName> diff = new ArrayList<>(Sets.symmetricDifference(childNames, otherChildNames));
1003                 verify(!diff.isEmpty(), "Augmentation identifiers %s and %s report no difference", this, o);
1004                 diff.sort(QName::compareTo);
1005                 return childNames.contains(diff.get(0)) ? -1 : 1;
1006             } else if (thisSize < otherSize) {
1007                 return 1;
1008             } else {
1009                 return -1;
1010             }
1011         }
1012
1013         private Object writeReplace() {
1014             return new AIv1(this);
1015         }
1016     }
1017
1018     /**
1019      * Fluent Builder of Instance Identifier instances.
1020      */
1021     public interface InstanceIdentifierBuilder extends Builder<YangInstanceIdentifier> {
1022         /**
1023          * Adds a {@link PathArgument} to path arguments of resulting instance identifier.
1024          *
1025          * @param arg A {@link PathArgument} to be added
1026          * @return this builder
1027          */
1028         @NonNull InstanceIdentifierBuilder node(PathArgument arg);
1029
1030         /**
1031          * Adds {@link NodeIdentifier} with supplied QName to path arguments of resulting instance identifier.
1032          *
1033          * @param nodeType QName of {@link NodeIdentifier} which will be added
1034          * @return this builder
1035          */
1036         @NonNull InstanceIdentifierBuilder node(QName nodeType);
1037
1038         /**
1039          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key values to path arguments of resulting
1040          * instance identifier.
1041          *
1042          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
1043          * @param keyValues Map of key components and their respective values for {@link NodeIdentifierWithPredicates}
1044          * @return this builder
1045          */
1046         @NonNull InstanceIdentifierBuilder nodeWithKey(QName nodeType, Map<QName, Object> keyValues);
1047
1048         /**
1049          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key, value.
1050          *
1051          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
1052          * @param key QName of key which will be added
1053          * @param value value of key which will be added
1054          * @return this builder
1055          */
1056         @NonNull InstanceIdentifierBuilder nodeWithKey(QName nodeType, QName key, Object value);
1057
1058         /**
1059          * Adds a collection of {@link PathArgument}s to path arguments of resulting instance identifier.
1060          *
1061          * @param args {@link PathArgument}s to be added
1062          * @return this builder
1063          * @throws NullPointerException if any of the arguments is null
1064          */
1065         @Beta
1066         @NonNull InstanceIdentifierBuilder append(Collection<? extends PathArgument> args);
1067
1068         /**
1069          * Adds a collection of {@link PathArgument}s to path arguments of resulting instance identifier.
1070          *
1071          * @param args {@link PathArgument}s to be added
1072          * @return this builder
1073          * @throws NullPointerException if any of the arguments is null
1074          */
1075         @Beta
1076         default @NonNull InstanceIdentifierBuilder append(final PathArgument... args) {
1077             return append(Arrays.asList(args));
1078         }
1079
1080         /**
1081          * Builds an {@link YangInstanceIdentifier} with path arguments from this builder.
1082          *
1083          * @return {@link YangInstanceIdentifier}
1084          */
1085         @Override
1086         YangInstanceIdentifier build();
1087     }
1088 }