001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *     http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.configuration2.tree;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.HashMap;
023import java.util.Iterator;
024import java.util.LinkedList;
025import java.util.List;
026import java.util.Map;
027import java.util.concurrent.atomic.AtomicReference;
028
029import org.apache.commons.configuration2.ex.ConfigurationRuntimeException;
030import org.apache.commons.lang3.mutable.Mutable;
031import org.apache.commons.lang3.mutable.MutableObject;
032
033/**
034 * <p>
035 * A specialized node model implementation which operates on
036 * {@link ImmutableNode} structures.
037 * </p>
038 * <p>
039 * This {@code NodeModel} implementation keeps all its data as a tree of
040 * {@link ImmutableNode} objects in memory. The managed structure can be
041 * manipulated in a thread-safe, non-blocking way. This is achieved by using
042 * atomic variables: The root of the tree is stored in an atomic reference
043 * variable. Each update operation causes a new structure to be constructed
044 * (which reuses as much from the original structure as possible). The old root
045 * node is then replaced by the new one using an atomic compare-and-set
046 * operation. If this fails, the manipulation has to be done anew on the updated
047 * structure.
048 * </p>
049 *
050 * @since 2.0
051 */
052public class InMemoryNodeModel implements NodeModel<ImmutableNode>
053{
054    /**
055     * A dummy node handler instance used in operations which require only a
056     * limited functionality.
057     */
058    private static final NodeHandler<ImmutableNode> DUMMY_HANDLER =
059            new TreeData(null,
060                    Collections.<ImmutableNode, ImmutableNode> emptyMap(),
061                    Collections.<ImmutableNode, ImmutableNode> emptyMap(), null, new ReferenceTracker());
062
063    /** Stores information about the current nodes structure. */
064    private final AtomicReference<TreeData> structure;
065
066    /**
067     * Creates a new instance of {@code InMemoryNodeModel} which is initialized
068     * with an empty root node.
069     */
070    public InMemoryNodeModel()
071    {
072        this(null);
073    }
074
075    /**
076     * Creates a new instance of {@code InMemoryNodeModel} and initializes it
077     * from the given root node. If the passed in node is <b>null</b>, a new,
078     * empty root node is created.
079     *
080     * @param root the new root node for this model
081     */
082    public InMemoryNodeModel(final ImmutableNode root)
083    {
084        structure =
085                new AtomicReference<>(
086                        createTreeData(initialRootNode(root), null));
087    }
088
089    /**
090     * Returns the root node of this mode. Note: This method should be used with
091     * care. The model may be updated concurrently which causes the root node to
092     * be replaced. If the root node is to be processed further (e.g. by
093     * executing queries on it), the model should be asked for its
094     * {@code NodeHandler}, and the root node should be obtained from there. The
095     * connection between a node handler and its root node remain constant
096     * because an update of the model causes the whole node handler to be
097     * replaced.
098     *
099     * @return the current root node
100     */
101    public ImmutableNode getRootNode()
102    {
103        return getTreeData().getRootNode();
104    }
105
106    /**
107     * {@inheritDoc} {@code InMemoryNodeModel} implements the
108     * {@code NodeHandler} interface itself. So this implementation just returns
109     * the <strong>this</strong> reference.
110     */
111    @Override
112    public NodeHandler<ImmutableNode> getNodeHandler()
113    {
114        return getReferenceNodeHandler();
115    }
116
117    @Override
118    public void addProperty(final String key, final Iterable<?> values,
119            final NodeKeyResolver<ImmutableNode> resolver)
120    {
121        addProperty(key, null, values, resolver);
122    }
123
124    /**
125     * Adds new property values using a tracked node as root node. This method
126     * works like the normal {@code addProperty()} method, but the origin of the
127     * operation (also for the interpretation of the passed in key) is a tracked
128     * node identified by the passed in {@code NodeSelector}. The selector can
129     * be <b>null</b>, then the root node is assumed.
130     *
131     * @param key the key
132     * @param selector the {@code NodeSelector} defining the root node (or
133     *        <b>null</b>)
134     * @param values the values to be added
135     * @param resolver the {@code NodeKeyResolver}
136     * @throws ConfigurationRuntimeException if the selector cannot be resolved
137     */
138    public void addProperty(final String key, final NodeSelector selector,
139            final Iterable<?> values,
140            final NodeKeyResolver<ImmutableNode> resolver)
141    {
142        if (valuesNotEmpty(values))
143        {
144            updateModel(tx -> {
145                initializeAddTransaction(tx, key, values, resolver);
146                return true;
147            }, selector, resolver);
148        }
149    }
150
151    @Override
152    public void addNodes(final String key, final Collection<? extends ImmutableNode> nodes,
153            final NodeKeyResolver<ImmutableNode> resolver)
154    {
155        addNodes(key, null, nodes, resolver);
156    }
157
158    /**
159     * Adds new nodes using a tracked node as root node. This method works like
160     * the normal {@code addNodes()} method, but the origin of the operation
161     * (also for the interpretation of the passed in key) is a tracked node
162     * identified by the passed in {@code NodeSelector}. The selector can be
163     * <b>null</b>, then the root node is assumed.
164     *
165     * @param key the key
166     * @param selector the {@code NodeSelector} defining the root node (or
167     *        <b>null</b>)
168     * @param nodes the collection of new nodes to be added
169     * @param resolver the {@code NodeKeyResolver}
170     * @throws ConfigurationRuntimeException if the selector cannot be resolved
171     */
172    public void addNodes(final String key, final NodeSelector selector,
173            final Collection<? extends ImmutableNode> nodes,
174            final NodeKeyResolver<ImmutableNode> resolver)
175    {
176        if (nodes != null && !nodes.isEmpty())
177        {
178            updateModel(tx -> {
179                final List<QueryResult<ImmutableNode>> results =
180                        resolver.resolveKey(tx.getQueryRoot(), key,
181                                tx.getCurrentData());
182                if (results.size() == 1)
183                {
184                    if (results.get(0).isAttributeResult())
185                    {
186                        throw attributeKeyException(key);
187                    }
188                    tx.addAddNodesOperation(results.get(0).getNode(), nodes);
189                }
190                else
191                {
192                    final NodeAddData<ImmutableNode> addData =
193                            resolver.resolveAddKey(tx.getQueryRoot(), key,
194                                    tx.getCurrentData());
195                    if (addData.isAttribute())
196                    {
197                        throw attributeKeyException(key);
198                    }
199                    final ImmutableNode newNode =
200                            new ImmutableNode.Builder(nodes.size())
201                                    .name(addData.getNewNodeName())
202                                    .addChildren(nodes).create();
203                    addNodesByAddData(tx, addData,
204                            Collections.singleton(newNode));
205                }
206                return true;
207            }, selector, resolver);
208        }
209    }
210
211    @Override
212    public void setProperty(final String key, final Object value,
213            final NodeKeyResolver<ImmutableNode> resolver)
214    {
215        setProperty(key, null, value, resolver);
216    }
217
218    /**
219     * Sets the value of a property using a tracked node as root node. This
220     * method works like the normal {@code setProperty()} method, but the origin
221     * of the operation (also for the interpretation of the passed in key) is a
222     * tracked node identified by the passed in {@code NodeSelector}. The
223     * selector can be <b>null</b>, then the root node is assumed.
224     *
225     * @param key the key
226     * @param selector the {@code NodeSelector} defining the root node (or
227     *        <b>null</b>)
228     * @param value the new value for this property
229     * @param resolver the {@code NodeKeyResolver}
230     * @throws ConfigurationRuntimeException if the selector cannot be resolved
231     */
232    public void setProperty(final String key, final NodeSelector selector,
233            final Object value, final NodeKeyResolver<ImmutableNode> resolver)
234    {
235        updateModel(tx -> {
236            boolean added = false;
237            final NodeUpdateData<ImmutableNode> updateData =
238                    resolver.resolveUpdateKey(tx.getQueryRoot(), key,
239                            value, tx.getCurrentData());
240            if (!updateData.getNewValues().isEmpty())
241            {
242                initializeAddTransaction(tx, key,
243                        updateData.getNewValues(), resolver);
244                added = true;
245            }
246            final boolean cleared =
247                    initializeClearTransaction(tx,
248                            updateData.getRemovedNodes());
249            final boolean updated =
250                    initializeUpdateTransaction(tx,
251                            updateData.getChangedValues());
252            return added || cleared || updated;
253        }, selector, resolver);
254    }
255
256    /**
257     * {@inheritDoc} This implementation checks whether nodes become undefined
258     * after subtrees have been removed. If this is the case, such nodes are
259     * removed, too. Return value is a collection with {@code QueryResult}
260     * objects for the elements to be removed from the model.
261     */
262    @Override
263    public List<QueryResult<ImmutableNode>> clearTree(final String key,
264            final NodeKeyResolver<ImmutableNode> resolver)
265    {
266        return clearTree(key, null, resolver);
267    }
268
269    /**
270     * Clears a whole sub tree using a tracked node as root node. This method
271     * works like the normal {@code clearTree()} method, but the origin of the
272     * operation (also for the interpretation of the passed in key) is a tracked
273     * node identified by the passed in {@code NodeSelector}. The selector can
274     * be <b>null</b>, then the root node is assumed.
275     *
276     * @param key the key
277     * @param selector the {@code NodeSelector} defining the root node (or
278     *        <b>null</b>)
279     * @param resolver the {@code NodeKeyResolver}
280     * @return a list with the results to be removed
281     * @throws ConfigurationRuntimeException if the selector cannot be resolved
282     */
283    public List<QueryResult<ImmutableNode>> clearTree(final String key,
284            final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver)
285    {
286        final List<QueryResult<ImmutableNode>> removedElements =
287                new LinkedList<>();
288        updateModel(tx -> {
289            boolean changes = false;
290            final TreeData currentStructure = tx.getCurrentData();
291            final List<QueryResult<ImmutableNode>> results = resolver.resolveKey(
292                    tx.getQueryRoot(), key, currentStructure);
293            removedElements.clear();
294            removedElements.addAll(results);
295            for (final QueryResult<ImmutableNode> result : results)
296            {
297                if (result.isAttributeResult())
298                {
299                    tx.addRemoveAttributeOperation(result.getNode(),
300                            result.getAttributeName());
301                }
302                else
303                {
304                    if (result.getNode() == currentStructure.getRootNode())
305                    {
306                        // the whole model is to be cleared
307                        clear(resolver);
308                        return false;
309                    }
310                    tx.addRemoveNodeOperation(
311                            currentStructure.getParent(result.getNode()),
312                            result.getNode());
313                }
314                changes = true;
315            }
316            return changes;
317        }, selector, resolver);
318
319        return removedElements;
320    }
321
322    /**
323     * {@inheritDoc} If this operation leaves an affected node in an undefined
324     * state, it is removed from the model.
325     */
326    @Override
327    public void clearProperty(final String key,
328            final NodeKeyResolver<ImmutableNode> resolver)
329    {
330        clearProperty(key, null, resolver);
331    }
332
333    /**
334     * Clears a property using a tracked node as root node. This method works
335     * like the normal {@code clearProperty()} method, but the origin of the
336     * operation (also for the interpretation of the passed in key) is a tracked
337     * node identified by the passed in {@code NodeSelector}. The selector can
338     * be <b>null</b>, then the root node is assumed.
339     *
340     * @param key the key
341     * @param selector the {@code NodeSelector} defining the root node (or
342     *        <b>null</b>)
343     * @param resolver the {@code NodeKeyResolver}
344     * @throws ConfigurationRuntimeException if the selector cannot be resolved
345     */
346    public void clearProperty(final String key, final NodeSelector selector,
347            final NodeKeyResolver<ImmutableNode> resolver)
348    {
349        updateModel(tx -> {
350            final List<QueryResult<ImmutableNode>> results =
351                    resolver.resolveKey(tx.getQueryRoot(), key,
352                            tx.getCurrentData());
353            return initializeClearTransaction(tx, results);
354        }, selector, resolver);
355    }
356
357    /**
358     * {@inheritDoc} A new empty root node is created with the same name as the
359     * current root node. Implementation note: Because this is a hard reset the
360     * usual dance for dealing with concurrent updates is not required here.
361     *
362     * @param resolver the {@code NodeKeyResolver}
363     */
364    @Override
365    public void clear(final NodeKeyResolver<ImmutableNode> resolver)
366    {
367        final ImmutableNode newRoot =
368                new ImmutableNode.Builder().name(getRootNode().getNodeName())
369                        .create();
370        setRootNode(newRoot);
371    }
372
373    /**
374     * {@inheritDoc} This implementation simply returns the current root node of this
375     * model.
376     */
377    @Override
378    public ImmutableNode getInMemoryRepresentation()
379    {
380        return getTreeData().getRootNode();
381    }
382
383    /**
384     * {@inheritDoc} All tracked nodes and reference objects managed by this
385     * model are cleared.Care has to be taken when this method is used and the
386     * model is accessed by multiple threads. It is not deterministic which
387     * concurrent operations see the old root and which see the new root node.
388     *
389     * @param newRoot the new root node to be set (can be <b>null</b>, then an
390     *        empty root node is set)
391     */
392    @Override
393    public void setRootNode(final ImmutableNode newRoot)
394    {
395        structure.set(createTreeData(initialRootNode(newRoot), structure.get()));
396    }
397
398    /**
399     * Replaces the root node of this model. This method is similar to
400     * {@link #setRootNode(ImmutableNode)}; however, tracked nodes will not get
401     * lost. The model applies the selectors of all tracked nodes on the new
402     * nodes hierarchy, so that corresponding nodes are selected (this may cause
403     * nodes to become detached if a select operation fails). This operation is
404     * useful if the new nodes hierarchy to be set is known to be similar to the
405     * old one. Note that reference objects are lost; there is no way to
406     * automatically match nodes between the old and the new nodes hierarchy.
407     *
408     * @param newRoot the new root node to be set (must not be <b>null</b>)
409     * @param resolver the {@code NodeKeyResolver}
410     * @throws IllegalArgumentException if the new root node is <b>null</b>
411     */
412    public void replaceRoot(final ImmutableNode newRoot,
413            final NodeKeyResolver<ImmutableNode> resolver)
414    {
415        if (newRoot == null)
416        {
417            throw new IllegalArgumentException(
418                    "Replaced root node must not be null!");
419        }
420
421        final TreeData current = structure.get();
422        // this step is needed to get a valid NodeHandler
423        final TreeData temp =
424                createTreeDataForRootAndTracker(newRoot,
425                        current.getNodeTracker());
426        structure.set(temp.updateNodeTracker(temp.getNodeTracker().update(
427                newRoot, null, resolver, temp)));
428    }
429
430    /**
431     * Merges the root node of this model with the specified node. This method
432     * is typically caused by configuration implementations when a configuration
433     * source is loaded, and its data has to be added to the model. It is
434     * possible to define the new name of the root node and to pass in a map
435     * with reference objects.
436     *
437     * @param node the node to be merged with the root node
438     * @param rootName the new name of the root node; can be <b>null</b>, then
439     *        the name of the root node is not changed unless it is <b>null</b>
440     * @param references an optional map with reference objects
441     * @param rootRef an optional reference object for the new root node
442     * @param resolver the {@code NodeKeyResolver}
443     */
444    public void mergeRoot(final ImmutableNode node, final String rootName,
445            final Map<ImmutableNode, ?> references, final Object rootRef,
446            final NodeKeyResolver<ImmutableNode> resolver)
447    {
448        updateModel(tx -> {
449            final TreeData current = tx.getCurrentData();
450            final String newRootName =
451                    determineRootName(current.getRootNode(), node, rootName);
452            if (newRootName != null)
453            {
454                tx.addChangeNodeNameOperation(current.getRootNode(),
455                        newRootName);
456            }
457            tx.addAddNodesOperation(current.getRootNode(),
458                    node.getChildren());
459            tx.addAttributesOperation(current.getRootNode(),
460                    node.getAttributes());
461            if (node.getValue() != null)
462            {
463                tx.addChangeNodeValueOperation(current.getRootNode(),
464                        node.getValue());
465            }
466            if (references != null)
467            {
468                tx.addNewReferences(references);
469            }
470            if (rootRef != null)
471            {
472                tx.addNewReference(current.getRootNode(), rootRef);
473            }
474            return true;
475        }, null, resolver);
476    }
477
478    /**
479     * Adds a node to be tracked. After this method has been called with a
480     * specific {@code NodeSelector}, the node associated with this key can be
481     * always obtained using {@link #getTrackedNode(NodeSelector)} with the same
482     * selector. This is useful because during updates of a model parts of the
483     * structure are replaced. Therefore, it is not a good idea to simply hold a
484     * reference to a node; this might become outdated soon. Rather, the node
485     * should be tracked. This mechanism ensures that always the correct node
486     * reference can be obtained.
487     *
488     * @param selector the {@code NodeSelector} defining the desired node
489     * @param resolver the {@code NodeKeyResolver}
490     * @throws ConfigurationRuntimeException if the selector does not select a
491     *         single node
492     */
493    public void trackNode(final NodeSelector selector,
494            final NodeKeyResolver<ImmutableNode> resolver)
495    {
496        boolean done;
497        do
498        {
499            final TreeData current = structure.get();
500            final NodeTracker newTracker =
501                    current.getNodeTracker().trackNode(current.getRootNode(),
502                            selector, resolver, current);
503            done =
504                    structure.compareAndSet(current,
505                            current.updateNodeTracker(newTracker));
506        } while (!done);
507    }
508
509    /**
510     * Allows tracking all nodes selected by a key. This method evaluates the
511     * specified key on the current nodes structure. For all selected nodes
512     * corresponding {@code NodeSelector} objects are created, and they are
513     * tracked. The returned collection of {@code NodeSelector} objects can be
514     * used for interacting with the selected nodes.
515     *
516     * @param key the key for selecting the nodes to track
517     * @param resolver the {@code NodeKeyResolver}
518     * @return a collection with the {@code NodeSelector} objects for the new
519     *         tracked nodes
520     */
521    public Collection<NodeSelector> selectAndTrackNodes(final String key,
522            final NodeKeyResolver<ImmutableNode> resolver)
523    {
524        final Mutable<Collection<NodeSelector>> refSelectors =
525                new MutableObject<>();
526        boolean done;
527        do
528        {
529            final TreeData current = structure.get();
530            final List<ImmutableNode> nodes =
531                    resolver.resolveNodeKey(current.getRootNode(), key, current);
532            if (nodes.isEmpty())
533            {
534                return Collections.emptyList();
535            }
536            done =
537                    structure.compareAndSet(
538                            current,
539                            createSelectorsForTrackedNodes(refSelectors, nodes,
540                                    current, resolver));
541        } while (!done);
542        return refSelectors.getValue();
543    }
544
545    /**
546     * Tracks all nodes which are children of the node selected by the passed in
547     * key. If the key selects exactly one node, for all children of this node
548     * {@code NodeSelector} objects are created, and they become tracked nodes.
549     * The returned collection of {@code NodeSelector} objects can be used for
550     * interacting with the selected nodes.
551     *
552     * @param key the key for selecting the parent node whose children are to be
553     *        tracked
554     * @param resolver the {@code NodeKeyResolver}
555     * @return a collection with the {@code NodeSelector} objects for the new
556     *         tracked nodes
557     */
558    public Collection<NodeSelector> trackChildNodes(final String key,
559            final NodeKeyResolver<ImmutableNode> resolver)
560    {
561        final Mutable<Collection<NodeSelector>> refSelectors =
562                new MutableObject<>();
563        boolean done;
564        do
565        {
566            refSelectors.setValue(Collections.<NodeSelector> emptyList());
567            final TreeData current = structure.get();
568            final List<ImmutableNode> nodes =
569                    resolver.resolveNodeKey(current.getRootNode(), key, current);
570            if (nodes.size() == 1)
571            {
572                final ImmutableNode node = nodes.get(0);
573                done =
574                        node.getChildren().isEmpty()
575                                || structure.compareAndSet(
576                                        current,
577                                        createSelectorsForTrackedNodes(
578                                                refSelectors,
579                                                node.getChildren(), current,
580                                                resolver));
581            }
582            else
583            {
584                done = true;
585            }
586        } while (!done);
587        return refSelectors.getValue();
588    }
589
590    /**
591     * Tracks a node which is a child of another node selected by the passed in
592     * key. If the selected node has a child node with this name, it is tracked
593     * and its selector is returned. Otherwise, a new child node with this name
594     * is created first.
595     *
596     * @param key the key for selecting the parent node
597     * @param childName the name of the child node
598     * @param resolver the {@code NodeKeyResolver}
599     * @return the {@code NodeSelector} for the tracked child node
600     * @throws ConfigurationRuntimeException if the passed in key does not
601     *         select a single node
602     */
603    public NodeSelector trackChildNodeWithCreation(final String key,
604            final String childName, final NodeKeyResolver<ImmutableNode> resolver)
605    {
606        final MutableObject<NodeSelector> refSelector =
607                new MutableObject<>();
608        boolean done;
609
610        do
611        {
612            final TreeData current = structure.get();
613            final List<ImmutableNode> nodes =
614                    resolver.resolveNodeKey(current.getRootNode(), key, current);
615            if (nodes.size() != 1)
616            {
617                throw new ConfigurationRuntimeException(
618                        "Key does not select a single node: " + key);
619            }
620
621            final ImmutableNode parent = nodes.get(0);
622            final TreeData newData =
623                    createDataWithTrackedChildNode(current, parent, childName,
624                            resolver, refSelector);
625
626            done = structure.compareAndSet(current, newData);
627        } while (!done);
628
629        return refSelector.getValue();
630    }
631
632    /**
633     * Returns the current {@code ImmutableNode} instance associated with the
634     * given {@code NodeSelector}. The node must be a tracked node, i.e.
635     * {@link #trackNode(NodeSelector, NodeKeyResolver)} must have been called
636     * before with the given selector.
637     *
638     * @param selector the {@code NodeSelector} defining the desired node
639     * @return the current {@code ImmutableNode} associated with this selector
640     * @throws ConfigurationRuntimeException if the selector is unknown
641     */
642    public ImmutableNode getTrackedNode(final NodeSelector selector)
643    {
644        return structure.get().getNodeTracker().getTrackedNode(selector);
645    }
646
647    /**
648     * Replaces a tracked node by another node. If the tracked node is not yet
649     * detached, it becomes now detached. The passed in node (which must not be
650     * <b>null</b>) becomes the new root node of an independent model for this
651     * tracked node. Further updates of this model do not affect the tracked
652     * node's model and vice versa.
653     *
654     * @param selector the {@code NodeSelector} defining the tracked node
655     * @param newNode the node replacing the tracked node (must not be
656     *        <b>null</b>)
657     * @throws ConfigurationRuntimeException if the selector cannot be resolved
658     * @throws IllegalArgumentException if the replacement node is <b>null</b>
659     */
660    public void replaceTrackedNode(final NodeSelector selector, final ImmutableNode newNode)
661    {
662        if (newNode == null)
663        {
664            throw new IllegalArgumentException(
665                    "Replacement node must not be null!");
666        }
667
668        boolean done;
669        do
670        {
671            final TreeData currentData = structure.get();
672            done =
673                    replaceDetachedTrackedNode(currentData, selector, newNode)
674                            || replaceActiveTrackedNode(currentData, selector,
675                                    newNode);
676        } while (!done);
677    }
678
679    /**
680     * Returns a {@code NodeHandler} for a tracked node. Such a handler may be
681     * required for operations on a sub tree of the model. The handler to be
682     * returned depends on the current state of the tracked node. If it is still
683     * active, a handler is used which shares some data (especially the parent
684     * mapping) with this model. Detached track nodes in contrast have their own
685     * separate model; in this case a handler associated with this model is
686     * returned.
687     *
688     * @param selector the {@code NodeSelector} defining the tracked node
689     * @return a {@code NodeHandler} for this tracked node
690     * @throws ConfigurationRuntimeException if the selector is unknown
691     */
692    public NodeHandler<ImmutableNode> getTrackedNodeHandler(
693            final NodeSelector selector)
694    {
695        final TreeData currentData = structure.get();
696        final InMemoryNodeModel detachedNodeModel =
697                currentData.getNodeTracker().getDetachedNodeModel(selector);
698        return detachedNodeModel != null ? detachedNodeModel.getNodeHandler()
699                : new TrackedNodeHandler(currentData.getNodeTracker()
700                        .getTrackedNode(selector), currentData);
701    }
702
703    /**
704     * Returns a flag whether the specified tracked node is detached. As long as
705     * the {@code NodeSelector} associated with that node returns a single
706     * instance, the tracked node is said to be <em>life</em>. If now an update
707     * of the model happens which invalidates the selector (maybe the target
708     * node was removed), the tracked node becomes detached. It is still
709     * possible to query the node; here the latest valid instance is returned.
710     * But further changes on the node model are no longer tracked for this
711     * node. So even if there are further changes which would make the
712     * {@code NodeSelector} valid again, the tracked node stays in detached
713     * state.
714     *
715     * @param selector the {@code NodeSelector} defining the desired node
716     * @return a flag whether this tracked node is in detached state
717     * @throws ConfigurationRuntimeException if the selector is unknown
718     */
719    public boolean isTrackedNodeDetached(final NodeSelector selector)
720    {
721        return structure.get().getNodeTracker().isTrackedNodeDetached(selector);
722    }
723
724    /**
725     * Removes a tracked node. This method is the opposite of
726     * {@code trackNode()}. It has to be called if there is no longer the need
727     * to track a specific node. Note that for each call of {@code trackNode()}
728     * there has to be a corresponding {@code untrackNode()} call. This ensures
729     * that multiple observers can track the same node.
730     *
731     * @param selector the {@code NodeSelector} defining the desired node
732     * @throws ConfigurationRuntimeException if the specified node is not
733     *         tracked
734     */
735    public void untrackNode(final NodeSelector selector)
736    {
737        boolean done;
738        do
739        {
740            final TreeData current = structure.get();
741            final NodeTracker newTracker =
742                    current.getNodeTracker().untrackNode(selector);
743            done =
744                    structure.compareAndSet(current,
745                            current.updateNodeTracker(newTracker));
746        } while (!done);
747    }
748
749    /**
750     * Returns a {@code ReferenceNodeHandler} object for this model. This
751     * extended node handler can be used to query references objects stored for
752     * this model.
753     *
754     * @return the {@code ReferenceNodeHandler}
755     */
756    public ReferenceNodeHandler getReferenceNodeHandler()
757    {
758        return getTreeData();
759    }
760
761    /**
762     * Returns the current {@code TreeData} object. This object contains all
763     * information about the current node structure.
764     *
765     * @return the current {@code TreeData} object
766     */
767    TreeData getTreeData()
768    {
769        return structure.get();
770    }
771
772    /**
773     * Updates the mapping from nodes to their parents for the passed in
774     * hierarchy of nodes. This method traverses all children and grand-children
775     * of the passed in root node. For each node in the subtree the parent
776     * relation is added to the map.
777     *
778     * @param parents the map with parent nodes
779     * @param root the root node of the current tree
780     */
781    static void updateParentMapping(final Map<ImmutableNode, ImmutableNode> parents,
782            final ImmutableNode root)
783    {
784        NodeTreeWalker.INSTANCE.walkBFS(root,
785                new ConfigurationNodeVisitorAdapter<ImmutableNode>()
786                {
787                    @Override
788                    public void visitBeforeChildren(final ImmutableNode node,
789                            final NodeHandler<ImmutableNode> handler)
790                    {
791                        for (final ImmutableNode c : node.getChildren())
792                        {
793                            parents.put(c, node);
794                        }
795                    }
796                }, DUMMY_HANDLER);
797    }
798
799    /**
800     * Checks if the passed in node is defined. Result is <b>true</b> if the
801     * node contains any data.
802     *
803     * @param node the node in question
804     * @return <b>true</b> if the node is defined, <b>false</b> otherwise
805     */
806    static boolean checkIfNodeDefined(final ImmutableNode node)
807    {
808        return node.getValue() != null || !node.getChildren().isEmpty()
809                || !node.getAttributes().isEmpty();
810    }
811
812    /**
813     * Initializes a transaction for an add operation.
814     *
815     * @param tx the transaction to be initialized
816     * @param key the key
817     * @param values the collection with node values
818     * @param resolver the {@code NodeKeyResolver}
819     */
820    private void initializeAddTransaction(final ModelTransaction tx, final String key,
821            final Iterable<?> values, final NodeKeyResolver<ImmutableNode> resolver)
822    {
823        final NodeAddData<ImmutableNode> addData =
824                resolver.resolveAddKey(tx.getQueryRoot(), key,
825                        tx.getCurrentData());
826        if (addData.isAttribute())
827        {
828            addAttributeProperty(tx, addData, values);
829        }
830        else
831        {
832            addNodeProperty(tx, addData, values);
833        }
834    }
835
836    /**
837     * Creates a {@code TreeData} object for the specified root node.
838     *
839     * @param root the root node of the current tree
840     * @param current the current {@code TreeData} object (may be <b>null</b>)
841     * @return the {@code TreeData} describing the current tree
842     */
843    private TreeData createTreeData(final ImmutableNode root, final TreeData current)
844    {
845        final NodeTracker newTracker =
846                current != null ? current.getNodeTracker()
847                        .detachAllTrackedNodes() : new NodeTracker();
848        return createTreeDataForRootAndTracker(root, newTracker);
849    }
850
851    /**
852     * Creates a {@code TreeData} object for the specified root node and
853     * {@code NodeTracker}. Other parameters are set to default values.
854     *
855     * @param root the new root node for this model
856     * @param newTracker the new {@code NodeTracker}
857     * @return the new {@code TreeData} object
858     */
859    private TreeData createTreeDataForRootAndTracker(final ImmutableNode root,
860            final NodeTracker newTracker)
861    {
862        return new TreeData(root, createParentMapping(root),
863                Collections.<ImmutableNode, ImmutableNode> emptyMap(),
864                newTracker, new ReferenceTracker());
865    }
866
867    /**
868     * Handles an add property operation if the property to be added is a node.
869     *
870     * @param tx the transaction
871     * @param addData the {@code NodeAddData}
872     * @param values the collection with node values
873     */
874    private static void addNodeProperty(final ModelTransaction tx,
875            final NodeAddData<ImmutableNode> addData, final Iterable<?> values)
876    {
877        final Collection<ImmutableNode> newNodes =
878                createNodesToAdd(addData.getNewNodeName(), values);
879        addNodesByAddData(tx, addData, newNodes);
880    }
881
882    /**
883     * Initializes a transaction to add a collection of nodes as described by a
884     * {@code NodeAddData} object. If necessary, new path nodes are created.
885     * Eventually, the new nodes are added as children to the specified target
886     * node.
887     *
888     * @param tx the transaction
889     * @param addData the {@code NodeAddData}
890     * @param newNodes the collection of new child nodes
891     */
892    private static void addNodesByAddData(final ModelTransaction tx,
893            final NodeAddData<ImmutableNode> addData,
894            final Collection<ImmutableNode> newNodes)
895    {
896        if (addData.getPathNodes().isEmpty())
897        {
898            tx.addAddNodesOperation(addData.getParent(), newNodes);
899        }
900        else
901        {
902            final ImmutableNode newChild = createNodeToAddWithPath(addData, newNodes);
903            tx.addAddNodeOperation(addData.getParent(), newChild);
904        }
905    }
906
907    /**
908     * Handles an add property operation if the property to be added is an
909     * attribute.
910     *
911     * @param tx the transaction
912     * @param addData the {@code NodeAddData}
913     * @param values the collection with node values
914     */
915    private static void addAttributeProperty(final ModelTransaction tx,
916            final NodeAddData<ImmutableNode> addData, final Iterable<?> values)
917    {
918        if (addData.getPathNodes().isEmpty())
919        {
920            tx.addAttributeOperation(addData.getParent(),
921                    addData.getNewNodeName(), values.iterator().next());
922        }
923        else
924        {
925            final int pathNodeCount = addData.getPathNodes().size();
926            final ImmutableNode childWithAttribute =
927                    new ImmutableNode.Builder()
928                            .name(addData.getPathNodes().get(pathNodeCount - 1))
929                            .addAttribute(addData.getNewNodeName(),
930                                    values.iterator().next()).create();
931            final ImmutableNode newChild =
932                    pathNodeCount > 1 ? createNodeOnPath(addData
933                            .getPathNodes().subList(0, pathNodeCount - 1)
934                            .iterator(),
935                            Collections.singleton(childWithAttribute))
936                            : childWithAttribute;
937            tx.addAddNodeOperation(addData.getParent(), newChild);
938        }
939    }
940
941    /**
942     * Creates a collection with new nodes with a given name and a value from a
943     * given collection.
944     *
945     * @param newNodeName the name of the new nodes
946     * @param values the collection with node values
947     * @return the newly created collection
948     */
949    private static Collection<ImmutableNode> createNodesToAdd(
950            final String newNodeName, final Iterable<?> values)
951    {
952        final Collection<ImmutableNode> nodes = new LinkedList<>();
953        for (final Object value : values)
954        {
955            nodes.add(new ImmutableNode.Builder().name(newNodeName)
956                    .value(value).create());
957        }
958        return nodes;
959    }
960
961    /**
962     * Creates a node structure consisting of the path nodes defined by the
963     * passed in {@code NodeAddData} instance and all new child nodes.
964     *
965     * @param addData the {@code NodeAddData}
966     * @param newNodes the collection of new child nodes
967     * @return the parent node of the newly created hierarchy
968     */
969    private static ImmutableNode createNodeToAddWithPath(
970            final NodeAddData<ImmutableNode> addData,
971            final Collection<ImmutableNode> newNodes)
972    {
973        return createNodeOnPath(addData.getPathNodes().iterator(), newNodes);
974    }
975
976    /**
977     * Recursive helper method for creating a path node for an add operation.
978     * All path nodes except for the last have a single child. The last path
979     * node has the new nodes as children.
980     *
981     * @param it the iterator over the names of the path nodes
982     * @param newNodes the collection of new child nodes
983     * @return the newly created path node
984     */
985    private static ImmutableNode createNodeOnPath(final Iterator<String> it,
986            final Collection<ImmutableNode> newNodes)
987    {
988        final String nodeName = it.next();
989        ImmutableNode.Builder builder;
990        if (it.hasNext())
991        {
992            builder = new ImmutableNode.Builder(1);
993            builder.addChild(createNodeOnPath(it, newNodes));
994        }
995        else
996        {
997            builder = new ImmutableNode.Builder(newNodes.size());
998            builder.addChildren(newNodes);
999        }
1000        return builder.name(nodeName).create();
1001    }
1002
1003    /**
1004     * Initializes a transaction to clear the values of a property based on the
1005     * passed in collection of affected results.
1006     *
1007     * @param tx the transaction to be initialized
1008     * @param results a collection with results pointing to the nodes to be
1009     *        cleared
1010     * @return a flag whether there are elements to be cleared
1011     */
1012    private static boolean initializeClearTransaction(final ModelTransaction tx,
1013            final Collection<QueryResult<ImmutableNode>> results)
1014    {
1015        for (final QueryResult<ImmutableNode> result : results)
1016        {
1017            if (result.isAttributeResult())
1018            {
1019                tx.addRemoveAttributeOperation(result.getNode(),
1020                        result.getAttributeName());
1021            }
1022            else
1023            {
1024                tx.addClearNodeValueOperation(result.getNode());
1025            }
1026        }
1027
1028        return !results.isEmpty();
1029    }
1030
1031    /**
1032     * Initializes a transaction to change the values of some query results
1033     * based on the passed in map.
1034     *
1035     * @param tx the transaction to be initialized
1036     * @param changedValues the map defining the elements to be changed
1037     * @return a flag whether there are elements to be updated
1038     */
1039    private static boolean initializeUpdateTransaction(final ModelTransaction tx,
1040            final Map<QueryResult<ImmutableNode>, Object> changedValues)
1041    {
1042        for (final Map.Entry<QueryResult<ImmutableNode>, Object> e : changedValues
1043                .entrySet())
1044        {
1045            if (e.getKey().isAttributeResult())
1046            {
1047                tx.addAttributeOperation(e.getKey().getNode(), e.getKey()
1048                        .getAttributeName(), e.getValue());
1049            }
1050            else
1051            {
1052                tx.addChangeNodeValueOperation(e.getKey().getNode(),
1053                        e.getValue());
1054            }
1055        }
1056
1057        return !changedValues.isEmpty();
1058    }
1059
1060    /**
1061     * Determines the initial root node of this model. If a root node has been
1062     * provided, it is used. Otherwise, an empty dummy root node is created.
1063     *
1064     * @param providedRoot the passed in root node
1065     * @return the root node to be used
1066     */
1067    private static ImmutableNode initialRootNode(final ImmutableNode providedRoot)
1068    {
1069        return providedRoot != null ? providedRoot
1070                : new ImmutableNode.Builder().create();
1071    }
1072
1073    /**
1074     * Determines the name of the root node for a merge operation. If a root
1075     * name is provided, it is used. Otherwise, if the current root node has no
1076     * name, the name of the node to be merged is used. A result of <b>null</b>
1077     * means that no node name has to be set.
1078     *
1079     * @param rootNode the current root node
1080     * @param node the node to be merged with the root node
1081     * @param rootName the name of the resulting node
1082     * @return the new name of the root node
1083     */
1084    private static String determineRootName(final ImmutableNode rootNode,
1085            final ImmutableNode node, final String rootName)
1086    {
1087        if (rootName != null)
1088        {
1089            return rootName;
1090        }
1091        if (rootNode.getNodeName() == null)
1092        {
1093            return node.getNodeName();
1094        }
1095        return null;
1096    }
1097
1098    /**
1099     * Creates the mapping to parent nodes for the nodes structured represented
1100     * by the passed in root node. Each node is assigned its parent node. Here
1101     * an iterative algorithm is used rather than a recursive one to avoid stack
1102     * overflow for huge structures.
1103     *
1104     * @param root the root node of the structure
1105     * @return the parent node mapping
1106     */
1107    private Map<ImmutableNode, ImmutableNode> createParentMapping(
1108            final ImmutableNode root)
1109    {
1110        final Map<ImmutableNode, ImmutableNode> parents =
1111                new HashMap<>();
1112        updateParentMapping(parents, root);
1113        return parents;
1114    }
1115
1116    /**
1117     * Performs a non-blocking, thread-safe update of this model based on a
1118     * transaction initialized by the passed in initializer. This method uses
1119     * the atomic reference for the model's current data to ensure that an
1120     * update was successful even if the model is concurrently accessed.
1121     *
1122     * @param txInit the {@code TransactionInitializer}
1123     * @param selector an optional {@code NodeSelector} defining the target node
1124     *        of the transaction
1125     * @param resolver the {@code NodeKeyResolver}
1126     */
1127    private void updateModel(final TransactionInitializer txInit,
1128            final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver)
1129    {
1130        boolean done;
1131
1132        do
1133        {
1134            final TreeData currentData = getTreeData();
1135            done =
1136                    executeTransactionOnDetachedTrackedNode(txInit, selector,
1137                            currentData, resolver)
1138                            || executeTransactionOnCurrentStructure(txInit,
1139                                    selector, currentData, resolver);
1140        } while (!done);
1141    }
1142
1143    /**
1144     * Executes a transaction on the current data of this model. This method is
1145     * called if an operation is to be executed on the model's root node or a
1146     * tracked node which is not yet detached.
1147     *
1148     * @param txInit the {@code TransactionInitializer}
1149     * @param selector an optional {@code NodeSelector} defining the target node
1150     * @param currentData the current data of the model
1151     * @param resolver the {@code NodeKeyResolver}
1152     * @return a flag whether the operation has been completed successfully
1153     */
1154    private boolean executeTransactionOnCurrentStructure(
1155            final TransactionInitializer txInit, final NodeSelector selector,
1156            final TreeData currentData, final NodeKeyResolver<ImmutableNode> resolver)
1157    {
1158        boolean done;
1159        final ModelTransaction tx =
1160                new ModelTransaction(currentData, selector, resolver);
1161        if (!txInit.initTransaction(tx))
1162        {
1163            done = true;
1164        }
1165        else
1166        {
1167            final TreeData newData = tx.execute();
1168            done = structure.compareAndSet(tx.getCurrentData(), newData);
1169        }
1170        return done;
1171    }
1172
1173    /**
1174     * Tries to execute a transaction on the model of a detached tracked node.
1175     * This method checks whether the target node of the transaction is a
1176     * tracked node and if this node is already detached. If this is the case,
1177     * the update operation is independent on this model and has to be executed
1178     * on the specific model for the detached node.
1179     *
1180     * @param txInit the {@code TransactionInitializer}
1181     * @param selector an optional {@code NodeSelector} defining the target node
1182     * @param currentData the current data of the model
1183     * @param resolver the {@code NodeKeyResolver} @return a flag whether the
1184     *        transaction could be executed
1185     * @throws ConfigurationRuntimeException if the selector cannot be resolved
1186     */
1187    private boolean executeTransactionOnDetachedTrackedNode(
1188            final TransactionInitializer txInit, final NodeSelector selector,
1189            final TreeData currentData, final NodeKeyResolver<ImmutableNode> resolver)
1190    {
1191        if (selector != null)
1192        {
1193            final InMemoryNodeModel detachedNodeModel =
1194                    currentData.getNodeTracker().getDetachedNodeModel(selector);
1195            if (detachedNodeModel != null)
1196            {
1197                detachedNodeModel.updateModel(txInit, null, resolver);
1198                return true;
1199            }
1200        }
1201
1202        return false;
1203    }
1204
1205    /**
1206     * Replaces a tracked node if it is already detached.
1207     *
1208     * @param currentData the current data of the model
1209     * @param selector the {@code NodeSelector} defining the tracked node
1210     * @param newNode the node replacing the tracked node
1211     * @return a flag whether the operation was successful
1212     */
1213    private boolean replaceDetachedTrackedNode(final TreeData currentData,
1214            final NodeSelector selector, final ImmutableNode newNode)
1215    {
1216        final InMemoryNodeModel detachedNodeModel =
1217                currentData.getNodeTracker().getDetachedNodeModel(selector);
1218        if (detachedNodeModel != null)
1219        {
1220            detachedNodeModel.setRootNode(newNode);
1221            return true;
1222        }
1223
1224        return false;
1225    }
1226
1227    /**
1228     * Replaces an active tracked node. The node then becomes detached.
1229     *
1230     * @param currentData the current data of the model
1231     * @param selector the {@code NodeSelector} defining the tracked node
1232     * @param newNode the node replacing the tracked node
1233     * @return a flag whether the operation was successful
1234     */
1235    private boolean replaceActiveTrackedNode(final TreeData currentData,
1236            final NodeSelector selector, final ImmutableNode newNode)
1237    {
1238        final NodeTracker newTracker =
1239                currentData.getNodeTracker().replaceAndDetachTrackedNode(
1240                        selector, newNode);
1241        return structure.compareAndSet(currentData,
1242                currentData.updateNodeTracker(newTracker));
1243    }
1244
1245    /**
1246     * Creates tracked node entries for the specified nodes and creates the
1247     * corresponding selectors.
1248     *
1249     * @param refSelectors the reference where to store the selectors
1250     * @param nodes the nodes to be tracked
1251     * @param current the current {@code TreeData} object
1252     * @param resolver the {@code NodeKeyResolver}
1253     * @return the updated {@code TreeData} object
1254     */
1255    private static TreeData createSelectorsForTrackedNodes(
1256            final Mutable<Collection<NodeSelector>> refSelectors,
1257            final List<ImmutableNode> nodes, final TreeData current,
1258            final NodeKeyResolver<ImmutableNode> resolver)
1259    {
1260        final List<NodeSelector> selectors =
1261                new ArrayList<>(nodes.size());
1262        final Map<ImmutableNode, String> cache = new HashMap<>();
1263        for (final ImmutableNode node : nodes)
1264        {
1265            selectors.add(new NodeSelector(resolver.nodeKey(node, cache,
1266                    current)));
1267        }
1268        refSelectors.setValue(selectors);
1269        final NodeTracker newTracker =
1270                current.getNodeTracker().trackNodes(selectors, nodes);
1271        return current.updateNodeTracker(newTracker);
1272    }
1273
1274    /**
1275     * Adds a tracked node that has already been resolved to the specified data
1276     * object.
1277     *
1278     * @param current the current {@code TreeData} object
1279     * @param node the node in question
1280     * @param resolver the {@code NodeKeyResolver}
1281     * @param refSelector here the newly created {@code NodeSelector} is
1282     *        returned
1283     * @return the new {@code TreeData} instance
1284     */
1285    private static TreeData updateDataWithNewTrackedNode(final TreeData current,
1286            final ImmutableNode node, final NodeKeyResolver<ImmutableNode> resolver,
1287            final MutableObject<NodeSelector> refSelector)
1288    {
1289        final NodeSelector selector =
1290                new NodeSelector(resolver.nodeKey(node,
1291                        new HashMap<ImmutableNode, String>(), current));
1292        refSelector.setValue(selector);
1293        final NodeTracker newTracker =
1294                current.getNodeTracker().trackNodes(
1295                        Collections.singleton(selector),
1296                        Collections.singleton(node));
1297        return current.updateNodeTracker(newTracker);
1298    }
1299
1300    /**
1301     * Creates a new data object with a tracked child node of the given parent
1302     * node. If such a child node already exists, it is used. Otherwise, a new
1303     * one is created.
1304     *
1305     * @param current the current {@code TreeData} object
1306     * @param parent the parent node
1307     * @param childName the name of the child node
1308     * @param resolver the {@code NodeKeyResolver}
1309     * @param refSelector here the newly created {@code NodeSelector} is
1310     *        returned
1311     * @return the new {@code TreeData} instance
1312     */
1313    private static TreeData createDataWithTrackedChildNode(final TreeData current,
1314            final ImmutableNode parent, final String childName,
1315            final NodeKeyResolver<ImmutableNode> resolver,
1316            final MutableObject<NodeSelector> refSelector)
1317    {
1318        TreeData newData;
1319        final List<ImmutableNode> namedChildren =
1320                current.getChildren(parent, childName);
1321        if (!namedChildren.isEmpty())
1322        {
1323            newData =
1324                    updateDataWithNewTrackedNode(current, namedChildren.get(0),
1325                            resolver, refSelector);
1326        }
1327        else
1328        {
1329            final ImmutableNode child =
1330                    new ImmutableNode.Builder().name(childName).create();
1331            final ModelTransaction tx = new ModelTransaction(current, null, resolver);
1332            tx.addAddNodeOperation(parent, child);
1333            newData =
1334                    updateDataWithNewTrackedNode(tx.execute(), child, resolver,
1335                            refSelector);
1336        }
1337        return newData;
1338    }
1339
1340    /**
1341     * Checks whether the specified collection with values is not empty.
1342     *
1343     * @param values the collection with node values
1344     * @return <b>true</b> if values are provided, <b>false</b> otherwise
1345     */
1346    private static boolean valuesNotEmpty(final Iterable<?> values)
1347    {
1348        return values.iterator().hasNext();
1349    }
1350
1351    /**
1352     * Creates an exception referring to an invalid key for adding properties.
1353     * Such an exception is thrown when an operation tries to add something to
1354     * an attribute.
1355     *
1356     * @param key the invalid key causing this exception
1357     * @return the exception
1358     */
1359    private static RuntimeException attributeKeyException(final String key)
1360    {
1361        return new IllegalArgumentException(
1362                "New nodes cannot be added to an attribute key: " + key);
1363    }
1364
1365    /**
1366     * An interface used internally for handling concurrent updates. An
1367     * implementation has to populate the passed in {@code ModelTransaction}.
1368     * The transaction is then executed, and an atomic update of the model's
1369     * {@code TreeData} is attempted. If this fails - because another update
1370     * came across -, the whole operation has to be tried anew.
1371     */
1372    private interface TransactionInitializer
1373    {
1374        /**
1375         * Initializes the specified transaction for an update operation. The
1376         * return value indicates whether the transaction should be executed. A
1377         * result of <b>false</b> means that the update is to be aborted (maybe
1378         * another update method was called).
1379         *
1380         * @param tx the transaction to be initialized
1381         * @return a flag whether the update should continue
1382         */
1383        boolean initTransaction(ModelTransaction tx);
1384    }
1385}