blob: 33dc688f36a83e15dce782b0dbd74d330c1685fc [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 *
Michal Vasko03ff5a72019-09-11 13:49:33 +02006 * Copyright (c) 2015 - 2019 CESNET, z.s.p.o.
Radek Krejcib1646a92018-11-02 16:08:26 +01007 *
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 '(' ')'
Michal Vaskod3678892020-05-21 10:06:58 +020046 * [7] NameTest ::= '*' | NCName ':' '*' | QName
47 * [8] NodeType ::= 'text' | 'node'
48 * [9] Predicate ::= '[' Expr ']'
49 * [10] PrimaryExpr ::= '(' Expr ')' | Literal | Number | FunctionCall
50 * [11] FunctionCall ::= FunctionName '(' ( Expr ( ',' Expr )* )? ')'
51 * [12] PathExpr ::= LocationPath | PrimaryExpr Predicate*
Radek Krejcib1646a92018-11-02 16:08:26 +010052 * | PrimaryExpr Predicate* '/' RelativeLocationPath
53 * | PrimaryExpr Predicate* '//' RelativeLocationPath
Michal Vaskod3678892020-05-21 10:06:58 +020054 * [13] OrExpr ::= AndExpr | OrExpr 'or' AndExpr
55 * [14] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr
56 * [15] EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr
Radek Krejcib1646a92018-11-02 16:08:26 +010057 * | EqualityExpr '!=' RelationalExpr
Michal Vaskod3678892020-05-21 10:06:58 +020058 * [16] RelationalExpr ::= AdditiveExpr
Radek Krejcib1646a92018-11-02 16:08:26 +010059 * | RelationalExpr '<' AdditiveExpr
60 * | RelationalExpr '>' AdditiveExpr
61 * | RelationalExpr '<=' AdditiveExpr
62 * | RelationalExpr '>=' AdditiveExpr
Michal Vaskod3678892020-05-21 10:06:58 +020063 * [17] AdditiveExpr ::= MultiplicativeExpr
Radek Krejcib1646a92018-11-02 16:08:26 +010064 * | AdditiveExpr '+' MultiplicativeExpr
65 * | AdditiveExpr '-' MultiplicativeExpr
Michal Vaskod3678892020-05-21 10:06:58 +020066 * [18] MultiplicativeExpr ::= UnaryExpr
Radek Krejcib1646a92018-11-02 16:08:26 +010067 * | MultiplicativeExpr '*' UnaryExpr
68 * | MultiplicativeExpr 'div' UnaryExpr
69 * | MultiplicativeExpr 'mod' UnaryExpr
Michal Vaskod3678892020-05-21 10:06:58 +020070 * [19] UnaryExpr ::= UnionExpr | '-' UnaryExpr
71 * [20] UnionExpr ::= PathExpr | UnionExpr '|' PathExpr
Radek Krejcib1646a92018-11-02 16:08:26 +010072 */
73
74/* expression tokens allocation */
75#define LYXP_EXPR_SIZE_START 10
76#define LYXP_EXPR_SIZE_STEP 5
77
78/* XPath matches allocation */
79#define LYXP_SET_SIZE_START 2
80#define LYXP_SET_SIZE_STEP 2
81
82/* building string when casting */
83#define LYXP_STRING_CAST_SIZE_START 64
84#define LYXP_STRING_CAST_SIZE_STEP 16
85
86/**
87 * @brief Tokens that can be in an XPath expression.
88 */
89enum lyxp_token {
90 LYXP_TOKEN_NONE = 0,
91 LYXP_TOKEN_PAR1, /* '(' */
92 LYXP_TOKEN_PAR2, /* ')' */
93 LYXP_TOKEN_BRACK1, /* '[' */
94 LYXP_TOKEN_BRACK2, /* ']' */
95 LYXP_TOKEN_DOT, /* '.' */
96 LYXP_TOKEN_DDOT, /* '..' */
97 LYXP_TOKEN_AT, /* '@' */
98 LYXP_TOKEN_COMMA, /* ',' */
99 /* LYXP_TOKEN_DCOLON, * '::' * axes not supported */
100 LYXP_TOKEN_NAMETEST, /* NameTest */
101 LYXP_TOKEN_NODETYPE, /* NodeType */
102 LYXP_TOKEN_FUNCNAME, /* FunctionName */
103 LYXP_TOKEN_OPERATOR_LOG, /* Operator 'and', 'or' */
104 LYXP_TOKEN_OPERATOR_COMP, /* Operator '=', '!=', '<', '<=', '>', '>=' */
105 LYXP_TOKEN_OPERATOR_MATH, /* Operator '+', '-', '*', 'div', 'mod', '-' (unary) */
106 LYXP_TOKEN_OPERATOR_UNI, /* Operator '|' */
107 LYXP_TOKEN_OPERATOR_PATH, /* Operator '/', '//' */
108 /* LYXP_TOKEN_AXISNAME, * AxisName * axes not supported */
109 LYXP_TOKEN_LITERAL, /* Literal - with either single or double quote */
110 LYXP_TOKEN_NUMBER /* Number */
111};
112
113/**
114 * @brief XPath (sub)expressions that can be repeated.
115 */
116enum lyxp_expr_type {
117 LYXP_EXPR_NONE = 0,
118 LYXP_EXPR_OR,
119 LYXP_EXPR_AND,
120 LYXP_EXPR_EQUALITY,
121 LYXP_EXPR_RELATIONAL,
122 LYXP_EXPR_ADDITIVE,
123 LYXP_EXPR_MULTIPLICATIVE,
124 LYXP_EXPR_UNARY,
125 LYXP_EXPR_UNION,
126};
127
128/**
Michal Vasko03ff5a72019-09-11 13:49:33 +0200129 * @brief Types of context nodes, #LYXP_NODE_ROOT_CONFIG used only in when or must conditions.
130 */
131enum lyxp_node_type {
Michal Vasko2caefc12019-11-14 16:07:56 +0100132 LYXP_NODE_NONE, /* invalid node type */
133
Michal Vasko03ff5a72019-09-11 13:49:33 +0200134 /* XML document roots */
135 LYXP_NODE_ROOT, /* access to all the data (node value first top-level node) */
136 LYXP_NODE_ROOT_CONFIG, /* <running> data context, no state data (node value first top-level node) */
137
138 /* XML elements */
Michal Vasko9f96a052020-03-10 09:41:45 +0100139 LYXP_NODE_ELEM, /* YANG data element (most common) */
140 LYXP_NODE_TEXT, /* YANG data text element (extremely specific use, unlikely to be ever needed) */
141 LYXP_NODE_META /* YANG metadata (do not use for the context node) */
Michal Vasko03ff5a72019-09-11 13:49:33 +0200142};
143
144/**
Radek Krejcib1646a92018-11-02 16:08:26 +0100145 * @brief Structure holding a parsed XPath expression.
146 */
147struct lyxp_expr {
148 enum lyxp_token *tokens; /* array of tokens */
149 uint16_t *tok_pos; /* array of the token offsets in expr */
150 uint16_t *tok_len; /* array of token lengths in expr */
151 enum lyxp_expr_type **repeat; /* array of expression types that this token begins and is repeated ended with 0,
152 more in the comment after this declaration */
153 uint16_t used; /* used array items */
154 uint16_t size; /* allocated array items */
155
156 const char *expr; /* the original XPath expression */
157};
158
159/*
160 * lyxp_expr repeat
161 *
162 * This value is NULL for all the tokens that do not begin an
163 * expression which can be repeated. Otherwise it is an array
164 * of expression types that this token begins. These values
165 * are used during evaluation to know whether we need to
166 * duplicate the current context or not and to decide what
167 * the current expression is (for example, if we are only
168 * starting the parsing and the first token has no repeat,
169 * we do not parse it as an OrExpr but directly as PathExpr).
170 * Examples:
171 *
172 * Expression: "/ *[key1 and key2 or key1 < key2]"
173 * Tokens: '/', '*', '[', NameTest, 'and', NameTest, 'or', NameTest, '<', NameTest, ']'
174 * Repeat: NULL, NULL, NULL, [AndExpr, NULL, NULL, NULL, [RelationalExpr, NULL, NULL, NULL
175 * OrExpr, 0],
176 * 0],
177 *
178 * Expression: "//node[key and node2]/key | /cont"
179 * Tokens: '//', 'NameTest', '[', 'NameTest', 'and', 'NameTest', ']', '/', 'NameTest', '|', '/', 'NameTest'
180 * Repeat: [UnionExpr, NULL, NULL, [AndExpr, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
181 * 0], 0],
182 *
183 * Operators between expressions which this concerns:
184 * 'or', 'and', '=', '!=', '<', '>', '<=', '>=', '+', '-', '*', 'div', 'mod', '|'
185 */
186
187/**
188 * @brief Supported types of (partial) XPath results.
189 */
190enum lyxp_set_type {
Michal Vaskod3678892020-05-21 10:06:58 +0200191 LYXP_SET_NODE_SET = 0,
Michal Vasko03ff5a72019-09-11 13:49:33 +0200192 LYXP_SET_SCNODE_SET,
Radek Krejcib1646a92018-11-02 16:08:26 +0100193 LYXP_SET_BOOLEAN,
194 LYXP_SET_NUMBER,
195 LYXP_SET_STRING
196};
Radek Krejcib1646a92018-11-02 16:08:26 +0100197
198/**
199 * @brief Item stored in an XPath set hash table.
200 */
201struct lyxp_set_hash_node {
202 struct lyd_node *node;
203 enum lyxp_node_type type;
204} _PACKED;
205
Radek Krejcib1646a92018-11-02 16:08:26 +0100206/**
207 * @brief XPath set - (partial) result.
208 */
209struct lyxp_set {
210 enum lyxp_set_type type;
211 union {
212 struct lyxp_set_node {
213 struct lyd_node *node;
214 enum lyxp_node_type type;
215 uint32_t pos;
216 } *nodes;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200217 struct lyxp_set_scnode {
218 struct lysc_node *scnode;
Radek Krejcib1646a92018-11-02 16:08:26 +0100219 enum lyxp_node_type type;
Michal Vasko5c4e5892019-11-14 12:31:38 +0100220 /* -2 - scnode not traversed, currently (the only node) in context;
221 * -1 - scnode not traversed except for the eval start, not currently in the context;
222 * 0 - scnode was traversed, but not currently in the context;
223 * 1 - scnode currently in context;
224 * 2 - scnode in context and just added, so skip it for the current operation;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200225 * >=3 - scnode is not in context because we are in a predicate and this scnode was used/will be used later */
Michal Vasko5c4e5892019-11-14 12:31:38 +0100226 int32_t in_ctx;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200227 } *scnodes;
Michal Vasko9f96a052020-03-10 09:41:45 +0100228 struct lyxp_set_meta {
229 struct lyd_meta *meta;
Radek Krejcib1646a92018-11-02 16:08:26 +0100230 enum lyxp_node_type type;
Michal Vasko9f96a052020-03-10 09:41:45 +0100231 uint32_t pos; /* if node_type is LYXP_SET_NODE_META, it is the parent node position */
232 } *meta;
Radek Krejcib1646a92018-11-02 16:08:26 +0100233 char *str;
234 long double num;
235 int bool;
236 } val;
237
Michal Vasko03ff5a72019-09-11 13:49:33 +0200238 /* this is valid only for type LYXP_SET_NODE_SET and LYXP_SET_SCNODE_SET */
Radek Krejcib1646a92018-11-02 16:08:26 +0100239 uint32_t used;
240 uint32_t size;
Radek Krejcib1646a92018-11-02 16:08:26 +0100241 struct hash_table *ht;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200242
243 /* XPath context information, this is valid only for type LYXP_SET_NODE_SET */
Radek Krejcib1646a92018-11-02 16:08:26 +0100244 uint32_t ctx_pos;
245 uint32_t ctx_size;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200246
247 /* general context */
248 struct ly_ctx *ctx;
249 union {
250 const struct lyd_node *ctx_node;
251 const struct lysc_node *ctx_scnode;
252 };
Michal Vasko5e0e6eb2019-11-06 15:47:50 +0100253 enum lyxp_node_type root_type;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200254 const struct lys_module *local_mod;
Michal Vaskof03ed032020-03-04 13:31:44 +0100255 const struct lyd_node *tree;
Michal Vasko03ff5a72019-09-11 13:49:33 +0200256 LYD_FORMAT format;
Radek Krejcib1646a92018-11-02 16:08:26 +0100257};
258
259/**
Michal Vasko03ff5a72019-09-11 13:49:33 +0200260 * @brief Evaluate an XPath expression on data. Be careful when using this function, the result can often
261 * be confusing without thorough understanding of XPath evaluation rules defined in RFC 7950.
Radek Krejcib1646a92018-11-02 16:08:26 +0100262 *
Michal Vaskoecd62de2019-11-13 12:35:11 +0100263 * @param[in] exp Parsed XPath expression to be evaluated.
Michal Vasko03ff5a72019-09-11 13:49:33 +0200264 * @param[in] format Format of the XPath expression (more specifcally, of any used prefixes).
265 * @param[in] local_mod Local module relative to the @p expr.
Michal Vaskod0aa1a82019-11-07 08:58:42 +0100266 * @param[in] ctx_node Current (context) data node, NULL for root node.
Michal Vasko03ff5a72019-09-11 13:49:33 +0200267 * @param[in] ctx_node_type Current (context) data node type. For every standard case use #LYXP_NODE_ELEM. But there are
268 * cases when the context node @p ctx_node is actually supposed to be the XML root, there is no such data node. So, in
Michal Vaskod0aa1a82019-11-07 08:58:42 +0100269 * this case just pass NULL for @p ctx_node and use an enum value for this kind of root (#LYXP_NODE_ROOT_CONFIG if
270 * @p ctx_node has config true, otherwise #LYXP_NODE_ROOT). #LYXP_NODE_TEXT and #LYXP_NODE_ATTR can also be used,
Radek Krejcib1646a92018-11-02 16:08:26 +0100271 * but there are no use-cases in YANG.
Michal Vaskof03ed032020-03-04 13:31:44 +0100272 * @param[in] tree Data tree on which to perform the evaluation, it must include all the available data (including
Michal Vaskod0aa1a82019-11-07 08:58:42 +0100273 * the tree of @p ctx_node).
Michal Vasko03ff5a72019-09-11 13:49:33 +0200274 * @param[out] set Result set. Must be valid and in the same libyang context as @p ctx_node.
275 * To be safe, always either zero or cast the @p set to empty. After done using, either cast
276 * the @p set to empty (if allocated statically) or free it (if allocated dynamically) to
Radek Krejcib1646a92018-11-02 16:08:26 +0100277 * prevent memory leaks.
278 * @param[in] options Whether to apply some evaluation restrictions.
Michal Vaskoecd62de2019-11-13 12:35:11 +0100279 * @return LY_ERR (LY_EINVAL, LY_EMEM, LY_EINT, LY_EVALID for invalid argument types/count,
280 * LY_EINCOMPLETE for unresolved when).
Radek Krejcib1646a92018-11-02 16:08:26 +0100281 */
Michal Vaskoecd62de2019-11-13 12:35:11 +0100282LY_ERR lyxp_eval(struct lyxp_expr *exp, LYD_FORMAT format, const struct lys_module *local_mod, const struct lyd_node *ctx_node,
Michal Vaskof03ed032020-03-04 13:31:44 +0100283 enum lyxp_node_type ctx_node_type, const struct lyd_node *tree, struct lyxp_set *set, int options);
Michal Vasko03ff5a72019-09-11 13:49:33 +0200284
285#define LYXP_SCHEMA 0x01 /**< Apply data node access restrictions defined for 'when' and 'must' evaluation. */
Radek Krejcib1646a92018-11-02 16:08:26 +0100286
287/**
Michal Vasko03ff5a72019-09-11 13:49:33 +0200288 * @brief Get all the partial XPath nodes (atoms) that are required for @p exp to be evaluated.
Radek Krejcib1646a92018-11-02 16:08:26 +0100289 *
Michal Vasko03ff5a72019-09-11 13:49:33 +0200290 * If any LYXP_SCNODE* options is set, only fatal errors are printed, otherwise they are downgraded
Radek Krejcib1646a92018-11-02 16:08:26 +0100291 * to warnings.
292 *
Michal Vasko03ff5a72019-09-11 13:49:33 +0200293 * @param[in] exp Parsed XPath expression to be evaluated.
294 * @param[in] format Format of the XPath expression (more specifcally, of any used prefixes).
295 * @param[in] local_mod Local module relative to the @p exp.
Michal Vaskod0aa1a82019-11-07 08:58:42 +0100296 * @param[in] ctx_scnode Current (context) schema node, NULL for root node.
Michal Vasko03ff5a72019-09-11 13:49:33 +0200297 * @param[in] ctx_scnode_type Current (context) schema node type.
298 * @param[out] set Result set. Must be valid and in the same libyang context as @p ctx_scnode.
299 * To be safe, always either zero or cast the @p set to empty. After done using, either cast
300 * the @p set to empty (if allocated statically) or free it (if allocated dynamically) to
Radek Krejcib1646a92018-11-02 16:08:26 +0100301 * prevent memory leaks.
302 * @param[in] options Whether to apply some evaluation restrictions, one flag must always be used.
Michal Vaskoecd62de2019-11-13 12:35:11 +0100303 * @return LY_ERR (same as lyxp_eval()).
Radek Krejcib1646a92018-11-02 16:08:26 +0100304 */
Michal Vasko03ff5a72019-09-11 13:49:33 +0200305LY_ERR lyxp_atomize(struct lyxp_expr *exp, LYD_FORMAT format, const struct lys_module *local_mod, const struct lysc_node *ctx_scnode,
306 enum lyxp_node_type ctx_scnode_type, struct lyxp_set *set, int options);
Radek Krejcib1646a92018-11-02 16:08:26 +0100307
308/* these are used only internally */
Michal Vasko03ff5a72019-09-11 13:49:33 +0200309#define LYXP_SCNODE 0x02 /**< No special data tree access modifiers. */
310#define LYXP_SCNODE_SCHEMA 0x04 /**< Apply schema node access restrictions defined for 'when' and 'must' evaluation. */
311#define LYXP_SCNODE_OUTPUT 0x08 /**< Search RPC/action output instead of input. */
Radek Krejcib1646a92018-11-02 16:08:26 +0100312
Michal Vasko03ff5a72019-09-11 13:49:33 +0200313#define LYXP_SCNODE_ALL 0x0E
Radek Krejcib1646a92018-11-02 16:08:26 +0100314
315/**
Radek Krejcib1646a92018-11-02 16:08:26 +0100316 * @brief Cast XPath set to another type.
317 * Indirectly context position aware.
318 *
319 * @param[in] set Set to cast.
320 * @param[in] target Target type to cast \p set into.
Michal Vasko03ff5a72019-09-11 13:49:33 +0200321 * @return LY_ERR
Radek Krejcib1646a92018-11-02 16:08:26 +0100322 */
Michal Vasko5e0e6eb2019-11-06 15:47:50 +0100323LY_ERR lyxp_set_cast(struct lyxp_set *set, enum lyxp_set_type target);
Michal Vasko03ff5a72019-09-11 13:49:33 +0200324
Radek Krejcib1646a92018-11-02 16:08:26 +0100325/**
Michal Vaskod3678892020-05-21 10:06:58 +0200326 * @brief Free dynamic content of a set.
327 *
328 * @param[in] set Set to modify.
329 */
330void lyxp_set_free_content(struct lyxp_set *set);
331
332/**
Michal Vaskoecd62de2019-11-13 12:35:11 +0100333 * @brief Insert schema node into set.
334 *
335 * @param[in] set Set to insert into.
336 * @param[in] node Node to insert.
337 * @param[in] node_type Node type of @p node.
338 * @return Index of the inserted node in set.
339 */
340int lyxp_set_scnode_insert_node(struct lyxp_set *set, const struct lysc_node *node, enum lyxp_node_type node_type);
341
342/**
343 * @brief Check for duplicates in a schema node set.
344 *
345 * @param[in] set Set to check.
346 * @param[in] node Node to look for in @p set.
347 * @param[in] node_type Type of @p node.
348 * @param[in] skip_idx Index from @p set to skip.
349 * @return Index of the found node, -1 if not found.
350 */
351int lyxp_set_scnode_dup_node_check(struct lyxp_set *set, const struct lysc_node *node, enum lyxp_node_type node_type,
352 int skip_idx);
353
354/**
355 * @brief Merge 2 schema node sets.
356 *
357 * @param[in] set1 Set to merge into.
358 * @param[in] set2 Set to merge. Its content is freed.
359 */
360void lyxp_set_scnode_merge(struct lyxp_set *set1, struct lyxp_set *set2);
361
362/**
Radek Krejcib1646a92018-11-02 16:08:26 +0100363 * @brief Parse an XPath expression into a structure of tokens.
364 * Logs directly.
365 *
Michal Vasko03ff5a72019-09-11 13:49:33 +0200366 * https://www.w3.org/TR/1999/REC-xpath-19991116/#exprlex
Radek Krejcib1646a92018-11-02 16:08:26 +0100367 *
368 * @param[in] ctx Context for errors.
369 * @param[in] expr XPath expression to parse. It is duplicated.
Radek Krejcib1646a92018-11-02 16:08:26 +0100370 * @return Filled expression structure or NULL on error.
371 */
372struct lyxp_expr *lyxp_expr_parse(struct ly_ctx *ctx, const char *expr);
373
374/**
Michal Vasko03ff5a72019-09-11 13:49:33 +0200375 * @brief Frees a parsed XPath expression. @p expr should not be used afterwards.
Radek Krejcib1646a92018-11-02 16:08:26 +0100376 *
377 * @param[in] ctx libyang context of the expression.
378 * @param[in] expr Expression to free.
379 */
380void lyxp_expr_free(struct ly_ctx *ctx, struct lyxp_expr *expr);
381
382#endif /* _XPATH_H */