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

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