blob: 5abd427c377097cd437fef7844f15bf005dbacd4 [file] [log] [blame]
Radek Krejcib1646a92018-11-02 16:08:26 +01001/**
2 * @file xpath.h
3 * @author Michal Vasko <mvasko@cesnet.cz>
4 * @brief YANG XPath evaluation functions header
5 *
6 * Copyright (c) 2015 CESNET, z.s.p.o.
7 *
8 * This source code is licensed under BSD 3-Clause License (the "License").
9 * You may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * https://opensource.org/licenses/BSD-3-Clause
13 */
14
15#ifndef _XPATH_H
16#define _XPATH_H
17
18#include <stdint.h>
19
Radek Krejcie7b95092019-05-15 11:03:07 +020020#include "log.h"
21
22struct ly_ctx;
23struct lysc_node;
24
Radek Krejcib1646a92018-11-02 16:08:26 +010025/*
26 * XPath evaluator fully compliant with http://www.w3.org/TR/1999/REC-xpath-19991116/
27 * except the following restrictions in the grammar.
28 *
29 * PARSED GRAMMAR
30 *
31 * Full axes are not supported, abbreviated forms must be used,
32 * variables are not supported, "id()" function is not supported,
33 * and processing instruction and comment nodes are not supported,
34 * which is also reflected in the grammar. Undefined rules and
35 * constants are tokens.
36 *
37 * Modified full grammar:
38 *
39 * [1] Expr ::= OrExpr // just an alias
40 *
41 * [2] LocationPath ::= RelativeLocationPath | AbsoluteLocationPath
42 * [3] AbsoluteLocationPath ::= '/' RelativeLocationPath? | '//' RelativeLocationPath
43 * [4] RelativeLocationPath ::= Step | RelativeLocationPath '/' Step | RelativeLocationPath '//' Step
44 * [5] Step ::= '@'? NodeTest Predicate* | '.' | '..'
45 * [6] NodeTest ::= NameTest | NodeType '(' ')'
46 * [7] Predicate ::= '[' Expr ']'
47 * [8] PrimaryExpr ::= '(' Expr ')' | Literal | Number | FunctionCall
48 * [9] FunctionCall ::= FunctionName '(' ( Expr ( ',' Expr )* )? ')'
49 * [10] PathExpr ::= LocationPath | PrimaryExpr Predicate*
50 * | PrimaryExpr Predicate* '/' RelativeLocationPath
51 * | PrimaryExpr Predicate* '//' RelativeLocationPath
52 * [11] OrExpr ::= AndExpr | OrExpr 'or' AndExpr
53 * [12] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr
54 * [13] EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr
55 * | EqualityExpr '!=' RelationalExpr
56 * [14] RelationalExpr ::= AdditiveExpr
57 * | RelationalExpr '<' AdditiveExpr
58 * | RelationalExpr '>' AdditiveExpr
59 * | RelationalExpr '<=' AdditiveExpr
60 * | RelationalExpr '>=' AdditiveExpr
61 * [15] AdditiveExpr ::= MultiplicativeExpr
62 * | AdditiveExpr '+' MultiplicativeExpr
63 * | AdditiveExpr '-' MultiplicativeExpr
64 * [16] MultiplicativeExpr ::= UnaryExpr
65 * | MultiplicativeExpr '*' UnaryExpr
66 * | MultiplicativeExpr 'div' UnaryExpr
67 * | MultiplicativeExpr 'mod' UnaryExpr
68 * [17] UnaryExpr ::= UnionExpr | '-' UnaryExpr
69 * [18] UnionExpr ::= PathExpr | UnionExpr '|' PathExpr
70 */
71
72/* expression tokens allocation */
73#define LYXP_EXPR_SIZE_START 10
74#define LYXP_EXPR_SIZE_STEP 5
75
76/* XPath matches allocation */
77#define LYXP_SET_SIZE_START 2
78#define LYXP_SET_SIZE_STEP 2
79
80/* building string when casting */
81#define LYXP_STRING_CAST_SIZE_START 64
82#define LYXP_STRING_CAST_SIZE_STEP 16
83
84/**
85 * @brief Tokens that can be in an XPath expression.
86 */
87enum lyxp_token {
88 LYXP_TOKEN_NONE = 0,
89 LYXP_TOKEN_PAR1, /* '(' */
90 LYXP_TOKEN_PAR2, /* ')' */
91 LYXP_TOKEN_BRACK1, /* '[' */
92 LYXP_TOKEN_BRACK2, /* ']' */
93 LYXP_TOKEN_DOT, /* '.' */
94 LYXP_TOKEN_DDOT, /* '..' */
95 LYXP_TOKEN_AT, /* '@' */
96 LYXP_TOKEN_COMMA, /* ',' */
97 /* LYXP_TOKEN_DCOLON, * '::' * axes not supported */
98 LYXP_TOKEN_NAMETEST, /* NameTest */
99 LYXP_TOKEN_NODETYPE, /* NodeType */
100 LYXP_TOKEN_FUNCNAME, /* FunctionName */
101 LYXP_TOKEN_OPERATOR_LOG, /* Operator 'and', 'or' */
102 LYXP_TOKEN_OPERATOR_COMP, /* Operator '=', '!=', '<', '<=', '>', '>=' */
103 LYXP_TOKEN_OPERATOR_MATH, /* Operator '+', '-', '*', 'div', 'mod', '-' (unary) */
104 LYXP_TOKEN_OPERATOR_UNI, /* Operator '|' */
105 LYXP_TOKEN_OPERATOR_PATH, /* Operator '/', '//' */
106 /* LYXP_TOKEN_AXISNAME, * AxisName * axes not supported */
107 LYXP_TOKEN_LITERAL, /* Literal - with either single or double quote */
108 LYXP_TOKEN_NUMBER /* Number */
109};
110
111/**
112 * @brief XPath (sub)expressions that can be repeated.
113 */
114enum lyxp_expr_type {
115 LYXP_EXPR_NONE = 0,
116 LYXP_EXPR_OR,
117 LYXP_EXPR_AND,
118 LYXP_EXPR_EQUALITY,
119 LYXP_EXPR_RELATIONAL,
120 LYXP_EXPR_ADDITIVE,
121 LYXP_EXPR_MULTIPLICATIVE,
122 LYXP_EXPR_UNARY,
123 LYXP_EXPR_UNION,
124};
125
126/**
127 * @brief Structure holding a parsed XPath expression.
128 */
129struct lyxp_expr {
130 enum lyxp_token *tokens; /* array of tokens */
131 uint16_t *tok_pos; /* array of the token offsets in expr */
132 uint16_t *tok_len; /* array of token lengths in expr */
133 enum lyxp_expr_type **repeat; /* array of expression types that this token begins and is repeated ended with 0,
134 more in the comment after this declaration */
135 uint16_t used; /* used array items */
136 uint16_t size; /* allocated array items */
137
138 const char *expr; /* the original XPath expression */
139};
140
141/*
142 * lyxp_expr repeat
143 *
144 * This value is NULL for all the tokens that do not begin an
145 * expression which can be repeated. Otherwise it is an array
146 * of expression types that this token begins. These values
147 * are used during evaluation to know whether we need to
148 * duplicate the current context or not and to decide what
149 * the current expression is (for example, if we are only
150 * starting the parsing and the first token has no repeat,
151 * we do not parse it as an OrExpr but directly as PathExpr).
152 * Examples:
153 *
154 * Expression: "/ *[key1 and key2 or key1 < key2]"
155 * Tokens: '/', '*', '[', NameTest, 'and', NameTest, 'or', NameTest, '<', NameTest, ']'
156 * Repeat: NULL, NULL, NULL, [AndExpr, NULL, NULL, NULL, [RelationalExpr, NULL, NULL, NULL
157 * OrExpr, 0],
158 * 0],
159 *
160 * Expression: "//node[key and node2]/key | /cont"
161 * Tokens: '//', 'NameTest', '[', 'NameTest', 'and', 'NameTest', ']', '/', 'NameTest', '|', '/', 'NameTest'
162 * Repeat: [UnionExpr, NULL, NULL, [AndExpr, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
163 * 0], 0],
164 *
165 * Operators between expressions which this concerns:
166 * 'or', 'and', '=', '!=', '<', '>', '<=', '>=', '+', '-', '*', 'div', 'mod', '|'
167 */
168
169/**
170 * @brief Supported types of (partial) XPath results.
171 */
172enum lyxp_set_type {
173 LYXP_SET_EMPTY = 0,
174 LYXP_SET_NODE_SET,
175 LYXP_SET_SNODE_SET,
176 LYXP_SET_BOOLEAN,
177 LYXP_SET_NUMBER,
178 LYXP_SET_STRING
179};
180#if 0
181#ifdef LY_ENABLED_CACHE
182
183/**
184 * @brief Item stored in an XPath set hash table.
185 */
186struct lyxp_set_hash_node {
187 struct lyd_node *node;
188 enum lyxp_node_type type;
189} _PACKED;
190
191#endif
192
193/**
194 * @brief XPath set - (partial) result.
195 */
196struct lyxp_set {
197 enum lyxp_set_type type;
198 union {
199 struct lyxp_set_node {
200 struct lyd_node *node;
201 enum lyxp_node_type type;
202 uint32_t pos;
203 } *nodes;
204 struct lyxp_set_snode {
205 struct lys_node *snode;
206 enum lyxp_node_type type;
207 /* 0 - snode was traversed, but not currently in the context,
208 * 1 - snode currently in context,
209 * 2 - snode in context and just added, so skip it for the current operation,
210 * >=3 - snode is not in context because we are in a predicate and this snode was used/will be used later */
211 uint32_t in_ctx;
212 } *snodes;
213 struct lyxp_set_attr {
214 struct lyd_attr *attr;
215 enum lyxp_node_type type;
216 uint32_t pos; /* if node_type is LYXP_SET_NODE_ATTR, it is the parent node position */
217 } *attrs;
218 char *str;
219 long double num;
220 int bool;
221 } val;
222
223 /* this is valid only for type LYXP_SET_NODE_SET and LYXP_SET_SNODE_SET */
224 uint32_t used;
225 uint32_t size;
226#ifdef LY_ENABLED_CACHE
227 struct hash_table *ht;
228#endif
229 /* this is valid only for type LYXP_SET_NODE_SET */
230 uint32_t ctx_pos;
231 uint32_t ctx_size;
232};
233
234/**
235 * @brief Evaluate the XPath expression \p expr on data. Be careful when using this function, the result can often
236 * be confusing without thorough understanding of XPath evaluation rules defined in RFC 6020.
237 *
238 * @param[in] expr XPath expression to evaluate. Must be in JSON format (prefixes are model names).
239 * @param[in] cur_node Current (context) data node. If the node has #LYD_VAL_INUSE flag, it is considered dummy (intended
240 * for but not restricted to evaluation with the LYXP_WHEN flag).
241 * @param[in] cur_node_type Current (context) data node type. For every standard case use #LYXP_NODE_ELEM. But there are
242 * cases when the context node \p cur_node is actually supposed to be the XML root, there is no such data node. So, in
243 * this case just pass the first top-level node into \p cur_node and use an enum value for this kind of root
244 * (#LYXP_NODE_ROOT_CONFIG if \p cur_node has config true, otherwise #LYXP_NODE_ROOT). #LYXP_NODE_TEXT and #LYXP_NODE_ATTR can also be used,
245 * but there are no use-cases in YANG.
246 * @param[in] local_mod Local module relative to the \p expr. Used only to determine the internal canonical value for identities.
247 * @param[out] set Result set. Must be valid and in the same libyang context as \p cur_node.
248 * To be safe, always either zero or cast the \p set to empty. After done using, either cast
249 * the \p set to empty (if allocated statically) or free it (if allocated dynamically) to
250 * prevent memory leaks.
251 * @param[in] options Whether to apply some evaluation restrictions.
252 * LYXP_MUST - apply must data tree access restrictions.
253 * LYXP_WHEN - apply when data tree access restrictions and consider LYD_WHEN flags in data nodes.
254 *
255 * @return EXIT_SUCCESS on success, EXIT_FAILURE on unresolved when dependency, -1 on error.
256 */
257int lyxp_eval(const char *expr, const struct lyd_node *cur_node, enum lyxp_node_type cur_node_type,
258 const struct lys_module *local_mod, struct lyxp_set *set, int options);
259
260/**
261 * @brief Get all the partial XPath nodes (atoms) that are required for \p expr to be evaluated.
262 *
263 * If any LYXP_SNODE* options is set, only fatal errors are printed, otherwise they are downgraded
264 * to warnings.
265 *
266 * @param[in] expr XPath expression to be evaluated. Must be in JSON format (prefixes are model names).
267 * @param[in] cur_snode Current (context) schema node.
268 * @param[in] cur_snode_type Current (context) schema node type.
269 * @param[out] set Result set. Must be valid and in the same libyang context as \p cur_snode.
270 * To be safe, always either zero or cast the \p set to empty. After done using, either cast
271 * the \p set to empty (if allocated statically) or free it (if allocated dynamically) to
272 * prevent memory leaks.
273 * @param[in] options Whether to apply some evaluation restrictions, one flag must always be used.
274 * LYXP_SNODE - no special data tree access modifiers.
275 * LYXP_SNODE_MUST - apply must data tree access restrictions.
276 * LYXP_SNODE_WHEN - apply when data tree access restrictions.
277 * LYXP_SNODE_OUTPUT - search RPC/action output instead input
278 * @param[out] ctx_snode Actual context node for the expression (it often changes for "when" expressions).
279 *
280 * @return EXIT_SUCCESS on success, -1 on error.
281 */
282int lyxp_atomize(const char *expr, const struct lys_node *cur_snode, enum lyxp_node_type cur_snode_type,
283 struct lyxp_set *set, int options, const struct lys_node **ctx_snode);
284
285/* these are used only internally */
286#define LYXP_SNODE 0x04
287#define LYXP_SNODE_MUST 0x08
288#define LYXP_SNODE_WHEN 0x10
289#define LYXP_SNODE_OUTPUT 0x20
290
291#define LYXP_SNODE_ALL 0x1C
292
293/**
294 * @brief Works like lyxp_atomize(), but it is executed on all the when and must expressions
295 * which the node has.
296 *
297 * @param[in] node Node to examine.
298 * @param[in,out] set Resulting set of atoms merged from all the expressions.
299 * Will be cleared before use.
300 * @param[in] set_ext_dep_flags Whether to set #LYS_XPCONF_DEP or #LYS_XPSTATE_DEP for conditions that
301 * require foreign configuration or state subtree and also for the node itself, if it has any such condition.
302 *
303 * @return EXIT_SUCCESS on success, -1 on error.
304 */
305int lyxp_node_atomize(const struct lys_node *node, struct lyxp_set *set, int set_ext_dep_flags);
306#endif
307/**
308 * @brief Check syntax of all the XPath expressions of the node.
309 *
310 * @param[in] node Node to examine.
311 *
312 * @return LY_ERR value.
313 */
314LY_ERR lyxp_node_check_syntax(const struct lysc_node *node);
315#if 0
316/**
317 * @brief Cast XPath set to another type.
318 * Indirectly context position aware.
319 *
320 * @param[in] set Set to cast.
321 * @param[in] target Target type to cast \p set into.
322 * @param[in] cur_node Current (context) data node. Cannot be NULL.
323 * @param[in] local_mod Local expression module.
324 * @param[in] options Whether to apply some evaluation restrictions.
325 *
326 * @return EXIT_SUCCESS on success, -1 on error.
327 */
328int lyxp_set_cast(struct lyxp_set *set, enum lyxp_set_type target, const struct lyd_node *cur_node,
329 const struct lys_module *local_mod, int options);
330
331/**
332 * @brief Free contents of an XPath \p set.
333 *
334 * @param[in] set Set to free.
335 */
336void lyxp_set_free(struct lyxp_set *set);
337#endif
338/**
339 * @brief Parse an XPath expression into a structure of tokens.
340 * Logs directly.
341 *
342 * http://www.w3.org/TR/1999/REC-xpath-19991116/ section 3.7
343 *
344 * @param[in] ctx Context for errors.
345 * @param[in] expr XPath expression to parse. It is duplicated.
346 *
347 * @return Filled expression structure or NULL on error.
348 */
349struct lyxp_expr *lyxp_expr_parse(struct ly_ctx *ctx, const char *expr);
350
351/**
352 * @brief Frees a parsed XPath expression. \p expr should not be used afterwards.
353 *
354 * @param[in] ctx libyang context of the expression.
355 * @param[in] expr Expression to free.
356 */
357void lyxp_expr_free(struct ly_ctx *ctx, struct lyxp_expr *expr);
358
359#endif /* _XPATH_H */