src/xpath.h

/**
 * @file xpath.h
 * @author Michal Vasko <mvasko@cesnet.cz>
 * @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,
 * "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 ::= VariableReference | '(' 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 4
#define LYXP_SET_SIZE_MUL_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_VARREF,        /* VariableReference */
    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,
    LYXP_SET_SCNODE_SET,
    LYXP_SET_BOOLEAN,
    LYXP_SET_NUMBER,
    LYXP_SET_STRING
};

/**
 * @brief Item stored in an XPath set hash table.
 */
struct lyxp_set_hash_node {
    struct lyd_node *node;
    enum lyxp_node_type type;
} _PACKED;

/**
 * @brief XPath variable bindings.
 */
struct lyxp_var {
    char *name;     /**< Variable name. In the XPath expression, the name is preceded by a '$' character. */
    char *value;    /**< The value of a variable is an object, which can be of any of the type that are possible
                         for the value of an expression. */
};

/**
 * @brief XPath set - (partial) result.
 */
struct lyxp_set {
    enum lyxp_set_type type;             /**< Type of the object (value). */
    union {
        struct lyxp_set_node {
            struct lyd_node *node;       /**< Data node. */
            enum lyxp_node_type type;    /**< Type of the node. */
            uint32_t pos;                /**< Unique node position in the data. */
        } *nodes;                        /**< Set of data nodes. */
        struct lyxp_set_scnode {
            struct lysc_node *scnode;    /**< Compiled YANG node. */
            enum lyxp_node_type type;    /**< Type of the node. */

/* _START and _ATOM values should have grouped values */
#define LYXP_SET_SCNODE_START         -2 /**< scnode not traversed, currently (the only node) in context */
#define LYXP_SET_SCNODE_START_USED    -1 /**< scnode not traversed except for the eval start, not currently in the context */
#define LYXP_SET_SCNODE_ATOM_NODE      0 /**< scnode was traversed, but not currently in the context */
#define LYXP_SET_SCNODE_ATOM_VAL       1 /**< scnode was traversed and its value used, but not currently in the context */
#define LYXP_SET_SCNODE_ATOM_CTX       2 /**< scnode currently in context */
#define LYXP_SET_SCNODE_ATOM_NEW_CTX   3 /**< scnode in context and just added, so skip it for the current operation */
#define LYXP_SET_SCNODE_ATOM_PRED_CTX  4 /**< includes any higher value - scnode is not in context because we are in
                                              a predicate and this scnode was used/will be used later */
            int32_t in_ctx;             /**< Flag specifies the state of the node in context. Values are defined
                                             as LYXP_SET_SCNODE_* */
        } *scnodes;                     /**< Set of compiled YANG data nodes. */
        struct lyxp_set_meta {
            struct lyd_meta *meta;      /**< Node that provides information about metadata of a data element. */
            enum lyxp_node_type type;   /**< Type of the node. */
            uint32_t pos;               /**< Unique node position in the data. if node_type is LYXP_SET_NODE_META,
                                             it is the parent node position */
        } *meta;                        /**< Set of YANG metadata objects. */
        char *str;                      /**< String object. */
        long double num;                /**< Object of the floating-point number. */
        ly_bool bln;                    /**< Boolean object. */
    } val;                              /**< Evaluated object (value). */

    /* this is valid only for type LYXP_SET_NODE_SET and LYXP_SET_SCNODE_SET */
    uint32_t used;          /**< Number of nodes in the set. */
    uint32_t size;          /**< Allocated size for the set. */
    struct hash_table *ht;  /**< Hash table for quick determination of whether a node is in the set. */

    /* XPath context information, this is valid only for type LYXP_SET_NODE_SET */
    uint32_t ctx_pos;       /**< Position of the current examined node in the set. */
    uint32_t ctx_size;      /**< Position of the last node at the time the node was examined. */

    /* general context */
    struct ly_ctx *ctx;                     /**< General context for logging. */
    union {
        const struct lyd_node *cur_node;    /**< Current (original context) node. */
        const struct lysc_node *cur_scnode; /**< Current (original context) compiled node. */
    };
    enum lyxp_node_type root_type;          /**< Type of root node. */
    const struct lysc_node *context_op;     /**< Schema of the current node. */
    const struct lyd_node *tree;            /**< Data tree on which to perform the evaluation. */
    const struct lys_module *cur_mod;       /**< Current module for the expression (where it was "instantiated"). */
    LY_VALUE_FORMAT format;                 /**< Format of the XPath expression. */
    void *prefix_data;                      /**< Format-specific prefix data (see ::ly_resolve_prefix). */
    const struct lyxp_var *vars;            /**< XPath variables. [Sized array](@ref sizedarrays).
                                                 Set of variable bindings. */
};

/**
 * @brief Print an XPath token \p tok type.
 *
 * @param[in] tok Token to print.
 * @return Token type string.
 */
const char *lyxp_print_token(enum lyxp_token tok);

/**
 * @brief Evaluate an XPath expression on data. Be careful when using this function, the result can often
 * be confusing without thorough understanding of XPath evaluation rules defined in RFC 7950.
 *
 * @param[in] ctx libyang context to use.
 * @param[in] exp Parsed XPath expression to be evaluated.
 * @param[in] cur_mod Current module for the expression (where it was "instantiated").
 * @param[in] format Format of the XPath expression (more specifically, of any used prefixes).
 * @param[in] prefix_data Format-specific prefix data (see ::ly_resolve_prefix).
 * @param[in] ctx_node Current (context) data node, NULL in case of the root node.
 * @param[in] tree Data tree on which to perform the evaluation, it must include all the available data (including
 * the tree of @p ctx_node). Can be any node of the tree, it is adjusted.
 * @param[in] vars [Sized array](@ref sizedarrays) of XPath variables.
 * @param[out] set Result set.
 * @param[in] options Whether to apply some evaluation restrictions.
 * @return LY_EVALID for invalid argument types/count,
 * @return LY_EINCOMPLETE for unresolved when,
 * @return LY_EINVAL, LY_EMEM, LY_EINT for other errors.
 */
LY_ERR lyxp_eval(const struct ly_ctx *ctx, const struct lyxp_expr *exp, const struct lys_module *cur_mod,
        LY_VALUE_FORMAT format, void *prefix_data, const struct lyd_node *ctx_node, const struct lyd_node *tree,
        const struct lyxp_var *vars, struct lyxp_set *set, uint32_t options);

/**
 * @brief Get all the partial XPath nodes (atoms) that are required for @p exp to be evaluated.
 *
 * @param[in] ctx libyang context to use.
 * @param[in] exp Parsed XPath expression to be evaluated.
 * @param[in] cur_mod Current module for the expression (where it was "instantiated").
 * @param[in] format Format of the XPath expression (more specifically, of any used prefixes).
 * @param[in] prefix_data Format-specific prefix data (see ::ly_resolve_prefix).
 * @param[in] ctx_scnode Current (context) schema node, NULL in case of the root node.
 * @param[out] set Result set.
 * @param[in] options Whether to apply some evaluation restrictions, one flag must always be used.
 * @return LY_ERR (same as ::lyxp_eval()).
 */
LY_ERR lyxp_atomize(const struct ly_ctx *ctx, const struct lyxp_expr *exp, const struct lys_module *cur_mod,
        LY_VALUE_FORMAT format, void *prefix_data, const struct lysc_node *ctx_scnode, struct lyxp_set *set,
        uint32_t options);

/** used only internally, maps with @ref findxpathoptions */
#define LYXP_IGNORE_WHEN     0x01   /**< Ignore unevaluated when in data nodes and do not return ::LY_EINCOMPLETE. */
#define LYXP_SCHEMA          0x02   /**< Apply data node access restrictions defined for 'when' and 'must' evaluation. */
#define LYXP_SCNODE          0x04   /**< No special tree access modifiers. */
#define LYXP_SCNODE_SCHEMA   LYS_FIND_XP_SCHEMA /**< Apply node access restrictions defined for 'when' and 'must' evaluation. */
#define LYXP_SCNODE_OUTPUT   LYS_FIND_XP_OUTPUT /**< Search RPC/action output nodes instead of input ones. */
#define LYXP_SCNODE_ALL      0x1C   /**< mask for all the LYXP_* values */
#define LYXP_SKIP_EXPR       0x20   /**< The rest of the expression will not be evaluated (lazy evaluation) */
#define LYXP_SCNODE_ERROR    LYS_FIND_NO_MATCH_ERROR    /**< Return error if a path segment matches no nodes, otherwise only
                                                             warning is printed. */
#define LYXP_ACCESS_TREE_ALL 0x80   /**< Explicit accessible tree of all the nodes. */
#define LYXP_ACCESS_TREE_CONFIG 0x0100  /**< Explicit accessible tree of only configuration data. */

/**
 * @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.
 * @return LY_ERR
 */
LY_ERR lyxp_set_cast(struct lyxp_set *set, enum lyxp_set_type target);

/**
 * @brief Free dynamic content of a set.
 *
 * @param[in] set Set to modify.
 */
void lyxp_set_free_content(struct lyxp_set *set);

/**
 * @brief Insert schema node into set.
 *
 * @param[in] set Set to insert into.
 * @param[in] node Node to insert.
 * @param[in] node_type Node type of @p node.
 * @param[out] index_p Optional pointer to store index if the inserted @p node.
 * @return LY_SUCCESS on success.
 * @return LY_EMEM on memory allocation failure.
 */
LY_ERR lyxp_set_scnode_insert_node(struct lyxp_set *set, const struct lysc_node *node, enum lyxp_node_type node_type,
        uint32_t *index_p);

/**
 * @brief Check for duplicates in a schema node set.
 *
 * @param[in] set Set to check.
 * @param[in] node Node to look for in @p set.
 * @param[in] node_type Type of @p node.
 * @param[in] skip_idx Index from @p set to skip.
 * @param[out] index_p Optional pointer to store index if the node is found.
 * @return Boolean value whether the @p node found or not.
 */
ly_bool lyxp_set_scnode_contains(struct lyxp_set *set, const struct lysc_node *node, enum lyxp_node_type node_type,
        int skip_idx, uint32_t *index_p);

/**
 * @brief Merge 2 schema node sets.
 *
 * @param[in] set1 Set to merge into.
 * @param[in] set2 Set to merge. Its content is freed.
 */
void lyxp_set_scnode_merge(struct lyxp_set *set1, struct lyxp_set *set2);

/**
 * @brief Parse an XPath expression into a structure of tokens.
 *        Logs directly.
 *
 * https://www.w3.org/TR/1999/REC-xpath-19991116/#exprlex
 *
 * @param[in] ctx Context for errors.
 * @param[in] expr_str XPath expression to parse. It is duplicated.
 * @param[in] expr_len Length of @p expr, can be 0 if @p expr is 0-terminated.
 * @param[in] reparse Whether to re-parse the expression to finalize full XPath parsing and fill
 * information about expressions and their operators (fill repeat).
 * @param[out] expr_p Pointer to return the filled expression structure.
 * @return LY_SUCCESS in case of success.
 * @return LY_EMEM in case of memory allocation failure.
 * @return LY_EVALID in case of invalid XPath expression in @p expr_str.
 */
LY_ERR lyxp_expr_parse(const struct ly_ctx *ctx, const char *expr_str, size_t expr_len, ly_bool reparse,
        struct lyxp_expr **expr_p);

/**
 * @brief Duplicate parsed XPath expression.
 *
 * @param[in] ctx Context with a dictionary.
 * @param[in] exp Parsed expression.
 * @param[out] dup Duplicated structure.
 * @return LY_ERR value.
 */
LY_ERR lyxp_expr_dup(const struct ly_ctx *ctx, const struct lyxp_expr *exp, struct lyxp_expr **dup);

/**
 * @brief Look at the next token and check its kind.
 *
 * @param[in] ctx Context for logging, not logged if NULL.
 * @param[in] exp Expression to use.
 * @param[in] tok_idx Token index in the expression \p exp.
 * @param[in] want_tok Expected token.
 * @return LY_EINCOMPLETE on EOF,
 * @return LY_ENOT on non-matching token,
 * @return LY_SUCCESS on success.
 */
LY_ERR lyxp_check_token(const struct ly_ctx *ctx, const struct lyxp_expr *exp, uint16_t tok_idx, enum lyxp_token want_tok);

/**
 * @brief Look at the next token and skip it if it matches the expected one.
 *
 * @param[in] ctx Context for logging, not logged if NULL.
 * @param[in] exp Expression to use.
 * @param[in,out] tok_idx Token index in the expression \p exp, is updated.
 * @param[in] want_tok Expected token.
 * @return LY_EINCOMPLETE on EOF,
 * @return LY_ENOT on non-matching token,
 * @return LY_SUCCESS on success.
 */
LY_ERR lyxp_next_token(const struct ly_ctx *ctx, const struct lyxp_expr *exp, uint16_t *tok_idx, enum lyxp_token want_tok);

/**
 * @brief Look at the next token and skip it if it matches either of the 2 expected ones.
 *
 * @param[in] ctx Context for logging, not logged if NULL.
 * @param[in] exp Expression to use.
 * @param[in,out] tok_idx Token index in the expression \p exp, is updated.
 * @param[in] want_tok1 Expected token 1.
 * @param[in] want_tok2 Expected token 2.
 * @return LY_EINCOMPLETE on EOF,
 * @return LY_ENOT on non-matching token,
 * @return LY_SUCCESS on success.
 */
LY_ERR lyxp_next_token2(const struct ly_ctx *ctx, const struct lyxp_expr *exp, uint16_t *tok_idx,
        enum lyxp_token want_tok1, enum lyxp_token want_tok2);

/**
 * @brief Find variable named @name in @p vars.
 *
 * @param[in] vars [Sized array](@ref sizedarrays) of XPath variables.
 * @param[in] name Name of the variable being searched.
 * @param[in] name_len Name length can be set to 0 if @p name is terminated by null byte.
 * @param[out] var Variable that was found. The parameter is optional.
 * @return LY_SUCCESS if the variable was found, otherwise LY_ENOTFOUND.
 */
LY_ERR lyxp_vars_find(struct lyxp_var *vars, const char *name, size_t name_len, struct lyxp_var **var);

/**
 * @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(const struct ly_ctx *ctx, struct lyxp_expr *expr);

#endif /* LY_XPATH_H */