xpath FEATURE start of integrating XPath implementation
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 0747637..b46409f 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -160,7 +160,8 @@
src/tree_schema.c
src/tree_schema_helpers.c
src/parser_yang.c
- src/xml.c)
+ src/xml.c
+ src/xpath.c)
#set(lintsrc
# tools/lint/main.c
diff --git a/src/common.h b/src/common.h
index 4dcbfff..ca1c29d 100644
--- a/src/common.h
+++ b/src/common.h
@@ -141,6 +141,8 @@
#define LY_VCODE_INORD LYVE_SYNTAX_YANG, "Invalid keyword \"%s\", it cannot appear after \"%s\"."
#define LY_VCODE_OOB LYVE_SYNTAX_YANG, "Value \"%.*s\" is out of \"%s\" bounds."
#define LY_VCODE_INDEV LYVE_SYNTAX_YANG, "Deviate \"%s\" does not support keyword \"%s\"."
+#define LY_VCODE_XP_EOE LYVE_XPATH, "Unterminated string delimited with %c (%.15s)."
+#define LY_VCODE_XP_INEXPR LYVE_XPATH, "Invalid expression 0x%x."
/******************************************************************************
* Context
diff --git a/src/log.h b/src/log.h
index 8613b18..d8b0a04 100644
--- a/src/log.h
+++ b/src/log.h
@@ -164,6 +164,7 @@
LYVE_SYNTAX, /**< generic syntax error */
LYVE_SYNTAX_YANG, /**< YANG-related syntax error */
LYVE_REFERENCE, /**< invalid referencing or using an item */
+ LYVE_XPATH, /**< invalid XPath expression */
LYVE_SEMANTICS /**< generic semantic error */
} LY_VECODE;
diff --git a/src/xml.c b/src/xml.c
index db25d70..06d79ce 100644
--- a/src/xml.c
+++ b/src/xml.c
@@ -24,30 +24,6 @@
#include "xml.h"
#include "common.h"
-/* Macro to test if character is whitespace */
-#define is_xmlws(c) (c == 0x20 || c == 0x9 || c == 0xa || c == 0xd)
-
-/* Macro to test if character is allowed to be a first character of an qualified identifier */
-#define is_xmlqnamestartchar(c) ((c >= 'a' && c <= 'z') || c == '_' || \
- (c >= 'A' && c <= 'Z') || /* c == ':' || */ \
- (c >= 0x370 && c <= 0x1fff && c != 0x37e ) || \
- (c >= 0xc0 && c <= 0x2ff && c != 0xd7 && c != 0xf7) || c == 0x200c || \
- c == 0x200d || (c >= 0x2070 && c <= 0x218f) || \
- (c >= 0x2c00 && c <= 0x2fef) || (c >= 0x3001 && c <= 0xd7ff) || \
- (c >= 0xf900 && c <= 0xfdcf) || (c >= 0xfdf0 && c <= 0xfffd) || \
- (c >= 0x10000 && c <= 0xeffff))
-
-/* Macro to test if character is allowed to be used in an qualified identifier */
-#define is_xmlqnamechar(c) ((c >= 'a' && c <= 'z') || c == '_' || c == '-' || \
- (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || /* c == ':' || */ \
- c == '.' || c == 0xb7 || (c >= 0x370 && c <= 0x1fff && c != 0x37e ) ||\
- (c >= 0xc0 && c <= 0x2ff && c != 0xd7 && c != 0xf7) || c == 0x200c || \
- c == 0x200d || (c >= 0x300 && c <= 0x36f) || \
- (c >= 0x2070 && c <= 0x218f) || (c >= 0x2030f && c <= 0x2040) || \
- (c >= 0x2c00 && c <= 0x2fef) || (c >= 0x3001 && c <= 0xd7ff) || \
- (c >= 0xf900 && c <= 0xfdcf) || (c >= 0xfdf0 && c <= 0xfffd) || \
- (c >= 0x10000 && c <= 0xeffff))
-
/* Move input p by s characters, if EOF log with lyxml_context c */
#define move_input(c,p,s) p += s; LY_CHECK_ERR_RET(!p[0], LOGVAL(c->ctx, LY_VLOG_LINE, &c->line, LY_VCODE_EOF), LY_EVALID)
diff --git a/src/xml.h b/src/xml.h
index f42b27e..5172c48 100644
--- a/src/xml.h
+++ b/src/xml.h
@@ -20,6 +20,30 @@
#include "context.h"
#include "set.h"
+/* Macro to test if character is whitespace */
+#define is_xmlws(c) (c == 0x20 || c == 0x9 || c == 0xa || c == 0xd)
+
+/* Macro to test if character is allowed to be a first character of an qualified identifier */
+#define is_xmlqnamestartchar(c) ((c >= 'a' && c <= 'z') || c == '_' || \
+ (c >= 'A' && c <= 'Z') || /* c == ':' || */ \
+ (c >= 0x370 && c <= 0x1fff && c != 0x37e ) || \
+ (c >= 0xc0 && c <= 0x2ff && c != 0xd7 && c != 0xf7) || c == 0x200c || \
+ c == 0x200d || (c >= 0x2070 && c <= 0x218f) || \
+ (c >= 0x2c00 && c <= 0x2fef) || (c >= 0x3001 && c <= 0xd7ff) || \
+ (c >= 0xf900 && c <= 0xfdcf) || (c >= 0xfdf0 && c <= 0xfffd) || \
+ (c >= 0x10000 && c <= 0xeffff))
+
+/* Macro to test if character is allowed to be used in an qualified identifier */
+#define is_xmlqnamechar(c) ((c >= 'a' && c <= 'z') || c == '_' || c == '-' || \
+ (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || /* c == ':' || */ \
+ c == '.' || c == 0xb7 || (c >= 0x370 && c <= 0x1fff && c != 0x37e ) ||\
+ (c >= 0xc0 && c <= 0x2ff && c != 0xd7 && c != 0xf7) || c == 0x200c || \
+ c == 0x200d || (c >= 0x300 && c <= 0x36f) || \
+ (c >= 0x2070 && c <= 0x218f) || (c >= 0x2030f && c <= 0x2040) || \
+ (c >= 0x2c00 && c <= 0x2fef) || (c >= 0x3001 && c <= 0xd7ff) || \
+ (c >= 0xf900 && c <= 0xfdcf) || (c >= 0xfdf0 && c <= 0xfffd) || \
+ (c >= 0x10000 && c <= 0xeffff))
+
struct lyxml_ns {
const char *element; /* element where the namespace is defined */
char *prefix; /* prefix of the namespace, NULL for the default namespace */
diff --git a/src/xpath.c b/src/xpath.c
new file mode 100644
index 0000000..4a3792d
--- /dev/null
+++ b/src/xpath.c
@@ -0,0 +1,362 @@
+/**
+ * @file xpath.c
+ * @author Michal Vasko <mvasko@cesnet.cz>
+ * @brief YANG XPath evaluation functions
+ *
+ * Copyright (c) 2015 - 2017 CESNET, z.s.p.o.
+ *
+ * This source code is licensed under BSD 3-Clause License (the "License").
+ * You may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * https://opensource.org/licenses/BSD-3-Clause
+ */
+
+#include "common.h"
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <assert.h>
+#include <limits.h>
+#include <errno.h>
+#include <math.h>
+#include <pcre.h>
+
+#include "xpath.h"
+#include "xml.h"
+
+/**
+ * @brief Parse NCName.
+ *
+ * @param[in] ncname Name to parse.
+ *
+ * @return Length of \p ncname valid bytes.
+ */
+static size_t
+parse_ncname(const char *ncname)
+{
+ unsigned int uc;
+ size_t size, len = 0;
+
+ LY_CHECK_RET(ly_getutf8(&ncname, &uc, &size), 0);
+ if (!is_xmlqnamestartchar(uc) || (uc == ':')) {
+ return len;
+ }
+
+ do {
+ len += size;
+ LY_CHECK_RET(ly_getutf8(&ncname, &uc, &size), 0);
+ } while (is_xmlqnamechar(uc) && (uc != ':'));
+
+ return len;
+}
+
+/**
+ * @brief Add \p token into the expression \p exp.
+ *
+ * @param[in] ctx libyang context to log in.
+ * @param[in] exp Expression to use.
+ * @param[in] token Token to add.
+ * @param[in] expr_pos Token position in the XPath expression.
+ * @param[in] tok_len Token length in the XPath expression.
+ * @return LY_ERR value
+ */
+static LY_ERR
+exp_add_token(struct ly_ctx *ctx, struct lyxp_expr *exp, enum lyxp_token token, uint16_t expr_pos, uint16_t tok_len)
+{
+ uint32_t prev;
+
+ if (exp->used == exp->size) {
+ prev = exp->size;
+ exp->size += LYXP_EXPR_SIZE_STEP;
+ if (prev > exp->size) {
+ LOGINT(ctx);
+ return LY_EINT;
+ }
+
+ exp->tokens = ly_realloc(exp->tokens, exp->size * sizeof *exp->tokens);
+ LY_CHECK_ERR_RET(!exp->tokens, LOGMEM(ctx), LY_EMEM);
+ exp->tok_pos = ly_realloc(exp->tok_pos, exp->size * sizeof *exp->tok_pos);
+ LY_CHECK_ERR_RET(!exp->tok_pos, LOGMEM(ctx), LY_EMEM);
+ exp->tok_len = ly_realloc(exp->tok_len, exp->size * sizeof *exp->tok_len);
+ LY_CHECK_ERR_RET(!exp->tok_len, LOGMEM(ctx), LY_EMEM);
+ }
+
+ exp->tokens[exp->used] = token;
+ exp->tok_pos[exp->used] = expr_pos;
+ exp->tok_len[exp->used] = tok_len;
+ ++exp->used;
+ return LY_SUCCESS;
+}
+
+void
+lyxp_expr_free(struct ly_ctx *ctx, struct lyxp_expr *expr)
+{
+ uint16_t i;
+
+ if (!expr) {
+ return;
+ }
+
+ lydict_remove(ctx, expr->expr);
+ free(expr->tokens);
+ free(expr->tok_pos);
+ free(expr->tok_len);
+ if (expr->repeat) {
+ for (i = 0; i < expr->used; ++i) {
+ free(expr->repeat[i]);
+ }
+ }
+ free(expr->repeat);
+ free(expr);
+}
+
+struct lyxp_expr *
+lyxp_expr_parse(struct ly_ctx *ctx, const char *expr)
+{
+ struct lyxp_expr *ret;
+ size_t parsed = 0, tok_len, ncname_len;
+ enum lyxp_token tok_type;
+ int prev_function_check = 0;
+
+ if (strlen(expr) > UINT16_MAX) {
+ LOGERR(ctx, LY_EINVAL, "XPath expression cannot be longer than %ud characters.", UINT16_MAX);
+ return NULL;
+ }
+
+ /* init lyxp_expr structure */
+ ret = calloc(1, sizeof *ret);
+ LY_CHECK_ERR_GOTO(!ret, LOGMEM(ctx), error);
+ ret->expr = lydict_insert(ctx, expr, strlen(expr));
+ LY_CHECK_ERR_GOTO(!ret->expr, LOGMEM(ctx), error);
+ ret->used = 0;
+ ret->size = LYXP_EXPR_SIZE_START;
+ ret->tokens = malloc(ret->size * sizeof *ret->tokens);
+ LY_CHECK_ERR_GOTO(!ret->tokens, LOGMEM(ctx), error);
+
+ ret->tok_pos = malloc(ret->size * sizeof *ret->tok_pos);
+ LY_CHECK_ERR_GOTO(!ret->tok_pos, LOGMEM(ctx), error);
+
+ ret->tok_len = malloc(ret->size * sizeof *ret->tok_len);
+ LY_CHECK_ERR_GOTO(!ret->tok_len, LOGMEM(ctx), error);
+
+ while (is_xmlws(expr[parsed])) {
+ ++parsed;
+ }
+
+ do {
+ if (expr[parsed] == '(') {
+
+ /* '(' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_PAR1;
+
+ if (prev_function_check && ret->used && (ret->tokens[ret->used - 1] == LYXP_TOKEN_NAMETEST)) {
+ /* it is a NodeType/FunctionName after all */
+ if (((ret->tok_len[ret->used - 1] == 4)
+ && (!strncmp(&expr[ret->tok_pos[ret->used - 1]], "node", 4)
+ || !strncmp(&expr[ret->tok_pos[ret->used - 1]], "text", 4))) ||
+ ((ret->tok_len[ret->used - 1] == 7)
+ && !strncmp(&expr[ret->tok_pos[ret->used - 1]], "comment", 7))) {
+ ret->tokens[ret->used - 1] = LYXP_TOKEN_NODETYPE;
+ } else {
+ ret->tokens[ret->used - 1] = LYXP_TOKEN_FUNCNAME;
+ }
+ prev_function_check = 0;
+ }
+
+ } else if (expr[parsed] == ')') {
+
+ /* ')' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_PAR2;
+
+ } else if (expr[parsed] == '[') {
+
+ /* '[' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_BRACK1;
+
+ } else if (expr[parsed] == ']') {
+
+ /* ']' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_BRACK2;
+
+ } else if (!strncmp(&expr[parsed], "..", 2)) {
+
+ /* '..' */
+ tok_len = 2;
+ tok_type = LYXP_TOKEN_DDOT;
+
+ } else if ((expr[parsed] == '.') && (!isdigit(expr[parsed + 1]))) {
+
+ /* '.' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_DOT;
+
+ } else if (expr[parsed] == '@') {
+
+ /* '@' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_AT;
+
+ } else if (expr[parsed] == ',') {
+
+ /* ',' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_COMMA;
+
+ } else if (expr[parsed] == '\'') {
+
+ /* Literal with ' */
+ for (tok_len = 1; (expr[parsed + tok_len] != '\0') && (expr[parsed + tok_len] != '\''); ++tok_len);
+ LY_CHECK_ERR_GOTO(expr[parsed + tok_len] == '\0',
+ LOGVAL(ctx, LY_VLOG_NONE, NULL, LY_VCODE_XP_EOE, expr[parsed], &expr[parsed]), error);
+ ++tok_len;
+ tok_type = LYXP_TOKEN_LITERAL;
+
+ } else if (expr[parsed] == '\"') {
+
+ /* Literal with " */
+ for (tok_len = 1; (expr[parsed + tok_len] != '\0') && (expr[parsed + tok_len] != '\"'); ++tok_len);
+ LY_CHECK_ERR_GOTO(expr[parsed + tok_len] == '\0',
+ LOGVAL(ctx, LY_VLOG_NONE, NULL, LY_VCODE_XP_EOE, expr[parsed], &expr[parsed]), error);
+ ++tok_len;
+ tok_type = LYXP_TOKEN_LITERAL;
+
+ } else if ((expr[parsed] == '.') || (isdigit(expr[parsed]))) {
+
+ /* Number */
+ for (tok_len = 0; isdigit(expr[parsed + tok_len]); ++tok_len);
+ if (expr[parsed + tok_len] == '.') {
+ ++tok_len;
+ for (; isdigit(expr[parsed + tok_len]); ++tok_len);
+ }
+ tok_type = LYXP_TOKEN_NUMBER;
+
+ } else if (expr[parsed] == '/') {
+
+ /* Operator '/', '//' */
+ if (!strncmp(&expr[parsed], "//", 2)) {
+ tok_len = 2;
+ } else {
+ tok_len = 1;
+ }
+ tok_type = LYXP_TOKEN_OPERATOR_PATH;
+
+ } else if (!strncmp(&expr[parsed], "!=", 2) || !strncmp(&expr[parsed], "<=", 2)
+ || !strncmp(&expr[parsed], ">=", 2)) {
+
+ /* Operator '!=', '<=', '>=' */
+ tok_len = 2;
+ tok_type = LYXP_TOKEN_OPERATOR_COMP;
+
+ } else if (expr[parsed] == '|') {
+
+ /* Operator '|' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_OPERATOR_UNI;
+
+ } else if ((expr[parsed] == '+') || (expr[parsed] == '-')) {
+
+ /* Operator '+', '-' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_OPERATOR_MATH;
+
+ } else if ((expr[parsed] == '=') || (expr[parsed] == '<') || (expr[parsed] == '>')) {
+
+ /* Operator '=', '<', '>' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_OPERATOR_COMP;
+
+ } else if (ret->used && (ret->tokens[ret->used - 1] != LYXP_TOKEN_AT)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_PAR1)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_BRACK1)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_COMMA)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_OPERATOR_LOG)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_OPERATOR_COMP)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_OPERATOR_MATH)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_OPERATOR_UNI)
+ && (ret->tokens[ret->used - 1] != LYXP_TOKEN_OPERATOR_PATH)) {
+
+ /* Operator '*', 'or', 'and', 'mod', or 'div' */
+ if (expr[parsed] == '*') {
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_OPERATOR_MATH;
+
+ } else if (!strncmp(&expr[parsed], "or", 2)) {
+ tok_len = 2;
+ tok_type = LYXP_TOKEN_OPERATOR_LOG;
+
+ } else if (!strncmp(&expr[parsed], "and", 3)) {
+ tok_len = 3;
+ tok_type = LYXP_TOKEN_OPERATOR_LOG;
+
+ } else if (!strncmp(&expr[parsed], "mod", 3) || !strncmp(&expr[parsed], "div", 3)) {
+ tok_len = 3;
+ tok_type = LYXP_TOKEN_OPERATOR_MATH;
+
+ } else if (prev_function_check) {
+ LOGVAL(ctx, LY_VLOG_NONE, NULL, LYVE_XPATH, "Invalid character 0x%x, perhaps \"%.*s\" is supposed to be a function call.",
+ expr[parsed], &expr[parsed], ret->tok_len[ret->used - 1], &ret->expr[ret->tok_pos[ret->used - 1]]);
+ goto error;
+ } else {
+ LOGVAL(ctx, LY_VLOG_NONE, NULL, LY_VCODE_XP_INEXPR, expr[parsed], &expr[parsed]);
+ goto error;
+ }
+ } else if (expr[parsed] == '*') {
+
+ /* NameTest '*' */
+ tok_len = 1;
+ tok_type = LYXP_TOKEN_NAMETEST;
+
+ } else {
+
+ /* NameTest (NCName ':' '*' | QName) or NodeType/FunctionName */
+ ncname_len = parse_ncname(&expr[parsed]);
+ LY_CHECK_ERR_GOTO(!ncname_len, LOGVAL(ctx, LY_VLOG_NONE, NULL, LY_VCODE_XP_INEXPR, expr[parsed], &expr[parsed]), error);
+ tok_len = ncname_len;
+
+ if (expr[parsed + tok_len] == ':') {
+ ++tok_len;
+ if (expr[parsed + tok_len] == '*') {
+ ++tok_len;
+ } else {
+ ncname_len = parse_ncname(&expr[parsed + tok_len]);
+ LY_CHECK_ERR_GOTO(!ncname_len, LOGVAL(ctx, LY_VLOG_NONE, NULL, LY_VCODE_XP_INEXPR, expr[parsed], &expr[parsed]), error);
+ tok_len += ncname_len;
+ }
+ /* remove old flag to prevent ambiguities */
+ prev_function_check = 0;
+ tok_type = LYXP_TOKEN_NAMETEST;
+ } else {
+ /* there is no prefix so it can still be NodeType/FunctionName, we can't finally decide now */
+ prev_function_check = 1;
+ tok_type = LYXP_TOKEN_NAMETEST;
+ }
+ }
+
+ /* store the token, move on to the next one */
+ LY_CHECK_GOTO(exp_add_token(ctx, ret, tok_type, parsed, tok_len), error);
+ parsed += tok_len;
+ while (is_xmlws(expr[parsed])) {
+ ++parsed;
+ }
+
+ } while (expr[parsed]);
+
+ /* prealloc repeat */
+ ret->repeat = calloc(ret->size, sizeof *ret->repeat);
+ LY_CHECK_ERR_GOTO(!ret->repeat, LOGMEM(ctx), error);
+
+ return ret;
+
+error:
+ lyxp_expr_free(ctx, ret);
+ return NULL;
+}
+
diff --git a/src/xpath.h b/src/xpath.h
new file mode 100644
index 0000000..df3a4f9
--- /dev/null
+++ b/src/xpath.h
@@ -0,0 +1,359 @@
+/**
+ * @file xpath.h
+ * @author Michal Vasko <mvasko@cesnet.cz>
+ * @brief YANG XPath evaluation functions header
+ *
+ * Copyright (c) 2015 CESNET, z.s.p.o.
+ *
+ * This source code is licensed under BSD 3-Clause License (the "License").
+ * You may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * https://opensource.org/licenses/BSD-3-Clause
+ */
+
+#ifndef _XPATH_H
+#define _XPATH_H
+
+#include <stdint.h>
+
+#include "libyang.h"
+#include "tree_schema.h"
+#if 0
+#include "tree_data.h"
+#endif
+/*
+ * XPath evaluator fully compliant with http://www.w3.org/TR/1999/REC-xpath-19991116/
+ * except the following restrictions in the grammar.
+ *
+ * PARSED GRAMMAR
+ *
+ * Full axes are not supported, abbreviated forms must be used,
+ * variables are not supported, "id()" function is not supported,
+ * and processing instruction and comment nodes are not supported,
+ * which is also reflected in the grammar. Undefined rules and
+ * constants are tokens.
+ *
+ * Modified full grammar:
+ *
+ * [1] Expr ::= OrExpr // just an alias
+ *
+ * [2] LocationPath ::= RelativeLocationPath | AbsoluteLocationPath
+ * [3] AbsoluteLocationPath ::= '/' RelativeLocationPath? | '//' RelativeLocationPath
+ * [4] RelativeLocationPath ::= Step | RelativeLocationPath '/' Step | RelativeLocationPath '//' Step
+ * [5] Step ::= '@'? NodeTest Predicate* | '.' | '..'
+ * [6] NodeTest ::= NameTest | NodeType '(' ')'
+ * [7] Predicate ::= '[' Expr ']'
+ * [8] PrimaryExpr ::= '(' Expr ')' | Literal | Number | FunctionCall
+ * [9] FunctionCall ::= FunctionName '(' ( Expr ( ',' Expr )* )? ')'
+ * [10] PathExpr ::= LocationPath | PrimaryExpr Predicate*
+ * | PrimaryExpr Predicate* '/' RelativeLocationPath
+ * | PrimaryExpr Predicate* '//' RelativeLocationPath
+ * [11] OrExpr ::= AndExpr | OrExpr 'or' AndExpr
+ * [12] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr
+ * [13] EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr
+ * | EqualityExpr '!=' RelationalExpr
+ * [14] RelationalExpr ::= AdditiveExpr
+ * | RelationalExpr '<' AdditiveExpr
+ * | RelationalExpr '>' AdditiveExpr
+ * | RelationalExpr '<=' AdditiveExpr
+ * | RelationalExpr '>=' AdditiveExpr
+ * [15] AdditiveExpr ::= MultiplicativeExpr
+ * | AdditiveExpr '+' MultiplicativeExpr
+ * | AdditiveExpr '-' MultiplicativeExpr
+ * [16] MultiplicativeExpr ::= UnaryExpr
+ * | MultiplicativeExpr '*' UnaryExpr
+ * | MultiplicativeExpr 'div' UnaryExpr
+ * | MultiplicativeExpr 'mod' UnaryExpr
+ * [17] UnaryExpr ::= UnionExpr | '-' UnaryExpr
+ * [18] UnionExpr ::= PathExpr | UnionExpr '|' PathExpr
+ */
+
+/* expression tokens allocation */
+#define LYXP_EXPR_SIZE_START 10
+#define LYXP_EXPR_SIZE_STEP 5
+
+/* XPath matches allocation */
+#define LYXP_SET_SIZE_START 2
+#define LYXP_SET_SIZE_STEP 2
+
+/* building string when casting */
+#define LYXP_STRING_CAST_SIZE_START 64
+#define LYXP_STRING_CAST_SIZE_STEP 16
+
+/**
+ * @brief Tokens that can be in an XPath expression.
+ */
+enum lyxp_token {
+ LYXP_TOKEN_NONE = 0,
+ LYXP_TOKEN_PAR1, /* '(' */
+ LYXP_TOKEN_PAR2, /* ')' */
+ LYXP_TOKEN_BRACK1, /* '[' */
+ LYXP_TOKEN_BRACK2, /* ']' */
+ LYXP_TOKEN_DOT, /* '.' */
+ LYXP_TOKEN_DDOT, /* '..' */
+ LYXP_TOKEN_AT, /* '@' */
+ LYXP_TOKEN_COMMA, /* ',' */
+ /* LYXP_TOKEN_DCOLON, * '::' * axes not supported */
+ LYXP_TOKEN_NAMETEST, /* NameTest */
+ LYXP_TOKEN_NODETYPE, /* NodeType */
+ LYXP_TOKEN_FUNCNAME, /* FunctionName */
+ LYXP_TOKEN_OPERATOR_LOG, /* Operator 'and', 'or' */
+ LYXP_TOKEN_OPERATOR_COMP, /* Operator '=', '!=', '<', '<=', '>', '>=' */
+ LYXP_TOKEN_OPERATOR_MATH, /* Operator '+', '-', '*', 'div', 'mod', '-' (unary) */
+ LYXP_TOKEN_OPERATOR_UNI, /* Operator '|' */
+ LYXP_TOKEN_OPERATOR_PATH, /* Operator '/', '//' */
+ /* LYXP_TOKEN_AXISNAME, * AxisName * axes not supported */
+ LYXP_TOKEN_LITERAL, /* Literal - with either single or double quote */
+ LYXP_TOKEN_NUMBER /* Number */
+};
+
+/**
+ * @brief XPath (sub)expressions that can be repeated.
+ */
+enum lyxp_expr_type {
+ LYXP_EXPR_NONE = 0,
+ LYXP_EXPR_OR,
+ LYXP_EXPR_AND,
+ LYXP_EXPR_EQUALITY,
+ LYXP_EXPR_RELATIONAL,
+ LYXP_EXPR_ADDITIVE,
+ LYXP_EXPR_MULTIPLICATIVE,
+ LYXP_EXPR_UNARY,
+ LYXP_EXPR_UNION,
+};
+
+/**
+ * @brief Structure holding a parsed XPath expression.
+ */
+struct lyxp_expr {
+ enum lyxp_token *tokens; /* array of tokens */
+ uint16_t *tok_pos; /* array of the token offsets in expr */
+ uint16_t *tok_len; /* array of token lengths in expr */
+ enum lyxp_expr_type **repeat; /* array of expression types that this token begins and is repeated ended with 0,
+ more in the comment after this declaration */
+ uint16_t used; /* used array items */
+ uint16_t size; /* allocated array items */
+
+ const char *expr; /* the original XPath expression */
+};
+
+/*
+ * lyxp_expr repeat
+ *
+ * This value is NULL for all the tokens that do not begin an
+ * expression which can be repeated. Otherwise it is an array
+ * of expression types that this token begins. These values
+ * are used during evaluation to know whether we need to
+ * duplicate the current context or not and to decide what
+ * the current expression is (for example, if we are only
+ * starting the parsing and the first token has no repeat,
+ * we do not parse it as an OrExpr but directly as PathExpr).
+ * Examples:
+ *
+ * Expression: "/ *[key1 and key2 or key1 < key2]"
+ * Tokens: '/', '*', '[', NameTest, 'and', NameTest, 'or', NameTest, '<', NameTest, ']'
+ * Repeat: NULL, NULL, NULL, [AndExpr, NULL, NULL, NULL, [RelationalExpr, NULL, NULL, NULL
+ * OrExpr, 0],
+ * 0],
+ *
+ * Expression: "//node[key and node2]/key | /cont"
+ * Tokens: '//', 'NameTest', '[', 'NameTest', 'and', 'NameTest', ']', '/', 'NameTest', '|', '/', 'NameTest'
+ * Repeat: [UnionExpr, NULL, NULL, [AndExpr, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
+ * 0], 0],
+ *
+ * Operators between expressions which this concerns:
+ * 'or', 'and', '=', '!=', '<', '>', '<=', '>=', '+', '-', '*', 'div', 'mod', '|'
+ */
+
+/**
+ * @brief Supported types of (partial) XPath results.
+ */
+enum lyxp_set_type {
+ LYXP_SET_EMPTY = 0,
+ LYXP_SET_NODE_SET,
+ LYXP_SET_SNODE_SET,
+ LYXP_SET_BOOLEAN,
+ LYXP_SET_NUMBER,
+ LYXP_SET_STRING
+};
+#if 0
+#ifdef LY_ENABLED_CACHE
+
+/**
+ * @brief Item stored in an XPath set hash table.
+ */
+struct lyxp_set_hash_node {
+ struct lyd_node *node;
+ enum lyxp_node_type type;
+} _PACKED;
+
+#endif
+
+/**
+ * @brief XPath set - (partial) result.
+ */
+struct lyxp_set {
+ enum lyxp_set_type type;
+ union {
+ struct lyxp_set_node {
+ struct lyd_node *node;
+ enum lyxp_node_type type;
+ uint32_t pos;
+ } *nodes;
+ struct lyxp_set_snode {
+ struct lys_node *snode;
+ enum lyxp_node_type type;
+ /* 0 - snode was traversed, but not currently in the context,
+ * 1 - snode currently in context,
+ * 2 - snode in context and just added, so skip it for the current operation,
+ * >=3 - snode is not in context because we are in a predicate and this snode was used/will be used later */
+ uint32_t in_ctx;
+ } *snodes;
+ struct lyxp_set_attr {
+ struct lyd_attr *attr;
+ enum lyxp_node_type type;
+ uint32_t pos; /* if node_type is LYXP_SET_NODE_ATTR, it is the parent node position */
+ } *attrs;
+ char *str;
+ long double num;
+ int bool;
+ } val;
+
+ /* this is valid only for type LYXP_SET_NODE_SET and LYXP_SET_SNODE_SET */
+ uint32_t used;
+ uint32_t size;
+#ifdef LY_ENABLED_CACHE
+ struct hash_table *ht;
+#endif
+ /* this is valid only for type LYXP_SET_NODE_SET */
+ uint32_t ctx_pos;
+ uint32_t ctx_size;
+};
+
+/**
+ * @brief Evaluate the XPath expression \p expr on data. Be careful when using this function, the result can often
+ * be confusing without thorough understanding of XPath evaluation rules defined in RFC 6020.
+ *
+ * @param[in] expr XPath expression to evaluate. Must be in JSON format (prefixes are model names).
+ * @param[in] cur_node Current (context) data node. If the node has #LYD_VAL_INUSE flag, it is considered dummy (intended
+ * for but not restricted to evaluation with the LYXP_WHEN flag).
+ * @param[in] cur_node_type Current (context) data node type. For every standard case use #LYXP_NODE_ELEM. But there are
+ * cases when the context node \p cur_node is actually supposed to be the XML root, there is no such data node. So, in
+ * this case just pass the first top-level node into \p cur_node and use an enum value for this kind of root
+ * (#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,
+ * but there are no use-cases in YANG.
+ * @param[in] local_mod Local module relative to the \p expr. Used only to determine the internal canonical value for identities.
+ * @param[out] set Result set. Must be valid and in the same libyang context as \p cur_node.
+ * To be safe, always either zero or cast the \p set to empty. After done using, either cast
+ * the \p set to empty (if allocated statically) or free it (if allocated dynamically) to
+ * prevent memory leaks.
+ * @param[in] options Whether to apply some evaluation restrictions.
+ * LYXP_MUST - apply must data tree access restrictions.
+ * LYXP_WHEN - apply when data tree access restrictions and consider LYD_WHEN flags in data nodes.
+ *
+ * @return EXIT_SUCCESS on success, EXIT_FAILURE on unresolved when dependency, -1 on error.
+ */
+int lyxp_eval(const char *expr, const struct lyd_node *cur_node, enum lyxp_node_type cur_node_type,
+ const struct lys_module *local_mod, struct lyxp_set *set, int options);
+
+/**
+ * @brief Get all the partial XPath nodes (atoms) that are required for \p expr to be evaluated.
+ *
+ * If any LYXP_SNODE* options is set, only fatal errors are printed, otherwise they are downgraded
+ * to warnings.
+ *
+ * @param[in] expr XPath expression to be evaluated. Must be in JSON format (prefixes are model names).
+ * @param[in] cur_snode Current (context) schema node.
+ * @param[in] cur_snode_type Current (context) schema node type.
+ * @param[out] set Result set. Must be valid and in the same libyang context as \p cur_snode.
+ * To be safe, always either zero or cast the \p set to empty. After done using, either cast
+ * the \p set to empty (if allocated statically) or free it (if allocated dynamically) to
+ * prevent memory leaks.
+ * @param[in] options Whether to apply some evaluation restrictions, one flag must always be used.
+ * LYXP_SNODE - no special data tree access modifiers.
+ * LYXP_SNODE_MUST - apply must data tree access restrictions.
+ * LYXP_SNODE_WHEN - apply when data tree access restrictions.
+ * LYXP_SNODE_OUTPUT - search RPC/action output instead input
+ * @param[out] ctx_snode Actual context node for the expression (it often changes for "when" expressions).
+ *
+ * @return EXIT_SUCCESS on success, -1 on error.
+ */
+int lyxp_atomize(const char *expr, const struct lys_node *cur_snode, enum lyxp_node_type cur_snode_type,
+ struct lyxp_set *set, int options, const struct lys_node **ctx_snode);
+
+/* these are used only internally */
+#define LYXP_SNODE 0x04
+#define LYXP_SNODE_MUST 0x08
+#define LYXP_SNODE_WHEN 0x10
+#define LYXP_SNODE_OUTPUT 0x20
+
+#define LYXP_SNODE_ALL 0x1C
+
+/**
+ * @brief Works like lyxp_atomize(), but it is executed on all the when and must expressions
+ * which the node has.
+ *
+ * @param[in] node Node to examine.
+ * @param[in,out] set Resulting set of atoms merged from all the expressions.
+ * Will be cleared before use.
+ * @param[in] set_ext_dep_flags Whether to set #LYS_XPCONF_DEP or #LYS_XPSTATE_DEP for conditions that
+ * require foreign configuration or state subtree and also for the node itself, if it has any such condition.
+ *
+ * @return EXIT_SUCCESS on success, -1 on error.
+ */
+int lyxp_node_atomize(const struct lys_node *node, struct lyxp_set *set, int set_ext_dep_flags);
+#endif
+/**
+ * @brief Check syntax of all the XPath expressions of the node.
+ *
+ * @param[in] node Node to examine.
+ *
+ * @return LY_ERR value.
+ */
+LY_ERR lyxp_node_check_syntax(const struct lysc_node *node);
+#if 0
+/**
+ * @brief Cast XPath set to another type.
+ * Indirectly context position aware.
+ *
+ * @param[in] set Set to cast.
+ * @param[in] target Target type to cast \p set into.
+ * @param[in] cur_node Current (context) data node. Cannot be NULL.
+ * @param[in] local_mod Local expression module.
+ * @param[in] options Whether to apply some evaluation restrictions.
+ *
+ * @return EXIT_SUCCESS on success, -1 on error.
+ */
+int lyxp_set_cast(struct lyxp_set *set, enum lyxp_set_type target, const struct lyd_node *cur_node,
+ const struct lys_module *local_mod, int options);
+
+/**
+ * @brief Free contents of an XPath \p set.
+ *
+ * @param[in] set Set to free.
+ */
+void lyxp_set_free(struct lyxp_set *set);
+#endif
+/**
+ * @brief Parse an XPath expression into a structure of tokens.
+ * Logs directly.
+ *
+ * http://www.w3.org/TR/1999/REC-xpath-19991116/ section 3.7
+ *
+ * @param[in] ctx Context for errors.
+ * @param[in] expr XPath expression to parse. It is duplicated.
+ *
+ * @return Filled expression structure or NULL on error.
+ */
+struct lyxp_expr *lyxp_expr_parse(struct ly_ctx *ctx, const char *expr);
+
+/**
+ * @brief Frees a parsed XPath expression. \p expr should not be used afterwards.
+ *
+ * @param[in] ctx libyang context of the expression.
+ * @param[in] expr Expression to free.
+ */
+void lyxp_expr_free(struct ly_ctx *ctx, struct lyxp_expr *expr);
+
+#endif /* _XPATH_H */