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

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