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