/* 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 */
