restconf/restconf-nb-rfc8040/src/main/java/org/opendaylight/restconf/nb/rfc8040/utils/parser/ParserFieldsParameter.java

   1 /*
   2  * Copyright (c) 2016 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.restconf.nb.rfc8040.utils.parser;
   9
  10 import java.util.AbstractMap.SimpleEntry;
  11 import java.util.ArrayList;
  12 import java.util.HashSet;
  13 import java.util.LinkedList;
  14 import java.util.List;
  15 import java.util.Map;
  16 import java.util.Objects;
  17 import java.util.Optional;
  18 import java.util.Set;
  19 import java.util.stream.Collectors;
  20 import org.eclipse.jdt.annotation.NonNull;
  21 import org.eclipse.jdt.annotation.Nullable;
  22 import org.opendaylight.restconf.common.context.InstanceIdentifierContext;
  23 import org.opendaylight.restconf.common.errors.RestconfDocumentedException;
  24 import org.opendaylight.restconf.nb.rfc8040.FieldsParam;
  25 import org.opendaylight.restconf.nb.rfc8040.FieldsParam.NodeSelector;
  26 import org.opendaylight.yangtools.yang.common.ErrorTag;
  27 import org.opendaylight.yangtools.yang.common.ErrorType;
  28 import org.opendaylight.yangtools.yang.common.QName;
  29 import org.opendaylight.yangtools.yang.common.QNameModule;
  30 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  31 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  32 import org.opendaylight.yangtools.yang.data.util.DataSchemaContextNode;
  33 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  34 import org.opendaylight.yangtools.yang.model.api.EffectiveModelContext;
  35 import org.opendaylight.yangtools.yang.model.api.LeafListSchemaNode;
  36 import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
  37
  38 /**
  39  * Utilities used for parsing of fields query parameter content.
  40  *
  41  * @param <T> type of identifier
  42  */
  43 public abstract class ParserFieldsParameter<T> {
  44     private static final ParserFieldsParameter<QName> QNAME_PARSER = new QNameParser();
  45     private static final ParserFieldsParameter<LinkedPathElement> PATH_PARSER = new PathParser();
  46
  47     private ParserFieldsParameter() {
  48     }
  49
  50     /**
  51      * Parse fields parameter and return complete list of child nodes organized into levels.
  52      *
  53      * @param identifier identifier context created from request URI
  54      * @param input input value of fields parameter
  55      * @return {@link List} of levels; each level contains set of {@link QName}
  56      */
  57     public static @NonNull List<Set<QName>> parseFieldsParameter(final @NonNull InstanceIdentifierContext<?> identifier,
  58                                                                  final @NonNull FieldsParam input) {
  59         return QNAME_PARSER.parseFields(identifier, input);
  60     }
  61
  62     /**
  63      * Parse fields parameter and return list of child node paths saved in lists.
  64      *
  65      * @param identifier identifier context created from request URI
  66      * @param input input value of fields parameter
  67      * @return {@link List} of {@link YangInstanceIdentifier} that are relative to the last {@link PathArgument}
  68      *     of provided {@code identifier}
  69      */
  70     public static @NonNull List<YangInstanceIdentifier> parseFieldsPaths(
  71             final @NonNull InstanceIdentifierContext<?> identifier, final @NonNull FieldsParam input) {
  72         final List<Set<LinkedPathElement>> levels = PATH_PARSER.parseFields(identifier, input);
  73         final List<Map<PathArgument, LinkedPathElement>> mappedLevels = mapLevelsContentByIdentifiers(levels);
  74         return buildPaths(mappedLevels);
  75     }
  76
  77     private static List<Map<PathArgument, LinkedPathElement>> mapLevelsContentByIdentifiers(
  78             final List<Set<LinkedPathElement>> levels) {
  79         // this step is used for saving some processing power - we can directly find LinkedPathElement using
  80         // representing PathArgument
  81         return levels.stream()
  82                 .map(linkedPathElements -> linkedPathElements.stream()
  83                         .map(linkedPathElement -> new SimpleEntry<>(linkedPathElement.targetNodeIdentifier,
  84                                 linkedPathElement))
  85                         .collect(Collectors.toMap(SimpleEntry::getKey, SimpleEntry::getValue)))
  86                 .collect(Collectors.toList());
  87     }
  88
  89     private static List<YangInstanceIdentifier> buildPaths(
  90             final List<Map<PathArgument, LinkedPathElement>> mappedLevels) {
  91         final List<YangInstanceIdentifier> completePaths = new ArrayList<>();
  92         // we must traverse levels from the deepest level to the top level, because each LinkedPathElement is only
  93         // linked to previous element
  94         for (int levelIndex = mappedLevels.size() - 1; levelIndex >= 0; levelIndex--) {
  95             // we go through unprocessed LinkedPathElements that represent leaves
  96             for (final LinkedPathElement pathElement : mappedLevels.get(levelIndex).values()) {
  97                 if (pathElement.processed) {
  98                     // this element was already processed from the lower level - skip it
  99                     continue;
 100                 }
 101                 pathElement.processed = true;
 102
 103                 // adding deepest path arguments, LinkedList is used for more effective insertion at the 0 index
 104                 final LinkedList<PathArgument> path = new LinkedList<>(pathElement.mixinNodesToTarget);
 105                 path.add(pathElement.targetNodeIdentifier);
 106
 107                 PathArgument previousIdentifier = pathElement.previousNodeIdentifier;
 108                 // adding path arguments from the linked LinkedPathElements recursively
 109                 for (int buildingLevel = levelIndex - 1; buildingLevel >= 0; buildingLevel--) {
 110                     final LinkedPathElement previousElement = mappedLevels.get(buildingLevel).get(previousIdentifier);
 111                     path.addFirst(previousElement.targetNodeIdentifier);
 112                     path.addAll(0, previousElement.mixinNodesToTarget);
 113                     previousIdentifier = previousElement.previousNodeIdentifier;
 114                     previousElement.processed = true;
 115                 }
 116                 completePaths.add(YangInstanceIdentifier.create(path));
 117             }
 118         }
 119         return completePaths;
 120     }
 121
 122     /**
 123      * Parse fields parameter and return complete list of child nodes organized into levels.
 124      *
 125      * @param identifier identifier context created from request URI
 126      * @param input input value of fields parameter
 127      * @return {@link List} of levels; each level contains {@link Set} of identifiers of type {@link T}
 128      */
 129     private @NonNull List<Set<T>> parseFields(final @NonNull InstanceIdentifierContext<?> identifier,
 130                                               final @NonNull FieldsParam input) {
 131         final DataSchemaContextNode<?> startNode = DataSchemaContextNode.fromDataSchemaNode(
 132                 (DataSchemaNode) identifier.getSchemaNode());
 133
 134         if (startNode == null) {
 135             throw new RestconfDocumentedException(
 136                     "Start node missing in " + input, ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 137         }
 138
 139         final List<Set<T>> parsed = new ArrayList<>();
 140         processSelectors(parsed, identifier.getSchemaContext(), identifier.getSchemaNode().getQName().getModule(),
 141             startNode, input.nodeSelectors());
 142         return parsed;
 143     }
 144
 145     private void processSelectors(final List<Set<T>> parsed, final EffectiveModelContext context,
 146             final QNameModule startNamespace, final DataSchemaContextNode<?> startNode,
 147             final List<NodeSelector> selectors) {
 148         final Set<T> startLevel = new HashSet<>();
 149         parsed.add(startLevel);
 150
 151         for (var selector : selectors) {
 152             var node = startNode;
 153             var namespace = startNamespace;
 154             var level = startLevel;
 155
 156
 157             // Note: path is guaranteed to have at least one step
 158             final var it = selector.path().iterator();
 159             while (true) {
 160                 // FIXME: The layout of this loop is rather weird, which is due to how prepareQNameLevel() operates. We
 161                 //        need to call it only when we know there is another identifier coming, otherwise we would end
 162                 //        up with empty levels sneaking into the mix.
 163                 //
 164                 //        Dealing with that weirdness requires understanding what the expected end results are and a
 165                 //        larger rewrite of the algorithms involved.
 166                 final var step = it.next();
 167                 final var module = step.module();
 168                 if (module != null) {
 169                     // FIXME: this is not defensive enough, as we can fail to find the module
 170                     namespace = context.findModules(module).iterator().next().getQNameModule();
 171                 }
 172
 173                 // add parsed identifier to results for current level
 174                 node = addChildToResult(node, step.identifier().bindTo(namespace), level);
 175                 if (!it.hasNext()) {
 176                     break;
 177                 }
 178
 179                 // go one level down
 180                 level = prepareQNameLevel(parsed, level);
 181             }
 182
 183             final var subs = selector.subSelectors();
 184             if (!subs.isEmpty()) {
 185                 processSelectors(parsed, context, namespace, node, subs);
 186             }
 187         }
 188     }
 189
 190     /**
 191      * Preparation of the identifiers level that is used as storage for parsed identifiers. If the current level exist
 192      * at the index that doesn't equal to the last index of already parsed identifiers, a new level of identifiers
 193      * is allocated and pushed to input parsed identifiers.
 194      *
 195      * @param parsedIdentifiers Already parsed list of identifiers grouped to multiple levels.
 196      * @param currentLevel Current level of identifiers (set).
 197      * @return Existing or new level of identifiers.
 198      */
 199     private Set<T> prepareQNameLevel(final List<Set<T>> parsedIdentifiers, final Set<T> currentLevel) {
 200         final Optional<Set<T>> existingLevel = parsedIdentifiers.stream()
 201                 .filter(qNameSet -> qNameSet.equals(currentLevel))
 202                 .findAny();
 203         if (existingLevel.isPresent()) {
 204             final int index = parsedIdentifiers.indexOf(existingLevel.get());
 205             if (index == parsedIdentifiers.size() - 1) {
 206                 final Set<T> nextLevel = new HashSet<>();
 207                 parsedIdentifiers.add(nextLevel);
 208                 return nextLevel;
 209             }
 210
 211             return parsedIdentifiers.get(index + 1);
 212         }
 213
 214         final Set<T> nextLevel = new HashSet<>();
 215         parsedIdentifiers.add(nextLevel);
 216         return nextLevel;
 217     }
 218
 219     /**
 220      * Add parsed child of current node to result for current level.
 221      *
 222      * @param currentNode current node
 223      * @param childQName parsed identifier of child node
 224      * @param level current nodes level
 225      * @return {@link DataSchemaContextNode}
 226      */
 227     abstract @NonNull DataSchemaContextNode<?> addChildToResult(@NonNull DataSchemaContextNode<?> currentNode,
 228             @NonNull QName childQName, @NonNull Set<T> level);
 229
 230     /**
 231      * Fields parser that stores set of {@link QName}s in each level. Because of this fact, from the output
 232      * it is is only possible to assume on what depth the selected element is placed. Identifiers of intermediary
 233      * mixin nodes are also flatten to the same level as identifiers of data nodes.<br>
 234      * Example: field 'a(/b/c);d/e' ('e' is place under choice node 'x') is parsed into following levels:<br>
 235      * <pre>
 236      * level 0: ['a', 'd']
 237      * level 1: ['b', 'x', 'e']
 238      * level 2: ['c']
 239      * </pre>
 240      */
 241     private static final class QNameParser extends ParserFieldsParameter<QName> {
 242         @Override
 243         DataSchemaContextNode<?> addChildToResult(final DataSchemaContextNode<?> currentNode, final QName childQName,
 244                                                   final Set<QName> level) {
 245             // resolve parent node
 246             final DataSchemaContextNode<?> parentNode = resolveMixinNode(
 247                     currentNode, level, currentNode.getIdentifier().getNodeType());
 248             if (parentNode == null) {
 249                 throw new RestconfDocumentedException(
 250                         "Not-mixin node missing in " + currentNode.getIdentifier().getNodeType().getLocalName(),
 251                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 252             }
 253
 254             // resolve child node
 255             final DataSchemaContextNode<?> childNode = resolveMixinNode(
 256                     parentNode.getChild(childQName), level, childQName);
 257             if (childNode == null) {
 258                 throw new RestconfDocumentedException(
 259                         "Child " + childQName.getLocalName() + " node missing in "
 260                                 + currentNode.getIdentifier().getNodeType().getLocalName(),
 261                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 262             }
 263
 264             // add final childNode node to level nodes
 265             level.add(childNode.getIdentifier().getNodeType());
 266             return childNode;
 267         }
 268
 269         /**
 270          * Resolve mixin node by searching for inner nodes until not mixin node or null is found.
 271          * All nodes expect of not mixin node are added to current level nodes.
 272          *
 273          * @param node          initial mixin or not-mixin node
 274          * @param level         current nodes level
 275          * @param qualifiedName qname of initial node
 276          * @return {@link DataSchemaContextNode}
 277          */
 278         private static @Nullable DataSchemaContextNode<?> resolveMixinNode(
 279                 final @Nullable DataSchemaContextNode<?> node, final @NonNull Set<QName> level,
 280                 final @NonNull QName qualifiedName) {
 281             DataSchemaContextNode<?> currentNode = node;
 282             while (currentNode != null && currentNode.isMixin()) {
 283                 level.add(qualifiedName);
 284                 currentNode = currentNode.getChild(qualifiedName);
 285             }
 286
 287             return currentNode;
 288         }
 289     }
 290
 291     /**
 292      * Fields parser that stores set of {@link LinkedPathElement}s in each level. Using {@link LinkedPathElement}
 293      * it is possible to create a chain of path arguments and build complete paths since this element contains
 294      * identifiers of intermediary mixin nodes and also linked previous element.<br>
 295      * Example: field 'a(/b/c);d/e' ('e' is place under choice node 'x') is parsed into following levels:<br>
 296      * <pre>
 297      * level 0: ['./a', './d']
 298      * level 1: ['a/b', '/d/x/e']
 299      * level 2: ['b/c']
 300      * </pre>
 301      */
 302     private static final class PathParser extends ParserFieldsParameter<LinkedPathElement> {
 303         @Override
 304         DataSchemaContextNode<?> addChildToResult(final DataSchemaContextNode<?> currentNode, final QName childQName,
 305                                                   final Set<LinkedPathElement> level) {
 306             final List<PathArgument> collectedMixinNodes = new ArrayList<>();
 307
 308             DataSchemaContextNode<?> actualContextNode = currentNode.getChild(childQName);
 309             while (actualContextNode != null && actualContextNode.isMixin()) {
 310                 if (actualContextNode.getDataSchemaNode() instanceof ListSchemaNode) {
 311                     // we need just a single node identifier from list in the path (key is not available)
 312                     actualContextNode = actualContextNode.getChild(childQName);
 313                     break;
 314                 } else if (actualContextNode.getDataSchemaNode() instanceof LeafListSchemaNode) {
 315                     // NodeWithValue is unusable - stop parsing
 316                     break;
 317                 } else {
 318                     collectedMixinNodes.add(actualContextNode.getIdentifier());
 319                     actualContextNode = actualContextNode.getChild(childQName);
 320                 }
 321             }
 322
 323             if (actualContextNode == null) {
 324                 throw new RestconfDocumentedException("Child " + childQName.getLocalName() + " node missing in "
 325                         + currentNode.getIdentifier().getNodeType().getLocalName(),
 326                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 327             }
 328             final LinkedPathElement linkedPathElement = new LinkedPathElement(currentNode.getIdentifier(),
 329                     collectedMixinNodes, actualContextNode.getIdentifier());
 330             level.add(linkedPathElement);
 331             return actualContextNode;
 332         }
 333     }
 334
 335     /**
 336      * {@link PathArgument} of data element grouped with identifiers of leading mixin nodes and previous node.<br>
 337      *  - identifiers of mixin nodes on the path to the target node - required for construction of full valid
 338      *    DOM paths,<br>
 339      *  - identifier of the previous non-mixin node - required to successfully create a chain of {@link PathArgument}s
 340      */
 341     private static final class LinkedPathElement {
 342         private final PathArgument previousNodeIdentifier;
 343         private final List<PathArgument> mixinNodesToTarget;
 344         private final PathArgument targetNodeIdentifier;
 345         private boolean processed = false;
 346
 347         /**
 348          * Creation of new {@link LinkedPathElement}.
 349          *
 350          * @param previousNodeIdentifier identifier of the previous non-mixin node
 351          * @param mixinNodesToTarget     identifiers of mixin nodes on the path to the target node
 352          * @param targetNodeIdentifier   identifier of target non-mixin node
 353          */
 354         private LinkedPathElement(final PathArgument previousNodeIdentifier,
 355                 final List<PathArgument> mixinNodesToTarget, final PathArgument targetNodeIdentifier) {
 356             this.previousNodeIdentifier = previousNodeIdentifier;
 357             this.mixinNodesToTarget = mixinNodesToTarget;
 358             this.targetNodeIdentifier = targetNodeIdentifier;
 359         }
 360
 361         @Override
 362         public boolean equals(final Object obj) {
 363             // this is need in order to make 'prepareQNameLevel(..)' working
 364             if (this == obj) {
 365                 return true;
 366             }
 367             if (obj == null || getClass() != obj.getClass()) {
 368                 return false;
 369             }
 370             final LinkedPathElement that = (LinkedPathElement) obj;
 371             return targetNodeIdentifier.equals(that.targetNodeIdentifier);
 372         }
 373
 374         @Override
 375         public int hashCode() {
 376             return Objects.hash(targetNodeIdentifier);
 377         }
 378     }
 379 }