/* 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 */
syntax highlighted by Code2HTML, v. 0.9.1