xpath/yang-xpath-impl/src/main/java/org/opendaylight/yangtools/yang/xpath/impl/AntlrXPathParser.java

   1 /*
   2  * Copyright (c) 2018 Pantheon Technologies, s.r.o.  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.yangtools.yang.xpath.impl;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static com.google.common.base.Verify.verifyNotNull;
  13 import static java.util.Objects.requireNonNull;
  14 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.getChild;
  15 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.illegalShape;
  16 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyAtLeastChildren;
  17 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyChildCount;
  18 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyTerminal;
  19 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyToken;
  20 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyTree;
  21
  22 import com.google.common.collect.ImmutableList;
  23 import com.google.common.collect.Iterators;
  24 import com.google.common.collect.Maps;
  25 import java.util.ArrayDeque;
  26 import java.util.ArrayList;
  27 import java.util.Arrays;
  28 import java.util.Deque;
  29 import java.util.Iterator;
  30 import java.util.LinkedHashSet;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Optional;
  34 import java.util.Set;
  35 import javax.xml.xpath.XPathExpressionException;
  36 import org.antlr.v4.runtime.CharStreams;
  37 import org.antlr.v4.runtime.CommonTokenStream;
  38 import org.antlr.v4.runtime.ParserRuleContext;
  39 import org.antlr.v4.runtime.tree.ParseTree;
  40 import org.antlr.v4.runtime.tree.TerminalNode;
  41 import org.opendaylight.yangtools.yang.common.QName;
  42 import org.opendaylight.yangtools.yang.common.QNameModule;
  43 import org.opendaylight.yangtools.yang.common.UnresolvedQName;
  44 import org.opendaylight.yangtools.yang.common.YangConstants;
  45 import org.opendaylight.yangtools.yang.common.YangNamespaceContext;
  46 import org.opendaylight.yangtools.yang.common.YangVersion;
  47 import org.opendaylight.yangtools.yang.xpath.antlr.xpathLexer;
  48 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser;
  49 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.AbbreviatedStepContext;
  50 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.AbsoluteLocationPathNorootContext;
  51 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.AdditiveExprContext;
  52 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.AndExprContext;
  53 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.AxisSpecifierContext;
  54 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.EqualityExprContext;
  55 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.ExprContext;
  56 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.FilterExprContext;
  57 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.FunctionCallContext;
  58 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.FunctionNameContext;
  59 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.LocationPathContext;
  60 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.MultiplicativeExprContext;
  61 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.NCNameContext;
  62 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.NameTestContext;
  63 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.NodeTestContext;
  64 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.OrExprContext;
  65 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.PathExprNoRootContext;
  66 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.PredicateContext;
  67 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.PrimaryExprContext;
  68 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.QNameContext;
  69 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.RelationalExprContext;
  70 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.RelativeLocationPathContext;
  71 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.StepContext;
  72 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.UnaryExprNoRootContext;
  73 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.UnionExprNoRootContext;
  74 import org.opendaylight.yangtools.yang.xpath.antlr.xpathParser.VariableReferenceContext;
  75 import org.opendaylight.yangtools.yang.xpath.api.YangBinaryOperator;
  76 import org.opendaylight.yangtools.yang.xpath.api.YangBooleanConstantExpr;
  77 import org.opendaylight.yangtools.yang.xpath.api.YangExpr;
  78 import org.opendaylight.yangtools.yang.xpath.api.YangFilterExpr;
  79 import org.opendaylight.yangtools.yang.xpath.api.YangFunction;
  80 import org.opendaylight.yangtools.yang.xpath.api.YangFunctionCallExpr;
  81 import org.opendaylight.yangtools.yang.xpath.api.YangLiteralExpr;
  82 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath;
  83 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.AxisStep;
  84 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.QNameStep;
  85 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.ResolvedQNameStep;
  86 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.Step;
  87 import org.opendaylight.yangtools.yang.xpath.api.YangNaryExpr;
  88 import org.opendaylight.yangtools.yang.xpath.api.YangNaryOperator;
  89 import org.opendaylight.yangtools.yang.xpath.api.YangNegateExpr;
  90 import org.opendaylight.yangtools.yang.xpath.api.YangNumberExpr;
  91 import org.opendaylight.yangtools.yang.xpath.api.YangPathExpr;
  92 import org.opendaylight.yangtools.yang.xpath.api.YangVariableReferenceExpr;
  93 import org.opendaylight.yangtools.yang.xpath.api.YangXPathAxis;
  94 import org.opendaylight.yangtools.yang.xpath.api.YangXPathExpression;
  95 import org.opendaylight.yangtools.yang.xpath.api.YangXPathMathMode;
  96 import org.opendaylight.yangtools.yang.xpath.api.YangXPathMathSupport;
  97 import org.opendaylight.yangtools.yang.xpath.api.YangXPathNodeType;
  98 import org.opendaylight.yangtools.yang.xpath.api.YangXPathParser;
  99
 100 /**
 101  * ANTLR-based XPath parser. Uses {@code xpath.g4} ANTLR grammar.
 102  *
 103  * @author Robert Varga
 104  */
 105 abstract class AntlrXPathParser implements YangXPathParser {
 106     static class Base extends AntlrXPathParser {
 107         Base(final YangXPathMathMode mathMode) {
 108             super(mathMode);
 109         }
 110
 111         @Override
 112         public YangXPathExpression parseExpression(final String xpath) throws XPathExpressionException {
 113             final ParseExprResult result = parseExpr(xpath);
 114             return new AntlrYangXPathExpression.Base(mathMode, result.minimumYangVersion, result.expression, xpath);
 115         }
 116
 117         @Override
 118         QNameStep createStep(final YangXPathAxis axis, final String localName,
 119                 final List<YangExpr> predicates) {
 120             return axis.asStep(UnresolvedQName.Unqualified.of(localName).intern(), predicates);
 121         }
 122
 123         @Override
 124         QNameStep createStep(final YangXPathAxis axis, final String prefix, final String localName,
 125                 final List<YangExpr> predicates) {
 126             return axis.asStep(UnresolvedQName.Qualified.of(prefix, localName).intern(), predicates);
 127         }
 128
 129         @Override
 130         QName createQName(final String localName) {
 131             throw new UnsupportedOperationException();
 132         }
 133
 134         @Override
 135         QName createQName(final String prefix, final String localName) {
 136             throw new UnsupportedOperationException();
 137         }
 138     }
 139
 140     static class Qualified extends Base implements QualifiedBound {
 141         final YangNamespaceContext namespaceContext;
 142
 143         Qualified(final YangXPathMathMode mathMode, final YangNamespaceContext namespaceContext) {
 144             super(mathMode);
 145             this.namespaceContext = requireNonNull(namespaceContext);
 146         }
 147
 148         @Override
 149         public YangXPathExpression.QualifiedBound parseExpression(final String xpath) throws XPathExpressionException {
 150             final ParseExprResult result = parseExpr(xpath);
 151             return new AntlrYangXPathExpression.Qualified(mathMode, result.minimumYangVersion, result.expression, xpath,
 152                 result.haveLiteral ? namespaceContext : null);
 153         }
 154
 155         @Override
 156         final QName createQName(final String prefix, final String localName) {
 157             return namespaceContext.createQName(prefix, localName);
 158         }
 159
 160         @Override
 161         ResolvedQNameStep createStep(final YangXPathAxis axis, final String prefix, final String localName,
 162                 final List<YangExpr> predicates) {
 163             return axis.asStep(createQName(prefix, localName), predicates);
 164         }
 165     }
 166
 167     static final class Unqualified extends Qualified implements UnqualifiedBound {
 168         private final QNameModule defaultNamespace;
 169
 170         Unqualified(final YangXPathMathMode mathMode, final YangNamespaceContext namespaceContext,
 171                 final QNameModule defaultNamespace) {
 172             super(mathMode, namespaceContext);
 173             this.defaultNamespace = requireNonNull(defaultNamespace);
 174         }
 175
 176         @Override
 177         public YangXPathExpression.UnqualifiedBound parseExpression(final String xpath)
 178                 throws XPathExpressionException {
 179             final ParseExprResult result = parseExpr(xpath);
 180
 181             return new AntlrYangXPathExpression.Unqualified(mathMode, result.minimumYangVersion, result.expression,
 182                 xpath, result.haveLiteral ? namespaceContext : null, defaultNamespace);
 183         }
 184
 185         @Override
 186         QName createQName(final String localName) {
 187             return QName.create(defaultNamespace, localName);
 188         }
 189
 190         @Override
 191         ResolvedQNameStep createStep(final YangXPathAxis axis, final String localName,
 192                 final List<YangExpr> predicates) {
 193             return axis.asStep(QName.create(defaultNamespace, localName), predicates);
 194         }
 195     }
 196
 197     private static final class ParseExprResult {
 198         final YangVersion minimumYangVersion;
 199         final YangExpr expression;
 200         final boolean haveLiteral;
 201
 202         ParseExprResult(final YangVersion minimumYangVersion, final YangExpr expression, final boolean haveLiteral) {
 203             this.minimumYangVersion = requireNonNull(minimumYangVersion);
 204             this.expression = requireNonNull(expression);
 205             this.haveLiteral = haveLiteral;
 206         }
 207     }
 208
 209     private static final Map<String, YangBinaryOperator> BINARY_OPERATORS = Maps.uniqueIndex(
 210         Arrays.asList(YangBinaryOperator.values()), YangBinaryOperator::toString);
 211     private static final Map<String, YangXPathNodeType> NODE_TYPES = Maps.uniqueIndex(Arrays.asList(
 212         YangXPathNodeType.values()), YangXPathNodeType::toString);
 213     private static final Map<String, YangXPathAxis> XPATH_AXES = Maps.uniqueIndex(Arrays.asList(YangXPathAxis.values()),
 214         YangXPathAxis::toString);
 215     private static final Map<QName, YangFunction> YANG_FUNCTIONS = Maps.uniqueIndex(Arrays.asList(
 216         YangFunction.values()), YangFunction::getIdentifier);
 217
 218     // Cached for checks in hot path
 219     private static final AxisStep SELF_STEP = YangXPathAxis.SELF.asStep();
 220
 221     final YangXPathMathMode mathMode;
 222     private final YangXPathMathSupport mathSupport;
 223     private final FunctionSupport functionSupport;
 224
 225     private YangVersion minimumYangVersion = YangVersion.VERSION_1;
 226     private boolean haveLiteral = false;
 227
 228     AntlrXPathParser(final YangXPathMathMode mathMode) {
 229         this.mathMode = requireNonNull(mathMode);
 230         mathSupport = mathMode.getSupport();
 231         functionSupport = new FunctionSupport(mathSupport);
 232     }
 233
 234     abstract QName createQName(String localName);
 235
 236     abstract QName createQName(String prefix, String localName);
 237
 238     abstract QNameStep createStep(YangXPathAxis axis, String localName, List<YangExpr> predicates);
 239
 240     abstract QNameStep createStep(YangXPathAxis axis, String prefix, String localName, List<YangExpr> predicates);
 241
 242     private QNameStep createStep(final YangXPathAxis axis, final QNameContext expr, final List<YangExpr> predicates) {
 243         return switch (expr.getChildCount()) {
 244             case 1 -> createStep(axis, getChild(expr, NCNameContext.class, 0).getText(), predicates);
 245             case 3 -> createStep(axis, getChild(expr, NCNameContext.class, 0).getText(),
 246                     getChild(expr, NCNameContext.class, 2).getText(), predicates);
 247             default -> throw illegalShape(expr);
 248         };
 249     }
 250
 251     @SuppressWarnings("checkstyle:illegalCatch")
 252     final ParseExprResult parseExpr(final String xpath) throws XPathExpressionException {
 253         // Create a parser and disconnect it from console error output
 254         final xpathLexer lexer = new xpathLexer(CharStreams.fromString(xpath));
 255         final xpathParser parser = new xpathParser(new CommonTokenStream(lexer));
 256
 257         final CapturingErrorListener listener = new CapturingErrorListener();
 258         lexer.removeErrorListeners();
 259         lexer.addErrorListener(listener);
 260         parser.removeErrorListeners();
 261         parser.addErrorListener(listener);
 262         final ExprContext antlr = parser.main().expr();
 263         listener.reportError();
 264
 265         // Reset our internal context
 266         minimumYangVersion = YangVersion.VERSION_1;
 267         haveLiteral = false;
 268
 269         final YangExpr expr;
 270         try {
 271             expr = parseExpr(antlr);
 272         } catch (RuntimeException e) {
 273             throw new XPathExpressionException(e);
 274         }
 275         return new ParseExprResult(minimumYangVersion, expr, haveLiteral);
 276     }
 277
 278     /**
 279      * Parse and simplify an XPath expression in {@link ExprContext} representation.
 280      *
 281      * @param ctx Current parsing context
 282      * @param expr ANTLR ExprContext
 283      * @return A {@link YangExpr}
 284      * @throws NullPointerException if {@code expr} is null
 285      * @throws IllegalArgumentException if {@code expr} references an unbound prefix
 286      */
 287     private YangExpr parseExpr(final ExprContext expr) {
 288         final OrExprContext or = expr.orExpr();
 289         final int size = or.getChildCount();
 290         if (size == 1) {
 291             return parseAnd(getChild(or, AndExprContext.class, 0));
 292         }
 293         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 294         for (int i = 0; i < size; i += 2) {
 295             tmp.add(parseAnd(getChild(or, AndExprContext.class, i)));
 296         }
 297         return YangNaryOperator.OR.exprWith(tmp);
 298     }
 299
 300     private YangExpr parseAdditive(final AdditiveExprContext expr) {
 301         final Iterator<ParseTree> it = expr.children.iterator();
 302         final YangExpr first = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 303         return it.hasNext() ? parseAdditiveExpr(first, it) : first;
 304     }
 305
 306     private YangExpr parseAnd(final AndExprContext expr) {
 307         final int size = expr.getChildCount();
 308         if (size == 1) {
 309             return parseEquality(getChild(expr, EqualityExprContext.class, 0));
 310         }
 311         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 312         for (int i = 0; i < size; i += 2) {
 313             tmp.add(parseEquality(getChild(expr, EqualityExprContext.class, i)));
 314         }
 315         return YangNaryOperator.AND.exprWith(tmp);
 316     }
 317
 318     private YangExpr parseEquality(final EqualityExprContext expr) {
 319         final Iterator<ParseTree> it = expr.children.iterator();
 320         final YangExpr first = parseRelational(nextContext(it, RelationalExprContext.class));
 321         return it.hasNext() ? parseEqualityExpr(first, it) : first;
 322     }
 323
 324     private YangExpr parseFilter(final FilterExprContext expr) {
 325         final Iterator<ParseTree> it = expr.children.iterator();
 326         final YangExpr first = parsePrimary(nextContext(it, PrimaryExprContext.class));
 327         return it.hasNext() ? YangFilterExpr.of(first, ImmutableList.copyOf(Iterators.transform(it,
 328             tree ->  parsePredicate(verifyTree(PredicateContext.class, tree)))))
 329                 : first;
 330     }
 331
 332     private YangExpr parseFunctionCall(final FunctionCallContext expr) {
 333         // We are mapping functions to RFC7950 YIN namespace, to keep us consistent with type/statement definitions
 334
 335         final FunctionNameContext name = getChild(expr, FunctionNameContext.class, 0);
 336         final QName parsed = switch (name.getChildCount()) {
 337             case 1 -> QName.create(YangConstants.RFC6020_YIN_MODULE, name.getChild(0).getText());
 338             case 3 -> createQName(name.getChild(0).getText(), name.getChild(2).getText());
 339             default -> throw illegalShape(name);
 340         };
 341         final List<YangExpr> args = expr.expr().stream().map(this::parseExpr).collect(ImmutableList.toImmutableList());
 342         final YangFunction func = YANG_FUNCTIONS.get(parsed);
 343         if (func != null) {
 344             if (minimumYangVersion.compareTo(func.getYangVersion()) < 0) {
 345                 minimumYangVersion = func.getYangVersion();
 346             }
 347
 348             final YangExpr funcExpr = functionSupport.functionToExpr(func, args);
 349             if (funcExpr instanceof YangLiteralExpr) {
 350                 haveLiteral = true;
 351             }
 352             return funcExpr;
 353         }
 354
 355         checkArgument(!YangConstants.RFC6020_YIN_MODULE.equals(parsed.getModule()), "Unknown default function %s",
 356             parsed);
 357         return YangFunctionCallExpr.of(parsed, args);
 358     }
 359
 360     private YangLocationPath parseLocationPath(final LocationPathContext expr) {
 361         verifyChildCount(expr, 1);
 362         final ParseTree first = expr.getChild(0);
 363         if (first instanceof RelativeLocationPathContext relativeLocation) {
 364             return YangLocationPath.relative(parseLocationPathSteps(relativeLocation));
 365         }
 366
 367         final AbsoluteLocationPathNorootContext abs = verifyTree(AbsoluteLocationPathNorootContext.class, first);
 368         verifyChildCount(abs, 2);
 369
 370         final Deque<Step> steps = parseLocationPathSteps(getChild(abs, RelativeLocationPathContext.class, 1));
 371         parseStepShorthand(abs.getChild(0)).ifPresent(steps::addFirst);
 372
 373         return YangLocationPath.absolute(steps);
 374     }
 375
 376     private YangExpr parseMultiplicative(final MultiplicativeExprContext expr) {
 377         final ParseTree first = expr.getChild(0);
 378         final YangExpr left = first instanceof UnaryExprNoRootContext unary ? parseUnary(unary)
 379             : YangLocationPath.root();
 380         if (expr.getChildCount() == 1) {
 381             return left;
 382         }
 383
 384         verifyChildCount(expr, 3);
 385         final YangBinaryOperator operator = parseOperator(expr.getChild(1));
 386         final YangExpr right = parseMultiplicative(getChild(expr, MultiplicativeExprContext.class, 2));
 387         final Optional<YangExpr> simple = simplifyNumbers(operator, left, right);
 388         return simple.isPresent() ? simple.get() : operator.exprWith(left, right);
 389     }
 390
 391     private YangExpr parsePathExpr(final PathExprNoRootContext expr) {
 392         final ParseTree first = expr.getChild(0);
 393         if (first instanceof LocationPathContext location) {
 394             return parseLocationPath(location);
 395         }
 396
 397         final YangExpr filter = parseFilter(verifyTree(FilterExprContext.class, first));
 398         if (expr.getChildCount() == 1) {
 399             return filter;
 400         }
 401
 402         verifyChildCount(expr, 3);
 403         final Deque<Step> steps = parseLocationPathSteps(getChild(expr, RelativeLocationPathContext.class, 2));
 404         parseStepShorthand(expr.getChild(1)).ifPresent(steps::addFirst);
 405         return YangPathExpr.of(filter, YangLocationPath.relative(steps));
 406     }
 407
 408     private YangExpr parsePredicate(final PredicateContext expr) {
 409         verifyChildCount(expr, 3);
 410         return parseExpr(getChild(expr, ExprContext.class, 1));
 411     }
 412
 413     private YangExpr parsePrimary(final PrimaryExprContext expr) {
 414         if (expr.getChildCount() == 3) {
 415             return parseExpr(getChild(expr, ExprContext.class, 1));
 416         }
 417
 418         verifyChildCount(expr, 1);
 419         final ParseTree first = expr.getChild(0);
 420         if (first instanceof TerminalNode terminal) {
 421             return parseTerminal(terminal);
 422         } else if (first instanceof FunctionCallContext function) {
 423             return parseFunctionCall(function);
 424         } else if (first instanceof VariableReferenceContext variable) {
 425             return YangVariableReferenceExpr.of(parseQName(variable.qName()));
 426         } else {
 427             throw illegalShape(first);
 428         }
 429     }
 430
 431     private YangExpr parseRelational(final RelationalExprContext expr) {
 432         final Iterator<ParseTree> it = expr.children.iterator();
 433         final YangExpr first = parseAdditive(nextContext(it, AdditiveExprContext.class));
 434         return it.hasNext() ? parseRelationalExpr(first, it) : first;
 435     }
 436
 437     private Deque<Step> parseLocationPathSteps(final RelativeLocationPathContext expr) {
 438         final Deque<Step> steps = new ArrayDeque<>(expr.getChildCount());
 439         final Iterator<ParseTree> it = expr.children.iterator();
 440         addNotSelfStep(steps, parseStep(nextContext(it, StepContext.class)));
 441
 442         while (it.hasNext()) {
 443             parseStepShorthand(it.next()).ifPresent(steps::add);
 444
 445             // Parse step and add it if it's not SELF_STEP
 446             addNotSelfStep(steps, parseStep(nextContext(it, StepContext.class)));
 447         }
 448
 449         return steps;
 450     }
 451
 452     private static void addNotSelfStep(final Deque<Step> steps, final Step step) {
 453         if (!SELF_STEP.equals(step)) {
 454             steps.add(step);
 455         }
 456     }
 457
 458     private YangExpr parseTerminal(final TerminalNode term) {
 459         final String text = term.getText();
 460         return switch (term.getSymbol().getType()) {
 461             case xpathParser.Literal -> {
 462                 // We have to strip quotes
 463                 haveLiteral = true;
 464                 yield YangLiteralExpr.of(text.substring(1, text.length() - 1));
 465             }
 466             case xpathParser.Number -> mathSupport.createNumber(text);
 467             default -> throw illegalShape(term);
 468         };
 469     }
 470
 471     private YangExpr parseUnary(final UnaryExprNoRootContext expr) {
 472         // any number of '-' and an union expr
 473         final int size = verifyAtLeastChildren(expr, 1);
 474         final YangExpr ret = parseUnion(getChild(expr, UnionExprNoRootContext.class, size - 1));
 475         if (size % 2 != 0) {
 476             // Even number of '-' tokens cancel out
 477             return ret;
 478         }
 479         return ret instanceof YangNumberExpr number ? mathSupport.negateNumber(number) : YangNegateExpr.of(ret);
 480     }
 481
 482     private YangExpr parseUnion(final UnionExprNoRootContext expr) {
 483         final ParseTree first = expr.getChild(0);
 484         final YangExpr path;
 485         if (first instanceof PathExprNoRootContext noRoot) {
 486             path = parsePathExpr(noRoot);
 487             if (expr.getChildCount() == 1) {
 488                 return path;
 489             }
 490         } else {
 491             path = YangLocationPath.root();
 492         }
 493
 494         verifyChildCount(expr, 3);
 495         final YangExpr union = parseUnion(getChild(expr, UnionExprNoRootContext.class, 2));
 496
 497         // Deduplicate expressions so we do not perform useless unioning
 498         final Set<YangExpr> expressions = new LinkedHashSet<>();
 499         expressions.add(path);
 500         if (union instanceof YangNaryExpr nary && nary.getOperator() == YangNaryOperator.UNION) {
 501             expressions.addAll(nary.getExpressions());
 502         } else {
 503             expressions.add(union);
 504         }
 505
 506         return YangNaryOperator.UNION.exprWith(expressions);
 507     }
 508
 509     private YangExpr parseAdditiveExpr(final YangExpr left, final Iterator<ParseTree> it) {
 510         YangExpr ret = left;
 511         do {
 512             final YangBinaryOperator operator = nextOperator(it);
 513             final YangExpr right = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 514             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 515             ret = simple.isPresent() ? simple.orElseThrow() : operator.exprWith(ret, right);
 516         } while (it.hasNext());
 517
 518         return ret;
 519     }
 520
 521     private Optional<YangExpr> simplifyNumbers(final YangBinaryOperator operator, final YangExpr left,
 522             final YangExpr right) {
 523         if (left instanceof YangNumberExpr leftNumber && right instanceof YangNumberExpr rightNumber) {
 524             // Constant folding on numbers -- precision plays a role here
 525             return mathSupport.tryEvaluate(operator, leftNumber, rightNumber);
 526         }
 527         return Optional.empty();
 528     }
 529
 530     private YangExpr parseEqualityExpr(final YangExpr left, final Iterator<ParseTree> it) {
 531         YangExpr ret = left;
 532         do {
 533             final YangBinaryOperator operator = nextOperator(it);
 534             final YangExpr right = parseRelational(nextContext(it, RelationalExprContext.class));
 535
 536             if (left.equals(right)) {
 537                 // Constant folding on expression level: equal expressions are result in equal results
 538                 switch (operator) {
 539                     case EQUALS:
 540                         return YangBooleanConstantExpr.TRUE;
 541                     case NOT_EQUALS:
 542                         return YangBooleanConstantExpr.FALSE;
 543                     default:
 544                         break;
 545                 }
 546             }
 547
 548             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 549             ret = simple.isPresent() ? simple.orElseThrow() : operator.exprWith(ret, right);
 550         } while (it.hasNext());
 551
 552         return ret;
 553     }
 554
 555     private YangExpr parseRelationalExpr(final YangExpr left, final Iterator<ParseTree> it) {
 556         YangExpr ret = left;
 557         do {
 558             final YangBinaryOperator operator = nextOperator(it);
 559             final YangExpr right = parseAdditive(nextContext(it, AdditiveExprContext.class));
 560             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 561             ret = simple.isPresent() ? simple.orElseThrow() : operator.exprWith(ret, right);
 562         } while (it.hasNext());
 563
 564         return ret;
 565     }
 566
 567     private Step parseStep(final StepContext expr) {
 568         if (expr.getChildCount() == 1) {
 569             final AbbreviatedStepContext abbrev = getChild(expr, AbbreviatedStepContext.class, 0);
 570             verifyChildCount(abbrev, 1);
 571             return switch (getTerminalType(abbrev, 0)) {
 572                 case xpathParser.DOT -> YangXPathAxis.SELF.asStep();
 573                 case xpathParser.DOTDOT -> YangXPathAxis.PARENT.asStep();
 574                 default -> throw illegalShape(abbrev);
 575             };
 576         }
 577
 578         final int size = verifyAtLeastChildren(expr, 2);
 579         final List<YangExpr> predicates = new ArrayList<>(size - 2);
 580         for (int i = 2; i < size; ++i) {
 581             predicates.add(parsePredicate(getChild(expr, PredicateContext.class, i)));
 582         }
 583
 584         final YangXPathAxis axis = parseAxis(getChild(expr, AxisSpecifierContext.class, 0));
 585         final NodeTestContext nodeTest = getChild(expr, NodeTestContext.class, 1);
 586         return switch (nodeTest.getChildCount()) {
 587             case 1 -> {
 588                 final NameTestContext nameChild = getChild(nodeTest, NameTestContext.class, 0);
 589                 final ParseTree first = nameChild.getChild(0);
 590                 if (first instanceof TerminalNode terminal) {
 591                     verify(terminal.getSymbol().getType() == xpathParser.MUL);
 592                     yield axis.asStep(predicates);
 593                 }
 594                 yield createStep(axis, verifyTree(QNameContext.class, first), predicates);
 595             }
 596             case 3 -> axis.asStep(parseNodeType(nodeTest.getChild(0)), predicates);
 597             case 4 -> {
 598                 final String text = verifyToken(nodeTest, 2, xpathParser.Literal).getText();
 599                 yield axis.asStep(text.substring(1, text.length() - 1), predicates);
 600             }
 601             default -> throw illegalShape(nodeTest);
 602         };
 603     }
 604
 605     private static YangXPathAxis parseAxis(final AxisSpecifierContext expr) {
 606         return switch (expr.getChildCount()) {
 607             case 0 -> YangXPathAxis.CHILD;
 608             case 1 -> {
 609                 verify(getTerminalType(expr, 0) == xpathParser.AT, "Unhandled axis specifier shape %s", expr);
 610                 yield YangXPathAxis.ATTRIBUTE;
 611             }
 612             case 2 -> {
 613                 final String str = verifyTerminal(expr.getChild(0)).getText();
 614                 yield verifyNotNull(XPATH_AXES.get(str), "Unhandled axis %s", str);
 615             }
 616             default -> throw illegalShape(expr);
 617         };
 618     }
 619
 620     private QName parseQName(final QNameContext expr) {
 621         return switch (expr.getChildCount()) {
 622             case 1 -> createQName(getChild(expr, NCNameContext.class, 0).getText());
 623             case 3 -> createQName(getChild(expr, NCNameContext.class, 0).getText(),
 624                     getChild(expr, NCNameContext.class, 2).getText());
 625             default -> throw illegalShape(expr);
 626         };
 627     }
 628
 629     private static <T extends ParserRuleContext> T nextContext(final Iterator<ParseTree> it, final Class<T> type) {
 630         return verifyTree(type, it.next());
 631     }
 632
 633     private static YangBinaryOperator nextOperator(final Iterator<ParseTree> it) {
 634         return parseOperator(it.next());
 635     }
 636
 637     private static int getTerminalType(final ParseTree parent, final int offset) {
 638         return verifyTerminal(parent.getChild(offset)).getSymbol().getType();
 639     }
 640
 641     private static YangXPathNodeType parseNodeType(final ParseTree tree) {
 642         final String str = verifyTerminal(tree).getText();
 643         return verifyNotNull(NODE_TYPES.get(str), "Unhandled node type %s", str);
 644     }
 645
 646     private static YangBinaryOperator parseOperator(final ParseTree tree) {
 647         final String str = verifyTerminal(tree).getText();
 648         return verifyNotNull(BINARY_OPERATORS.get(str), "Unhandled operator %s", str);
 649     }
 650
 651     private static Optional<Step> parseStepShorthand(final ParseTree tree) {
 652         return switch (verifyTerminal(tree).getSymbol().getType()) {
 653             case xpathParser.PATHSEP -> Optional.empty();
 654             case xpathParser.ABRPATH -> Optional.of(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
 655             default -> throw illegalShape(tree);
 656         };
 657     }
 658 }