home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxsuper.h < prev    next >
C/C++ Source or Header  |  1995-12-31  |  16KB  |  448 lines
  1. /* classes: h_files */
  2.  
  3. #ifndef RXSUPERH
  4. #define RXSUPERH
  5.  
  6. /***********************************************************
  7.  
  8. Copyright 1995 by Tom Lord
  9.  
  10.                         All Rights Reserved
  11.  
  12. Permission to use, copy, modify, and distribute this software and its 
  13. documentation for any purpose and without fee is hereby granted, 
  14. provided that the above copyright notice appear in all copies and that
  15. both that copyright notice and this permission notice appear in 
  16. supporting documentation, and that the name of the copyright holder not be
  17. used in advertising or publicity pertaining to distribution of the
  18. software without specific, written prior permission.  
  19.  
  20. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  21. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  22. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  23. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  24. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  25. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  26. PERFORMANCE OF THIS SOFTWARE.
  27.  
  28. ******************************************************************/
  29.  
  30. /*  lord    Sun May  7 12:40:17 1995    */
  31.  
  32.  
  33.  
  34. #include "rxnfa.h"
  35.  
  36.  
  37.  
  38. /* This begins the description of the superstate NFA.
  39.  *
  40.  * The superstate NFA corresponds to the NFA in these ways:
  41.  *
  42.  * Superstate states correspond to sets of NFA states (nfa_states(SUPER)),
  43.  *
  44.  * Superstate edges correspond to NFA paths.
  45.  *
  46.  * The superstate has no epsilon transitions;
  47.  * every edge has a character label, and a (possibly empty) side
  48.  * effect label.   The side effect label corresponds to a list of
  49.  * side effects that occur in the NFA.  These parts are referred
  50.  * to as:   superedge_character(EDGE) and superedge_sides(EDGE).
  51.  *
  52.  * For a superstate edge EDGE starting in some superstate SUPER,
  53.  * the following is true (in pseudo-notation :-):
  54.  *
  55.  *       exists DEST in nfa_states s.t. 
  56.  *         exists nfaEDGE in nfa_edges s.t.
  57.  *                 origin (nfaEDGE) == DEST
  58.  *              && origin (nfaEDGE) is a member of nfa_states(SUPER)
  59.  *              && exists PF in possible_futures(dest(nfaEDGE)) s.t.
  60.  *                     sides_of_possible_future (PF) == superedge_sides (EDGE)
  61.  *
  62.  * also:
  63.  *
  64.  *      let SUPER2 := superedge_destination(EDGE)
  65.  *          nfa_states(SUPER2)
  66.  *           == union of all nfa state sets S s.t.
  67.  *                          exists PF in possible_futures(dest(nfaEDGE)) s.t.
  68.  *                            sides_of_possible_future (PF) == superedge_sides (EDGE)
  69.  *                          && S == dests_of_possible_future (PF) }
  70.  *
  71.  * Or in english, every superstate is a set of nfa states.  A given
  72.  * character and a superstate implies many transitions in the NFA --
  73.  * those that begin with an edge labeled with that character from a
  74.  * state in the set corresponding to the superstate.
  75.  * 
  76.  * The destinations of those transitions each have a set of possible
  77.  * futures.  A possible future is a list of side effects and a set of
  78.  * destination NFA states.  Two sets of possible futures can be
  79.  * `merged' by combining all pairs of possible futures that have the
  80.  * same side effects.  A pair is combined by creating a new future
  81.  * with the same side effect but the union of the two destination sets.
  82.  * In this way, all the possible futures suggested by a superstate
  83.  * and a character can be merged into a set of possible futures where
  84.  * no two elements of the set have the same set of side effects.
  85.  *
  86.  * The destination of a possible future, being a set of NFA states, 
  87.  * corresponds to a supernfa state.  So, the merged set of possible
  88.  * futures we just created can serve as a set of edges in the
  89.  * supernfa.
  90.  *
  91.  * The representation of the superstate nfa and the nfa is critical.
  92.  * The nfa has to be compact, but has to facilitate the rapid
  93.  * computation of missing superstates.  The superstate nfa has to 
  94.  * be fast to interpret, lazilly constructed, and bounded in space.
  95.  *
  96.  * To facilitate interpretation, the superstate data structures are 
  97.  * peppered with `instruction frames'.  There is an instruction set
  98.  * defined below which matchers using the supernfa must be able to
  99.  * interpret.
  100.  *
  101.  * We'd like to make it possible but not mandatory to use code
  102.  * addresses to represent instructions (c.f. gcc's computed goto).
  103.  * Therefore, we define an enumerated type of opcodes, and when
  104.  * writing one of these instructions into a data structure, use
  105.  * the opcode as an index into a table of instruction values.
  106.  * 
  107.  * Below are the opcodes that occur in the superstate nfa.
  108.  *
  109.  * The descriptions of the opcodes refer to data structures that are
  110.  * described further below. 
  111.  */
  112.  
  113. enum rx_opcode
  114. {
  115.   /* 
  116.    * BACKTRACK_POINT is invoked when a character transition in 
  117.    * a superstate leads to more than one edge.  In that case,
  118.    * the edges have to be explored independently using a backtracking
  119.    * strategy.
  120.    *
  121.    * A BACKTRACK_POINT instruction is stored in a superstate's 
  122.    * transition table for some character when it is known that that
  123.    * character crosses more than one edge.  On encountering this
  124.    * instruction, the matcher saves enough state to backtrack to this
  125.    * point later in the match.
  126.    */
  127.   rx_backtrack_point = 0,    /* data is (struct transition_class *) */
  128.  
  129.   /* 
  130.    * RX_DO_SIDE_EFFECTS evaluates the side effects of an epsilon path.
  131.    * There is one occurence of this instruction per rx_distinct_future.
  132.    * This instruction is skipped if a rx_distinct_future has no side effects.
  133.    */
  134.   rx_do_side_effects = rx_backtrack_point + 1,
  135.  
  136.   /* data is (struct rx_distinct_future *) */
  137.  
  138.   /* 
  139.    * RX_CACHE_MISS instructions are stored in rx_distinct_futures whose
  140.    * destination superstate has been reclaimed (or was never built).
  141.    * It recomputes the destination superstate.
  142.    * RX_CACHE_MISS is also stored in a superstate transition table before
  143.    * any of its edges have been built.
  144.    */
  145.   rx_cache_miss = rx_do_side_effects + 1,
  146.   /* data is (struct rx_distinct_future *) */
  147.  
  148.   /* 
  149.    * RX_NEXT_CHAR is called to consume the next character and take the
  150.    * corresponding transition.  This is the only instruction that uses 
  151.    * the DATA field of the instruction frame instead of DATA_2.
  152.    * The comments about rx_inx explain this further.
  153.    */
  154.   rx_next_char = rx_cache_miss + 1, /* data is (struct superstate *) */
  155.  
  156.   /* RX_BACKTRACK indicates that a transition fails.  Don't
  157.    * confuse this with rx_backtrack_point.
  158.    */
  159.   rx_backtrack = rx_next_char + 1, /* no data */
  160.  
  161.   /* 
  162.    * RX_ERROR_INX is stored only in places that should never be executed.
  163.    */
  164.   rx_error_inx = rx_backtrack + 1, /* Not supposed to occur. */
  165.  
  166.   rx_num_instructions = rx_error_inx + 1
  167. };
  168.  
  169. /* The heart of the matcher is a `word-code-interpreter' 
  170.  * (like a byte-code interpreter, except that instructions
  171.  * are a full word wide).
  172.  *
  173.  * Instructions are not stored in a vector of code, instead,
  174.  * they are scattered throughout the data structures built
  175.  * by the regexp compiler and the matcher.  One word-code instruction,
  176.  * together with the arguments to that instruction, constitute
  177.  * an instruction frame (struct rx_inx).
  178.  *
  179.  * This structure type is padded by hand to a power of 2 because
  180.  * in one of the dominant cases, we dispatch by indexing a table
  181.  * of instruction frames.  If that indexing can be accomplished
  182.  * by just a shift of the index, we're happy.
  183.  *
  184.  * Instructions take at most one argument, but there are two
  185.  * slots in an instruction frame that might hold that argument.
  186.  * These are called data and data_2.  The data slot is only
  187.  * used for one instruction (RX_NEXT_CHAR).  For all other 
  188.  * instructions, data should be set to 0.
  189.  *
  190.  * RX_NEXT_CHAR is the most important instruction by far.
  191.  * By reserving the data field for its exclusive use, 
  192.  * instruction dispatch is sped up in that case.  There is
  193.  * no need to fetch both the instruction and the data,
  194.  * only the data is needed.  In other words, a `cycle' begins
  195.  * by fetching the field data.  If that is non-0, then it must
  196.  * be the destination state of a next_char transition, so
  197.  * make that value the current state, advance the match position
  198.  * by one character, and start a new cycle.  On the other hand,
  199.  * if data is 0, fetch the instruction and do a more complicated
  200.  * dispatch on that.
  201.  */
  202.  
  203. struct rx_inx 
  204. {
  205.   void * data;
  206.   void * data_2;
  207.   void * inx;
  208.   void * fnord;
  209. };
  210.  
  211. #ifndef RX_TAIL_ARRAY
  212. #define RX_TAIL_ARRAY  1
  213. #endif
  214.  
  215. /* A superstate corresponds to a set of nfa states.  Those sets are
  216.  * represented by STRUCT RX_SUPERSET.  The constructors
  217.  * guarantee that only one (shared) structure is created for a given set.
  218.  */
  219. struct rx_superset
  220. {
  221.   int is_final;
  222.   int refs;            /* This is a reference counted structure. */
  223.  
  224.   /* We keep these sets in a cache because (in an unpredictable way),
  225.    * the same set is often created again and again.  But that is also
  226.    * problematic -- compatibility with POSIX and GNU regex requires
  227.    * that we not be able to tell when a program discards a particular
  228.    * NFA (thus invalidating the supersets created from it).
  229.    *
  230.    * But when a cache hit appears to occur, we will have in hand the
  231.    * nfa for which it may have happened.  That is why every nfa is given
  232.    * its own sequence number.  On a cache hit, the cache is validated
  233.    * by comparing the nfa sequence number to this field:
  234.    */
  235.   int id;
  236.  
  237.   struct rx_nfa_state * car;    /* May or may not be a valid addr. */
  238.   struct rx_superset * cdr;
  239.  
  240.   /* If the corresponding superstate exists: */
  241.   struct rx_superstate * superstate;
  242.  
  243.  
  244.   /* There is another bookkeeping problem.  It is expensive to 
  245.    * compute the starting nfa state set for an nfa.  So, once computed,
  246.    * it is cached in the `struct rx'.
  247.    *
  248.    * But, the state set can be flushed from the superstate cache.
  249.    * When that happens, we can't know if the corresponding `struct rx'
  250.    * is still alive or if it has been freed or re-used by the program.
  251.    * So, the cached pointer to this set in a struct rx might be invalid
  252.    * and we need a way to validate it.
  253.    *
  254.    * Fortunately, even if this set is flushed from the cache, it is
  255.    * not freed.  It just goes on the free-list of supersets.
  256.    * So we can still examine it.  
  257.    *
  258.    * So to validate a starting set memo, check to see if the
  259.    * starts_for field still points back to the struct rx in question,
  260.    * and if the ID matches the rx sequence number.
  261.    */
  262.   struct rx * starts_for;
  263.  
  264.   /* This is used to link into a hash bucket so these objects can
  265.    * be `hash-consed'.
  266.    */
  267.   struct rx_hash_item hash_item;
  268. };
  269.  
  270. #define rx_protect_superset(RX,CON) (++(CON)->refs)
  271.  
  272. /* The terminology may be confusing (rename this structure?).
  273.  * Every character occurs in at most one rx_super_edge per super-state.
  274.  * But, that structure might have more than one option, indicating a point
  275.  * of non-determinism. 
  276.  *
  277.  * In other words, this structure holds a list of superstate edges
  278.  * sharing a common starting state and character label.  The edges
  279.  * are in the field OPTIONS.  All superstate edges sharing the same
  280.  * starting state and character are in this list.
  281.  */
  282. struct rx_super_edge
  283. {
  284.   struct rx_super_edge *next;
  285.   struct rx_inx rx_backtrack_frame;
  286.   int cset_size;
  287.   rx_Bitset cset;
  288.   struct rx_distinct_future *options;
  289. };
  290.  
  291. /* A superstate is a set of nfa states (RX_SUPERSET) along
  292.  * with a transition table.  Superstates are built on demand and reclaimed
  293.  * without warning.  To protect a superstate from this ghastly fate,
  294.  * use LOCK_SUPERSTATE. 
  295.  */
  296. struct rx_superstate
  297. {
  298.   int rx_id;            /* c.f. the id field of rx_superset */
  299.   int locks;            /* protection from reclamation */
  300.  
  301.   /* Within a superstate cache, all the superstates are kept in a big
  302.    * queue.  The tail of the queue is the state most likely to be
  303.    * reclaimed.  The *recyclable fields hold the queue position of 
  304.    * this state.
  305.    */
  306.   struct rx_superstate * next_recyclable;
  307.   struct rx_superstate * prev_recyclable;
  308.  
  309.   /* The supernfa edges that exist in the cache and that have
  310.    * this state as their destination are kept in this list:
  311.    */
  312.   struct rx_distinct_future * transition_refs;
  313.  
  314.   /* The list of nfa states corresponding to this superstate: */
  315.   struct rx_superset * contents;
  316.  
  317.   /* The list of edges in the cache beginning from this state. */
  318.   struct rx_super_edge * edges;
  319.  
  320.   /* A tail of the recyclable queue is marked as semifree.  A semifree
  321.    * state has no incoming next_char transitions -- any transition
  322.    * into a semifree state causes a complex dispatch with the side
  323.    * effect of rescuing the state from its semifree state into a 
  324.    * fully free state at the head of the queue.
  325.    *
  326.    * An alternative to this might be to make next_char more expensive,
  327.    * and to move a state to the head of the recyclable queue whenever
  328.    * it is entered.  That way, popular states would never be recycled.
  329.    *
  330.    * But unilaterally making next_char more expensive actually loses.
  331.    * So, incoming transitions are only made expensive for states near
  332.    * the tail of the recyclable queue.  The more cache contention
  333.    * there is, the more frequently a state will have to prove itself
  334.    * and be moved back to the front of the queue.  If there is less 
  335.    * contention, then popular states just aggregate in the front of 
  336.    * the queue and stay there.
  337.    */
  338.   int is_semifree;
  339.  
  340.  
  341.   /* This keeps track of the size of the transition table for this
  342.    * state.  There is a half-hearted attempt to support variable sized
  343.    * superstates.
  344.    */
  345.   int trans_size;
  346.  
  347.   /* Indexed by characters... */
  348.   struct rx_inx transitions[RX_TAIL_ARRAY];
  349. };
  350.  
  351.  
  352. /* A list of distinct futures define the edges that leave from a 
  353.  * given superstate on a given character.  c.f. rx_super_edge.
  354.  */
  355. struct rx_distinct_future
  356. {
  357.   struct rx_distinct_future * next_same_super_edge[2];
  358.   struct rx_distinct_future * next_same_dest;
  359.   struct rx_distinct_future * prev_same_dest;
  360.   struct rx_superstate * present;    /* source state */
  361.   struct rx_superstate * future;    /* destination state */
  362.   struct rx_super_edge * edge;
  363.  
  364.  
  365.   /* The future_frame holds the instruction that should be executed
  366.    * after all the side effects are done, when it is time to complete
  367.    * the transition to the next state.
  368.    *
  369.    * Normally this is a next_char instruction, but it may be a
  370.    * cache_miss instruction as well, depending on whether or not
  371.    * the superstate is in the cache and semifree.
  372.    * 
  373.    * If this is the only future for a given superstate/char, and
  374.    * if there are no side effects to be performed, this frame is
  375.    * not used (directly) at all.  Instead, its contents are copied
  376.    * into the transition table of the starting state of this dist. future
  377.    * (a sort of goto elimination).
  378.    */
  379.   struct rx_inx future_frame;
  380.  
  381.   struct rx_inx side_effects_frame;
  382.   struct rx_se_list * effects;
  383. };
  384.  
  385. #define rx_lock_superstate(R,S)  ((S)->locks++)
  386. #define rx_unlock_superstate(R,S) (--(S)->locks)
  387.  
  388.  
  389. struct rx_cache;
  390.  
  391. #ifdef __STDC__
  392. typedef void (*rx_morecore_fn)(struct rx_cache *);
  393. #else
  394. typedef void (*rx_morecore_fn)();
  395. #endif
  396.  
  397. struct rx_cache
  398. {
  399.   struct rx_hash_rules superset_hash_rules;
  400.  
  401.   struct rx_superstate * lru_superstate;
  402.   struct rx_superstate * semifree_superstate;
  403.  
  404.   struct rx_superset * empty_superset;
  405.  
  406.   int superstates;
  407.   int semifree_superstates;
  408.   int hits;
  409.   int misses;
  410.  
  411.   int bytes_allowed;
  412.   int bytes_used;
  413.  
  414.   int local_cset_size;
  415.   void ** instruction_table;
  416.  
  417.   struct rx_hash superset_table;
  418. };
  419.  
  420. extern struct rx_cache * rx_default_cache;
  421.  
  422.  
  423. #ifdef __STDC__
  424. extern void rx_release_superset (struct rx *rx,
  425.                  struct rx_superset *set);
  426. extern struct rx_superset * rx_superset_cons (struct rx * rx,
  427.                           struct rx_nfa_state *car, struct rx_superset *cdr);
  428. extern struct rx_superset * rx_superstate_eclosure_union
  429. (struct rx * rx, struct rx_superset *set, struct rx_nfa_state_set *ecl) ;
  430. extern struct rx_superstate * rx_superstate (struct rx *rx,
  431.                          struct rx_superset *set);
  432. extern struct rx_inx * rx_handle_cache_miss
  433. (struct rx *rx, struct rx_superstate *super, unsigned char chr, void *data) ;
  434.  
  435. #else /* STDC */
  436. extern void rx_release_superset ();
  437. extern struct rx_superset * rx_superset_cons ();
  438. extern struct rx_superset * rx_superstate_eclosure_union
  439. extern struct rx_superstate * rx_superstate ();
  440. extern struct rx_inx * rx_handle_cache_miss
  441.  
  442. #endif /* STDC */
  443.  
  444.  
  445.  
  446.  
  447. #endif  /* RXSUPERH */
  448.