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 private @Nullable Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> findNext() {
112 // We always start with non-empty frames, as we signal end of data when we reach the end. We know this never
113 // null, by Eclipse insists. We do not care (that much) and use a poll() here.
114 // TODO: this is a huge method which could be restructured with hard tailcalls, alas we do not have those (yet?)
115 // Any such refactor better have some benchmarks to show non-regression.
116 Frame current = frames.poll();
117 while (current != null) {
118 final PathArgument next = remainingSelect.poll();
120 // We are matching this frame, and if we got here it must have a stashed iterator, as we deal with
121 // single match entries without using the stack. Look for first matching child and return it.
122 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
123 while (iter.hasNext()) {
124 final MapEntryNode child = iter.next();
125 if (matches(child)) {
126 return pushAndReturn(current, child);
130 // Unwind this frame's state and select the next frame from the stack
131 current = unwind(current.select);
135 // Alright, here we are looking for a child to select. This is where things get dicey, as there is a number
138 // 1. we are iterating a map. We are matching the next child against 'next', which can have a number of
139 // outcomes in and of itself.
140 if (current instanceof MapFrame) {
141 final Iterator<MapEntryNode> iter = ((MapFrame) current).iter;
142 if (remainingSelect.isEmpty()) {
143 // ... so all of 1) and this is the last-step map. In this case we want to find the next matching
144 // child without going to stack. We want to push next back, though, as we either need to resume
145 // from it (arriving back here), or will have dealt with it.
146 while (iter.hasNext()) {
147 final MapEntryNode child = iter.next();
148 if (matches(child)) {
149 remainingSelect.push(next);
150 return pushAndReturn(current, child);
154 // Unwind frames and retry
155 current = unwind(current, next);
159 // ... so all of 1) but this time this is an intermediate step. If we have a child, we'll push the map
160 // entry and set the child frame as current. Let the loop deal with the rest of the lookup.
161 if (iter.hasNext()) {
162 final MapEntryNode child = iter.next();
163 frames.push(current);
164 currentPath.addLast(child.getIdentifier());
165 current = new Frame(child, next);
169 // ... all of 1) but we do not have any more children to match. Discard this frame and move on.
170 current = unwind(current, next);
174 // 2. we are at a normal container, where we need to resolve a child. This is also a bit involved, so now:
175 final Optional<NormalizedNode<?, ?>> optChild = NormalizedNodes.getDirectChild(current.data, next);
176 if (optChild.isEmpty()) {
177 // If we did not find the child, as we can have only a single match. Unwind to next possible match.
178 current = unwind(current, next);
182 // If we have a child see if this is the ultimate select step, if so, short circuit stack. We do not record
184 final NormalizedNode<?, ?> child = optChild.orElseThrow();
185 if (remainingSelect.isEmpty()) {
186 // This is the ultimate step in lookup, process it without churning the stack by imposing a dedicated
187 // Frame. In either case we are done with this frame, unwinding it in both cases.
188 if (matches(child)) {
189 return unwindAndReturn(current, next, child);
192 current = unwind(current, next);
196 // Push our state back, it's just a placeholder for 'currentSelect'. Current path points at us and so does
198 currentPath.addLast(current.data.getIdentifier());
200 // Now decide what sort of entry to push. For maps we want to start an iterator already, so it gets
201 // picked up as a continuation.
202 if (child instanceof MapNode) {
203 final MapNode map = (MapNode) child;
204 final PathArgument target = remainingSelect.peek();
205 if (target instanceof NodeIdentifierWithPredicates) {
206 final Optional<MapEntryNode> optEntry = map.getChild((NodeIdentifierWithPredicates) target);
207 if (optEntry.isPresent()) {
208 final MapEntryNode entry = optEntry.orElseThrow();
209 if (remainingSelect.size() != 1) {
210 // We need to perform further selection push this frame, an empty frame for the map and
211 // finally a frame for the map entry.
212 remainingSelect.pop();
213 frames.push(current);
214 currentPath.addLast(map.getIdentifier());
215 frames.push(new Frame(map, next));
216 current = new Frame(entry, target);
220 // We have selected entry, see it it matches. In any case rewind, potentially returning
222 if (matches(entry)) {
223 return unwindAndReturn(current, next, entry);
227 // We failed to find a matching entry, unwind
228 current = unwind(current, next);
232 // We have a wildcard, expand it
233 frames.push(current);
234 current = new MapFrame(child, next, map.getValue().iterator());
236 // Next step in iteration, deal with it
237 frames.push(current);
238 current = new Frame(child, next);
242 // All done, there be entries no more.
243 // Consistency check and clear leftover state
244 verify(frames.isEmpty());
245 remainingSelect.clear();
250 // Construct child path. This concatenates currentPath and child's identifier.
251 private YangInstanceIdentifier createIdentifier(final NormalizedNode<?, ?> child) {
252 currentPath.addLast(child.getIdentifier());
253 final YangInstanceIdentifier ret = YangInstanceIdentifier.create(currentPath);
254 currentPath.removeLast();
258 // Save a frame for further processing return its child as an item.
259 private Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> pushAndReturn(final Frame frame,
260 final MapEntryNode child) {
261 final YangInstanceIdentifier childPath = createIdentifier(child);
263 // Push the frame back to work, return the result
265 return Map.entry(childPath, child);
268 // Unwind any leftover frames and return a matching item
269 private Entry<YangInstanceIdentifier, NormalizedNode<?, ?>> unwindAndReturn(final Frame frame,
270 final PathArgument next, final NormalizedNode<?, ?> child) {
271 final YangInstanceIdentifier childPath = createIdentifier(child);
273 return Map.entry(childPath, child);
277 * Unwind the stack, discarding current frame, and possibly some others. The unwind starts with pushing {@code next}
278 * to {@link #remainingSelect}, hence we remember to handle it next time around. It then defers to
279 * {@link #unwind(PathArgument)}.
281 * @param current Current frame
282 * @param next Next path argument to lookup (after this frame)
283 * @return Next frame to process, null if there is no other work
285 private @Nullable Frame unwind(final Frame current, final PathArgument next) {
286 remainingSelect.push(next);
287 return unwind(current.select);
291 * Unwind the stack, discarding current frame, and possibly some others. Unwind removes contents of
292 * {@link #currentPath}, walking back towards the query root.
295 * Since we are unwinding a data item, we pop its path -- hence {@link #currentPath} points to the parent path.
296 * We then examine {@link Frame#select} to see if it's null -- if it is, we have reached the top-most frame and
297 * hence have nothing left to do.
300 * Otherwise we remember {@code select} back to {@link #remainingSelect} and pop the next frame to be processed.
301 * If the frame does not have work, as indicated by {@link Frame#hasNext()}, we unwind it as well.
304 * We repeat this process until we find a frame with some work or we run out of frames.
306 * @param current Current frame
307 * @param next Next path argument to lookup (after this frame)
308 * @return Next frame to process, null if there is no other work
310 @SuppressFBWarnings(value = "NP_NONNULL_RETURN_VIOLATION", justification = "Ungrokked @Nullable")
311 private @Nullable Frame unwind(final @Nullable PathArgument selectArg) {
312 @Nullable PathArgument select = selectArg;
314 currentPath.removeLast();
315 if (select == null) {
316 verify(frames.isEmpty());
320 remainingSelect.push(select);
321 // pop() for its state-checking properties. Last frame should have had select == null and we would have
323 final Frame next = frames.pop();
324 if (next.hasNext()) {
327 select = next.select;
331 private boolean matches(final NormalizedNode<?, ?> data) {
332 return DOMQueryMatcher.matches(data, predicates);