1 /*
2 tre-ast.c - Abstract syntax tree (AST) routines
3
4 Copyright (c) 2001-2006 Ville Laurikari <vl@iki.fi>
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
10
11 This library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with this library; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19
20 */
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif /* HAVE_CONFIG_H */
25 #include <assert.h>
26
27 #include "tre-ast.h"
28 #include "tre-mem.h"
29
30 tre_ast_node_t *
tre_ast_new_node(tre_mem_t mem,tre_ast_type_t type,size_t size)31 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size)
32 {
33 tre_ast_node_t *node;
34
35 node = tre_mem_calloc(mem, sizeof(*node));
36 if (!node)
37 return NULL;
38 node->obj = tre_mem_calloc(mem, size);
39 if (!node->obj)
40 return NULL;
41 node->type = type;
42 node->nullable = -1;
43 node->submatch_id = -1;
44
45 return node;
46 }
47
48 tre_ast_node_t *
tre_ast_new_literal(tre_mem_t mem,int code_min,int code_max,int position)49 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position)
50 {
51 tre_ast_node_t *node;
52 tre_literal_t *lit;
53
54 node = tre_ast_new_node(mem, LITERAL, sizeof(tre_literal_t));
55 if (!node)
56 return NULL;
57 lit = node->obj;
58 lit->code_min = code_min;
59 lit->code_max = code_max;
60 lit->position = position;
61
62 return node;
63 }
64
65 tre_ast_node_t *
tre_ast_new_iter(tre_mem_t mem,tre_ast_node_t * arg,int min,int max,int minimal)66 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max,
67 int minimal)
68 {
69 tre_ast_node_t *node;
70 tre_iteration_t *iter;
71
72 node = tre_ast_new_node(mem, ITERATION, sizeof(tre_iteration_t));
73 if (!node)
74 return NULL;
75 iter = node->obj;
76 iter->arg = arg;
77 iter->min = min;
78 iter->max = max;
79 iter->minimal = minimal;
80 node->num_submatches = arg->num_submatches;
81
82 return node;
83 }
84
85 tre_ast_node_t *
tre_ast_new_union(tre_mem_t mem,tre_ast_node_t * left,tre_ast_node_t * right)86 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right)
87 {
88 tre_ast_node_t *node;
89
90 node = tre_ast_new_node(mem, UNION, sizeof(tre_union_t));
91 if (node == NULL)
92 return NULL;
93 ((tre_union_t *)node->obj)->left = left;
94 ((tre_union_t *)node->obj)->right = right;
95 node->num_submatches = left->num_submatches + right->num_submatches;
96
97 return node;
98 }
99
100 tre_ast_node_t *
tre_ast_new_catenation(tre_mem_t mem,tre_ast_node_t * left,tre_ast_node_t * right)101 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
102 tre_ast_node_t *right)
103 {
104 tre_ast_node_t *node;
105
106 node = tre_ast_new_node(mem, CATENATION, sizeof(tre_catenation_t));
107 if (node == NULL)
108 return NULL;
109 ((tre_catenation_t *)node->obj)->left = left;
110 ((tre_catenation_t *)node->obj)->right = right;
111 node->num_submatches = left->num_submatches + right->num_submatches;
112
113 return node;
114 }
115
116 #ifdef TRE_DEBUG
117
118 static void
tre_findent(FILE * stream,int i)119 tre_findent(FILE *stream, int i)
120 {
121 while (i-- > 0)
122 fputc(' ', stream);
123 }
124
125 void
tre_print_params(int * params)126 tre_print_params(int *params)
127 {
128 int i;
129 if (params)
130 {
131 DPRINT(("params ["));
132 for (i = 0; i < TRE_PARAM_LAST; i++)
133 {
134 if (params[i] == TRE_PARAM_UNSET)
135 DPRINT(("unset"));
136 else if (params[i] == TRE_PARAM_DEFAULT)
137 DPRINT(("default"));
138 else
139 DPRINT(("%d", params[i]));
140 if (i < TRE_PARAM_LAST - 1)
141 DPRINT((", "));
142 }
143 DPRINT(("]"));
144 }
145 }
146
147 static void
tre_do_print(FILE * stream,tre_ast_node_t * ast,int indent)148 tre_do_print(FILE *stream, tre_ast_node_t *ast, int indent)
149 {
150 int code_min, code_max, pos;
151 int num_tags = ast->num_tags;
152 tre_literal_t *lit;
153 tre_iteration_t *iter;
154
155 tre_findent(stream, indent);
156 switch (ast->type)
157 {
158 case LITERAL:
159 lit = ast->obj;
160 code_min = lit->code_min;
161 code_max = lit->code_max;
162 pos = lit->position;
163 if (IS_EMPTY(lit))
164 {
165 fprintf(stream, "literal empty\n");
166 }
167 else if (IS_ASSERTION(lit))
168 {
169 int i;
170 char *assertions[] = { "bol", "eol", "ctype", "!ctype",
171 "bow", "eow", "wb", "!wb" };
172 if (code_max >= ASSERT_LAST << 1)
173 assert(0);
174 fprintf(stream, "assertions: ");
175 for (i = 0; (1 << i) <= ASSERT_LAST; i++)
176 if (code_max & (1 << i))
177 fprintf(stream, "%s ", assertions[i]);
178 fprintf(stream, "\n");
179 }
180 else if (IS_TAG(lit))
181 {
182 fprintf(stream, "tag %d\n", code_max);
183 }
184 else if (IS_BACKREF(lit))
185 {
186 fprintf(stream, "backref %d, pos %d\n", code_max, pos);
187 }
188 else if (IS_PARAMETER(lit))
189 {
190 tre_print_params(lit->u.params);
191 fprintf(stream, "\n");
192 }
193 else
194 {
195 fprintf(stream, "literal (%c, %c) (%d, %d), pos %d, sub %d, "
196 "%d tags\n", code_min, code_max, code_min, code_max, pos,
197 ast->submatch_id, num_tags);
198 }
199 break;
200 case ITERATION:
201 iter = ast->obj;
202 fprintf(stream, "iteration {%d, %d}, sub %d, %d tags, %s\n",
203 iter->min, iter->max, ast->submatch_id, num_tags,
204 iter->minimal ? "minimal" : "greedy");
205 tre_do_print(stream, iter->arg, indent + 2);
206 break;
207 case UNION:
208 fprintf(stream, "union, sub %d, %d tags\n", ast->submatch_id, num_tags);
209 tre_do_print(stream, ((tre_union_t *)ast->obj)->left, indent + 2);
210 tre_do_print(stream, ((tre_union_t *)ast->obj)->right, indent + 2);
211 break;
212 case CATENATION:
213 fprintf(stream, "catenation, sub %d, %d tags\n", ast->submatch_id,
214 num_tags);
215 tre_do_print(stream, ((tre_catenation_t *)ast->obj)->left, indent + 2);
216 tre_do_print(stream, ((tre_catenation_t *)ast->obj)->right, indent + 2);
217 break;
218 default:
219 assert(0);
220 break;
221 }
222 }
223
224 static void
tre_ast_fprint(FILE * stream,tre_ast_node_t * ast)225 tre_ast_fprint(FILE *stream, tre_ast_node_t *ast)
226 {
227 tre_do_print(stream, ast, 0);
228 }
229
230 void
tre_ast_print(tre_ast_node_t * tree)231 tre_ast_print(tre_ast_node_t *tree)
232 {
233 printf("AST:\n");
234 tre_ast_fprint(stdout, tree);
235 }
236
237 #endif /* TRE_DEBUG */
238
239 /* EOF */
240