1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
6 * @defgroup parse Parse
9 * @brief Create parse tree from string input and grammar graph
13 * The parse operation is to check if an input (a string or vector of
14 * strings) matches the node tree. On success, the result is stored in a
15 * tree that describes which part of the input matches which node.
17 * The parsing tree is sometimes referenced by another node than the
18 * root node. Use ec_pnode_get_root() to get the root node in that case.
25 #include <sys/queue.h>
26 #include <sys/types.h>
35 * Create an empty parsing tree.
37 * This function is used internally when parsing an input using
43 * The empty parse tree.
45 struct ec_pnode *ec_pnode(const struct ec_node *node);
48 * Free a parsing tree.
51 * The root of the parsing tree to be freed. It must not have
54 void ec_pnode_free(struct ec_pnode *pnode);
57 * Remove and free all the children of a parsing tree node.
60 * Node whose children will be freed.
62 void ec_pnode_free_children(struct ec_pnode *pnode);
65 * Duplicate a parsing tree.
68 * A node inside a parsing tree.
70 * A pointer to the copy of the input node, at the same place in the
71 * copy of the parsing tree. Return NULL on error (errno is set).
73 struct ec_pnode *ec_pnode_dup(const struct ec_pnode *pnode);
76 * Get the string vector associated to a parsing node.
78 * When an input is parsed successfully (i.e. the input string vector
79 * matches the grammar tree), the matching string vector is copied
80 * inside the associated parsing node.
82 * For instance, parsing the input ["foo", "bar"] on a grammar which is
83 * a sequence of strings, the attached string vector will be ["foo",
84 * "bar"] on the root pnode, ["foo"] on the first leaf, and ["bar"] on
87 * If the parsing tree does not match (see ec_pnode_matches()), it
88 * the associated string vector is NULL.
91 * The parsing node. If NULL, the function returns NULL.
93 * The string vector associated to the parsing node, or NULL
94 * if the node is not yet parsed (this happens when building the
95 * parsing tree), or if the parsing tree does not match the
98 const struct ec_strvec *ec_pnode_get_strvec(const struct ec_pnode *pnode);
101 * Parse a string using a grammar tree.
103 * This is equivalent to calling ec_parse_strvec() on the same
104 * node, with a string vector containing only the argument string str.
111 * A parsing tree, or NULL on error (errno is set).
113 struct ec_pnode *ec_parse(const struct ec_node *node, const char *str);
116 * Parse a string vector using a grammar tree.
118 * Generate a parsing tree by parsing the input string vector using the
119 * given grammar tree.
121 * The parsing tree is composed of struct ec_pnode, and each of them is
122 * associated to a struct ec_node (the grammar node), to the string vector
123 * that matched the subtree, and to optional attributes.
125 * When the input matches the grammar tree, the string vector associated
126 * to the root node of the returned parsing tree is the same than the
127 * strvec argument. Calling ec_pnode_matches() on this tree returns true.
129 * If the input does not match the grammar tree, the returned parsing
130 * tree only contains one root node, with no associated string vector.
131 * Calling ec_pnode_matches() on this tree returns false.
136 * The input string vector.
138 * A parsing tree, or NULL on error (errno is set).
140 struct ec_pnode *ec_parse_strvec(const struct ec_node *node,
141 const struct ec_strvec *strvec);
148 #define EC_PARSE_NOMATCH INT_MAX
150 /* internal: used by nodes
152 * pstate is the current parse tree, which is built piece by piece while
153 * parsing the node tree: ec_parse_child() creates a new child in
154 * this state parse tree, and calls the parse() method for the child
155 * node, with pstate pointing to this new child. If it does not match,
156 * the child is removed in the state, else it is kept, with its
157 * possible descendants.
160 * the number of matched strings in strvec on success
161 * EC_PARSE_NOMATCH (positive) if it does not match
162 * -1 on error, and errno is set
164 int ec_parse_child(const struct ec_node *node,
165 struct ec_pnode *pstate,
166 const struct ec_strvec *strvec);
173 void ec_pnode_link_child(struct ec_pnode *pnode,
174 struct ec_pnode *child);
180 void ec_pnode_unlink_child(struct ec_pnode *pnode,
181 struct ec_pnode *child);
184 #define ec_pnode_get_root(parse) ({ \
185 const struct ec_pnode *p_ = parse; /* check type */ \
186 struct ec_pnode *pnode_ = (struct ec_pnode *)parse; \
187 typeof(parse) res_; \
189 res_ = __ec_pnode_get_root(pnode_); \
198 struct ec_pnode *__ec_pnode_get_root(struct ec_pnode *pnode);
205 struct ec_pnode *ec_pnode_get_parent(const struct ec_pnode *pnode);
208 * Get the first child of a tree.
211 struct ec_pnode *ec_pnode_get_first_child(const struct ec_pnode *pnode);
218 struct ec_pnode *ec_pnode_get_last_child(const struct ec_pnode *pnode);
225 struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode);
232 #define EC_PNODE_FOREACH_CHILD(child, parse) \
233 for (child = ec_pnode_get_first_child(parse); \
235 child = ec_pnode_next(child)) \
242 bool ec_pnode_has_child(const struct ec_pnode *pnode);
249 const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode);
256 void ec_pnode_del_last_child(struct ec_pnode *pnode);
263 struct ec_dict *ec_pnode_get_attrs(struct ec_pnode *pnode);
270 void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode);
277 struct ec_pnode *ec_pnode_find(struct ec_pnode *pnode,
285 struct ec_pnode *ec_pnode_find_next(struct ec_pnode *root,
286 struct ec_pnode *start,
287 const char *id, bool iter_children);
290 * Iterate among parse tree
293 * for (iter = pnode; iter != NULL; iter = EC_PNODE_ITER_NEXT(pnode, iter, 1))
295 struct ec_pnode *__ec_pnode_iter_next(const struct ec_pnode *root,
296 struct ec_pnode *pnode, bool iter_children);
298 /* keep the const if any */
299 #define EC_PNODE_ITER_NEXT(root, parse, iter_children) ({ \
300 const struct ec_pnode *p_ = parse; /* check type */ \
301 struct ec_pnode *pnode_ = (struct ec_pnode *)parse; \
302 typeof(parse) res_; \
304 res_ = __ec_pnode_iter_next(root, pnode_, iter_children); \
313 size_t ec_pnode_len(const struct ec_pnode *pnode);
320 size_t ec_pnode_matches(const struct ec_pnode *pnode);