2 * Copyright (c) 2018 Pantheon Technologies, s.r.o. All rights reserved.
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
8 package org.opendaylight.yangtools.yang.xpath.impl;
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;
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;
34 import java.util.Optional;
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;
100 * ANTLR-based XPath parser. Uses {@code xpath.g4} ANTLR grammar.
102 * @author Robert Varga
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);
115 // Cached for checks in hot path
116 private static final AxisStep SELF_STEP = YangXPathAxis.SELF.asStep();
118 private final YangXPathMathMode mathMode;
119 private final YangXPathMathSupport mathSupport;
120 private final YangNamespaceContext namespaceContext;
121 private final FunctionSupport functionSupport;
123 AntlrXPathParser(final YangXPathMathMode mathMode, final YangNamespaceContext namespaceContext) {
124 this.mathMode = requireNonNull(mathMode);
125 this.mathSupport = mathMode.getSupport();
126 this.namespaceContext = requireNonNull(namespaceContext);
127 this.functionSupport = new FunctionSupport(namespaceContext, mathSupport);
131 public YangXPathExpression parseExpression(final String xpath) throws XPathExpressionException {
132 // Create a parser and disconnect it from console error output
133 final xpathLexer lexer = new xpathLexer(CharStreams.fromString(xpath));
134 final xpathParser parser = new xpathParser(new CommonTokenStream(lexer));
136 final List<XPathExpressionException> errors = new ArrayList<>();
137 final BaseErrorListener listener = new BaseErrorListener() {
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);
144 if (errors.isEmpty()) {
147 errors.get(0).addSuppressed(ex);
152 lexer.removeErrorListeners();
153 lexer.addErrorListener(listener);
154 parser.removeErrorListeners();
155 parser.addErrorListener(listener);
157 final YangExpr expr = parseExpr(parser.main().expr());
158 if (!errors.isEmpty()) {
162 return new AntlrYangXPathExpression(namespaceContext, mathMode, expr, xpath);
166 * Parse and simplify an XPath expression in {@link ExprContext} representation.
168 * @param expr ANTLR ExprContext
169 * @return A {@link YangExpr}
170 * @throws NullPointerException if {@code expr} is null
171 * @throws IllegalArgumentException if {@code expr} references an unbound prefix
173 private YangExpr parseExpr(final ExprContext expr) {
174 final OrExprContext or = expr.orExpr();
175 final int size = or.getChildCount();
177 return parseAnd(getChild(or, AndExprContext.class, 0));
179 final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
180 for (int i = 0; i < size; i += 2) {
181 tmp.add(parseAnd(getChild(or, AndExprContext.class, i)));
183 return YangNaryOperator.OR.exprWith(tmp);
186 private YangExpr parseAdditive(final AdditiveExprContext expr) {
187 final Iterator<ParseTree> it = expr.children.iterator();
188 final YangExpr first = parseMultiplicative(nextContext(it, MultiplicativeExprContext.class));
189 return it.hasNext() ? parseAdditiveExpr(first, it) : first;
192 private YangExpr parseAnd(final AndExprContext expr) {
193 final int size = expr.getChildCount();
195 return parseEquality(getChild(expr, EqualityExprContext.class, 0));
197 final List<YangExpr> tmp = new ArrayList<>((size + 1) / 2);
198 for (int i = 0; i < size; i += 2) {
199 tmp.add(parseEquality(getChild(expr, EqualityExprContext.class, i)));
201 return YangNaryOperator.AND.exprWith(tmp);
204 private YangExpr parseEquality(final EqualityExprContext expr) {
205 final Iterator<ParseTree> it = expr.children.iterator();
206 final YangExpr first = parseRelational(nextContext(it, RelationalExprContext.class));
207 return it.hasNext() ? parseEqualityExpr(first, it) : first;
210 private YangExpr parseFilter(final FilterExprContext expr) {
211 final Iterator<ParseTree> it = expr.children.iterator();
212 final YangExpr first = parsePrimary(nextContext(it, PrimaryExprContext.class));
213 return it.hasNext() ? YangFilterExpr.of(first, ImmutableList.copyOf(Iterators.transform(it,
214 tree -> parsePredicate(verifyTree(PredicateContext.class, tree)))))
218 private YangExpr parseFunctionCall(final FunctionCallContext expr) {
219 // We are mapping functions to RFC7950 YIN namespace, to keep us consistent with type/statement definitions
221 final FunctionNameContext name = getChild(expr, FunctionNameContext.class, 0);
223 switch (name.getChildCount()) {
225 parsed = QName.create(YangConstants.RFC6020_YIN_MODULE, name.getChild(0).getText());
228 parsed = namespaceContext.createQName(name.getChild(0).getText(), name.getChild(2).getText());
231 throw illegalShape(name);
234 final List<YangExpr> args = ImmutableList.copyOf(Lists.transform(expr.expr(), this::parseExpr));
235 final YangFunction func = YANG_FUNCTIONS.get(parsed);
237 return functionSupport.functionToExpr(func, args);
240 checkArgument(!YangConstants.RFC6020_YIN_MODULE.equals(parsed.getModule()), "Unknown default function %s",
242 return YangFunctionCallExpr.of(parsed, args);
245 private YangLocationPath parseLocationPath(final LocationPathContext expr) {
246 verifyChildCount(expr, 1);
247 final ParseTree first = expr.getChild(0);
248 if (first instanceof RelativeLocationPathContext) {
249 return parseRelativeLocationPath((RelativeLocationPathContext) first);
252 final AbsoluteLocationPathNorootContext abs = verifyTree(AbsoluteLocationPathNorootContext.class, first);
253 verifyChildCount(abs, 2);
255 final Deque<Step> steps = parseLocationPathSteps(getChild(abs, RelativeLocationPathContext.class, 1));
256 switch (getTerminalType(abs, 0)) {
257 case xpathParser.PATHSEP:
259 case xpathParser.ABRPATH:
260 steps.addFirst(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
263 throw illegalShape(abs);
266 return YangLocationPath.of(true, steps);
269 private YangExpr parseMultiplicative(final MultiplicativeExprContext expr) {
270 final ParseTree first = expr.getChild(0);
272 if (first instanceof UnaryExprNoRootContext) {
273 left = parseUnary((UnaryExprNoRootContext) first);
275 left = YangLocationPath.root();
277 if (expr.getChildCount() == 1) {
281 verifyChildCount(expr, 3);
282 final YangBinaryOperator operator = parseOperator(expr.getChild(1));
283 final YangExpr right = parseMultiplicative(getChild(expr, MultiplicativeExprContext.class, 2));
284 final Optional<YangExpr> simple = simplifyNumbers(operator, left, right);
285 return simple.isPresent() ? simple.get() : operator.exprWith(left, right);
288 private YangExpr parsePathExpr(final PathExprNoRootContext expr) {
289 final ParseTree first = expr.getChild(0);
290 if (first instanceof LocationPathContext) {
291 return parseLocationPath((LocationPathContext) first);
294 final YangExpr filter = parseFilter(verifyTree(FilterExprContext.class, first));
295 if (expr.getChildCount() == 1) {
299 verifyChildCount(expr, 3);
300 return parseOperator(expr.getChild(1)).exprWith(filter,
301 parseRelativeLocationPath(getChild(expr, RelativeLocationPathContext.class, 2)));
304 private YangExpr parsePredicate(final PredicateContext expr) {
305 verifyChildCount(expr, 3);
306 return parseExpr(getChild(expr, ExprContext.class, 1));
309 private YangExpr parsePrimary(final PrimaryExprContext expr) {
310 if (expr.getChildCount() == 3) {
311 return parseExpr(getChild(expr, ExprContext.class, 1));
314 verifyChildCount(expr, 1);
315 final ParseTree first = expr.getChild(0);
316 if (first instanceof TerminalNode) {
317 return parseTerminal((TerminalNode) first);
319 if (first instanceof FunctionCallContext) {
320 return parseFunctionCall((FunctionCallContext) first);
322 if (first instanceof VariableReferenceContext) {
323 return YangVariableReferenceExpr.of(parseQName(((VariableReferenceContext) first).qName()));
325 throw illegalShape(first);
328 private YangExpr parseRelational(final RelationalExprContext expr) {
329 final Iterator<ParseTree> it = expr.children.iterator();
330 final YangExpr first = parseAdditive(nextContext(it, AdditiveExprContext.class));
331 return it.hasNext() ? parseRelationalExpr(first, it) : first;
334 private Deque<Step> parseLocationPathSteps(final RelativeLocationPathContext expr) {
335 final Deque<Step> steps = new ArrayDeque<>(expr.getChildCount());
336 final Iterator<ParseTree> it = expr.children.iterator();
337 steps.add(parseStep(nextContext(it, StepContext.class)));
339 while (it.hasNext()) {
340 final ParseTree tree = it.next();
341 switch (verifyTerminal(tree).getSymbol().getType()) {
342 case xpathParser.PATHSEP:
344 case xpathParser.ABRPATH:
345 steps.add(YangXPathAxis.DESCENDANT_OR_SELF.asStep());
348 throw illegalShape(tree);
351 // Parse step and add it if it's not SELF_STEP
352 final Step step = parseStep(nextContext(it, StepContext.class));
353 if (!SELF_STEP.equals(step)) {
361 private YangLocationPath parseRelativeLocationPath(final RelativeLocationPathContext expr) {
362 return YangLocationPath.of(false, parseLocationPathSteps(expr));
365 private YangExpr parseTerminal(final TerminalNode term) {
366 final String text = term.getText();
367 switch (term.getSymbol().getType()) {
368 case xpathParser.Literal:
369 // We have to strip quotes
370 return YangLiteralExpr.of(text.substring(1, text.length() - 1));
371 case xpathParser.Number:
372 return mathSupport.createNumber(text);
374 throw illegalShape(term);
378 private YangExpr parseUnary(final UnaryExprNoRootContext expr) {
379 // any number of '-' and an union expr
380 final int size = verifyAtLeastChildren(expr, 1);
381 final YangExpr ret = parseUnion(getChild(expr, UnionExprNoRootContext.class, size - 1));
383 // Even number of '-' tokens cancel out
386 return ret instanceof YangNumberExpr ? mathSupport.negateNumber((YangNumberExpr) ret) : YangNegateExpr.of(ret);
389 private YangExpr parseUnion(final UnionExprNoRootContext expr) {
390 final ParseTree first = expr.getChild(0);
392 if (first instanceof PathExprNoRootContext) {
393 path = parsePathExpr((PathExprNoRootContext) first);
394 if (expr.getChildCount() == 1) {
398 path = YangLocationPath.root();
401 verifyChildCount(expr, 3);
402 final YangExpr union = parseUnion(getChild(expr, UnionExprNoRootContext.class, 2));
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());
413 expressions.add(union);
416 expressions.add(union);
419 return YangNaryOperator.UNION.exprWith(expressions);
422 private YangExpr parseAdditiveExpr(final YangExpr left, final Iterator<ParseTree> it) {
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());
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);
440 return Optional.empty();
443 private YangExpr parseEqualityExpr(final YangExpr left, final Iterator<ParseTree> it) {
446 final YangBinaryOperator operator = nextOperator(it);
447 final YangExpr right = parseRelational(nextContext(it, RelationalExprContext.class));
449 if (left.equals(right)) {
450 // Constant folding on expression level: equal expressions are result in equal results
453 return YangBooleanConstantExpr.TRUE;
455 return YangBooleanConstantExpr.FALSE;
461 final Optional<YangExpr> simple = simplifyNumbers(operator, ret, right);
462 ret = simple.isPresent() ? simple.get() : operator.exprWith(ret, right);
463 } while (it.hasNext());
468 private YangExpr parseRelationalExpr(final YangExpr left, final Iterator<ParseTree> it) {
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());
480 private QName parseQName(final QNameContext expr) {
481 switch (expr.getChildCount()) {
483 return namespaceContext.createQName(getChild(expr, NCNameContext.class, 0).getText());
485 return namespaceContext.createQName(getChild(expr, NCNameContext.class, 0).getText(),
486 getChild(expr, NCNameContext.class, 2).getText());
488 throw illegalShape(expr);
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();
502 throw illegalShape(abbrev);
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)));
512 final YangXPathAxis axis = parseAxis(getChild(expr, AxisSpecifierContext.class, 0));
513 final NodeTestContext nodeTest = getChild(expr, NodeTestContext.class, 1);
514 switch (nodeTest.getChildCount()) {
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);
522 return axis.asStep(parseQName(verifyTree(QNameContext.class, first)), predicates);
524 return axis.asStep(parseNodeType(nodeTest.getChild(0)), predicates);
526 final String text = verifyToken(nodeTest, 2, xpathParser.Literal).getText();
527 return axis.asStep(text.substring(1, text.length() - 1), predicates);
529 throw illegalShape(nodeTest);
533 private static YangXPathAxis parseAxis(final AxisSpecifierContext expr) {
534 switch (expr.getChildCount()) {
536 return YangXPathAxis.CHILD;
538 verify(getTerminalType(expr, 0) == xpathParser.AT, "Unhandled axis specifier shape %s", expr);
539 return YangXPathAxis.ATTRIBUTE;
541 final String str = verifyTerminal(expr.getChild(0)).getText();
542 return verifyNotNull(XPATH_AXES.get(str), "Unhandled axis %s", str);
544 throw illegalShape(expr);
548 private static <T extends ParserRuleContext> T nextContext(final Iterator<ParseTree> it, final Class<T> type) {
549 return verifyTree(type, it.next());
552 private static YangBinaryOperator nextOperator(final Iterator<ParseTree> it) {
553 return parseOperator(it.next());
556 private static int getTerminalType(final ParseTree parent, final int offset) {
557 return verifyTerminal(parent.getChild(offset)).getSymbol().getType();
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);
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);