BUG-1493: split off recursion tracking and rework it
[controller.git] / opendaylight / md-sal / sal-inmemory-datastore / src / main / java / org / opendaylight / controller / md / sal / dom / store / impl / ResolveDataChangeEventsTask.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.controller.md.sal.dom.store.impl;
9
10 import com.google.common.base.Optional;
11 import com.google.common.base.Preconditions;
12 import com.google.common.collect.ArrayListMultimap;
13 import com.google.common.collect.Multimap;
14
15 import java.util.ArrayList;
16 import java.util.Collection;
17 import java.util.Map.Entry;
18 import java.util.concurrent.Callable;
19
20 import org.opendaylight.controller.md.sal.common.api.data.AsyncDataBroker.DataChangeScope;
21 import org.opendaylight.controller.md.sal.common.api.data.AsyncDataChangeEvent;
22 import org.opendaylight.controller.md.sal.common.api.data.AsyncDataChangeListener;
23 import org.opendaylight.controller.md.sal.dom.store.impl.DOMImmutableDataChangeEvent.Builder;
24 import org.opendaylight.controller.md.sal.dom.store.impl.DOMImmutableDataChangeEvent.SimpleEventFactory;
25 import org.opendaylight.controller.md.sal.dom.store.impl.tree.ListenerTree;
26 import org.opendaylight.controller.md.sal.dom.store.impl.tree.ListenerTree.Walker;
27 import org.opendaylight.yangtools.util.concurrent.NotificationManager;
28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
29 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
30 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodeContainer;
31 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidate;
32 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidateNode;
33 import org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType;
34 import org.slf4j.Logger;
35 import org.slf4j.LoggerFactory;
36
37 /**
38  * Resolve Data Change Events based on modifications and listeners
39  *
40  * Computes data change events for all affected registered listeners in data
41  * tree.
42  */
43 final class ResolveDataChangeEventsTask implements Callable<Iterable<ChangeListenerNotifyTask>> {
44     private static final Logger LOG = LoggerFactory.getLogger(ResolveDataChangeEventsTask.class);
45
46     @SuppressWarnings("rawtypes")
47     private final NotificationManager<AsyncDataChangeListener, AsyncDataChangeEvent> notificationMgr;
48     private final DataTreeCandidate candidate;
49     private final ListenerTree listenerRoot;
50
51     private Multimap<DataChangeListenerRegistration<?>, DOMImmutableDataChangeEvent> collectedEvents;
52
53     @SuppressWarnings("rawtypes")
54     public ResolveDataChangeEventsTask(final DataTreeCandidate candidate, final ListenerTree listenerTree,
55             final NotificationManager<AsyncDataChangeListener, AsyncDataChangeEvent> notificationMgr) {
56         this.candidate = Preconditions.checkNotNull(candidate);
57         this.listenerRoot = Preconditions.checkNotNull(listenerTree);
58         this.notificationMgr = Preconditions.checkNotNull(notificationMgr);
59     }
60
61     /**
62      * Resolves and creates Notification Tasks
63      *
64      * Implementation of done as Map-Reduce with two steps: 1. resolving events
65      * and their mapping to listeners 2. merging events affecting same listener
66      *
67      * @return An {@link Iterable} of Notification Tasks which needs to be executed in
68      *         order to delivery data change events.
69      */
70     @Override
71     public synchronized Iterable<ChangeListenerNotifyTask> call() {
72         try (final Walker w = listenerRoot.getWalker()) {
73             // Defensive: reset internal state
74             collectedEvents = ArrayListMultimap.create();
75
76             // Run through the tree
77             final ResolveDataChangeState s = ResolveDataChangeState.initial(candidate.getRootPath(), w.getRootNode());
78             resolveAnyChangeEvent(s, candidate.getRootNode());
79
80             /*
81              * Convert to tasks, but be mindful of multiple values -- those indicate multiple
82              * wildcard matches, which need to be merged.
83              */
84             final Collection<ChangeListenerNotifyTask> ret = new ArrayList<>();
85             for (Entry<DataChangeListenerRegistration<?>, Collection<DOMImmutableDataChangeEvent>> e : collectedEvents.asMap().entrySet()) {
86                 final Collection<DOMImmutableDataChangeEvent> col = e.getValue();
87                 final DOMImmutableDataChangeEvent event;
88
89                 if (col.size() != 1) {
90                     final Builder b = DOMImmutableDataChangeEvent.builder(DataChangeScope.BASE);
91                     for (DOMImmutableDataChangeEvent i : col) {
92                         b.merge(i);
93                     }
94
95                     event = b.build();
96                     LOG.trace("Merged events {} into event {}", col, event);
97                 } else {
98                     event = col.iterator().next();
99                 }
100
101                 ret.add(new ChangeListenerNotifyTask(e.getKey(), event, notificationMgr));
102             }
103
104             // FIXME: so now we have tasks to submit tasks... Inception-style!
105             LOG.debug("Created tasks {}", ret);
106             return ret;
107         }
108     }
109
110     /**
111      * Resolves data change event for supplied node
112      *
113      * @param path
114      *            Path to current node in tree
115      * @param listeners
116      *            Collection of Listener registration nodes interested in
117      *            subtree
118      * @param modification
119      *            Modification of current node
120      * @param before
121      *            - Original (before) state of current node
122      * @param after
123      *            - After state of current node
124      * @return True if the subtree changed, false otherwise
125      */
126     private boolean resolveAnyChangeEvent(final ResolveDataChangeState state, final DataTreeCandidateNode node) {
127         if (node.getModificationType() != ModificationType.UNMODIFIED &&
128                 !node.getDataAfter().isPresent() && !node.getDataBefore().isPresent()) {
129             LOG.debug("Modification at {} has type {}, but no before- and after-data. Assuming unchanged.",
130                     state.getPath(), node.getModificationType());
131             return false;
132         }
133
134         // no before and after state is present
135
136         switch (node.getModificationType()) {
137         case SUBTREE_MODIFIED:
138             return resolveSubtreeChangeEvent(state, node);
139         case MERGE:
140         case WRITE:
141             Preconditions.checkArgument(node.getDataAfter().isPresent(),
142                     "Modification at {} has type {} but no after-data", state.getPath(), node.getModificationType());
143             if (!node.getDataBefore().isPresent()) {
144                 resolveCreateEvent(state, node.getDataAfter().get());
145                 return true;
146             }
147
148             return resolveReplacedEvent(state, node.getDataBefore().get(), node.getDataAfter().get());
149         case DELETE:
150             Preconditions.checkArgument(node.getDataBefore().isPresent(),
151                     "Modification at {} has type {} but no before-data", state.getPath(), node.getModificationType());
152             resolveDeleteEvent(state, node.getDataBefore().get());
153             return true;
154         case UNMODIFIED:
155             return false;
156         }
157
158         throw new IllegalStateException(String.format("Unhandled node state %s at %s", node.getModificationType(), state.getPath()));
159     }
160
161     private boolean resolveReplacedEvent(final ResolveDataChangeState state,
162             final NormalizedNode<?, ?> beforeData, final NormalizedNode<?, ?> afterData) {
163
164         if (beforeData instanceof NormalizedNodeContainer<?, ?, ?>) {
165             /*
166              * Node is a container (contains a child) and we have interested
167              * listeners registered for it, that means we need to do
168              * resolution of changes on children level and can not
169              * shortcut resolution.
170              */
171             LOG.trace("Resolving subtree replace event for {} before {}, after {}", state.getPath(), beforeData, afterData);
172             @SuppressWarnings("unchecked")
173             NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>> beforeCont = (NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>>) beforeData;
174             @SuppressWarnings("unchecked")
175             NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>> afterCont = (NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>>) afterData;
176             return resolveNodeContainerReplaced(state, beforeCont, afterCont);
177         }
178
179         // Node is a Leaf type (does not contain child nodes)
180         // so normal equals method is sufficient for determining change.
181         if (beforeData.equals(afterData)) {
182             LOG.trace("Skipping equal leaf {}", state.getPath());
183             return false;
184         }
185
186         LOG.trace("Resolving leaf replace event for {} , before {}, after {}", state.getPath(), beforeData, afterData);
187         DOMImmutableDataChangeEvent event = DOMImmutableDataChangeEvent.builder(DataChangeScope.BASE).addUpdated(state.getPath(), beforeData, afterData).build();
188         state.addEvent(event);
189         state.collectEvents(beforeData, afterData, collectedEvents);
190         return true;
191     }
192
193     private boolean resolveNodeContainerReplaced(final ResolveDataChangeState state,
194             final NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>> beforeCont,
195                     final NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>> afterCont) {
196         if (!state.needsProcessing()) {
197             LOG.trace("Not processing replaced container {}", state.getPath());
198             return true;
199         }
200
201         // We look at all children from before and compare it with after state.
202         boolean childChanged = false;
203         for (NormalizedNode<PathArgument, ?> beforeChild : beforeCont.getValue()) {
204             final PathArgument childId = beforeChild.getIdentifier();
205
206             if (resolveNodeContainerChildUpdated(state.child(childId), beforeChild, afterCont.getChild(childId))) {
207                 childChanged = true;
208             }
209         }
210
211         for (NormalizedNode<PathArgument, ?> afterChild : afterCont.getValue()) {
212             final PathArgument childId = afterChild.getIdentifier();
213
214             /*
215              * We have already iterated of the before-children, so have already
216              * emitted modify/delete events. This means the child has been
217              * created.
218              */
219             if (!beforeCont.getChild(childId).isPresent()) {
220                 resolveSameEventRecursivelly(state.child(childId), afterChild, DOMImmutableDataChangeEvent.getCreateEventFactory());
221                 childChanged = true;
222             }
223         }
224
225         if (childChanged) {
226             DOMImmutableDataChangeEvent event = DOMImmutableDataChangeEvent.builder(DataChangeScope.BASE)
227                     .addUpdated(state.getPath(), beforeCont, afterCont).build();
228             state.addEvent(event);
229         }
230
231         state.collectEvents(beforeCont, afterCont, collectedEvents);
232         return childChanged;
233     }
234
235     private boolean resolveNodeContainerChildUpdated(final ResolveDataChangeState state,
236             final NormalizedNode<PathArgument, ?> before, final Optional<NormalizedNode<PathArgument, ?>> after) {
237         if (after.isPresent()) {
238             // REPLACE or SUBTREE Modified
239             return resolveReplacedEvent(state, before, after.get());
240         }
241
242         // AFTER state is not present - child was deleted.
243         resolveSameEventRecursivelly(state, before, DOMImmutableDataChangeEvent.getRemoveEventFactory());
244         return true;
245     }
246
247     /**
248      * Resolves create events deep down the interest listener tree.
249      *
250      * @param path
251      * @param listeners
252      * @param afterState
253      * @return
254      */
255     private void resolveCreateEvent(final ResolveDataChangeState state, final NormalizedNode<?, ?> afterState) {
256         @SuppressWarnings({ "unchecked", "rawtypes" })
257         final NormalizedNode<PathArgument, ?> node = (NormalizedNode) afterState;
258         resolveSameEventRecursivelly(state, node, DOMImmutableDataChangeEvent.getCreateEventFactory());
259     }
260
261     private void resolveDeleteEvent(final ResolveDataChangeState state, final NormalizedNode<?, ?> beforeState) {
262         @SuppressWarnings({ "unchecked", "rawtypes" })
263         final NormalizedNode<PathArgument, ?> node = (NormalizedNode) beforeState;
264         resolveSameEventRecursivelly(state, node, DOMImmutableDataChangeEvent.getRemoveEventFactory());
265     }
266
267     private void resolveSameEventRecursivelly(final ResolveDataChangeState state,
268             final NormalizedNode<PathArgument, ?> node, final SimpleEventFactory eventFactory) {
269         if (!state.needsProcessing()) {
270             LOG.trace("Skipping child {}", state.getPath());
271             return;
272         }
273
274         // We have listeners for this node or it's children, so we will try
275         // to do additional processing
276         if (node instanceof NormalizedNodeContainer<?, ?, ?>) {
277             LOG.trace("Resolving subtree recursive event for {}, type {}", state.getPath(), eventFactory);
278
279             // Node has children, so we will try to resolve it's children
280             // changes.
281             @SuppressWarnings("unchecked")
282             NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>> container = (NormalizedNodeContainer<?, PathArgument, NormalizedNode<PathArgument, ?>>) node;
283             for (NormalizedNode<PathArgument, ?> child : container.getValue()) {
284                 final PathArgument childId = child.getIdentifier();
285
286                 LOG.trace("Resolving event for child {}", childId);
287                 resolveSameEventRecursivelly(state.child(childId), child, eventFactory);
288             }
289         }
290
291         final DOMImmutableDataChangeEvent event = eventFactory.create(state.getPath(), node);
292         LOG.trace("Adding event {} at path {}", event, state.getPath());
293         state.addEvent(event);
294         state.collectEvents(event.getOriginalSubtree(), event.getUpdatedSubtree(), collectedEvents);
295     }
296
297     private boolean resolveSubtreeChangeEvent(final ResolveDataChangeState state, final DataTreeCandidateNode modification) {
298         Preconditions.checkArgument(modification.getDataBefore().isPresent(), "Subtree change with before-data not present at path %s", state.getPath());
299         Preconditions.checkArgument(modification.getDataAfter().isPresent(), "Subtree change with after-data not present at path %s", state.getPath());
300
301         DataChangeScope scope = null;
302         for (DataTreeCandidateNode childMod : modification.getChildNodes()) {
303             final ResolveDataChangeState childState = state.child(childMod.getIdentifier());
304
305             switch (childMod.getModificationType()) {
306             case WRITE:
307             case MERGE:
308             case DELETE:
309                 if (resolveAnyChangeEvent(childState, childMod)) {
310                     scope = DataChangeScope.ONE;
311                 }
312                 break;
313             case SUBTREE_MODIFIED:
314                 if (resolveSubtreeChangeEvent(childState, childMod) && scope == null) {
315                     scope = DataChangeScope.SUBTREE;
316                 }
317                 break;
318             case UNMODIFIED:
319                 // no-op
320                 break;
321             }
322         }
323
324         final NormalizedNode<?, ?> before = modification.getDataBefore().get();
325         final NormalizedNode<?, ?> after = modification.getDataAfter().get();
326
327         if (scope != null) {
328             DOMImmutableDataChangeEvent one = DOMImmutableDataChangeEvent.builder(scope).addUpdated(state.getPath(), before, after).build();
329             state.addEvent(one);
330         }
331
332         state.collectEvents(before, after, collectedEvents);
333         return scope != null;
334     }
335
336     @SuppressWarnings("rawtypes")
337     public static ResolveDataChangeEventsTask create(final DataTreeCandidate candidate,
338             final ListenerTree listenerTree,
339             final NotificationManager<AsyncDataChangeListener,AsyncDataChangeEvent> notificationMgr) {
340         return new ResolveDataChangeEventsTask(candidate, listenerTree, notificationMgr);
341     }
342 }

©2013 OpenDaylight, A Linux Foundation Collaborative Project. All Rights Reserved.
OpenDaylight is a registered trademark of The OpenDaylight Project, Inc.
Linux Foundation and OpenDaylight are registered trademarks of the Linux Foundation.
Linux is a registered trademark of Linus Torvalds.