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