include/ecoli_parse.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 /**
   6  * @defgroup parse Parse
   7  * @{
   8  *
   9  * @brief Create parse tree from string input and grammar graph
  10  *
  11  * Node parse API.
  12  *
  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.
  16  *
  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.
  19  * @}
  20  */
  21
  22 #ifndef ECOLI_PNODE_
  23 #define ECOLI_PNODE_
  24
  25 #include <sys/queue.h>
  26 #include <sys/types.h>
  27 #include <limits.h>
  28 #include <stdio.h>
  29 #include <stdbool.h>
  30
  31 struct ec_node;
  32 struct ec_pnode;
  33
  34 /**
  35  * Create an empty parsing tree.
  36  *
  37  * This function is used internally when parsing an input using
  38  * a grammar tree.
  39  *
  40  * @param node
  41  *   The grammar node.
  42  * @return
  43  *   The empty parse tree.
  44  */
  45 struct ec_pnode *ec_pnode(const struct ec_node *node);
  46
  47 /**
  48  * Free a parsing tree.
  49  *
  50  * @param pnode
  51  *   The root of the parsing tree to be freed. It must not have
  52  *   any parent.
  53  */
  54 void ec_pnode_free(struct ec_pnode *pnode);
  55
  56 /**
  57  * Remove and free all the children of a parsing tree node.
  58  *
  59  * @param pnode
  60  *   Node whose children will be freed.
  61  */
  62 void ec_pnode_free_children(struct ec_pnode *pnode);
  63
  64 /**
  65  * Duplicate a parsing tree.
  66  *
  67  * @param pnode
  68  *   A node inside a parsing tree.
  69  * @return
  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).
  72  */
  73 struct ec_pnode *ec_pnode_dup(const struct ec_pnode *pnode);
  74
  75 /**
  76  * Get the string vector associated to a parsing node.
  77  *
  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.
  81  *
  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
  85  * the second leaf.
  86  *
  87  * If the parsing tree does not match (see ec_pnode_matches()), it
  88  * the associated string vector is NULL.
  89  *
  90  * @param pnode
  91  *   The parsing node. If NULL, the function returns NULL.
  92  * @return
  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
  96  *   input.
  97  */
  98 const struct ec_strvec *ec_pnode_get_strvec(const struct ec_pnode *pnode);
  99
 100 /**
 101  * Parse a string using a grammar tree.
 102  *
 103  * This is equivalent to calling ec_parse_strvec() on the same
 104  * node, with a string vector containing only the argument string str.
 105  *
 106  * @param node
 107  *   The grammar node.
 108  * @param str
 109  *   The input string.
 110  * @return
 111  *   A parsing tree, or NULL on error (errno is set).
 112  */
 113 struct ec_pnode *ec_parse(const struct ec_node *node, const char *str);
 114
 115 /**
 116  * Parse a string vector using a grammar tree.
 117  *
 118  * Generate a parsing tree by parsing the input string vector using the
 119  * given grammar tree.
 120  *
 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.
 124  *
 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.
 128  *
 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.
 132  *
 133  * @param node
 134  *   The grammar node.
 135  * @param str
 136  *   The input string vector.
 137  * @return
 138  *   A parsing tree, or NULL on error (errno is set).
 139  */
 140 struct ec_pnode *ec_parse_strvec(const struct ec_node *node,
 141                                 const struct ec_strvec *strvec);
 142
 143 /**
 144  * Return value of ec_parse_child() when input does not match grammar.
 145  */
 146 #define EC_PARSE_NOMATCH INT_MAX
 147
 148 /**
 149  * Parse a string vector using a grammar tree, from a parent node.
 150  *
 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.
 154  *
 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.
 159  *
 160  * @param node
 161  *   The grammar node.
 162  * @param str
 163  *   The input string vector.
 164  * @return
 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.
 169  */
 170 int ec_parse_child(const struct ec_node *node, struct ec_pnode *pstate,
 171                 const struct ec_strvec *strvec);
 172
 173 /**
 174  * Link a parsing node to a parsing tree.
 175  *
 176  * Add a child to a node in a parsing tree, at the end of the children
 177  * list.
 178  *
 179  * @param pnode
 180  *   The node of the parsing tree where the child is added.
 181  * @param child
 182  *   The node (or subtree) to add in the children list.
 183  */
 184 void ec_pnode_link_child(struct ec_pnode *pnode, struct ec_pnode *child);
 185
 186 /**
 187  * Remove a child node from parsing tree.
 188  *
 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.
 191  *
 192  * @param child
 193  *   The node (or subtree) to remove.
 194  */
 195 void ec_pnode_unlink_child(struct ec_pnode *child);
 196
 197 /**
 198  * Get the root of the parsing tree.
 199  *
 200  * Get the root of the parsing tree, keeping the const statement
 201  * if the argument has it.
 202  *
 203  * @param pnode
 204  *   A node in the parsing tree.
 205  * @return
 206  *   The root of the parsing tree.
 207  */
 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_;                                     \
 212         (void)p_;                                               \
 213         res_ = ec_pnode_get_root(pnode_);                       \
 214         res_;                                                   \
 215 })
 216
 217 /**
 218  * Get the root of the parsing tree.
 219  *
 220  * You may also use EC_PNODE_GET_ROOT() instead, that keeps the
 221  * const statement.
 222  *
 223  * @param pnode
 224  *   A node in the parsing tree.
 225  * @return
 226  *   The root of the parsing tree.
 227  */
 228 struct ec_pnode *ec_pnode_get_root(struct ec_pnode *pnode);
 229
 230 /**
 231  * Get the parent node in the parsing tree.
 232  *
 233  * @param pnode
 234  *   A node in the parsing tree.
 235  * @return
 236  *   The parent node, or NULL if it is the root.
 237  */
 238 struct ec_pnode *ec_pnode_get_parent(const struct ec_pnode *pnode);
 239
 240 /**
 241  * Get the first child of a node in the parsing tree.
 242  *
 243  * @param pnode
 244  *   A node in the parsing tree.
 245  * @return
 246  *   The first child node, or NULL if it has no child.
 247  */
 248 struct ec_pnode *ec_pnode_get_first_child(const struct ec_pnode *pnode);
 249
 250 /**
 251  * Get the last child of a node in the parsing tree.
 252  *
 253  * @param pnode
 254  *   A node in the parsing tree.
 255  * @return
 256  *   The last child node, or NULL if it has no child.
 257  */
 258 struct ec_pnode *ec_pnode_get_last_child(const struct ec_pnode *pnode);
 259
 260 /**
 261  * Get the next sibling node.
 262  *
 263  * If pnode is the root of the parsing tree, return NULL. Else return
 264  * the next sibling node.
 265  *
 266  * @param pnode
 267  *   A node in the parsing tree..
 268  * @return
 269  *   The next sibling, or NULL if there is no sibling.
 270  */
 271 struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode);
 272
 273 /**
 274  * Iterate the children of a node.
 275  *
 276  * @param child
 277  *   The item that will be set at each iteration.
 278  * @param pnode
 279  *   The parent node in the parsing tree.
 280  */
 281 #define EC_PNODE_FOREACH_CHILD(child, pnode)                    \
 282         for (child = ec_pnode_get_first_child(pnode);           \
 283              child != NULL;                                     \
 284              child = ec_pnode_next(child))                      \
 285
 286 /**
 287  * Get the grammar node corresponding to the parsing node.
 288  *
 289  * @param pnode
 290  *   A node in the parsing tree.
 291  * @return
 292  *   The corresponding grammar node, that issued the parse.
 293  */
 294 const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode);
 295
 296 /**
 297  * Unlink and free the last child.
 298  *
 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.
 303  *
 304  * @param pnode
 305  *   A node in the parsing tree which has at least one child.
 306  */
 307 void ec_pnode_del_last_child(struct ec_pnode *pnode);
 308
 309 /**
 310  * Get attributes associated to a node in a parsing tree.
 311  *
 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.
 315  *
 316  * @param pnode
 317  *   A node in the parsing tree.
 318  * @return
 319  *   The dictionary containing the attributes.
 320  */
 321 struct ec_dict *ec_pnode_get_attrs(struct ec_pnode *pnode);
 322
 323 /**
 324  * Dump a parsing tree.
 325  *
 326  * @param out
 327  *   The stream where the dump is done.
 328  * @param pnode
 329  *   The parsing tree to dump.
 330  */
 331 void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode);
 332
 333 /**
 334  * Find a node from its identifier.
 335  *
 336  * Find the first node in the parsing tree which has the given
 337  * node identifier. The search is a depth-first search.
 338  *
 339  * @param root
 340  *   The node of the parsing tree where the search starts.
 341  * @param id
 342  *   The node identifier string to match.
 343  * @return
 344  *   The first node matching the identifier, or NULL if not found.
 345  */
 346 struct ec_pnode *ec_pnode_find(struct ec_pnode *root, const char *id);
 347
 348 /**
 349  * Find the next node matching an identifier.
 350  *
 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
 353  * 2 options:
 354  * - continue the depth-first search where it was interrupted.
 355  * - skip the children of the current node, and continue the depth-first
 356  *   search.
 357  *
 358  * @param pnode
 359  *   The root of the search, as passed to ec_pnode_find().
 360  * @param prev
 361  *   The node returned by the previous search.
 362  * @param id
 363  *   The node identifier string to match.
 364  * @param iter_children
 365  *   True to iterate the children of "prev", false to skip them.
 366  * @return
 367  *   The next node matching the identifier, or NULL if not found.
 368  */
 369 struct ec_pnode *ec_pnode_find_next(struct ec_pnode *root,
 370                                 struct ec_pnode *prev,
 371                                 const char *id, bool iter_children);
 372
 373 /**
 374  * Iterate among parse tree
 375  *
 376  * Use it with:
 377  * for (iter = pnode; iter != NULL; iter = EC_PNODE_ITER_NEXT(pnode, iter, 1))
 378  */
 379 struct ec_pnode *__ec_pnode_iter_next(const struct ec_pnode *root,
 380                                 struct ec_pnode *pnode, bool iter_children);
 381
 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_;                                             \
 387         (void)p_;                                                       \
 388         res_ = __ec_pnode_iter_next(root, pnode_, iter_children);       \
 389         res_;                                                           \
 390 })
 391
 392 /**
 393  *
 394  *
 395  *
 396  */
 397 size_t ec_pnode_len(const struct ec_pnode *pnode);
 398
 399 /**
 400  *
 401  *
 402  *
 403  */
 404 size_t ec_pnode_matches(const struct ec_pnode *pnode);
 405
 406 #endif