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(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(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         switch (expr.getChildCount()) {
 244             case 1:
 245                 return createStep(axis, getChild(expr, NCNameContext.class, 0).getText(), predicates);
 246             case 3:
 247                 return createStep(axis, getChild(expr, NCNameContext.class, 0).getText(),
 248                     getChild(expr, NCNameContext.class, 2).getText(), predicates);
 249             default:
 250                 throw illegalShape(expr);
 251         }
 252     }
 253
 254     @SuppressWarnings("checkstyle:illegalCatch")
 255     final ParseExprResult parseExpr(final String xpath) throws XPathExpressionException {
 256         // Create a parser and disconnect it from console error output
 257         final xpathLexer lexer = new xpathLexer(CharStreams.fromString(xpath));
 258         final xpathParser parser = new xpathParser(new CommonTokenStream(lexer));
 259
 260         final CapturingErrorListener listener = new CapturingErrorListener();
 261         lexer.removeErrorListeners();
 262         lexer.addErrorListener(listener);
 263         parser.removeErrorListeners();
 264         parser.addErrorListener(listener);
 265         final ExprContext antlr = parser.main().expr();
 266         listener.reportError();
 267
 268         // Reset our internal context
 269         minimumYangVersion = YangVersion.VERSION_1;
 270         haveLiteral = false;
 271
 272         final YangExpr expr;
 273         try {
 274             expr = parseExpr(antlr);
 275         } catch (RuntimeException e) {
 276             throw new XPathExpressionException(e);
 277         }
 278         return new ParseExprResult(minimumYangVersion, expr, haveLiteral);
 279     }
 280
 281     /**
 282      * Parse and simplify an XPath expression in {@link ExprContext} representation.
 283      *
 284      * @param ctx Current parsing context
 285      * @param expr ANTLR ExprContext
 286      * @return A {@link YangExpr}
 287      * @throws NullPointerException if {@code expr} is null
 288      * @throws IllegalArgumentException if {@code expr} references an unbound prefix
 289      */
 290     private YangExpr parseExpr(final ExprContext expr) {
 291         final OrExprContext or = expr.orExpr();
 292         final int size = or.getChildCount();
 293         if (size == 1) {
 294             return parseAnd(getChild(or, AndExprContext.class, 0));
 295         }
 296         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 297         for (int i = 0; i < size; i += 2) {
 298             tmp.add(parseAnd(getChild(or, AndExprContext.class, i)));
 299         }
 300         return YangNaryOperator.OR.exprWith(tmp);
 301     }
 302
 303     private YangExpr parseAdditive(final AdditiveExprContext expr) {
 304         final Iterator<ParseTree> it = expr.children.iterator();
 305         final YangExpr first = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 306         return it.hasNext() ? parseAdditiveExpr(first, it) : first;
 307     }
 308
 309     private YangExpr parseAnd(final AndExprContext expr) {
 310         final int size = expr.getChildCount();
 311         if (size == 1) {
 312             return parseEquality(getChild(expr, EqualityExprContext.class, 0));
 313         }
 314         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 315         for (int i = 0; i < size; i += 2) {
 316             tmp.add(parseEquality(getChild(expr, EqualityExprContext.class, i)));
 317         }
 318         return YangNaryOperator.AND.exprWith(tmp);
 319     }
 320
 321     private YangExpr parseEquality(final EqualityExprContext expr) {
 322         final Iterator<ParseTree> it = expr.children.iterator();
 323         final YangExpr first = parseRelational(nextContext(it, RelationalExprContext.class));
 324         return it.hasNext() ? parseEqualityExpr(first, it) : first;
 325     }
 326
 327     private YangExpr parseFilter(final FilterExprContext expr) {
 328         final Iterator<ParseTree> it = expr.children.iterator();
 329         final YangExpr first = parsePrimary(nextContext(it, PrimaryExprContext.class));
 330         return it.hasNext() ? YangFilterExpr.of(first, ImmutableList.copyOf(Iterators.transform(it,
 331             tree ->  parsePredicate(verifyTree(PredicateContext.class, tree)))))
 332                 : first;
 333     }
 334
 335     private YangExpr parseFunctionCall(final FunctionCallContext expr) {
 336         // We are mapping functions to RFC7950 YIN namespace, to keep us consistent with type/statement definitions
 337
 338         final FunctionNameContext name = getChild(expr, FunctionNameContext.class, 0);
 339         final QName parsed;
 340         switch (name.getChildCount()) {
 341             case 1:
 342                 parsed = QName.create(YangConstants.RFC6020_YIN_MODULE, name.getChild(0).getText());
 343                 break;
 344             case 3:
 345                 parsed = createQName(name.getChild(0).getText(), name.getChild(2).getText());
 346                 break;
 347             default:
 348                 throw illegalShape(name);
 349         }
 350
 351         final List<YangExpr> args = expr.expr().stream().map(this::parseExpr).collect(ImmutableList.toImmutableList());
 352         final YangFunction func = YANG_FUNCTIONS.get(parsed);
 353         if (func != null) {
 354             if (minimumYangVersion.compareTo(func.getYangVersion()) < 0) {
 355                 minimumYangVersion = func.getYangVersion();
 356             }
 357
 358             final YangExpr funcExpr = functionSupport.functionToExpr(func, args);
 359             if (funcExpr instanceof YangLiteralExpr) {
 360                 haveLiteral = true;
 361             }
 362             return funcExpr;
 363         }
 364
 365         checkArgument(!YangConstants.RFC6020_YIN_MODULE.equals(parsed.getModule()), "Unknown default function %s",
 366             parsed);
 367         return YangFunctionCallExpr.of(parsed, args);
 368     }
 369
 370     private YangLocationPath parseLocationPath(final LocationPathContext expr) {
 371         verifyChildCount(expr, 1);
 372         final ParseTree first = expr.getChild(0);
 373         if (first instanceof RelativeLocationPathContext) {
 374             return YangLocationPath.relative(parseLocationPathSteps((RelativeLocationPathContext) first));
 375         }
 376
 377         final AbsoluteLocationPathNorootContext abs = verifyTree(AbsoluteLocationPathNorootContext.class, first);
 378         verifyChildCount(abs, 2);
 379
 380         final Deque<Step> steps = parseLocationPathSteps(getChild(abs, RelativeLocationPathContext.class, 1));
 381         parseStepShorthand(abs.getChild(0)).ifPresent(steps::addFirst);
 382
 383         return YangLocationPath.absolute(steps);
 384     }
 385
 386     private YangExpr parseMultiplicative(final MultiplicativeExprContext expr) {
 387         final ParseTree first = expr.getChild(0);
 388         final YangExpr left;
 389         if (first instanceof UnaryExprNoRootContext) {
 390             left = parseUnary((UnaryExprNoRootContext) first);
 391         } else {
 392             left = YangLocationPath.root();
 393         }
 394         if (expr.getChildCount() == 1) {
 395             return left;
 396         }
 397
 398         verifyChildCount(expr, 3);
 399         final YangBinaryOperator operator = parseOperator(expr.getChild(1));
 400         final YangExpr right = parseMultiplicative(getChild(expr, MultiplicativeExprContext.class, 2));
 401         final Optional<YangExpr> simple = simplifyNumbers(operator, left, right);
 402         return simple.isPresent() ? simple.get() : operator.exprWith(left, right);
 403     }
 404
 405     private YangExpr parsePathExpr(final PathExprNoRootContext expr) {
 406         final ParseTree first = expr.getChild(0);
 407         if (first instanceof LocationPathContext) {
 408             return parseLocationPath((LocationPathContext) first);
 409         }
 410
 411         final YangExpr filter = parseFilter(verifyTree(FilterExprContext.class, first));
 412         if (expr.getChildCount() == 1) {
 413             return filter;
 414         }
 415
 416         verifyChildCount(expr, 3);
 417         final Deque<Step> steps = parseLocationPathSteps(getChild(expr, RelativeLocationPathContext.class, 2));
 418         parseStepShorthand(expr.getChild(1)).ifPresent(steps::addFirst);
 419         return YangPathExpr.of(filter, YangLocationPath.relative(steps));
 420     }
 421
 422     private YangExpr parsePredicate(final PredicateContext expr) {
 423         verifyChildCount(expr, 3);
 424         return parseExpr(getChild(expr, ExprContext.class, 1));
 425     }
 426
 427     private YangExpr parsePrimary(final PrimaryExprContext expr) {
 428         if (expr.getChildCount() == 3) {
 429             return parseExpr(getChild(expr, ExprContext.class, 1));
 430         }
 431
 432         verifyChildCount(expr, 1);
 433         final ParseTree first = expr.getChild(0);
 434         if (first instanceof TerminalNode) {
 435             return parseTerminal((TerminalNode) first);
 436         }
 437         if (first instanceof FunctionCallContext) {
 438             return parseFunctionCall((FunctionCallContext) first);
 439         }
 440         if (first instanceof VariableReferenceContext) {
 441             return YangVariableReferenceExpr.of(parseQName(((VariableReferenceContext) first).qName()));
 442         }
 443         throw illegalShape(first);
 444     }
 445
 446     private YangExpr parseRelational(final RelationalExprContext expr) {
 447         final Iterator<ParseTree> it = expr.children.iterator();
 448         final YangExpr first = parseAdditive(nextContext(it, AdditiveExprContext.class));
 449         return it.hasNext() ? parseRelationalExpr(first, it) : first;
 450     }
 451
 452     private Deque<Step> parseLocationPathSteps(final RelativeLocationPathContext expr) {
 453         final Deque<Step> steps = new ArrayDeque<>(expr.getChildCount());
 454         final Iterator<ParseTree> it = expr.children.iterator();
 455         addNotSelfStep(steps, parseStep(nextContext(it, StepContext.class)));
 456
 457         while (it.hasNext()) {
 458             parseStepShorthand(it.next()).ifPresent(steps::add);
 459
 460             // Parse step and add it if it's not SELF_STEP
 461             addNotSelfStep(steps, parseStep(nextContext(it, StepContext.class)));
 462         }
 463
 464         return steps;
 465     }
 466
 467     private static void addNotSelfStep(final Deque<Step> steps, final Step step) {
 468         if (!SELF_STEP.equals(step)) {
 469             steps.add(step);
 470         }
 471     }
 472
 473     private YangExpr parseTerminal(final TerminalNode term) {
 474         final String text = term.getText();
 475         switch (term.getSymbol().getType()) {
 476             case xpathParser.Literal:
 477                 // We have to strip quotes
 478                 haveLiteral = true;
 479                 return YangLiteralExpr.of(text.substring(1, text.length() - 1));
 480             case xpathParser.Number:
 481                 return mathSupport.createNumber(text);
 482             default:
 483                 throw illegalShape(term);
 484         }
 485     }
 486
 487     private YangExpr parseUnary(final UnaryExprNoRootContext expr) {
 488         // any number of '-' and an union expr
 489         final int size = verifyAtLeastChildren(expr, 1);
 490         final YangExpr ret = parseUnion(getChild(expr, UnionExprNoRootContext.class, size - 1));
 491         if (size % 2 != 0) {
 492             // Even number of '-' tokens cancel out
 493             return ret;
 494         }
 495         return ret instanceof YangNumberExpr ? mathSupport.negateNumber((YangNumberExpr) ret) : YangNegateExpr.of(ret);
 496     }
 497
 498     private YangExpr parseUnion(final UnionExprNoRootContext expr) {
 499         final ParseTree first = expr.getChild(0);
 500         final YangExpr path;
 501         if (first instanceof PathExprNoRootContext) {
 502             path = parsePathExpr((PathExprNoRootContext) first);
 503             if (expr.getChildCount() == 1) {
 504                 return path;
 505             }
 506         } else {
 507             path = YangLocationPath.root();
 508         }
 509
 510         verifyChildCount(expr, 3);
 511         final YangExpr union = parseUnion(getChild(expr, UnionExprNoRootContext.class, 2));
 512
 513         // Deduplicate expressions so we do not perform useless unioning
 514         final Set<YangExpr> expressions = new LinkedHashSet<>();
 515         expressions.add(path);
 516         if (union instanceof YangNaryExpr) {
 517             // If the result is a union expression, integrate it into this expression
 518             final YangNaryExpr nary = (YangNaryExpr) union;
 519             if (nary.getOperator() == YangNaryOperator.UNION) {
 520                 expressions.addAll(nary.getExpressions());
 521             } else {
 522                 expressions.add(union);
 523             }
 524         } else {
 525             expressions.add(union);
 526         }
 527
 528         return YangNaryOperator.UNION.exprWith(expressions);
 529     }
 530
 531     private YangExpr parseAdditiveExpr(final YangExpr left, final Iterator<ParseTree> it) {
 532         YangExpr ret = left;
 533         do {
 534             final YangBinaryOperator operator = nextOperator(it);
 535             final YangExpr right = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 536             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 537             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 538         } while (it.hasNext());
 539
 540         return ret;
 541     }
 542
 543     private Optional<YangExpr> simplifyNumbers(final YangBinaryOperator operator, final YangExpr left,
 544             final YangExpr right) {
 545         if (left instanceof YangNumberExpr && right instanceof YangNumberExpr) {
 546             // Constant folding on numbers -- precision plays a role here
 547             return mathSupport.tryEvaluate(operator, (YangNumberExpr)left, (YangNumberExpr)right);
 548         }
 549         return Optional.empty();
 550     }
 551
 552     private YangExpr parseEqualityExpr(final YangExpr left, final Iterator<ParseTree> it) {
 553         YangExpr ret = left;
 554         do {
 555             final YangBinaryOperator operator = nextOperator(it);
 556             final YangExpr right = parseRelational(nextContext(it, RelationalExprContext.class));
 557
 558             if (left.equals(right)) {
 559                 // Constant folding on expression level: equal expressions are result in equal results
 560                 switch (operator) {
 561                     case EQUALS:
 562                         return YangBooleanConstantExpr.TRUE;
 563                     case NOT_EQUALS:
 564                         return YangBooleanConstantExpr.FALSE;
 565                     default:
 566                         break;
 567                 }
 568             }
 569
 570             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 571             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 572         } while (it.hasNext());
 573
 574         return ret;
 575     }
 576
 577     private YangExpr parseRelationalExpr(final YangExpr left, final Iterator<ParseTree> it) {
 578         YangExpr ret = left;
 579         do {
 580             final YangBinaryOperator operator = nextOperator(it);
 581             final YangExpr right = parseAdditive(nextContext(it, AdditiveExprContext.class));
 582             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 583             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 584         } while (it.hasNext());
 585
 586         return ret;
 587     }
 588
 589     private Step parseStep(final StepContext expr) {
 590         if (expr.getChildCount() == 1) {
 591             final AbbreviatedStepContext abbrev = getChild(expr, AbbreviatedStepContext.class, 0);
 592             verifyChildCount(abbrev, 1);
 593             switch (getTerminalType(abbrev, 0)) {
 594                 case xpathParser.DOT:
 595                     return YangXPathAxis.SELF.asStep();
 596                 case xpathParser.DOTDOT:
 597                     return YangXPathAxis.PARENT.asStep();
 598                 default:
 599                     throw illegalShape(abbrev);
 600             }
 601         }
 602
 603         final int size = verifyAtLeastChildren(expr, 2);
 604         final List<YangExpr> predicates = new ArrayList<>(size - 2);
 605         for (int i = 2; i < size; ++i) {
 606             predicates.add(parsePredicate(getChild(expr, PredicateContext.class, i)));
 607         }
 608
 609         final YangXPathAxis axis = parseAxis(getChild(expr, AxisSpecifierContext.class, 0));
 610         final NodeTestContext nodeTest = getChild(expr, NodeTestContext.class, 1);
 611         switch (nodeTest.getChildCount()) {
 612             case 1:
 613                 final NameTestContext nameChild = getChild(nodeTest, NameTestContext.class, 0);
 614                 final ParseTree first = nameChild.getChild(0);
 615                 if (first instanceof TerminalNode) {
 616                     verify(((TerminalNode) first).getSymbol().getType() == xpathParser.MUL);
 617                     return axis.asStep(predicates);
 618                 }
 619                 return createStep(axis, verifyTree(QNameContext.class, first), predicates);
 620             case 3:
 621                 return axis.asStep(parseNodeType(nodeTest.getChild(0)), predicates);
 622             case 4:
 623                 final String text = verifyToken(nodeTest, 2, xpathParser.Literal).getText();
 624                 return axis.asStep(text.substring(1, text.length() - 1), predicates);
 625             default:
 626                 throw illegalShape(nodeTest);
 627         }
 628     }
 629
 630     private static YangXPathAxis parseAxis(final AxisSpecifierContext expr) {
 631         switch (expr.getChildCount()) {
 632             case 0:
 633                 return YangXPathAxis.CHILD;
 634             case 1:
 635                 verify(getTerminalType(expr, 0) == xpathParser.AT, "Unhandled axis specifier shape %s", expr);
 636                 return YangXPathAxis.ATTRIBUTE;
 637             case 2:
 638                 final String str = verifyTerminal(expr.getChild(0)).getText();
 639                 return verifyNotNull(XPATH_AXES.get(str), "Unhandled axis %s", str);
 640             default:
 641                 throw illegalShape(expr);
 642         }
 643     }
 644
 645     private QName parseQName(final QNameContext expr) {
 646         switch (expr.getChildCount()) {
 647             case 1:
 648                 return createQName(getChild(expr, NCNameContext.class, 0).getText());
 649             case 3:
 650                 return createQName(getChild(expr, NCNameContext.class, 0).getText(),
 651                     getChild(expr, NCNameContext.class, 2).getText());
 652             default:
 653                 throw illegalShape(expr);
 654         }
 655     }
 656
 657     private static <T extends ParserRuleContext> T nextContext(final Iterator<ParseTree> it, final Class<T> type) {
 658         return verifyTree(type, it.next());
 659     }
 660
 661     private static YangBinaryOperator nextOperator(final Iterator<ParseTree> it) {
 662         return parseOperator(it.next());
 663     }
 664
 665     private static int getTerminalType(final ParseTree parent, final int offset) {
 666         return verifyTerminal(parent.getChild(offset)).getSymbol().getType();
 667     }
 668
 669     private static YangXPathNodeType parseNodeType(final ParseTree tree) {
 670         final String str = verifyTerminal(tree).getText();
 671         return verifyNotNull(NODE_TYPES.get(str), "Unhandled node type %s", str);
 672     }
 673
 674     private static YangBinaryOperator parseOperator(final ParseTree tree) {
 675         final String str = verifyTerminal(tree).getText();
 676         return verifyNotNull(BINARY_OPERATORS.get(str), "Unhandled operator %s", str);
 677     }
 678
 679     private static Optional<Step> parseStepShorthand(final ParseTree tree) {
 680         switch (verifyTerminal(tree).getSymbol().getType()) {
 681             case xpathParser.PATHSEP:
 682                 return Optional.empty();
 683             case xpathParser.ABRPATH:
 684                 return Optional.of(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
 685             default:
 686                 throw illegalShape(tree);
 687         }
 688     }
 689 }