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