home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / gnu / sed-2.05-src.lha / sed-2.05 / rx.h < prev    next >
C/C++ Source or Header  |  1994-05-13  |  33KB  |  1,054 lines
  1. #if !defined(RXH) || defined(RX_WANT_SE_DEFS)
  2. #define RXH
  3.  
  4. /*    Copyright (C) 1992, 1993 Free Software Foundation, Inc.
  5.  
  6. This program is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this software; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19. /*  t. lord    Wed Sep 23 18:20:57 1992    */
  20.  
  21.  
  22.  
  23.  
  24. #ifndef RX_WANT_SE_DEFS
  25.  
  26. /* This page: Bitsets */
  27.  
  28. #ifndef RX_subset
  29. typedef unsigned int RX_subset;
  30. #define RX_subset_bits    (32)
  31. #define RX_subset_mask    (RX_subset_bits - 1)
  32. #endif
  33.  
  34. typedef RX_subset * rx_Bitset;
  35.  
  36. #ifdef __STDC__
  37. typedef void (*rx_bitset_iterator) (void *, int member_index);
  38. #else
  39. typedef void (*rx_bitset_iterator) ();
  40. #endif
  41.  
  42. #define rx_bitset_subset(N)  ((N) / RX_subset_bits)
  43. #define rx_bitset_subset_val(B,N)  ((B)[rx_bitset_subset(N)])
  44. #define RX_bitset_access(B,N,OP) \
  45.   ((B)[rx_bitset_subset(N)] OP rx_subset_singletons[(N) & RX_subset_mask])
  46. #define RX_bitset_member(B,N)   RX_bitset_access(B, N, &)
  47. #define RX_bitset_enjoin(B,N)   RX_bitset_access(B, N, |=)
  48. #define RX_bitset_remove(B,N)   RX_bitset_access(B, N, &= ~)
  49. #define RX_bitset_toggle(B,N)   RX_bitset_access(B, N, ^= )
  50. #define rx_bitset_numb_subsets(N) (((N) + RX_subset_bits - 1) / RX_subset_bits)
  51. #define rx_sizeof_bitset(N)    (rx_bitset_numb_subsets(N) * sizeof(RX_subset))
  52.  
  53.  
  54.  
  55. /* This page: Splay trees. */
  56.  
  57. #ifdef __STDC__
  58. typedef int (*rx_sp_comparer) (void * a, void * b);
  59. #else
  60. typedef int (*rx_sp_comparer) ();
  61. #endif
  62.  
  63. struct rx_sp_node 
  64. {
  65.   void * key;
  66.   void * data;
  67.   struct rx_sp_node * kids[2];
  68. };
  69.  
  70. #ifdef __STDC__
  71. typedef void (*rx_sp_key_data_freer) (struct rx_sp_node *);
  72. #else
  73. typedef void (*rx_sp_key_data_freer) ();
  74. #endif
  75.  
  76.  
  77. /* giant inflatable hash trees */
  78.  
  79. struct rx_hash_item
  80. {
  81.   struct rx_hash_item * next_same_hash;
  82.   struct rx_hash * table;
  83.   unsigned long hash;
  84.   void * data;
  85.   void * binding;
  86. };
  87.  
  88. struct rx_hash
  89. {
  90.   struct rx_hash * parent;
  91.   int refs;
  92.   struct rx_hash * children[13];
  93.   struct rx_hash_item * buckets [13];
  94.   int bucket_size [13];
  95. };
  96.  
  97. struct rx_hash_rules;
  98.  
  99. #ifdef __STDC__
  100. /* should return like == */
  101. typedef int (*rx_hash_eq)(void *, void *);
  102. typedef struct rx_hash * (*rx_alloc_hash)(struct rx_hash_rules *);
  103. typedef void (*rx_free_hash)(struct rx_hash *,
  104.                 struct rx_hash_rules *);
  105. typedef struct rx_hash_item * (*rx_alloc_hash_item)(struct rx_hash_rules *,
  106.                             void *);
  107. typedef void (*rx_free_hash_item)(struct rx_hash_item *,
  108.                  struct rx_hash_rules *);
  109. #else
  110. typedef int (*rx_hash_eq)();
  111. typedef struct rx_hash * (*rx_alloc_hash)();
  112. typedef void (*rx_free_hash)();
  113. typedef struct rx_hash_item * (*rx_alloc_hash_item)();
  114. typedef void (*rx_free_hash_item)();
  115. #endif
  116.  
  117. struct rx_hash_rules
  118. {
  119.   rx_hash_eq eq;
  120.   rx_alloc_hash hash_alloc;
  121.   rx_free_hash free_hash;
  122.   rx_alloc_hash_item hash_item_alloc;
  123.   rx_free_hash_item free_hash_item;
  124. };
  125.  
  126.  
  127.  
  128. /* Matchers decide what to do by examining a series of these.
  129.  * Instruction types are described below.
  130.  */
  131. struct rx_inx 
  132. {
  133.   void * inx;
  134.   void * data;
  135.   void * data_2;
  136.   void * fnord;
  137. };
  138.  
  139. /* Struct RX holds a compiled regular expression - that is, an nfa ready to be
  140.  * converted on demand to a more efficient nfa.  This is for the low level interface.
  141.  * The high-level interface incloses this in a `struct re_pattern_buffer'.
  142.  */
  143. struct rx_cache;
  144. #ifdef __STDC__
  145. struct rx_se_list;
  146. struct rx;
  147. typedef int (*rx_se_list_order) (struct rx *,
  148.                  struct rx_se_list *, struct rx_se_list *);
  149. #else
  150. typedef int (*rx_se_list_order) ();
  151. #endif
  152.  
  153. struct rx_superset;
  154.  
  155. struct rx
  156. {
  157.   int rx_id;        /* Every edition numbered and signed by eclose_nfa. */
  158.  
  159.   struct rx_cache * cache;  /* Where superstates come from */
  160.  
  161.   /* Every regex defines the size of its own character set. */
  162.   int local_cset_size;
  163.  
  164.   void * buffer;        /* Malloced memory for the nfa. */
  165.   unsigned long allocated;    /* Size of that memory. */
  166.  
  167.   /* How much buffer space to save for external uses.  After compilation,
  168.    * this space will be available at (buffer + allocated - reserved)
  169.    */
  170.   unsigned long reserved;
  171.  
  172.   /* --------- The remaining fields are for internal use only. --------- */
  173.   /* --------- But! they should be initialized to 0.           --------- */
  174.   /* NODEC is the number of nodes in the NFA with non-epsilon
  175.    * orx transitions. 
  176.    */
  177.   int nodec;
  178.  
  179.   /* EPSNODEC is the number of nodes with only epsilon (orx) transitions. */
  180.   int epsnodec;
  181.  
  182.   /* The sum of NODEC & EPSNODEC is the total number of states in the
  183.    * compiled NFA.
  184.    */
  185.  
  186.   /* side_effect_progs temporarily holds a tree of side effect lists. */
  187.   struct rx_hash se_list_memo;
  188.  
  189.   /* A memo for sets of states in the possible_future lists of an nfa: */
  190.   struct rx_hash set_list_memo;
  191.  
  192.   /* The instruction table is indexed by the enum of instructions defined in 
  193.    * rxrun.h.  The values in the table are used to fill in the `inx'
  194.    * slot of instruction frames (see rxrun.h).
  195.    */
  196.   void ** instruction_table;
  197.   struct rx_nfa_state *nfa_states;
  198.   struct rx_nfa_state *start;
  199.  
  200.   /* This orders the search through super-nfa paths. */
  201.   rx_se_list_order se_list_cmp;
  202.  
  203.   struct rx_superset * start_set;
  204. };
  205.  
  206. /* An RX NFA may contain epsilon edges labeled with side effects.
  207.  * These side effects represent match actions that can not normally be
  208.  * defined in a `pure' NFA; for example, recording the location at
  209.  * which a paren is crossed in a register structure.  
  210.  *
  211.  * A matcher is supposed to find a particular path
  212.  * through the NFA (such as leftmost-longest), and then to execute the
  213.  * side effects along that path.  Operationally, the space of paths is
  214.  * searched and side effects are carried out incrementally, and with
  215.  * backtracking.
  216.  *
  217.  * As the NFA is manipulated during matching sets of side effects.
  218.  * Simple lists are used to hold side effect lists. 
  219.  */
  220.  
  221. typedef void * rx_side_effect;
  222.  
  223. struct rx_se_list
  224. {
  225.   rx_side_effect car;
  226.   struct rx_se_list * cdr;
  227. };
  228.  
  229.  
  230.  
  231. /* Struct rexp_node holds an expression tree that represents a regexp.
  232.  * In this expression tree, every node has a type, and some parameters
  233.  * appropriate to that type.
  234.  */
  235.  
  236. enum rexp_node_type
  237. {
  238.   r_cset,            /* Match from a character set. `a' or `[a-z]'*/
  239.   r_concat,            /* Concat two regexps.   `ab' */
  240.   r_alternate,            /* Choose one of two regexps. `a\|b' */
  241.   r_opt,            /* Optional regexp. `a?' */
  242.   r_star,            /* Repeated regexp. `a*' */
  243.   r_2phase_star,        /* hard to explain */
  244.   r_side_effect,        /* Matches the empty string, but
  245.                  * implies that a side effect must
  246.                  * take place.  These nodes are used
  247.                  * by the parser to implement parens,
  248.                  * backreferences etc.
  249.                  */
  250.  
  251.   r_data            /* R_DATA is soley for the convenience
  252.                  * of parsers or other rexp
  253.                  * transformers that want to
  254.                  * (temporarily) introduce new node
  255.                  * types in rexp structures.  These
  256.                  * must be eliminated
  257.                      * by the time build_nfa is called.
  258.                    */
  259. };
  260.  
  261. struct rexp_node
  262. {
  263.   enum rexp_node_type type;
  264.   union
  265.   {
  266.     rx_Bitset cset;
  267.     rx_side_effect side_effect;
  268.     struct
  269.       {
  270.     struct rexp_node *left;
  271.     struct rexp_node *right;
  272.       } pair;
  273.     void * data;
  274.   } params;
  275. };
  276.  
  277.  
  278.  
  279. /* This defines the structure of the NFA into which rexps are compiled. */
  280.  
  281. struct rx_nfa_state
  282. {
  283.   int id;        
  284.   struct rx_nfa_edge *edges;
  285.   struct rx_possible_future *futures;
  286.   unsigned int is_final:1;
  287.   unsigned int is_start:1;
  288.   unsigned int eclosure_needed:1;
  289.   struct rx_nfa_state *next;
  290.   unsigned int mark:1;
  291. };
  292.  
  293. enum rx_nfa_etype
  294. {
  295.   ne_cset,
  296.   ne_epsilon,
  297.   ne_side_effect        /* A special kind of epsilon. */
  298. };
  299.  
  300. struct rx_nfa_edge
  301. {
  302.   struct rx_nfa_edge *next;
  303.   enum rx_nfa_etype type;
  304.   struct rx_nfa_state *dest;
  305.   union
  306.   {
  307.     rx_Bitset cset;
  308.     rx_side_effect side_effect;
  309.   } params;
  310. };
  311.  
  312. struct rx_nfa_state_set
  313. {
  314.