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