protocol/restconf-api/src/main/java/org/opendaylight/restconf/api/query/FieldsParameterParser.java

   1 /*
   2  * Copyright (c) 2021 PANTHEON.tech, s.r.o. 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.api.query;
   9
  10 import com.google.common.collect.ImmutableList;
  11 import java.text.ParseException;
  12 import java.util.ArrayDeque;
  13 import java.util.ArrayList;
  14 import java.util.Deque;
  15 import java.util.List;
  16 import org.eclipse.jdt.annotation.NonNull;
  17 import org.opendaylight.restconf.api.ApiPath.ApiIdentifier;
  18 import org.opendaylight.restconf.api.query.FieldsParam.NodeSelector;
  19 import org.opendaylight.yangtools.yang.common.YangNames;
  20
  21 /**
  22  * Stateful parser for {@link FieldsParam}. This is not as hard as IETF's ABNF would lead you to believe. The original
  23  *  definition is:
  24  * <pre>
  25  *    fields-expr = path "(" fields-expr ")" / path ";" fields-expr / path
  26  *    path = api-identifier [ "/" path ]
  27  * </pre>
  28  * To make some sense of this, let's express the same constructs in a more powerful ANTLR4 grammar.
  29  *
  30  * <p>
  31  * {@code path} is a rather simple
  32  * <pre>
  33  *    path = api-identifier ("/" api-identifier)*
  34  * </pre>
  35  * which is to say a {@code path} is "a sequence of one or more api-identifiers, separated by slashes". This boils in
  36  * turn down to a list {@link ApiIdentifier}s, which is guaranteed to have at least one item.
  37  *
  38  * <p>
  39  * {@code fields-expr} can be rewritten as three distinct possibilities:
  40  * <pre>
  41  *    fields-expr : path "(" fields-expr ")"
  42  *                | path ";" fields-expr
  43  *                | path
  44  * </pre>
  45  * which makes it clear it is a recursive structure, where the parentheses part is sub-filters and ';' serves as
  46  * concatenation. So let's rewrite that by folding the common part and use optional elements and introducing proper
  47  * names for constructs
  48  * <pre>
  49  *   fields         : node-selectors EOF
  50  *   node-selectors : node-selector (";" node-selector)*
  51  *   node-selector  : path sub-selectors?
  52  *   sub-selectors  : "(" node-selectors ")"
  53  *   path           : api-identifier ("/" api-identifier)*
  54  * </pre>
  55  *
  56  * <p>
  57  * That ANTLR4 grammar dictates the layout of {@link FieldsParam}. It also shows the parsing is recursive on
  58  * {@code node-selectors}, which is what {@link #parse(String)} and
  59  * {@link NodeSelectorParser#parseSubSelectors(String, int)} deal with.
  60  */
  61 final class FieldsParameterParser {
  62     // Lazily instantiated queue for reuse of parser when we encounter sub-selectors. We could just rely on JIT/GC
  63     // dealing with allocation rate, but we should be ready to see malicious inputs. One example of that is
  64     // multiple nested sub-selectors like "a(b(c(d)));e(f(g(h)));i(j(k(l)))" With this cache we end allocating only four
  65     // parsers instead of ten.
  66     private Deque<NodeSelectorParser> parsers;
  67
  68     @NonNull FieldsParam parse(final String str) throws ParseException {
  69         final var nodeSelectors = ImmutableList.<NodeSelector>builder();
  70
  71         int idx = 0;
  72         final var parser = new NodeSelectorParser();
  73         while (true) {
  74             final int next = parser.fillFrom(str, idx);
  75             nodeSelectors.add(parser.collectAndReset());
  76
  77             if (next == str.length()) {
  78                 // We have reached the end, we are done
  79                 return new FieldsParam(nodeSelectors.build());
  80             }
  81
  82             final char ch = str.charAt(next);
  83             if (ch != ';') {
  84                 throw new ParseException("Expecting ';', not '" + ch + "'", next);
  85             }
  86             idx = next + 1;
  87         }
  88     }
  89
  90     private @NonNull NodeSelectorParser getParser() {
  91         final var local = parsers;
  92         if (local != null) {
  93             final var existing = local.poll();
  94             if (existing != null) {
  95                 return existing;
  96             }
  97         }
  98         return new NodeSelectorParser();
  99     }
 100
 101     private void putParser(final NodeSelectorParser parser) {
 102         var local = parsers;
 103         if (local == null) {
 104             // Let's be conservative with memory allocation
 105             parsers = local = new ArrayDeque<>(2);
 106         }
 107         local.push(parser);
 108     }
 109
 110     private static void expectIdentifierStart(final String str, final int offset) throws ParseException {
 111         final char ch = charAt(str, offset);
 112         if (!YangNames.IDENTIFIER_START.matches(ch)) {
 113             throw new ParseException("Expecting [a-ZA-Z_], not '" + ch + "'", offset);
 114         }
 115     }
 116
 117     private static char charAt(final String str, final int offset) throws ParseException {
 118         if (str.length() == offset) {
 119             throw new ParseException("Unexpected end of input", offset);
 120         }
 121         return str.charAt(offset);
 122     }
 123
 124     // A note here: we could store 'str' either in this object, or FieldsParameterParser, but that makes it a bit
 125     // removed via indirection. We are opting for explicit argument passing to ensure JIT sees it as a local variable
 126     // along with offset.
 127     private final class NodeSelectorParser {
 128         private final List<ApiIdentifier> path = new ArrayList<>(4);
 129
 130         // Not that common: lazily instantiated
 131         private List<NodeSelector> selectors;
 132
 133         int fillFrom(final String str, final int offset) throws ParseException {
 134             return parsePathStepFirst(str, offset);
 135         }
 136
 137         @NonNull NodeSelector collectAndReset() {
 138             final ImmutableList<ApiIdentifier> collectedPath = ImmutableList.copyOf(path);
 139             path.clear();
 140
 141             final ImmutableList<NodeSelector> collectedSelectors;
 142             if (selectors != null && !selectors.isEmpty()) {
 143                 collectedSelectors = ImmutableList.copyOf(selectors);
 144                 selectors.clear();
 145             } else {
 146                 collectedSelectors = ImmutableList.of();
 147             }
 148
 149             return new NodeSelector(collectedPath, collectedSelectors);
 150         }
 151
 152         // We are at the start of a step in path. We are dealing with the first part of
 153         //   identifier (":" identifier)?
 154         // but are mindful of the big picture
 155         private int parsePathStepFirst(final String str, final int offset) throws ParseException {
 156             expectIdentifierStart(str, offset);
 157
 158             int idx = offset + 1;
 159             while (true) {
 160                 if (idx == str.length()) {
 161                     path.add(new ApiIdentifier(null, str.substring(offset)));
 162                     return idx;
 163                 }
 164
 165                 final char ch = str.charAt(idx);
 166                 if (!YangNames.NOT_IDENTIFIER_PART.matches(ch)) {
 167                     idx++;
 168                     continue;
 169                 }
 170
 171                 final String first = str.substring(offset, idx);
 172                 if (ch == ':') {
 173                     // We have complete first identifier, now switch to parsing the second identifier
 174                     return parsePathStepSecond(first, str, idx + 1);
 175                 }
 176                 path.add(new ApiIdentifier(null, first));
 177
 178                 return switch (ch) {
 179                     case ';', ')' -> /* End of this selector, return */ idx;
 180                     case '/' -> /* Process next step */ parsePathStepFirst(str, idx + 1);
 181                     case '(' -> /* Process at least one sub-selector */ parseSubSelectors(str, idx + 1);
 182                     default -> throw new ParseException("Expecting [a-zA-Z_.-/(:;], not '" + ch + "'", idx);
 183                 };
 184             }
 185         }
 186
 187         // We are at the second identifier of a step in path, we already have the first identifier from
 188         //   identifier (":" identifier)?
 189         // but are mindful of the big picture
 190         private int parsePathStepSecond(final String module, final String str, final int offset) throws ParseException {
 191             expectIdentifierStart(str, offset);
 192
 193             int idx = offset + 1;
 194             while (true) {
 195                 if (idx == str.length()) {
 196                     path.add(new ApiIdentifier(module, str.substring(offset)));
 197                     return idx;
 198                 }
 199
 200                 final char ch = str.charAt(idx);
 201                 if (!YangNames.NOT_IDENTIFIER_PART.matches(ch)) {
 202                     idx++;
 203                     continue;
 204                 }
 205                 path.add(new ApiIdentifier(module, str.substring(offset, idx)));
 206
 207                 return switch (ch) {
 208                     case ';', ')' -> /* End of this selector, return */ idx;
 209                     case '/' -> /* Process next step */ parsePathStepFirst(str, idx + 1);
 210                     case '(' -> /* Process at least one sub-selector */ parseSubSelectors(str, idx + 1);
 211                     default -> throw new ParseException("Expecting [a-zA-Z_.-/(:;], not '" + ch + "'", idx);
 212                 };
 213             }
 214         }
 215
 216         // We are dealing with sub-selectors here
 217         private int parseSubSelectors(final String str, final int offset) throws ParseException {
 218             var local = selectors;
 219             if (local == null) {
 220                 selectors = local = new ArrayList<>(4);
 221             }
 222
 223             int idx = offset;
 224             final var parser = getParser();
 225             while (true) {
 226                 final int next = parser.fillFrom(str, idx);
 227                 local.add(parser.collectAndReset());
 228
 229                 final char ch = charAt(str, next);
 230                 switch (ch) {
 231                     case ';':
 232                         // Another sub-selector
 233                         idx = next + 1;
 234                         continue;
 235                     case ')':
 236                         // End of these sub-selectors, return the parser for reuse
 237                         putParser(parser);
 238                         return next + 1;
 239                     default:
 240                         throw new ParseException("Expecting [;)], not '" + ch + "'", next);
 241                 }
 242             }
 243         }
 244     }
 245 }