home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / librx / !librx / DOC < prev   
Encoding:
Text File  |  1995-03-21  |  6.6 KB  |  180 lines
  1. Most of the interfaces are covered by the documentation for GNU regex.
  2.  
  3. This file will accumulate factoids about other interfaces until
  4. somebody writes a manual.
  5.  
  6.  
  7. * Don't Pass Registers Gratuitously
  8.  
  9. Search and match functions take an optional parameter which is a
  10. pointer to "registers" or "match positions".  This parameter points
  11. to a structure which during the match is filled in with the offset locations
  12. of parenthesized subexpressions.
  13.  
  14. Unless you specificly need the values that would be stored in that
  15. structure, you should pass NULL for this parameter.  Usually Rx will
  16. do less backtracking (and so run much faster) if subexpression
  17. positions are not being measured.
  18.  
  19.  
  20. * Use syntax_parens
  21.  
  22. Sometimes you need to know the positions of *some* parenthesized
  23. subexpressions, but not others.  You can still help Rx to avoid 
  24. backtracking by telling it specificly which subexpressions you are interested
  25. in.  You do this by filling in the rxb.syntax_parens field of
  26. a pattern buffer.
  27.  
  28.   /* If this is a valid pointer, it tells rx not to store the extents of 
  29.    * certain subexpressions (those corresponding to non-zero entries).
  30.    * Passing 0x1 is the same as passing an array of all ones.  Passing 0x0
  31.    * is the same as passing an array of all zeros.
  32.    * The array should contain as many entries as their are subexps in the 
  33.    * regexp.
  34.    */
  35.   char * syntax_parens;
  36.  
  37.  
  38. * RX_SEARCH
  39.  
  40. For an example of how to use rx_search, you can look at how
  41. re_search_2 is defined (in rx.c).  Basicly you need to define three
  42. functions.  These are GET_BURST, FETCH_CHAR, and BACK_REF.  They each
  43. operate on `struct rx_string_position' and a closure of your design
  44. passed as void *.
  45.  
  46.     struct rx_string_position
  47.     {
  48.       const unsigned char * pos;    /* The current pos. */
  49.       const unsigned char * string;     /* The current string burst. */
  50.       const unsigned char * end;    /* First invalid position >= POS. */
  51.       int offset;            /* Integer address of  current burst */
  52.       int size;                /* Current string's size. */
  53.       int search_direction;        /* 1 or -1 */
  54.       int search_end;            /* First position to not try. */
  55.     };
  56.  
  57. On entry to GET_BURST, all these fields are set, but POS may be >=
  58. END.  In fact, STRING and END might both be 0.
  59.  
  60. The function of GET_BURST is to make all the fields valid without
  61. changing the logical position in the string.  SEARCH_DIRECTION is a
  62. hint about which way the matcher will move next.  It is usually 1, and
  63. is -1 only when fastmapping during a reverse search.  SEARCH_END
  64. terminates the burst.
  65.  
  66.     typedef enum rx_get_burst_return
  67.       (*rx_get_burst_fn) (struct rx_string_position * pos,
  68.                   void * app_closure,
  69.                   int stop);
  70.                            
  71.  
  72. The closure is whatever you pass to rx_search.  STOP is an argument to
  73. rx_search that bounds the search.  You should never return a string
  74. position from with SEARCH_END set beyond the position indicated by
  75. STOP.
  76.  
  77.  
  78.     enum rx_get_burst_return
  79.     {
  80.       rx_get_burst_continuation,
  81.       rx_get_burst_error,
  82.       rx_get_burst_ok,
  83.       rx_get_burst_no_more
  84.     };
  85.  
  86. Those are the possible return values of get_burst.  Normally, you only
  87. ever care about the last two.  An error return indicates something
  88. like trouble reading a file.  A continuation return means suspend the
  89. search and resume by retrying GET_BURST if the search is restarted.
  90.  
  91. GET_BURST is not quite as trivial as you might hope.  If you have a
  92. fragmented string, you really have to keep two adjacent fragments at
  93. all times, even though the GET_BURST interface looks like you only
  94. need one.  This is because of operators like `word-boundary' that try
  95. to look at two adjacent characters.  Such operators are implemented
  96. with FETCH_CHAR.
  97.  
  98.     typedef int (*rx_fetch_char_fn) (struct rx_string_position * pos,
  99.                      int offset,
  100.                      void * app_closure,
  101.                      int stop);
  102.  
  103. That takes the same closure passed to GET_BURST.  It returns the
  104. character at POS or at one past POS according to whether OFFSET is 0
  105. or 1. 
  106.  
  107. It is guaranteed that POS + OFFSET is within the string being searched.
  108.  
  109.  
  110.  
  111. The last function compares characters at one position with characters
  112. previously matched by a parenthesized subexpression.
  113.  
  114.     enum rx_back_check_return
  115.     {
  116.       rx_back_check_continuation,
  117.       rx_back_check_error,
  118.       rx_back_check_pass,
  119.       rx_back_check_fail
  120.     };
  121.     
  122.     typedef enum rx_back_check_return
  123.       (*rx_back_check_fn) (struct rx_string_position * pos,
  124.                    int lparen,
  125.                    int rparen,
  126.                    unsigned char * translate,
  127.                    void * app_closure,
  128.                    int stop);
  129.                            
  130. LPAREN and RPAREN are the integer indexes of the previously matched
  131. characters.  The comparison should translate both characters being
  132. compared by mapping them through TRANSLATE.  POS is the point at which
  133. to begin comparing.  It should be advanced to the last character
  134. matched during backreferencing.
  135.  
  136. * Compilation Stages
  137.  
  138. In rx_compile, a string is compiled into a pattern buffer.
  139. Compilation proceeds in these stages:
  140.  
  141.     1. Make a syntax tree for the regexp.
  142.     2. Duplicate the syntax tree and make both trees nodes
  143.        in a single unifying tree.
  144.     3. In one of the two trees, remove all side effects that
  145.        aren't needed to test for the possibility of a match.
  146.        Such side effects include the filling in of output registers
  147.        for subexpressions that are not backreferenced.
  148.     4. Optimize the unifying tree.
  149.     5. Translate the tree to an NFA.
  150.     6. Analyze and optimize the NFA.
  151.     7. Copy the NFA into a contiguous region of memory.
  152.  
  153.  
  154. * Cache Size
  155.  
  156. During a search or match, the NFA is translated into a "super NFA".
  157. A super NFA can match the patterns of the corresponding NFA in no more 
  158. and often fewer steps.
  159.  
  160. The catch is that the super NFA may be costly to construct in its entirety;
  161. it may not even fit in memory.  So, states of the NFA are constructed 
  162. on demand and discarded after a period of non-use.  They are kept in a cache
  163. so that time is not wasted constructing existing nodes twice.
  164.  
  165. The size of the super state NFA cache is a contributing factor the performance
  166. of Rx.   The larger the cache (to a point) the faster Rx can run.  The
  167. variable rx_cache_bound is an upper limit on the number of superstates
  168. that can exist in the cache.
  169.  
  170. The defaulting setting is 128.  GNU sed uses 4096.  Neither setting
  171. has much justification although sed's is after a small number of quick
  172. and dirty experiments.  The memory consumed by one superstate is
  173. between 4k and 8k.  The cache only grows to its bounded size if there
  174. is actual demand for that many states.  Sed's setting, for example,
  175. may appear quite high but in practice that much memory is hardly ever
  176. used.  The default setting was chosen based on the heuristic that a
  177. megabyte is the upper limit on what a good citizen library can
  178. allocate without special arrangement.
  179.  
  180.