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

   1 /*
   2  * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.data.api;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.annotations.Beta;
  15 import com.google.common.cache.CacheBuilder;
  16 import com.google.common.cache.CacheLoader;
  17 import com.google.common.cache.LoadingCache;
  18 import com.google.common.collect.ImmutableList;
  19 import com.google.common.collect.ImmutableMap;
  20 import com.google.common.collect.ImmutableSet;
  21 import com.google.common.collect.Iterables;
  22 import com.google.common.collect.Sets;
  23 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  24 import java.io.Serializable;
  25 import java.lang.reflect.Array;
  26 import java.util.AbstractMap.SimpleImmutableEntry;
  27 import java.util.ArrayList;
  28 import java.util.Arrays;
  29 import java.util.Collection;
  30 import java.util.Deque;
  31 import java.util.Iterator;
  32 import java.util.List;
  33 import java.util.Map;
  34 import java.util.Map.Entry;
  35 import java.util.Objects;
  36 import java.util.Optional;
  37 import java.util.Set;
  38 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  39 import java.util.function.Function;
  40 import org.eclipse.jdt.annotation.NonNull;
  41 import org.eclipse.jdt.annotation.Nullable;
  42 import org.opendaylight.yangtools.concepts.Builder;
  43 import org.opendaylight.yangtools.concepts.Immutable;
  44 import org.opendaylight.yangtools.concepts.Path;
  45 import org.opendaylight.yangtools.util.HashCodeBuilder;
  46 import org.opendaylight.yangtools.util.ImmutableOffsetMap;
  47 import org.opendaylight.yangtools.util.SharedSingletonMap;
  48 import org.opendaylight.yangtools.util.SingletonSet;
  49 import org.opendaylight.yangtools.yang.common.QName;
  50 import org.opendaylight.yangtools.yang.common.QNameModule;
  51 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetEntryNode;
  52
  53 /**
  54  * Unique identifier of a particular node instance in the data tree.
  55  *
  56  * <p>
  57  * Java representation of YANG Built-in type <code>instance-identifier</code>,
  58  * which conceptually is XPath expression minimized to uniquely identify element
  59  * in data tree which conforms to constraints maintained by YANG Model,
  60  * effectively this makes Instance Identifier a path to element in data tree.
  61  *
  62  * <p>
  63  * Constraints put in YANG specification on instance-identifier allowed it to be
  64  * effectively represented in Java and it's evaluation does not require
  65  * full-blown XPath processor.
  66  *
  67  * <p>
  68  * <h3>Path Arguments</h3>
  69  * Path to the node represented in instance identifier consists of
  70  * {@link PathArgument} which carries necessary information to uniquely identify
  71  * node on particular level in the subtree.
  72  *
  73  * <ul>
  74  * <li>{@link NodeIdentifier} - Identifier of node, which has cardinality
  75  * <code>0..1</code> in particular subtree in data tree.</li>
  76  * <li>{@link NodeIdentifierWithPredicates} - Identifier of node (list item),
  77  * which has cardinality <code>0..n</code>.</li>
  78  * <li>{@link NodeWithValue} - Identifier of instance <code>leaf</code> node or
  79  * <code>leaf-list</code> node.</li>
  80  * <li>{@link AugmentationIdentifier} - Identifier of instance of
  81  * <code>augmentation</code> node.</li>
  82  * </ul>
  83  *
  84  * @see <a href="http://tools.ietf.org/html/rfc6020#section-9.13">RFC6020</a>
  85  */
  86 // FIXME: 4.0.0: this concept needs to be moved to yang-common, as parser components need the ability to refer
  87 //               to data nodes -- most notably XPath expressions and {@code default} statement arguments need to be able
  88 //               to represent these.
  89 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         private static final class Singleton extends NodeIdentifierWithPredicates {
 576             private static final long serialVersionUID = 1L;
 577
 578             private final @NonNull QName key;
 579             private final @NonNull Object value;
 580
 581             Singleton(final QName node, final QName key, final Object value) {
 582                 super(node);
 583                 this.key = requireNonNull(key);
 584                 this.value = requireNonNull(value);
 585             }
 586
 587             @Override
 588             public SingletonSet<Entry<QName, Object>> entrySet() {
 589                 return SingletonSet.of(new SimpleImmutableEntry<>(key, value));
 590             }
 591
 592             @Override
 593             public SingletonSet<QName> keySet() {
 594                 return SingletonSet.of(key);
 595             }
 596
 597             @Override
 598             public SingletonSet<Object> values() {
 599                 return SingletonSet.of(value);
 600             }
 601
 602             @Override
 603             public int size() {
 604                 return 1;
 605             }
 606
 607             @Override
 608             public ImmutableMap<QName, Object> asMap() {
 609                 return ImmutableMap.of(key, value);
 610             }
 611
 612             @Override
 613             boolean equalMapping(final NodeIdentifierWithPredicates other) {
 614                 final Singleton single = (Singleton) other;
 615                 return key.equals(single.key) && Objects.deepEquals(value, single.value);
 616             }
 617
 618             @Override
 619             Object keyValue(final QName qname) {
 620                 return key.equals(qname) ? value : null;
 621             }
 622         }
 623
 624         private static final class Regular extends NodeIdentifierWithPredicates {
 625             private static final long serialVersionUID = 1L;
 626
 627             private final @NonNull Map<QName, Object> keyValues;
 628
 629             Regular(final QName node, final Map<QName, Object> keyValues) {
 630                 super(node);
 631                 this.keyValues = requireNonNull(keyValues);
 632             }
 633
 634             @Override
 635             public Set<Entry<QName, Object>> entrySet() {
 636                 return keyValues.entrySet();
 637             }
 638
 639             @Override
 640             public Set<QName> keySet() {
 641                 return keyValues.keySet();
 642             }
 643
 644             @Override
 645             public Collection<Object> values() {
 646                 return keyValues.values();
 647             }
 648
 649             @Override
 650             public int size() {
 651                 return keyValues.size();
 652             }
 653
 654             @Override
 655             public Map<QName, Object> asMap() {
 656                 return keyValues;
 657             }
 658
 659             @Override
 660             Object keyValue(final QName qname) {
 661                 return keyValues.get(qname);
 662             }
 663
 664             @Override
 665             boolean equalMapping(final NodeIdentifierWithPredicates other) {
 666                 final Map<QName, Object> otherKeyValues = ((Regular) other).keyValues;
 667                 // TODO: benchmark to see if just calling equals() on the two maps is not faster
 668                 if (keyValues == otherKeyValues) {
 669                     return true;
 670                 }
 671                 if (keyValues.size() != otherKeyValues.size()) {
 672                     return false;
 673                 }
 674
 675                 for (Entry<QName, Object> entry : entrySet()) {
 676                     final Object otherValue = otherKeyValues.get(entry.getKey());
 677                     if (otherValue == null || !Objects.deepEquals(entry.getValue(), otherValue)) {
 678                         return false;
 679                     }
 680                 }
 681
 682                 return true;
 683             }
 684         }
 685
 686         private static final long serialVersionUID = -4787195606494761540L;
 687
 688         NodeIdentifierWithPredicates(final QName node) {
 689             super(node);
 690         }
 691
 692         public static @NonNull NodeIdentifierWithPredicates of(final QName node) {
 693             return new Regular(node, ImmutableMap.of());
 694         }
 695
 696         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final QName key, final Object value) {
 697             return new Singleton(node, key, value);
 698         }
 699
 700         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final Entry<QName, Object> entry) {
 701             return of(node, entry.getKey(), entry.getValue());
 702         }
 703
 704         public static @NonNull NodeIdentifierWithPredicates of(final QName node, final Map<QName, Object> keyValues) {
 705             return keyValues.size() == 1 ? of(keyValues, node)
 706                     // Retains ImmutableMap for empty maps. For larger sizes uses a shared key set.
 707                     : new Regular(node, ImmutableOffsetMap.unorderedCopyOf(keyValues));
 708         }
 709
 710         public static @NonNull NodeIdentifierWithPredicates of(final QName node,
 711                 final ImmutableOffsetMap<QName, Object> keyValues) {
 712             return keyValues.size() == 1 ? of(keyValues, node) : new Regular(node, keyValues);
 713         }
 714
 715         @Deprecated
 716         public static @NonNull NodeIdentifierWithPredicates of(final QName node,
 717                 final SharedSingletonMap<QName, Object> keyValues) {
 718             return of(node, keyValues.getEntry());
 719         }
 720
 721         private static @NonNull NodeIdentifierWithPredicates of(final Map<QName, Object> keyValues, final QName node) {
 722             return of(node, keyValues.entrySet().iterator().next());
 723         }
 724
 725         /**
 726          * Return the set of predicates keys and values. Keys are guaranteeed to be unique.
 727          *
 728          * @return Predicate set.
 729          */
 730         @Beta
 731         public abstract @NonNull Set<Entry<QName, Object>> entrySet();
 732
 733         /**
 734          * Return the predicate key in the iteration order of {@link #entrySet()}.
 735          *
 736          * @return Predicate values.
 737          */
 738         @Beta
 739         public abstract @NonNull Set<QName> keySet();
 740
 741         /**
 742          * Return the predicate values in the iteration order of {@link #entrySet()}.
 743          *
 744          * @return Predicate values.
 745          */
 746         @Beta
 747         public abstract @NonNull Collection<Object> values();
 748
 749         @Beta
 750         public final @Nullable Object getValue(final QName key) {
 751             return keyValue(requireNonNull(key));
 752         }
 753
 754         @Beta
 755         public final <T> @Nullable T getValue(final QName key, final Class<T> valueClass) {
 756             return valueClass.cast(getValue(key));
 757         }
 758
 759         /**
 760          * Return the number of predicates present.
 761          *
 762          * @return The number of predicates present.
 763          */
 764         @Beta
 765         public abstract int size();
 766
 767         /**
 768          * A Map-like view of this identifier's predicates. The view is expected to be stable and effectively-immutable.
 769          *
 770          * @return Map of predicates.
 771          * @deprecated This method in a provisional one. It can be used in the code base, but users requiring it should
 772          *             contact <a href="mailto:yangtools-dev@lists.opendaylight.org">yangtools-dev</a> for migration
 773          *             guidelines. Callers are strongly encouraged to explore {@link #entrySet()}, {@link #size()},
 774          *             {@link #values()} and {@link #keySet()} as an alternative.
 775          */
 776         @Beta
 777         @Deprecated
 778         // FIXME: 4.0.0: evaluate the real usefulness of this. The problem here is Map.hashCode() and Map.equals(),
 779         //               which limits our options.
 780         public abstract @NonNull Map<QName, Object> asMap();
 781
 782         @Override
 783         protected final int hashCodeImpl() {
 784             int result = 31 * super.hashCodeImpl();
 785             for (Entry<QName, Object> entry : entrySet()) {
 786                 result += entry.getKey().hashCode() + YangInstanceIdentifier.hashCode(entry.getValue());
 787             }
 788             return result;
 789         }
 790
 791         @Override
 792         @SuppressWarnings("checkstyle:equalsHashCode")
 793         public final boolean equals(final Object obj) {
 794             return super.equals(obj) && equalMapping((NodeIdentifierWithPredicates) obj);
 795         }
 796
 797         abstract boolean equalMapping(NodeIdentifierWithPredicates other);
 798
 799         abstract @Nullable Object keyValue(@NonNull QName qname);
 800
 801         @Override
 802         public final String toString() {
 803             return super.toString() + '[' + asMap() + ']';
 804         }
 805
 806         @Override
 807         public final String toRelativeString(final PathArgument previous) {
 808             return super.toRelativeString(previous) + '[' + asMap() + ']';
 809         }
 810
 811         @Override
 812         final Object writeReplace() {
 813             return new NIPv2(this);
 814         }
 815     }
 816
 817     /**
 818      * Simple path argument identifying a {@link LeafSetEntryNode} leaf
 819      * overall data tree.
 820      */
 821     public static final class NodeWithValue<T> extends AbstractPathArgument {
 822         private static final long serialVersionUID = -3637456085341738431L;
 823
 824         private final T value;
 825
 826         public NodeWithValue(final QName node, final T value) {
 827             super(node);
 828             this.value = value;
 829         }
 830
 831         public T getValue() {
 832             return value;
 833         }
 834
 835         @Override
 836         protected int hashCodeImpl() {
 837             final int prime = 31;
 838             int result = super.hashCodeImpl();
 839             result = prime * result + YangInstanceIdentifier.hashCode(value);
 840             return result;
 841         }
 842
 843         @Override
 844         @SuppressWarnings("checkstyle:equalsHashCode")
 845         public boolean equals(final Object obj) {
 846             if (!super.equals(obj)) {
 847                 return false;
 848             }
 849             final NodeWithValue<?> other = (NodeWithValue<?>) obj;
 850             return Objects.deepEquals(value, other.value);
 851         }
 852
 853         @Override
 854         public String toString() {
 855             return super.toString() + '[' + value + ']';
 856         }
 857
 858         @Override
 859         public String toRelativeString(final PathArgument previous) {
 860             return super.toRelativeString(previous) + '[' + value + ']';
 861         }
 862
 863         @Override
 864         Object writeReplace() {
 865             return new NIVv1(this);
 866         }
 867     }
 868
 869     /**
 870      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode}
 871      * node in particular subtree.
 872      *
 873      * <p>
 874      * Augmentation is uniquely identified by set of all possible child nodes.
 875      * This is possible
 876      * to identify instance of augmentation,
 877      * since RFC6020 states that <code>augment</code> that augment
 878      * statement must not add multiple nodes from same namespace
 879      * / module to the target node.
 880      *
 881      * @see <a href="http://tools.ietf.org/html/rfc6020#section-7.15">RFC6020</a>
 882      */
 883     public static final class AugmentationIdentifier implements PathArgument {
 884         private static final long serialVersionUID = -8122335594681936939L;
 885
 886         private static final LoadingCache<ImmutableSet<QName>, AugmentationIdentifier> CACHE = CacheBuilder.newBuilder()
 887                 .weakValues().build(new CacheLoader<ImmutableSet<QName>, AugmentationIdentifier>() {
 888                     @Override
 889                     public AugmentationIdentifier load(final ImmutableSet<QName> key) {
 890                         return new AugmentationIdentifier(key);
 891                     }
 892                 });
 893
 894         private final @NonNull ImmutableSet<QName> childNames;
 895
 896         @Override
 897         public QName getNodeType() {
 898             // This should rather throw exception than return always null
 899             throw new UnsupportedOperationException("Augmentation node has no QName");
 900         }
 901
 902         /**
 903          * Construct new augmentation identifier using supplied set of possible
 904          * child nodes.
 905          *
 906          * @param childNames
 907          *            Set of possible child nodes.
 908          */
 909         public AugmentationIdentifier(final ImmutableSet<QName> childNames) {
 910             this.childNames = requireNonNull(childNames);
 911         }
 912
 913         /**
 914          * Construct new augmentation identifier using supplied set of possible
 915          * child nodes.
 916          *
 917          * @param childNames
 918          *            Set of possible child nodes.
 919          */
 920         public AugmentationIdentifier(final Set<QName> childNames) {
 921             this.childNames = ImmutableSet.copyOf(childNames);
 922         }
 923
 924         /**
 925          * Return an AugmentationIdentifier for a particular set of QNames. Unlike the constructor, this factory method
 926          * uses a global instance cache, resulting in object reuse for equal inputs.
 927          *
 928          * @param childNames Set of possible child nodes
 929          * @return An {@link AugmentationIdentifier}
 930          */
 931         public static @NonNull AugmentationIdentifier create(final ImmutableSet<QName> childNames) {
 932             return CACHE.getUnchecked(childNames);
 933         }
 934
 935         /**
 936          * Return an AugmentationIdentifier for a particular set of QNames. Unlike the constructor, this factory method
 937          * uses a global instance cache, resulting in object reuse for equal inputs.
 938          *
 939          * @param childNames Set of possible child nodes
 940          * @return An {@link AugmentationIdentifier}
 941          */
 942         public static @NonNull AugmentationIdentifier create(final Set<QName> childNames) {
 943             final AugmentationIdentifier existing = CACHE.getIfPresent(childNames);
 944             return existing != null ? existing : create(ImmutableSet.copyOf(childNames));
 945         }
 946
 947         /**
 948          * Returns set of all possible child nodes.
 949          *
 950          * @return set of all possible child nodes.
 951          */
 952         public @NonNull Set<QName> getPossibleChildNames() {
 953             return childNames;
 954         }
 955
 956         @Override
 957         public String toString() {
 958             return "AugmentationIdentifier{" + "childNames=" + childNames + '}';
 959         }
 960
 961         @Override
 962         public String toRelativeString(final PathArgument previous) {
 963             return toString();
 964         }
 965
 966         @Override
 967         public boolean equals(final Object obj) {
 968             if (this == obj) {
 969                 return true;
 970             }
 971             if (!(obj instanceof AugmentationIdentifier)) {
 972                 return false;
 973             }
 974
 975             AugmentationIdentifier that = (AugmentationIdentifier) obj;
 976             return childNames.equals(that.childNames);
 977         }
 978
 979         @Override
 980         public int hashCode() {
 981             return childNames.hashCode();
 982         }
 983
 984         @Override
 985         @SuppressWarnings("checkstyle:parameterName")
 986         public int compareTo(final PathArgument o) {
 987             if (!(o instanceof AugmentationIdentifier)) {
 988                 return -1;
 989             }
 990             AugmentationIdentifier other = (AugmentationIdentifier) o;
 991             Set<QName> otherChildNames = other.getPossibleChildNames();
 992             int thisSize = childNames.size();
 993             int otherSize = otherChildNames.size();
 994             if (thisSize == otherSize) {
 995                 // Quick Set-based comparison
 996                 if (childNames.equals(otherChildNames)) {
 997                     return 0;
 998                 }
 999
1000                 // We already know the sets are not equal, but have equal size, hence the sets differ in their elements,
1001                 // but potentially share a common set of elements. The most consistent way of comparing them is using
1002                 // total ordering defined by QName's compareTo. Hence convert both sets to lists ordered
1003                 // by QName.compareTo() and decide on the first differing element.
1004                 final List<QName> diff = new ArrayList<>(Sets.symmetricDifference(childNames, otherChildNames));
1005                 verify(!diff.isEmpty(), "Augmentation identifiers %s and %s report no difference", this, o);
1006                 diff.sort(QName::compareTo);
1007                 return childNames.contains(diff.get(0)) ? -1 : 1;
1008             } else if (thisSize < otherSize) {
1009                 return 1;
1010             } else {
1011                 return -1;
1012             }
1013         }
1014
1015         private Object writeReplace() {
1016             return new AIv1(this);
1017         }
1018     }
1019
1020     /**
1021      * Fluent Builder of Instance Identifier instances.
1022      */
1023     public interface InstanceIdentifierBuilder extends Builder<YangInstanceIdentifier> {
1024         /**
1025          * Adds a {@link PathArgument} to path arguments of resulting instance identifier.
1026          *
1027          * @param arg A {@link PathArgument} to be added
1028          * @return this builder
1029          */
1030         @NonNull InstanceIdentifierBuilder node(PathArgument arg);
1031
1032         /**
1033          * Adds {@link NodeIdentifier} with supplied QName to path arguments of resulting instance identifier.
1034          *
1035          * @param nodeType QName of {@link NodeIdentifier} which will be added
1036          * @return this builder
1037          */
1038         @NonNull InstanceIdentifierBuilder node(QName nodeType);
1039
1040         /**
1041          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key values to path arguments of resulting
1042          * instance identifier.
1043          *
1044          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
1045          * @param keyValues Map of key components and their respective values for {@link NodeIdentifierWithPredicates}
1046          * @return this builder
1047          */
1048         @NonNull InstanceIdentifierBuilder nodeWithKey(QName nodeType, Map<QName, Object> keyValues);
1049
1050         /**
1051          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key, value.
1052          *
1053          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
1054          * @param key QName of key which will be added
1055          * @param value value of key which will be added
1056          * @return this builder
1057          */
1058         @NonNull InstanceIdentifierBuilder nodeWithKey(QName nodeType, QName key, Object value);
1059
1060         /**
1061          * Adds a collection of {@link PathArgument}s to path arguments of resulting instance identifier.
1062          *
1063          * @param args {@link PathArgument}s to be added
1064          * @return this builder
1065          * @throws NullPointerException if any of the arguments is null
1066          */
1067         @Beta
1068         @NonNull InstanceIdentifierBuilder append(Collection<? extends PathArgument> args);
1069
1070         /**
1071          * Adds a collection of {@link PathArgument}s to path arguments of resulting instance identifier.
1072          *
1073          * @param args {@link PathArgument}s to be added
1074          * @return this builder
1075          * @throws NullPointerException if any of the arguments is null
1076          */
1077         @Beta
1078         default @NonNull InstanceIdentifierBuilder append(final PathArgument... args) {
1079             return append(Arrays.asList(args));
1080         }
1081
1082         /**
1083          * Builds an {@link YangInstanceIdentifier} with path arguments from this builder.
1084          *
1085          * @return {@link YangInstanceIdentifier}
1086          */
1087         @Override
1088         YangInstanceIdentifier build();
1089     }
1090 }