home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume4 / se / part6 / pat / pat.c < prev   
Encoding:
C/C++ Source or Header  |  1986-11-30  |  11.7 KB  |  550 lines
  1. /*
  2. ** pat.c
  3. **
  4. ** pattern matching subroutines for the se screen editor.
  5. ** knows about both Unix and SWT style patterns.
  6. **
  7. ** routines declared static are not necessary for the rest
  8. ** of the editor, therefore make them static in the name
  9. ** of modularity.
  10. */
  11.  
  12. #include <stdio.h>
  13. #include <ctype.h>
  14. #include "../constdefs.h"
  15.  
  16. /* Definitions used only for pattern matching */
  17.  
  18. #define AND             '&'
  19. #define CCL             '['
  20. #define CCLEND          ']'
  21. #define CHAR            'a'
  22. #define CLOSIZE         1
  23. #define CLOSURE         '*'
  24. #define DASH            '-'
  25. #define DITTO           0200
  26. #define EOL             '$'
  27. #define NCCL            'n'
  28. #define NEWLINE         '\n'
  29. #define TAB             '\t'
  30.  
  31. /* variables which are changeable if using unix style or swt style */
  32. /* initially unix style */
  33. static char ANY = '.';
  34. static char BOL = '^';
  35. static char NOTINCCL = '^';
  36. static char START_TAG = '(';
  37. static char STOP_TAG = ')';
  38. static char ESCAPE = '\\';
  39. static int unix_style = YES;
  40.  
  41. /* Array dimensions and other limit values */
  42. #define MAXLINE         128
  43. #define MAXPAT          128
  44.  
  45. /* Pattern matching subroutines: */
  46.  
  47. /* set_patterns -- tell the pattern routines what style patterns we're using */
  48.  
  49. set_patterns(tounix)
  50. int tounix;
  51. {
  52.     if (tounix == YES)
  53.     {
  54.         ANY = '.';
  55.         BOL = '^';
  56.         NOTINCCL = '^';
  57.         START_TAG = '(';
  58.         STOP_TAG = ')';
  59.         ESCAPE = '\\';
  60.         unix_style = YES;
  61.     }
  62.     else
  63.     {
  64.         ANY = '?';
  65.         BOL = '%';
  66.         NOTINCCL = '~';
  67.         START_TAG = '{';
  68.         STOP_TAG = '}';
  69.         ESCAPE = '@';
  70.         unix_style = NO;
  71.     }
  72. }
  73.  
  74. /* match () --- find match anywhere on line */
  75.  
  76. match (lin, pat)
  77. register char lin[];
  78. register char pat[];
  79. {
  80.     int junk[9];
  81.     register char *pc;
  82.  
  83.     for (pc = lin; *pc != EOS; pc++)
  84.         if (amatch (lin, pc - lin, pat, junk, junk) >= 0)
  85.             return (YES);
  86.     return (NO);
  87. }
  88.  
  89.  
  90. /* amatch() --- (recursive) look for match starting at lin[from] */
  91.  
  92. amatch(lin, from, pat, tagbeg, tagend)
  93. int from, tagbeg[], tagend[];
  94. char lin[], pat[];
  95. {
  96.     char *ch, *lastc;
  97.     register char *ppat;
  98.     int k;
  99.  
  100.     lastc = lin + from;     /* next unexamined input character */
  101.     for (ppat = pat; *ppat != EOS; ppat += patsiz (ppat))
  102.         if (*ppat == CLOSURE)   /* a closure entry */
  103.         {
  104.             ppat++;
  105.             for (ch = lastc; *ch != EOS; )
  106.                 /* match as many as possible */
  107.                 if (omatch (lin, &ch, ppat) == NO)
  108.                     break;
  109.             /*
  110.              * ch now points to character that made us fail
  111.              * try to match rest of pattern against rest of input
  112.              * shrink the closure by 1 after each failure
  113.              */
  114.             for (ppat += patsiz (ppat); ch >= lastc; ch--)
  115.                 /* successful match of rest of pattern */
  116.                 if ((k = amatch (lin, ch - lin, ppat, tagbeg,
  117.                     tagend)) >= 0)
  118.                     break;
  119.             lastc = lin + k;        /* if k < 0, failure;
  120.                          * if k >= 0, success */
  121.             break;
  122.         }
  123.         else if (*ppat == START_TAG)
  124.             tagbeg[*(ppat + 1)] = lastc - lin;
  125.         else if (*ppat == STOP_TAG)
  126.             tagend[*(ppat + 1)] = lastc - lin;
  127.             /* non-closure */
  128.         else if (omatch (lin, &lastc, ppat) == NO)
  129.             return (-1);
  130.         /* else
  131.             omatch succeeded */
  132.     return (lastc - lin);
  133. }
  134.  
  135.  
  136. /* omatch () --- try to match a single pattern at ppat */
  137.  
  138. static omatch (lin, adplin, ppat)
  139. char lin[], **adplin, *ppat;
  140. {
  141.     register char *plin;
  142.     register int bump, retval;
  143.  
  144.     plin = *adplin;
  145.     retval = NO;
  146.     if (*plin == EOS)
  147.         return (retval);
  148.     bump = -1;
  149.     if (*ppat == CHAR)
  150.     {
  151.         if (*plin == *(ppat + 1))
  152.             bump = 1;
  153.     }
  154.  
  155.     else if (*ppat == BOL)
  156.     {
  157.         if (plin == lin)
  158.             bump = 0;
  159.     }
  160.  
  161.     else if (*ppat == ANY)
  162.     {
  163.         if (*plin != NEWLINE)
  164.             bump = 1;
  165.     }
  166.  
  167.     else if (*ppat == EOL)
  168.     {
  169.         if (*plin == NEWLINE)
  170.             bump = 0;
  171.     }
  172.  
  173.     else if(*ppat == CCL)
  174.     {
  175.         if (locate (*plin, ppat + 1) == YES)
  176.             bump = 1;
  177.     }
  178.  
  179.     else if(*ppat == NCCL)
  180.     {
  181.         if (*plin != NEWLINE && locate (*plin, ppat + 1) == NO)
  182.             bump = 1;
  183.     }
  184.     else
  185.         error ("in omatch: can't happen.");
  186.  
  187.     if (bump >= 0)
  188.     {
  189.         *adplin += bump;
  190.         retval = YES;
  191.     }
  192.     return (retval);
  193. }
  194.  
  195.  
  196. /* locate () --- look for c in char class at ppat */
  197.  
  198. static locate (c, ppat)
  199. register char c, *ppat;
  200. {
  201.     register char *pclas;
  202.  
  203.     /* size of class is at ppat, characters follow */
  204.     for (pclas = ppat + *ppat; pclas > ppat; pclas--)
  205.         if (c == *pclas)
  206.             return (YES);
  207.     return (NO);
  208. }
  209.  
  210.  
  211. /* patsiz () --- returns size of pattern entry at ppat */
  212.  
  213. static patsiz (ppat)
  214. register char *ppat;
  215. {
  216.  
  217.     if (*ppat == CHAR || *ppat == START_TAG || *ppat == STOP_TAG)
  218.         return (2);
  219.  
  220.     else if (*ppat == BOL || *ppat == EOL || *ppat == ANY)
  221.         return (1);
  222.  
  223.     else if (*ppat == CCL || *ppat == NCCL)
  224.         return (*(ppat + 1) + 2);
  225.  
  226.     else if (*ppat == CLOSURE)
  227.         return (CLOSIZE);
  228.  
  229.     else
  230.         error ("in patsiz: can't happen.");
  231. }
  232.  
  233.  
  234. /* makpat () --- make pattern from arg[from], terminate at delim */
  235.  
  236. makpat (arg, from, delim, pat)
  237. char arg[], delim, pat[];
  238. int from;
  239. {
  240.     char ch, esc ();
  241.     int argsub, junk, lastsub, ls, patsub, tag_nest, tag_num, tag_stack[9];
  242.  
  243.     lastsub = patsub = 0;
  244.     tag_num = -1;
  245.     tag_nest = -1;
  246.     for (argsub = from; arg[argsub] != delim && arg[argsub] != EOS;
  247.         argsub++)
  248.     {
  249.         ls = patsub;
  250.         if (arg[argsub] == ANY)
  251.             junk = addset (ANY, pat, &patsub, MAXPAT);
  252.         else if (arg[argsub] == BOL && argsub == from)
  253.             junk = addset (BOL, pat, &patsub, MAXPAT);
  254.         else if (arg[argsub] == EOL && arg[argsub + 1] == delim)
  255.             junk = addset (EOL, pat, &patsub, MAXPAT);
  256.         else if (arg[argsub] == CCL)
  257.         {
  258.             if (getccl (arg, &argsub, pat, &patsub) == ERR)
  259.                 return (ERR);
  260.         }
  261.         else if (arg[argsub] == CLOSURE && argsub > from)
  262.         {
  263.             ls = lastsub;
  264.             if (pat[ls] == BOL || pat[ls] == EOL ||
  265.                 pat[ls] == CLOSURE || pat[ls] == START_TAG ||
  266.                 pat[ls] == STOP_TAG)
  267.                 break;
  268.             stclos (pat, &patsub, &lastsub);
  269.         }
  270.         else if (start_tag(arg, &argsub))
  271.                 /* start_tag knows about unix or not */
  272.         {
  273.             /* too many tagged sub-patterns */
  274.             if (tag_num >= 8)
  275.                 break;
  276.             tag_num++;
  277.             tag_nest++;
  278.             tag_stack[tag_nest] = tag_num;
  279.             junk = addset (START_TAG, pat, &patsub, MAXPAT);
  280.             junk = addset (tag_num, pat, &patsub, MAXPAT);
  281.         }
  282.         else if (stop_tag(arg, &argsub) && tag_nest > -1)
  283.                 /* stop_tag knows about unix or not */
  284.         {
  285.             junk = addset (STOP_TAG, pat, &patsub, MAXPAT);
  286.             junk = addset (tag_stack[tag_nest], pat, &patsub, MAXPAT);
  287.             tag_nest--;
  288.         }
  289.         else
  290.         {
  291.             junk = addset (CHAR, pat, &patsub, MAXPAT);
  292.  
  293.             /* don't allow match of newline other than via $ */
  294.             if ((ch = esc(arg, &argsub)) == NEWLINE)
  295.                 return (ERR);
  296.             junk = addset (ch, pat, &patsub, MAXPAT);
  297.         }
  298.         lastsub = ls;
  299.     }
  300.  
  301.     if (arg[argsub] != delim)               /* terminated early */
  302.         return (ERR);
  303.     else if (addset (EOS, pat, &patsub, MAXPAT) == NO)      /* no room */
  304.         return (ERR);
  305.     else if (tag_nest != -1)
  306.         return (ERR);
  307.     else
  308.         return (argsub);
  309. }
  310.  
  311.  
  312. /* getccl () --- expand char class at arg[*pasub] into pat[*pindex] */
  313.  
  314. static getccl (arg, pasub, pat, pindex)
  315. char arg[], pat[];
  316. int *pasub, *pindex;
  317. {
  318.     int junk, start;
  319.  
  320.     (*pasub)++;             /* skip over [ */
  321.     if (arg[*pasub] == NOTINCCL)
  322.     {
  323.         junk = addset (NCCL, pat, pindex, MAXPAT);
  324.         (*pasub)++;
  325.     }
  326.     else
  327.         junk = addset (CCL, pat, pindex, MAXPAT);
  328.  
  329.     start = *pindex;
  330.     junk = addset (0, pat, pindex, MAXPAT); /* leave room for count */
  331.     filset (CCLEND, arg, pasub, pat, pindex, MAXPAT);
  332.     pat[start] = *pindex - start - 1;
  333.  
  334.     if (arg[*pasub] == CCLEND)
  335.         return (OK);
  336.     else
  337.         return (ERR);
  338. }
  339.  
  340.  
  341. /* stclos () --- insert closure entry at pat[*ppatsub] */
  342.  
  343. static stclos (pat, ppatsub, plastsub)
  344. char pat[];
  345. int *ppatsub, *plastsub;
  346. {
  347.     int i, j, junk;
  348.  
  349.     for (i = *ppatsub - 1; i >= *plastsub; i--)     /* make a hole */
  350.     {
  351.         j = i + CLOSIZE;
  352.         junk = addset (pat[i], pat, &j, MAXPAT);
  353.     }
  354.     *ppatsub += CLOSIZE;
  355.     /* put closure in it */
  356.     junk = addset (CLOSURE, pat, plastsub, MAXPAT);
  357. }
  358.  
  359.  
  360. /* maksub () --- make substitution string in sub */
  361.  
  362. maksub (arg, from, delim, sub)
  363. char arg[], delim, sub[];
  364. int from;
  365. {
  366.     char esc ();
  367.     int argsub, index, junk;
  368.  
  369.     index = 0;
  370.     for (argsub = from; arg[argsub] != delim && arg[argsub] != EOS;
  371.         argsub++)
  372.         if (arg[argsub] == AND)
  373.         {
  374.             junk = addset (DITTO, sub, &index, MAXPAT);
  375.             junk = addset (0, sub, &index, MAXPAT);
  376.         }
  377.         else if (arg[argsub] == ESCAPE && isdigit (arg[argsub + 1]))
  378.         {
  379.             argsub++;
  380.             junk = addset (DITTO, sub, &index, MAXPAT);
  381.             junk = addset (arg[argsub] - '0', sub, &index, MAXPAT);
  382.         }
  383.         else
  384.             junk = addset (esc (arg, &argsub), sub, &index, MAXPAT);
  385.     if (arg[argsub] != delim)               /* missing delimeter */
  386.         return (ERR);
  387.     else if (addset (EOS, sub, &index, MAXPAT) == NO)       /* no room */
  388.         return (ERR);
  389.     else
  390.         return (argsub);
  391. }
  392.  
  393.  
  394. /* catsub () --- add replacement text to end of new */
  395.  
  396. catsub (lin, from, to, sub, new, k, maxnew)
  397. register char lin[], new[], sub[];
  398. int from[], *k, maxnew, to[];
  399. {
  400.     int junk, ri;
  401.     register int i, j;
  402.  
  403.     for (i = 0; sub[i] != EOS; i++)
  404.         if ((sub[i] & 0xff) == DITTO)
  405.         {
  406.             ri = sub[++i];
  407.             for (j = from[ri]; j < to[ri]; j++)
  408.                 junk = addset (lin[j], new, k, maxnew);
  409.         }
  410.         else
  411.             junk = addset (sub[i], new, k, maxnew);
  412. }
  413.  
  414.  
  415. /* filset () --- expand set at array[*pasub] into set[*pindex], stop at delim */
  416.  
  417. filset (delim, array, pasub, set, pindex, maxset)
  418. char array[], delim, set[];
  419. int maxset, *pasub, *pindex;
  420. {
  421.     char esc ();
  422.     int junk;
  423.     static char digits[] = "0123456789";
  424.     static char lowalf[] = "abcdefghijklmnopqrstuvwxyz";
  425.     static char upalf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  426.  
  427.     for ( ; array[*pasub] != delim && array[*pasub] != EOS; (*pasub)++)
  428.         if (array[*pasub] == ESCAPE)
  429.             junk = addset (esc (array, pasub), set, pindex, maxset);
  430.         else if (array[*pasub] != DASH)
  431.             junk = addset (array[*pasub], set, pindex, maxset);
  432.             /* literal DASH */
  433.         else if (*pindex <= 0 || array[*pasub + 1] == EOS ||
  434.             array[*pasub + 1] == delim)
  435.             junk = addset (DASH, set, pindex, maxset);
  436.         /* else if (index (digits, set[*pindex - 1]) >= 0) */
  437.         else if (isdigit(set[*pindex - 1]))
  438.             dodash (digits, array, pasub, set, pindex, maxset);
  439.         /* else if(index (lowalf, set[*pindex - 1]) >= 0) */
  440.         else if (islower(set[*pindex - 1]))
  441.             dodash (lowalf, array, pasub, set, pindex, maxset);
  442.         /* else if (index (upalf, set[*pindex - 1]) >= 0) */
  443.         else if (isupper(set[*pindex - 1]))
  444.             dodash (upalf, array, pasub, set, pindex, maxset);
  445.         else
  446.             junk = addset (DASH, set, pindex, maxset);
  447. }
  448.  
  449.  
  450. /*
  451. ** dodash () --- expand array[*pasub - 1]-array[*pasub + 1] into set[*pindex],
  452. **               from valid
  453. */
  454.  
  455. static dodash (valid, array, pasub, set, pindex, maxset)
  456. char array[], set[], valid[];
  457. int maxset, *pasub, *pindex;
  458. {
  459.     char esc ();
  460.     int junk, k, limit;
  461.  
  462.     (*pasub)++;
  463.     (*pindex)--;
  464.     limit = index (valid, esc (array, pasub));
  465.     for (k = index (valid, set[*pindex]); k <= limit; k++)
  466.         junk = addset (valid[k], set, pindex, maxset);
  467. }
  468.  
  469.  
  470. /* addset () --- put c in set[*pindex];  if it fits, increment *pindex */
  471.  
  472. addset (c, set, pindex, maxsiz)
  473. int maxsiz, *pindex;
  474. char c, set[];
  475. {
  476.  
  477.     if (*pindex >= maxsiz)
  478.         return (NO);
  479.     else
  480.     {
  481.         set[(*pindex)++] = c;
  482.         return (YES);
  483.     }
  484. }
  485.  
  486.  
  487. /* esc () --- map array[*pindex] into escaped character if appropriate */
  488.  
  489. char esc (array, pindex)
  490. char array[];
  491. int *pindex;
  492. {
  493.  
  494.     if (array[*pindex] != ESCAPE)
  495.         return (array[*pindex]);
  496.     else if (array[*pindex + 1] == EOS)     /* ESCAPE not special at end */
  497.         return (ESCAPE);
  498.     else
  499.     {
  500.         if (array[++(*pindex)] == 'n')
  501.             return (NEWLINE);
  502.         else if (array[*pindex] == 't')
  503.             return (TAB);
  504.         else
  505.             return (array[*pindex]);
  506.     }
  507. }
  508.  
  509. /* start_tag --- determine if we've seen the start of a tagged pattern */
  510.  
  511. static int start_tag(arg, argsub)
  512. char *arg;
  513. int *argsub;
  514. {
  515.     if (unix_style)
  516.         if (arg[*argsub] == ESCAPE && arg[*argsub + 1] == START_TAG)
  517.         {
  518.             (*argsub)++;
  519.             return (YES);
  520.         }
  521.         else
  522.             return (NO);
  523.     else
  524.         if (arg[*argsub] == START_TAG)
  525.             return (YES);
  526.         else
  527.             return (NO);
  528. }
  529.  
  530. /* stop_tag --- determine if we've seen the end of a tagged pattern */
  531.  
  532. static int stop_tag(arg, argsub)
  533. char *arg;
  534. int *argsub;
  535. {
  536.     if (unix_style)
  537.         if (arg[*argsub] == ESCAPE && arg[*argsub + 1] == STOP_TAG)
  538.         {
  539.             (*argsub)++;
  540.             return (YES);
  541.         }
  542.         else
  543.             return (NO);
  544.     else
  545.         if (arg[*argsub] == STOP_TAG)
  546.             return (YES);
  547.         else
  548.             return (NO);
  549. }
  550.