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