infra/data-impl/src/main/java/io/fd/honeycomb/data/impl/ModificationDiff.java

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package io.fd.honeycomb.data.impl;
  18
  19 import static com.google.common.base.Preconditions.checkArgument;
  20 import static com.google.common.base.Preconditions.checkNotNull;
  21 import static org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType.APPEARED;
  22 import static org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType.DELETE;
  23 import static org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType.DISAPPEARED;
  24 import static org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType.WRITE;
  25
  26 import com.google.common.collect.ImmutableMap;
  27 import java.util.Collection;
  28 import java.util.Collections;
  29 import java.util.EnumSet;
  30 import java.util.HashMap;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Optional;
  34 import java.util.stream.Collectors;
  35 import java.util.stream.Stream;
  36 import javax.annotation.Nonnull;
  37 import javax.annotation.Nullable;
  38 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  39 import org.opendaylight.yangtools.yang.data.api.schema.MixinNode;
  40 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  41 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidateNode;
  42 import org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType;
  43 import org.opendaylight.yangtools.yang.model.api.AugmentationSchema;
  44 import org.opendaylight.yangtools.yang.model.api.AugmentationTarget;
  45 import org.opendaylight.yangtools.yang.model.api.ChoiceSchemaNode;
  46 import org.opendaylight.yangtools.yang.model.api.ContainerSchemaNode;
  47 import org.opendaylight.yangtools.yang.model.api.DataNodeContainer;
  48 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  49 import org.opendaylight.yangtools.yang.model.api.LeafListSchemaNode;
  50 import org.opendaylight.yangtools.yang.model.api.LeafSchemaNode;
  51 import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
  52 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  53 import org.opendaylight.yangtools.yang.model.api.SchemaNode;
  54 import org.slf4j.Logger;
  55 import org.slf4j.LoggerFactory;
  56
  57 /**
  58  * Recursively collects and provides all unique and non-null modifications (modified normalized nodes).
  59  */
  60 final class ModificationDiff {
  61
  62     private static final Logger LOG = LoggerFactory.getLogger(ModificationDiff.class);
  63
  64     private static final ModificationDiff EMPTY_DIFF = new ModificationDiff(Collections.emptyMap());
  65     private static final EnumSet VALID_MODIFICATIONS = EnumSet.of(WRITE, DELETE);
  66     private static final EnumSet IGNORED_MODIFICATIONS = EnumSet.of(APPEARED, DISAPPEARED);
  67
  68     private final Map<YangInstanceIdentifier, NormalizedNodeUpdate> updates;
  69
  70     private ModificationDiff(@Nonnull Map<YangInstanceIdentifier, NormalizedNodeUpdate> updates) {
  71         this.updates = updates;
  72     }
  73
  74     /**
  75      * Get processed modifications.
  76      *
  77      * @return mapped modifications, where key is keyed {@link YangInstanceIdentifier}.
  78      */
  79     Map<YangInstanceIdentifier, NormalizedNodeUpdate> getUpdates() {
  80         return updates;
  81     }
  82
  83     private ModificationDiff merge(final ModificationDiff other) {
  84         if (this == EMPTY_DIFF) {
  85             return other;
  86         }
  87
  88         if (other == EMPTY_DIFF) {
  89             return this;
  90         }
  91
  92         return new ModificationDiff(join(updates, other.updates));
  93     }
  94
  95     private static Map<YangInstanceIdentifier, NormalizedNodeUpdate> join(
  96             Map<YangInstanceIdentifier, NormalizedNodeUpdate> first,
  97             Map<YangInstanceIdentifier, NormalizedNodeUpdate> second) {
  98         final Map<YangInstanceIdentifier, NormalizedNodeUpdate> merged = new HashMap<>();
  99         merged.putAll(first);
 100         merged.putAll(second);
 101         return merged;
 102     }
 103
 104     private static ModificationDiff create(Modification modification) {
 105         return new ModificationDiff(ImmutableMap.of(modification.getId(), NormalizedNodeUpdate.create(modification)));
 106     }
 107
 108     /**
 109      * Produce an aggregated diff from a candidate node recursively. MixinNodes are ignored as modifications and so
 110      * are complex nodes which direct leaves were not modified.
 111      */
 112     @Nonnull
 113     static ModificationDiff recursivelyFromCandidate(@Nonnull final Modification modification) {
 114         // recursively process child nodes for exact modifications
 115         return recursivelyChildrenFromCandidate(modification)
 116                 // also add modification on current level, if elligible
 117                 .merge(isModification(modification)
 118                         ? ModificationDiff.create(modification)
 119                         : EMPTY_DIFF);
 120     }
 121
 122     /**
 123      * Same as {@link #recursivelyFromCandidate(Modification)} but does
 124      * not process the root node for modifications, since it's the artificial data root, that has no child leaves but
 125      * always is marked as SUBTREE_MODIFIED.
 126      */
 127     @Nonnull
 128     static ModificationDiff recursivelyFromCandidateRoot(@Nonnull final DataTreeCandidateNode currentCandidate,
 129                                                          @Nonnull final SchemaContext ctx) {
 130         return recursivelyChildrenFromCandidate(new Modification(YangInstanceIdentifier.EMPTY, currentCandidate, ctx));
 131     }
 132
 133     /**
 134      * Check whether current node was modified. {@link MixinNode}s are ignored
 135      * and only nodes which direct leaves(or choices) are modified are considered a modification.
 136      */
 137     private static Boolean isModification(@Nonnull final Modification modification) {
 138         // Disappear is not a modification
 139         if (IGNORED_MODIFICATIONS.contains(modification.getModificationType())) {
 140             return false;
 141         // Mixin nodes are not considered modifications
 142         } else if (modification.isMixin() && !modification.is(AugmentationSchema.class)) {
 143             return false;
 144         } else {
 145             return isCurrentModified(modification);
 146         }
 147     }
 148
 149     private static Boolean isCurrentModified(@Nonnull final Modification modification) {
 150         // First check if it's an empty presence node
 151         final boolean emptyPresenceNode = isEmptyPresenceNode(modification);
 152
 153         // Check if there are any modified leaves and if so, consider current node as modified
 154         final Boolean directLeavesModified = emptyPresenceNode
 155                 || modification.streamChildren()
 156                 // Checking leaf or leaf-lists children for direct modification, which means that leafs of leaf lists
 157                 // trigger a modification on parent node
 158                 .filter(child -> child.is(LeafSchemaNode.class) || child.is(LeafListSchemaNode.class))
 159                 // For some reason, we get modifications on unmodified list keys
 160                 // and that messes up our modifications collection here, so we need to skip
 161                 .filter(Modification::isBeforeAndAfterDifferent)
 162                 .filter(child -> VALID_MODIFICATIONS.contains(child.getModificationType()))
 163                 .findFirst()
 164                 .isPresent();
 165
 166         // Also as fallback check choices (choices do not exist in BA world and if anything within a choice was modified,
 167         // consider its parent as being modified)
 168         final boolean modified = directLeavesModified
 169                 || modification.streamChildren()
 170                 .filter(child -> child.is(ChoiceSchemaNode.class))
 171                 // Recursively check each choice if there was any change to it
 172                 .filter(ModificationDiff::isCurrentModified)
 173                 .findFirst()
 174                 .isPresent();
 175
 176         if (modified) {
 177             LOG.debug("Modification detected as {} at {}",
 178                     modification.getModificationType(), modification.getId());
 179         }
 180
 181         return modified;
 182     }
 183
 184     /**
 185      * Check if new data are empty but still to be considered as a modification, meaning it's presence has a meaning
 186      * e.g. containers with presence statement.
 187      */
 188     private static boolean isEmptyPresenceNode(@Nonnull final Modification modification) {
 189         return modification.is(ContainerSchemaNode.class)
 190                 && ((ContainerSchemaNode) modification.getSchemaNode()).isPresenceContainer()
 191                 && modification.getChildNodes().isEmpty()
 192                 && VALID_MODIFICATIONS.contains(modification.getModificationType());
 193     }
 194
 195     /**
 196      * Process all non-leaf child nodes recursively, creating aggregated {@link ModificationDiff}.
 197      */
 198     private static ModificationDiff recursivelyChildrenFromCandidate(@Nonnull final Modification modification) {
 199         // recursively process child nodes for specific modifications
 200         return modification.streamChildren()
 201                 .filter(child -> !child.is(LeafSchemaNode.class))
 202                 .map(ModificationDiff::recursivelyFromCandidate)
 203                 .reduce(ModificationDiff::merge)
 204                 .orElse(EMPTY_DIFF);
 205     }
 206
 207     @Override
 208     public String toString() {
 209         return "ModificationDiff{updates=" + updates + '}';
 210     }
 211
 212     /**
 213      * Update to a normalized node identifiable by its {@link YangInstanceIdentifier}.
 214      */
 215     static final class NormalizedNodeUpdate {
 216
 217         @Nonnull
 218         private final YangInstanceIdentifier id;
 219         @Nullable
 220         private final NormalizedNode<?, ?> dataBefore;
 221         @Nullable
 222         private final NormalizedNode<?, ?> dataAfter;
 223
 224         private NormalizedNodeUpdate(@Nonnull final YangInstanceIdentifier id,
 225                                      @Nullable final NormalizedNode<?, ?> dataBefore,
 226                                      @Nullable final NormalizedNode<?, ?> dataAfter) {
 227             this.id = checkNotNull(id);
 228             this.dataAfter = dataAfter;
 229             this.dataBefore = dataBefore;
 230         }
 231
 232         @Nullable
 233         public NormalizedNode<?, ?> getDataBefore() {
 234             return dataBefore;
 235         }
 236
 237         @Nullable
 238         public NormalizedNode<?, ?> getDataAfter() {
 239             return dataAfter;
 240         }
 241
 242         @Nonnull
 243         public YangInstanceIdentifier getId() {
 244             return id;
 245         }
 246
 247         static NormalizedNodeUpdate create(@Nonnull final Modification modification) {
 248             final com.google.common.base.Optional<NormalizedNode<?, ?>> beforeData =
 249                     modification.getDataBefore();
 250             final com.google.common.base.Optional<NormalizedNode<?, ?>> afterData =
 251                     modification.getDataAfter();
 252             checkArgument(beforeData.isPresent() || afterData.isPresent(),
 253                     "Both before and after data are null for %s", modification.getId());
 254             return NormalizedNodeUpdate.create(modification.getId(), beforeData.orNull(), afterData.orNull());
 255         }
 256
 257         static NormalizedNodeUpdate create(@Nonnull final YangInstanceIdentifier id,
 258                                            @Nullable final NormalizedNode<?, ?> dataBefore,
 259                                            @Nullable final NormalizedNode<?, ?> dataAfter) {
 260             return new NormalizedNodeUpdate(id, dataBefore, dataAfter);
 261         }
 262
 263         @Override
 264         public boolean equals(final Object other) {
 265             if (this == other) {
 266                 return true;
 267             }
 268             if (other == null || getClass() != other.getClass()) {
 269                 return false;
 270             }
 271
 272             final NormalizedNodeUpdate that = (NormalizedNodeUpdate) other;
 273
 274             return id.equals(that.id);
 275
 276         }
 277
 278         @Override
 279         public int hashCode() {
 280             return id.hashCode();
 281         }
 282
 283         @Override
 284         public String toString() {
 285             return "NormalizedNodeUpdate{" + "id=" + id
 286                     + ", dataBefore=" + dataBefore
 287                     + ", dataAfter=" + dataAfter
 288                     + '}';
 289         }
 290     }
 291
 292     /**
 293      * Intermediate representation of a modification + its schema.
 294      */
 295     private static final class Modification {
 296         private final YangInstanceIdentifier id;
 297         private final DataTreeCandidateNode dataCandidate;
 298         // Using Object as type for schema node since it's the only type that's a parent to all schema node types from
 299         // yangtools. The hierarchy does not use e.g. SchemaNode class for all types
 300         private final Object parentNode;
 301         private final Object schemaNode;
 302
 303         Modification(final YangInstanceIdentifier id,
 304                      final DataTreeCandidateNode dataCandidate,
 305                      final Object parentNode,
 306                      final Object schemaNode) {
 307             this.id = id;
 308             this.dataCandidate = dataCandidate;
 309             this.parentNode = parentNode;
 310             this.schemaNode = schemaNode;
 311         }
 312
 313         Modification(final YangInstanceIdentifier id,
 314                      final DataTreeCandidateNode dataCandidate,
 315                      final Object schemaNode) {
 316             this(id, dataCandidate, schemaNode, schemaNode);
 317         }
 318
 319         List<Modification> getChildNodes() {
 320             return streamChildren().collect(Collectors.toList());
 321         }
 322
 323         YangInstanceIdentifier getId() {
 324             return id;
 325         }
 326
 327         ModificationType getModificationType() {
 328             return dataCandidate.getModificationType();
 329         }
 330
 331         com.google.common.base.Optional<NormalizedNode<?, ?>> getDataBefore() {
 332             return dataCandidate.getDataBefore();
 333         }
 334
 335         com.google.common.base.Optional<NormalizedNode<?, ?>> getDataAfter() {
 336             return dataCandidate.getDataAfter();
 337         }
 338
 339         Object getSchemaNode() {
 340             return schemaNode;
 341         }
 342
 343         boolean is(final Class<?> schemaType) {
 344             return schemaType.isAssignableFrom(schemaNode.getClass());
 345         }
 346
 347         boolean isMixin() {
 348             // Checking whether node is a mixin is not performed on schema, but on data since mixin is
 349             // only a NormalizedNode concept, not a schema concept
 350             return dataCandidate.getDataBefore().orNull() instanceof MixinNode ||
 351                     dataCandidate.getDataAfter().orNull() instanceof MixinNode;
 352         }
 353
 354         private boolean isBeforeAndAfterDifferent() {
 355             if (dataCandidate.getDataBefore().isPresent()) {
 356                 return !dataCandidate.getDataBefore().get().equals(dataCandidate.getDataAfter().orNull());
 357             }
 358
 359             // considering not a modification if data after is also null
 360             return dataCandidate.getDataAfter().isPresent();
 361         }
 362
 363         private AugmentationSchema findAugmentation(Object currentNode,
 364                                                     final YangInstanceIdentifier.AugmentationIdentifier identifier) {
 365             if (currentNode != null) {
 366                 // check if identifier points to some augmentation of currentNode
 367                 if (currentNode instanceof AugmentationTarget) {
 368                     Optional<AugmentationSchema> augmentationSchema =
 369                         ((AugmentationTarget) currentNode).getAvailableAugmentations().stream()
 370                             .filter(aug -> identifier.equals(new YangInstanceIdentifier.AugmentationIdentifier(
 371                                 aug.getChildNodes().stream()
 372                                     .map(SchemaNode::getQName)
 373                                     .collect(Collectors.toSet()))))
 374                             .findFirst();
 375                     if (augmentationSchema.isPresent()) {
 376                         return augmentationSchema.get();
 377                     }
 378                 }
 379
 380                 // continue search:
 381                 Collection<DataSchemaNode> childNodes = Collections.emptyList();
 382                 if (currentNode instanceof DataNodeContainer) {
 383                     childNodes = ((DataNodeContainer) currentNode).getChildNodes();
 384                 } else if (currentNode instanceof ChoiceSchemaNode) {
 385                     childNodes = ((ChoiceSchemaNode) currentNode).getCases().stream()
 386                         .flatMap(cas -> cas.getChildNodes().stream()).collect(Collectors.toList());
 387                 }
 388                 return childNodes.stream().map(n -> findAugmentation(n, identifier)).filter(n -> n != null).findFirst()
 389                     .orElse(null);
 390             } else {
 391                 return null;
 392             }
 393         }
 394
 395         Stream<Modification> streamChildren() {
 396             return dataCandidate.getChildNodes().stream()
 397                 .map(child -> {
 398                     final YangInstanceIdentifier childId = id.node(child.getIdentifier());
 399                     final Object schemaChild = schemaChild(schemaNode, child.getIdentifier());
 400                     // An augment cannot change other augment, so we do not update parent node if we are streaming
 401                     // children of AugmentationSchema (otherwise we would fail to find schema for nested augmentations):
 402                     final Object newParent = (schemaNode instanceof AugmentationSchema)
 403                         ? parentNode
 404                         : schemaNode;
 405                     return new Modification(childId, child, newParent, schemaChild);
 406                 });
 407         }
 408
 409         /**
 410          * Find next schema node in hierarchy.
 411          */
 412         private Object schemaChild(final Object schemaNode, final YangInstanceIdentifier.PathArgument identifier) {
 413             Object found = null;
 414
 415             if (identifier instanceof YangInstanceIdentifier.AugmentationIdentifier) {
 416                 if (schemaNode instanceof AugmentationTarget) {
 417                     // Find matching augmentation
 418                     found = ((AugmentationTarget) schemaNode).getAvailableAugmentations().stream()
 419                         .filter(aug -> identifier.equals(new YangInstanceIdentifier.AugmentationIdentifier(
 420                             aug.getChildNodes().stream()
 421                                 .map(SchemaNode::getQName)
 422                                 .collect(Collectors.toSet()))))
 423                         .findFirst()
 424                         .orElse(null);
 425
 426                     if (found == null) {
 427                         // An augment cannot change other augment, but all augments only change their targets (data nodes).
 428                         //
 429                         // As a consequence, if nested augmentations are present,
 430                         // AugmentationSchema might reference child schema node instances that do not include changes
 431                         // from nested augments.
 432                         //
 433                         // But schemaNode, as mentioned earlier, contains all the changes introduced by augments.
 434                         //
 435                         // On the other hand, in case of augments which introduce leaves,
 436                         // we need to address AugmentationSchema node directly so we can't simply do
 437                         // found = schemaNode;
 438                         //
 439                         found =
 440                             findAugmentation(parentNode, (YangInstanceIdentifier.AugmentationIdentifier) identifier);
 441                     }
 442                 }
 443             } else if (schemaNode instanceof DataNodeContainer) {
 444                 // Special handling for list aggregator nodes. If we are at list aggregator node e.g. MapNode and
 445                 // we are searching for schema for a list entry e.g. MapEntryNode just return the same schema
 446                 if (schemaNode instanceof ListSchemaNode &&
 447                     ((SchemaNode) schemaNode).getQName().equals(identifier.getNodeType())) {
 448                     found = schemaNode;
 449                 } else {
 450                     found = ((DataNodeContainer) schemaNode).getDataChildByName(identifier.getNodeType());
 451                 }
 452             } else if (schemaNode instanceof ChoiceSchemaNode) {
 453                 // For choices, iterate through all the cases
 454                 final Optional<DataSchemaNode> maybeChild = ((ChoiceSchemaNode) schemaNode).getCases().stream()
 455                         .flatMap(cas -> cas.getChildNodes().stream())
 456                         .filter(child -> child.getQName().equals(identifier.getNodeType()))
 457                         .findFirst();
 458                 if (maybeChild.isPresent()) {
 459                     found = maybeChild.get();
 460                 }
 461                 // Special handling for leaf-list nodes. Basically the same as is for list mixin nodes
 462             } else if (schemaNode instanceof LeafListSchemaNode &&
 463                 ((SchemaNode) schemaNode).getQName().equals(identifier.getNodeType())) {
 464                 found = schemaNode;
 465             }
 466
 467             return checkNotNull(found, "Unable to find child node in: %s identifiable by: %s", schemaNode, identifier);
 468         }
 469
 470         @Override
 471         public String toString() {
 472             return "Modification{" +
 473                     "id=" + id +
 474                     '}';
 475         }
 476     }
 477 }