]> git.saurik.com Git - apple/libc.git/blob - regex/TRE/lib/tre-ast.c
projects / apple / libc.git / blob
? search:


12f8cdc6ba95d161f041c7a85ece5a140eed9d7b
[apple/libc.git] / regex / TRE / lib / tre-ast.c
1 /*
2 tre-ast.c - Abstract syntax tree (AST) routines
3
4 This software is released under a BSD-style license.
5 See the file LICENSE for details and copyright.
6
7 */
8
9 #ifdef HAVE_CONFIG_H
10 #include <config.h>
11 #endif /* HAVE_CONFIG_H */
12 #include <assert.h>
13
14 #include "tre-ast.h"
15 #include "tre-mem.h"
16
17 tre_ast_node_t *
18 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size)
19 {
20 tre_ast_node_t *node;
21
22 node = tre_mem_calloc(mem, sizeof(*node));
23 if (!node)
24 return NULL;
25 node->obj = tre_mem_calloc(mem, size);
26 if (!node->obj)
27 return NULL;
28 node->type = type;
29 node->nullable = -1;
30 node->submatch_id = -1;
31
32 return node;
33 }
34
35 tre_ast_node_t *
36 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position)
37 {
38 tre_ast_node_t *node;
39 tre_literal_t *lit;
40
41 node = tre_ast_new_node(mem, LITERAL, sizeof(tre_literal_t));
42 if (!node)
43 return NULL;
44 lit = node->obj;
45 lit->code_min = code_min;
46 lit->code_max = code_max;
47 lit->position = position;
48
49 return node;
50 }
51
52 tre_ast_node_t *
53 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max,
54 int minimal)
55 {
56 tre_ast_node_t *node;
57 tre_iteration_t *iter;
58
59 node = tre_ast_new_node(mem, ITERATION, sizeof(tre_iteration_t));
60 if (!node)
61 return NULL;
62 iter = node->obj;
63 iter->arg = arg;
64 iter->min = min;
65 iter->max = max;
66 iter->minimal = minimal;
67 node->num_submatches = arg->num_submatches;
68
69 return node;
70 }
71
72 tre_ast_node_t *
73 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right)
74 {
75 tre_ast_node_t *node;
76
77 node = tre_ast_new_node(mem, UNION, sizeof(tre_union_t));
78 if (node == NULL)
79 return NULL;
80 ((tre_union_t *)node->obj)->left = left;
81 ((tre_union_t *)node->obj)->right = right;
82 node->num_submatches = left->num_submatches + right->num_submatches;
83
84 return node;
85 }
86
87 tre_ast_node_t *
88 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
89 tre_ast_node_t *right)
90 {
91 tre_ast_node_t *node;
92
93 node = tre_ast_new_node(mem, CATENATION, sizeof(tre_catenation_t));
94 if (node == NULL)
95 return NULL;
96 ((tre_catenation_t *)node->obj)->left = left;
97 ((tre_catenation_t *)node->obj)->right = right;
98 node->num_submatches = left->num_submatches + right->num_submatches;
99
100 return node;
101 }
102
103 #ifdef TRE_DEBUG
104
105 static void
106 tre_findent(FILE *stream, int i)
107 {
108 while (i-- > 0)
109 fputc(' ', stream);
110 }
111
112 void
113 tre_print_params(int *params)
114 {
115 int i;
116 if (params)
117 {
118 DPRINT(("params ["));
119 for (i = 0; i < TRE_PARAM_LAST; i++)
120 {
121 if (params[i] == TRE_PARAM_UNSET)
122 DPRINT(("unset"));
123 else if (params[i] == TRE_PARAM_DEFAULT)
124 DPRINT(("default"));
125 else
126 DPRINT(("%d", params[i]));
127 if (i < TRE_PARAM_LAST - 1)
128 DPRINT((", "));
129 }
130 DPRINT(("]"));
131 }
132 }
133
134 static void
135 tre_do_print(FILE *stream, tre_ast_node_t *ast, int indent)
136 {
137 int code_min, code_max, pos;
138 int num_tags = ast->num_tags;
139 tre_literal_t *lit;
140 tre_iteration_t *iter;
141
142 tre_findent(stream, indent);
143 switch (ast->type)
144 {
145 case LITERAL:
146 lit = ast->obj;
147 code_min = lit->code_min;
148 code_max = lit->code_max;
149 pos = lit->position;
150 if (IS_EMPTY(lit))
151 {
152 fprintf(stream, "literal empty\n");
153 }
154 else if (IS_ASSERTION(lit))
155 {
156 int i;
157 char *assertions[] = { "bol", "eol", "bracket",
158 "bow", "eow", "wb", "!wb", "backref" };
159 if (code_max >= ASSERT_LAST << 1)
160 assert(0);
161 fprintf(stream, "assertions: ");
162 for (i = 0; (1 << i) <= ASSERT_LAST; i++)
163 if (code_max & (1 << i))
164 fprintf(stream, "%s ", assertions[i]);
165 fprintf(stream, "\n");
166 }
167 else if (IS_TAG(lit))
168 {
169 fprintf(stream, "tag %d\n", code_max);
170 }
171 else if (IS_BACKREF(lit))
172 {
173 fprintf(stream, "backref %d, pos %d\n", code_max, pos);
174 }
175 else if (IS_PARAMETER(lit))
176 {
177 tre_print_params(lit->u.params);
178 fprintf(stream, "\n");
179 }
180 else
181 {
182 fprintf(stream, "literal (%c, %c) (%d, %d), pos %d, sub %d, "
183 "%d tags\n", code_min, code_max, code_min, code_max, pos,
184 ast->submatch_id, num_tags);
185 }
186 break;
187 case ITERATION:
188 iter = ast->obj;
189 fprintf(stream, "iteration {%d, %d}, sub %d, %d tags, %s\n",
190 iter->min, iter->max, ast->submatch_id, num_tags,
191 iter->minimal ? "minimal" : "greedy");
192 tre_do_print(stream, iter->arg, indent + 2);
193 break;
194 case UNION:
195 fprintf(stream, "union, sub %d, %d tags\n", ast->submatch_id, num_tags);
196 tre_do_print(stream, ((tre_union_t *)ast->obj)->left, indent + 2);
197 tre_do_print(stream, ((tre_union_t *)ast->obj)->right, indent + 2);
198 break;
199 case CATENATION:
200 fprintf(stream, "catenation, sub %d, %d tags\n", ast->submatch_id,
201 num_tags);
202 tre_do_print(stream, ((tre_catenation_t *)ast->obj)->left, indent + 2);
203 tre_do_print(stream, ((tre_catenation_t *)ast->obj)->right, indent + 2);
204 break;
205 default:
206 assert(0);
207 break;
208 }
209 }
210
211 static void
212 tre_ast_fprint(FILE *stream, tre_ast_node_t *ast)
213 {
214 tre_do_print(stream, ast, 0);
215 }
216
217 void
218 tre_ast_print(tre_ast_node_t *tree)
219 {
220 printf("AST:\n");
221 tre_ast_fprint(stdout, tree);
222 }
223
224 #endif /* TRE_DEBUG */
225
226 /* EOF */
mirror of libc