From b9bb9e5187b1530df9a0f22e734f4e2c546e439e Mon Sep 17 00:00:00 2001 From: Olivier Matz Date: Tue, 10 Mar 2020 16:48:44 +0100 Subject: [PATCH] api documentation for ec_parse --- include/ecoli_parse.h | 194 ++++++++++++++++++++++++++++------------ src/ecoli_complete.c | 4 +- src/ecoli_node_cond.c | 4 +- src/ecoli_node_many.c | 2 +- src/ecoli_node_re_lex.c | 2 +- src/ecoli_node_sh_lex.c | 2 +- src/ecoli_node_subset.c | 2 +- src/ecoli_parse.c | 46 +++++----- todo.txt | 5 ++ 9 files changed, 175 insertions(+), 86 deletions(-) diff --git a/include/ecoli_parse.h b/include/ecoli_parse.h index ec41895..44ace53 100644 --- a/include/ecoli_parse.h +++ b/include/ecoli_parse.h @@ -141,149 +141,233 @@ struct ec_pnode *ec_parse_strvec(const struct ec_node *node, const struct ec_strvec *strvec); /** + * Return value of ec_parse_child() when input does not match grammar. + */ +#define EC_PARSE_NOMATCH INT_MAX + +/** + * Parse a string vector using a grammar tree, from a parent node. * + * This function is usually called from an intermediate node (like + * ec_node_seq, ec_node_or, ...) to backfill the parsing tree, which is + * built piece by piece while browsing the grammar tree. * + * ec_parse_child() creates a new child in this parsing tree, and calls + * the parse() method for the child node, with pstate pointing to this + * new child. If it does not match, the child is removed in the state, + * else it is kept, with its possible descendants. * + * @param node + * The grammar node. + * @param str + * The input string vector. + * @return + * On success: the number of matched elements in the input string + * vector (which can be 0), or EC_PARSE_NOMATCH (which is a positive + * value) if the input does not match the grammar. On error, -1 is + * returned, and errno is set. */ -#define EC_PARSE_NOMATCH INT_MAX +int ec_parse_child(const struct ec_node *node, struct ec_pnode *pstate, + const struct ec_strvec *strvec); -/* internal: used by nodes +/** + * Link a parsing node to a parsing tree. * - * pstate is the current parse tree, which is built piece by piece while - * parsing the node tree: ec_parse_child() creates a new child in - * this state parse tree, and calls the parse() method for the child - * node, with pstate pointing to this new child. If it does not match, - * the child is removed in the state, else it is kept, with its - * possible descendants. + * Add a child to a node in a parsing tree, at the end of the children + * list. * - * return: - * the number of matched strings in strvec on success - * EC_PARSE_NOMATCH (positive) if it does not match - * -1 on error, and errno is set + * @param pnode + * The node of the parsing tree where the child is added. + * @param child + * The node (or subtree) to add in the children list. */ -int ec_parse_child(const struct ec_node *node, - struct ec_pnode *pstate, - const struct ec_strvec *strvec); +void ec_pnode_link_child(struct ec_pnode *pnode, struct ec_pnode *child); /** + * Remove a child node from parsing tree. * + * Remove a child node (and its children) from the children list its + * parent node in the parsing tree. The child node is not freed. * - * + * @param child + * The node (or subtree) to remove. */ -void ec_pnode_link_child(struct ec_pnode *pnode, - struct ec_pnode *child); +void ec_pnode_unlink_child(struct ec_pnode *child); + /** + * Get the root of the parsing tree. * + * Get the root of the parsing tree, keeping the const statement + * if the argument has it. * - * + * @param pnode + * A node in the parsing tree. + * @return + * The root of the parsing tree. */ -void ec_pnode_unlink_child(struct ec_pnode *pnode, - struct ec_pnode *child); - -/* keep the const */ -#define ec_pnode_get_root(parse) ({ \ +#define EC_PNODE_GET_ROOT(parse) ({ \ const struct ec_pnode *p_ = parse; /* check type */ \ struct ec_pnode *pnode_ = (struct ec_pnode *)parse; \ typeof(parse) res_; \ (void)p_; \ - res_ = __ec_pnode_get_root(pnode_); \ + res_ = ec_pnode_get_root(pnode_); \ res_; \ }) /** + * Get the root of the parsing tree. * + * You may also use EC_PNODE_GET_ROOT() instead, that keeps the + * const statement. * - * + * @param pnode + * A node in the parsing tree. + * @return + * The root of the parsing tree. */ -struct ec_pnode *__ec_pnode_get_root(struct ec_pnode *pnode); +struct ec_pnode *ec_pnode_get_root(struct ec_pnode *pnode); /** + * Get the parent node in the parsing tree. * - * - * + * @param pnode + * A node in the parsing tree. + * @return + * The parent node, or NULL if it is the root. */ struct ec_pnode *ec_pnode_get_parent(const struct ec_pnode *pnode); /** - * Get the first child of a tree. + * Get the first child of a node in the parsing tree. * + * @param pnode + * A node in the parsing tree. + * @return + * The first child node, or NULL if it has no child. */ struct ec_pnode *ec_pnode_get_first_child(const struct ec_pnode *pnode); /** + * Get the last child of a node in the parsing tree. * - * - * + * @param pnode + * A node in the parsing tree. + * @return + * The last child node, or NULL if it has no child. */ struct ec_pnode *ec_pnode_get_last_child(const struct ec_pnode *pnode); /** + * Get the next sibling node. * + * If pnode is the root of the parsing tree, return NULL. Else return + * the next sibling node. * - * + * @param pnode + * A node in the parsing tree.. + * @return + * The next sibling, or NULL if there is no sibling. */ struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode); /** + * Iterate the children of a node. * - * - * + * @param child + * The item that will be set at each iteration. + * @param pnode + * The parent node in the parsing tree. */ -#define EC_PNODE_FOREACH_CHILD(child, parse) \ - for (child = ec_pnode_get_first_child(parse); \ +#define EC_PNODE_FOREACH_CHILD(child, pnode) \ + for (child = ec_pnode_get_first_child(pnode); \ child != NULL; \ child = ec_pnode_next(child)) \ /** + * Get the grammar node corresponding to the parsing node. * - * - * - */ -bool ec_pnode_has_child(const struct ec_pnode *pnode); - -/** - * - * - * + * @param pnode + * A node in the parsing tree. + * @return + * The corresponding grammar node, that issued the parse. */ const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode); /** + * Unlink and free the last child. * + * Shortcut to unlink and free the last child of a node. It is a quite + * common operation in intermediate nodes (like ec_node_seq, + * ec_node_many, ...) to remove a subtree that was temporarily added + * when during the completion process. * - * + * @param pnode + * A node in the parsing tree which has at least one child. */ void ec_pnode_del_last_child(struct ec_pnode *pnode); /** + * Get attributes associated to a node in a parsing tree. * + * Attributes are key/values that are stored in a dictionary + * and attached to a node in the parsing tree. An attribute can be + * added to a node by the parsing or completion method of an ec_node. * - * + * @param pnode + * A node in the parsing tree. + * @return + * The dictionary containing the attributes. */ struct ec_dict *ec_pnode_get_attrs(struct ec_pnode *pnode); /** + * Dump a parsing tree. * - * - * + * @param out + * The stream where the dump is done. + * @param pnode + * The parsing tree to dump. */ void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode); /** + * Find a node from its identifier. * + * Find the first node in the parsing tree which has the given + * node identifier. The search is a depth-first search. * - * + * @param root + * The node of the parsing tree where the search starts. + * @param id + * The node identifier string to match. + * @return + * The first node matching the identifier, or NULL if not found. */ -struct ec_pnode *ec_pnode_find(struct ec_pnode *pnode, - const char *id); +struct ec_pnode *ec_pnode_find(struct ec_pnode *root, const char *id); /** + * Find the next node matching an identifier. * + * After a succesful call to ec_pnode_find() or ec_pnode_find_next(), it + * is possible to get the next node that has the specified id. There are + * 2 options: + * - continue the depth-first search where it was interrupted. + * - skip the children of the current node, and continue the depth-first + * search. * - * + * @param pnode + * The root of the search, as passed to ec_pnode_find(). + * @param prev + * The node returned by the previous search. + * @param id + * The node identifier string to match. + * @param iter_children + * True to iterate the children of "prev", false to skip them. + * @return + * The next node matching the identifier, or NULL if not found. */ struct ec_pnode *ec_pnode_find_next(struct ec_pnode *root, - struct ec_pnode *start, + struct ec_pnode *prev, const char *id, bool iter_children); /** diff --git a/src/ecoli_complete.c b/src/ecoli_complete.c index 537de57..0d9fd95 100644 --- a/src/ecoli_complete.c +++ b/src/ecoli_complete.c @@ -130,8 +130,8 @@ ec_complete_child(const struct ec_node *node, /* restore parent parse state */ if (cur_pstate != NULL) { - ec_pnode_unlink_child(cur_pstate, child_pstate); - assert(!ec_pnode_has_child(child_pstate)); + ec_pnode_unlink_child(child_pstate); + assert(ec_pnode_get_first_child(child_pstate) == NULL); } ec_pnode_free(child_pstate); comp->cur_pstate = cur_pstate; diff --git a/src/ecoli_node_cond.c b/src/ecoli_node_cond.c index 8938830..649ecbb 100644 --- a/src/ecoli_node_cond.c +++ b/src/ecoli_node_cond.c @@ -224,7 +224,7 @@ eval_root(const struct ec_pnode *pstate, struct cond_result **in, size_t in_len) if (out->htable == NULL) goto fail; - root = ec_pnode_get_root(pstate); + root = EC_PNODE_GET_ROOT(pstate); if (ec_htable_set(out->htable, &root, sizeof(root), NULL, NULL) < 0) goto fail; @@ -717,7 +717,7 @@ ec_node_cond_parse(const struct ec_node *node, struct ec_pnode *pstate, if (valid == 0) { child = ec_pnode_get_last_child(pstate); - ec_pnode_unlink_child(pstate, child); + ec_pnode_unlink_child(child); ec_pnode_free(child); return EC_PARSE_NOMATCH; } diff --git a/src/ecoli_node_many.c b/src/ecoli_node_many.c index 54c100c..5bfb92c 100644 --- a/src/ecoli_node_many.c +++ b/src/ecoli_node_many.c @@ -58,7 +58,7 @@ static int ec_node_many_parse(const struct ec_node *node, /* it matches an empty strvec, no need to continue */ if (ret == 0) { child_parse = ec_pnode_get_last_child(pstate); - ec_pnode_unlink_child(pstate, child_parse); + ec_pnode_unlink_child(child_parse); ec_pnode_free(child_parse); break; } diff --git a/src/ecoli_node_re_lex.c b/src/ecoli_node_re_lex.c index 726c6cf..8590fc6 100644 --- a/src/ecoli_node_re_lex.c +++ b/src/ecoli_node_re_lex.c @@ -147,7 +147,7 @@ ec_node_re_lex_parse(const struct ec_node *node, ret = 1; } else if (ret != EC_PARSE_NOMATCH) { child_parse = ec_pnode_get_last_child(pstate); - ec_pnode_unlink_child(pstate, child_parse); + ec_pnode_unlink_child(child_parse); ec_pnode_free(child_parse); ret = EC_PARSE_NOMATCH; } diff --git a/src/ecoli_node_sh_lex.c b/src/ecoli_node_sh_lex.c index 7dd0358..3f5abbc 100644 --- a/src/ecoli_node_sh_lex.c +++ b/src/ecoli_node_sh_lex.c @@ -242,7 +242,7 @@ ec_node_sh_lex_parse(const struct ec_node *node, ret = 1; } else if (ret != EC_PARSE_NOMATCH) { child_parse = ec_pnode_get_last_child(pstate); - ec_pnode_unlink_child(pstate, child_parse); + ec_pnode_unlink_child(child_parse); ec_pnode_free(child_parse); ret = EC_PARSE_NOMATCH; } diff --git a/src/ecoli_node_subset.c b/src/ecoli_node_subset.c index 7e65170..c62e514 100644 --- a/src/ecoli_node_subset.c +++ b/src/ecoli_node_subset.c @@ -98,7 +98,7 @@ __ec_node_subset_parse(struct parse_result *out, struct ec_node **table, /* replace the previous best result */ ec_pnode_free(best_parse); best_parse = ec_pnode_get_last_child(pstate); - ec_pnode_unlink_child(pstate, best_parse); + ec_pnode_unlink_child(best_parse); best_result.parse_len = result.parse_len + 1; best_result.len = len + result.len; diff --git a/src/ecoli_parse.c b/src/ecoli_parse.c index c47c7b4..7b36ed5 100644 --- a/src/ecoli_parse.c +++ b/src/ecoli_parse.c @@ -64,7 +64,7 @@ static int __ec_parse_child(const struct ec_node *node, if (ret == EC_PARSE_NOMATCH) { if (!is_root) { - ec_pnode_unlink_child(pstate, child); + ec_pnode_unlink_child(child); ec_pnode_free(child); } return ret; @@ -80,7 +80,7 @@ static int __ec_parse_child(const struct ec_node *node, fail: if (!is_root) { - ec_pnode_unlink_child(pstate, child); + ec_pnode_unlink_child(child); ec_pnode_free(child); } return -1; @@ -211,7 +211,7 @@ struct ec_pnode *ec_pnode_dup(const struct ec_pnode *pnode) const struct ec_pnode *root; struct ec_pnode *dup_root, *dup = NULL; - root = ec_pnode_get_root(pnode); + root = EC_PNODE_GET_ROOT(pnode); dup_root = __ec_pnode_dup(root, pnode, &dup); if (dup_root == NULL) return NULL; @@ -271,6 +271,7 @@ static void __ec_pnode_dump(FILE *out, __ec_pnode_dump(out, child, indent + 1); } +// XXX dump in other formats? yaml? json? void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode) { fprintf(out, "------------------- parse dump:\n"); @@ -299,11 +300,14 @@ void ec_pnode_link_child(struct ec_pnode *pnode, child->parent = pnode; } -void ec_pnode_unlink_child(struct ec_pnode *pnode, - struct ec_pnode *child) +void ec_pnode_unlink_child(struct ec_pnode *child) { - TAILQ_REMOVE(&pnode->children, child, next); - child->parent = NULL; + struct ec_pnode *parent = child->parent; + + if (parent != NULL) { + TAILQ_REMOVE(&parent->children, child, next); + child->parent = NULL; + } } struct ec_pnode * @@ -323,11 +327,6 @@ struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode) return TAILQ_NEXT(pnode, next); } -bool ec_pnode_has_child(const struct ec_pnode *pnode) -{ - return !TAILQ_EMPTY(&pnode->children); -} - const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode) { if (pnode == NULL) @@ -341,11 +340,13 @@ void ec_pnode_del_last_child(struct ec_pnode *pnode) struct ec_pnode *child; child = ec_pnode_get_last_child(pnode); - ec_pnode_unlink_child(pnode, child); - ec_pnode_free(child); + if (child != NULL) { + ec_pnode_unlink_child(child); + ec_pnode_free(child); + } } -struct ec_pnode *__ec_pnode_get_root(struct ec_pnode *pnode) +struct ec_pnode *ec_pnode_get_root(struct ec_pnode *pnode) { if (pnode == NULL) return NULL; @@ -386,19 +387,19 @@ struct ec_pnode *__ec_pnode_iter_next(const struct ec_pnode *root, } struct ec_pnode * -ec_pnode_find_next(struct ec_pnode *root, struct ec_pnode *start, +ec_pnode_find_next(struct ec_pnode *root, struct ec_pnode *prev, const char *id, bool iter_children) { struct ec_pnode *iter; if (root == NULL) return NULL; - if (start == NULL) - start = root; + if (prev == NULL) + prev = root; else - start = EC_PNODE_ITER_NEXT(root, start, iter_children); + prev = EC_PNODE_ITER_NEXT(root, prev, iter_children); - for (iter = start; iter != NULL; + for (iter = prev; iter != NULL; iter = EC_PNODE_ITER_NEXT(root, iter, 1)) { if (iter->node != NULL && !strcmp(ec_node_id(iter->node), id)) @@ -408,10 +409,9 @@ ec_pnode_find_next(struct ec_pnode *root, struct ec_pnode *start, return NULL; } -struct ec_pnode *ec_pnode_find(struct ec_pnode *pnode, - const char *id) +struct ec_pnode *ec_pnode_find(struct ec_pnode *root, const char *id) { - return ec_pnode_find_next(pnode, NULL, id, 1); + return ec_pnode_find_next(root, NULL, id, 1); } struct ec_dict * diff --git a/todo.txt b/todo.txt index 16521f0..739e350 100644 --- a/todo.txt +++ b/todo.txt @@ -45,6 +45,8 @@ X remove weakref? - sh_lex to provide offsets in attributes - accessors for all structs - private vs user attributes? +- limit max loop, +- limit max completions dependencies ============ @@ -85,6 +87,7 @@ examples - mini shell: cd, ls, cat, stat - mini network console based on ip - dialog-like for use in shell +- pcap https://github.com/the-tcpdump-group/libpcap/blob/master/grammar.y doc === @@ -516,3 +519,5 @@ alloc ec_strvec() free ec_strvec_free() action ec_strvec_*() +--- + -- 2.20.1