46489d31f34847292b238ab8e21f270f7574f025
[yangtools.git] / 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  * This program and the accompanying materials are made available under the
4  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
5  * and is available at http://www.eclipse.org/legal/epl-v10.html
6  */
7 package org.opendaylight.yangtools.yang.data.api;
8
9 import com.google.common.base.Optional;
10 import com.google.common.base.Preconditions;
11 import com.google.common.collect.ImmutableMap;
12 import com.google.common.collect.ImmutableSet;
13 import com.google.common.collect.Iterables;
14 import java.io.Serializable;
15 import java.lang.reflect.Array;
16 import java.util.Arrays;
17 import java.util.Collection;
18 import java.util.Iterator;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.Map.Entry;
22 import java.util.Objects;
23 import java.util.Set;
24 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
25 import javax.annotation.Nonnull;
26 import javax.annotation.Nullable;
27 import org.opendaylight.yangtools.concepts.Builder;
28 import org.opendaylight.yangtools.concepts.Immutable;
29 import org.opendaylight.yangtools.concepts.Path;
30 import org.opendaylight.yangtools.util.HashCodeBuilder;
31 import org.opendaylight.yangtools.yang.common.QName;
32 import org.opendaylight.yangtools.yang.common.QNameModule;
33 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetEntryNode;
34
35 /**
36  * Unique identifier of a particular node instance in the data tree.
37  *
38  * <p>
39  * Java representation of YANG Built-in type <code>instance-identifier</code>,
40  * which conceptually is XPath expression minimized to uniquely identify element
41  * in data tree which conforms to constraints maintained by YANG Model,
42  * effectively this makes Instance Identifier a path to element in data tree.
43  * <p>
44  * Constraints put in YANG specification on instance-identifier allowed it to be
45  * effectively represented in Java and it's evaluation does not require
46  * full-blown XPath processor.
47  * <p>
48  * <h3>Path Arguments</h3>
49  * Path to the node represented in instance identifier consists of
50  * {@link PathArgument} which carries necessary information to uniquely identify
51  * node on particular level in the subtree.
52  * <p>
53  * <ul>
54  * <li>{@link NodeIdentifier} - Identifier of node, which has cardinality
55  * <code>0..1</code> in particular subtree in data tree.</li>
56  * <li>{@link NodeIdentifierWithPredicates} - Identifier of node (list item),
57  * which has cardinality <code>0..n</code>.</li>
58  * <li>{@link NodeWithValue} - Identifier of instance <code>leaf</code> node or
59  * <code>leaf-list</code> node.</li>
60  * <li>{@link AugmentationIdentifier} - Identifier of instance of
61  * <code>augmentation</code> node.</li>
62  * </ul>
63  *
64  *
65  * @see <a href="http://tools.ietf.org/html/rfc6020#section-9.13">RFC6020</a>
66  */
67 public abstract class YangInstanceIdentifier extends IterablePathArguments implements Path<YangInstanceIdentifier>, Immutable, Serializable {
68     /**
69      * An empty {@link YangInstanceIdentifier}. It corresponds to the path of the conceptual
70      * root of the YANG namespace.
71      */
72     public static final YangInstanceIdentifier EMPTY = FixedYangInstanceIdentifier.EMPTY_INSTANCE;
73
74     private static final AtomicReferenceFieldUpdater<YangInstanceIdentifier, String> TOSTRINGCACHE_UPDATER =
75             AtomicReferenceFieldUpdater.newUpdater(YangInstanceIdentifier.class, String.class, "toStringCache");
76     private static final long serialVersionUID = 4L;
77
78     private final int hash;
79     private transient volatile String toStringCache = null;
80
81     // Package-private to prevent outside subclassing
82     YangInstanceIdentifier(final int hash) {
83         this.hash = hash;
84     }
85
86     @Nonnull abstract YangInstanceIdentifier createRelativeIdentifier(int skipFromRoot);
87     @Nonnull abstract Collection<PathArgument> tryPathArguments();
88     @Nonnull abstract Collection<PathArgument> tryReversePathArguments();
89
90     /**
91      * Check if this instance identifier has empty path arguments, e.g. it is
92      * empty and corresponds to {@link #EMPTY}.
93      *
94      * @return True if this instance identifier is empty, false otherwise.
95      */
96     public abstract boolean isEmpty();
97
98     /**
99      * Return the conceptual parent {@link YangInstanceIdentifier}, which has
100      * one item less in {@link #getPathArguments()}.
101      *
102      * @return Parent {@link YangInstanceIdentifier}, or null if this is object is {@link #EMPTY}.
103      */
104     @Nullable public abstract YangInstanceIdentifier getParent();
105
106     /**
107      * Returns a list of path arguments.
108      *
109      * @deprecated Use {@link #getPathArguments()} instead.
110      * @return Immutable list of path arguments.
111      */
112     @Deprecated
113     public final List<PathArgument> getPath() {
114         return getPathArguments();
115     }
116
117     /**
118      * Returns an ordered iteration of path arguments.
119      *
120      * @return Immutable iteration of path arguments.
121      */
122     @Override
123     public abstract List<PathArgument> getPathArguments();
124
125     /**
126      * Returns an iterable of path arguments in reverse order. This is useful
127      * when walking up a tree organized this way.
128      *
129      * @return Immutable iterable of path arguments in reverse order.
130      */
131     @Override
132     public abstract List<PathArgument> getReversePathArguments();
133
134     /**
135      * Returns the last PathArgument. This is equivalent of iterating
136      * to the last element of the iterable returned by {@link #getPathArguments()}.
137      *
138      * @return The last past argument, or null if there are no PathArguments.
139      */
140     public abstract PathArgument getLastPathArgument();
141
142     public static YangInstanceIdentifier create(final Iterable<? extends PathArgument> path) {
143         if (Iterables.isEmpty(path)) {
144             return EMPTY;
145         }
146
147         final HashCodeBuilder<PathArgument> hash = new HashCodeBuilder<>();
148         for (PathArgument a : path) {
149             hash.addArgument(a);
150         }
151
152         return FixedYangInstanceIdentifier.create(path, hash.build());
153     }
154
155     public static YangInstanceIdentifier create(final PathArgument... path) {
156         // We are forcing a copy, since we cannot trust the user
157         return create(Arrays.asList(path));
158     }
159
160     @Override
161     public final int hashCode() {
162         /*
163          * The caching is safe, since the object contract requires
164          * immutability of the object and all objects referenced from this
165          * object.
166          * Used lists, maps are immutable. Path Arguments (elements) are also
167          * immutable, since the PathArgument contract requires immutability.
168          */
169         return hash;
170     }
171
172     boolean pathArgumentsEqual(final YangInstanceIdentifier other) {
173         return Iterables.elementsEqual(getPathArguments(), other.getPathArguments());
174     }
175
176     @Override
177     public boolean equals(final Object obj) {
178         if (this == obj) {
179             return true;
180         }
181         if (!(obj instanceof YangInstanceIdentifier)) {
182             return false;
183         }
184         YangInstanceIdentifier other = (YangInstanceIdentifier) obj;
185         if (this.hashCode() != obj.hashCode()) {
186             return false;
187         }
188
189         return pathArgumentsEqual(other);
190     }
191
192     /**
193      * Constructs a new Instance Identifier with new {@link NodeIdentifier} added to the end of path arguments
194      *
195      * @param name QName of {@link NodeIdentifier}
196      * @return Instance Identifier with additional path argument added to the end.
197      */
198     public final YangInstanceIdentifier node(final QName name) {
199         return node(new NodeIdentifier(name));
200     }
201
202     /**
203      *
204      * Constructs a new Instance Identifier with new {@link PathArgument} added to the end of path arguments
205      *
206      * @param arg Path argument which should be added to the end
207      * @return Instance Identifier with additional path argument added to the end.
208      */
209     public final YangInstanceIdentifier node(final PathArgument arg) {
210         return new StackedYangInstanceIdentifier(this, arg, HashCodeBuilder.nextHashCode(hash, arg));
211     }
212
213     /**
214      * Get the relative path from an ancestor. This method attempts to perform
215      * the reverse of concatenating a base (ancestor) and a path.
216      *
217      * @param ancestor
218      *            Ancestor against which the relative path should be calculated
219      * @return This object's relative path from parent, or Optional.absent() if
220      *         the specified parent is not in fact an ancestor of this object.
221      */
222     public Optional<YangInstanceIdentifier> relativeTo(final YangInstanceIdentifier ancestor) {
223         final Iterator<?> lit = getPathArguments().iterator();
224         final Iterator<?> oit = ancestor.getPathArguments().iterator();
225         int common = 0;
226
227         while (oit.hasNext()) {
228             // Ancestor is not really an ancestor
229             if (!lit.hasNext() || !lit.next().equals(oit.next())) {
230                 return Optional.absent();
231             }
232
233             ++common;
234         }
235
236         if (common == 0) {
237             return Optional.of(this);
238         }
239         if (!lit.hasNext()) {
240             return Optional.of(EMPTY);
241         }
242
243         return Optional.of(createRelativeIdentifier(common));
244     }
245
246     private static int hashCode(final Object value) {
247         if (value == null) {
248             return 0;
249         }
250
251         if (byte[].class.equals(value.getClass())) {
252             return Arrays.hashCode((byte[]) value);
253         }
254
255         if (value.getClass().isArray()) {
256             int hash = 0;
257             int length = Array.getLength(value);
258             for (int i = 0; i < length; i++) {
259                 hash += Objects.hashCode(Array.get(value, i));
260             }
261
262             return hash;
263         }
264
265         return Objects.hashCode(value);
266     }
267
268     // Static factories & helpers
269
270     /**
271      *
272      * Returns a new InstanceIdentifier with only one path argument of type {@link NodeIdentifier} with supplied QName
273      *
274      * @param name QName of first node identifier
275      * @return Instance Identifier with only one path argument of type {@link NodeIdentifier}
276      */
277     public static YangInstanceIdentifier of(final QName name) {
278         return create(new NodeIdentifier(name));
279     }
280
281     /**
282      *
283      * Returns new builder for InstanceIdentifier with empty path arguments.
284      *
285      * @return new builder for InstanceIdentifier with empty path arguments.
286      */
287     public static InstanceIdentifierBuilder builder() {
288         return new YangInstanceIdentifierBuilder();
289     }
290
291     /**
292      *
293      * Returns new builder for InstanceIdentifier with path arguments copied from original instance identifier.
294      *
295      * @param origin Instace Identifier from which path arguments are copied.
296      * @return new builder for InstanceIdentifier with path arguments copied from original instance identifier.
297      */
298     public static InstanceIdentifierBuilder builder(final YangInstanceIdentifier origin) {
299         return new YangInstanceIdentifierBuilder(origin.getPathArguments(), origin.hashCode());
300     }
301
302     /**
303      * Path argument / component of InstanceIdentifier
304      *
305      * Path argument uniquely identifies node in data tree on particular
306      * level.
307      * <p>
308      * This interface itself is used as common parent for actual
309      * path arguments types and should not be implemented by user code.
310      * <p>
311      * Path arguments SHOULD contain only minimum of information
312      * required to uniquely identify node on particular subtree level.
313      *
314      * For actual path arguments types see:
315      * <ul>
316      * <li>{@link NodeIdentifier} - Identifier of container or leaf
317      * <li>{@link NodeIdentifierWithPredicates} - Identifier of list entries, which have key defined
318      * <li>{@link AugmentationIdentifier} - Identifier of augmentation
319      * <li>{@link NodeWithValue} - Identifier of leaf-list entry
320      * </ul>
321      */
322     public interface PathArgument extends Comparable<PathArgument>, Immutable, Serializable {
323         /**
324          * If applicable returns unique QName of data node as defined in YANG
325          * Schema.
326          *
327          * This method may return null, if the corresponding schema node, does
328          * not have QName associated, such as in cases of augmentations.
329          *
330          * @return Node type
331          */
332         QName getNodeType();
333
334         /**
335          * Return the string representation of this object for use in context
336          * provided by a previous object. This method can be implemented in
337          * terms of {@link #toString()}, but implementations are encourage to
338          * reuse any context already emitted by the previous object.
339          *
340          * @param previous Previous path argument
341          * @return String representation
342          */
343         String toRelativeString(PathArgument previous);
344     }
345
346     private static abstract class AbstractPathArgument implements PathArgument {
347         private static final long serialVersionUID = -4546547994250849340L;
348         private final QName nodeType;
349         private transient int hashValue;
350         private volatile transient boolean hashGuard = false;
351
352         protected AbstractPathArgument(final QName nodeType) {
353             this.nodeType = Preconditions.checkNotNull(nodeType);
354         }
355
356         @Override
357         public final QName getNodeType() {
358             return nodeType;
359         }
360
361         @Override
362         public int compareTo(final PathArgument o) {
363             return nodeType.compareTo(o.getNodeType());
364         }
365
366         protected int hashCodeImpl() {
367             return 31 + getNodeType().hashCode();
368         }
369
370         @Override
371         public final int hashCode() {
372             if (!hashGuard) {
373                 hashValue = hashCodeImpl();
374                 hashGuard = true;
375             }
376
377             return hashValue;
378         }
379
380         @Override
381         public boolean equals(final Object obj) {
382             if (this == obj) {
383                 return true;
384             }
385             if (obj == null || this.getClass() != obj.getClass()) {
386                 return false;
387             }
388
389             return getNodeType().equals(((AbstractPathArgument)obj).getNodeType());
390         }
391
392         @Override
393         public String toString() {
394             return getNodeType().toString();
395         }
396
397         @Override
398         public String toRelativeString(final PathArgument previous) {
399             if (previous instanceof AbstractPathArgument) {
400                 final QNameModule mod = ((AbstractPathArgument)previous).getNodeType().getModule();
401                 if (getNodeType().getModule().equals(mod)) {
402                     return getNodeType().getLocalName();
403                 }
404             }
405
406             return getNodeType().toString();
407         }
408     }
409
410     /**
411      * Fluent Builder of Instance Identifier instances
412      */
413     public interface InstanceIdentifierBuilder extends Builder<YangInstanceIdentifier> {
414         /**
415          * Adds a {@link PathArgument} to to path arguments of resulting instance identifier.
416          *
417          * @param arg A {@link PathArgument} to be added
418          * @return this builder
419          */
420         InstanceIdentifierBuilder node(PathArgument arg);
421
422         /**
423          * Adds {@link NodeIdentifier} with supplied QName to path arguments of resulting instance identifier.
424          *
425          * @param nodeType QName of {@link NodeIdentifier} which will be added
426          * @return this builder
427          */
428         InstanceIdentifierBuilder node(QName nodeType);
429
430         /**
431          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key values to path arguments of resulting instance identifier.
432          *
433          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
434          * @param keyValues Map of key components and their respective values for {@link NodeIdentifierWithPredicates}
435          * @return this builder
436          */
437         InstanceIdentifierBuilder nodeWithKey(QName nodeType, Map<QName, Object> keyValues);
438
439         /**
440          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key, value.
441          *
442          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
443          * @param key QName of key which will be added
444          * @param value value of key which will be added
445          * @return this builder
446          */
447         InstanceIdentifierBuilder nodeWithKey(QName nodeType, QName key, Object value);
448
449         /**
450          *
451          * Builds an {@link YangInstanceIdentifier} with path arguments from this builder
452          *
453          * @return {@link YangInstanceIdentifier}
454          */
455         @Override
456         YangInstanceIdentifier build();
457
458         /*
459          * @deprecated use #build()
460          */
461         @Deprecated
462         YangInstanceIdentifier toInstance();
463     }
464
465     /**
466      * Simple path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.ContainerNode} or
467      * {@link org.opendaylight.yangtools.yang.data.api.schema.LeafNode} leaf in particular subtree.
468      */
469     public static final class NodeIdentifier extends AbstractPathArgument {
470         private static final long serialVersionUID = -2255888212390871347L;
471
472         public NodeIdentifier(final QName node) {
473             super(node);
474         }
475     }
476
477     /**
478      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode} leaf
479      * overall data tree.
480      */
481     public static final class NodeIdentifierWithPredicates extends AbstractPathArgument {
482         private static final long serialVersionUID = -4787195606494761540L;
483
484         private final Map<QName, Object> keyValues;
485
486         public NodeIdentifierWithPredicates(final QName node, final Map<QName, Object> keyValues) {
487             super(node);
488             this.keyValues = ImmutableMap.copyOf(keyValues);
489         }
490
491         public NodeIdentifierWithPredicates(final QName node, final QName key, final Object value) {
492             this(node, ImmutableMap.of(key, value));
493         }
494
495         public Map<QName, Object> getKeyValues() {
496             return keyValues;
497         }
498
499         @Override
500         protected int hashCodeImpl() {
501             final int prime = 31;
502             int result = super.hashCodeImpl();
503             result = prime * result;
504
505             for (Entry<QName, Object> entry : keyValues.entrySet()) {
506                 result += Objects.hashCode(entry.getKey()) + YangInstanceIdentifier.hashCode(entry.getValue());
507             }
508             return result;
509         }
510
511         @Override
512         public boolean equals(final Object obj) {
513             if (!super.equals(obj)) {
514                 return false;
515             }
516
517             final Map<QName, Object> otherKeyValues = ((NodeIdentifierWithPredicates) obj).keyValues;
518
519             // TODO: benchmark to see if just calling equals() on the two maps is not faster
520             if (keyValues == otherKeyValues) {
521                 return true;
522             }
523             if (keyValues.size() != otherKeyValues.size()) {
524                 return false;
525             }
526
527             for (Entry<QName, Object> entry : keyValues.entrySet()) {
528                 if (!otherKeyValues.containsKey(entry.getKey())
529                         || !Objects.deepEquals(entry.getValue(), otherKeyValues.get(entry.getKey()))) {
530
531                     return false;
532                 }
533             }
534
535             return true;
536         }
537
538         @Override
539         public String toString() {
540             return super.toString() + '[' + keyValues + ']';
541         }
542
543         @Override
544         public String toRelativeString(final PathArgument previous) {
545             return super.toRelativeString(previous) + '[' + keyValues + ']';
546         }
547     }
548
549     /**
550      * Simple path argument identifying a {@link LeafSetEntryNode} leaf
551      * overall data tree.
552      */
553     public static final class NodeWithValue extends AbstractPathArgument {
554         private static final long serialVersionUID = -3637456085341738431L;
555
556         private final Object value;
557
558         public NodeWithValue(final QName node, final Object value) {
559             super(node);
560             this.value = value;
561         }
562
563         public Object getValue() {
564             return value;
565         }
566
567         @Override
568         protected int hashCodeImpl() {
569             final int prime = 31;
570             int result = super.hashCodeImpl();
571             result = prime * result + ((value == null) ? 0 : YangInstanceIdentifier.hashCode(value));
572             return result;
573         }
574
575         @Override
576         public boolean equals(final Object obj) {
577             if (!super.equals(obj)) {
578                 return false;
579             }
580             final NodeWithValue other = (NodeWithValue) obj;
581             return Objects.deepEquals(value, other.value);
582         }
583
584         @Override
585         public String toString() {
586             return super.toString() + '[' + value + ']';
587         }
588
589         @Override
590         public String toRelativeString(final PathArgument previous) {
591             return super.toRelativeString(previous) + '[' + value + ']';
592         }
593     }
594
595     /**
596      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode} node in
597      * particular subtree.
598      *
599      * Augmentation is uniquely identified by set of all possible child nodes.
600      * This is possible
601      * to identify instance of augmentation,
602      * since RFC6020 states that <code>augment</code> that augment
603      * statement must not add multiple nodes from same namespace
604      * / module to the target node.
605      *
606      *
607      * @see <a href="http://tools.ietf.org/html/rfc6020#section-7.15">RFC6020</a>
608      */
609     public static final class AugmentationIdentifier implements PathArgument {
610         private static final long serialVersionUID = -8122335594681936939L;
611         private final ImmutableSet<QName> childNames;
612
613         @Override
614         public QName getNodeType() {
615             // This should rather throw exception than return always null
616             throw new UnsupportedOperationException("Augmentation node has no QName");
617         }
618
619         /**
620          *
621          * Construct new augmentation identifier using supplied set of possible
622          * child nodes
623          *
624          * @param childNames
625          *            Set of possible child nodes.
626          */
627         public AugmentationIdentifier(final Set<QName> childNames) {
628             this.childNames = ImmutableSet.copyOf(childNames);
629         }
630
631         /**
632          * Returns set of all possible child nodes
633          *
634          * @return set of all possible child nodes.
635          */
636         public Set<QName> getPossibleChildNames() {
637             return childNames;
638         }
639
640         @Override
641         public String toString() {
642             final StringBuilder sb = new StringBuilder("AugmentationIdentifier{");
643             sb.append("childNames=").append(childNames).append('}');
644             return sb.toString();
645         }
646
647         @Override
648         public String toRelativeString(final PathArgument previous) {
649             return toString();
650         }
651
652         @Override
653         public boolean equals(final Object o) {
654             if (this == o) {
655                 return true;
656             }
657             if (!(o instanceof AugmentationIdentifier)) {
658                 return false;
659             }
660
661             AugmentationIdentifier that = (AugmentationIdentifier) o;
662             return childNames.equals(that.childNames);
663         }
664
665         @Override
666         public int hashCode() {
667             return childNames.hashCode();
668         }
669
670         @Override
671         public int compareTo(final PathArgument o) {
672             if (!(o instanceof AugmentationIdentifier)) {
673                 return -1;
674             }
675             AugmentationIdentifier other = (AugmentationIdentifier) o;
676             Set<QName> otherChildNames = other.getPossibleChildNames();
677             int thisSize = childNames.size();
678             int otherSize = otherChildNames.size();
679             if (thisSize == otherSize) {
680                 Iterator<QName> otherIterator = otherChildNames.iterator();
681                 for (QName name : childNames) {
682                     int c = name.compareTo(otherIterator.next());
683                     if (c != 0) {
684                         return c;
685                     }
686                 }
687                 return 0;
688             } else if (thisSize < otherSize) {
689                 return 1;
690             } else {
691                 return -1;
692             }
693         }
694     }
695
696     @Override
697     public final boolean contains(final YangInstanceIdentifier other) {
698         Preconditions.checkArgument(other != null, "other should not be null");
699
700         final Iterator<?> lit = getPathArguments().iterator();
701         final Iterator<?> oit = other.getPathArguments().iterator();
702
703         while (lit.hasNext()) {
704             if (!oit.hasNext()) {
705                 return false;
706             }
707
708             if (!lit.next().equals(oit.next())) {
709                 return false;
710             }
711         }
712
713         return true;
714     }
715
716     @Override
717     public final String toString() {
718         /*
719          * The toStringCache is safe, since the object contract requires
720          * immutability of the object and all objects referenced from this
721          * object.
722          * Used lists, maps are immutable. Path Arguments (elements) are also
723          * immutable, since the PathArgument contract requires immutability.
724          * The cache is thread-safe - if multiple computations occurs at the
725          * same time, cache will be overwritten with same result.
726          */
727         String ret = toStringCache;
728         if (ret == null) {
729             final StringBuilder builder = new StringBuilder("/");
730             PathArgument prev = null;
731             for (PathArgument argument : getPathArguments()) {
732                 if (prev != null) {
733                     builder.append('/');
734                 }
735                 builder.append(argument.toRelativeString(prev));
736                 prev = argument;
737             }
738
739             ret = builder.toString();
740             TOSTRINGCACHE_UPDATER.lazySet(this, ret);
741         }
742         return ret;
743     }
744 }