    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 {@link ImmutableNode} structures.
    036 * </p>
    037 * <p>
    038 * This {@code NodeModel} implementation keeps all its data as a tree of {@link ImmutableNode} objects in memory. The
    039 * managed structure can be manipulated in a thread-safe, non-blocking way. This is achieved by using atomic variables:
    040 * The root of the tree is stored in an atomic reference variable. Each update operation causes a new structure to be
    041 * constructed (which reuses as much from the original structure as possible). The old root node is then replaced by the
    042 * new one using an atomic compare-and-set operation. If this fails, the manipulation has to be done anew on the updated
    043 * structure.
    044 * </p>
    045 *
    046 * @since 2.0
    047 */
    048public class InMemoryNodeModel implements NodeModel<ImmutableNode> {
    049    /**
    050     * A dummy node handler instance used in operations which require only a limited functionality.
    051     */
    052    private static final NodeHandler<ImmutableNode> DUMMY_HANDLER = new TreeData(null, Collections.<ImmutableNode, ImmutableNode>emptyMap(),
    053        Collections.<ImmutableNode, ImmutableNode>emptyMap(), null, new ReferenceTracker());
    054
    055    /** Stores information about the current nodes structure. */
    056    private final AtomicReference<TreeData> structure;
    057
    058    /**
    059     * Creates a new instance of {@code InMemoryNodeModel} which is initialized with an empty root node.
    060     */
    061    public InMemoryNodeModel() {
    062        this(null);
    063    }
    064
    065    /**
    066     * Creates a new instance of {@code InMemoryNodeModel} and initializes it from the given root node. If the passed in
    067     * node is <b>null</b>, a new, empty root node is created.
    068     *
    069     * @param root the new root node for this model
    070     */
    071    public InMemoryNodeModel(final ImmutableNode root) {
    072        structure = new AtomicReference<>(createTreeData(initialRootNode(root), null));
    073    }
    074
    075    /**
    076     * Returns the root node of this mode. Note: This method should be used with care. The model may be updated concurrently
    077     * which causes the root node to be replaced. If the root node is to be processed further (e.g. by executing queries on
    078     * it), the model should be asked for its {@code NodeHandler}, and the root node should be obtained from there. The
    079     * connection between a node handler and its root node remain constant because an update of the model causes the whole
    080     * node handler to be replaced.
    081     *
    082     * @return the current root node
    083     */
    084    public ImmutableNode getRootNode() {
    085        return getTreeData().getRootNode();
    086    }
    087
    088    /**
    089     * {@inheritDoc} {@code InMemoryNodeModel} implements the {@code NodeHandler} interface itself. So this implementation
    090     * just returns the <strong>this</strong> reference.
    091     */
    092    @Override
    093    public NodeHandler<ImmutableNode> getNodeHandler() {
    094        return getReferenceNodeHandler();
    095    }
    096
    097    @Override
    098    public void addProperty(final String key, final Iterable<?> values, final NodeKeyResolver<ImmutableNode> resolver) {
    099        addProperty(key, null, values, resolver);
    100    }
    101
    102    /**
    103     * Adds new property values using a tracked node as root node. This method works like the normal {@code addProperty()}
    104     * method, but the origin of the operation (also for the interpretation of the passed in key) is a tracked node
    105     * identified by the passed in {@code NodeSelector}. The selector can be <b>null</b>, then the root node is assumed.
    106     *
    107     * @param key the key
    108     * @param selector the {@code NodeSelector} defining the root node (or <b>null</b>)
    109     * @param values the values to be added
    110     * @param resolver the {@code NodeKeyResolver}
    111     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    112     */
    113    public void addProperty(final String key, final NodeSelector selector, final Iterable<?> values, final NodeKeyResolver<ImmutableNode> resolver) {
    114        if (valuesNotEmpty(values)) {
    115            updateModel(tx -> {
    116                initializeAddTransaction(tx, key, values, resolver);
    117                return true;
    118            }, selector, resolver);
    119        }
    120    }
    121
    122    @Override
    123    public void addNodes(final String key, final Collection<? extends ImmutableNode> nodes, final NodeKeyResolver<ImmutableNode> resolver) {
    124        addNodes(key, null, nodes, resolver);
    125    }
    126
    127    /**
    128     * Adds new nodes using a tracked node as root node. This method works like the normal {@code addNodes()} method, but
    129     * the origin of the operation (also for the interpretation of the passed in key) is a tracked node identified by the
    130     * passed in {@code NodeSelector}. The selector can be <b>null</b>, then the root node is assumed.
    131     *
    132     * @param key the key
    133     * @param selector the {@code NodeSelector} defining the root node (or <b>null</b>)
    134     * @param nodes the collection of new nodes to be added
    135     * @param resolver the {@code NodeKeyResolver}
    136     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    137     */
    138    public void addNodes(final String key, final NodeSelector selector, final Collection<? extends ImmutableNode> nodes,
    139        final NodeKeyResolver<ImmutableNode> resolver) {
    140        if (nodes != null && !nodes.isEmpty()) {
    141            updateModel(tx -> {
    142                final List<QueryResult<ImmutableNode>> results = resolver.resolveKey(tx.getQueryRoot(), key, tx.getCurrentData());
    143                if (results.size() == 1) {
    144                    if (results.get(0).isAttributeResult()) {
    145                        throw attributeKeyException(key);
    146                    }
    147                    tx.addAddNodesOperation(results.get(0).getNode(), nodes);
    148                } else {
    149                    final NodeAddData<ImmutableNode> addData = resolver.resolveAddKey(tx.getQueryRoot(), key, tx.getCurrentData());
    150                    if (addData.isAttribute()) {
    151                        throw attributeKeyException(key);
    152                    }
    153                    final ImmutableNode newNode = new ImmutableNode.Builder(nodes.size()).name(addData.getNewNodeName()).addChildren(nodes).create();
    154                    addNodesByAddData(tx, addData, Collections.singleton(newNode));
    155                }
    156                return true;
    157            }, selector, resolver);
    158        }
    159    }
    160
    161    @Override
    162    public void setProperty(final String key, final Object value, final NodeKeyResolver<ImmutableNode> resolver) {
    163        setProperty(key, null, value, resolver);
    164    }
    165
    166    /**
    167     * Sets the value of a property using a tracked node as root node. This method works like the normal
    168     * {@code setProperty()} method, but the origin of the operation (also for the interpretation of the passed in key) is a
    169     * tracked node identified by the passed in {@code NodeSelector}. The selector can be <b>null</b>, then the root node is
    170     * assumed.
    171     *
    172     * @param key the key
    173     * @param selector the {@code NodeSelector} defining the root node (or <b>null</b>)
    174     * @param value the new value for this property
    175     * @param resolver the {@code NodeKeyResolver}
    176     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    177     */
    178    public void setProperty(final String key, final NodeSelector selector, final Object value, final NodeKeyResolver<ImmutableNode> resolver) {
    179        updateModel(tx -> {
    180            boolean added = false;
    181            final NodeUpdateData<ImmutableNode> updateData = resolver.resolveUpdateKey(tx.getQueryRoot(), key, value, tx.getCurrentData());
    182            if (!updateData.getNewValues().isEmpty()) {
    183                initializeAddTransaction(tx, key, updateData.getNewValues(), resolver);
    184                added = true;
    185            }
    186            final boolean cleared = initializeClearTransaction(tx, updateData.getRemovedNodes());
    187            final boolean updated = initializeUpdateTransaction(tx, updateData.getChangedValues());
    188            return added || cleared || updated;
    189        }, selector, resolver);
    190    }
    191
    192    /**
    193     * {@inheritDoc} This implementation checks whether nodes become undefined after subtrees have been removed. If this is
    194     * the case, such nodes are removed, too. Return value is a collection with {@code QueryResult} objects for the elements
    195     * to be removed from the model.
    196     */
    197    @Override
    198    public List<QueryResult<ImmutableNode>> clearTree(final String key, final NodeKeyResolver<ImmutableNode> resolver) {
    199        return clearTree(key, null, resolver);
    200    }
    201
    202    /**
    203     * Clears a whole sub tree using a tracked node as root node. This method works like the normal {@code clearTree()}
    204     * method, but the origin of the operation (also for the interpretation of the passed in key) is a tracked node
    205     * identified by the passed in {@code NodeSelector}. The selector can be <b>null</b>, then the root node is assumed.
    206     *
    207     * @param key the key
    208     * @param selector the {@code NodeSelector} defining the root node (or <b>null</b>)
    209     * @param resolver the {@code NodeKeyResolver}
    210     * @return a list with the results to be removed
    211     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    212     */
    213    public List<QueryResult<ImmutableNode>> clearTree(final String key, final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver) {
    214        final List<QueryResult<ImmutableNode>> removedElements = new LinkedList<>();
    215        updateModel(tx -> {
    216            boolean changes = false;
    217            final TreeData currentStructure = tx.getCurrentData();
    218            final List<QueryResult<ImmutableNode>> results = resolver.resolveKey(tx.getQueryRoot(), key, currentStructure);
    219            removedElements.clear();
    220            removedElements.addAll(results);
    221            for (final QueryResult<ImmutableNode> result : results) {
    222                if (result.isAttributeResult()) {
    223                    tx.addRemoveAttributeOperation(result.getNode(), result.getAttributeName());
    224                } else {
    225                    if (result.getNode() == currentStructure.getRootNode()) {
    226                        // the whole model is to be cleared
    227                        clear(resolver);
    228                        return false;
    229                    }
    230                    tx.addRemoveNodeOperation(currentStructure.getParent(result.getNode()), result.getNode());
    231                }
    232                changes = true;
    233            }
    234            return changes;
    235        }, selector, resolver);
    236
    237        return removedElements;
    238    }
    239
    240    /**
    241     * {@inheritDoc} If this operation leaves an affected node in an undefined state, it is removed from the model.
    242     */
    243    @Override
    244    public void clearProperty(final String key, final NodeKeyResolver<ImmutableNode> resolver) {
    245        clearProperty(key, null, resolver);
    246    }
    247
    248    /**
    249     * Clears a property using a tracked node as root node. This method works like the normal {@code clearProperty()}
    250     * method, but the origin of the operation (also for the interpretation of the passed in key) is a tracked node
    251     * identified by the passed in {@code NodeSelector}. The selector can be <b>null</b>, then the root node is assumed.
    252     *
    253     * @param key the key
    254     * @param selector the {@code NodeSelector} defining the root node (or <b>null</b>)
    255     * @param resolver the {@code NodeKeyResolver}
    256     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    257     */
    258    public void clearProperty(final String key, final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver) {
    259        updateModel(tx -> {
    260            final List<QueryResult<ImmutableNode>> results = resolver.resolveKey(tx.getQueryRoot(), key, tx.getCurrentData());
    261            return initializeClearTransaction(tx, results);
    262        }, selector, resolver);
    263    }
    264
    265    /**
    266     * {@inheritDoc} A new empty root node is created with the same name as the current root node. Implementation note:
    267     * Because this is a hard reset the usual dance for dealing with concurrent updates is not required here.
    268     *
    269     * @param resolver the {@code NodeKeyResolver}
    270     */
    271    @Override
    272    public void clear(final NodeKeyResolver<ImmutableNode> resolver) {
    273        final ImmutableNode newRoot = new ImmutableNode.Builder().name(getRootNode().getNodeName()).create();
    274        setRootNode(newRoot);
    275    }
    276
    277    /**
    278     * {@inheritDoc} This implementation simply returns the current root node of this model.
    279     */
    280    @Override
    281    public ImmutableNode getInMemoryRepresentation() {
    282        return getTreeData().getRootNode();
    283    }
    284
    285    /**
    286     * {@inheritDoc} All tracked nodes and reference objects managed by this model are cleared.Care has to be taken when
    287     * this method is used and the model is accessed by multiple threads. It is not deterministic which concurrent
    288     * operations see the old root and which see the new root node.
    289     *
    290     * @param newRoot the new root node to be set (can be <b>null</b>, then an empty root node is set)
    291     */
    292    @Override
    293    public void setRootNode(final ImmutableNode newRoot) {
    294        structure.set(createTreeData(initialRootNode(newRoot), structure.get()));
    295    }
    296
    297    /**
    298     * Replaces the root node of this model. This method is similar to {@link #setRootNode(ImmutableNode)}; however, tracked
    299     * nodes will not get lost. The model applies the selectors of all tracked nodes on the new nodes hierarchy, so that
    300     * corresponding nodes are selected (this may cause nodes to become detached if a select operation fails). This
    301     * operation is useful if the new nodes hierarchy to be set is known to be similar to the old one. Note that reference
    302     * objects are lost; there is no way to automatically match nodes between the old and the new nodes hierarchy.
    303     *
    304     * @param newRoot the new root node to be set (must not be <b>null</b>)
    305     * @param resolver the {@code NodeKeyResolver}
    306     * @throws IllegalArgumentException if the new root node is <b>null</b>
    307     */
    308    public void replaceRoot(final ImmutableNode newRoot, final NodeKeyResolver<ImmutableNode> resolver) {
    309        if (newRoot == null) {
    310            throw new IllegalArgumentException("Replaced root node must not be null!");
    311        }
    312
    313        final TreeData current = structure.get();
    314        // this step is needed to get a valid NodeHandler
    315        final TreeData temp = createTreeDataForRootAndTracker(newRoot, current.getNodeTracker());
    316        structure.set(temp.updateNodeTracker(temp.getNodeTracker().update(newRoot, null, resolver, temp)));
    317    }
    318
    319    /**
    320     * Merges the root node of this model with the specified node. This method is typically caused by configuration
    321     * implementations when a configuration source is loaded, and its data has to be added to the model. It is possible to
    322     * define the new name of the root node and to pass in a map with reference objects.
    323     *
    324     * @param node the node to be merged with the root node
    325     * @param rootName the new name of the root node; can be <b>null</b>, then the name of the root node is not changed
    326     *        unless it is <b>null</b>
    327     * @param references an optional map with reference objects
    328     * @param rootRef an optional reference object for the new root node
    329     * @param resolver the {@code NodeKeyResolver}
    330     */
    331    public void mergeRoot(final ImmutableNode node, final String rootName, final Map<ImmutableNode, ?> references, final Object rootRef,
    332        final NodeKeyResolver<ImmutableNode> resolver) {
    333        updateModel(tx -> {
    334            final TreeData current = tx.getCurrentData();
    335            final String newRootName = determineRootName(current.getRootNode(), node, rootName);
    336            if (newRootName != null) {
    337                tx.addChangeNodeNameOperation(current.getRootNode(), newRootName);
    338            }
    339            tx.addAddNodesOperation(current.getRootNode(), node.getChildren());
    340            tx.addAttributesOperation(current.getRootNode(), node.getAttributes());
    341            if (node.getValue() != null) {
    342                tx.addChangeNodeValueOperation(current.getRootNode(), node.getValue());
    343            }
    344            if (references != null) {
    345                tx.addNewReferences(references);
    346            }
    347            if (rootRef != null) {
    348                tx.addNewReference(current.getRootNode(), rootRef);
    349            }
    350            return true;
    351        }, null, resolver);
    352    }
    353
    354    /**
    355     * Adds a node to be tracked. After this method has been called with a specific {@code NodeSelector}, the node
    356     * associated with this key can be always obtained using {@link #getTrackedNode(NodeSelector)} with the same selector.
    357     * This is useful because during updates of a model parts of the structure are replaced. Therefore, it is not a good
    358     * idea to simply hold a reference to a node; this might become outdated soon. Rather, the node should be tracked. This
    359     * mechanism ensures that always the correct node reference can be obtained.
    360     *
    361     * @param selector the {@code NodeSelector} defining the desired node
    362     * @param resolver the {@code NodeKeyResolver}
    363     * @throws ConfigurationRuntimeException if the selector does not select a single node
    364     */
    365    public void trackNode(final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver) {
    366        boolean done;
    367        do {
    368            final TreeData current = structure.get();
    369            final NodeTracker newTracker = current.getNodeTracker().trackNode(current.getRootNode(), selector, resolver, current);
    370            done = structure.compareAndSet(current, current.updateNodeTracker(newTracker));
    371        } while (!done);
    372    }
    373
    374    /**
    375     * Allows tracking all nodes selected by a key. This method evaluates the specified key on the current nodes structure.
    376     * For all selected nodes corresponding {@code NodeSelector} objects are created, and they are tracked. The returned
    377     * collection of {@code NodeSelector} objects can be used for interacting with the selected nodes.
    378     *
    379     * @param key the key for selecting the nodes to track
    380     * @param resolver the {@code NodeKeyResolver}
    381     * @return a collection with the {@code NodeSelector} objects for the new tracked nodes
    382     */
    383    public Collection<NodeSelector> selectAndTrackNodes(final String key, final NodeKeyResolver<ImmutableNode> resolver) {
    384        final Mutable<Collection<NodeSelector>> refSelectors = new MutableObject<>();
    385        boolean done;
    386        do {
    387            final TreeData current = structure.get();
    388            final List<ImmutableNode> nodes = resolver.resolveNodeKey(current.getRootNode(), key, current);
    389            if (nodes.isEmpty()) {
    390                return Collections.emptyList();
    391            }
    392            done = structure.compareAndSet(current, createSelectorsForTrackedNodes(refSelectors, nodes, current, resolver));
    393        } while (!done);
    394        return refSelectors.getValue();
    395    }
    396
    397    /**
    398     * Tracks all nodes which are children of the node selected by the passed in key. If the key selects exactly one node,
    399     * for all children of this node {@code NodeSelector} objects are created, and they become tracked nodes. The returned
    400     * collection of {@code NodeSelector} objects can be used for interacting with the selected nodes.
    401     *
    402     * @param key the key for selecting the parent node whose children are to be tracked
    403     * @param resolver the {@code NodeKeyResolver}
    404     * @return a collection with the {@code NodeSelector} objects for the new tracked nodes
    405     */
    406    public Collection<NodeSelector> trackChildNodes(final String key, final NodeKeyResolver<ImmutableNode> resolver) {
    407        final Mutable<Collection<NodeSelector>> refSelectors = new MutableObject<>();
    408        boolean done;
    409        do {
    410            refSelectors.setValue(Collections.<NodeSelector>emptyList());
    411            final TreeData current = structure.get();
    412            final List<ImmutableNode> nodes = resolver.resolveNodeKey(current.getRootNode(), key, current);
    413            if (nodes.size() == 1) {
    414                final ImmutableNode node = nodes.get(0);
    415                done = node.getChildren().isEmpty()
    416                    || structure.compareAndSet(current, createSelectorsForTrackedNodes(refSelectors, node.getChildren(), current, resolver));
    417            } else {
    418                done = true;
    419            }
    420        } while (!done);
    421        return refSelectors.getValue();
    422    }
    423
    424    /**
    425     * Tracks a node which is a child of another node selected by the passed in key. If the selected node has a child node
    426     * with this name, it is tracked and its selector is returned. Otherwise, a new child node with this name is created
    427     * first.
    428     *
    429     * @param key the key for selecting the parent node
    430     * @param childName the name of the child node
    431     * @param resolver the {@code NodeKeyResolver}
    432     * @return the {@code NodeSelector} for the tracked child node
    433     * @throws ConfigurationRuntimeException if the passed in key does not select a single node
    434     */
    435    public NodeSelector trackChildNodeWithCreation(final String key, final String childName, final NodeKeyResolver<ImmutableNode> resolver) {
    436        final MutableObject<NodeSelector> refSelector = new MutableObject<>();
    437        boolean done;
    438
    439        do {
    440            final TreeData current = structure.get();
    441            final List<ImmutableNode> nodes = resolver.resolveNodeKey(current.getRootNode(), key, current);
    442            if (nodes.size() != 1) {
    443                throw new ConfigurationRuntimeException("Key does not select a single node: " + key);
    444            }
    445
    446            final ImmutableNode parent = nodes.get(0);
    447            final TreeData newData = createDataWithTrackedChildNode(current, parent, childName, resolver, refSelector);
    448
    449            done = structure.compareAndSet(current, newData);
    450        } while (!done);
    451
    452        return refSelector.getValue();
    453    }
    454
    455    /**
    456     * Returns the current {@code ImmutableNode} instance associated with the given {@code NodeSelector}. The node must be a
    457     * tracked node, i.e. {@link #trackNode(NodeSelector, NodeKeyResolver)} must have been called before with the given
    458     * selector.
    459     *
    460     * @param selector the {@code NodeSelector} defining the desired node
    461     * @return the current {@code ImmutableNode} associated with this selector
    462     * @throws ConfigurationRuntimeException if the selector is unknown
    463     */
    464    public ImmutableNode getTrackedNode(final NodeSelector selector) {
    465        return structure.get().getNodeTracker().getTrackedNode(selector);
    466    }
    467
    468    /**
    469     * Replaces a tracked node by another node. If the tracked node is not yet detached, it becomes now detached. The passed
    470     * in node (which must not be <b>null</b>) becomes the new root node of an independent model for this tracked node.
    471     * Further updates of this model do not affect the tracked node's model and vice versa.
    472     *
    473     * @param selector the {@code NodeSelector} defining the tracked node
    474     * @param newNode the node replacing the tracked node (must not be <b>null</b>)
    475     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    476     * @throws IllegalArgumentException if the replacement node is <b>null</b>
    477     */
    478    public void replaceTrackedNode(final NodeSelector selector, final ImmutableNode newNode) {
    479        if (newNode == null) {
    480            throw new IllegalArgumentException("Replacement node must not be null!");
    481        }
    482
    483        boolean done;
    484        do {
    485            final TreeData currentData = structure.get();
    486            done = replaceDetachedTrackedNode(currentData, selector, newNode) || replaceActiveTrackedNode(currentData, selector, newNode);
    487        } while (!done);
    488    }
    489
    490    /**
    491     * Returns a {@code NodeHandler} for a tracked node. Such a handler may be required for operations on a sub tree of the
    492     * model. The handler to be returned depends on the current state of the tracked node. If it is still active, a handler
    493     * is used which shares some data (especially the parent mapping) with this model. Detached track nodes in contrast have
    494     * their own separate model; in this case a handler associated with this model is returned.
    495     *
    496     * @param selector the {@code NodeSelector} defining the tracked node
    497     * @return a {@code NodeHandler} for this tracked node
    498     * @throws ConfigurationRuntimeException if the selector is unknown
    499     */
    500    public NodeHandler<ImmutableNode> getTrackedNodeHandler(final NodeSelector selector) {
    501        final TreeData currentData = structure.get();
    502        final InMemoryNodeModel detachedNodeModel = currentData.getNodeTracker().getDetachedNodeModel(selector);
    503        return detachedNodeModel != null ? detachedNodeModel.getNodeHandler()
    504            : new TrackedNodeHandler(currentData.getNodeTracker().getTrackedNode(selector), currentData);
    505    }
    506
    507    /**
    508     * Returns a flag whether the specified tracked node is detached. As long as the {@code NodeSelector} associated with
    509     * that node returns a single instance, the tracked node is said to be <em>life</em>. If now an update of the model
    510     * happens which invalidates the selector (maybe the target node was removed), the tracked node becomes detached. It is
    511     * still possible to query the node; here the latest valid instance is returned. But further changes on the node model
    512     * are no longer tracked for this node. So even if there are further changes which would make the {@code NodeSelector}
    513     * valid again, the tracked node stays in detached state.
    514     *
    515     * @param selector the {@code NodeSelector} defining the desired node
    516     * @return a flag whether this tracked node is in detached state
    517     * @throws ConfigurationRuntimeException if the selector is unknown
    518     */
    519    public boolean isTrackedNodeDetached(final NodeSelector selector) {
    520        return structure.get().getNodeTracker().isTrackedNodeDetached(selector);
    521    }
    522
    523    /**
    524     * Removes a tracked node. This method is the opposite of {@code trackNode()}. It has to be called if there is no longer
    525     * the need to track a specific node. Note that for each call of {@code trackNode()} there has to be a corresponding
    526     * {@code untrackNode()} call. This ensures that multiple observers can track the same node.
    527     *
    528     * @param selector the {@code NodeSelector} defining the desired node
    529     * @throws ConfigurationRuntimeException if the specified node is not tracked
    530     */
    531    public void untrackNode(final NodeSelector selector) {
    532        boolean done;
    533        do {
    534            final TreeData current = structure.get();
    535            final NodeTracker newTracker = current.getNodeTracker().untrackNode(selector);
    536            done = structure.compareAndSet(current, current.updateNodeTracker(newTracker));
    537        } while (!done);
    538    }
    539
    540    /**
    541     * Returns a {@code ReferenceNodeHandler} object for this model. This extended node handler can be used to query
    542     * references objects stored for this model.
    543     *
    544     * @return the {@code ReferenceNodeHandler}
    545     */
    546    public ReferenceNodeHandler getReferenceNodeHandler() {
    547        return getTreeData();
    548    }
    549
    550    /**
    551     * Returns the current {@code TreeData} object. This object contains all information about the current node structure.
    552     *
    553     * @return the current {@code TreeData} object
    554     */
    555    TreeData getTreeData() {
    556        return structure.get();
    557    }
    558
    559    /**
    560     * Updates the mapping from nodes to their parents for the passed in hierarchy of nodes. This method traverses all
    561     * children and grand-children of the passed in root node. For each node in the subtree the parent relation is added to
    562     * the map.
    563     *
    564     * @param parents the map with parent nodes
    565     * @param root the root node of the current tree
    566     */
    567    static void updateParentMapping(final Map<ImmutableNode, ImmutableNode> parents, final ImmutableNode root) {
    568        NodeTreeWalker.INSTANCE.walkBFS(root, new ConfigurationNodeVisitorAdapter<ImmutableNode>() {
    569            @Override
    570            public void visitBeforeChildren(final ImmutableNode node, final NodeHandler<ImmutableNode> handler) {
    571                for (final ImmutableNode c : node) {
    572                    parents.put(c, node);
    573                }
    574            }
    575        }, DUMMY_HANDLER);
    576    }
    577
    578    /**
    579     * Checks if the passed in node is defined. Result is <b>true</b> if the node contains any data.
    580     *
    581     * @param node the node in question
    582     * @return <b>true</b> if the node is defined, <b>false</b> otherwise
    583     */
    584    static boolean checkIfNodeDefined(final ImmutableNode node) {
    585        return node.getValue() != null || !node.getChildren().isEmpty() || !node.getAttributes().isEmpty();
    586    }
    587
    588    /**
    589     * Initializes a transaction for an add operation.
    590     *
    591     * @param tx the transaction to be initialized
    592     * @param key the key
    593     * @param values the collection with node values
    594     * @param resolver the {@code NodeKeyResolver}
    595     */
    596    private void initializeAddTransaction(final ModelTransaction tx, final String key, final Iterable<?> values,
    597        final NodeKeyResolver<ImmutableNode> resolver) {
    598        final NodeAddData<ImmutableNode> addData = resolver.resolveAddKey(tx.getQueryRoot(), key, tx.getCurrentData());
    599        if (addData.isAttribute()) {
    600            addAttributeProperty(tx, addData, values);
    601        } else {
    602            addNodeProperty(tx, addData, values);
    603        }
    604    }
    605
    606    /**
    607     * Creates a {@code TreeData} object for the specified root node.
    608     *
    609     * @param root the root node of the current tree
    610     * @param current the current {@code TreeData} object (may be <b>null</b>)
    611     * @return the {@code TreeData} describing the current tree
    612     */
    613    private TreeData createTreeData(final ImmutableNode root, final TreeData current) {
    614        final NodeTracker newTracker = current != null ? current.getNodeTracker().detachAllTrackedNodes() : new NodeTracker();
    615        return createTreeDataForRootAndTracker(root, newTracker);
    616    }
    617
    618    /**
    619     * Creates a {@code TreeData} object for the specified root node and {@code NodeTracker}. Other parameters are set to
    620     * default values.
    621     *
    622     * @param root the new root node for this model
    623     * @param newTracker the new {@code NodeTracker}
    624     * @return the new {@code TreeData} object
    625     */
    626    private TreeData createTreeDataForRootAndTracker(final ImmutableNode root, final NodeTracker newTracker) {
    627        return new TreeData(root, createParentMapping(root), Collections.<ImmutableNode, ImmutableNode>emptyMap(), newTracker, new ReferenceTracker());
    628    }
    629
    630    /**
    631     * Handles an add property operation if the property to be added is a node.
    632     *
    633     * @param tx the transaction
    634     * @param addData the {@code NodeAddData}
    635     * @param values the collection with node values
    636     */
    637    private static void addNodeProperty(final ModelTransaction tx, final NodeAddData<ImmutableNode> addData, final Iterable<?> values) {
    638        final Collection<ImmutableNode> newNodes = createNodesToAdd(addData.getNewNodeName(), values);
    639        addNodesByAddData(tx, addData, newNodes);
    640    }
    641
    642    /**
    643     * Initializes a transaction to add a collection of nodes as described by a {@code NodeAddData} object. If necessary,
    644     * new path nodes are created. Eventually, the new nodes are added as children to the specified target node.
    645     *
    646     * @param tx the transaction
    647     * @param addData the {@code NodeAddData}
    648     * @param newNodes the collection of new child nodes
    649     */
    650    private static void addNodesByAddData(final ModelTransaction tx, final NodeAddData<ImmutableNode> addData, final Collection<ImmutableNode> newNodes) {
    651        if (addData.getPathNodes().isEmpty()) {
    652            tx.addAddNodesOperation(addData.getParent(), newNodes);
    653        } else {
    654            final ImmutableNode newChild = createNodeToAddWithPath(addData, newNodes);
    655            tx.addAddNodeOperation(addData.getParent(), newChild);
    656        }
    657    }
    658
    659    /**
    660     * Handles an add property operation if the property to be added is an attribute.
    661     *
    662     * @param tx the transaction
    663     * @param addData the {@code NodeAddData}
    664     * @param values the collection with node values
    665     */
    666    private static void addAttributeProperty(final ModelTransaction tx, final NodeAddData<ImmutableNode> addData, final Iterable<?> values) {
    667        if (addData.getPathNodes().isEmpty()) {
    668            tx.addAttributeOperation(addData.getParent(), addData.getNewNodeName(), values.iterator().next());
    669        } else {
    670            final int pathNodeCount = addData.getPathNodes().size();
    671            final ImmutableNode childWithAttribute = new ImmutableNode.Builder().name(addData.getPathNodes().get(pathNodeCount - 1))
    672                .addAttribute(addData.getNewNodeName(), values.iterator().next()).create();
    673            final ImmutableNode newChild = pathNodeCount > 1
    674                ? createNodeOnPath(addData.getPathNodes().subList(0, pathNodeCount - 1).iterator(), Collections.singleton(childWithAttribute))
    675                : childWithAttribute;
    676            tx.addAddNodeOperation(addData.getParent(), newChild);
    677        }
    678    }
    679
    680    /**
    681     * Creates a collection with new nodes with a given name and a value from a given collection.
    682     *
    683     * @param newNodeName the name of the new nodes
    684     * @param values the collection with node values
    685     * @return the newly created collection
    686     */
    687    private static Collection<ImmutableNode> createNodesToAdd(final String newNodeName, final Iterable<?> values) {
    688        final Collection<ImmutableNode> nodes = new LinkedList<>();
    689        for (final Object value : values) {
    690            nodes.add(new ImmutableNode.Builder().name(newNodeName).value(value).create());
    691        }
    692        return nodes;
    693    }
    694
    695    /**
    696     * Creates a node structure consisting of the path nodes defined by the passed in {@code NodeAddData} instance and all
    697     * new child nodes.
    698     *
    699     * @param addData the {@code NodeAddData}
    700     * @param newNodes the collection of new child nodes
    701     * @return the parent node of the newly created hierarchy
    702     */
    703    private static ImmutableNode createNodeToAddWithPath(final NodeAddData<ImmutableNode> addData, final Collection<ImmutableNode> newNodes) {
    704        return createNodeOnPath(addData.getPathNodes().iterator(), newNodes);
    705    }
    706
    707    /**
    708     * Recursive helper method for creating a path node for an add operation. All path nodes except for the last have a
    709     * single child. The last path node has the new nodes as children.
    710     *
    711     * @param it the iterator over the names of the path nodes
    712     * @param newNodes the collection of new child nodes
    713     * @return the newly created path node
    714     */
    715    private static ImmutableNode createNodeOnPath(final Iterator<String> it, final Collection<ImmutableNode> newNodes) {
    716        final String nodeName = it.next();
    717        final ImmutableNode.Builder builder;
    718        if (it.hasNext()) {
    719            builder = new ImmutableNode.Builder(1);
    720            builder.addChild(createNodeOnPath(it, newNodes));
    721        } else {
    722            builder = new ImmutableNode.Builder(newNodes.size());
    723            builder.addChildren(newNodes);
    724        }
    725        return builder.name(nodeName).create();
    726    }
    727
    728    /**
    729     * Initializes a transaction to clear the values of a property based on the passed in collection of affected results.
    730     *
    731     * @param tx the transaction to be initialized
    732     * @param results a collection with results pointing to the nodes to be cleared
    733     * @return a flag whether there are elements to be cleared
    734     */
    735    private static boolean initializeClearTransaction(final ModelTransaction tx, final Collection<QueryResult<ImmutableNode>> results) {
    736        for (final QueryResult<ImmutableNode> result : results) {
    737            if (result.isAttributeResult()) {
    738                tx.addRemoveAttributeOperation(result.getNode(), result.getAttributeName());
    739            } else {
    740                tx.addClearNodeValueOperation(result.getNode());
    741            }
    742        }
    743
    744        return !results.isEmpty();
    745    }
    746
    747    /**
    748     * Initializes a transaction to change the values of some query results based on the passed in map.
    749     *
    750     * @param tx the transaction to be initialized
    751     * @param changedValues the map defining the elements to be changed
    752     * @return a flag whether there are elements to be updated
    753     */
    754    private static boolean initializeUpdateTransaction(final ModelTransaction tx, final Map<QueryResult<ImmutableNode>, Object> changedValues) {
    755        for (final Map.Entry<QueryResult<ImmutableNode>, Object> e : changedValues.entrySet()) {
    756            if (e.getKey().isAttributeResult()) {
    757                tx.addAttributeOperation(e.getKey().getNode(), e.getKey().getAttributeName(), e.getValue());
    758            } else {
    759                tx.addChangeNodeValueOperation(e.getKey().getNode(), e.getValue());
    760            }
    761        }
    762
    763        return !changedValues.isEmpty();
    764    }
    765
    766    /**
    767     * Determines the initial root node of this model. If a root node has been provided, it is used. Otherwise, an empty
    768     * dummy root node is created.
    769     *
    770     * @param providedRoot the passed in root node
    771     * @return the root node to be used
    772     */
    773    private static ImmutableNode initialRootNode(final ImmutableNode providedRoot) {
    774        return providedRoot != null ? providedRoot : new ImmutableNode.Builder().create();
    775    }
    776
    777    /**
    778     * Determines the name of the root node for a merge operation. If a root name is provided, it is used. Otherwise, if the
    779     * current root node has no name, the name of the node to be merged is used. A result of <b>null</b> means that no node
    780     * name has to be set.
    781     *
    782     * @param rootNode the current root node
    783     * @param node the node to be merged with the root node
    784     * @param rootName the name of the resulting node
    785     * @return the new name of the root node
    786     */
    787    private static String determineRootName(final ImmutableNode rootNode, final ImmutableNode node, final String rootName) {
    788        if (rootName != null) {
    789            return rootName;
    790        }
    791        if (rootNode.getNodeName() == null) {
    792            return node.getNodeName();
    793        }
    794        return null;
    795    }
    796
    797    /**
    798     * Creates the mapping to parent nodes for the nodes structured represented by the passed in root node. Each node is
    799     * assigned its parent node. Here an iterative algorithm is used rather than a recursive one to avoid stack overflow for
    800     * huge structures.
    801     *
    802     * @param root the root node of the structure
    803     * @return the parent node mapping
    804     */
    805    private Map<ImmutableNode, ImmutableNode> createParentMapping(final ImmutableNode root) {
    806        final Map<ImmutableNode, ImmutableNode> parents = new HashMap<>();
    807        updateParentMapping(parents, root);
    808        return parents;
    809    }
    810
    811    /**
    812     * Performs a non-blocking, thread-safe update of this model based on a transaction initialized by the passed in
    813     * initializer. This method uses the atomic reference for the model's current data to ensure that an update was
    814     * successful even if the model is concurrently accessed.
    815     *
    816     * @param txInit the {@code TransactionInitializer}
    817     * @param selector an optional {@code NodeSelector} defining the target node of the transaction
    818     * @param resolver the {@code NodeKeyResolver}
    819     */
    820    private void updateModel(final TransactionInitializer txInit, final NodeSelector selector, final NodeKeyResolver<ImmutableNode> resolver) {
    821        boolean done;
    822
    823        do {
    824            final TreeData currentData = getTreeData();
    825            done = executeTransactionOnDetachedTrackedNode(txInit, selector, currentData, resolver)
    826                || executeTransactionOnCurrentStructure(txInit, selector, currentData, resolver);
    827        } while (!done);
    828    }
    829
    830    /**
    831     * Executes a transaction on the current data of this model. This method is called if an operation is to be executed on
    832     * the model's root node or a tracked node which is not yet detached.
    833     *
    834     * @param txInit the {@code TransactionInitializer}
    835     * @param selector an optional {@code NodeSelector} defining the target node
    836     * @param currentData the current data of the model
    837     * @param resolver the {@code NodeKeyResolver}
    838     * @return a flag whether the operation has been completed successfully
    839     */
    840    private boolean executeTransactionOnCurrentStructure(final TransactionInitializer txInit, final NodeSelector selector, final TreeData currentData,
    841        final NodeKeyResolver<ImmutableNode> resolver) {
    842        final boolean done;
    843        final ModelTransaction tx = new ModelTransaction(currentData, selector, resolver);
    844        if (!txInit.initTransaction(tx)) {
    845            done = true;
    846        } else {
    847            final TreeData newData = tx.execute();
    848            done = structure.compareAndSet(tx.getCurrentData(), newData);
    849        }
    850        return done;
    851    }
    852
    853    /**
    854     * Tries to execute a transaction on the model of a detached tracked node. This method checks whether the target node of
    855     * the transaction is a tracked node and if this node is already detached. If this is the case, the update operation is
    856     * independent on this model and has to be executed on the specific model for the detached node.
    857     *
    858     * @param txInit the {@code TransactionInitializer}
    859     * @param selector an optional {@code NodeSelector} defining the target node
    860     * @param currentData the current data of the model
    861     * @param resolver the {@code NodeKeyResolver} @return a flag whether the transaction could be executed
    862     * @throws ConfigurationRuntimeException if the selector cannot be resolved
    863     */
    864    private boolean executeTransactionOnDetachedTrackedNode(final TransactionInitializer txInit, final NodeSelector selector, final TreeData currentData,
    865        final NodeKeyResolver<ImmutableNode> resolver) {
    866        if (selector != null) {
    867            final InMemoryNodeModel detachedNodeModel = currentData.getNodeTracker().getDetachedNodeModel(selector);
    868            if (detachedNodeModel != null) {
    869                detachedNodeModel.updateModel(txInit, null, resolver);
    870                return true;
    871            }
    872        }
    873
    874        return false;
    875    }
    876
    877    /**
    878     * Replaces a tracked node if it is already detached.
    879     *
    880     * @param currentData the current data of the model
    881     * @param selector the {@code NodeSelector} defining the tracked node
    882     * @param newNode the node replacing the tracked node
    883     * @return a flag whether the operation was successful
    884     */
    885    private boolean replaceDetachedTrackedNode(final TreeData currentData, final NodeSelector selector, final ImmutableNode newNode) {
    886        final InMemoryNodeModel detachedNodeModel = currentData.getNodeTracker().getDetachedNodeModel(selector);
    887        if (detachedNodeModel != null) {
    888            detachedNodeModel.setRootNode(newNode);
    889            return true;
    890        }
    891
    892        return false;
    893    }
    894
    895    /**
    896     * Replaces an active tracked node. The node then becomes detached.
    897     *
    898     * @param currentData the current data of the model
    899     * @param selector the {@code NodeSelector} defining the tracked node
    900     * @param newNode the node replacing the tracked node
    901     * @return a flag whether the operation was successful
    902     */
    903    private boolean replaceActiveTrackedNode(final TreeData currentData, final NodeSelector selector, final ImmutableNode newNode) {
    904        final NodeTracker newTracker = currentData.getNodeTracker().replaceAndDetachTrackedNode(selector, newNode);
    905        return structure.compareAndSet(currentData, currentData.updateNodeTracker(newTracker));
    906    }
    907
    908    /**
    909     * Creates tracked node entries for the specified nodes and creates the corresponding selectors.
    910     *
    911     * @param refSelectors the reference where to store the selectors
    912     * @param nodes the nodes to be tracked
    913     * @param current the current {@code TreeData} object
    914     * @param resolver the {@code NodeKeyResolver}
    915     * @return the updated {@code TreeData} object
    916     */
    917    private static TreeData createSelectorsForTrackedNodes(final Mutable<Collection<NodeSelector>> refSelectors, final List<ImmutableNode> nodes,
    918        final TreeData current, final NodeKeyResolver<ImmutableNode> resolver) {
    919        final List<NodeSelector> selectors = new ArrayList<>(nodes.size());
    920        final Map<ImmutableNode, String> cache = new HashMap<>();
    921        for (final ImmutableNode node : nodes) {
    922            selectors.add(new NodeSelector(resolver.nodeKey(node, cache, current)));
    923        }
    924        refSelectors.setValue(selectors);
    925        final NodeTracker newTracker = current.getNodeTracker().trackNodes(selectors, nodes);
    926        return current.updateNodeTracker(newTracker);
    927    }
    928
    929    /**
    930     * Adds a tracked node that has already been resolved to the specified data object.
    931     *
    932     * @param current the current {@code TreeData} object
    933     * @param node the node in question
    934     * @param resolver the {@code NodeKeyResolver}
    935     * @param refSelector here the newly created {@code NodeSelector} is returned
    936     * @return the new {@code TreeData} instance
    937     */
    938    private static TreeData updateDataWithNewTrackedNode(final TreeData current, final ImmutableNode node, final NodeKeyResolver<ImmutableNode> resolver,
    939        final MutableObject<NodeSelector> refSelector) {
    940        final NodeSelector selector = new NodeSelector(resolver.nodeKey(node, new HashMap<>(), current));
    941        refSelector.setValue(selector);
    942        final NodeTracker newTracker = current.getNodeTracker().trackNodes(Collections.singleton(selector), Collections.singleton(node));
    943        return current.updateNodeTracker(newTracker);
    944    }
    945
    946    /**
    947     * Creates a new data object with a tracked child node of the given parent node. If such a child node already exists, it
    948     * is used. Otherwise, a new one is created.
    949     *
    950     * @param current the current {@code TreeData} object
    951     * @param parent the parent node
    952     * @param childName the name of the child node
    953     * @param resolver the {@code NodeKeyResolver}
    954     * @param refSelector here the newly created {@code NodeSelector} is returned
    955     * @return the new {@code TreeData} instance
    956     */
    957    private static TreeData createDataWithTrackedChildNode(final TreeData current, final ImmutableNode parent, final String childName,
    958        final NodeKeyResolver<ImmutableNode> resolver, final MutableObject<NodeSelector> refSelector) {
    959        final TreeData newData;
    960        final List<ImmutableNode> namedChildren = current.getChildren(parent, childName);
    961        if (!namedChildren.isEmpty()) {
    962            newData = updateDataWithNewTrackedNode(current, namedChildren.get(0), resolver, refSelector);
    963        } else {
    964            final ImmutableNode child = new ImmutableNode.Builder().name(childName).create();
    965            final ModelTransaction tx = new ModelTransaction(current, null, resolver);
    966            tx.addAddNodeOperation(parent, child);
    967            newData = updateDataWithNewTrackedNode(tx.execute(), child, resolver, refSelector);
    968        }
    969        return newData;
    970    }
    971
    972    /**
    973     * Checks whether the specified collection with values is not empty.
    974     *
    975     * @param values the collection with node values
    976     * @return <b>true</b> if values are provided, <b>false</b> otherwise
    977     */
    978    private static boolean valuesNotEmpty(final Iterable<?> values) {
    979        return values.iterator().hasNext();
    980    }
    981
    982    /**
    983     * Creates an exception referring to an invalid key for adding properties. Such an exception is thrown when an operation
    984     * tries to add something to an attribute.
    985     *
    986     * @param key the invalid key causing this exception
    987     * @return the exception
    988     */
    989    private static IllegalArgumentException attributeKeyException(final String key) {
    990        return new IllegalArgumentException("New nodes cannot be added to an attribute key: " + key);
    991    }
    992
    993    /**
    994     * An interface used internally for handling concurrent updates. An implementation has to populate the passed in
    995     * {@code ModelTransaction}. The transaction is then executed, and an atomic update of the model's {@code TreeData} is
    996     * attempted. If this fails - because another update came across -, the whole operation has to be tried anew.
    997     */
    998    private interface TransactionInitializer {
    999        /**
    1000         * Initializes the specified transaction for an update operation. The return value indicates whether the transaction
    1001         * should be executed. A result of <b>false</b> means that the update is to be aborted (maybe another update method was
    1002         * called).
    1003         *
    1004         * @param tx the transaction to be initialized
    1005         * @return a flag whether the update should continue
    1006         */
    1007        boolean initTransaction(ModelTransaction tx);
    1008    }
    1009}