include/ecoli_node.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 /**
   6  * @defgroup grammar_graph Grammar Graph
   7  * @{
   8  *
   9  * @brief Libecoli grammar nodes.
  10  *
  11  * The grammar node is a main structure of the ecoli library, used to define
  12  * how to match and complete the input tokens. A node is a generic object
  13  * that implements:
  14  * - a parse(node, input) method: check if an input matches
  15  * - a complete(node, input) method: return possible completions for
  16  *   a given input
  17  * - some other methods to initialize, free, ...
  18  *
  19  * One basic example is the string node (ec_node_str). A node
  20  * ec_node_str("foo") will match any token list starting with "foo",
  21  * for example:
  22  * - ["foo"]
  23  * - ["foo", "bar", ...]
  24  * But will not match:
  25  * - []
  26  * - ["bar", ...]
  27  *
  28  * A node ec_node_str("foo") will complete with "foo" if the input
  29  * contains one token, with the same beginning than "foo":
  30  * - [""]
  31  * - ["f"]
  32  * - ["fo"]
  33  * - ["foo"]
  34  * But it will not complete:
  35  * - []
  36  * - ["bar"]
  37  * - ["f", ""]
  38  * - ["", "f"]
  39  *
  40  * A node can have child nodes. For instance, a sequence node
  41  * ec_node_seq(ec_node_str("foo"), ec_node_str("bar")) will match
  42  * a sequence: ["foo", "bar"].
  43  *
  44  * Note: at some places in the documentation and the code, we may talk
  45  * about the grammar tree, but as loops are allowed, we should instead
  46  * talk about grammar graph.
  47  */
  48
  49 #ifndef ECOLI_NODE_
  50 #define ECOLI_NODE_
  51
  52 #include <sys/queue.h>
  53 #include <sys/types.h>
  54 #include <stdbool.h>
  55 #include <stdio.h>
  56
  57 /**
  58  * Node has no identifier.
  59  */
  60 #define EC_NO_ID "no-id"
  61
  62 struct ec_node;
  63 struct ec_pnode;
  64 struct ec_comp;
  65 struct ec_strvec;
  66 struct ec_dict;
  67 struct ec_config;
  68 struct ec_config_schema;
  69
  70 /**
  71  * Register a node type at library load.
  72  *
  73  * The node type is registered in a function that has the the
  74  * constructor attribute: the function is called at library load.
  75  *
  76  * @param t
  77  *   The name of the ec_node_type structure variable.
  78  */
  79 #define EC_NODE_TYPE_REGISTER(t)                                        \
  80         static void ec_node_init_##t(void);                             \
  81         static void __attribute__((constructor, used))                  \
  82         ec_node_init_##t(void)                                          \
  83         {                                                               \
  84                 if (ec_node_type_register(&t, 0) < 0)                   \
  85                         fprintf(stderr,                                 \
  86                                 "cannot register node type %s\n",       \
  87                                 t.name);                                \
  88         }
  89
  90 /**
  91  * Register a node type at library load, overriding previous registration.
  92  *
  93  * The node type is registered in a function that has the the
  94  * constructor attribute: the function is called at library load.
  95  *
  96  * Be careful when using this macro, as the last type with a given name
  97  * is the one that is actually registered. The call order may be hard to
  98  * predict, especially within the same binary.
  99  *
 100  * @param t
 101  *   The name of the ec_node_type structure variable.
 102  */
 103 #define EC_NODE_TYPE_REGISTER_OVERRIDE(t)                               \
 104         static void ec_node_init_##t(void);                             \
 105         static void __attribute__((constructor, used))                  \
 106         ec_node_init_##t(void)                                          \
 107         {                                                               \
 108                 if (ec_node_type_register(&t, 1) < 0)                   \
 109                         fprintf(stderr,                                 \
 110                                 "cannot register node type %s\n",       \
 111                                 t.name);                                \
 112         }
 113
 114 /**
 115  * A list of node types.
 116  */
 117 TAILQ_HEAD(ec_node_type_list, ec_node_type);
 118
 119 /**
 120  * Function type used to configure a node.
 121  *
 122  * The function pointer is not called directly, the helper
 123  * @ec_node_set_config() should be used instead.
 124  *
 125  * The configuration passed to this function pointer is valid,
 126  * i.e. @ec_config_validate() returned 0 on it.
 127  *
 128  * @param node
 129  *   The node to configure.
 130  * @param config
 131  *   The configuration to apply to the node.
 132  * @return
 133  *   0 on success, negative on error (errno is set).
 134  */
 135 typedef int (*ec_node_set_config_t)(struct ec_node *node,
 136                                 const struct ec_config *config);
 137
 138 /**
 139  * Parse a string vector using the given grammar graph.
 140  *
 141  * The function pointer is not called directly, the helpers @ec_parse(),
 142  * ec_parse_strvec() or ec_parse_child() should be used instead.
 143  *
 144  * The implementation of this method for a node that manages children
 145  * will call ec_parse_child(child, pstate, child_strvec).
 146  *
 147  * @param node
 148  *   The grammar graph.
 149  * @param pstate
 150  *   A pointer to the leaf being parsed in the parsing tree. It can be
 151  *   used by a node to retrieve information from the current parsing
 152  *   tree. To get the root of the tree, @ec_pnode_get_root(pstate) should
 153  *   be used.
 154  * @param strvec
 155  *   The string vector to be parsed.
 156  * @return
 157  *   On success, return the number of consumed items in the string vector
 158  *   (can be 0) or EC_PARSE_NOMATCH if the node cannot parse the string
 159  *   vector. On error, a negative value is returned and errno is set.
 160  */
 161 typedef int (*ec_parse_t)(const struct ec_node *node,
 162                         struct ec_pnode *pstate,
 163                         const struct ec_strvec *strvec);
 164
 165 /**
 166  * Get completion items using the given grammar graph.
 167  *
 168  * The function pointer should not be called directly, the helpers
 169  * @ec_complete(), ec_complete_strvec() or ec_complete_child() should be
 170  * used instead.
 171  *
 172  * This function completes the last element of the string vector.
 173  * For instance, node.type->complete(node, comp, ["ls"]) will
 174  * list all commands that starts with "ls", while
 175  * node.type->complete(node, comp, ["ls", ""]) will list all
 176  * possible values for the next argument.
 177  *
 178  * The implementation of this function in the node is supposed
 179  * to either:
 180  * - call @ec_comp_add_item(node, comp, ...) for each completion item
 181  *   that should be added to the list. This is typically done in
 182  *   terminal nodes, for example in ec_node_str or ec_node_file.
 183  * - call @ec_complete_child(child, comp, child_strvec) to let
 184  *   the children nodes add their own completion. This is the
 185  *   case of ec_node_or which trivially calls @ec_complete_child()
 186  *   on all its children, and of ec_node_seq, which has to
 187  *   do a more complex job (parsing strvec).
 188  *
 189  * A node that does not provide any method for the completion
 190  * will fallback to ec_complete_unknown(): this helper returns
 191  * a completion item of type EC_COMP_UNKNOWN, just to indicate
 192  * that everything before the last element of the string vector
 193  * has been parsed successfully, but we don't know how to
 194  * complete the last element.
 195  *
 196  * @param node
 197  *   The root node of the grammar graph.
 198  * @param comp
 199  *   The current list of completion items, to be filled by the
 200  *   node.type->complete() method.
 201  * @param strvec
 202  *   The string vector to be completed.
 203  * @return
 204  *   0 on success, or a negative value on error (errno is set).
 205  */
 206 typedef int (*ec_complete_t)(const struct ec_node *node,
 207                                 struct ec_comp *comp,
 208                                 const struct ec_strvec *strvec);
 209
 210 /**
 211  * Get the short description of a grammar node.
 212  *
 213  * This function pointer should not be called directly. The
 214  * @ec_node_desc() helper should be used instead.
 215  *
 216  * This callback is typically used when building a help string for a
 217  * grammar graph. It is used in ecoli editline interface to generate
 218  * contextual help like this (first column):
 219  *   <int>     An integer.
 220  *   foo       The foo string.
 221  *   bar       The bar string.
 222  *
 223  * If this callback is set to NULL in the node type, the
 224  * default behavior is to return the node type name inside <>, for
 225  * instance "<int>". The string node type implements this method to
 226  * return the string value. An integer node could implement it
 227  * to return its range (ex: "1..10").
 228  *
 229  * The returned value is a pointer that must be freed by
 230  * the caller with @ec_free().
 231  *
 232  * On error, NULL is returned and errno is set.
 233  */
 234 typedef char * (*ec_node_desc_t)(const struct ec_node *);
 235
 236 /**
 237  * Initialize the node private area.
 238  *
 239  * This function pointer should not be called directly. The @ec_node()
 240  * and ec_node_from_type() helpers, that allocate new nodes, should be
 241  * used instead.
 242  *
 243  * If not NULL, this function is called when a node is instanciated, to
 244  * initialize the private area of a node. In any case, the private area
 245  * is first zeroed.
 246  *
 247  * On success, 0 is returned. On error, a negative value is returned and
 248  * errno is set.
 249  */
 250 typedef int (*ec_node_init_priv_t)(struct ec_node *);
 251
 252 /**
 253  * Free the node private area.
 254  *
 255  * This function pointer should not be called directly. The
 256  * @ec_node_free() helper should be used instead.
 257  *
 258  * When a node is deleted, this function is called to free the resources
 259  * referenced in the node private area.
 260  */
 261 typedef void (*ec_node_free_priv_t)(struct ec_node *);
 262
 263 /**
 264  * Count the number of node children.
 265  *
 266  * This function pointer should not be called directly. The
 267  * @ec_node_get_children_count() helper should be used instead.
 268  *
 269  * Some grammar nodes like seq, or, many, (...), reference children
 270  * nodes in the grammar graph. This function returns the number of
 271  * children.
 272  */
 273 typedef size_t (*ec_node_get_children_count_t)(const struct ec_node *);
 274
 275 /**
 276  * Count the number of node children.
 277  *
 278  * This function pointer should not be called directly. The
 279  * @ec_node_get_child() helper should be used instead.
 280  *
 281  * Some grammar nodes like seq, or, many, (...), reference children
 282  * nodes in the grammar graph. This function sets the i-th child (with i
 283  * lower than the return value of ec_node_get_children_count()) in the
 284  * child pointer. It also returns the number of references to the child
 285  * owned by the parent. This information is used by the algorithm that
 286  * frees a grammar graph taking care of loops.
 287  *
 288  * On success, 0 is returned. On error, a negative value is returned and
 289  * errno is set.
 290  */
 291 typedef int (*ec_node_get_child_t)(const struct ec_node *,
 292         size_t i, struct ec_node **child, unsigned int *refs);
 293
 294 /**
 295  * A structure describing a grammar node type.
 296  *
 297  * It is usually defined as a static const structure in the code
 298  * defining a new grammar node type. Examples can be found in
 299  * ecoli_node_<type>.c files.
 300  */
 301 struct ec_node_type {
 302         TAILQ_ENTRY(ec_node_type) next;  /**< Next in list. */
 303         const char *name;                /**< Node type name. */
 304         /** Configuration schema array, must be terminated by a sentinel
 305          *  (.type = EC_CONFIG_TYPE_NONE). */
 306         const struct ec_config_schema *schema;
 307         size_t size;                     /**< Size of private area */
 308         ec_node_set_config_t set_config; /**< Validate and set configuration. */
 309         ec_parse_t parse;                /**< Parse a string vector. */
 310         ec_complete_t complete;          /**< Get completion items. */
 311         ec_node_desc_t desc;             /**< Get short description. */
 312         ec_node_init_priv_t init_priv;   /**< Initialize private area. */
 313         ec_node_free_priv_t free_priv;   /**< Free node resourses. */
 314         /** Get children count. */
 315         ec_node_get_children_count_t get_children_count;
 316         ec_node_get_child_t get_child;   /**< Get the i-th child. */
 317 };
 318
 319 /**
 320  * Register a node type.
 321  *
 322  * The name of the type being registered is a uniq identifier. However,
 323  * it is possible to force the registration of a type with an existing
 324  * name by setting "override" to true. Note that the initial type is not
 325  * removed from the list, instead the new one is added before in the
 326  * list.
 327  *
 328  * @param type
 329  *   The node type to be registered.
 330  * @param override
 331  *   Allow the registration of an existing type.
 332  * @return
 333  *   0 on success, negative value on error.
 334  */
 335 int ec_node_type_register(struct ec_node_type *type, bool override);
 336
 337 /**
 338  * Lookup node type by name.
 339  *
 340  * @param name
 341  *   The name of the node type to search.
 342  * @return
 343  *   The (read-only) node type if found, or NULL on error.
 344  */
 345 const struct ec_node_type *ec_node_type_lookup(const char *name);
 346
 347 /**
 348  * Dump registered log types.
 349  *
 350  * @param out
 351  *   The stream where the dump is sent.
 352  */
 353 void ec_node_type_dump(FILE *out);
 354
 355 /**
 356  * Get the config schema of a node type.
 357  *
 358  * @param type
 359  *   The node type.
 360  * @return
 361  *   The (read-only) config schema of the node type, or NULL
 362  *   if the node type has no config schema.
 363  */
 364 const struct ec_config_schema *
 365 ec_node_type_schema(const struct ec_node_type *type);
 366
 367 /**
 368  * Get the name of a node type.
 369  *
 370  * @param type
 371  *   The node type.
 372  * @return
 373  *   The (read-only) name of the node type.
 374  */
 375 const char *
 376 ec_node_type_name(const struct ec_node_type *type);
 377
 378 /**
 379  * create a new node when the type is known, typically called from the node
 380  * code */
 381 struct ec_node *ec_node_from_type(const struct ec_node_type *type, const char *id);
 382
 383 /**
 384  * Create a new node from type name.
 385  */
 386 struct ec_node *ec_node(const char *typename, const char *id);
 387
 388 struct ec_node *ec_node_clone(struct ec_node *node);
 389 void ec_node_free(struct ec_node *node);
 390
 391 /* set configuration of a node
 392  * after a call to this function, the config is
 393  * owned by the node and must not be used by the caller
 394  * on error, the config is freed. */
 395 int ec_node_set_config(struct ec_node *node, struct ec_config *config);
 396
 397 /* get the current node configuration. Return NULL if no configuration. */
 398 const struct ec_config *ec_node_get_config(struct ec_node *node);
 399
 400 size_t ec_node_get_children_count(const struct ec_node *node);
 401 int
 402 ec_node_get_child(const struct ec_node *node, size_t i,
 403         struct ec_node **child, unsigned int *refs);
 404
 405 /* XXX add more accessors */
 406 const struct ec_node_type *ec_node_type(const struct ec_node *node);
 407 struct ec_dict *ec_node_attrs(const struct ec_node *node);
 408 const char *ec_node_id(const struct ec_node *node);
 409
 410 char *ec_node_desc(const struct ec_node *node);
 411
 412 void ec_node_dump(FILE *out, const struct ec_node *node);
 413 struct ec_node *ec_node_find(struct ec_node *node, const char *id);
 414
 415 /* check the type of a node */
 416 int ec_node_check_type(const struct ec_node *node,
 417                 const struct ec_node_type *type);
 418
 419 const char *ec_node_get_type_name(const struct ec_node *node);
 420
 421 /**
 422  * Get the pointer to the node private area.
 423  *
 424  * @param node
 425  *   The grammar node.
 426  * @return
 427  *   The pointer to the node private area.
 428  */
 429 void *ec_node_priv(const struct ec_node *node);
 430
 431 #endif
 432
 433  /** @} */