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);
144 * Return value of ec_parse_child() when input does not match grammar.
146 #define EC_PARSE_NOMATCH INT_MAX
149 * Parse a string vector using a grammar tree, from a parent node.
151 * This function is usually called from an intermediate node (like
152 * ec_node_seq, ec_node_or, ...) to backfill the parsing tree, which is
153 * built piece by piece while browsing the grammar tree.
155 * ec_parse_child() creates a new child in this parsing tree, and calls
156 * the parse() method for the child node, with pstate pointing to this
157 * new child. If it does not match, the child is removed in the state,
158 * else it is kept, with its possible descendants.
163 * The input string vector.
165 * On success: the number of matched elements in the input string
166 * vector (which can be 0), or EC_PARSE_NOMATCH (which is a positive
167 * value) if the input does not match the grammar. On error, -1 is
168 * returned, and errno is set.
170 int ec_parse_child(const struct ec_node *node, struct ec_pnode *pstate,
171 const struct ec_strvec *strvec);
174 * Link a parsing node to a parsing tree.
176 * Add a child to a node in a parsing tree, at the end of the children
180 * The node of the parsing tree where the child is added.
182 * The node (or subtree) to add in the children list.
184 void ec_pnode_link_child(struct ec_pnode *pnode, struct ec_pnode *child);
187 * Remove a child node from parsing tree.
189 * Remove a child node (and its children) from the children list its
190 * parent node in the parsing tree. The child node is not freed.
193 * The node (or subtree) to remove.
195 void ec_pnode_unlink_child(struct ec_pnode *child);
198 * Get the root of the parsing tree.
200 * Get the root of the parsing tree, keeping the const statement
201 * if the argument has it.
204 * A node in the parsing tree.
206 * The root of the parsing tree.
208 #define EC_PNODE_GET_ROOT(parse) ({ \
209 const struct ec_pnode *p_ = parse; /* check type */ \
210 struct ec_pnode *pnode_ = (struct ec_pnode *)parse; \
211 typeof(parse) res_; \
213 res_ = ec_pnode_get_root(pnode_); \
218 * Get the root of the parsing tree.
220 * You may also use EC_PNODE_GET_ROOT() instead, that keeps the
224 * A node in the parsing tree.
226 * The root of the parsing tree.
228 struct ec_pnode *ec_pnode_get_root(struct ec_pnode *pnode);
231 * Get the parent node in the parsing tree.
234 * A node in the parsing tree.
236 * The parent node, or NULL if it is the root.
238 struct ec_pnode *ec_pnode_get_parent(const struct ec_pnode *pnode);
241 * Get the first child of a node in the parsing tree.
244 * A node in the parsing tree.
246 * The first child node, or NULL if it has no child.
248 struct ec_pnode *ec_pnode_get_first_child(const struct ec_pnode *pnode);
251 * Get the last child of a node in the parsing tree.
254 * A node in the parsing tree.
256 * The last child node, or NULL if it has no child.
258 struct ec_pnode *ec_pnode_get_last_child(const struct ec_pnode *pnode);
261 * Get the next sibling node.
263 * If pnode is the root of the parsing tree, return NULL. Else return
264 * the next sibling node.
267 * A node in the parsing tree..
269 * The next sibling, or NULL if there is no sibling.
271 struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode);
274 * Iterate the children of a node.
277 * The item that will be set at each iteration.
279 * The parent node in the parsing tree.
281 #define EC_PNODE_FOREACH_CHILD(child, pnode) \
282 for (child = ec_pnode_get_first_child(pnode); \
284 child = ec_pnode_next(child)) \
287 * Get the grammar node corresponding to the parsing node.
290 * A node in the parsing tree.
292 * The corresponding grammar node, that issued the parse.
294 const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode);
297 * Unlink and free the last child.
299 * Shortcut to unlink and free the last child of a node. It is a quite
300 * common operation in intermediate nodes (like ec_node_seq,
301 * ec_node_many, ...) to remove a subtree that was temporarily added
302 * when during the completion process.
305 * A node in the parsing tree which has at least one child.
307 void ec_pnode_del_last_child(struct ec_pnode *pnode);
310 * Get attributes associated to a node in a parsing tree.
312 * Attributes are key/values that are stored in a dictionary
313 * and attached to a node in the parsing tree. An attribute can be
314 * added to a node by the parsing or completion method of an ec_node.
317 * A node in the parsing tree.
319 * The dictionary containing the attributes.
321 struct ec_dict *ec_pnode_get_attrs(struct ec_pnode *pnode);
324 * Dump a parsing tree.
327 * The stream where the dump is done.
329 * The parsing tree to dump.
331 void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode);
334 * Find a node from its identifier.
336 * Find the first node in the parsing tree which has the given
337 * node identifier. The search is a depth-first search.
340 * The node of the parsing tree where the search starts.
342 * The node identifier string to match.
344 * The first node matching the identifier, or NULL if not found.
346 struct ec_pnode *ec_pnode_find(struct ec_pnode *root, const char *id);
349 * Find the next node matching an identifier.
351 * After a succesful call to ec_pnode_find() or ec_pnode_find_next(), it
352 * is possible to get the next node that has the specified id. There are
354 * - continue the depth-first search where it was interrupted.
355 * - skip the children of the current node, and continue the depth-first
359 * The root of the search, as passed to ec_pnode_find().
361 * The node returned by the previous search.
363 * The node identifier string to match.
364 * @param iter_children
365 * True to iterate the children of "prev", false to skip them.
367 * The next node matching the identifier, or NULL if not found.
369 struct ec_pnode *ec_pnode_find_next(struct ec_pnode *root,
370 struct ec_pnode *prev,
371 const char *id, bool iter_children);
374 * Iterate among parse tree
377 * for (iter = pnode; iter != NULL; iter = EC_PNODE_ITER_NEXT(pnode, iter, 1))
379 struct ec_pnode *__ec_pnode_iter_next(const struct ec_pnode *root,
380 struct ec_pnode *pnode, bool iter_children);
382 /* keep the const if any */
383 #define EC_PNODE_ITER_NEXT(root, parse, iter_children) ({ \
384 const struct ec_pnode *p_ = parse; /* check type */ \
385 struct ec_pnode *pnode_ = (struct ec_pnode *)parse; \
386 typeof(parse) res_; \
388 res_ = __ec_pnode_iter_next(root, pnode_, iter_children); \
397 size_t ec_pnode_len(const struct ec_pnode *pnode);
404 size_t ec_pnode_matches(const struct ec_pnode *pnode);