/* tree.h - parse tree decls for regexps * **************************************************************** * Copyright (C) 1998, 2000 Thomas Lord * * See the file "COPYING" for further information about * the copyright and warranty status of this work. */ #ifndef INCLUDE__RX__TREE_H #define INCLUDE__RX__TREE_H #include "hackerlab/machine/types.h" #include "hackerlab/uni/coding.h" #include "hackerlab/bitsets/bits.h" #include "hackerlab/rx/bits-tree-rules.h" /*(h1 "The Expression Tree Structure") * */ /*(c #s"enum rx_exp_node_type" :category type) * enum rx_exp_node_type; * * Every expression node is tagged with a type that describes how * the node should be interpreted. * * The Rx representation of regexp expression trees contains a simple * optimization: a sub-tree which consists entirely of concatenations * of singleton character set nodes can be replaced by a single * node of type `r_string'. * * insert*/ #define RX_EXP_NODE_TYPES(FN) \ /* Match from a character set. `a' or `[a-z]' \ */ \ RX_EXP_NODE_TYPE_##FN(r_cset) \ \ /* Match two subexpressions in order. `ab' \ */ \ RX_EXP_NODE_TYPE_##FN(r_concat) \ \ /* Match two subexpressions in order. -no syntax- \ * However, maximize the length of the _right_ subexpression \ * not the _left_ subexpression. This is used to implement + \ * and {n,} \ */ \ RX_EXP_NODE_TYPE_##FN(r_right_concat) \ \ /* Choose one of two subexpressions. `a\|b' \ */ \ RX_EXP_NODE_TYPE_##FN(r_alternate) \ \ /* Match the subexpression any number of times. `a*' \ */ \ RX_EXP_NODE_TYPE_##FN(r_star) \ \ /* Shorthand for a concatenation of characters \ */ \ RX_EXP_NODE_TYPE_##FN(r_string) \ \ /* Generates a tagged, final nfa state. \ */ \ RX_EXP_NODE_TYPE_##FN(r_cut) \ \ /* Counted subexpression. `a{4, 1000}' \ */ \ RX_EXP_NODE_TYPE_##FN(r_interval) \ \ /* Parenthesized subexpression \ */ \ RX_EXP_NODE_TYPE_##FN(r_parens) \ \ /* Context-sensative operator such as "^" and "\1" \ */ \ RX_EXP_NODE_TYPE_##FN(r_context) #define RX_EXP_NODE_TYPE_ENUM(X) X, enum rx_exp_node_type { RX_EXP_NODE_TYPES(ENUM) }; /*end-insert */ /*(c #s"struct rx_exp_node" :category type) * struct rx_exp_node; * * This is the type of one node of a regexp expression tree. * insert*/ struct rx_exp_node { /* This is a reference counted structure type. * See `rx_save_exp' and `rx_free_exp'. */ int refs; /* The expression type of this node. */ enum rx_exp_node_type type; /* If the node is of type `r_cset', these describe the character set * matched. */ int cset_size; bits cset; /* If the node is of type `r_interval' ("a{x,y}"), then these * describe the range of the interval (`intval' is `x' and `intval2' * is `y'). * * If the node is of type `r_cut', `intval' is the state label * generated by the cut. * * If the node is of type `r_parens', `intval' is the expression * number (for backreferences and `pmatch' data from `regexec') or * 0, if the expression is an anonymous subexpression (formed by * `[[:(...):]]'.) * * If the node is of type `r_context', `invtval' is the context * operator. Valid operators are '$' and '^' (anchors), and '0' * .. '9' (backreferences). * */ long intval; long intval2; /* If the node is of type `r_concat', `r_right_concat' or * `r_alternate', these are the left and right children of * the node. * * If the node is of type `r_star', `r_interval' or `r_parens', then * `left' is the child of the node. */ struct rx_exp_node *left; struct rx_exp_node *right; /* If the node is of type `r_string', this is the contents of the * string. This string is not 0-terminated. */ t_uchar * str; size_t str_len; enum uni_encoding_scheme encoding; /* Intervals, parentheses and context operators are special because * they are not expressible as regular expressions. Also, any * composite expression with a subexpression which is not a regular * expression is itself not a regular expression. * * `rx_analyze_rexp' fills in this field with a non-zero value for * expression nodes which are "not a regular expression". * * If this field is not 0, a backtracking search may be necessay * when comparing this regexp to a string. */ int observed; /* If an `observed' regexp contains only parenthesized * subexpressions and no other non-regular-expression operators * (anchors or backreferences) then backtracking search is only * necessary if the caller of the regexp comparison function wants * to know the positions of matching subexpressions (the * `regmatch_t' data in Posix interfaces). If the caller only wants * to know the start and end positions of the overall match, and the * pattern contains no anchors or backreferences, then a DFA * (non-backtracking) algorithm can be used even if `observed' is * non-0. * * If `observed' is not 0, then `observation_contingent' is * useful. If `observation_contingent' is 1, the pattern * contains no anchors or backreferences implying that a fast * DFA search may be possible. */ int observation_contingent; /* We have two strategies available for matching: * * the NFA technique: potentially slow, but space efficient. * the NFA->DFA technique: more reliable throughput but higher * latency; much less space efficient. * * `small_advised_p' is set to a non-0 value by `rx_analyze_rexp' if * it seems that the NFA technique will not be too slow. */ int small_advised_p; /* Some expressions match only strings of one particular length. * Knowing that length, if it is defined, leads to some easy and * rewarding optimizations. * * `rx_analyze_rexp' fills in this field with that length, or -1 if * no such length can be computed for this expression. */ long len; /* In the tree rooted at this node, what is the maximum and * minimum subexpression number of an enclosed subexpression. * * This is needed during matching when matching a parenthesized * subexpression. For trees with no numbered subexpressions, * these values are 0. */ int max_enclosed_paren; int min_enclosed_paren; /* These fields are used to cache results computed by * `rx_simplify_rexp' and `rx_unfa'. */ struct rx_exp_node * simplified; struct rx_cached_rexp * cr; struct rx_exp_node * next_same_nfa; struct rx_exp_node * prev_same_nfa; }; /*end-insert */ /* automatically generated __STDC__ prototypes */ extern struct rx_exp_node * rx_exp_node (enum rx_exp_node_type type); extern struct rx_exp_node * rx_mk_r_cset (enum rx_exp_node_type type, int size, bits b); extern struct rx_exp_node * rx_mk_r_cset_take (enum rx_exp_node_type type, int size, bits b); extern struct rx_exp_node * rx_mk_r_binop (enum rx_exp_node_type type, struct rx_exp_node * a, struct rx_exp_node * b); extern struct rx_exp_node * rx_mk_r_monop (enum rx_exp_node_type type, struct rx_exp_node * a); extern struct rx_exp_node * rx_mk_r_str (enum rx_exp_node_type type, const t_uchar * s, size_t len, enum uni_encoding_scheme encoding); extern struct rx_exp_node * rx_mk_r_int (enum rx_exp_node_type type, int intval); extern struct rx_exp_node * rx_mk_r_subexp_int (enum rx_exp_node_type type, struct rx_exp_node * subexp, int intval); extern struct rx_exp_node * rx_mk_r_int2 (enum rx_exp_node_type type, int intval, int intval2); extern struct rx_exp_node * rx_mk_r_subexp_int2 (enum rx_exp_node_type type, struct rx_exp_node * subexp, int intval, int intval2); extern void rx_save_exp (struct rx_exp_node * node); extern void rx_free_exp (struct rx_exp_node * node); extern int rx_exp_equal (struct rx_exp_node * a, struct rx_exp_node * b); extern unsigned long rx_exp_hash (struct rx_exp_node * node); #endif /* INCLUDE__RX__TREE_H */