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.common.errors.RestconfError.ErrorTag;
  25 import org.opendaylight.yangtools.yang.common.ErrorType;
  26 import org.opendaylight.yangtools.yang.common.QName;
  27 import org.opendaylight.yangtools.yang.common.QNameModule;
  28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  29 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  30 import org.opendaylight.yangtools.yang.data.util.DataSchemaContextNode;
  31 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  32 import org.opendaylight.yangtools.yang.model.api.LeafListSchemaNode;
  33 import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
  34 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  35
  36 /**
  37  * Utilities used for parsing of fields query parameter content.
  38  *
  39  * @param <T> type of identifier
  40  */
  41 public abstract class ParserFieldsParameter<T> {
  42     private static final ParserFieldsParameter<QName> QNAME_PARSER = new QNameParser();
  43     private static final ParserFieldsParameter<LinkedPathElement> PATH_PARSER = new PathParser();
  44
  45     private ParserFieldsParameter() {
  46     }
  47
  48     /**
  49      * Parse fields parameter and return complete list of child nodes organized into levels.
  50      *
  51      * @param identifier identifier context created from request URI
  52      * @param input input value of fields parameter
  53      * @return {@link List} of levels; each level contains set of {@link QName}
  54      */
  55     public static @NonNull List<Set<QName>> parseFieldsParameter(final @NonNull InstanceIdentifierContext<?> identifier,
  56                                                                  final @NonNull String input) {
  57         return QNAME_PARSER.parseFields(identifier, input);
  58     }
  59
  60     /**
  61      * Parse fields parameter and return list of child node paths saved in lists.
  62      *
  63      * @param identifier identifier context created from request URI
  64      * @param input input value of fields parameter
  65      * @return {@link List} of {@link YangInstanceIdentifier} that are relative to the last {@link PathArgument}
  66      *     of provided {@code identifier}
  67      */
  68     public static @NonNull List<YangInstanceIdentifier> parseFieldsPaths(
  69             final @NonNull InstanceIdentifierContext<?> identifier, final @NonNull String input) {
  70         final List<Set<LinkedPathElement>> levels = PATH_PARSER.parseFields(identifier, input);
  71         final List<Map<PathArgument, LinkedPathElement>> mappedLevels = mapLevelsContentByIdentifiers(levels);
  72         return buildPaths(mappedLevels);
  73     }
  74
  75     private static List<Map<PathArgument, LinkedPathElement>> mapLevelsContentByIdentifiers(
  76             final List<Set<LinkedPathElement>> levels) {
  77         // this step is used for saving some processing power - we can directly find LinkedPathElement using
  78         // representing PathArgument
  79         return levels.stream()
  80                 .map(linkedPathElements -> linkedPathElements.stream()
  81                         .map(linkedPathElement -> new SimpleEntry<>(linkedPathElement.targetNodeIdentifier,
  82                                 linkedPathElement))
  83                         .collect(Collectors.toMap(SimpleEntry::getKey, SimpleEntry::getValue)))
  84                 .collect(Collectors.toList());
  85     }
  86
  87     private static List<YangInstanceIdentifier> buildPaths(
  88             final List<Map<PathArgument, LinkedPathElement>> mappedLevels) {
  89         final List<YangInstanceIdentifier> completePaths = new ArrayList<>();
  90         // we must traverse levels from the deepest level to the top level, because each LinkedPathElement is only
  91         // linked to previous element
  92         for (int levelIndex = mappedLevels.size() - 1; levelIndex >= 0; levelIndex--) {
  93             // we go through unprocessed LinkedPathElements that represent leaves
  94             for (final LinkedPathElement pathElement : mappedLevels.get(levelIndex).values()) {
  95                 if (pathElement.processed) {
  96                     // this element was already processed from the lower level - skip it
  97                     continue;
  98                 }
  99                 pathElement.processed = true;
 100
 101                 // adding deepest path arguments, LinkedList is used for more effective insertion at the 0 index
 102                 final LinkedList<PathArgument> path = new LinkedList<>(pathElement.mixinNodesToTarget);
 103                 path.add(pathElement.targetNodeIdentifier);
 104
 105                 PathArgument previousIdentifier = pathElement.previousNodeIdentifier;
 106                 // adding path arguments from the linked LinkedPathElements recursively
 107                 for (int buildingLevel = levelIndex - 1; buildingLevel >= 0; buildingLevel--) {
 108                     final LinkedPathElement previousElement = mappedLevels.get(buildingLevel).get(previousIdentifier);
 109                     path.addFirst(previousElement.targetNodeIdentifier);
 110                     path.addAll(0, previousElement.mixinNodesToTarget);
 111                     previousIdentifier = previousElement.previousNodeIdentifier;
 112                     previousElement.processed = true;
 113                 }
 114                 completePaths.add(YangInstanceIdentifier.create(path));
 115             }
 116         }
 117         return completePaths;
 118     }
 119
 120     /**
 121      * Parse fields parameter and return complete list of child nodes organized into levels.
 122      *
 123      * @param identifier identifier context created from request URI
 124      * @param input input value of fields parameter
 125      * @return {@link List} of levels; each level contains {@link Set} of identifiers of type {@link T}
 126      */
 127     private @NonNull List<Set<T>> parseFields(final @NonNull InstanceIdentifierContext<?> identifier,
 128                                               final @NonNull String input) {
 129         final List<Set<T>> parsed = new ArrayList<>();
 130         final SchemaContext context = identifier.getSchemaContext();
 131         final QNameModule startQNameModule = identifier.getSchemaNode().getQName().getModule();
 132         final DataSchemaContextNode<?> startNode = DataSchemaContextNode.fromDataSchemaNode(
 133                 (DataSchemaNode) identifier.getSchemaNode());
 134
 135         if (startNode == null) {
 136             throw new RestconfDocumentedException(
 137                     "Start node missing in " + input, ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 138         }
 139
 140         parseInput(input, startQNameModule, startNode, parsed, context);
 141         return parsed;
 142     }
 143
 144     /**
 145      * Parse input value of fields parameter and create list of sets. Each set represents one level of child nodes.
 146      *
 147      * @param input input value of fields parameter
 148      * @param startQNameModule starting qname module
 149      * @param startNode starting node
 150      * @param parsed list of results
 151      * @param context schema context
 152      */
 153     private void parseInput(final @NonNull String input, final @NonNull QNameModule startQNameModule,
 154                             final @NonNull DataSchemaContextNode<?> startNode,
 155                             final @NonNull List<Set<T>> parsed, final SchemaContext context) {
 156         int currentPosition = 0;
 157         int startPosition = 0;
 158         DataSchemaContextNode<?> currentNode = startNode;
 159         QNameModule currentQNameModule = startQNameModule;
 160
 161         Set<T> currentLevel = new HashSet<>();
 162         parsed.add(currentLevel);
 163
 164         DataSchemaContextNode<?> parenthesisNode = currentNode;
 165         Set<T> parenthesisLevel = currentLevel;
 166         QNameModule parenthesisQNameModule = currentQNameModule;
 167
 168         while (currentPosition < input.length()) {
 169             final char currentChar = input.charAt(currentPosition);
 170
 171             if (ParserConstants.YANG_IDENTIFIER_PART.matches(currentChar)) {
 172                 currentPosition++;
 173                 continue;
 174             }
 175
 176             switch (currentChar) {
 177                 case '/':
 178                     // add parsed identifier to results for current level
 179                     currentNode = addChildToResult(currentNode, input.substring(startPosition, currentPosition),
 180                             currentQNameModule, currentLevel);
 181                     // go one level down
 182                     currentLevel = prepareQNameLevel(parsed, currentLevel);
 183
 184                     currentPosition++;
 185                     break;
 186                 case ':':
 187                     // new namespace and revision found
 188                     currentQNameModule = context.findModules(
 189                             input.substring(startPosition, currentPosition)).iterator().next().getQNameModule();
 190                     currentPosition++;
 191                     break;
 192                 case '(':
 193                     // add current child to parsed results for current level
 194                     final DataSchemaContextNode<?> child = addChildToResult(
 195                             currentNode,
 196                             input.substring(startPosition, currentPosition), currentQNameModule, currentLevel);
 197                     // call with child node as new start node for one level down
 198                     final int closingParenthesis = currentPosition
 199                             + findClosingParenthesis(input.substring(currentPosition + 1));
 200                     parseInput(
 201                             input.substring(currentPosition + 1, closingParenthesis),
 202                             currentQNameModule,
 203                             child,
 204                             parsed,
 205                             context);
 206
 207                     // closing parenthesis must be at the end of input or separator and one more character is expected
 208                     currentPosition = closingParenthesis + 1;
 209                     if (currentPosition != input.length()) {
 210                         if (currentPosition + 1 < input.length()) {
 211                             if (input.charAt(currentPosition) == ';') {
 212                                 currentPosition++;
 213                             } else {
 214                                 throw new RestconfDocumentedException(
 215                                         "Missing semicolon character after "
 216                                                 + child.getIdentifier().getNodeType().getLocalName()
 217                                                 + " child nodes",
 218                                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 219                             }
 220                         } else {
 221                             throw new RestconfDocumentedException(
 222                                     "Unexpected character '"
 223                                             + input.charAt(currentPosition)
 224                                             + "' found in fields parameter value",
 225                                     ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 226                         }
 227                     }
 228
 229                     break;
 230                 case ';':
 231                     // complete identifier found
 232                     addChildToResult(
 233                             currentNode,
 234                             input.substring(startPosition, currentPosition), currentQNameModule, currentLevel);
 235                     currentPosition++;
 236
 237                     // next nodes can be placed on already utilized level-s
 238                     currentNode = parenthesisNode;
 239                     currentQNameModule = parenthesisQNameModule;
 240                     currentLevel = parenthesisLevel;
 241                     break;
 242                 default:
 243                     throw new RestconfDocumentedException(
 244                             "Unexpected character '" + currentChar + "' found in fields parameter value",
 245                             ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 246             }
 247
 248             startPosition = currentPosition;
 249         }
 250
 251         // parse input to end
 252         if (startPosition < input.length()) {
 253             addChildToResult(currentNode, input.substring(startPosition), currentQNameModule, currentLevel);
 254         }
 255     }
 256
 257     /**
 258      * Preparation of the identifiers level that is used as storage for parsed identifiers. If the current level exist
 259      * at the index that doesn't equal to the last index of already parsed identifiers, a new level of identifiers
 260      * is allocated and pushed to input parsed identifiers.
 261      *
 262      * @param parsedIdentifiers Already parsed list of identifiers grouped to multiple levels.
 263      * @param currentLevel Current level of identifiers (set).
 264      * @return Existing or new level of identifiers.
 265      */
 266     private Set<T> prepareQNameLevel(final List<Set<T>> parsedIdentifiers, final Set<T> currentLevel) {
 267         final Optional<Set<T>> existingLevel = parsedIdentifiers.stream()
 268                 .filter(qNameSet -> qNameSet.equals(currentLevel))
 269                 .findAny();
 270         if (existingLevel.isPresent()) {
 271             final int index = parsedIdentifiers.indexOf(existingLevel.get());
 272             if (index == parsedIdentifiers.size() - 1) {
 273                 final Set<T> nextLevel = new HashSet<>();
 274                 parsedIdentifiers.add(nextLevel);
 275                 return nextLevel;
 276             }
 277
 278             return parsedIdentifiers.get(index + 1);
 279         }
 280
 281         final Set<T> nextLevel = new HashSet<>();
 282         parsedIdentifiers.add(nextLevel);
 283         return nextLevel;
 284     }
 285
 286     /**
 287      * Find position of matching parenthesis increased by one, but at most equals to input size.
 288      *
 289      * @param input input where to find for closing parenthesis
 290      * @return int position of closing parenthesis increased by one
 291      */
 292     private static int findClosingParenthesis(final @NonNull String input) {
 293         int position = 0;
 294         int count = 1;
 295
 296         while (position < input.length()) {
 297             final char currentChar = input.charAt(position);
 298
 299             if (currentChar == '(') {
 300                 count++;
 301             }
 302
 303             if (currentChar == ')') {
 304                 count--;
 305             }
 306
 307             if (count == 0) {
 308                 break;
 309             }
 310
 311             position++;
 312         }
 313
 314         // closing parenthesis was not found
 315         if (position >= input.length()) {
 316             throw new RestconfDocumentedException("Missing closing parenthesis in fields parameter",
 317                     ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 318         }
 319
 320         return ++position;
 321     }
 322
 323     /**
 324      * Add parsed child of current node to result for current level.
 325      *
 326      * @param currentNode current node
 327      * @param identifier parsed identifier of child node
 328      * @param currentQNameModule current namespace and revision in {@link QNameModule}
 329      * @param level current nodes level
 330      * @return {@link DataSchemaContextNode}
 331      */
 332     abstract @NonNull DataSchemaContextNode<?> addChildToResult(@NonNull DataSchemaContextNode<?> currentNode,
 333             @NonNull String identifier, @NonNull QNameModule currentQNameModule, @NonNull Set<T> level);
 334
 335     /**
 336      * Fields parser that stores set of {@link QName}s in each level. Because of this fact, from the output
 337      * it is is only possible to assume on what depth the selected element is placed. Identifiers of intermediary
 338      * mixin nodes are also flatten to the same level as identifiers of data nodes.<br>
 339      * Example: field 'a(/b/c);d/e' ('e' is place under choice node 'x') is parsed into following levels:<br>
 340      * <pre>
 341      * level 0: ['a', 'd']
 342      * level 1: ['b', 'x', 'e']
 343      * level 2: ['c']
 344      * </pre>
 345      */
 346     private static final class QNameParser extends ParserFieldsParameter<QName> {
 347         @Override
 348         DataSchemaContextNode<?> addChildToResult(final DataSchemaContextNode<?> currentNode, final String identifier,
 349                                                   final QNameModule currentQNameModule, final Set<QName> level) {
 350             final QName childQName = QName.create(currentQNameModule, identifier);
 351
 352             // resolve parent node
 353             final DataSchemaContextNode<?> parentNode = resolveMixinNode(
 354                     currentNode, level, currentNode.getIdentifier().getNodeType());
 355             if (parentNode == null) {
 356                 throw new RestconfDocumentedException(
 357                         "Not-mixin node missing in " + currentNode.getIdentifier().getNodeType().getLocalName(),
 358                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 359             }
 360
 361             // resolve child node
 362             final DataSchemaContextNode<?> childNode = resolveMixinNode(
 363                     parentNode.getChild(childQName), level, childQName);
 364             if (childNode == null) {
 365                 throw new RestconfDocumentedException(
 366                         "Child " + identifier + " node missing in "
 367                                 + currentNode.getIdentifier().getNodeType().getLocalName(),
 368                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 369             }
 370
 371             // add final childNode node to level nodes
 372             level.add(childNode.getIdentifier().getNodeType());
 373             return childNode;
 374         }
 375
 376         /**
 377          * Resolve mixin node by searching for inner nodes until not mixin node or null is found.
 378          * All nodes expect of not mixin node are added to current level nodes.
 379          *
 380          * @param node          initial mixin or not-mixin node
 381          * @param level         current nodes level
 382          * @param qualifiedName qname of initial node
 383          * @return {@link DataSchemaContextNode}
 384          */
 385         private static @Nullable DataSchemaContextNode<?> resolveMixinNode(
 386                 final @Nullable DataSchemaContextNode<?> node, final @NonNull Set<QName> level,
 387                 final @NonNull QName qualifiedName) {
 388             DataSchemaContextNode<?> currentNode = node;
 389             while (currentNode != null && currentNode.isMixin()) {
 390                 level.add(qualifiedName);
 391                 currentNode = currentNode.getChild(qualifiedName);
 392             }
 393
 394             return currentNode;
 395         }
 396     }
 397
 398     /**
 399      * Fields parser that stores set of {@link LinkedPathElement}s in each level. Using {@link LinkedPathElement}
 400      * it is possible to create a chain of path arguments and build complete paths since this element contains
 401      * identifiers of intermediary mixin nodes and also linked previous element.<br>
 402      * Example: field 'a(/b/c);d/e' ('e' is place under choice node 'x') is parsed into following levels:<br>
 403      * <pre>
 404      * level 0: ['./a', './d']
 405      * level 1: ['a/b', '/d/x/e']
 406      * level 2: ['b/c']
 407      * </pre>
 408      */
 409     private static final class PathParser extends ParserFieldsParameter<LinkedPathElement> {
 410         @Override
 411         DataSchemaContextNode<?> addChildToResult(final DataSchemaContextNode<?> currentNode, final String identifier,
 412                 final QNameModule currentQNameModule, final Set<LinkedPathElement> level) {
 413             final QName childQName = QName.create(currentQNameModule, identifier);
 414             final List<PathArgument> collectedMixinNodes = new ArrayList<>();
 415
 416             DataSchemaContextNode<?> actualContextNode = currentNode.getChild(childQName);
 417             while (actualContextNode != null && actualContextNode.isMixin()) {
 418                 if (actualContextNode.getDataSchemaNode() instanceof ListSchemaNode) {
 419                     // we need just a single node identifier from list in the path (key is not available)
 420                     actualContextNode = actualContextNode.getChild(childQName);
 421                     break;
 422                 } else if (actualContextNode.getDataSchemaNode() instanceof LeafListSchemaNode) {
 423                     // NodeWithValue is unusable - stop parsing
 424                     break;
 425                 } else {
 426                     collectedMixinNodes.add(actualContextNode.getIdentifier());
 427                     actualContextNode = actualContextNode.getChild(childQName);
 428                 }
 429             }
 430
 431             if (actualContextNode == null) {
 432                 throw new RestconfDocumentedException("Child " + identifier + " node missing in "
 433                         + currentNode.getIdentifier().getNodeType().getLocalName(),
 434                         ErrorType.PROTOCOL, ErrorTag.INVALID_VALUE);
 435             }
 436             final LinkedPathElement linkedPathElement = new LinkedPathElement(currentNode.getIdentifier(),
 437                     collectedMixinNodes, actualContextNode.getIdentifier());
 438             level.add(linkedPathElement);
 439             return actualContextNode;
 440         }
 441     }
 442
 443     /**
 444      * {@link PathArgument} of data element grouped with identifiers of leading mixin nodes and previous node.<br>
 445      *  - identifiers of mixin nodes on the path to the target node - required for construction of full valid
 446      *    DOM paths,<br>
 447      *  - identifier of the previous non-mixin node - required to successfully create a chain of {@link PathArgument}s
 448      */
 449     private static final class LinkedPathElement {
 450         private final PathArgument previousNodeIdentifier;
 451         private final List<PathArgument> mixinNodesToTarget;
 452         private final PathArgument targetNodeIdentifier;
 453         private boolean processed = false;
 454
 455         /**
 456          * Creation of new {@link LinkedPathElement}.
 457          *
 458          * @param previousNodeIdentifier identifier of the previous non-mixin node
 459          * @param mixinNodesToTarget     identifiers of mixin nodes on the path to the target node
 460          * @param targetNodeIdentifier   identifier of target non-mixin node
 461          */
 462         private LinkedPathElement(final PathArgument previousNodeIdentifier,
 463                 final List<PathArgument> mixinNodesToTarget, final PathArgument targetNodeIdentifier) {
 464             this.previousNodeIdentifier = previousNodeIdentifier;
 465             this.mixinNodesToTarget = mixinNodesToTarget;
 466             this.targetNodeIdentifier = targetNodeIdentifier;
 467         }
 468
 469         @Override
 470         public boolean equals(final Object obj) {
 471             // this is need in order to make 'prepareQNameLevel(..)' working
 472             if (this == obj) {
 473                 return true;
 474             }
 475             if (obj == null || getClass() != obj.getClass()) {
 476                 return false;
 477             }
 478             final LinkedPathElement that = (LinkedPathElement) obj;
 479             return targetNodeIdentifier.equals(that.targetNodeIdentifier);
 480         }
 481
 482         @Override
 483         public int hashCode() {
 484             return Objects.hash(targetNodeIdentifier);
 485         }
 486     }
 487 }