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