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