<commit_before>/**
 * @file xpath.h
 * @author <NAME> <<EMAIL>>
 * @brief YANG XPath evaluation functions header
 *
 * Copyright (c) 2015 - 2020 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 LY_XPATH_H
#define LY_XPATH_H

#include <stddef.h>
#include <stdint.h>

#include "compat.h"
#include "log.h"
#include "tree.h"
#include "tree_schema.h"

struct ly_ctx;
struct lyd_node;

/**
 * @internal
 * @page internals
 * @section internalsXpath XPath Implementation
 *
 * XPath evaluator fully compliant with http://www.w3.org/TR/1999/REC-xpath-19991116/
 * except the following restrictions in the grammar.
 *
 * @subsection internalsXpathGrammar 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:
 * @code
 * [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] NameTest ::= '*' | NCName ':' '*' | QName
 * [8] NodeType ::= 'text' | 'node'
 * [9] Predicate ::= '[' Expr ']'
 * [10] PrimaryExpr ::= '(' Expr ')' | Literal | Number | FunctionCall
 * [11] FunctionCall ::= FunctionName '(' ( Expr ( ',' Expr )* )? ')'
 * [12] PathExpr ::= LocationPath | PrimaryExpr Predicate*
 *                 | PrimaryExpr Predicate* '/' RelativeLocationPath
 *                 | PrimaryExpr Predicate* '//' RelativeLocationPath
 * [13] OrExpr ::= AndExpr | OrExpr 'or' AndExpr
 * [14] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr
 * [15] EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr
 *                     | EqualityExpr '!=' RelationalExpr
 * [16] RelationalExpr ::= AdditiveExpr
 *                       | RelationalExpr '<' AdditiveExpr
 *                       | RelationalExpr '>' AdditiveExpr
 *                       | RelationalExpr '<=' AdditiveExpr
 *                       | RelationalExpr '>=' AdditiveExpr
 * [17] AdditiveExpr ::= MultiplicativeExpr
 *                     | AdditiveExpr '+' MultiplicativeExpr
 *                     | AdditiveExpr '-' MultiplicativeExpr
 * [18] MultiplicativeExpr ::= UnaryExpr
 *                     | MultiplicativeExpr '*' UnaryExpr
 *                     | MultiplicativeExpr 'div' UnaryExpr
 *                     | MultiplicativeExpr 'mod' UnaryExpr
 * [19] UnaryExpr ::= UnionExpr | '-' UnaryExpr
 * [20] UnionExpr ::= PathExpr | UnionExpr '|' PathExpr
 * @endcode
 */

/* 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

/* Maximum number of nested expressions. */
#define LYXP_MAX_BLOCK_DEPTH 100

/**
 * @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_OPER_LOG,      /* Operator 'and', 'or' */
    LYXP_TOKEN_OPER_EQUAL,    /* Operator '=' */
    LYXP_TOKEN_OPER_NEQUAL,   /* Operator '!=' */
    LYXP_TOKEN_OPER_COMP,     /* Operator '<', '<=', '>', '>=' */
    LYXP_TOKEN_OPER_MATH,     /* Operator '+', '-', '*', 'div', 'mod', '-' (unary) */
    LYXP_TOKEN_OPER_UNI,      /* Operator '|' */
    LYXP_TOKEN_OPER_PATH,     /* Operator '/' */
    LYXP_TOKEN_OPER_RPATH,    /* Operator '//' (recursive path) */
    /* 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 Types of context nodes, #LYXP_NODE_ROOT_CONFIG used only in when or must conditions.
 */
enum lyxp_node_type {
    LYXP_NODE_NONE,             /* invalid node type */

    /* XML document roots */
    LYXP_NODE_ROOT,             /* access to all the data (node value first top-level node) */
    LYXP_NODE_ROOT_CONFIG,      /* <running> data context, no state data (node value first top-level node) */

    /* XML elements */
    LYXP_NODE_ELEM,             /* YANG data element (most common) */
    LYXP_NODE_TEXT,             /* YANG data text element (extremely specific use, unlikely to be ever needed) */
    LYXP_NODE_META              /* YANG metadata (do not use for the context node) */
};

/**
 * @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_NODE_SET = 0,<commit_msg>xpath DOC change explanation of repeat structure<commit_after>/**
 * @file xpath.h
 * @author <NAME> <<EMAIL>>
 * @brief YANG XPath evaluation functions header
 *
 * Copyright (c) 2015 - 2020 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 LY_XPATH_H
#define LY_XPATH_H

#include <stddef.h>
#include <stdint.h>

#include "compat.h"
#include "log.h"
#include "tree.h"
#include "tree_schema.h"

struct ly_ctx;
struct lyd_node;

/**
 * @internal
 * @page internals
 * @section internalsXpath XPath Implementation
 *
 * XPath evaluator fully compliant with http://www.w3.org/TR/1999/REC-xpath-19991116/
 * except the following restrictions in the grammar.
 *
 * @subsection internalsXpathGrammar 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:
 * @code
 * [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] NameTest ::= '*' | NCName ':' '*' | QName
 * [8] NodeType ::= 'text' | 'node'
 * [9] Predicate ::= '[' Expr ']'
 * [10] PrimaryExpr ::= '(' Expr ')' | Literal | Number | FunctionCall
 * [11] FunctionCall ::= FunctionName '(' ( Expr ( ',' Expr )* )? ')'
 * [12] PathExpr ::= LocationPath | PrimaryExpr Predicate*
 *                 | PrimaryExpr Predicate* '/' RelativeLocationPath
 *                 | PrimaryExpr Predicate* '//' RelativeLocationPath
 * [13] OrExpr ::= AndExpr | OrExpr 'or' AndExpr
 * [14] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr
 * [15] EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr
 *                     | EqualityExpr '!=' RelationalExpr
 * [16] RelationalExpr ::= AdditiveExpr
 *                       | RelationalExpr '<' AdditiveExpr
 *                       | RelationalExpr '>' AdditiveExpr
 *                       | RelationalExpr '<=' AdditiveExpr
 *                       | RelationalExpr '>=' AdditiveExpr
 * [17] AdditiveExpr ::= MultiplicativeExpr
 *                     | AdditiveExpr '+' MultiplicativeExpr
 *                     | AdditiveExpr '-' MultiplicativeExpr
 * [18] MultiplicativeExpr ::= UnaryExpr
 *                     | MultiplicativeExpr '*' UnaryExpr
 *                     | MultiplicativeExpr 'div' UnaryExpr
 *                     | MultiplicativeExpr 'mod' UnaryExpr
 * [19] UnaryExpr ::= UnionExpr | '-' UnaryExpr
 * [20] UnionExpr ::= PathExpr | UnionExpr '|' PathExpr
 * @endcode
 */

/* 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

/* Maximum number of nested expressions. */
#define LYXP_MAX_BLOCK_DEPTH 100

/**
 * @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_OPER_LOG,      /* Operator 'and', 'or' */
    LYXP_TOKEN_OPER_EQUAL,    /* Operator '=' */
    LYXP_TOKEN_OPER_NEQUAL,   /* Operator '!=' */
    LYXP_TOKEN_OPER_COMP,     /* Operator '<', '<=', '>', '>=' */
    LYXP_TOKEN_OPER_MATH,     /* Operator '+', '-', '*', 'div', 'mod', '-' (unary) */
    LYXP_TOKEN_OPER_UNI,      /* Operator '|' */
    LYXP_TOKEN_OPER_PATH,     /* Operator '/' */
    LYXP_TOKEN_OPER_RPATH,    /* Operator '//' (recursive path) */
    /* 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 Types of context nodes, #LYXP_NODE_ROOT_CONFIG used only in when or must conditions.
 */
enum lyxp_node_type {
    LYXP_NODE_NONE,             /* invalid node type */

    /* XML document roots */
    LYXP_NODE_ROOT,             /* access to all the data (node value first top-level node) */
    LYXP_NODE_ROOT_CONFIG,      /* <running> data context, no state data (node value first top-level node) */

    /* XML elements */
    LYXP_NODE_ELEM,             /* YANG data element (most common) */
    LYXP_NODE_TEXT,             /* YANG data text element (extremely specific use, unlikely to be ever needed) */
    LYXP_NODE_META              /* YANG metadata (do not use for the context node) */
};

/**
 * @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:
 *
 * Expr:   "/ *[key1 and key2 or key1 < key2]"
 * Tokens: '/'  '*'  '['  NameTest 'and'  NameTest 'or' NameTest       '<'  NameTest ']'
 * Repeat: NULL NULL NULL _        NULL   NULL     NULL _              NULL NULL     NULL
 *                        |                             v
 *                        v                             RelationalExpr 0
 *                        AndExpr  OrExpr 0
 *
 * Expr:   "//node[key and node2]/key | /cont"
 * Tokens: '//'      NameTest '['  NameTest 'and' NameTest ']'  '/'  NameTest '|'  '/'  NameTest
 * Repeat: _         NULL     NULL _        NULL  NULL     NULL NULL NULL     NULL NULL NULL
 *         |                       v
 *         v                       AndExpr  0
 *         UnionExpr 0
 *
 * Operators between expressions which this concerns:
 *     'or', 'and', '=', '!=', '<', '>', '<=', '>=', '+', '-', '*', 'div', 'mod', '|'
 */

/**
 * @brief Supported types of (partial) XPath results.
 */
enum lyxp_set_type {
    LYXP_SET_NODE_SET = 0,
{'fraction_non_alphanumeric': 0.12801810865191146, 'fraction_numerical': 0.011443661971830986, 'mean_word_length': 2.4621245102307356, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 27, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6759197', 'n_tokens_mistral': 5340, 'n_tokens_neox': 4988, 'n_words': 1403}