regex/TRE/lib/tre-ast.h

   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. */
  21 typedef 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. */
  47 typedef 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. */
  68 typedef 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). */
  82 typedef 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. */
  89 typedef 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. */
 105 typedef 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 *
 114 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size);
 115
 116 __private_extern__ tre_ast_node_t *
 117 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position);
 118
 119 __private_extern__ tre_ast_node_t *
 120 tre_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 *
 124 tre_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 *
 127 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
 128                        tre_ast_node_t *right);
 129
 130 #ifdef TRE_DEBUG
 131 void
 132 tre_ast_print(tre_ast_node_t *tree);
 133
 134 /* XXX - rethink AST printing API */
 135 void
 136 tre_print_params(int *params);
 137 #endif /* TRE_DEBUG */
 138
 139 #endif /* TRE_AST_H */
 140
 141 /* EOF */