data/yang-data-tree-spi/src/main/java/org/opendaylight/yangtools/yang/data/tree/spi/DataTreeCandidates.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.data.tree.spi;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verifyNotNull;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.annotations.Beta;
  15 import java.util.ArrayList;
  16 import java.util.Iterator;
  17 import java.util.List;
  18 import org.eclipse.jdt.annotation.NonNull;
  19 import org.eclipse.jdt.annotation.Nullable;
  20 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  21 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  22 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  23 import org.opendaylight.yangtools.yang.data.tree.api.CursorAwareDataTreeModification;
  24 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeCandidate;
  25 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeCandidateNode;
  26 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeModification;
  27 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeModificationCursor;
  28 import org.opendaylight.yangtools.yang.data.tree.api.ModificationType;
  29 import org.slf4j.Logger;
  30 import org.slf4j.LoggerFactory;
  31
  32 /**
  33  * Utility class holding methods useful when dealing with {@link DataTreeCandidate} instances.
  34  */
  35 @Beta
  36 public final class DataTreeCandidates {
  37     private static final Logger LOG = LoggerFactory.getLogger(DataTreeCandidates.class);
  38
  39     private DataTreeCandidates() {
  40         // Hidden on purpose
  41     }
  42
  43     public static @NonNull DataTreeCandidate newDataTreeCandidate(final YangInstanceIdentifier rootPath,
  44                                                                   final DataTreeCandidateNode rootNode) {
  45         return new DefaultDataTreeCandidate(rootPath, rootNode);
  46     }
  47
  48     public static @NonNull DataTreeCandidate fromNormalizedNode(final YangInstanceIdentifier rootPath,
  49                                                                 final NormalizedNode node) {
  50         return new DefaultDataTreeCandidate(rootPath, new NormalizedNodeDataTreeCandidateNode(node));
  51     }
  52
  53     public static void applyToCursor(final DataTreeModificationCursor cursor, final DataTreeCandidate candidate) {
  54         DataTreeCandidateNodes.applyToCursor(cursor, candidate.getRootNode());
  55     }
  56
  57     public static void applyToModification(final DataTreeModification modification, final DataTreeCandidate candidate) {
  58         if (modification instanceof CursorAwareDataTreeModification) {
  59             applyToCursorAwareModification((CursorAwareDataTreeModification) modification, candidate);
  60             return;
  61         }
  62
  63         final DataTreeCandidateNode node = candidate.getRootNode();
  64         final YangInstanceIdentifier path = candidate.getRootPath();
  65         switch (node.modificationType()) {
  66             case DELETE:
  67                 modification.delete(path);
  68                 LOG.debug("Modification {} deleted path {}", modification, path);
  69                 break;
  70             case SUBTREE_MODIFIED:
  71                 LOG.debug("Modification {} modified path {}", modification, path);
  72
  73                 NodeIterator iterator = new NodeIterator(null, path, node.childNodes().iterator());
  74                 do {
  75                     iterator = iterator.next(modification);
  76                 } while (iterator != null);
  77                 break;
  78             case UNMODIFIED:
  79                 LOG.debug("Modification {} unmodified path {}", modification, path);
  80                 // No-op
  81                 break;
  82             case WRITE:
  83                 modification.write(path, verifyNotNull(node.dataAfter()));
  84                 LOG.debug("Modification {} written path {}", modification, path);
  85                 break;
  86             default:
  87                 throw new IllegalArgumentException("Unsupported modification " + node.modificationType());
  88         }
  89     }
  90
  91     /**
  92      * Compress a list of DataTreeCandidates into a single DataTreeCandidate. The resulting candidate is a summarization
  93      * of changes recorded in the input candidates.
  94      *
  95      * @param candidates Input list, must be non-empty
  96      * @return Summarized DataTreeCandidate
  97      * @throws IllegalArgumentException if candidates is empty, or contains candidates with mismatched root path
  98      * @throws NullPointerException     if {@code candidates} is null or contains a null entry
  99      */
 100     public static @NonNull DataTreeCandidate aggregate(@NonNull final List<? extends DataTreeCandidate> candidates) {
 101         final Iterator<? extends DataTreeCandidate> it = candidates.iterator();
 102         checkArgument(it.hasNext(), "Input must not be empty");
 103         final DataTreeCandidate first = requireNonNull(it.next(), "Input must not contain null entries");
 104         if (!it.hasNext()) {
 105             // Short-circuit
 106             return first;
 107         }
 108         final YangInstanceIdentifier rootPath = first.getRootPath();
 109         final List<DataTreeCandidateNode> roots = new ArrayList<>(candidates.size());
 110         roots.add(first.getRootNode());
 111         it.forEachRemaining(candidate -> {
 112             final YangInstanceIdentifier root = candidate.getRootPath();
 113             checkArgument(rootPath.equals(root), "Expecting root path %s, encountered %s", rootPath, root);
 114             roots.add(candidate.getRootNode());
 115         });
 116         return DataTreeCandidates.newDataTreeCandidate(rootPath, fastCompressNode(roots.get(0), roots));
 117     }
 118
 119     private static DataTreeCandidateNode fastCompressNode(final DataTreeCandidateNode first,
 120                                                           final List<DataTreeCandidateNode> input) {
 121         final var last = input.get(input.size() - 1);
 122         final var nodeModification = last.modificationType();
 123         final var dataBefore = first.dataBefore();
 124         final var dataAfter = last.dataAfter();
 125         switch (nodeModification) {
 126             case DELETE:
 127                 ModificationType previous = first.modificationType();
 128                 // Check if node had data before
 129                 if (previous == ModificationType.DELETE || previous == ModificationType.DISAPPEARED
 130                     || previous == ModificationType.UNMODIFIED && dataBefore == null) {
 131                     illegalModification(ModificationType.DELETE, ModificationType.DELETE);
 132                 }
 133                 if (dataBefore == null) {
 134                     return new TerminalDataTreeCandidateNode(null, ModificationType.UNMODIFIED, null, null);
 135                 }
 136                 return new TerminalDataTreeCandidateNode(null, nodeModification, verifyNotNull(dataBefore), null);
 137             case WRITE:
 138                 return new TerminalDataTreeCandidateNode(null, nodeModification, dataBefore, verifyNotNull(dataAfter));
 139             case APPEARED:
 140             case DISAPPEARED:
 141             case SUBTREE_MODIFIED:
 142             case UNMODIFIED:
 143                 // No luck, we need to iterate
 144                 return slowCompressNodes(first, input);
 145             default:
 146                 throw new IllegalStateException("Unsupported modification type " + nodeModification);
 147         }
 148     }
 149
 150     private static DataTreeCandidateNode slowCompressNodes(final DataTreeCandidateNode first,
 151                                                            final List<DataTreeCandidateNode> input) {
 152         // finalNode contains summarized changes
 153         TerminalDataTreeCandidateNode finalNode = new TerminalDataTreeCandidateNode(null, first.dataBefore());
 154         input.forEach(node -> compressNode(finalNode, node, null));
 155         finalNode.setAfter(input.get(input.size() - 1).dataAfter());
 156         return cleanUpTree(finalNode);
 157     }
 158
 159     private static void compressNode(final TerminalDataTreeCandidateNode finalNode, final DataTreeCandidateNode node,
 160                                      final PathArgument parent) {
 161         PathArgument identifier;
 162         try {
 163             identifier = node.name();
 164         } catch (IllegalStateException e) {
 165             identifier = null;
 166         }
 167         // Check if finalNode has stored any changes for node
 168         if (finalNode.getNode(identifier).isEmpty()) {
 169             TerminalDataTreeCandidateNode parentNode = finalNode.getNode(parent)
 170                     .orElseThrow(() -> new IllegalArgumentException("No node found for " + parent + " identifier"));
 171             TerminalDataTreeCandidateNode childNode = new TerminalDataTreeCandidateNode(
 172                     identifier,
 173                     node.dataBefore(),
 174                     parentNode);
 175             parentNode.addChildNode(childNode);
 176         }
 177
 178         ModificationType nodeModification = node.modificationType();
 179         switch (nodeModification) {
 180             case UNMODIFIED:
 181                 // If node is unmodified there is no need iterate through its child nodes
 182                 break;
 183             case WRITE:
 184             case DELETE:
 185             case APPEARED:
 186             case DISAPPEARED:
 187             case SUBTREE_MODIFIED:
 188                 finalNode.setModification(identifier,
 189                         compressModifications(finalNode.getModification(identifier), nodeModification,
 190                                 finalNode.dataAfter(identifier) == null));
 191                 finalNode.setData(identifier, node.dataAfter());
 192
 193                 for (DataTreeCandidateNode child : node.childNodes()) {
 194                     compressNode(finalNode, child, identifier);
 195                 }
 196                 break;
 197             default:
 198                 throw new IllegalStateException("Unsupported modification type " + nodeModification);
 199         }
 200     }
 201
 202     // Removes redundant changes
 203     private static DataTreeCandidateNode cleanUpTree(final TerminalDataTreeCandidateNode finalNode) {
 204         return cleanUpTree(finalNode, finalNode);
 205     }
 206
 207     // Compare data before and after in order to find modified nodes without actual changes
 208     private static DataTreeCandidateNode cleanUpTree(final TerminalDataTreeCandidateNode finalNode,
 209                                                      final TerminalDataTreeCandidateNode node) {
 210         final var identifier = node.name();
 211         final var nodeModification = node.modificationType();
 212         final var childNodes = node.childNodes();
 213         for (var childNode : childNodes) {
 214             cleanUpTree(finalNode, (TerminalDataTreeCandidateNode) childNode);
 215         }
 216         final var dataBefore = finalNode.dataBefore(identifier);
 217
 218         switch (nodeModification) {
 219             case UNMODIFIED:
 220                 finalNode.deleteNode(identifier);
 221                 return finalNode;
 222             case WRITE:
 223                 return finalNode;
 224             case DELETE:
 225                 if (dataBefore == null) {
 226                     finalNode.deleteNode(identifier);
 227                 }
 228                 return finalNode;
 229             case APPEARED:
 230                 if (dataBefore != null) {
 231                     illegalModification(ModificationType.APPEARED, ModificationType.WRITE);
 232                 }
 233                 if (childNodes.isEmpty()) {
 234                     finalNode.deleteNode(identifier);
 235                 }
 236                 return finalNode;
 237             case DISAPPEARED:
 238                 if (dataBefore == null || childNodes.isEmpty()) {
 239                     finalNode.deleteNode(identifier);
 240                 }
 241                 return finalNode;
 242             case SUBTREE_MODIFIED:
 243                 if (dataBefore == null) {
 244                     illegalModification(ModificationType.SUBTREE_MODIFIED, ModificationType.DELETE);
 245                 }
 246                 if (childNodes.isEmpty()) {
 247                     finalNode.deleteNode(identifier);
 248                 }
 249                 return finalNode;
 250             default:
 251                 throw new IllegalStateException("Unsupported modification type " + nodeModification);
 252         }
 253     }
 254
 255     private static ModificationType compressModifications(final ModificationType firstModification,
 256                                                           final ModificationType secondModification,
 257                                                           final boolean hasNoDataBefore) {
 258         switch (firstModification) {
 259             case UNMODIFIED:
 260                 if (hasNoDataBefore) {
 261                     return switch (secondModification) {
 262                         case UNMODIFIED, WRITE, APPEARED -> secondModification;
 263                         case DELETE -> illegalModification(ModificationType.DELETE, ModificationType.DELETE);
 264                         case SUBTREE_MODIFIED ->
 265                             illegalModification(ModificationType.SUBTREE_MODIFIED, ModificationType.DELETE);
 266                         case DISAPPEARED -> illegalModification(ModificationType.DISAPPEARED, ModificationType.DELETE);
 267                     };
 268                 }
 269                 if (secondModification == ModificationType.APPEARED) {
 270                     return illegalModification(ModificationType.APPEARED, ModificationType.WRITE);
 271                 }
 272                 return secondModification;
 273             case WRITE:
 274                 return switch (secondModification) {
 275                     case UNMODIFIED, WRITE, SUBTREE_MODIFIED -> ModificationType.WRITE;
 276                     case DELETE -> ModificationType.DELETE;
 277                     case DISAPPEARED -> ModificationType.DISAPPEARED;
 278                     case APPEARED -> illegalModification(ModificationType.APPEARED, firstModification);
 279                 };
 280             case DELETE:
 281                 return switch (secondModification) {
 282                     case UNMODIFIED -> ModificationType.DELETE;
 283                     case WRITE, APPEARED -> ModificationType.WRITE;
 284                     case DELETE -> illegalModification(ModificationType.DELETE, firstModification);
 285                     case DISAPPEARED -> illegalModification(ModificationType.DISAPPEARED, firstModification);
 286                     case SUBTREE_MODIFIED -> illegalModification(ModificationType.SUBTREE_MODIFIED, firstModification);
 287                 };
 288             case APPEARED:
 289                 return switch (secondModification) {
 290                     case UNMODIFIED, SUBTREE_MODIFIED -> ModificationType.APPEARED;
 291                     case DELETE, DISAPPEARED -> ModificationType.UNMODIFIED;
 292                     case WRITE -> ModificationType.WRITE;
 293                     case APPEARED -> illegalModification(ModificationType.APPEARED, firstModification);
 294                 };
 295             case DISAPPEARED:
 296                 return switch (secondModification) {
 297                     case UNMODIFIED, WRITE -> secondModification;
 298                     case APPEARED -> ModificationType.SUBTREE_MODIFIED;
 299                     case DELETE -> illegalModification(ModificationType.DELETE, firstModification);
 300                     case DISAPPEARED -> illegalModification(ModificationType.DISAPPEARED, firstModification);
 301                     case SUBTREE_MODIFIED -> illegalModification(ModificationType.SUBTREE_MODIFIED, firstModification);
 302                 };
 303             case SUBTREE_MODIFIED:
 304                 return switch (secondModification) {
 305                     case UNMODIFIED, SUBTREE_MODIFIED -> ModificationType.SUBTREE_MODIFIED;
 306                     case WRITE, DELETE, DISAPPEARED -> secondModification;
 307                     case APPEARED -> illegalModification(ModificationType.APPEARED, firstModification);
 308                 };
 309             default:
 310                 throw new IllegalStateException("Unsupported modification type " + firstModification);
 311         }
 312     }
 313
 314     private static ModificationType illegalModification(final ModificationType first, final ModificationType second) {
 315         throw new IllegalArgumentException(first + " modification event on " + second + " node");
 316     }
 317
 318     private static void applyToCursorAwareModification(final CursorAwareDataTreeModification modification,
 319                                                        final DataTreeCandidate candidate) {
 320         final YangInstanceIdentifier candidatePath = candidate.getRootPath();
 321         final YangInstanceIdentifier parent = candidatePath.getParent();
 322         if (parent == null) {
 323             try (DataTreeModificationCursor cursor = modification.openCursor()) {
 324                 DataTreeCandidateNodes.applyRootToCursor(cursor, candidate.getRootNode());
 325             }
 326         } else {
 327             try (DataTreeModificationCursor cursor = modification.openCursor(parent).orElseThrow()) {
 328                 DataTreeCandidateNodes.applyRootedNodeToCursor(cursor, candidatePath, candidate.getRootNode());
 329             }
 330         }
 331     }
 332
 333     private static final class NodeIterator {
 334         private final Iterator<DataTreeCandidateNode> iterator;
 335         private final YangInstanceIdentifier path;
 336         private final NodeIterator parent;
 337
 338         NodeIterator(final @Nullable NodeIterator parent, final YangInstanceIdentifier path,
 339                      final Iterator<DataTreeCandidateNode> iterator) {
 340             this.iterator = requireNonNull(iterator);
 341             this.path = requireNonNull(path);
 342             this.parent = parent;
 343         }
 344
 345         NodeIterator next(final DataTreeModification modification) {
 346             while (iterator.hasNext()) {
 347                 final DataTreeCandidateNode node = iterator.next();
 348                 final YangInstanceIdentifier child = path.node(node.name());
 349
 350                 switch (node.modificationType()) {
 351                     case DELETE:
 352                         modification.delete(child);
 353                         LOG.debug("Modification {} deleted path {}", modification, child);
 354                         break;
 355                     case APPEARED:
 356                     case DISAPPEARED:
 357                     case SUBTREE_MODIFIED:
 358                         LOG.debug("Modification {} modified path {}", modification, child);
 359                         return new NodeIterator(this, child, node.childNodes().iterator());
 360                     case UNMODIFIED:
 361                         LOG.debug("Modification {} unmodified path {}", modification, child);
 362                         // No-op
 363                         break;
 364                     case WRITE:
 365                         modification.write(child, verifyNotNull(node.dataAfter()));
 366                         LOG.debug("Modification {} written path {}", modification, child);
 367                         break;
 368                     default:
 369                         throw new IllegalArgumentException("Unsupported modification " + node.modificationType());
 370                 }
 371             }
 372             return parent;
 373         }
 374     }
 375 }