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