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 */ 227