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.AbstractMap.SimpleImmutableEntry;
18 import java.util.ArrayDeque;
19 import java.util.Iterator;
20 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.PathArgument;
29 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
30 import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
31 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
32 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
35 final class LazyDOMQueryResultIterator extends AbstractIterator<Entry<YangInstanceIdentifier, NormalizedNode<?, ?>>> {
36 private static class Frame {
37 final NormalizedNode<?, ?> data;
38 final @Nullable PathArgument select;
40 @SuppressFBWarnings(value = "NP_STORE_INTO_NONNULL_FIELD", justification = "Ungrokked @Nullable")
41 Frame(final NormalizedNode<?, ?> data) {
42 this.data = requireNonNull(data);
43 // The only case when this can be null: if this a top-level container, as ensured by the sole caller
47 Frame(final NormalizedNode<?, ?> data, final PathArgument selectArg) {
48 this.data = requireNonNull(data);
49 this.select = requireNonNull(selectArg);
52 // Bimorphic invocation here, MapFrame checks with its iterator.
58 public final String toString() {
59 return addToStringAttributes(MoreObjects.toStringHelper(this).omitNullValues()).toString();
62 protected ToStringHelper addToStringAttributes(final ToStringHelper helper) {
63 return helper.add("data", data.getIdentifier()).add("select", select);
67 private static final class MapFrame extends Frame {
68 final Iterator<MapEntryNode> iter;
70 MapFrame(final NormalizedNode<?, ?> data, final PathArgument selectArg, final Iterator<MapEntryNode> iter) {
71 super(data, selectArg);
72 this.iter = requireNonNull(iter);
77 return iter.hasNext();
81 protected ToStringHelper addToStringAttributes(final ToStringHelper helper) {
82 return super.addToStringAttributes(helper).add("hasNext", iter.hasNext());
86 // Steps remaining in the select part of the query. @Nullable helps with null analysis with Deque.poll()
87 private final ArrayDeque<@Nullable PathArgument> remainingSelect = new ArrayDeque<>();
88 // Absolute path from root of current data item
89 private final ArrayDeque<PathArgument> currentPath = new ArrayDeque<>();
90 // Work backlog, in terms of frames that need to be processed
91 private final ArrayDeque<Frame> frames = new ArrayDeque<>();
92 // The predicates which need to be evaluated
93 private final List<? extends DOMQueryPredicate> predicates;
95 LazyDOMQueryResultIterator(final DOMQuery query, final NormalizedNode<?, ?> queryRoot) {
96 // Note: DOMQueryEvaluator has taken care of the empty case, this is always non-empty
97 remainingSelect.addAll(query.getSelect().getPathArguments());
98 currentPath.addAll(query.getRoot().getPathArguments());
99 predicates = query.getPredicates();
100 frames.push(new Frame(queryRoot));
104 protected Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> computeNext() {
105 final Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> next = findNext();
106 return next != null ? next : endOfData();
109 @SuppressFBWarnings(value = "NP_NONNULL_RETURN_VIOLATION", justification = "Ungrokked @Nullable")
110 private @Nullable Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> findNext() {
111 // We always start with non-empty frames, as we signal end of data when we reach the end. We know this never
112 // null, by Eclipse insists. We do not care (that much) and use a poll() here.
113 // TODO: this is a huge method which could be restructured with hard tailcalls, alas we do not have those (yet?)
114 // Any such refactor better have some benchmarks to show non-regression.
115 Frame current = frames.poll();
116 while (current != null) {
117 final PathArgument next = remainingSelect.poll();
119 // We are matching this frame, and if we got here it must have a stashed iterator, as we deal with
120 // single match entries without using the stack. Look for first matching child and return it.
121 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
122 while (iter.hasNext()) {
123 final MapEntryNode child = iter.next();
124 if (matches(child)) {
125 return pushAndReturn(current, child);
129 // Unwind this frame's state and select the next frame from the stack
130 current = unwind(current.select);
134 // Alright, here we are looking for a child to select. This is where things get dicey, as there is a number
137 // 1. we are iterating a map. We are matching the next child against 'next', which can have a number of
138 // outcomes in and of itself.
139 if (current instanceof MapFrame) {
140 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
141 if (remainingSelect.isEmpty()) {
142 // ... so all of 1) and this is the last-step map. In this case we want to find the next matching
143 // child without going to stack. We want to push next back, though, as we either need to resume
144 // from it (arriving back here), or will have dealt with it.
145 while (iter.hasNext()) {
146 final MapEntryNode child = iter.next();
147 if (matches(child)) {
148 remainingSelect.push(next);
149 return pushAndReturn(current, child);
153 // Unwind frames and retry
154 current = unwind(current, next);
158 // ... so all of 1) but this time this is an intermediate step. If we have a child, we'll push the map
159 // entry and set the child frame as current. Let the loop deal with the rest of the lookup.
160 if (iter.hasNext()) {
161 final MapEntryNode child = iter.next();
162 frames.push(current);
163 currentPath.addLast(child.getIdentifier());
164 current = new Frame(child, next);
168 // ... all of 1) but we do not have any more children to match. Discard this frame and move on.
169 current = unwind(current, next);
173 // 2. we are at a normal container, where we need to resolve a child. This is also a bit involved, so now:
174 final Optional<NormalizedNode<?, ?>> optChild = NormalizedNodes.getDirectChild(current.data, next);
175 if (optChild.isEmpty()) {
176 // If we did not find the child, as we can have only a single match. Unwind to next possible match.
177 current = unwind(current, next);
181 // If we have a child see if this is the ultimate select step, if so, short circuit stack. We do not record
183 final NormalizedNode<?, ?> child = optChild.orElseThrow();
184 if (remainingSelect.isEmpty()) {
185 // This is the ultimate step in lookup, process it without churning the stack by imposing a dedicated
186 // Frame. In either case we are done with this frame, unwinding it in both cases.
187 if (matches(child)) {
188 final YangInstanceIdentifier childPath = createIdentifier(child);
189 unwind(current, next);
190 return new SimpleImmutableEntry<>(childPath, child);
193 current = unwind(current, next);
197 // Push our state back, it's just a placeholder for 'currentSelect'. Current path points at us and so does
199 currentPath.addLast(current.data.getIdentifier());
200 frames.push(current);
202 // Now decide what sort of entry to push. For maps we want to start an iterator already, so it gets
203 // picked up as a continuation.
204 current = child instanceof MapNode ? new MapFrame(child, next, ((MapNode) child).getValue().iterator())
205 : new Frame(child, next);
208 // All done, there be entries no more.
209 // Consistency check and clear leftover state
210 verify(frames.isEmpty());
211 remainingSelect.clear();
216 // Construct child path. This concatenates currentPath and child's identifier.
217 private YangInstanceIdentifier createIdentifier(final NormalizedNode<?, ?> child) {
218 currentPath.addLast(child.getIdentifier());
219 final YangInstanceIdentifier ret = YangInstanceIdentifier.create(currentPath);
220 currentPath.removeLast();
224 // Save a frame for further processing return its child as an item.
225 private Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> pushAndReturn(final Frame frame,
226 final MapEntryNode child) {
227 final YangInstanceIdentifier childPath = createIdentifier(child);
229 // Push the frame back to work, return the result
231 return new SimpleImmutableEntry<>(childPath, child);
235 * Unwind the stack, discarding current frame, and possibly some others. The unwind starts with pushing {@code next}
236 * to {@link #remainingSelect}, hence we remember to handle it next time around. It then defers to
237 * {@link #unwind(PathArgument)}.
239 * @param current Current frame
240 * @param next Next path argument to lookup (after this frame)
241 * @return Next frame to process, null if there is no other work
243 private @Nullable Frame unwind(final Frame current, final PathArgument next) {
244 remainingSelect.push(next);
245 return unwind(current.select);
249 * Unwind the stack, discarding current frame, and possibly some others. Unwind removes contents of
250 * {@link #currentPath}, walking back towards the query root.
253 * Since we are unwinding a data item, we pop its path -- hence {@link #currentPath} points to the parent path.
254 * We then examine {@link Frame#select} to see if it's null -- if it is, we have reached the top-most frame and
255 * hence have nothing left to do.
258 * Otherwise we remember {@code select} back to {@link #remainingSelect} and pop the next frame to be processed.
259 * If the frame does not have work, as indicated by {@link Frame#hasNext()}, we unwind it as well.
262 * We repeat this process until we find a frame with some work or we run out of frames.
264 * @param current Current frame
265 * @param next Next path argument to lookup (after this frame)
266 * @return Next frame to process, null if there is no other work
268 @SuppressFBWarnings(value = "NP_NONNULL_RETURN_VIOLATION", justification = "Ungrokked @Nullable")
269 private @Nullable Frame unwind(final @Nullable PathArgument selectArg) {
270 @Nullable PathArgument select = selectArg;
272 currentPath.removeLast();
273 if (select == null) {
274 verify(frames.isEmpty());
278 remainingSelect.push(select);
279 // pop() for its state-checking properties. Last frame should have had select == null and we would have
281 final Frame next = frames.pop();
282 if (next.hasNext()) {
285 select = next.select;
289 private boolean matches(final NormalizedNode<?, ?> data) {
290 return matches(data, predicates);
293 static boolean matches(final NormalizedNode<?, ?> data, final List<? extends DOMQueryPredicate> predicates) {
294 for (DOMQueryPredicate pred : predicates) {
295 // Okay, now we need to deal with predicates, but do it in a smart fashion, so we do not end up iterating
296 // all over the place. Typically we will be matching just a leaf.
297 final YangInstanceIdentifier path = pred.getPath();
298 final Optional<NormalizedNode<?, ?>> node;
299 if (path.coerceParent().isEmpty()) {
300 node = NormalizedNodes.getDirectChild(data, path.getLastPathArgument());
302 node = NormalizedNodes.findNode(data, path);
305 if (!pred.test(node.orElse(null))) {