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