2 tre-ast.h - Abstract syntax tree (AST) definitions
4 This software is released under a BSD-style license.
5 See the file LICENSE for details and copyright.
16 #include "tre-internal.h"
17 #include "tre-compile.h"
19 /* The different AST node types. */
27 /* Special subtypes of TRE_LITERAL. */
28 #define EMPTY -1 /* Empty leaf (denotes empty string). */
29 #define ASSERTION -2 /* Assertion leaf. */
30 #define TAG -3 /* Tag leaf. */
31 #define BACKREF -4 /* Back reference leaf. */
32 #define PARAMETER -5 /* Parameter. */
34 #define IS_SPECIAL(x) ((x)->code_min < 0)
35 #define IS_EMPTY(x) ((x)->code_min == EMPTY)
36 #define IS_ASSERTION(x) ((x)->code_min == ASSERTION)
37 #define IS_TAG(x) ((x)->code_min == TAG)
38 #define IS_BACKREF(x) ((x)->code_min == BACKREF)
39 #define IS_PARAMETER(x) ((x)->code_min == PARAMETER)
41 #define SUBMATCH_ID_INVISIBLE_START (INT_MAX / 2 + 1)
44 /* A generic AST node. All AST nodes consist of this node on the top
45 level with `obj' pointing to the actual content. */
46 typedef struct _tre_ast_node {
47 void *obj; /* Pointer to actual node. */
48 tre_last_matched_branch_pre_t *last_matched_branch;
49 tre_last_matched_pre_t *last_matched_in_progress;
50 tre_pos_and_tags_t *firstpos;
51 tre_pos_and_tags_t *lastpos;
52 /* The original pointer is used to point to the original node, when a
53 * CATENATION and tag are added. If NULL, this is node is the original */
54 struct _tre_ast_node *original;
55 tre_ast_type_t type; /* Type of the node. */
64 /* A "literal" node. These are created for assertions, back references,
65 tags, matching parameter settings, and all expressions that match one
72 tre_bracket_match_list_t *bracket_match_list;
77 /* A "catenation" node. These are created when two regexps are concatenated.
78 If there are more than one subexpressions in sequence, the `left' part
79 holds all but the last, and `right' part holds the last subexpression
80 (catenation is left associative). */
83 tre_ast_node_t *right;
86 /* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}"
89 /* Subexpression to match. */
91 /* Minimum number of consecutive matches. */
93 /* Maximum number of consecutive matches. */
95 /* If 0, match as many characters as possible, if 1 match as few as
96 possible. Note that this does not always mean the same thing as
97 matching as many/few repetitions as possible. */
98 unsigned int minimal:1;
99 /* Approximate matching parameters (or NULL). */
103 /* An "union" node. These are created for the "|" operator. */
105 tre_ast_node_t *left;
106 tre_ast_node_t *right;
107 /* The left end right end tags if non-zero */
113 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size);
116 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position);
119 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max,
123 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right);
126 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
127 tre_ast_node_t *right);
131 tre_ast_print(tre_ast_node_t *tree);
133 /* XXX - rethink AST printing API */
135 tre_print_params(int *params);
136 #endif /* TRE_DEBUG */
138 #endif /* TRE_AST_H */