yang/yang-xpath-impl/src/main/java/org/opendaylight/yangtools/yang/xpath/impl/AntlrXPathParser.java

   1 /*
   2  * Copyright (c) 2018 Pantheon Technologies, s.r.o.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.xpath.impl;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static com.google.common.base.Verify.verifyNotNull;
  13 import static java.util.Objects.requireNonNull;
  14 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.getChild;
  15 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.illegalShape;
  16 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyAtLeastChildren;
  17 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyChildCount;
  18 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyTerminal;
  19 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyToken;
  20 import static org.opendaylight.yangtools.yang.xpath.impl.ParseTreeUtils.verifyTree;
  21
  22 import com.google.common.collect.ImmutableList;
  23 import com.google.common.collect.Iterators;
  24 import com.google.common.collect.Lists;
  25 import com.google.common.collect.Maps;
  26 import java.util.ArrayDeque;
  27 import java.util.ArrayList;
  28 import java.util.Arrays;
  29 import java.util.Deque;
  30 import java.util.Iterator;
  31 import java.util.LinkedHashSet;
  32 import java.util.List;
  33 import java.util.Map;
  34 import java.util.Optional;
  35 import java.util.Set;
  36 import javax.xml.xpath.XPathExpressionException;
  37 import org.antlr.v4.runtime.CharStreams;
  38 import org.antlr.v4.runtime.CommonTokenStream;
  39 import org.antlr.v4.runtime.ParserRuleContext;
  40 import org.antlr.v4.runtime.tree.ParseTree;
  41 import org.antlr.v4.runtime.tree.TerminalNode;
  42 import org.opendaylight.yangtools.yang.common.QName;
  43 import org.opendaylight.yangtools.yang.common.YangConstants;
  44 import org.opendaylight.yangtools.yang.common.YangNamespaceContext;
  45 import org.opendaylight.yangtools.yang.xpath.api.YangBinaryOperator;
  46 import org.opendaylight.yangtools.yang.xpath.api.YangBooleanConstantExpr;
  47 import org.opendaylight.yangtools.yang.xpath.api.YangExpr;
  48 import org.opendaylight.yangtools.yang.xpath.api.YangFilterExpr;
  49 import org.opendaylight.yangtools.yang.xpath.api.YangFunction;
  50 import org.opendaylight.yangtools.yang.xpath.api.YangFunctionCallExpr;
  51 import org.opendaylight.yangtools.yang.xpath.api.YangLiteralExpr;
  52 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath;
  53 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.AxisStep;
  54 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.Step;
  55 import org.opendaylight.yangtools.yang.xpath.api.YangNaryExpr;
  56 import org.opendaylight.yangtools.yang.xpath.api.YangNaryOperator;
  57 import org.opendaylight.yangtools.yang.xpath.api.YangNegateExpr;
  58 import org.opendaylight.yangtools.yang.xpath.api.YangNumberExpr;
  59 import org.opendaylight.yangtools.yang.xpath.api.YangPathExpr;
  60 import org.opendaylight.yangtools.yang.xpath.api.YangVariableReferenceExpr;
  61 import org.opendaylight.yangtools.yang.xpath.api.YangXPathAxis;
  62 import org.opendaylight.yangtools.yang.xpath.api.YangXPathExpression;
  63 import org.opendaylight.yangtools.yang.xpath.api.YangXPathMathMode;
  64 import org.opendaylight.yangtools.yang.xpath.api.YangXPathMathSupport;
  65 import org.opendaylight.yangtools.yang.xpath.api.YangXPathNodeType;
  66 import org.opendaylight.yangtools.yang.xpath.api.YangXPathParser;
  67 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AbbreviatedStepContext;
  68 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AbsoluteLocationPathNorootContext;
  69 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AdditiveExprContext;
  70 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AndExprContext;
  71 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.AxisSpecifierContext;
  72 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.EqualityExprContext;
  73 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.ExprContext;
  74 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FilterExprContext;
  75 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FunctionCallContext;
  76 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.FunctionNameContext;
  77 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.LocationPathContext;
  78 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.MultiplicativeExprContext;
  79 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NCNameContext;
  80 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NameTestContext;
  81 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.NodeTestContext;
  82 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.OrExprContext;
  83 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PathExprNoRootContext;
  84 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PredicateContext;
  85 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.PrimaryExprContext;
  86 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.QNameContext;
  87 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.RelationalExprContext;
  88 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.RelativeLocationPathContext;
  89 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.StepContext;
  90 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.UnaryExprNoRootContext;
  91 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.UnionExprNoRootContext;
  92 import org.opendaylight.yangtools.yang.xpath.impl.xpathParser.VariableReferenceContext;
  93 import org.slf4j.Logger;
  94 import org.slf4j.LoggerFactory;
  95
  96 /**
  97  * ANTLR-based XPath parser. Uses {@code xpath.g4} ANTLR grammar.
  98  *
  99  * @author Robert Varga
 100  */
 101 final class AntlrXPathParser implements YangXPathParser {
 102     private static final Logger LOG = LoggerFactory.getLogger(AntlrXPathParser.class);
 103     private static final Map<String, YangBinaryOperator> BINARY_OPERATORS = Maps.uniqueIndex(
 104         Arrays.asList(YangBinaryOperator.values()), YangBinaryOperator::toString);
 105     private static final Map<String, YangXPathNodeType> NODE_TYPES = Maps.uniqueIndex(Arrays.asList(
 106         YangXPathNodeType.values()), YangXPathNodeType::toString);
 107     private static final Map<String, YangXPathAxis> XPATH_AXES = Maps.uniqueIndex(Arrays.asList(YangXPathAxis.values()),
 108         YangXPathAxis::toString);
 109     private static final Map<QName, YangFunction> YANG_FUNCTIONS = Maps.uniqueIndex(Arrays.asList(
 110         YangFunction.values()), YangFunction::getIdentifier);
 111
 112     // Cached for checks in hot path
 113     private static final AxisStep SELF_STEP = YangXPathAxis.SELF.asStep();
 114
 115     private final YangXPathMathMode mathMode;
 116     private final YangXPathMathSupport mathSupport;
 117     private final YangNamespaceContext namespaceContext;
 118     private final FunctionSupport functionSupport;
 119
 120     AntlrXPathParser(final YangXPathMathMode mathMode, final YangNamespaceContext namespaceContext) {
 121         this.mathMode = requireNonNull(mathMode);
 122         this.mathSupport = mathMode.getSupport();
 123         this.namespaceContext = requireNonNull(namespaceContext);
 124         this.functionSupport = new FunctionSupport(namespaceContext, mathSupport);
 125     }
 126
 127     @Override
 128     public YangXPathExpression parseExpression(final String xpath) throws XPathExpressionException {
 129         // Create a parser and disconnect it from console error output
 130         final xpathLexer lexer = new xpathLexer(CharStreams.fromString(xpath));
 131         final xpathParser parser = new xpathParser(new CommonTokenStream(lexer));
 132
 133         final CapturingErrorListener listener = new CapturingErrorListener();
 134         lexer.removeErrorListeners();
 135         lexer.addErrorListener(listener);
 136         parser.removeErrorListeners();
 137         parser.addErrorListener(listener);
 138
 139         final YangExpr expr = parseExpr(parser.main().expr());
 140         listener.reportError();
 141         return new AntlrYangXPathExpression(namespaceContext, mathMode, expr, xpath);
 142     }
 143
 144     /**
 145      * Parse and simplify an XPath expression in {@link ExprContext} representation.
 146      *
 147      * @param expr ANTLR ExprContext
 148      * @return A {@link YangExpr}
 149      * @throws NullPointerException if {@code expr} is null
 150      * @throws IllegalArgumentException if {@code expr} references an unbound prefix
 151      */
 152     private YangExpr parseExpr(final ExprContext expr) {
 153         final OrExprContext or = expr.orExpr();
 154         final int size = or.getChildCount();
 155         if (size == 1) {
 156             return parseAnd(getChild(or, AndExprContext.class, 0));
 157         }
 158         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 159         for (int i = 0; i < size; i += 2) {
 160             tmp.add(parseAnd(getChild(or, AndExprContext.class, i)));
 161         }
 162         return YangNaryOperator.OR.exprWith(tmp);
 163     }
 164
 165     private YangExpr parseAdditive(final AdditiveExprContext expr) {
 166         final Iterator<ParseTree> it = expr.children.iterator();
 167         final YangExpr first = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 168         return it.hasNext() ? parseAdditiveExpr(first, it) : first;
 169     }
 170
 171     private YangExpr parseAnd(final AndExprContext expr) {
 172         final int size = expr.getChildCount();
 173         if (size == 1) {
 174             return parseEquality(getChild(expr, EqualityExprContext.class, 0));
 175         }
 176         final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
 177         for (int i = 0; i < size; i += 2) {
 178             tmp.add(parseEquality(getChild(expr, EqualityExprContext.class, i)));
 179         }
 180         return YangNaryOperator.AND.exprWith(tmp);
 181     }
 182
 183     private YangExpr parseEquality(final EqualityExprContext expr) {
 184         final Iterator<ParseTree> it = expr.children.iterator();
 185         final YangExpr first = parseRelational(nextContext(it, RelationalExprContext.class));
 186         return it.hasNext() ? parseEqualityExpr(first, it) : first;
 187     }
 188
 189     private YangExpr parseFilter(final FilterExprContext expr) {
 190         final Iterator<ParseTree> it = expr.children.iterator();
 191         final YangExpr first = parsePrimary(nextContext(it, PrimaryExprContext.class));
 192         return it.hasNext() ? YangFilterExpr.of(first, ImmutableList.copyOf(Iterators.transform(it,
 193             tree ->  parsePredicate(verifyTree(PredicateContext.class, tree)))))
 194                 : first;
 195     }
 196
 197     private YangExpr parseFunctionCall(final FunctionCallContext expr) {
 198         // We are mapping functions to RFC7950 YIN namespace, to keep us consistent with type/statement definitions
 199
 200         final FunctionNameContext name = getChild(expr, FunctionNameContext.class, 0);
 201         final QName parsed;
 202         switch (name.getChildCount()) {
 203             case 1:
 204                 parsed = QName.create(YangConstants.RFC6020_YIN_MODULE, name.getChild(0).getText());
 205                 break;
 206             case 3:
 207                 parsed = namespaceContext.createQName(name.getChild(0).getText(), name.getChild(2).getText());
 208                 break;
 209             default:
 210                 throw illegalShape(name);
 211         }
 212
 213         final List<YangExpr> args = ImmutableList.copyOf(Lists.transform(expr.expr(), this::parseExpr));
 214         final YangFunction func = YANG_FUNCTIONS.get(parsed);
 215         if (func != null) {
 216             return functionSupport.functionToExpr(func, args);
 217         }
 218
 219         checkArgument(!YangConstants.RFC6020_YIN_MODULE.equals(parsed.getModule()), "Unknown default function %s",
 220             parsed);
 221         return YangFunctionCallExpr.of(parsed, args);
 222     }
 223
 224     private YangLocationPath parseLocationPath(final LocationPathContext expr) {
 225         verifyChildCount(expr, 1);
 226         final ParseTree first = expr.getChild(0);
 227         if (first instanceof RelativeLocationPathContext) {
 228             return parseRelativeLocationPath((RelativeLocationPathContext) first);
 229         }
 230
 231         final AbsoluteLocationPathNorootContext abs = verifyTree(AbsoluteLocationPathNorootContext.class, first);
 232         verifyChildCount(abs, 2);
 233
 234         final Deque<Step> steps = parseLocationPathSteps(getChild(abs, RelativeLocationPathContext.class, 1));
 235         parseStepShorthand(abs.getChild(0)).ifPresent(steps::addFirst);
 236
 237         return YangLocationPath.of(true, steps);
 238     }
 239
 240     private YangExpr parseMultiplicative(final MultiplicativeExprContext expr) {
 241         final ParseTree first = expr.getChild(0);
 242         final YangExpr left;
 243         if (first instanceof UnaryExprNoRootContext) {
 244             left = parseUnary((UnaryExprNoRootContext) first);
 245         } else {
 246             left = YangLocationPath.root();
 247         }
 248         if (expr.getChildCount() == 1) {
 249             return left;
 250         }
 251
 252         verifyChildCount(expr, 3);
 253         final YangBinaryOperator operator = parseOperator(expr.getChild(1));
 254         final YangExpr right = parseMultiplicative(getChild(expr, MultiplicativeExprContext.class, 2));
 255         final Optional<YangExpr> simple = simplifyNumbers(operator, left, right);
 256         return simple.isPresent() ? simple.get() : operator.exprWith(left, right);
 257     }
 258
 259     private YangExpr parsePathExpr(final PathExprNoRootContext expr) {
 260         final ParseTree first = expr.getChild(0);
 261         if (first instanceof LocationPathContext) {
 262             return parseLocationPath((LocationPathContext) first);
 263         }
 264
 265         final YangExpr filter = parseFilter(verifyTree(FilterExprContext.class, first));
 266         if (expr.getChildCount() == 1) {
 267             return filter;
 268         }
 269
 270         verifyChildCount(expr, 3);
 271         final Deque<Step> steps = parseLocationPathSteps(getChild(expr, RelativeLocationPathContext.class, 2));
 272         parseStepShorthand(expr.getChild(1)).ifPresent(steps::addFirst);
 273         return YangPathExpr.of(filter, YangLocationPath.of(false, steps));
 274     }
 275
 276     private YangExpr parsePredicate(final PredicateContext expr) {
 277         verifyChildCount(expr, 3);
 278         return parseExpr(getChild(expr, ExprContext.class, 1));
 279     }
 280
 281     private YangExpr parsePrimary(final PrimaryExprContext expr) {
 282         if (expr.getChildCount() == 3) {
 283             return parseExpr(getChild(expr, ExprContext.class, 1));
 284         }
 285
 286         verifyChildCount(expr, 1);
 287         final ParseTree first = expr.getChild(0);
 288         if (first instanceof TerminalNode) {
 289             return parseTerminal((TerminalNode) first);
 290         }
 291         if (first instanceof FunctionCallContext) {
 292             return parseFunctionCall((FunctionCallContext) first);
 293         }
 294         if (first instanceof VariableReferenceContext) {
 295             return YangVariableReferenceExpr.of(parseQName(((VariableReferenceContext) first).qName()));
 296         }
 297         throw illegalShape(first);
 298     }
 299
 300     private YangExpr parseRelational(final RelationalExprContext expr) {
 301         final Iterator<ParseTree> it = expr.children.iterator();
 302         final YangExpr first = parseAdditive(nextContext(it, AdditiveExprContext.class));
 303         return it.hasNext() ? parseRelationalExpr(first, it) : first;
 304     }
 305
 306     private Deque<Step> parseLocationPathSteps(final RelativeLocationPathContext expr) {
 307         final Deque<Step> steps = new ArrayDeque<>(expr.getChildCount());
 308         final Iterator<ParseTree> it = expr.children.iterator();
 309         steps.add(parseStep(nextContext(it, StepContext.class)));
 310
 311         while (it.hasNext()) {
 312             parseStepShorthand(it.next()).ifPresent(steps::add);
 313
 314             // Parse step and add it if it's not SELF_STEP
 315             final Step step = parseStep(nextContext(it, StepContext.class));
 316             if (!SELF_STEP.equals(step)) {
 317                 steps.add(step);
 318             }
 319         }
 320
 321         return steps;
 322     }
 323
 324     private YangLocationPath parseRelativeLocationPath(final RelativeLocationPathContext expr) {
 325         return YangLocationPath.of(false, parseLocationPathSteps(expr));
 326     }
 327
 328     private YangExpr parseTerminal(final TerminalNode term) {
 329         final String text = term.getText();
 330         switch (term.getSymbol().getType()) {
 331             case xpathParser.Literal:
 332                 // We have to strip quotes
 333                 return YangLiteralExpr.of(text.substring(1, text.length() - 1));
 334             case xpathParser.Number:
 335                 return mathSupport.createNumber(text);
 336             default:
 337                 throw illegalShape(term);
 338         }
 339     }
 340
 341     private YangExpr parseUnary(final UnaryExprNoRootContext expr) {
 342         // any number of '-' and an union expr
 343         final int size = verifyAtLeastChildren(expr, 1);
 344         final YangExpr ret = parseUnion(getChild(expr, UnionExprNoRootContext.class, size - 1));
 345         if (size % 2 != 0) {
 346             // Even number of '-' tokens cancel out
 347             return ret;
 348         }
 349         return ret instanceof YangNumberExpr ? mathSupport.negateNumber((YangNumberExpr) ret) : YangNegateExpr.of(ret);
 350     }
 351
 352     private YangExpr parseUnion(final UnionExprNoRootContext expr) {
 353         final ParseTree first = expr.getChild(0);
 354         final YangExpr path;
 355         if (first instanceof PathExprNoRootContext) {
 356             path = parsePathExpr((PathExprNoRootContext) first);
 357             if (expr.getChildCount() == 1) {
 358                 return path;
 359             }
 360         } else {
 361             path = YangLocationPath.root();
 362         }
 363
 364         verifyChildCount(expr, 3);
 365         final YangExpr union = parseUnion(getChild(expr, UnionExprNoRootContext.class, 2));
 366
 367         // Deduplicate expressions so we do not perform useless unioning
 368         final Set<YangExpr> expressions = new LinkedHashSet<>();
 369         expressions.add(path);
 370         if (union instanceof YangNaryExpr) {
 371             // If the result is a union expression, integrate it into this expression
 372             final YangNaryExpr nary = (YangNaryExpr) union;
 373             if (nary.getOperator() == YangNaryOperator.UNION) {
 374                 expressions.addAll(nary.getExpressions());
 375             } else {
 376                 expressions.add(union);
 377             }
 378         } else {
 379             expressions.add(union);
 380         }
 381
 382         return YangNaryOperator.UNION.exprWith(expressions);
 383     }
 384
 385     private YangExpr parseAdditiveExpr(final YangExpr left, final Iterator<ParseTree> it) {
 386         YangExpr ret = left;
 387         do {
 388             final YangBinaryOperator operator = nextOperator(it);
 389             final YangExpr right = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
 390             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 391             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 392         } while (it.hasNext());
 393
 394         return ret;
 395     }
 396
 397     private Optional<YangExpr> simplifyNumbers(final YangBinaryOperator operator, final YangExpr left,
 398             final YangExpr right) {
 399         if (left instanceof YangNumberExpr && right instanceof YangNumberExpr) {
 400             // Constant folding on numbers -- precision plays a role here
 401             return mathSupport.tryEvaluate(operator, (YangNumberExpr)left, (YangNumberExpr)right);
 402         }
 403         return Optional.empty();
 404     }
 405
 406     private YangExpr parseEqualityExpr(final YangExpr left, final Iterator<ParseTree> it) {
 407         YangExpr ret = left;
 408         do {
 409             final YangBinaryOperator operator = nextOperator(it);
 410             final YangExpr right = parseRelational(nextContext(it, RelationalExprContext.class));
 411
 412             if (left.equals(right)) {
 413                 // Constant folding on expression level: equal expressions are result in equal results
 414                 switch (operator) {
 415                     case EQUALS:
 416                         return YangBooleanConstantExpr.TRUE;
 417                     case NOT_EQUALS:
 418                         return YangBooleanConstantExpr.FALSE;
 419                     default:
 420                         break;
 421                 }
 422             }
 423
 424             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 425             ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
 426         } while (it.hasNext());
 427
 428         return ret;
 429     }
 430
 431     private YangExpr parseRelationalExpr(final YangExpr left, final Iterator<ParseTree> it) {
 432         YangExpr ret = left;
 433         do {
 434             final YangBinaryOperator operator = nextOperator(it);
 435             final YangExpr right = parseAdditive(nextContext(it, AdditiveExprContext.class));
 436             final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
 437             ret = simple.isPresent() ? simple.get() : nextOperator(it).exprWith(ret, right);
 438         } while (it.hasNext());
 439
 440         return ret;
 441     }
 442
 443     private QName parseQName(final QNameContext expr) {
 444         switch (expr.getChildCount()) {
 445             case 1:
 446                 return namespaceContext.createQName(getChild(expr, NCNameContext.class, 0).getText());
 447             case 3:
 448                 return namespaceContext.createQName(getChild(expr, NCNameContext.class, 0).getText(),
 449                     getChild(expr, NCNameContext.class, 2).getText());
 450             default:
 451                 throw illegalShape(expr);
 452         }
 453     }
 454
 455     private Step parseStep(final StepContext expr) {
 456         if (expr.getChildCount() == 1) {
 457             final AbbreviatedStepContext abbrev = getChild(expr, AbbreviatedStepContext.class, 0);
 458             verifyChildCount(abbrev, 1);
 459             switch (getTerminalType(abbrev, 0)) {
 460                 case xpathParser.DOT:
 461                     return YangXPathAxis.SELF.asStep();
 462                 case xpathParser.DOTDOT:
 463                     return YangXPathAxis.PARENT.asStep();
 464                 default:
 465                     throw illegalShape(abbrev);
 466             }
 467         }
 468
 469         final int size = verifyAtLeastChildren(expr, 2);
 470         final List<YangExpr> predicates = new ArrayList<>(size - 2);
 471         for (int i = 2; i < size; ++i) {
 472             predicates.add(parsePredicate(getChild(expr, PredicateContext.class, i)));
 473         }
 474
 475         final YangXPathAxis axis = parseAxis(getChild(expr, AxisSpecifierContext.class, 0));
 476         final NodeTestContext nodeTest = getChild(expr, NodeTestContext.class, 1);
 477         switch (nodeTest.getChildCount()) {
 478             case 1:
 479                 final NameTestContext nameChild = getChild(nodeTest, NameTestContext.class, 0);
 480                 final ParseTree first = nameChild.getChild(0);
 481                 if (first instanceof TerminalNode) {
 482                     verify(((TerminalNode) first).getSymbol().getType() == xpathParser.MUL);
 483                     return axis.asStep(predicates);
 484                 }
 485                 return axis.asStep(parseQName(verifyTree(QNameContext.class, first)), predicates);
 486             case 3:
 487                 return axis.asStep(parseNodeType(nodeTest.getChild(0)), predicates);
 488             case 4:
 489                 final String text = verifyToken(nodeTest, 2, xpathParser.Literal).getText();
 490                 return axis.asStep(text.substring(1, text.length() - 1), predicates);
 491             default:
 492                 throw illegalShape(nodeTest);
 493         }
 494     }
 495
 496     private static YangXPathAxis parseAxis(final AxisSpecifierContext expr) {
 497         switch (expr.getChildCount()) {
 498             case 0:
 499                 return YangXPathAxis.CHILD;
 500             case 1:
 501                 verify(getTerminalType(expr, 0) == xpathParser.AT, "Unhandled axis specifier shape %s", expr);
 502                 return YangXPathAxis.ATTRIBUTE;
 503             case 2:
 504                 final String str = verifyTerminal(expr.getChild(0)).getText();
 505                 return verifyNotNull(XPATH_AXES.get(str), "Unhandled axis %s", str);
 506             default:
 507                 throw illegalShape(expr);
 508         }
 509     }
 510
 511     private static <T extends ParserRuleContext> T nextContext(final Iterator<ParseTree> it, final Class<T> type) {
 512         return verifyTree(type, it.next());
 513     }
 514
 515     private static YangBinaryOperator nextOperator(final Iterator<ParseTree> it) {
 516         return parseOperator(it.next());
 517     }
 518
 519     private static int getTerminalType(final ParseTree parent, final int offset) {
 520         return verifyTerminal(parent.getChild(offset)).getSymbol().getType();
 521     }
 522
 523     private static YangXPathNodeType parseNodeType(final ParseTree tree) {
 524         final String str = verifyTerminal(tree).getText();
 525         return verifyNotNull(NODE_TYPES.get(str), "Unhandled node type %s", str);
 526     }
 527
 528     private static YangBinaryOperator parseOperator(final ParseTree tree) {
 529         final String str = verifyTerminal(tree).getText();
 530         return verifyNotNull(BINARY_OPERATORS.get(str), "Unhandled operator %s", str);
 531     }
 532
 533     private static Optional<Step> parseStepShorthand(final ParseTree tree) {
 534         switch (verifyTerminal(tree).getSymbol().getType()) {
 535             case xpathParser.PATHSEP:
 536                 return Optional.empty();
 537             case xpathParser.ABRPATH:
 538                 return Optional.of(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
 539             default:
 540                 throw illegalShape(tree);
 541         }
 542     }
 543 }