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 cursorAware) {
  59             applyToCursorAwareModification(cursorAware, candidate);
  60             return;
  61         }
  62
  63         final var node = candidate.getRootNode();
  64         final var path = candidate.getRootPath();
  65         final var type = node.modificationType();
  66         switch (type) {
  67             case DELETE -> {
  68                 modification.delete(path);
  69                 LOG.debug("Modification {} deleted path {}", modification, path);
  70             }
  71             case SUBTREE_MODIFIED -> {
  72                 LOG.debug("Modification {} modified path {}", modification, path);
  73
  74                 var iterator = new NodeIterator(null, path, node.childNodes().iterator());
  75                 do {
  76                     iterator = iterator.next(modification);
  77                 } while (iterator != null);
  78             }
  79             case UNMODIFIED -> {
  80                 LOG.debug("Modification {} unmodified path {}", modification, path);
  81                 // No-op
  82             }
  83             case WRITE -> {
  84                 modification.write(path, verifyNotNull(node.dataAfter()));
  85                 LOG.debug("Modification {} written path {}", modification, path);
  86             }
  87             default -> throw new IllegalArgumentException("Unsupported modification " + type);
  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 var it = candidates.iterator();
 102         checkArgument(it.hasNext(), "Input must not be empty");
 103         final var first = requireNonNull(it.next(), "Input must not contain null entries");
 104         if (!it.hasNext()) {
 105             // Short-circuit
 106             return first;
 107         }
 108         final var rootPath = first.getRootPath();
 109         final var roots = new ArrayList<DataTreeCandidateNode>(candidates.size());
 110         roots.add(first.getRootNode());
 111         it.forEachRemaining(candidate -> {
 112             final var 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 dataBefore = first.dataBefore();
 123         final var dataAfter = last.dataAfter();
 124         final var type = last.modificationType();
 125
 126         return switch (type) {
 127             case DELETE -> {
 128                 final var previous = first.modificationType();
 129                 // Check if node had data before
 130                 if (previous == ModificationType.DELETE || previous == ModificationType.DISAPPEARED
 131                     || previous == ModificationType.UNMODIFIED && dataBefore == null) {
 132                     throw illegalModification(ModificationType.DELETE, ModificationType.DELETE);
 133                 }
 134
 135                 yield dataBefore != null ? new TerminalDataTreeCandidateNode(null, type, dataBefore, null)
 136                     : new TerminalDataTreeCandidateNode(null, ModificationType.UNMODIFIED, null, null);
 137             }
 138             case WRITE -> new TerminalDataTreeCandidateNode(null, type, dataBefore, verifyNotNull(dataAfter));
 139             case APPEARED, DISAPPEARED, SUBTREE_MODIFIED, UNMODIFIED ->
 140                 // No luck, we need to iterate
 141                 slowCompressNodes(first, input);
 142         };
 143     }
 144
 145     private static DataTreeCandidateNode slowCompressNodes(final DataTreeCandidateNode first,
 146             final List<DataTreeCandidateNode> input) {
 147         // finalNode contains summarized changes
 148         final var finalNode = new TerminalDataTreeCandidateNode(null, first.dataBefore());
 149         input.forEach(node -> compressNode(finalNode, node, null));
 150         finalNode.setAfter(input.get(input.size() - 1).dataAfter());
 151         return cleanUpTree(finalNode);
 152     }
 153
 154     private static void compressNode(final TerminalDataTreeCandidateNode finalNode, final DataTreeCandidateNode node,
 155             final PathArgument parent) {
 156         PathArgument identifier;
 157         try {
 158             identifier = node.name();
 159         } catch (IllegalStateException e) {
 160             identifier = null;
 161         }
 162         // Check if finalNode has stored any changes for node
 163         if (finalNode.getNode(identifier).isEmpty()) {
 164             final var parentNode = finalNode.getNode(parent)
 165                 .orElseThrow(() -> new IllegalArgumentException("No node found for " + parent + " identifier"));
 166             parentNode.addChildNode(new TerminalDataTreeCandidateNode(identifier, node.dataBefore(), parentNode));
 167         }
 168
 169         final var nodeModification = node.modificationType();
 170         switch (nodeModification) {
 171             case UNMODIFIED -> {
 172                 // If node is unmodified there is no need iterate through its child nodes
 173             }
 174             case APPEARED, DELETE, DISAPPEARED, SUBTREE_MODIFIED, WRITE -> {
 175                 finalNode.setModification(identifier, compressModifications(finalNode.getModification(identifier),
 176                     nodeModification, finalNode.dataAfter(identifier) == null));
 177                 finalNode.setData(identifier, node.dataAfter());
 178
 179                 for (var child : node.childNodes()) {
 180                     compressNode(finalNode, child, identifier);
 181                 }
 182             }
 183             default -> throw new IllegalStateException("Unsupported modification type " + nodeModification);
 184         }
 185     }
 186
 187     // Removes redundant changes
 188     private static DataTreeCandidateNode cleanUpTree(final TerminalDataTreeCandidateNode finalNode) {
 189         return cleanUpTree(finalNode, finalNode);
 190     }
 191
 192     // Compare data before and after in order to find modified nodes without actual changes
 193     private static DataTreeCandidateNode cleanUpTree(final TerminalDataTreeCandidateNode finalNode,
 194             final TerminalDataTreeCandidateNode node) {
 195         final var identifier = node.name();
 196         final var childNodes = node.childNodes();
 197         for (var childNode : childNodes) {
 198             cleanUpTree(finalNode, (TerminalDataTreeCandidateNode) childNode);
 199         }
 200         final var dataBefore = finalNode.dataBefore(identifier);
 201
 202         switch (node.modificationType()) {
 203             // XXX: Forces JEP-441 exhaustiveness. Revisit when a better option comes along.
 204             case null -> throw new NullPointerException("null modificationType");
 205             case UNMODIFIED -> finalNode.deleteNode(identifier);
 206             case WRITE -> {
 207                 // No-op
 208             }
 209             case DELETE -> {
 210                 if (dataBefore == null) {
 211                     finalNode.deleteNode(identifier);
 212                 }
 213             }
 214             case APPEARED -> {
 215                 if (dataBefore != null) {
 216                     throw illegalModification(ModificationType.APPEARED, ModificationType.WRITE);
 217                 }
 218                 if (childNodes.isEmpty()) {
 219                     finalNode.deleteNode(identifier);
 220                 }
 221             }
 222             case DISAPPEARED -> {
 223                 if (dataBefore == null || childNodes.isEmpty()) {
 224                     finalNode.deleteNode(identifier);
 225                 }
 226             }
 227             case SUBTREE_MODIFIED -> {
 228                 if (dataBefore == null) {
 229                     throw illegalModification(ModificationType.SUBTREE_MODIFIED, ModificationType.DELETE);
 230                 }
 231                 if (childNodes.isEmpty()) {
 232                     finalNode.deleteNode(identifier);
 233                 }
 234             }
 235         }
 236
 237         return finalNode;
 238     }
 239
 240     private static ModificationType compressModifications(final ModificationType first, final ModificationType second,
 241             final boolean hasNoDataBefore) {
 242         return switch (first) {
 243             case UNMODIFIED -> {
 244                 if (hasNoDataBefore) {
 245                     yield switch (second) {
 246                             case UNMODIFIED, WRITE, APPEARED -> second;
 247                             case DELETE, DISAPPEARED, SUBTREE_MODIFIED ->
 248                                 throw illegalModification(second, ModificationType.DELETE);
 249                         };
 250                 }
 251                 if (second == ModificationType.APPEARED) {
 252                     throw illegalModification(ModificationType.APPEARED, ModificationType.WRITE);
 253                 }
 254                 yield second;
 255             }
 256             case WRITE -> switch (second) {
 257                 case UNMODIFIED, WRITE, SUBTREE_MODIFIED -> ModificationType.WRITE;
 258                 case DELETE -> ModificationType.DELETE;
 259                 case DISAPPEARED -> ModificationType.DISAPPEARED;
 260                 case APPEARED -> throw illegalModification(ModificationType.APPEARED, first);
 261             };
 262             case DELETE -> switch (second) {
 263                 case UNMODIFIED -> ModificationType.DELETE;
 264                 case WRITE, APPEARED -> ModificationType.WRITE;
 265                 case DELETE, DISAPPEARED, SUBTREE_MODIFIED -> throw illegalModification(second, first);
 266             };
 267             case APPEARED -> switch (second) {
 268                 case UNMODIFIED, SUBTREE_MODIFIED -> ModificationType.APPEARED;
 269                 case DELETE, DISAPPEARED -> ModificationType.UNMODIFIED;
 270                 case WRITE -> ModificationType.WRITE;
 271                 case APPEARED -> throw illegalModification(ModificationType.APPEARED, first);
 272             };
 273             case DISAPPEARED -> switch (second) {
 274                 case UNMODIFIED, WRITE -> second;
 275                 case APPEARED -> ModificationType.SUBTREE_MODIFIED;
 276                 case DELETE, DISAPPEARED, SUBTREE_MODIFIED -> throw illegalModification(second, first);
 277             };
 278             case SUBTREE_MODIFIED -> switch (second) {
 279                 case UNMODIFIED, SUBTREE_MODIFIED -> ModificationType.SUBTREE_MODIFIED;
 280                 case WRITE, DELETE, DISAPPEARED -> second;
 281                 case APPEARED -> throw illegalModification(ModificationType.APPEARED, first);
 282             };
 283         };
 284     }
 285
 286     private static IllegalArgumentException illegalModification(final ModificationType first,
 287             final ModificationType second) {
 288         return new IllegalArgumentException(first + " modification event on " + second + " node");
 289     }
 290
 291     private static void applyToCursorAwareModification(final CursorAwareDataTreeModification modification,
 292                                                        final DataTreeCandidate candidate) {
 293         final var candidatePath = candidate.getRootPath();
 294         final var parent = candidatePath.getParent();
 295         if (parent == null) {
 296             try (var cursor = modification.openCursor()) {
 297                 DataTreeCandidateNodes.applyRootToCursor(cursor, candidate.getRootNode());
 298             }
 299         } else {
 300             try (var cursor = modification.openCursor(parent).orElseThrow()) {
 301                 DataTreeCandidateNodes.applyRootedNodeToCursor(cursor, candidatePath, candidate.getRootNode());
 302             }
 303         }
 304     }
 305
 306     private static final class NodeIterator {
 307         private final Iterator<DataTreeCandidateNode> iterator;
 308         private final YangInstanceIdentifier path;
 309         private final NodeIterator parent;
 310
 311         NodeIterator(final @Nullable NodeIterator parent, final YangInstanceIdentifier path,
 312                      final Iterator<DataTreeCandidateNode> iterator) {
 313             this.iterator = requireNonNull(iterator);
 314             this.path = requireNonNull(path);
 315             this.parent = parent;
 316         }
 317
 318         NodeIterator next(final DataTreeModification modification) {
 319             while (iterator.hasNext()) {
 320                 final var node = iterator.next();
 321                 final var child = path.node(node.name());
 322                 switch (node.modificationType()) {
 323                     // XXX: Forces JEP-441 exhaustiveness. Revisit when a better option comes along.
 324                     case null -> throw new NullPointerException("null modificationType");
 325                     case DELETE -> {
 326                         modification.delete(child);
 327                         LOG.debug("Modification {} deleted path {}", modification, child);
 328                     }
 329                     case APPEARED, DISAPPEARED, SUBTREE_MODIFIED -> {
 330                         LOG.debug("Modification {} modified path {}", modification, child);
 331                         return new NodeIterator(this, child, node.childNodes().iterator());
 332                     }
 333                     case UNMODIFIED -> {
 334                         // No-op
 335                         LOG.debug("Modification {} unmodified path {}", modification, child);
 336                     }
 337                     case WRITE -> {
 338                         modification.write(child, verifyNotNull(node.dataAfter()));
 339                         LOG.debug("Modification {} written path {}", modification, child);
 340                     }
 341                 }
 342             }
 343             return parent;
 344         }
 345     }
 346 }