1/* 2 tre-ast.h - Abstract syntax tree (AST) definitions 3 4 This software is released under a BSD-style license. 5 See the file LICENSE for details and copyright. 6 7*/ 8 9 10#ifndef TRE_AST_H 11#define TRE_AST_H 1 12 13#include <limits.h> 14 15#include "tre-mem.h" 16#include "tre-internal.h" 17#include "tre-compile.h" 18#include "tre-last-matched.h" 19 20/* The different AST node types. */ 21typedef enum { 22 LITERAL, 23 CATENATION, 24 ITERATION, 25 UNION 26} tre_ast_type_t; 27 28/* Special subtypes of TRE_LITERAL. */ 29#define EMPTY -1 /* Empty leaf (denotes empty string). */ 30#define ASSERTION -2 /* Assertion leaf. */ 31#define TAG -3 /* Tag leaf. */ 32#define BACKREF -4 /* Back reference leaf. */ 33#define PARAMETER -5 /* Parameter. */ 34 35#define IS_SPECIAL(x) ((x)->code_min < 0) 36#define IS_EMPTY(x) ((x)->code_min == EMPTY) 37#define IS_ASSERTION(x) ((x)->code_min == ASSERTION) 38#define IS_TAG(x) ((x)->code_min == TAG) 39#define IS_BACKREF(x) ((x)->code_min == BACKREF) 40#define IS_PARAMETER(x) ((x)->code_min == PARAMETER) 41 42#define SUBMATCH_ID_INVISIBLE_START (INT_MAX / 2 + 1) 43 44 45/* A generic AST node. All AST nodes consist of this node on the top 46 level with `obj' pointing to the actual content. */ 47typedef struct _tre_ast_node { 48 void *obj; /* Pointer to actual node. */ 49 tre_last_matched_branch_pre_t *last_matched_branch; 50 tre_last_matched_pre_t *last_matched_in_progress; 51 tre_pos_and_tags_t *firstpos; 52 tre_pos_and_tags_t *lastpos; 53 /* The original pointer is used to point to the original node, when a 54 * CATENATION and tag are added. If NULL, this is node is the original */ 55 struct _tre_ast_node *original; 56 tre_ast_type_t type; /* Type of the node. */ 57 int submatch_id; 58 int num_submatches; 59 int num_tags; 60 short nullable; 61 short make_branches; 62} tre_ast_node_t; 63 64 65/* A "literal" node. These are created for assertions, back references, 66 tags, matching parameter settings, and all expressions that match one 67 character. */ 68typedef struct { 69 tre_cint_t code_min; 70 tre_cint_t code_max; 71 int position; 72 union { 73 tre_bracket_match_list_t *bracket_match_list; 74 int *params; 75 } u; 76} tre_literal_t; 77 78/* A "catenation" node. These are created when two regexps are concatenated. 79 If there are more than one subexpressions in sequence, the `left' part 80 holds all but the last, and `right' part holds the last subexpression 81 (catenation is left associative). */ 82typedef struct { 83 tre_ast_node_t *left; 84 tre_ast_node_t *right; 85} tre_catenation_t; 86 87/* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}" 88 operators. */ 89typedef struct { 90 /* Subexpression to match. */ 91 tre_ast_node_t *arg; 92 /* Minimum number of consecutive matches. */ 93 int min; 94 /* Maximum number of consecutive matches. */ 95 int max; 96 /* If 0, match as many characters as possible, if 1 match as few as 97 possible. Note that this does not always mean the same thing as 98 matching as many/few repetitions as possible. */ 99 unsigned int minimal:1; 100 /* Approximate matching parameters (or NULL). */ 101 int *params; 102} tre_iteration_t; 103 104/* An "union" node. These are created for the "|" operator. */ 105typedef struct { 106 tre_ast_node_t *left; 107 tre_ast_node_t *right; 108 /* The left end right end tags if non-zero */ 109 int left_tag; 110 int right_tag; 111} tre_union_t; 112 113__private_extern__ tre_ast_node_t * 114tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size); 115 116__private_extern__ tre_ast_node_t * 117tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position); 118 119__private_extern__ tre_ast_node_t * 120tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, 121 int minimal); 122 123__private_extern__ tre_ast_node_t * 124tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right); 125 126__private_extern__ tre_ast_node_t * 127tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, 128 tre_ast_node_t *right); 129 130#ifdef TRE_DEBUG 131void 132tre_ast_print(tre_ast_node_t *tree); 133 134/* XXX - rethink AST printing API */ 135void 136tre_print_params(int *params); 137#endif /* TRE_DEBUG */ 138 139#endif /* TRE_AST_H */ 140 141/* EOF */ 142