/* tree.c - parse trees for regexps
*
****************************************************************
* Copyright (C) 1998, 2000 Thomas Lord
*
* See the file "COPYING" for further information about
* the copyright and warranty status of this work.
*/
#include "hackerlab/bugs/panic.h"
#include "hackerlab/char/str.h"
#include "hackerlab/mem/mem.h"
#include "hackerlab/rx/nfa-cache.h"
#include "hackerlab/rx/tree.h"
static unsigned long exps_allocated = 0;
static unsigned long exps_freed = 0;
/****************************************************************
*(h0 "Regexp Expression Trees"
* :subtitle "rx/rexp.c"
* :includes ("rx/tree.h"))
*
*
* Every regexp has a natural representation as a syntax tree. The
* type `struct rx_exp_node' is used to represent one node of such a
* tree. Functions are provided that construct and manipulate
* expression trees representing regexps.
*
* Syntax trees can be constructed directly by programs as a way to
* specify a regexp and strings obeying standard regexp syntax can be
* parsed to produce syntax trees. Regexp parsing is explained in
* xref:"Regexp Parsing". The topic of this chapter is the output
* of parsing: the data structure used to represent a regexp syntax
* tree.
*
* Rx is able to compute some analytic (recursively defined)
* properties of regexp expression tree nodes. Therefore, the Rx
* representation of expression tree nodes contains some "extra"
* fields to hold that data.
*
* Rx is able to translate an expression tree into an NFA and
* indirectly into a DFA. The performance of this translation is
* commonly critical and is greatly improved by caching information
* in still more "extra" fields of expression nodes.
*/
/*(menu)
*/
/*(include-documentation "tree.h")
*/
/****************************************************************
*(h1 "Regexp Tree Allocation and Initialization")
*/
/*(c rx_exp_node)
* struct rx_exp_node * rx_exp_node (int type);
*
* Allocate a new expression node and initialize its type
* and reference count. The reference count is initialized to 1,
* the type to `type', and all other fields to 0.
*
* If the allocation fails, return 0.
*
*/
struct rx_exp_node *
rx_exp_node (enum rx_exp_node_type type)
{
struct rx_exp_node *n;
n = (struct rx_exp_node *) rx_nfa_cache_malloc (sizeof (*n));
if (!n)
return 0;
++exps_allocated;
mem_set0 ((char *)n, sizeof (*n));
n->type = type;
n->refs = 1;
return n;
}
/*(c rx_mk_r_cset)
* struct rx_exp_node * rx_mk_r_cset (enum rx_exp_node_type type,
* int size, bits b);
*
* Allocate a new character set expression node. The reference count
* is initialized to 1, the type to `type', the `cset' field to a
* newly allocated copy of `b', the `cset_size' field to `size', and
* all other fields to 0.
*
* If any allocation fails, return 0;
*
* `type' should be `r_cset'.
*/
struct rx_exp_node *
rx_mk_r_cset (enum rx_exp_node_type type, int size, bits b)
{
struct rx_exp_node * n;
if (type != r_cset)
panic ("unreasonable rexp node type in rx_mk_r_cset");
n = rx_exp_node (type);
if (!n)
return 0;
n->cset = bits_dup (b);
if (!n->cset)
{
rx_free_exp (n);
return 0;
}
n->cset_size = size;
return n;
}
/*(c rx_mk_r_cset_take)
* struct rx_exp_node * rx_mk_r_cset_take (enum rx_exp_node_type type,
* int size, bits b);
*
* Allocate a new character set expression node. The reference count
* is initialized to 1, the type to `type', the `cset' field to a
* newly allocated copy of `b', the `cset_size' field to `size', and
* all other fields to 0.
*
* If any allocation fails, return 0.
*
* `type' should be `r_cset'.
*/
struct rx_exp_node *
rx_mk_r_cset_take (enum rx_exp_node_type type, int size, bits b)
{
struct rx_exp_node * n;
if (type != r_cset)
panic ("unreasonable rexp node type in rx_mk_r_cset_take");
n = rx_exp_node (type);
if (!n)
return 0;
n->cset = b;
n->cset_size = size;
return n;
}
/*(c rx_mk_r_binop)
* struct rx_exp_node * rx_mk_r_binop (enum rx_exp_node_type type,
* struct rx_exp_node * a,
* struct rx_exp_node * b);
*
* Allocate a regexp expression node with two subexpressions. The
* reference count is initialized to 1, the type to `type', the `left'
* and `right' fields to `a' and `b', and all other fields to 0.
*
* If any allocation fails, return 0.
*
* The reference counts of `a' and `b' are not modified by this
* function -- the caller's reference count to those nodes is taken
* over by this function.
*
* `type' should be `r_concat' `r_right_concat' or `r_alternate'.
*/
struct rx_exp_node *
rx_mk_r_binop (enum rx_exp_node_type type,
struct rx_exp_node * a,
struct rx_exp_node * b)
{
struct rx_exp_node * n;
if ((type != r_concat) && (type != r_right_concat) && (type != r_alternate))
panic ("unreasonable rexp node type in rx_mk_r_binop");
n = rx_exp_node (type);
if (!n)
return 0;
n->left = a;
n->right = b;
return n;
}
/*(c rx_mk_r_monop)
* struct rx_exp_node * rx_mk_r_monop (enum rx_exp_node_type type,
* struct rx_exp_node * a);
*
* Allocate a regexp expression node with one subexpression. The
* reference count is initialized to 1, the type to `type', the `left'
* field to `a', and all other fields to 0.
*
* If any allocation fails, return 0.
*
* The reference count of `a' is not modified by this function -- the
* caller's reference count to that node is taken over by this
* function.
*
* `type' should be `r_star', `r_interval', `r_parens', or `r_context'.
*/
struct rx_exp_node *
rx_mk_r_monop (enum rx_exp_node_type type,
struct rx_exp_node * a)
{
struct rx_exp_node * n;
if ( (type != r_star)
&& (type != r_interval)
&& (type != r_parens)
&& (type != r_context))
panic ("unreasonable rexp node type in rx_mk_r_monop");
n = rx_exp_node (type);
if (!n)
return 0;
n->left = a;
n->right = 0;
return n;
}
/*(c rx_mk_r_str)
* 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);
*
* Allocate a regexp expression node whose parameter is a string. The
* reference count is initialized to 1, the type to `type', the `str'
* field to a newly allocated copy of the `len'-byte string `s', the
* `str_len' field is initialized to `len', and all other fields to 0.
*
* If any allocation fails, return 0.
*
* `type' should be `r_string'.
*/
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)
{
struct rx_exp_node *n;
if (type != r_string)
panic ("unreasonable rexp node type in rx_mk_r_str_c");
n = rx_exp_node (type);
if (!n)
return 0;
n->str = (t_uchar *)rx_nfa_cache_malloc (len);
if (len && !n->str)
{
rx_free_exp (n);
return 0;
}
mem_move (n->str, s, len);
n->str_len = len;
n->encoding = encoding;
return n;
}
/*(c rx_mk_r_int)
* struct rx_exp_node * rx_mk_r_int (enum rx_exp_node_type type,
* int intval);
*
* Allocate a regexp expression node whose parameter is an integer.
* The reference count is initialized to 1, the type to `type', the
* `intval' field is initialized to `intval', and all other fields to
* 0.
*
* If any allocation fails, return 0.
*
* `type' should be `r_cut', `r_parens', or `r_context'.
*/
struct rx_exp_node *
rx_mk_r_int (enum rx_exp_node_type type,
int intval)
{
struct rx_exp_node * n;
if ( (type != r_cut)
&& (type != r_parens)
&& (type != r_context))
panic ("unreasonable rexp node type in rx_mk_r_int");
n = rx_exp_node (type);
if (!n)
return 0;
n->intval = intval;
return n;
}
/*(c rx_mk_r_subexp_int)
* struct rx_exp_node * rx_mk_r_subexp_int (enum rx_exp_node_type type,
* struct rx_exp_node * subexp,
* int intval);
*
* Allocate a regexp expression node whose parameters are a
* subexpression and an integer. The reference count is initialized
* to 1, the type to `type', the `left' field is initialized to
* `subexp', the `intval' field is initialized to `intval', and all
* other fields to 0.
*
* The reference count of `subexp' is not modified by this function --
* the caller's reference count to that node is taken over by this
* function.
*
* If any allocation fails, return 0.
*
* `type' should be `r_parens'. `intval' is the subexpression number
* for this parenthesized expression (the number used for
* backreferences). If `intval' is 0, this is an anonymous
* subexpression (it can not be backreferenced).
*/
struct rx_exp_node *
rx_mk_r_subexp_int (enum rx_exp_node_type type,
struct rx_exp_node * subexp,
int intval)
{
struct rx_exp_node * n;
if (type != r_parens)
panic ("unreasonable rexp node type in rx_mk_r_subexp_int");
n = rx_exp_node (type);
if (!n)
return 0;
n->left = subexp;
n->intval = intval;
return n;
}
/*(c rx_mk_r_int2)
* struct rx_exp_node * rx_mk_r_int2 (enum rx_exp_node_type type,
* int intval,
* int intval2);
*
* Allocate a regexp expression node whose parameters are two
* integers. The reference count is initialized to 1, the type to
* `type', the `intval' and `intval2' fields are initialized to `intval' and `intval2', and all
* other fields to 0.
*
* If any allocation fails, return 0.
*
* `type' should be `r_interval'.
*/
struct rx_exp_node *
rx_mk_r_int2 (enum rx_exp_node_type type,
int intval,
int intval2)
{
struct rx_exp_node * n;
if (type != r_interval)
panic ("unreasonable rexp node type in rx_mk_r_int2");
n = rx_exp_node (type);
if (!n)
return 0;
n->intval = intval;
n->intval2 = intval2;
return n;
}
/*(c rx_mk_r_subexp_int2)
* struct rx_exp_node * rx_mk_r_subexp_int2 (enum rx_exp_node_type type,
* struct rx_exp_node * subexp,
* int intval,
* int intval2);
*
* Allocate a regexp expression node whose parameters are a
* subexpression and two integers. The reference count is initialized
* to 1, the type to `type', the `left' field is initialized to
* `subexp', the `intval' and `intval2' fields are initialized to
* `intval' and `intval2', and all other fields to 0.
*
* The reference count of `subexp' is not modified by this function --
* the caller's reference count to that node is taken over by this
* function.
*
* If any allocation fails, return 0.
*
* `type' should be `r_interval'. The two integer parameters are the
* lower and upper bound of the iteration.
*/
struct rx_exp_node *
rx_mk_r_subexp_int2 (enum rx_exp_node_type type,
struct rx_exp_node * subexp,
int intval,
int intval2)
{
struct rx_exp_node * n;
if (type != r_interval)
panic ("unreasonable rexp node type in rx_mk_r_int2");
n = rx_exp_node (type);
if (!n)
return 0;
n->left = subexp;
n->intval = intval;
n->intval2 = intval2;
return n;
}
/****************************************************************
*(h1 "Regexp Tree Reference Counting and Copying.")
*
*/
/*(c rx_save_exp)
* void rx_save_exp (struct rx_exp_node * node);
*
* Increment the reference count of `node'.
*/
void
rx_save_exp (struct rx_exp_node * node)
{
if (node)
++node->refs;
}
/*(c rx_free_exp)
* void rx_free_exp (struct rx_exp_node * node);
*
* Decrement the reference count of `node'. If it drops to 0, free
* the node, free all allocated data attached to it, and recursively
* `rx_free_exp' the sub-expressions of `node'.
*/
void
rx_free_exp (struct rx_exp_node * node)
{
if (node && !--node->refs)
{
if (node->cr)
{
node->next_same_nfa->prev_same_nfa = node->prev_same_nfa;
node->prev_same_nfa->next_same_nfa = node->next_same_nfa;
}
if (node->cset)
bits_free (node->cset);
if (node->str)
rx_nfa_cache_free (node->str);
rx_free_exp (node->left);
rx_free_exp (node->right);
rx_free_exp (node->simplified);
rx_nfa_cache_free ((char *)node);
++exps_freed;
/* safe_printfmt (1, "free %lx\n", (unsigned long)node); */
}
}
/****************************************************************
*(h1 "Regexp Tree Hashing and Equality")
*
*/
/*(c rx_exp_equal)
* int rx_exp_equal (struct rx_exp_node * a, struct rx_exp_node * b);
*
* Return 1 if two regexp expression trees are "equal", 0 otherwise.
*
* "Equal" means that the two trees have identical structure which is
* a sufficient but not necessary condition of the two patterns
* matching the same set of strings with identical results.
*/
int
rx_exp_equal (struct rx_exp_node * a, struct rx_exp_node * b)
{
int ret;
if (a == b)
return 1;
if ((a == 0) || (b == 0))
return 0;
if (a->type != b->type)
return 0;
switch (a->type)
{
case r_cset:
ret = ( (a->cset_size == b->cset_size)
&& bits_is_equal (a->cset, b->cset));
break;
case r_string:
ret = ( (a->str_len == b->str_len)
&& !str_cmp_n (a->str, a->str_len, b->str, a->str_len));
break;
case r_cut:
ret = (a->intval == b->intval);
break;
case r_concat:
case r_right_concat:
case r_alternate:
ret = ( rx_exp_equal (a->left, b->left)
&& rx_exp_equal (a->right, b->right));
break;
case r_star:
ret = rx_exp_equal (a->left, b->left);
break;
case r_interval:
ret = ( (a->intval == b->intval)
&& (a->intval2 == b->intval2)
&& rx_exp_equal (a->left, b->left));
break;
case r_parens:
ret = ( (a->intval == b->intval)
&& rx_exp_equal (a->left, b->left));
break;
case r_context:
ret = (a->intval == b->intval);
break;
default:
return 0;
}
return ret;
}
static unsigned long
exp_hash (struct rx_exp_node * node, unsigned long seed)
{
unsigned long contribution;
if (!node)
return seed;
/* This is just made up and should be checked out. */
contribution = ( node->type
^ str_hash_n (node->str, node->str_len)
^ ((seed << 3) + node->intval)
^ ((seed << 3) + node->intval2));
seed = contribution ^ (seed << 11) ^ (seed >> (8 * sizeof (seed) - 11));
seed = exp_hash (node->left, seed);
seed = exp_hash (node->right, seed);
return seed;
}
/*(c rx_exp_hash)
* unsigned long rx_exp_hash (struct rx_exp_node * node);
*
* Compute a word-sized hash value for an expression tree. Regexps
* which are equal (in the sense of `rx_exp_equal') have equal hash
* values (in the sense of `==').
*/
unsigned long
rx_exp_hash (struct rx_exp_node * node)
{
return exp_hash (node, 0);
}
syntax highlighted by Code2HTML, v. 0.9.1