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