2 * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
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
8 package org.opendaylight.mdsal.dom.spi.query;
10 import static com.google.common.base.Verify.verify;
11 import static java.util.Objects.requireNonNull;
13 import com.google.common.base.MoreObjects;
14 import com.google.common.base.MoreObjects.ToStringHelper;
15 import com.google.common.collect.AbstractIterator;
16 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
17 import java.util.ArrayDeque;
18 import java.util.Iterator;
19 import java.util.List;
21 import java.util.Map.Entry;
22 import java.util.Optional;
23 import org.eclipse.jdt.annotation.NonNullByDefault;
24 import org.eclipse.jdt.annotation.Nullable;
25 import org.opendaylight.mdsal.dom.api.query.DOMQuery;
26 import org.opendaylight.mdsal.dom.api.query.DOMQueryPredicate;
27 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
29 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
30 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
31 import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
32 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
33 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
36 final class DOMQueryIterator extends AbstractIterator<Entry<YangInstanceIdentifier, NormalizedNode<?, ?>>> {
37 private static class Frame {
38 final NormalizedNode<?, ?> data;
39 final @Nullable PathArgument select;
41 @SuppressFBWarnings(value = "NP_STORE_INTO_NONNULL_FIELD", justification = "Ungrokked @Nullable")
42 Frame(final NormalizedNode<?, ?> data) {
43 this.data = requireNonNull(data);
44 // The only case when this can be null: if this a top-level container, as ensured by the sole caller
48 Frame(final NormalizedNode<?, ?> data, final PathArgument selectArg) {
49 this.data = requireNonNull(data);
50 this.select = requireNonNull(selectArg);
53 // Bimorphic invocation here, MapFrame checks with its iterator.
59 public final String toString() {
60 return addToStringAttributes(MoreObjects.toStringHelper(this).omitNullValues()).toString();
63 protected ToStringHelper addToStringAttributes(final ToStringHelper helper) {
64 return helper.add("data", data.getIdentifier()).add("select", select);
68 private static final class MapFrame extends Frame {
69 final Iterator<MapEntryNode> iter;
71 MapFrame(final NormalizedNode<?, ?> data, final PathArgument selectArg, final Iterator<MapEntryNode> iter) {
72 super(data, selectArg);
73 this.iter = requireNonNull(iter);
78 return iter.hasNext();
82 protected ToStringHelper addToStringAttributes(final ToStringHelper helper) {
83 return super.addToStringAttributes(helper).add("hasNext", iter.hasNext());
87 // Steps remaining in the select part of the query. @Nullable helps with null analysis with Deque.poll()
88 private final ArrayDeque<@Nullable PathArgument> remainingSelect = new ArrayDeque<>();
89 // Absolute path from root of current data item
90 private final ArrayDeque<PathArgument> currentPath = new ArrayDeque<>();
91 // Work backlog, in terms of frames that need to be processed
92 private final ArrayDeque<Frame> frames = new ArrayDeque<>();
93 // The predicates which need to be evaluated
94 private final List<? extends DOMQueryPredicate> predicates;
96 DOMQueryIterator(final DOMQuery query, final NormalizedNode<?, ?> queryRoot) {
97 // Note: DOMQueryEvaluator has taken care of the empty case, this is always non-empty
98 remainingSelect.addAll(query.getSelect().getPathArguments());
99 currentPath.addAll(query.getRoot().getPathArguments());
100 predicates = query.getPredicates();
101 frames.push(new Frame(queryRoot));
105 protected Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> computeNext() {
106 final Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> next = findNext();
107 return next != null ? next : endOfData();
110 @SuppressFBWarnings(value = "NP_NONNULL_RETURN_VIOLATION", justification = "Ungrokked @Nullable")
111 // TODO: this is a huge method which could be restructured with hard tailcalls, alas we do not have those (yet?)
112 // Any such refactor better have some benchmarks to show non-regression.
113 private @Nullable Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> findNext() {
114 // We always start with non-empty frames, as we signal end of data when we reach the end. 'currentPath' points
115 // to the next frame to process.
117 // We know this is never null and would have preferred to use pop(), but Eclipse insists. We do not care
118 // (that much) and use a poll() here.
119 Frame current = frames.poll();
120 while (current != null) {
121 // Whenever we reach here, 'currentPath' points to the 'current' entry, while 'frames' has current's parent
122 // on top. Every 'continue' site in this block is expected to maintain that invariant.
123 // Furthermore all 'return' sites are expected to leave 'frames' and 'currentPath' consistent, otherwise
124 // next invocation of this method would violate this invariant.
126 // Look what's next in the 'select' part of the lookup
127 final PathArgument next = remainingSelect.poll();
129 // We are matching this frame, and if we got here it must have a stashed iterator, as we deal with
130 // single match entries without using the stack. Look for first matching child and return it.
131 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
132 while (iter.hasNext()) {
133 final MapEntryNode child = iter.next();
134 if (matches(child)) {
135 return pushAndReturn(current, child);
139 // Unwind this frame's state and select the next frame from the stack
140 current = unwind(current.select);
144 // Alright, here we are looking for a child to select. This is where things get dicey, as there is a number
147 // 1. we are iterating a map. We are matching the next child against 'next', which can have a number of
148 // outcomes in and of itself.
149 if (current instanceof MapFrame) {
150 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
151 if (remainingSelect.isEmpty()) {
152 // ... so all of 1) and this is the last-step map. In this case we want to find the next matching
153 // child without going to stack. We want to push next back, though, as we either need to resume
154 // from it (arriving back here), or will have dealt with it.
155 while (iter.hasNext()) {
156 final MapEntryNode child = iter.next();
157 if (matches(child)) {
158 remainingSelect.push(next);
159 return pushAndReturn(current, child);
163 // Unwind frames and retry
164 current = unwind(current, next);
168 // ... so all of 1) but this time this is an intermediate step. If we have a child, we'll push the map
169 // entry and set the child frame as current. Let the loop deal with the rest of the lookup.
170 if (iter.hasNext()) {
171 final MapEntryNode child = iter.next();
172 frames.push(current);
173 currentPath.addLast(child.getIdentifier());
174 current = new Frame(child, next);
178 // ... all of 1) but we do not have any more children to match. Discard this frame and move on.
179 current = unwind(current, next);
183 // 2. we are at a normal container, where we need to resolve a child. This is also a bit involved, so now:
184 final Optional<NormalizedNode<?, ?>> optChild = NormalizedNodes.getDirectChild(current.data, next);
185 if (optChild.isEmpty()) {
186 // If we did not find the child, as we can have only a single match. Unwind to next possible match.
187 current = unwind(current, next);
191 // If we have a child see if this is the ultimate select step, if so, short circuit stack. We do not record
193 final NormalizedNode<?, ?> child = optChild.orElseThrow();
194 if (remainingSelect.isEmpty()) {
195 // This is the ultimate step in lookup, process it without churning the stack by imposing a dedicated
196 // Frame. In either case we are done with this frame, unwinding it in both cases.
197 if (matches(child)) {
198 return unwindAndReturn(current, next, child);
201 current = unwind(current, next);
205 // Now decide what sort of entry to push. For maps we want to start an iterator already, so it gets
206 // picked up as a continuation.
207 if (child instanceof MapNode) {
208 final MapNode map = (MapNode) child;
209 final PathArgument target = remainingSelect.peek();
210 if (target instanceof NodeIdentifierWithPredicates) {
211 final Optional<MapEntryNode> optEntry = map.getChild((NodeIdentifierWithPredicates) target);
212 if (optEntry.isPresent()) {
213 final MapEntryNode entry = optEntry.orElseThrow();
214 if (remainingSelect.size() != 1) {
215 // We need to perform further selection push this frame, an empty frame for the map and
216 // finally a frame for the map entry.
217 remainingSelect.pop();
218 frames.push(current);
219 currentPath.addLast(map.getIdentifier());
220 frames.push(new Frame(map, next));
221 currentPath.addLast(target);
222 current = new Frame(entry, target);
226 // We have selected entry, see it it matches. In any case rewind, potentially returning
228 if (matches(entry)) {
229 return unwindAndReturn(current, next, entry);
233 // We failed to find a matching entry, unwind
234 current = unwind(current, next);
238 // We have a wildcard, expand it
239 frames.push(current);
240 currentPath.addLast(next);
241 current = new MapFrame(child, next, map.getValue().iterator());
243 // Next step in iteration, deal with it
244 frames.push(current);
245 currentPath.addLast(child.getIdentifier());
246 current = new Frame(child, next);
250 // All done, there be entries no more.
251 // Consistency check and clear leftover state
252 verify(frames.isEmpty());
253 remainingSelect.clear();
258 // Construct child path. This concatenates currentPath and child's identifier.
259 private YangInstanceIdentifier createIdentifier(final NormalizedNode<?, ?> child) {
260 currentPath.addLast(child.getIdentifier());
261 final YangInstanceIdentifier ret = YangInstanceIdentifier.create(currentPath);
262 currentPath.removeLast();
266 // Save a frame for further processing return its child as an item.
267 private Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> pushAndReturn(final Frame frame,
268 final MapEntryNode child) {
269 final YangInstanceIdentifier childPath = createIdentifier(child);
271 // Push the frame back to work, return the result
273 return Map.entry(childPath, child);
276 // Unwind any leftover frames and return a matching item
277 private Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> unwindAndReturn(final Frame frame,
278 final PathArgument next, final NormalizedNode<?, ?> child) {
279 final YangInstanceIdentifier childPath = createIdentifier(child);
281 return Map.entry(childPath, child);
285 * Unwind the stack, discarding current frame, and possibly some others. The unwind starts with pushing {@code next}
286 * to {@link #remainingSelect}, hence we remember to handle it next time around. It then defers to
287 * {@link #unwind(PathArgument)}.
289 * @param current Current frame
290 * @param next Next path argument to lookup (after this frame)
291 * @return Next frame to process, null if there is no other work
293 private @Nullable Frame unwind(final Frame current, final PathArgument next) {
294 remainingSelect.push(next);
295 return unwind(current.select);
299 * Unwind the stack, discarding current frame, and possibly some others. Unwind removes contents of
300 * {@link #currentPath}, walking back towards the query root.
303 * Since we are unwinding a data item, we pop its path -- hence {@link #currentPath} points to the parent path.
304 * We then examine {@link Frame#select} to see if it's null -- if it is, we have reached the top-most frame and
305 * hence have nothing left to do.
308 * Otherwise we remember {@code select} back to {@link #remainingSelect} and pop the next frame to be processed.
309 * If the frame does not have work, as indicated by {@link Frame#hasNext()}, we unwind it as well.
312 * We repeat this process until we find a frame with some work or we run out of frames.
314 * @param current Current frame
315 * @param next Next path argument to lookup (after this frame)
316 * @return Next frame to process, null if there is no other work
318 @SuppressFBWarnings(value = "NP_NONNULL_RETURN_VIOLATION", justification = "Ungrokked @Nullable")
319 private @Nullable Frame unwind(final @Nullable PathArgument selectArg) {
320 @Nullable PathArgument select = selectArg;
322 currentPath.removeLast();
323 if (select == null) {
324 verify(frames.isEmpty());
328 remainingSelect.push(select);
329 // pop() for its state-checking properties. Last frame should have had select == null and we would have
331 final Frame next = frames.pop();
332 if (next.hasNext()) {
335 select = next.select;
339 private boolean matches(final NormalizedNode<?, ?> data) {
340 return DOMQueryMatcher.matchesAll(data, predicates);