yang/yang-xpath-impl/src/main/java/org/opendaylight/yangtools/yang/xpath/impl/XPathParser.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
  14 import com.google.common.base.VerifyException;
  15 import com.google.common.collect.ImmutableList;
  16 import com.google.common.collect.ImmutableSet;
  17 import com.google.common.collect.Iterators;
  18 import com.google.common.collect.Lists;
  19 import com.google.common.collect.Maps;
  20 import java.util.ArrayDeque;
  21 import java.util.ArrayList;
  22 import java.util.Arrays;
  23 import java.util.Collection;
  24 import java.util.Deque;
  25 import java.util.Iterator;
  26 import java.util.LinkedHashSet;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Optional;
  30 import java.util.Set;
  31 import java.util.function.Function;
  32 import javax.xml.xpath.XPathExpressionException;
  33 import org.antlr.v4.runtime.BaseErrorListener;
  34 import org.antlr.v4.runtime.CharStreams;
  35 import org.antlr.v4.runtime.CommonTokenStream;
  36 import org.antlr.v4.runtime.ParserRuleContext;
  37 import org.antlr.v4.runtime.RecognitionException;
  38 import org.antlr.v4.runtime.Recognizer;
  39 import org.antlr.v4.runtime.Token;
  40 import org.antlr.v4.runtime.tree.ParseTree;
  41 import org.antlr.v4.runtime.tree.TerminalNode;
  42 import org.eclipse.jdt.annotation.Nullable;
  43 import org.opendaylight.yangtools.yang.common.QName;
  44 import org.opendaylight.yangtools.yang.common.QNameModule;
  45 import org.opendaylight.yangtools.yang.common.YangConstants;
  46 import org.opendaylight.yangtools.yang.xpath.api.YangBinaryOperator;
  47 import org.opendaylight.yangtools.yang.xpath.api.YangBooleanConstantExpr;
  48 import org.opendaylight.yangtools.yang.xpath.api.YangExpr;
  49 import org.opendaylight.yangtools.yang.xpath.api.YangFilterExpr;
  50 import org.opendaylight.yangtools.yang.xpath.api.YangFunction;
  51 import org.opendaylight.yangtools.yang.xpath.api.YangFunctionCallExpr;
  52 import org.opendaylight.yangtools.yang.xpath.api.YangLiteralExpr;
  53 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath;
  54 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.AxisStep;
  55 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.Step;
  56 import org.opendaylight.yangtools.yang.xpath.api.YangNaryExpr;
  57 import org.opendaylight.yangtools.yang.xpath.api.YangNaryOperator;
  58 import org.opendaylight.yangtools.yang.xpath.api.YangNegateExpr;
  59 import org.opendaylight.yangtools.yang.xpath.api.YangNumberExpr;
  60 import org.opendaylight.yangtools.yang.xpath.api.YangQNameExpr;
  61 import org.opendaylight.yangtools.yang.xpath.api.YangVariableReferenceExpr;
  62 import org.opendaylight.yangtools.yang.xpath.api.YangXPathAxis;
  63 import org.opendaylight.yangtools.yang.xpath.api.YangXPathExpression;
  64 import org.opendaylight.yangtools.yang.xpath.api.YangXPathNodeType;
  65 import org.opendaylight.yangtools.yang.xpath.api.YangXPathParser;
  66 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.EqQuotedStringContext;
  67 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.InstanceIdentifierContext;
  68 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.KeyPredicateContext;
  69 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.KeyPredicateExprContext;
  70 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.LeafListPredicateContext;
  71 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.LeafListPredicateExprContext;
  72 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.NodeIdentifierContext;
  73 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.PathArgumentContext;
  74 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.PosContext;
  75 import org.opendaylight.yangtools.yang.xpath.impl.instanceIdentifierParser.QuotedStringContext;
  76 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AbbreviatedStepContext;
  77 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AbsoluteLocationPathNorootContext;
  78 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AdditiveExprContext;
  79 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AndExprContext;
  80 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AxisSpecifierContext;
  81 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.EqualityExprContext;
  82 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.ExprContext;
  83 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FilterExprContext;
  84 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FunctionCallContext;
  85 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FunctionNameContext;
  86 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.LocationPathContext;
  87 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.MultiplicativeExprContext;
  88 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NCNameContext;
  89 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NameTestContext;
  90 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NodeTestContext;
  91 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.OrExprContext;
  92 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PathExprNoRootContext;
  93 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PredicateContext;
  94 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PrimaryExprContext;
  95 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.QNameContext;
  96 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.RelationalExprContext;
  97 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.RelativeLocationPathContext;
  98 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.StepContext;
  99 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.UnaryExprNoRootContext;
 100 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.UnionExprNoRootContext;
 101 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.VariableReferenceContext;
 102 import org.slf4j.Logger;
 103 import org.slf4j.LoggerFactory;
 104
 105 /**
 106  * ANTLR-based XPath parser. Uses {@code xpath.g4} ANTLR grammar.
 107  *
 108  * @author Robert Varga
 109  */
 110 abstract class XPathParser<N extends YangNumberExpr<N, ?>> implements YangXPathParser {
 111     private static final Logger LOG = LoggerFactory.getLogger(XPathParser.class);
 112     private static final Map<String, YangBinaryOperator> BINARY_OPERATORS = Maps.uniqueIndex(
 113         Arrays.asList(YangBinaryOperator.values()), YangBinaryOperator::toString);
 114     private static final Map<String, YangXPathNodeType> NODE_TYPES = Maps.uniqueIndex(Arrays.asList(
 115         YangXPathNodeType.values()), YangXPathNodeType::toString);
 116     private static final Map<String, YangXPathAxis> XPATH_AXES = Maps.uniqueIndex(Arrays.asList(YangXPathAxis.values()),
 117         YangXPathAxis::toString);
 118     private static final Map<QName, YangFunction> YANG_FUNCTIONS = Maps.uniqueIndex(Arrays.asList(
 119         YangFunction.values()), YangFunction::getIdentifier);
 120
 121     // Cached for checks in hot path
 122     private static final AxisStep SELF_STEP = YangXPathAxis.SELF.asStep();
 123
 124     private final QNameSupport qnameSupport;
 125
 126     XPathParser(final QNameModule implicitNamespace, final Function<String, QNameModule> prefixes) {
 127         qnameSupport = new QNameSupport(implicitNamespace, prefixes);
 128     }
 129
 130     @Override
 131     public YangXPathExpression parseExpression(final String xpath) throws XPathExpressionException {
 132         // Create a parser and disconnect it from console error output
 133         final xpathLexer lexer = new xpathLexer(CharStreams.fromString(xpath));
 134         final xpathParser parser = new xpathParser(new CommonTokenStream(lexer));
 135
 136         final List<XPathExpressionException> errors = new ArrayList<>();
 137         final BaseErrorListener listener = new BaseErrorListener() {
 138             @Override
 139             public void syntaxError(final @Nullable Recognizer<?, ?> recognizer, final @Nullable Object offendingSymbol,
 140                     final int line, final int charPositionInLine, final @Nullable String msg,
 141                     final @Nullable RecognitionException cause) {
 142                 final XPathExpressionException ex = new XPathExpressionException(msg);
 143                 ex.initCause(cause);
 144                 if (errors.isEmpty()) {
 145                     errors.add(ex);
 146                 } else {
 147                     errors.get(0).addSuppressed(ex);
 148                 }
 149             }
 150         };
 151
 152         lexer.removeErrorListeners();
 153         lexer.addErrorListener(listener);
 154         parser.removeErrorListeners();
 155         parser.addErrorListener(listener);
 156
 157         final YangExpr expr = parseExpr(parser.main().expr());
 158         if (!errors.isEmpty()) {
 159             throw errors.get(0);
 160         }
 161
 162         return new AntlrYangXPathExpression(qnameSupport, expr, xpath);
 163     }
 164
 165     /**
 166      * Parse and simplify an XPath expression in {@link ExprContext} representation.
 167      *
 168      * @param expr ANTLR ExprContext
 169      * @return A {@link YangExpr}
 170      * @throws NullPointerException if {@code expr} is null
 171      * @throws IllegalArgumentException if {@code expr} references an unbound prefix
 172      */
 173     private YangExpr parseExpr(final ExprContext expr) {
 174         final OrExprContext or = expr.orExpr();
 175         final int size = or.getChildCount();
 176         if (size == 1) {
 177             return parseAnd(getChild(or, AndExprContext.class, 0));
 178         }
 179         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 180         for (int i = 0; i < size; i += 2) {
 181             tmp.add(parseAnd(getChild(or, AndExprContext.class, i)));
 182         }
 183         return YangNaryOperator.OR.exprWith(tmp);
 184     }
 185
 186     /**
 187      * Create a {@link YangNumberExpr} backed by specified string.
 188      *
 189      * @param str String, matching {@link xpathParser#Number} production.
 190      * @return number expression
 191      * @throws NullPointerException if {@code str} is null
 192      */
 193     abstract N createNumber(String str);
 194
 195     /**
 196      * Create a {@link YangNumberExpr} representing the negated value of a number.
 197      *
 198      * @param number input number
 199      * @return negated number expression
 200      * @throws NullPointerException if {@code number} is null
 201      */
 202     abstract N negateNumber(N number);
 203
 204     private YangExpr parseAdditive(final AdditiveExprContext expr) {
 205         final Iterator<ParseTree> it = expr.children.iterator();
 206         final YangExpr first = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 207         return it.hasNext() ? parseAdditiveExpr(first, it) : first;
 208     }
 209
 210     private YangExpr parseAnd(final AndExprContext expr) {
 211         final int size = expr.getChildCount();
 212         if (size == 1) {
 213             return parseEquality(getChild(expr, EqualityExprContext.class, 0));
 214         }
 215         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 216         for (int i = 0; i < size; i += 2) {
 217             tmp.add(parseEquality(getChild(expr, EqualityExprContext.class, i)));
 218         }
 219         return YangNaryOperator.AND.exprWith(tmp);
 220     }
 221
 222     private YangExpr parseEquality(final EqualityExprContext expr) {
 223         final Iterator<ParseTree> it = expr.children.iterator();
 224         final YangExpr first = parseRelational(nextContext(it, RelationalExprContext.class));
 225         return it.hasNext() ? parseEqualityExpr(first, it) : first;
 226     }
 227
 228     private YangExpr parseFilter(final FilterExprContext expr) {
 229         final Iterator<ParseTree> it = expr.children.iterator();
 230         final YangExpr first = parsePrimary(nextContext(it, PrimaryExprContext.class));
 231         return it.hasNext() ? YangFilterExpr.of(first, ImmutableList.copyOf(Iterators.transform(it,
 232             tree ->  parsePredicate(verifyTree(PredicateContext.class, tree)))))
 233                 : first;
 234     }
 235
 236     private YangExpr parseFunctionCall(final FunctionCallContext expr) {
 237         // We are mapping functions to RFC7950 YIN namespace, to keep us consistent with type/statement definitions
 238
 239         final FunctionNameContext name = getChild(expr, FunctionNameContext.class, 0);
 240         final QName parsed;
 241         switch (name.getChildCount()) {
 242             case 1:
 243                 parsed = QName.create(YangConstants.RFC6020_YIN_MODULE, name.getChild(0).getText());
 244                 break;
 245             case 3:
 246                 parsed = qnameSupport.createQName(name.getChild(0).getText(), name.getChild(2).getText());
 247                 break;
 248             default:
 249                 throw illegalShape(name);
 250         }
 251
 252         final List<YangExpr> args = ImmutableList.copyOf(Lists.transform(expr.expr(), this::parseExpr));
 253         final YangFunction func = YANG_FUNCTIONS.get(parsed);
 254         if (func != null) {
 255             return Functions.functionToExpr(func, args);
 256         }
 257
 258         checkArgument(!YangConstants.RFC6020_YIN_MODULE.equals(parsed.getModule()), "Unknown default function %s",
 259             parsed);
 260         return YangFunctionCallExpr.of(parsed, args);
 261     }
 262
 263     private YangLocationPath parseLocationPath(final LocationPathContext expr) {
 264         verifyChildCount(expr, 1);
 265         final ParseTree first = expr.getChild(0);
 266         if (first instanceof RelativeLocationPathContext) {
 267             return parseRelativeLocationPath((RelativeLocationPathContext) first);
 268         }
 269
 270         final AbsoluteLocationPathNorootContext abs = verifyTree(AbsoluteLocationPathNorootContext.class, first);
 271         verifyChildCount(abs, 2);
 272
 273         final Deque<Step> steps = parseLocationPathSteps(getChild(abs, RelativeLocationPathContext.class, 1));
 274         switch (getTerminalType(abs, 0)) {
 275             case xpathParser.PATHSEP:
 276                 break;
 277             case xpathParser.ABRPATH:
 278                 steps.addFirst(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
 279                 break;
 280             default:
 281                 throw illegalShape(abs);
 282         }
 283
 284         return YangLocationPath.of(true, steps);
 285     }
 286
 287     private YangExpr parseMultiplicative(final MultiplicativeExprContext expr) {
 288         final ParseTree first = expr.getChild(0);
 289         final YangExpr left;
 290         if (first instanceof UnaryExprNoRootContext) {
 291             left = parseUnary((UnaryExprNoRootContext) first);
 292         } else {
 293             left = YangLocationPath.root();
 294         }
 295         if (expr.getChildCount() == 1) {
 296             return left;
 297         }
 298
 299         verifyChildCount(expr, 3);
 300         final YangBinaryOperator operator = parseOperator(expr.getChild(1));
 301         final YangExpr right = parseMultiplicative(getChild(expr, MultiplicativeExprContext.class, 2));
 302         final Optional<YangExpr> simple = simplifyNumbers(operator, left, right);
 303         return simple.isPresent() ? simple.get() : operator.exprWith(left, right);
 304     }
 305
 306     private YangExpr parsePathExpr(final PathExprNoRootContext expr) {
 307         final ParseTree first = expr.getChild(0);
 308         if (first instanceof LocationPathContext) {
 309             return parseLocationPath((LocationPathContext) first);
 310         }
 311
 312         final YangExpr filter = parseFilter(verifyTree(FilterExprContext.class, first));
 313         if (expr.getChildCount() == 1) {
 314             return filter;
 315         }
 316
 317         verifyChildCount(expr, 3);
 318         return parseOperator(expr.getChild(1)).exprWith(filter,
 319             parseRelativeLocationPath(getChild(expr, RelativeLocationPathContext.class, 2)));
 320     }
 321
 322     private YangExpr parsePredicate(final PredicateContext expr) {
 323         verifyChildCount(expr, 3);
 324         return parseExpr(getChild(expr, ExprContext.class, 1));
 325     }
 326
 327     private YangExpr parsePrimary(final PrimaryExprContext expr) {
 328         if (expr.getChildCount() == 3) {
 329             return parseExpr(getChild(expr, ExprContext.class, 1));
 330         }
 331
 332         verifyChildCount(expr, 1);
 333         final ParseTree first = expr.getChild(0);
 334         if (first instanceof TerminalNode) {
 335             return parseTerminal((TerminalNode) first);
 336         }
 337         if (first instanceof FunctionCallContext) {
 338             return parseFunctionCall((FunctionCallContext) first);
 339         }
 340         if (first instanceof VariableReferenceContext) {
 341             return YangVariableReferenceExpr.of(parseQName(((VariableReferenceContext) first).qName()));
 342         }
 343         throw illegalShape(first);
 344     }
 345
 346     private YangExpr parseRelational(final RelationalExprContext expr) {
 347         final Iterator<ParseTree> it = expr.children.iterator();
 348         final YangExpr first = parseAdditive(nextContext(it, AdditiveExprContext.class));
 349         return it.hasNext() ? parseRelationalExpr(first, it) : first;
 350     }
 351
 352     private Deque<Step> parseLocationPathSteps(final RelativeLocationPathContext expr) {
 353         final Deque<Step> steps = new ArrayDeque<>(expr.getChildCount());
 354         final Iterator<ParseTree> it = expr.children.iterator();
 355         steps.add(parseStep(nextContext(it, StepContext.class)));
 356
 357         while (it.hasNext()) {
 358             final ParseTree tree = it.next();
 359             switch (verifyTerminal(tree).getSymbol().getType()) {
 360                 case xpathParser.PATHSEP:
 361                     break;
 362                 case xpathParser.ABRPATH:
 363                     steps.add(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
 364                     break;
 365                 default:
 366                     throw illegalShape(tree);
 367             }
 368
 369             // Parse step and add it if it's not SELF_STEP
 370             final Step step = parseStep(nextContext(it, StepContext.class));
 371             if (!SELF_STEP.equals(step)) {
 372                 steps.add(step);
 373             }
 374         }
 375
 376         return steps;
 377     }
 378
 379     private YangLocationPath parseRelativeLocationPath(final RelativeLocationPathContext expr) {
 380         return YangLocationPath.of(false, parseLocationPathSteps(expr));
 381     }
 382
 383     private YangExpr parseTerminal(final TerminalNode term) {
 384         final String text = term.getText();
 385         switch (term.getSymbol().getType()) {
 386             case xpathParser.Literal:
 387                 // We have to strip quotes
 388                 return parseLiteral(text.substring(1, text.length() - 1));
 389             case xpathParser.Number:
 390                 return createNumber(text);
 391             default:
 392                 throw illegalShape(term);
 393         }
 394     }
 395
 396     private YangLiteralExpr parseLiteral(final String text) {
 397         if (text.isEmpty()) {
 398             return YangLiteralExpr.empty();
 399         }
 400         if (text.charAt(0) == '/') {
 401             return parseLocationLiteral(text);
 402         }
 403         return parseQNameLiteral(text);
 404     }
 405
 406     private YangLiteralExpr parseLocationLiteral(final String text) {
 407         final xpathLexer lexer = new xpathLexer(CharStreams.fromString(text));
 408         final instanceIdentifierParser parser = new instanceIdentifierParser(new CommonTokenStream(lexer));
 409         lexer.removeErrorListeners();
 410         parser.removeErrorListeners();
 411
 412         // FIXME: add listeners
 413
 414         final InstanceIdentifierContext id = parser.instanceIdentifier();
 415         final int length = id.getChildCount();
 416         final List<Step> steps = new ArrayList<>(length / 2);
 417         for (int i = 1; i < length; i += 2) {
 418             steps.add(parsePathArgument(getChild(id, PathArgumentContext.class, i)));
 419         }
 420
 421         return new InstanceIdentifierLiteralExpr(text, steps);
 422     }
 423
 424     private Step parsePathArgument(final PathArgumentContext expr) {
 425         final QName qname = parseInstanceIdentifierQName(getChild(expr, NodeIdentifierContext.class, 0));
 426         switch (expr.getChildCount()) {
 427             case 1:
 428                 return YangXPathAxis.CHILD.asStep(qname, ImmutableSet.of());
 429             case 2:
 430                 return YangXPathAxis.CHILD.asStep(qname,
 431                     parsePathArgumentPredicate(getChild(expr, instanceIdentifierParser.PredicateContext.class, 1)));
 432             default:
 433                 throw illegalShape(expr);
 434         }
 435     }
 436
 437     private Collection<YangExpr> parsePathArgumentPredicate(final instanceIdentifierParser.PredicateContext expr) {
 438         final ParseTree first = expr.getChild(0);
 439         if (first instanceof LeafListPredicateContext) {
 440             return ImmutableSet.of(YangBinaryOperator.EQUALS.exprWith(YangLocationPath.self(),
 441                 parseEqStringValue(getChild(((LeafListPredicateContext) first)
 442                     .getChild(LeafListPredicateExprContext.class, 0), EqQuotedStringContext.class, 1))));
 443         } else if (first instanceof PosContext) {
 444             return ImmutableSet.of(YangBinaryOperator.EQUALS.exprWith(Functions.POSITION,
 445                 createNumber(((PosContext) first).getToken(instanceIdentifierParser.PositiveIntegerValue, 0)
 446                     .getText())));
 447         }
 448
 449         final int length = expr.getChildCount();
 450         final List<YangExpr> ret = new ArrayList<>(length);
 451         for (int i = 0; i < length; ++i) {
 452             final KeyPredicateExprContext pred = getChild(expr, KeyPredicateContext.class, i)
 453                     .getChild(KeyPredicateExprContext.class, 0);
 454             ret.add(YangBinaryOperator.EQUALS.exprWith(
 455                 YangQNameExpr.of(parseInstanceIdentifierQName(getChild(pred, NodeIdentifierContext.class, 0))),
 456                 parseEqStringValue(getChild(pred, EqQuotedStringContext.class, 1))));
 457
 458         }
 459
 460         return ret;
 461     }
 462
 463     private YangLiteralExpr parseEqStringValue(final EqQuotedStringContext expr) {
 464         return parseLiteral(verifyToken(getChild(expr, QuotedStringContext.class, expr.getChildCount() - 1), 1,
 465             instanceIdentifierParser.STRING).getText());
 466     }
 467
 468     private QName parseInstanceIdentifierQName(final NodeIdentifierContext expr) {
 469         return qnameSupport.createQName(verifyToken(expr, 0, instanceIdentifierParser.Identifier).getText(),
 470             verifyToken(expr, 2, instanceIdentifierParser.Identifier).getText());
 471     }
 472
 473     private YangLiteralExpr parseQNameLiteral(final String text) {
 474         final int firstColon = text.indexOf(':');
 475         if (firstColon != -1) {
 476             // If we have two colons this node cannot be interpreted as a QName -- this may explode at evaluation-time,
 477             // but that's fine as it will just result in evaluation error. Users do have unit tests, right?
 478             final int secondColon = text.indexOf(':', firstColon + 1);
 479             if (secondColon == -1) {
 480                 final Optional<QNameModule> optNamespace = qnameSupport.resolvePrefix(text.substring(0, firstColon));
 481                 // If we cannot resolve the namespace at evaluation-time has to deal with it.
 482                 if (optNamespace.isPresent()) {
 483                     try {
 484                         return new QNameLiteralExpr(text, QName.create(optNamespace.get(),
 485                             text.substring(firstColon + 1)));
 486                     } catch (IllegalArgumentException e) {
 487                         LOG.trace("Cannot interpret {} as a QName", text, e);
 488                         return YangLiteralExpr.of(text);
 489                     }
 490                 }
 491             }
 492         }
 493         return YangLiteralExpr.of(text);
 494     }
 495
 496     private YangExpr parseUnary(final UnaryExprNoRootContext expr) {
 497         // any number of '-' and an union expr
 498         final int size = verifyAtLeastChildren(expr, 1);
 499         final YangExpr ret = parseUnion(getChild(expr, UnionExprNoRootContext.class, size - 1));
 500         if (size % 2 != 0) {
 501             // Even number of '-' tokens cancel out
 502             return ret;
 503         }
 504
 505         return ret instanceof YangNumberExpr ? negateNumber((N) ret) : YangNegateExpr.of(ret);
 506     }
 507
 508     private YangExpr parseUnion(final UnionExprNoRootContext expr) {
 509         final ParseTree first = expr.getChild(0);
 510         final YangExpr path;
 511         if (first instanceof PathExprNoRootContext) {
 512             path = parsePathExpr((PathExprNoRootContext) first);
 513             if (expr.getChildCount() == 1) {
 514                 return path;
 515             }
 516         } else {
 517             path = YangLocationPath.root();
 518         }
 519
 520         verifyChildCount(expr, 3);
 521         final YangExpr union = parseUnion(getChild(expr, UnionExprNoRootContext.class, 2));
 522
 523         // Deduplicate expressions so we do not perform useless unioning
 524         final Set<YangExpr> expressions = new LinkedHashSet<>();
 525         expressions.add(path);
 526         if (union instanceof YangNaryExpr) {
 527             // If the result is a union expression, integrate it into this expression
 528             final YangNaryExpr nary = (YangNaryExpr) union;
 529             if (nary.getOperator() == YangNaryOperator.UNION) {
 530                 expressions.addAll(nary.getExpressions());
 531             } else {
 532                 expressions.add(union);
 533             }
 534         } else {
 535             expressions.add(union);
 536         }
 537
 538         return YangNaryOperator.UNION.exprWith(expressions);
 539     }
 540
 541     private YangExpr parseAdditiveExpr(final YangExpr left, final Iterator<ParseTree> it) {
 542         YangExpr ret = left;
 543         do {
 544             final YangBinaryOperator operator = nextOperator(it);
 545             final YangExpr right = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 546             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 547             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 548         } while (it.hasNext());
 549
 550         return ret;
 551     }
 552
 553     private Optional<YangExpr> simplifyNumbers(final YangBinaryOperator operator, final YangExpr left,
 554             final YangExpr right) {
 555         if (left instanceof YangNumberExpr && right instanceof YangNumberExpr) {
 556             // Constant folding on numbers -- precision plays a role here
 557             return simplifyNumbers(operator, (N) left, (N) right);
 558         }
 559         return Optional.empty();
 560     }
 561
 562     Optional<YangExpr> simplifyNumbers(final YangBinaryOperator operator, final N left, final N right) {
 563         switch (operator) {
 564             case EQUALS:
 565                 return Optional.of(YangBooleanConstantExpr.of(left.getNumber().equals(right.getNumber())));
 566             case NOT_EQUALS:
 567                 return Optional.of(YangBooleanConstantExpr.of(!left.getNumber().equals(right.getNumber())));
 568             default:
 569                 return Optional.empty();
 570         }
 571     }
 572
 573     private YangExpr parseEqualityExpr(final YangExpr left, final Iterator<ParseTree> it) {
 574         YangExpr ret = left;
 575         do {
 576             final YangBinaryOperator operator = nextOperator(it);
 577             final YangExpr right = parseRelational(nextContext(it, RelationalExprContext.class));
 578
 579             if (left.equals(right)) {
 580                 // Constant folding on expression level: equal expressions are result in equal results
 581                 switch (operator) {
 582                     case EQUALS:
 583                         return YangBooleanConstantExpr.TRUE;
 584                     case NOT_EQUALS:
 585                         return YangBooleanConstantExpr.FALSE;
 586                     default:
 587                         break;
 588                 }
 589             }
 590
 591             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 592             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 593         } while (it.hasNext());
 594
 595         return ret;
 596     }
 597
 598     private YangExpr parseRelationalExpr(final YangExpr left, final Iterator<ParseTree> it) {
 599         YangExpr ret = left;
 600         do {
 601             final YangBinaryOperator operator = nextOperator(it);
 602             final YangExpr right = parseAdditive(nextContext(it, AdditiveExprContext.class));
 603             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 604             ret = simple.isPresent() ? simple.get() : nextOperator(it).exprWith(ret, right);
 605         } while (it.hasNext());
 606
 607         return ret;
 608     }
 609
 610     private QName parseQName(final QNameContext expr) {
 611         switch (expr.getChildCount()) {
 612             case 1:
 613                 return qnameSupport.createQName(getChild(expr, NCNameContext.class, 0).getText());
 614             case 3:
 615                 return qnameSupport.createQName(getChild(expr, NCNameContext.class, 0).getText(),
 616                     getChild(expr, NCNameContext.class, 2).getText());
 617             default:
 618                 throw illegalShape(expr);
 619         }
 620     }
 621
 622     private Step parseStep(final StepContext expr) {
 623         if (expr.getChildCount() == 1) {
 624             final AbbreviatedStepContext abbrev = getChild(expr, AbbreviatedStepContext.class, 0);
 625             verifyChildCount(abbrev, 1);
 626             switch (getTerminalType(abbrev, 0)) {
 627                 case xpathParser.DOT:
 628                     return YangXPathAxis.SELF.asStep();
 629                 case xpathParser.DOTDOT:
 630                     return YangXPathAxis.PARENT.asStep();
 631                 default:
 632                     throw illegalShape(abbrev);
 633             }
 634         }
 635
 636         final int size = verifyAtLeastChildren(expr, 2);
 637         final List<YangExpr> predicates = new ArrayList<>(size - 2);
 638         for (int i = 2; i < size; ++i) {
 639             predicates.add(parsePredicate(getChild(expr, PredicateContext.class, i)));
 640         }
 641
 642         final YangXPathAxis axis = parseAxis(getChild(expr, AxisSpecifierContext.class, 0));
 643         final NodeTestContext nodeTest = getChild(expr, NodeTestContext.class, 1);
 644         switch (nodeTest.getChildCount()) {
 645             case 1:
 646                 final NameTestContext nameChild = getChild(nodeTest, NameTestContext.class, 0);
 647                 final ParseTree first = nameChild.getChild(0);
 648                 if (first instanceof TerminalNode) {
 649                     verify(((TerminalNode) first).getSymbol().getType() == xpathParser.MUL);
 650                     return axis.asStep(predicates);
 651                 }
 652                 return axis.asStep(parseQName(verifyTree(QNameContext.class, first)), predicates);
 653             case 3:
 654                 return axis.asStep(parseNodeType(nodeTest.getChild(0)), predicates);
 655             case 4:
 656                 final String text = verifyToken(nodeTest, 2, xpathParser.Literal).getText();
 657                 return axis.asStep(text.substring(1, text.length() - 1), predicates);
 658             default:
 659                 throw illegalShape(nodeTest);
 660         }
 661     }
 662
 663     private static YangXPathAxis parseAxis(final AxisSpecifierContext expr) {
 664         switch (expr.getChildCount()) {
 665             case 0:
 666                 return YangXPathAxis.CHILD;
 667             case 1:
 668                 verify(getTerminalType(expr, 0) == xpathParser.AT, "Unhandled axis specifier shape %s", expr);
 669                 return YangXPathAxis.ATTRIBUTE;
 670             case 2:
 671                 final String str = verifyTerminal(expr.getChild(0)).getText();
 672                 return verifyNotNull(XPATH_AXES.get(str), "Unhandled axis %s", str);
 673             default:
 674                 throw illegalShape(expr);
 675         }
 676     }
 677
 678     private static <T extends ParserRuleContext> T nextContext(final Iterator<ParseTree> it, final Class<T> type) {
 679         return verifyTree(type, it.next());
 680     }
 681
 682     private static YangBinaryOperator nextOperator(final Iterator<ParseTree> it) {
 683         return parseOperator(it.next());
 684     }
 685
 686     private static <T extends ParseTree> T getChild(final ParseTree parent, final Class<T> type, final int offset) {
 687         return verifyTree(type, parent.getChild(offset));
 688     }
 689
 690     private static Token verifyToken(final ParseTree parent, final int offset, final int expected) {
 691         final TerminalNode node = verifyTerminal(parent.getChild(offset));
 692         final Token ret = node.getSymbol();
 693         final int type = ret.getType();
 694         verify(type == expected, "Item %s has type %s, expected %s", node, type, expected);
 695         return ret;
 696     }
 697
 698     private static int getTerminalType(final ParseTree parent, final int offset) {
 699         return verifyTerminal(parent.getChild(offset)).getSymbol().getType();
 700     }
 701
 702     private static YangXPathNodeType parseNodeType(final ParseTree tree) {
 703         final String str = verifyTerminal(tree).getText();
 704         return verifyNotNull(NODE_TYPES.get(str), "Unhandled node type %s", str);
 705     }
 706
 707     private static YangBinaryOperator parseOperator(final ParseTree tree) {
 708         final String str = verifyTerminal(tree).getText();
 709         return verifyNotNull(BINARY_OPERATORS.get(str), "Unhandled operator %s", str);
 710     }
 711
 712     private static void verifyChildCount(final ParseTree tree, final int expected) {
 713         if (tree.getChildCount() != expected) {
 714             throw illegalShape(tree);
 715         }
 716     }
 717
 718     private static int verifyAtLeastChildren(final ParseTree tree, final int expected) {
 719         final int count = tree.getChildCount();
 720         if (count < expected) {
 721             throw illegalShape(tree);
 722         }
 723         return count;
 724     }
 725
 726     private static TerminalNode verifyTerminal(final ParseTree tree) {
 727         if (tree instanceof TerminalNode) {
 728             return (TerminalNode) tree;
 729         }
 730         throw new VerifyException(String.format("'%s' is not a terminal node", tree.getText()));
 731     }
 732
 733     private static <T extends ParseTree> T verifyTree(final Class<T> type, final ParseTree tree) {
 734         if (type.isInstance(tree)) {
 735             return type.cast(tree);
 736         }
 737         throw new VerifyException(String.format("'%s' does not have expected type %s", tree.getText(), type));
 738     }
 739
 740     private static VerifyException illegalShape(final ParseTree tree) {
 741         return new VerifyException(String.format("Invalid parser shape of '%s'", tree.getText()));
 742     }
 743 }