home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume18 / gnugrep1.3.pch / cvt1.2to1.3
Text File  |  1989-03-12  |  47KB  |  1,565 lines
  1. diff -rcN grep-1.2/Makefile grep-1.3/Makefile
  2. *** grep-1.2/Makefile    Thu Oct 13 22:11:28 1988
  3. --- grep-1.3/Makefile    Tue Feb 28 23:37:13 1989
  4. ***************
  5. *** 5,27 ****
  6.   # Add -DUSG for System V.
  7.   CFLAGS = -O
  8.   
  9.   # You may add getopt.o if your C library lacks getopt(); note that
  10.   # 4.3BSD getopt() is said to be somewhat broken.
  11.   # Add alloca.o if your machine does not support alloca().
  12. ! OBJS = grep.o dfa.o regex.o
  13.   
  14.   all: regress
  15.   
  16. ! regress: grep
  17.       cd tests; sh regress.sh
  18.   
  19. ! grep: $(OBJS)
  20. !     $(CC) $(CFLAGS) -o grep $(OBJS)
  21. !     rm -f egrep
  22. !     ln grep egrep
  23.   
  24.   clean:
  25. !     rm -f grep egrep *.o core tests/core tests/tmp.script
  26.   
  27. ! dfa.o grep.o: dfa.h
  28. ! grep.o regex.o: regex.h
  29. --- 5,40 ----
  30.   # Add -DUSG for System V.
  31.   CFLAGS = -O
  32.   
  33. + #
  34.   # You may add getopt.o if your C library lacks getopt(); note that
  35.   # 4.3BSD getopt() is said to be somewhat broken.
  36. + #
  37.   # Add alloca.o if your machine does not support alloca().
  38. ! #
  39. ! OBJS = dfa.o regex.o
  40. ! GOBJ = grep.o
  41. ! EOBJ = egrep.o
  42.   
  43. + # Space provided for machine dependent libraries.
  44. + LIBS =
  45. + 
  46.   all: regress
  47.   
  48. ! regress: egrep grep
  49.       cd tests; sh regress.sh
  50.   
  51. ! egrep: $(OBJS) $(EOBJ)
  52. !     $(CC) $(CFLAGS) -o egrep $(OBJS) $(EOBJ) $(LIBS)
  53. ! 
  54. ! egrep.o: grep.c
  55. !     $(CC) $(CFLAGS) -DEGREP -c grep.c
  56. !     mv grep.o egrep.o
  57. ! 
  58. ! grep: $(OBJS) $(GOBJ)
  59. !     $(CC) $(CFLAGS) -o grep $(OBJS) $(GOBJ) $(LIBS)
  60.   
  61.   clean:
  62. !     rm -f grep egrep *.o core tests/core tests/tmp.script tests/khadafy.out
  63.   
  64. ! dfa.o egrep.o grep.o: dfa.h
  65. ! egrep.o grep.o regex.o: regex.h
  66. diff -rcN grep-1.2/README grep-1.3/README
  67. *** grep-1.2/README    Tue Dec 13 11:04:21 1988
  68. --- grep-1.3/README    Wed Mar  1 21:43:59 1989
  69. ***************
  70. *** 1,4 ****
  71. ! This README documents GNU e?grep version 1.2.
  72.   
  73.   Changes needed to the makefile under various perversions of Unix are
  74.   described therein.
  75. --- 1,4 ----
  76. ! This README documents GNU e?grep version 1.3.
  77.   
  78.   Changes needed to the makefile under various perversions of Unix are
  79.   described therein.
  80. diff -rcN grep-1.2/README.sunos4 grep-1.3/README.sunos4
  81. *** grep-1.2/README.sunos4    Wed Dec 31 18:00:00 1969
  82. --- grep-1.3/README.sunos4    Tue Feb 28 22:35:10 1989
  83. ***************
  84. *** 0 ****
  85. --- 1,96 ----
  86. + Date:    Fri, 24 Feb 89 15:36:40 -0600
  87. + To:      mike@wheaties.ai.mit.edu
  88. + From:    Dave Cohrs <dave@cs.wisc.edu>
  89. + Subject: bug + fix in gnu grep 1.2 (from prep.ai.mit.edu)
  90. + 
  91. + I tried installing the GNU grep 1.2 on a Sun4 running 4.0.1 and
  92. + "Spencer test #36" failed.  After some experimenting, I found and
  93. + fixed the bug.  Well, actually, the bug in the the C compiler, but
  94. + I managed a workaround.
  95. + 
  96. + Description:
  97. + 
  98. + The Sun4 4.0.1 C compiler with -O doesn't generate the correct for
  99. + statements of the form
  100. +     if("string")
  101. +         x;
  102. +     else
  103. +         y;
  104. + To be exact, "y;" gets executed, while "x;" should.  This causes the
  105. + #define FETCH() to fail for test #36.
  106. + 
  107. + Fix:
  108. + 
  109. + In an #ifdef sparc in dfa.c, I made two versions of FETCH, FETCH0() and
  110. + the regular FETCH().  The former takes only one argument, the latter
  111. + expects its 2nd argument to contain a non-nil string.  This removes
  112. + the need to test the constant strings, and the compiler bug isn't
  113. + exercised.  I then changed the one instance of FETCH() with a nil
  114. + second argument to be FETCH0() instead.
  115. + 
  116. + dave cohrs
  117. + 
  118. + ===================================================================
  119. + RCS file: RCS/dfa.c,v
  120. + retrieving revision 1.1
  121. + diff -c -r1.1 dfa.c
  122. + *** /tmp/,RCSt1a05930    Fri Feb 24 15:32:33 1989
  123. + --- dfa.c    Fri Feb 24 15:23:34 1989
  124. + ***************
  125. + *** 285,293 ****
  126. + --- 285,315 ----
  127. +                      is turned off). */
  128. +   
  129. +   /* Note that characters become unsigned here. */
  130. + + #ifdef sparc
  131. + + /*
  132. + +  * Sun4 4.0.1 C compiler can't compare constant strings correctly.
  133. + +  * e.g. if("test") { x; } else { y; }
  134. + +  * the compiler will not generate code to execute { x; }, but
  135. + +  * executes { y; } instead.
  136. + +  */
  137. + + #define FETCH0(c)                 \
  138. + +   {                         \
  139. + +     if (! lexleft)                 \
  140. + +       return _END;                 \
  141. + +     (c) = (unsigned char) *lexptr++;  \
  142. + +     --lexleft;                     \
  143. + +   }
  144. +   #define FETCH(c, eoferr)             \
  145. +     {                         \
  146. +       if (! lexleft)                 \
  147. + +       regerror(eoferr);            \
  148. + +     (c) = (unsigned char) *lexptr++;  \
  149. + +     --lexleft;                     \
  150. + +   }
  151. + + #else
  152. + + #define FETCH(c, eoferr)             \
  153. + +   {                         \
  154. + +     if (! lexleft)                 \
  155. +         if (eoferr)                 \
  156. +       regerror(eoferr);            \
  157. +         else                     \
  158. + ***************
  159. + *** 295,300 ****
  160. + --- 317,323 ----
  161. +       (c) = (unsigned char) *lexptr++;  \
  162. +       --lexleft;                     \
  163. +     }
  164. + + #endif sparc
  165. +   
  166. +   static _token
  167. +   lex()
  168. + ***************
  169. + *** 303,309 ****
  170. + --- 326,336 ----
  171. +     int invert;
  172. +     _charset cset;
  173. +   
  174. + + #ifdef sparc
  175. + +   FETCH0(c);
  176. + + #else
  177. +     FETCH(c, (char *) 0);
  178. + + #endif sparc
  179. +     switch (c)
  180. +       {
  181. +       case '^':
  182. diff -rcN grep-1.2/dfa.c grep-1.3/dfa.c
  183. *** grep-1.2/dfa.c    Thu Oct 13 22:11:29 1988
  184. --- grep-1.3/dfa.c    Tue Feb 28 18:46:35 1989
  185. ***************
  186. *** 105,110 ****
  187. --- 105,112 ----
  188.   You are forbidden to forbid anyone else to use, share and improve
  189.   what you give them.   Help stamp out software-hoarding!  */
  190.   
  191. + #include <stdio.h>
  192. + #include <assert.h>
  193.   #include <ctype.h>
  194.   #include "dfa.h"
  195.   
  196. ***************
  197. *** 135,140 ****
  198. --- 137,143 ----
  199.   {
  200.     ptr_t r = malloc(n);
  201.   
  202. +   assert(n != 0);
  203.     if (r)
  204.       return r;
  205.     else
  206. ***************
  207. *** 148,153 ****
  208. --- 151,157 ----
  209.   {
  210.     ptr_t r = realloc(p, n);
  211.   
  212. +   assert(n != 0);
  213.     if (r)
  214.       return r;
  215.     else
  216. ***************
  217. *** 1122,1128 ****
  218.         {
  219.       copy(&r->follows[i], &merged);
  220.       epsclosure(&merged, r);
  221. !     REALLOC(r->follows[i].elems, _position, merged.nelem);
  222.       copy(&merged, &r->follows[i]);
  223.         }
  224.   
  225. --- 1126,1133 ----
  226.         {
  227.       copy(&r->follows[i], &merged);
  228.       epsclosure(&merged, r);
  229. !     if (r->follows[i].nelem < merged.nelem)
  230. !       REALLOC(r->follows[i].elems, _position, merged.nelem);
  231.       copy(&merged, &r->follows[i]);
  232.         }
  233.   
  234. ***************
  235. *** 1719,1742 ****
  236.   Having found the postfix representation of the regular expression,
  237.   try to find a long sequence of characters that must appear in any line
  238.   containing the r.e.
  239. ! Finding a "longest" sequence is beyond the scope of this bagatelle;
  240. ! we take the easy way out and hope for the best.
  241.   
  242. ! We do a bottom-up calculation of several (possibly zero-length) sequences
  243. ! of characters that must appear in matches of r.e.'s represented by trees
  244. ! rooted at the nodes of the postfix representation:
  245.       sequences that must appear at the left of the match ("left")
  246.       sequences that must appear at the right of the match ("right")
  247. !     sequences that must appear somewhere in the match ("in")
  248.       sequences that must constitute the match ("is")
  249. ! When we get to the root of the tree, we use its calculated "in" sequence
  250. ! as our answer.  The sequence we find is returned in r->must (where "r" is
  251. ! the single argument passed to "regmust"); the length of the sequence is
  252. ! returned in r->mustn.
  253.   
  254.   The sequences calculated for the various types of node (in pseudo ANSI c)
  255.   are shown below.  "p" is the operand of unary operators (and the left-hand
  256. ! operand of binary operators); "q" is the right-hand operand of binary operators.
  257.   "ZERO" means "a zero-length sequence" below.
  258.   
  259.   Type    left        right        is        in
  260. --- 1724,1749 ----
  261.   Having found the postfix representation of the regular expression,
  262.   try to find a long sequence of characters that must appear in any line
  263.   containing the r.e.
  264. ! Finding a "longest" sequence is beyond the scope here;
  265. ! we take an easy way out and hope for the best.
  266. ! (Take "(ab|a)b"--please.)
  267.   
  268. ! We do a bottom-up calculation of sequences of characters that must appear
  269. ! in matches of r.e.'s represented by trees rooted at the nodes of the postfix
  270. ! representation:
  271.       sequences that must appear at the left of the match ("left")
  272.       sequences that must appear at the right of the match ("right")
  273. !     lists of sequences that must appear somewhere in the match ("in")
  274.       sequences that must constitute the match ("is")
  275. ! When we get to the root of the tree, we use one of the longest of its
  276. ! calculated "in" sequences as our answer.  The sequence we find is returned in
  277. ! r->must (where "r" is the single argument passed to "regmust");
  278. ! the length of the sequence is returned in r->mustn.
  279.   
  280.   The sequences calculated for the various types of node (in pseudo ANSI c)
  281.   are shown below.  "p" is the operand of unary operators (and the left-hand
  282. ! operand of binary operators); "q" is the right-hand operand of binary operators
  283. ! .
  284.   "ZERO" means "a zero-length sequence" below.
  285.   
  286.   Type    left        right        is        in
  287. ***************
  288. *** 1749,1865 ****
  289.   
  290.   QMARK    ZERO        ZERO        ZERO        ZERO
  291.   
  292. ! PLUS    p->left        p->right    ZERO        ZERO
  293.   
  294. ! CAT    (p->is==ZERO)?    (q->is==ZERO)?    (p->is!=ZERO &&    longest of
  295. !     p->left :    q->right :    q->is!=ZERO) ?    p->in, q->in, or
  296.       p->is##q->left    p->right##q->is    p->is##q->is :    p->right##q->left
  297.                       ZERO
  298.   
  299. ! OR    longest common    longest common    (do p->is and    (do p->in and
  300. !     leading        trailing    q->is have same    q->in have same
  301. !     (sub)sequence    (sub)sequence    length and    length and
  302. !     of p->left    of p->right    content) ?    content) ?
  303. !     and q->left    and q->right    p->is : NULL    p->in : NULL
  304.   
  305.   If there's anything else we recognize in the tree, all four sequences get set
  306.   to zero-length sequences.  If there's something we don't recognize in the tree,
  307.   we just return a zero-length sequence.
  308.   
  309. ! After the above calculations are performed, three additional steps are taken:
  310.   
  311. ! 1.    If there's a non-zero-length "is" sequence, it replaces the
  312. !     "left", "right", and "in" sequences.
  313. ! 2.    If the "left" sequence is longer than the "in" sequence, it replaces
  314. !     the "in" sequence.
  315. ! 3.    If the "right" sequence is longer than the "in" sequence, it replaces
  316. !     the "in" sequence.
  317. ! 
  318. ! Possibilities:
  319. ! 1.    Find the longest common (sub)sequence of p->in and q->in when doing
  320. !     an OR node's "in" sequence?  Possibly effective, as in
  321. !         egrep 'pepsi|epsilon'
  322. !     but is it cheap and easy enough?
  323. ! 2.    In replacing "in" sequences with "left" and "right" sequences, how
  324. !     should ties be broken?
  325. ! 3.    Switch to allocated memory, rather than relying on a defined MUST_MAX?
  326.   */
  327.   
  328. ! #define TRUE    1
  329. ! #define FALSE    0
  330.   
  331. ! typedef struct {
  332. !     int    n;
  333. !     char    p[MUST_MAX];
  334. ! } counted;
  335.   
  336. ! #define initcounted(cp)    ((cp)->n = 0)
  337. ! 
  338. ! static void
  339. ! cntcpy(top, fromp)
  340. ! counted *    top;
  341. ! counted *    fromp;
  342. ! {
  343. !     register char *    fp;
  344. !     register char *    tp;
  345. !     register int    n;
  346. ! 
  347. !     fp = fromp->p;
  348. !     tp = top->p;
  349. !     n = fromp->n;
  350. !     top->n = n;
  351. !     while (n-- > 0)
  352. !         *tp++ = *fp++;
  353. ! }
  354. ! 
  355. ! static void
  356. ! cntcat(top, fromp)
  357. ! counted *    top;
  358. ! counted *    fromp;
  359. ! {
  360. !     register char *    fp;
  361. !     register char *    tp;
  362. !     register int    n;
  363. ! 
  364. !     fp = fromp->p;
  365. !     tp = top->p + top->n;
  366. !     n = fromp->n;
  367. !     top->n += n;
  368. !     while (n-- > 0)
  369. !         *tp++ = *fp++;
  370. ! }
  371. ! 
  372. ! static int
  373. ! cntsame(acp, bcp)
  374. ! counted *    acp;
  375. ! counted *    bcp;
  376.   {
  377.       register int    i;
  378.   
  379. !     if (acp->n != bcp->n)
  380. !         return FALSE;
  381. !     for (i = 0; i < acp->n; ++i)
  382. !         if (acp->p[i] != bcp->p[i])
  383. !             return FALSE;
  384. !     return TRUE;
  385.   }
  386.   
  387.   
  388.   typedef struct {
  389. !     counted    left;
  390. !     counted    right;
  391. !     counted    in;
  392. !     counted    is;
  393.   } must;
  394.   
  395.   static void
  396. ! initmust(mp)
  397. ! must *    mp;
  398.   {
  399. !     initcounted(&mp->left);
  400. !     initcounted(&mp->right);
  401. !     initcounted(&mp->in);
  402. !     initcounted(&mp->is);
  403.   }
  404.   
  405.   static void
  406. --- 1756,2022 ----
  407.   
  408.   QMARK    ZERO        ZERO        ZERO        ZERO
  409.   
  410. ! PLUS    p->left        p->right    ZERO        p->in
  411.   
  412. ! CAT    (p->is==ZERO)?    (q->is==ZERO)?    (p->is!=ZERO &&    p->in plus
  413. !     p->left :    q->right :    q->is!=ZERO) ?    q->in plus
  414.       p->is##q->left    p->right##q->is    p->is##q->is :    p->right##q->left
  415.                       ZERO
  416.   
  417. ! OR    longest common    longest common    (do p->is and    substrings common to
  418. !     leading        trailing    q->is have same    p->in and q->in
  419. !     (sub)sequence    (sub)sequence    length and    
  420. !     of p->left    of p->right    content) ?    
  421. !     and q->left    and q->right    p->is : NULL    
  422.   
  423.   If there's anything else we recognize in the tree, all four sequences get set
  424.   to zero-length sequences.  If there's something we don't recognize in the tree,
  425.   we just return a zero-length sequence.
  426.   
  427. ! Break ties in favor of infrequent letters (choosing 'zzz' in preference to
  428. ! 'aaa')?
  429.   
  430. ! And. . .is it here or someplace that we might ponder "optimizations" such as
  431. !     egrep 'psi|epsilon'    ->    egrep 'psi'
  432. !     egrep 'pepsi|epsilon'    ->    egrep 'epsi'
  433. !                     (Yes, we now find "epsi" as a "string
  434. !                     that must occur", but we might also
  435. !                     simplify the *entire* r.e. being sought
  436. ! )
  437. !     grep '[c]'        ->    grep 'c'
  438. !     grep '(ab|a)b'        ->    grep 'ab'
  439. !     grep 'ab*'        ->    grep 'a'
  440. !     grep 'a*b'        ->    grep 'b'
  441. ! There are several issues:
  442. !     Is optimization easy (enough)?
  443. ! 
  444. !     Does optimization actually accomplish anything,
  445. !     or is the automaton you get from "psi|epsilon" (for example)
  446. !     the same as the one you get from "psi" (for example)?
  447. ! 
  448. !     Are optimizable r.e.'s likely to be used in real-life situations
  449. !     (something like 'ab*' is probably unlikely; something like is
  450. !     'psi|epsilon' is likelier)?
  451.   */
  452.   
  453. ! static char *
  454. ! icatalloc(old, new)
  455. ! char *    old;
  456. ! char *    new;
  457. ! {
  458. !     register char *    result;
  459. !     register int    oldsize, newsize;
  460. ! 
  461. !     newsize = (new == NULL) ? 0 : strlen(new);
  462. !     if (old == NULL)
  463. !         oldsize = 0;
  464. !     else if (newsize == 0)
  465. !         return old;
  466. !     else    oldsize = strlen(old);
  467. !     if (old == NULL)
  468. !         result = (char *) malloc(newsize + 1);
  469. !     else    result = (char *) realloc((void *) old, oldsize + newsize + 1);
  470. !     if (result != NULL && new != NULL)
  471. !         (void) strcpy(result + oldsize, new);
  472. !     return result;
  473. ! }
  474. ! 
  475. ! static char *
  476. ! icpyalloc(string)
  477. ! const char *    string;
  478. ! {
  479. !     return icatalloc((char *) NULL, string);
  480. ! }
  481. ! 
  482. ! static char *
  483. ! istrstr(lookin, lookfor)
  484. ! char *        lookin;
  485. ! register char *    lookfor;
  486. ! {
  487. !     register char *    cp;
  488. !     register int    len;
  489.   
  490. !     len = strlen(lookfor);
  491. !     for (cp = lookin; *cp != '\0'; ++cp)
  492. !         if (strncmp(cp, lookfor, len) == 0)
  493. !             return cp;
  494. !     return NULL;
  495. ! }
  496. ! 
  497. ! static void
  498. ! ifree(cp)
  499. ! char *    cp;
  500. ! {
  501. !     if (cp != NULL)
  502. !         free(cp);
  503. ! }
  504. ! 
  505. ! static void
  506. ! freelist(cpp)
  507. ! register char **    cpp;
  508. ! {
  509. !     register int    i;
  510. ! 
  511. !     if (cpp == NULL)
  512. !         return;
  513. !     for (i = 0; cpp[i] != NULL; ++i) {
  514. !         free(cpp[i]);
  515. !         cpp[i] = NULL;
  516. !     }
  517. ! }
  518. ! 
  519. ! static char **
  520. ! enlist(cpp, new, len)
  521. ! register char **    cpp;
  522. ! register char *        new;
  523. ! {
  524. !     register int    i, j;
  525. ! 
  526. !     if (cpp == NULL)
  527. !         return NULL;
  528. !     if ((new = icpyalloc(new)) == NULL) {
  529. !         freelist(cpp);
  530. !         return NULL;
  531. !     }
  532. !     new[len] = '\0';
  533. !     /*
  534. !     ** Is there already something in the list that's new (or longer)?
  535. !     */
  536. !     for (i = 0; cpp[i] != NULL; ++i)
  537. !         if (istrstr(cpp[i], new) != NULL) {
  538. !             free(new);
  539. !             return cpp;
  540. !         }
  541. !     /*
  542. !     ** Eliminate any obsoleted strings.
  543. !     */
  544. !     j = 0;
  545. !     while (cpp[j] != NULL)
  546. !         if (istrstr(new, cpp[j]) == NULL)
  547. !             ++j;
  548. !         else {
  549. !             free(cpp[j]);
  550. !             if (--i == j)
  551. !                 break;
  552. !             cpp[j] = cpp[i];
  553. !         }
  554. !     /*
  555. !     ** Add the new string.
  556. !     */
  557. !     cpp = (char **) realloc((char *) cpp, (i + 2) * sizeof *cpp);
  558. !     if (cpp == NULL)
  559. !         return NULL;
  560. !     cpp[i] = new;
  561. !     cpp[i + 1] = NULL;
  562. !     return cpp;
  563. ! }
  564. ! 
  565. ! /*
  566. ! ** Given pointers to two strings,
  567. ! ** return a pointer to an allocated list of their distinct common substrings.
  568. ! ** Return NULL if something seems wild.
  569. ! */
  570.   
  571. ! static char **
  572. ! comsubs(left, right)
  573. ! char *    left;
  574. ! char *    right;
  575. ! {
  576. !     register char **    cpp;
  577. !     register char *        lcp;
  578. !     register char *        rcp;
  579. !     register int        i, len;
  580. ! 
  581. !     if (left == NULL || right == NULL)
  582. !         return NULL;
  583. !     cpp = (char **) malloc(sizeof *cpp);
  584. !     if (cpp == NULL)
  585. !         return NULL;
  586. !     cpp[0] = NULL;
  587. !     for (lcp = left; *lcp != '\0'; ++lcp) {
  588. !         len = 0;
  589. !         rcp = strchr(right, *lcp);
  590. !         while (rcp != NULL) {
  591. !             for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i)
  592. !                 ;
  593. !             if (i > len)
  594. !                 len = i;
  595. !             rcp = strchr(rcp + 1, *lcp);
  596. !         }
  597. !         if (len == 0)
  598. !             continue;
  599. !         if ((cpp = enlist(cpp, lcp, len)) == NULL)
  600. !             break;
  601. !     }
  602. !     return cpp;
  603. ! }
  604. ! 
  605. ! static char **
  606. ! addlists(old, new)
  607. ! char **    old;
  608. ! char **    new;
  609.   {
  610.       register int    i;
  611.   
  612. !     if (old == NULL || new == NULL)
  613. !         return NULL;
  614. !     for (i = 0; new[i] != NULL; ++i) {
  615. !         old = enlist(old, new[i], strlen(new[i]));
  616. !         if (old == NULL)
  617. !             break;
  618. !     }
  619. !     return old;
  620.   }
  621.   
  622. + /*
  623. + ** Given two lists of substrings,
  624. + ** return a new list giving substrings common to both.
  625. + */
  626. + 
  627. + static char **
  628. + inboth(left, right)
  629. + char **    left;
  630. + char **    right;
  631. + {
  632. +     register char **    both;
  633. +     register char **    temp;
  634. +     register int        lnum, rnum;
  635. + 
  636. +     if (left == NULL || right == NULL)
  637. +         return NULL;
  638. +     both = (char **) malloc(sizeof *both);
  639. +     if (both == NULL)
  640. +         return NULL;
  641. +     both[0] = NULL;
  642. +     for (lnum = 0; left[lnum] != NULL; ++lnum) {
  643. +         for (rnum = 0; right[rnum] != NULL; ++rnum) {
  644. +             temp = comsubs(left[lnum], right[rnum]);
  645. +             if (temp == NULL) {
  646. +                 freelist(both);
  647. +                 return NULL;
  648. +             }
  649. +             both = addlists(both, temp);
  650. +             freelist(temp);
  651. +             if (both == NULL)
  652. +                 return NULL;
  653. +         }
  654. +     }
  655. +     return both;
  656. + }
  657.   
  658.   typedef struct {
  659. !     char **    in;
  660. !     char *    left;
  661. !     char *    right;
  662. !     char *    is;
  663.   } must;
  664.   
  665.   static void
  666. ! resetmust(mp)
  667. ! register must *    mp;
  668.   {
  669. !     mp->left[0] = mp->right[0] = mp->is[0] = '\0';
  670. !     freelist(mp->in);
  671.   }
  672.   
  673.   static void
  674. ***************
  675. *** 1866,1884 ****
  676.   regmust(r)
  677.   register struct regexp *    r;
  678.   {
  679. !     must            musts[MUST_MAX];
  680.       register must *        mp;
  681. !     counted            result;
  682.       register int        ri;
  683.       register int        i;
  684.       register _token        t;
  685.   
  686.       reg->mustn = 0;
  687.       reg->must[0] = '\0';
  688. !     if (reg->tindex > MUST_MAX)
  689.           return;
  690.       mp = musts;
  691. !     initcounted(&result);
  692.       for (ri = 0; ri < reg->tindex; ++ri) {
  693.           switch (t = reg->tokens[ri]) {
  694.           case _ALLBEGLINE:
  695. --- 2023,2056 ----
  696.   regmust(r)
  697.   register struct regexp *    r;
  698.   {
  699. !     register must *        musts;
  700.       register must *        mp;
  701. !     register char *        result;
  702.       register int        ri;
  703.       register int        i;
  704.       register _token        t;
  705. +     static must        must0;
  706.   
  707.       reg->mustn = 0;
  708.       reg->must[0] = '\0';
  709. !     musts = (must *) malloc((reg->tindex + 1) * sizeof *musts);
  710. !     if (musts == NULL)
  711.           return;
  712.       mp = musts;
  713. !     for (i = 0; i <= reg->tindex; ++i)
  714. !         mp[i] = must0;
  715. !     for (i = 0; i <= reg->tindex; ++i) {
  716. !         mp[i].in = (char **) malloc(sizeof *mp[i].in);
  717. !         mp[i].left = malloc(2);
  718. !         mp[i].right = malloc(2);
  719. !         mp[i].is = malloc(2);
  720. !         if (mp[i].in == NULL || mp[i].left == NULL ||
  721. !             mp[i].right == NULL || mp[i].is == NULL)
  722. !                 goto done;
  723. !         mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0';
  724. !         mp[i].in[0] = NULL;
  725. !     }
  726. !     result = "";
  727.       for (ri = 0; ri < reg->tindex; ++ri) {
  728.           switch (t = reg->tokens[ri]) {
  729.           case _ALLBEGLINE:
  730. ***************
  731. *** 1894,1900 ****
  732.           case _LIMWORD:
  733.           case _NOTLIMWORD:
  734.           case _BACKREF:
  735. !             initmust(mp);
  736.               break;
  737.           case _STAR:
  738.           case _QMARK:
  739. --- 2066,2072 ----
  740.           case _LIMWORD:
  741.           case _NOTLIMWORD:
  742.           case _BACKREF:
  743. !             resetmust(mp);
  744.               break;
  745.           case _STAR:
  746.           case _QMARK:
  747. ***************
  748. *** 1901,1945 ****
  749.               if (mp <= musts)
  750.                   goto done;    /* "cannot happen" */
  751.               --mp;
  752. !             initmust(mp);
  753.               break;
  754.           case _OR:
  755.               if (mp < &musts[2])
  756.                   goto done;    /* "cannot happen" */
  757.               {
  758. !                 register must *    lmp;
  759. !                 register must *    rmp;
  760. !                 register int    j, n;
  761.   
  762.                   rmp = --mp;
  763.                   lmp = --mp;
  764.                   /* Guaranteed to be.  Unlikely, but. . . */
  765. !                 if (!cntsame(&lmp->is, &rmp->is))
  766. !                     initcounted(&lmp->is);
  767.                   /* Left side--easy */
  768. !                 n = lmp->left.n;
  769. !                 if (n > rmp->left.n)
  770. !                     n = rmp->left.n;
  771. !                 for (i = 0; i < n; ++i)
  772. !                     if (lmp->left.p[i] != rmp->left.p[i])
  773. !                         break;
  774. !                 lmp->left.n = i;
  775.                   /* Right side */
  776. !                 n = lmp->right.n;
  777. !                 if (n > rmp->right.n)
  778. !                     n = rmp->right.n;
  779.                   for (i = 0; i < n; ++i)
  780. !                     if (lmp->right.p[lmp->right.n-i-1] !=
  781. !                         rmp->right.p[rmp->right.n-i-1])
  782.                           break;
  783.                   for (j = 0; j < i; ++j)
  784. !                     lmp->right.p[j] =
  785. !                         lmp->right.p[(lmp->right.n -
  786. !                             i) + j];
  787. !                 lmp->right.n = i;
  788. !                 /* Includes.  Unlikely, but. . . */
  789. !                 if (!cntsame(&lmp->in, &rmp->in))
  790. !                     initcounted(&lmp->in);
  791.               }
  792.               break;
  793.           case _PLUS:
  794. --- 2073,2120 ----
  795.               if (mp <= musts)
  796.                   goto done;    /* "cannot happen" */
  797.               --mp;
  798. !             resetmust(mp);
  799.               break;
  800.           case _OR:
  801.               if (mp < &musts[2])
  802.                   goto done;    /* "cannot happen" */
  803.               {
  804. !                 register char **    new;
  805. !                 register must *        lmp;
  806. !                 register must *        rmp;
  807. !                 register int        j, ln, rn, n;
  808.   
  809.                   rmp = --mp;
  810.                   lmp = --mp;
  811.                   /* Guaranteed to be.  Unlikely, but. . . */
  812. !                 if (strcmp(lmp->is, rmp->is) != 0)
  813. !                     lmp->is[0] = '\0';
  814.                   /* Left side--easy */
  815. !                 i = 0;
  816. !                 while (lmp->left[i] != '\0' &&
  817. !                     lmp->left[i] == rmp->left[i])
  818. !                         ++i;
  819. !                 lmp->left[i] = '\0';
  820.                   /* Right side */
  821. !                 ln = strlen(lmp->right);
  822. !                 rn = strlen(rmp->right);
  823. !                 n = ln;
  824. !                 if (n > rn)
  825. !                     n = rn;
  826.                   for (i = 0; i < n; ++i)
  827. !                     if (lmp->right[ln - i - 1] !=
  828. !                         rmp->right[rn - i - 1])
  829.                           break;
  830.                   for (j = 0; j < i; ++j)
  831. !                     lmp->right[j] =
  832. !                         lmp->right[(ln - i) + j];
  833. !                 lmp->right[j] = '\0';
  834. !                 new = inboth(lmp->in, rmp->in);
  835. !                 if (new == NULL)
  836. !                     goto done;
  837. !                 freelist(lmp->in);
  838. !                 free((char *) lmp->in);
  839. !                 lmp->in = new;
  840.               }
  841.               break;
  842.           case _PLUS:
  843. ***************
  844. *** 1946,2001 ****
  845.               if (mp <= musts)
  846.                   goto done;    /* "cannot happen" */
  847.               --mp;
  848. !             initcounted(&mp->is);
  849.               break;
  850.           case _END:
  851.               if (mp != &musts[1])
  852.                   goto done;    /* "cannot happen" */
  853. !             result = musts[0].in;
  854.               goto done;
  855.           case _CAT:
  856.               if (mp < &musts[2])
  857.                   goto done;    /* "cannot happen" */
  858.               {
  859. !                 must *    lmp;
  860. !                 must *    rmp;
  861. !                 must    new;
  862. !                 must *    nmp;
  863. !                 int    a, b, c;
  864.   
  865.                   rmp = --mp;
  866.                   lmp = --mp;
  867. !                 nmp = &new;
  868. !                 initmust(nmp);
  869.                   /* Left-hand */
  870. !                 cntcat(&nmp->left, &lmp->left);
  871. !                 if (lmp->is.n != 0)
  872. !                     cntcat(&nmp->left, &rmp->left);
  873.                   /* Right-hand */
  874. !                 if (rmp->is.n != 0)
  875. !                     cntcat(&nmp->right, &lmp->right);
  876. !                 cntcat(&nmp->right, &rmp->right);
  877.                   /* Guaranteed to be */
  878. !                 if (lmp->is.n != 0 && rmp->is.n != 0) {
  879. !                     cntcat(&nmp->is, &lmp->is);
  880. !                     cntcat(&nmp->is, &rmp->is);
  881.                   }
  882. -                 /* Interior */
  883. -                 a = lmp->in.n;
  884. -                 b = rmp->in.n;
  885. -                 c = lmp->right.n + rmp->left.n;
  886. -                 if (a == 0 && b == 0 && c == 0) {
  887. -                     /* nothing */
  888. -                     ;
  889. -                 } else if (c > a && c > b) {
  890. -                     cntcat(&nmp->in, &lmp->right);
  891. -                     cntcat(&nmp->in, &rmp->left);
  892. -                 } else if (a > b) {
  893. -                     cntcat(&nmp->in, &lmp->in);
  894. -                 } else {
  895. -                     cntcat(&nmp->in, &rmp->in);
  896. -                 }
  897. -                 *mp = new;
  898.               }
  899.               break;
  900.           default:
  901. --- 2121,2187 ----
  902.               if (mp <= musts)
  903.                   goto done;    /* "cannot happen" */
  904.               --mp;
  905. !             mp->is[0] = '\0';
  906.               break;
  907.           case _END:
  908.               if (mp != &musts[1])
  909.                   goto done;    /* "cannot happen" */
  910. !             for (i = 0; musts[0].in[i] != NULL; ++i)
  911. !                 if (strlen(musts[0].in[i]) > strlen(result))
  912. !                     result = musts[0].in[i];
  913.               goto done;
  914.           case _CAT:
  915.               if (mp < &musts[2])
  916.                   goto done;    /* "cannot happen" */
  917.               {
  918. !                 register must *    lmp;
  919. !                 register must *    rmp;
  920.   
  921.                   rmp = --mp;
  922.                   lmp = --mp;
  923. !                 /*
  924. !                 ** In.  Everything in left, plus everything in
  925. !                 ** right, plus catenation of
  926. !                 ** left's right and right's left.
  927. !                 */
  928. !                 lmp->in = addlists(lmp->in, rmp->in);
  929. !                 if (lmp->in == NULL)
  930. !                     goto done;
  931. !                 if (lmp->right[0] != '\0' &&
  932. !                     rmp->left[0] != '\0') {
  933. !                         register char *    tp;
  934. ! 
  935. !                         tp = icpyalloc(lmp->right);
  936. !                         if (tp == NULL)
  937. !                             goto done;
  938. !                         tp = icatalloc(tp, rmp->left);
  939. !                         if (tp == NULL)
  940. !                             goto done;
  941. !                         lmp->in = enlist(lmp->in, tp,
  942. !                             strlen(tp));
  943. !                         free(tp);
  944. !                         if (lmp->in == NULL)
  945. !                             goto done;
  946. !                 }
  947.                   /* Left-hand */
  948. !                 if (lmp->is[0] != '\0') {
  949. !                     lmp->left = icatalloc(lmp->left,
  950. !                         rmp->left);
  951. !                     if (lmp->left == NULL)
  952. !                         goto done;
  953. !                 }
  954.                   /* Right-hand */
  955. !                 if (rmp->is[0] == '\0')
  956. !                     lmp->right[0] = '\0';
  957. !                 lmp->right = icatalloc(lmp->right, rmp->right);
  958. !                 if (lmp->right == NULL)
  959. !                     goto done;
  960.                   /* Guaranteed to be */
  961. !                 if (lmp->is[0] != '\0' && rmp->is[0] != '\0') {
  962. !                     lmp->is = icatalloc(lmp->is, rmp->is);
  963. !                     if (lmp->is == NULL)
  964. !                         goto done;
  965.                   }
  966.               }
  967.               break;
  968.           default:
  969. ***************
  970. *** 2002,2036 ****
  971.               if (t < _END) {
  972.                   /* "cannot happen" */
  973.                   goto done;
  974.               } else if (t >= _SET) {
  975.                   /* easy enough */
  976. !                 initmust(mp);
  977.               } else {
  978.                   /* plain character */
  979. !                 mp->left.p[0] = mp->right.p[0] =
  980. !                     mp->in.p[0] = mp->is.p[0] = t;
  981. !                 mp->left.n = mp->right.n =
  982. !                     mp->in.n = mp->is.n = 1;
  983. !                 break;
  984.               }
  985.               break;
  986.           }
  987. -         /*
  988. -         ** "Additional steps"
  989. -         */
  990. -         if (mp->is.n > 0) {
  991. -             cntcpy(&mp->left, &mp->is);
  992. -             cntcpy(&mp->right, &mp->is);
  993. -             cntcpy(&mp->in, &mp->is);
  994. -         }
  995. -         if (mp->left.n > mp->in.n)
  996. -             cntcpy(&mp->in, &mp->left);
  997. -         if (mp->right.n > mp->in.n)
  998. -             cntcpy(&mp->in, &mp->right);
  999.           ++mp;
  1000.       }
  1001.   done:
  1002. !     reg->mustn = result.n;
  1003. !     for (i = 0; i < result.n; ++i)
  1004. !         reg->must[i] = result.p[i];
  1005.   }
  1006. --- 2188,2223 ----
  1007.               if (t < _END) {
  1008.                   /* "cannot happen" */
  1009.                   goto done;
  1010. +             } else if (t == '\0') {
  1011. +                 /* not on *my* shift */
  1012. +                 goto done;
  1013.               } else if (t >= _SET) {
  1014.                   /* easy enough */
  1015. !                 resetmust(mp);
  1016.               } else {
  1017.                   /* plain character */
  1018. !                 resetmust(mp);
  1019. !                 mp->is[0] = mp->left[0] = mp->right[0] = t;
  1020. !                 mp->is[1] = mp->left[1] = mp->right[1] = '\0';
  1021. !                 mp->in = enlist(mp->in, mp->is, 1);
  1022. !                 if (mp->in == NULL)
  1023. !                     goto done;
  1024.               }
  1025.               break;
  1026.           }
  1027.           ++mp;
  1028.       }
  1029.   done:
  1030. !     (void) strncpy(reg->must, result, MUST_MAX - 1);
  1031. !     reg->must[MUST_MAX - 1] = '\0';
  1032. !     reg->mustn = strlen(reg->must);
  1033. !     mp = musts;
  1034. !     for (i = 0; i <= reg->tindex; ++i) {
  1035. !         freelist(mp[i].in);
  1036. !         ifree((char *) mp[i].in);
  1037. !         ifree(mp[i].left);
  1038. !         ifree(mp[i].right);
  1039. !         ifree(mp[i].is);
  1040. !     }
  1041. !     free((char *) mp);
  1042.   }
  1043. diff -rcN grep-1.2/dfa.h grep-1.3/dfa.h
  1044. *** grep-1.2/dfa.h    Thu Oct 13 22:11:29 1988
  1045. --- grep-1.3/dfa.h    Tue Feb 28 21:53:15 1989
  1046. ***************
  1047. *** 103,108 ****
  1048. --- 103,117 ----
  1049.   You are forbidden to forbid anyone else to use, share and improve
  1050.   what you give them.   Help stamp out software-hoarding!  */
  1051.   
  1052. + 
  1053. + #ifdef USG
  1054. + #include <string.h>
  1055. + extern char *index();
  1056. + #else
  1057. + #include <strings.h>
  1058. + extern char *strchr(), *strrchr(), *memcpy();
  1059. + #endif
  1060. + 
  1061.   #ifdef __STDC__
  1062.   
  1063.   /* Missing include files for GNU C. */
  1064. ***************
  1065. *** 113,124 ****
  1066.   extern void *realloc(void *, size_t);
  1067.   extern void free(void *);
  1068.   
  1069. - #ifndef USG
  1070. - extern char *strchr(), *strrchr(), *memcpy();
  1071. - #else
  1072. - extern char *index();
  1073. - #endif
  1074. - 
  1075.   extern char *bcopy(), *bzero();
  1076.   
  1077.   #ifdef SOMEDAY
  1078. --- 122,127 ----
  1079. ***************
  1080. *** 136,147 ****
  1081.   extern char *calloc(), *malloc(), *realloc();
  1082.   extern void free();
  1083.   
  1084. - #ifndef USG
  1085. - extern char *strchr(), *strrchr(), *memcpy();
  1086. - #else
  1087. - extern char *index();
  1088. - #endif
  1089. - 
  1090.   extern char *bcopy(), *bzero();
  1091.   
  1092.   #define ISALNUM(c) (isascii(c) && isalnum(c))
  1093. --- 139,144 ----
  1094. ***************
  1095. *** 380,387 ****
  1096.      a constraint. */
  1097.   typedef struct
  1098.   {
  1099. !   unsigned index:24,        /* Index into the parse array. */
  1100. !        constraint:8;    /* Constraint for matching this position. */
  1101.   } _position;
  1102.   
  1103.   /* Sets of positions are stored as arrays. */
  1104. --- 377,384 ----
  1105.      a constraint. */
  1106.   typedef struct
  1107.   {
  1108. !   unsigned index;        /* Index into the parse array. */
  1109. !   unsigned constraint;        /* Constraint for matching this position. */
  1110.   } _position;
  1111.   
  1112.   /* Sets of positions are stored as arrays. */
  1113. ***************
  1114. *** 398,407 ****
  1115.   {
  1116.     int hash;            /* Hash of the positions of this state. */
  1117.     _position_set elems;        /* Positions this state could match. */
  1118. !   unsigned newline:1,        /* True if previous state matched newline. */
  1119. !        letter:1,        /* True if previous state matched a letter. */
  1120. !        backref:1,        /* True if this state matches a \<digit>. */
  1121. !        constraint:8;    /* Constraint for this state to accept. */
  1122.     int first_end;        /* Token value of the first _END in elems. */
  1123.   } _dfa_state;
  1124.   
  1125. --- 395,404 ----
  1126.   {
  1127.     int hash;            /* Hash of the positions of this state. */
  1128.     _position_set elems;        /* Positions this state could match. */
  1129. !   char newline;            /* True if previous state matched newline. */
  1130. !   char letter;            /* True if previous state matched a letter. */
  1131. !   char backref;            /* True if this state matches a \<digit>. */
  1132. !   unsigned char constraint;    /* Constraint for this state to accept. */
  1133.     int first_end;        /* Token value of the first _END in elems. */
  1134.   } _dfa_state;
  1135.   
  1136. diff -rcN grep-1.2/getopt.c grep-1.3/getopt.c
  1137. *** grep-1.2/getopt.c    Sun Dec 11 10:37:36 1988
  1138. --- grep-1.3/getopt.c    Tue Feb 28 17:44:55 1989
  1139. ***************
  1140. *** 406,412 ****
  1141.           if (opterr != 0)
  1142.             fprintf (stderr, "%s: no argument for `-%c' option\n",
  1143.                  argv[0], c);
  1144. !         optarg = 0;
  1145.             }
  1146.           else
  1147.             /* We already incremented `optind' once;
  1148. --- 406,412 ----
  1149.           if (opterr != 0)
  1150.             fprintf (stderr, "%s: no argument for `-%c' option\n",
  1151.                  argv[0], c);
  1152. !         c = '?';
  1153.             }
  1154.           else
  1155.             /* We already incremented `optind' once;
  1156. diff -rcN grep-1.2/grep.c grep-1.3/grep.c
  1157. *** grep-1.2/grep.c    Tue Dec 13 10:54:54 1988
  1158. --- grep-1.3/grep.c    Tue Feb 28 23:05:53 1989
  1159. ***************
  1160. *** 368,376 ****
  1161.         /* If a potential backreference is indicated, try it out with
  1162.            a backtracking matcher to make sure the line is a match. */
  1163.         if (try_backref && re_search(®ex, matching_line,
  1164. !                        next_line - matching_line,
  1165.                          0,
  1166. !                        next_line - matching_line,
  1167.                          NULL) < 0)
  1168.           {
  1169.             resume = next_line;
  1170. --- 368,376 ----
  1171.         /* If a potential backreference is indicated, try it out with
  1172.            a backtracking matcher to make sure the line is a match. */
  1173.         if (try_backref && re_search(®ex, matching_line,
  1174. !                        next_line - matching_line - 1,
  1175.                          0,
  1176. !                        next_line - matching_line - 1,
  1177.                          NULL) < 0)
  1178.           {
  1179.             resume = next_line;
  1180. ***************
  1181. *** 542,548 ****
  1182.     exit(ERROR);
  1183.   }
  1184.   
  1185. ! static char version[] = "GNU e?grep, version 1.2";
  1186.   
  1187.   main(argc, argv)
  1188.        int argc;
  1189. --- 542,548 ----
  1190.     exit(ERROR);
  1191.   }
  1192.   
  1193. ! static char version[] = "GNU e?grep, version 1.3";
  1194.   
  1195.   main(argc, argv)
  1196.        int argc;
  1197. ***************
  1198. *** 679,695 ****
  1199.       break;
  1200.         }
  1201.   
  1202. !   /* Set the syntax depending on arg 0 and whether to ignore case. */
  1203. !   if (*prog == 'e')
  1204. !     {
  1205. !       regsyntax(RE_SYNTAX_EGREP, ignore_case);
  1206. !       re_set_syntax(RE_SYNTAX_EGREP);
  1207. !     }
  1208. !   else
  1209. !     {
  1210. !       regsyntax(RE_SYNTAX_GREP, ignore_case);
  1211. !       re_set_syntax(RE_SYNTAX_GREP);
  1212. !     }
  1213.   
  1214.     /* Compile the regexp according to all the options. */
  1215.     if (regexp_file)
  1216. --- 679,692 ----
  1217.       break;
  1218.         }
  1219.   
  1220. !   /* Set the syntax depending on whether we are EGREP or not. */
  1221. ! #ifdef EGREP
  1222. !   regsyntax(RE_SYNTAX_EGREP, ignore_case);
  1223. !   re_set_syntax(RE_SYNTAX_EGREP);
  1224. ! #else
  1225. !   regsyntax(RE_SYNTAX_GREP, ignore_case);
  1226. !   re_set_syntax(RE_SYNTAX_GREP);
  1227. ! #endif
  1228.   
  1229.     /* Compile the regexp according to all the options. */
  1230.     if (regexp_file)
  1231. ***************
  1232. *** 712,717 ****
  1233. --- 709,715 ----
  1234.         if (i == len)
  1235.           the_regexp = realloc(the_regexp, len *= 2);
  1236.       }
  1237. +       fclose(fp);
  1238.         /* Nuke the concluding newline so we won't match the empty string. */
  1239.         if (i > 0 && the_regexp[i - 1] == '\n')
  1240.       --i;
  1241. diff -rcN grep-1.2/grep.man grep-1.3/grep.man
  1242. *** grep-1.2/grep.man    Tue Dec 13 11:46:46 1988
  1243. --- grep-1.3/grep.man    Tue Feb 28 21:42:46 1989
  1244. ***************
  1245. *** 6,21 ****
  1246.   .B grep
  1247.   [
  1248.   .B \-CVbchilnsvwx
  1249. ! ]
  1250. ! [
  1251. ! .B \-\c
  1252. ! .I num
  1253. ! ]
  1254. ! [
  1255.   .B \-AB
  1256.   .I num
  1257. ! ]
  1258. ! [ [
  1259.   .B \-e
  1260.   ]
  1261.   .I expr
  1262. --- 6,17 ----
  1263.   .B grep
  1264.   [
  1265.   .B \-CVbchilnsvwx
  1266. ! ] [
  1267. ! .BI \- num
  1268. ! ] [
  1269.   .B \-AB
  1270.   .I num
  1271. ! ] [ [
  1272.   .B \-e
  1273.   ]
  1274.   .I expr
  1275. ***************
  1276. *** 254,260 ****
  1277.   the aforementioned BMG search for a large class of regexps.
  1278.   .PP
  1279.   Richard Stallman wrote the backtracking regexp matcher that is
  1280. ! used for \\fIdigit\fP backreferences, as well as the getopt that
  1281.   is provided for 4.2BSD sites.  The backtracking matcher was
  1282.   originally written for GNU Emacs.
  1283.   .PP
  1284. --- 250,256 ----
  1285.   the aforementioned BMG search for a large class of regexps.
  1286.   .PP
  1287.   Richard Stallman wrote the backtracking regexp matcher that is
  1288. ! used for \\\fIdigit\fP backreferences, as well as the getopt that
  1289.   is provided for 4.2BSD sites.  The backtracking matcher was
  1290.   originally written for GNU Emacs.
  1291.   .PP
  1292. diff -rcN grep-1.2/regex.c grep-1.3/regex.c
  1293. *** grep-1.2/regex.c    Sun Oct 16 14:55:19 1988
  1294. --- grep-1.3/regex.c    Tue Feb 28 17:44:59 1989
  1295. ***************
  1296. *** 1,106 ****
  1297. ! /* Extended regular expression matching and search.
  1298. !    Copyright (C) 1985 Free Software Foundation, Inc.
  1299.   
  1300. !                NO WARRANTY
  1301.   
  1302. -   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  1303. - NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  1304. - WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  1305. - RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  1306. - WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  1307. - BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  1308. - FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  1309. - AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  1310. - DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  1311. - CORRECTION.
  1312.   
  1313. !  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  1314. ! STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  1315. ! WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  1316. ! LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  1317. ! OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  1318. ! USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  1319. ! DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  1320. ! A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  1321. ! PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  1322. ! DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  1323. ! 
  1324. !         GENERAL PUBLIC LICENSE TO COPY
  1325. ! 
  1326. !   1. You may copy and distribute verbatim copies of this source file
  1327. ! as you receive it, in any medium, provided that you conspicuously and
  1328. ! appropriately publish on each copy a valid copyright notice "Copyright
  1329. ! (C) 1985 Free Software Foundation, Inc."; and include following the
  1330. ! copyright notice a verbatim copy of the above disclaimer of warranty
  1331. ! and of this License.  You may charge a distribution fee for the
  1332. ! physical act of transferring a copy.
  1333. ! 
  1334. !   2. You may modify your copy or copies of this source file or
  1335. ! any portion of it, and copy and distribute such modifications under
  1336. ! the terms of Paragraph 1 above, provided that you also do the following:
  1337. ! 
  1338. !     a) cause the modified files to carry prominent notices stating
  1339. !     that you changed the files and the date of any change; and
  1340. ! 
  1341. !     b) cause the whole of any work that you distribute or publish,
  1342. !     that in whole or in part contains or is a derivative of this
  1343. !     program or any part thereof, to be licensed at no charge to all
  1344. !     third parties on terms identical to those contained in this
  1345. !     License Agreement (except that you may choose to grant more extensive
  1346. !     warranty protection to some or all third parties, at your option).
  1347. ! 
  1348. !     c) You may charge a distribution fee for the physical act of
  1349. !     transferring a copy, and you may at your option offer warranty
  1350. !     protection in exchange for a fee.
  1351. ! 
  1352. ! Mere aggregation of another unrelated program with this program (or its
  1353. ! derivative) on a volume of a storage or distribution medium does not bring
  1354. ! the other program under the scope of these terms.
  1355. ! 
  1356. !   3. You may copy and distribute this program (or a portion or derivative
  1357. ! of it, under Paragraph 2) in object code or executable form under the terms
  1358. ! of Paragraphs 1 and 2 above provided that you also do one of the following:
  1359. ! 
  1360. !     a) accompany it with the complete corresponding machine-readable
  1361. !     source code, which must be distributed under the terms of
  1362. !     Paragraphs 1 and 2 above; or,
  1363. ! 
  1364. !     b) accompany it with a written offer, valid for at least three
  1365. !     years, to give any third party free (except for a nominal
  1366. !     shipping charge) a complete machine-readable copy of the
  1367. !     corresponding source code, to be distributed under the terms of
  1368. !     Paragraphs 1 and 2 above; or,
  1369. ! 
  1370. !     c) accompany it with the information you received as to where the
  1371. !     corresponding source code may be obtained.  (This alternative is
  1372. !     allowed only for noncommercial distribution and only if you
  1373. !     received the program in object code or executable form alone.)
  1374. ! 
  1375. ! For an executable file, complete source code means all the source code for
  1376. ! all modules it contains; but, as a special exception, it need not include
  1377. ! source code for modules which are standard libraries that accompany the
  1378. ! operating system on which the executable file runs.
  1379. ! 
  1380. !   4. You may not copy, sublicense, distribute or transfer this program
  1381. ! except as expressly provided under this License Agreement.  Any attempt
  1382. ! otherwise to copy, sublicense, distribute or transfer this program is void and
  1383. ! your rights to use the program under this License agreement shall be
  1384. ! automatically terminated.  However, parties who have received computer
  1385. ! software programs from you with this License Agreement will not have
  1386. ! their licenses terminated so long as such parties remain in full compliance.
  1387. ! 
  1388. !   5. If you wish to incorporate parts of this program into other free
  1389. ! programs whose distribution conditions are different, write to the Free
  1390. ! Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  1391. ! worked out a simple rule that can be stated here, but we will often permit
  1392. ! this.  We will be guided by the two goals of preserving the free status of
  1393. ! all derivatives of our free software and of promoting the sharing and reuse of
  1394. ! software.
  1395. ! 
  1396. ! 
  1397. ! In other words, you are welcome to use, share and improve this program.
  1398. ! You are forbidden to forbid anyone else to use, share and improve
  1399. ! what you give them.   Help stamp out software-hoarding!  */
  1400.   
  1401.   
  1402.   /* To test, compile with -Dtest.
  1403. --- 1,24 ----
  1404. ! /* Extended regular expression matching and search library.
  1405. !    Copyright (C) 1985, 1989 Free Software Foundation, Inc.
  1406.   
  1407. !    This program is free software; you can redistribute it and/or modify
  1408. !    it under the terms of the GNU General Public License as published by
  1409. !    the Free Software Foundation; either version 1, or (at your option)
  1410. !    any later version.
  1411. ! 
  1412. !    This program is distributed in the hope that it will be useful,
  1413. !    but WITHOUT ANY WARRANTY; without even the implied warranty of
  1414. !    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  1415. !    GNU General Public License for more details.
  1416. ! 
  1417. !    You should have received a copy of the GNU General Public License
  1418. !    along with this program; if not, write to the Free Software
  1419. !    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  1420.   
  1421.   
  1422. !    In other words, you are welcome to use, share and improve this program.
  1423. !    You are forbidden to forbid anyone else to use, share and improve
  1424. !    what you give them.   Help stamp out software-hoarding!  */
  1425.   
  1426.   
  1427.   /* To test, compile with -Dtest.
  1428. diff -rcN grep-1.2/regex.h grep-1.3/regex.h
  1429. *** grep-1.2/regex.h    Sat Aug 13 13:15:10 1988
  1430. --- grep-1.3/regex.h    Tue Feb 28 17:44:59 1989
  1431. ***************
  1432. *** 1,106 ****
  1433.   /* Definitions for data structures callers pass the regex library.
  1434. !    Copyright (C) 1985 Free Software Foundation, Inc.
  1435.   
  1436. !                NO WARRANTY
  1437.   
  1438. -   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  1439. - NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  1440. - WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  1441. - RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  1442. - WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  1443. - BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  1444. - FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  1445. - AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  1446. - DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  1447. - CORRECTION.
  1448.   
  1449. !  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  1450. ! STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  1451. ! WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  1452. ! LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  1453. ! OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  1454. ! USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  1455. ! DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  1456. ! A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  1457. ! PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  1458. ! DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  1459. ! 
  1460. !         GENERAL PUBLIC LICENSE TO COPY
  1461. ! 
  1462. !   1. You may copy and distribute verbatim copies of this source file
  1463. ! as you receive it, in any medium, provided that you conspicuously and
  1464. ! appropriately publish on each copy a valid copyright notice "Copyright
  1465. ! (C) 1985 Free Software Foundation, Inc."; and include following the
  1466. ! copyright notice a verbatim copy of the above disclaimer of warranty
  1467. ! and of this License.  You may charge a distribution fee for the
  1468. ! physical act of transferring a copy.
  1469. ! 
  1470. !   2. You may modify your copy or copies of this source file or
  1471. ! any portion of it, and copy and distribute such modifications under
  1472. ! the terms of Paragraph 1 above, provided that you also do the following:
  1473. ! 
  1474. !     a) cause the modified files to carry prominent notices stating
  1475. !     that you changed the files and the date of any change; and
  1476. ! 
  1477. !     b) cause the whole of any work that you distribute or publish,
  1478. !     that in whole or in part contains or is a derivative of this
  1479. !     program or any part thereof, to be licensed at no charge to all
  1480. !     third parties on terms identical to those contained in this
  1481. !     License Agreement (except that you may choose to grant more extensive
  1482. !     warranty protection to some or all third parties, at your option).
  1483. ! 
  1484. !     c) You may charge a distribution fee for the physical act of
  1485. !     transferring a copy, and you may at your option offer warranty
  1486. !     protection in exchange for a fee.
  1487. ! 
  1488. ! Mere aggregation of another unrelated program with this program (or its
  1489. ! derivative) on a volume of a storage or distribution medium does not bring
  1490. ! the other program under the scope of these terms.
  1491. ! 
  1492. !   3. You may copy and distribute this program (or a portion or derivative
  1493. ! of it, under Paragraph 2) in object code or executable form under the terms
  1494. ! of Paragraphs 1 and 2 above provided that you also do one of the following:
  1495. ! 
  1496. !     a) accompany it with the complete corresponding machine-readable
  1497. !     source code, which must be distributed under the terms of
  1498. !     Paragraphs 1 and 2 above; or,
  1499. ! 
  1500. !     b) accompany it with a written offer, valid for at least three
  1501. !     years, to give any third party free (except for a nominal
  1502. !     shipping charge) a complete machine-readable copy of the
  1503. !     corresponding source code, to be distributed under the terms of
  1504. !     Paragraphs 1 and 2 above; or,
  1505. ! 
  1506. !     c) accompany it with the information you received as to where the
  1507. !     corresponding source code may be obtained.  (This alternative is
  1508. !     allowed only for noncommercial distribution and only if you
  1509. !     received the program in object code or executable form alone.)
  1510. ! 
  1511. ! For an executable file, complete source code means all the source code for
  1512. ! all modules it contains; but, as a special exception, it need not include
  1513. ! source code for modules which are standard libraries that accompany the
  1514. ! operating system on which the executable file runs.
  1515. ! 
  1516. !   4. You may not copy, sublicense, distribute or transfer this program
  1517. ! except as expressly provided under this License Agreement.  Any attempt
  1518. ! otherwise to copy, sublicense, distribute or transfer this program is void and
  1519. ! your rights to use the program under this License agreement shall be
  1520. ! automatically terminated.  However, parties who have received computer
  1521. ! software programs from you with this License Agreement will not have
  1522. ! their licenses terminated so long as such parties remain in full compliance.
  1523. ! 
  1524. !   5. If you wish to incorporate parts of this program into other free
  1525. ! programs whose distribution conditions are different, write to the Free
  1526. ! Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  1527. ! worked out a simple rule that can be stated here, but we will often permit
  1528. ! this.  We will be guided by the two goals of preserving the free status of
  1529. ! all derivatives of our free software and of promoting the sharing and reuse of
  1530. ! software.
  1531. ! 
  1532. ! 
  1533. ! In other words, you are welcome to use, share and improve this program.
  1534. ! You are forbidden to forbid anyone else to use, share and improve
  1535. ! what you give them.   Help stamp out software-hoarding!  */
  1536.   
  1537.   
  1538.   /* Define number of parens for which we record the beginnings and ends.
  1539. --- 1,24 ----
  1540.   /* Definitions for data structures callers pass the regex library.
  1541. !    Copyright (C) 1985, 1989 Free Software Foundation, Inc.
  1542.   
  1543. !    This program is free software; you can redistribute it and/or modify
  1544. !    it under the terms of the GNU General Public License as published by
  1545. !    the Free Software Foundation; either version 1, or (at your option)
  1546. !    any later version.
  1547. ! 
  1548. !    This program is distributed in the hope that it will be useful,
  1549. !    but WITHOUT ANY WARRANTY; without even the implied warranty of
  1550. !    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  1551. !    GNU General Public License for more details.
  1552. ! 
  1553. !    You should have received a copy of the GNU General Public License
  1554. !    along with this program; if not, write to the Free Software
  1555. !    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  1556.   
  1557.   
  1558. !    In other words, you are welcome to use, share and improve this program.
  1559. !    You are forbidden to forbid anyone else to use, share and improve
  1560. !    what you give them.   Help stamp out software-hoarding!  */
  1561.   
  1562.   
  1563.   /* Define number of parens for which we record the beginnings and ends.
  1564.  
  1565.