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  *
 145  *
 146  *
 147  */
 148 #define EC_PARSE_NOMATCH INT_MAX
 149
 150 /* internal: used by nodes
 151  *
 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.
 158  *
 159  * return:
 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
 163  */
 164 int ec_parse_child(const struct ec_node *node,
 165                         struct ec_pnode *pstate,
 166                         const struct ec_strvec *strvec);
 167
 168 /**
 169  *
 170  *
 171  *
 172  */
 173 void ec_pnode_link_child(struct ec_pnode *pnode,
 174                         struct ec_pnode *child);
 175 /**
 176  *
 177  *
 178  *
 179  */
 180 void ec_pnode_unlink_child(struct ec_pnode *pnode,
 181                         struct ec_pnode *child);
 182
 183 /* keep the const */
 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_;                                     \
 188         (void)p_;                                               \
 189         res_ = __ec_pnode_get_root(pnode_);                     \
 190         res_;                                                   \
 191 })
 192
 193 /**
 194  *
 195  *
 196  *
 197  */
 198 struct ec_pnode *__ec_pnode_get_root(struct ec_pnode *pnode);
 199
 200 /**
 201  *
 202  *
 203  *
 204  */
 205 struct ec_pnode *ec_pnode_get_parent(const struct ec_pnode *pnode);
 206
 207 /**
 208  * Get the first child of a tree.
 209  *
 210  */
 211 struct ec_pnode *ec_pnode_get_first_child(const struct ec_pnode *pnode);
 212
 213 /**
 214  *
 215  *
 216  *
 217  */
 218 struct ec_pnode *ec_pnode_get_last_child(const struct ec_pnode *pnode);
 219
 220 /**
 221  *
 222  *
 223  *
 224  */
 225 struct ec_pnode *ec_pnode_next(const struct ec_pnode *pnode);
 226
 227 /**
 228  *
 229  *
 230  *
 231  */
 232 #define EC_PNODE_FOREACH_CHILD(child, parse)                    \
 233         for (child = ec_pnode_get_first_child(parse);           \
 234              child != NULL;                                     \
 235              child = ec_pnode_next(child))                      \
 236
 237 /**
 238  *
 239  *
 240  *
 241  */
 242 bool ec_pnode_has_child(const struct ec_pnode *pnode);
 243
 244 /**
 245  *
 246  *
 247  *
 248  */
 249 const struct ec_node *ec_pnode_get_node(const struct ec_pnode *pnode);
 250
 251 /**
 252  *
 253  *
 254  *
 255  */
 256 void ec_pnode_del_last_child(struct ec_pnode *pnode);
 257
 258 /**
 259  *
 260  *
 261  *
 262  */
 263 struct ec_dict *ec_pnode_get_attrs(struct ec_pnode *pnode);
 264
 265 /**
 266  *
 267  *
 268  *
 269  */
 270 void ec_pnode_dump(FILE *out, const struct ec_pnode *pnode);
 271
 272 /**
 273  *
 274  *
 275  *
 276  */
 277 struct ec_pnode *ec_pnode_find(struct ec_pnode *pnode,
 278         const char *id);
 279
 280 /**
 281  *
 282  *
 283  *
 284  */
 285 struct ec_pnode *ec_pnode_find_next(struct ec_pnode *root,
 286                                 struct ec_pnode *start,
 287                                 const char *id, bool iter_children);
 288
 289 /**
 290  * Iterate among parse tree
 291  *
 292  * Use it with:
 293  * for (iter = pnode; iter != NULL; iter = EC_PNODE_ITER_NEXT(pnode, iter, 1))
 294  */
 295 struct ec_pnode *__ec_pnode_iter_next(const struct ec_pnode *root,
 296                                 struct ec_pnode *pnode, bool iter_children);
 297
 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_;                                             \
 303         (void)p_;                                                       \
 304         res_ = __ec_pnode_iter_next(root, pnode_, iter_children);       \
 305         res_;                                                           \
 306 })
 307
 308 /**
 309  *
 310  *
 311  *
 312  */
 313 size_t ec_pnode_len(const struct ec_pnode *pnode);
 314
 315 /**
 316  *
 317  *
 318  *
 319  */
 320 size_t ec_pnode_matches(const struct ec_pnode *pnode);
 321
 322 #endif