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