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