home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / p / plbin.zip / pl / src / pl-glob.c < prev    next >
C/C++ Source or Header  |  1993-02-23  |  11KB  |  539 lines
  1. /*  pl-glob.c,v 1.4 1993/02/23 13:16:33 jan Exp
  2.  
  3.     Copyright (c) 1990 Jan Wielemaker. All rights reserved.
  4.     See ../LICENCE to find out about your rights.
  5.     jan@swi.psy.uva.nl
  6.  
  7.     Purpose: File Name Expansion
  8. */
  9.  
  10. #if __TOS__
  11. #include <tos.h>
  12. #define HIDDEN    0x02
  13. #define SUBDIR 0x10
  14. #endif
  15.  
  16. #include "pl-incl.h"
  17.  
  18. #if unix || EMX
  19. #include <sys/param.h>
  20. #include <sys/stat.h>
  21. #ifdef DIR_INCLUDE
  22. #include DIR_INCLUDE
  23. #else
  24. #include <dirent.h>
  25. #endif
  26. #ifdef DIR_INCLUDE2
  27. #include DIR_INCLUDE2
  28. #endif
  29. #ifndef IS_DIR_SEPARATOR
  30. #define IS_DIR_SEPARATOR(c)    ((c) == '/')
  31. #endif
  32. #endif
  33.  
  34.  
  35. /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  36. Unix Wildcard Matching.  Recognised:
  37.  
  38.   ?        matches one arbitrary character
  39.   *        matches any number of any character
  40.   [xa-z]    matches x and a-z
  41.   {p1,p2}    matches pattern p1 or p2
  42.  
  43.   backslash (\) escapes a character.
  44.  
  45. First the pattern is compiled into an intermediate representation.  Next
  46. this intermediate representation is matched  against  the  target.   The
  47. non-ascii  characters  are  used  to  store  control  sequences  in  the
  48. intermediate representation:
  49.  
  50.   ANY        Match any character
  51.   STAR        Match (possibly empty) sequence
  52.   ALT <offset>    Match, if fails, continue at <pc> + offset
  53.   JMP <offset>    Jump <offset> instructions
  54.   ANYOF        Next 16 bytes are bitmap
  55. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  56.  
  57. #define MAXEXPAND    1024
  58. #define NextIndex(i)    ((i) < MAXEXPAND-1 ? (i)+1 : 0)
  59.  
  60. #define MAXCODE 512
  61.  
  62. #define ANY    128
  63. #define STAR    129
  64. #define ALT    130
  65. #define JMP    131
  66. #define ANYOF    132
  67. #define EXIT    133
  68.  
  69. #define NOCURL    0
  70. #define CURL    1
  71.  
  72. #if !O_UCHAR_PREDEFINED
  73. typedef unsigned char uchar;
  74. #endif
  75.  
  76. struct bag
  77. { int     in;            /* in index */
  78.   int     out;            /* out index */
  79.   int     size;            /* number of entries */
  80.   bool     changed;        /* did bag change? */
  81.   bool     expanded;        /* Expanded bag? */
  82.   char    *bag[MAXEXPAND];    /* bag of paths */
  83. };
  84.  
  85. static struct out
  86. { int    size;
  87.   uchar    code[MAXCODE];
  88. } cbuf;
  89.  
  90. forwards char    *compile_pattern P((struct out *, char *, int));
  91. forwards bool    match_pattern P((uchar *, char *));
  92. forwards int    stringCompare P((char**, char**));
  93. forwards bool    expand P((char *, char **, int *));
  94. forwards bool    Exists P((char *));
  95. forwards char    *change_string P((char *, char *));
  96. forwards bool    expandBag P((struct bag *));
  97.  
  98. #define Output(c)    { if ( Out->size > MAXCODE-1 ) \
  99.               { warning("pattern too large"); \
  100.                 return (char *) NULL; \
  101.               } \
  102.               Out->code[Out->size++] = c; \
  103.             }
  104. #define setMap(c)    { map[(c)/8] |= 1 << ((c) % 8); }
  105.  
  106. bool
  107. compilePattern(p)
  108. char *p;
  109. { cbuf.size = 0;
  110.   if ( compile_pattern(&cbuf, p, NOCURL) == (char *) NULL )
  111.     fail;
  112.  
  113.   succeed;
  114. }
  115.  
  116.  
  117. static char *
  118. compile_pattern(Out, p, curl)
  119. struct out *Out;
  120. char *p;
  121. int curl;
  122. { char c;
  123.  
  124.   for(;;)
  125.   { switch(c = *p++)
  126.     { case EOS:
  127.     break;
  128.       case '\\':
  129.     Output(*p == EOS ? '\\' : (*p & 0x7f));
  130.     if (*p == EOS )
  131.       break;
  132.     p++;
  133.     continue;
  134.       case '?':
  135.     Output(ANY);
  136.     continue;
  137.       case '*':
  138.     Output(STAR);
  139.     continue;
  140.       case '[':
  141.     { uchar *map;
  142.       int n;
  143.  
  144.       Output(ANYOF);
  145.       map = &Out->code[Out->size];
  146.       Out->size += 16;
  147.       if ( Out->size >= MAXCODE )
  148.       { warning("Pattern too long");
  149.         return (char *) NULL;
  150.       }
  151.  
  152.       for( n=0; n < 16; n++)
  153.         map[n] = 0;
  154.  
  155.       for(;;)
  156.       { switch( c = *p++ )
  157.         { case '\\':
  158.         if ( *p == EOS )
  159.         { warning("Unmatched '['");
  160.           return (char *)NULL;
  161.         }
  162.         setMap(*p);
  163.         p++;
  164.         continue;
  165.           case ']':
  166.         break;
  167.           default:
  168.         if ( p[-1] != ']' && p[0] == '-' && p[1] != ']' )
  169.         { register int chr;
  170.  
  171.           for ( chr=p[-1]; chr <= p[1]; chr++ )
  172.             setMap(chr);
  173.           p += 2;
  174.         } else
  175.           setMap(c);
  176.         continue;
  177.         }
  178.         break;
  179.       }
  180.  
  181.       continue;
  182.     }
  183.       case '{':
  184.     { int ai, aj = -1;
  185.  
  186.       for(;;)
  187.       { Output(ALT); ai = Out->size; Output(0);
  188.         if ( (p = compile_pattern(Out, p, CURL)) == (char *) NULL )
  189.           return (char *) NULL;
  190.         if ( aj > 0 )
  191.           Out->code[aj] = Out->size - aj;
  192.         if ( *p == ',' )
  193.         { Output(JMP); aj = Out->size; Output(0);
  194.           Out->code[ai] = Out->size - ai;
  195.           Output(ALT); ai = Out->size; Output(0);
  196.           p++;
  197.         } else if ( *p == '}' )
  198.         { p++;
  199.           break;
  200.         } else
  201.         { warning("Unmatched '{'");
  202.           return (char *) NULL;
  203.         }
  204.       }
  205.       
  206.       continue;
  207.     }
  208.       case '}':
  209.       case ',':
  210.     if ( curl == CURL )
  211.     { p--;
  212.       return p;
  213.     }
  214.     /*FALLTHROUGH*/
  215.       default:
  216.     Output(c & 0x7f);
  217.     continue;
  218.     }
  219.  
  220.     Output(EXIT);
  221.     return p;
  222.   }
  223. }
  224.  
  225.  
  226. bool
  227. matchPattern(s)
  228. char *s;
  229. { return match_pattern(cbuf.code, s);
  230. }
  231.  
  232. static bool
  233. match_pattern(p, s)
  234. register uchar *p;
  235. register char *s;
  236. { register uchar c;
  237.  
  238.   for(;;)
  239.   { switch( c = *p++ )
  240.     { case EXIT:
  241.       return (*s == EOS ? TRUE : FALSE);
  242.       case ANY:                        /* ? */
  243.       if ( *s == EOS )
  244.         fail;
  245.       s++;
  246.       continue;
  247.       case ANYOF:                    /* [...] */
  248.       if ( p[*s / 8] & (1 << (*s % 8)) )
  249.       { p += 16;
  250.         s++;
  251.         continue;
  252.       }
  253.       fail;
  254.       case STAR:                    /* * */
  255.       do
  256.       { if ( match_pattern(p, s) )
  257.           succeed;
  258.       } while( *s++ );
  259.       fail;
  260.       case JMP:                        /* { ... } */
  261.       p += *p;
  262.       continue;
  263.       case ALT:
  264.       if ( match_pattern(p+1, s) )
  265.         succeed;
  266.       p += *p;
  267.       continue;      
  268.       default:                        /* character */
  269.       if ( c != (uchar) *s )
  270.         fail;
  271.       s++;
  272.       continue;
  273.     }
  274.   }
  275. }
  276.  
  277.  
  278. word
  279. pl_wildcard_match(pattern, string)
  280. Word pattern, string;
  281. { char *p, *s;
  282.  
  283.   initAllocLocal();
  284.   p = primitiveToString(*pattern, TRUE);
  285.   s = primitiveToString(*string, TRUE);
  286.   stopAllocLocal();
  287.  
  288.   if ( p == (char *)NULL || s == (char *)NULL )
  289.     return warning("wildcard_match/2: instantiation fault");
  290.  
  291.   TRY( compilePattern(p) );
  292.  
  293.   return matchPattern(s);
  294. }
  295.  
  296. /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  297. File Name Expansion.
  298. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  299.  
  300. word
  301. pl_expand_file_name(f, l)
  302. Word f, l;
  303. { char spec[MAXPATHLEN];
  304.   char *s = primitiveToString(*f, FALSE);
  305.   char *vector[MAXEXPAND];
  306.   char **v;
  307.   int filled;
  308.  
  309.   if ( s == (char *) NULL )
  310.     return warning("expand_file_name/2: instantiation fault");
  311.   if ( strlen(s) > MAXPATHLEN-1 )
  312.     return warning("expand_file_name/2: name too long");
  313.   TRY( expandVars(s, spec) );
  314.  
  315.   TRY( expand(spec, vector, &filled) );
  316.  
  317.   for( v = vector; filled > 0; filled--, v++ )
  318.   { word w;
  319.  
  320.     w = (word) lookupAtom(*v);
  321.     APPENDLIST(l, &w);
  322.   }
  323.  
  324.   CLOSELIST(l);
  325.  
  326.   succeed;
  327. }
  328.  
  329. static int
  330. stringCompare(s1, s2)
  331. register char **s1, **s2;
  332. { return strcmp(*s1, *s2);
  333. }
  334.  
  335. static bool
  336. expand(f, argv, argc)
  337. char *f;
  338. char **argv;
  339. int *argc;
  340. { struct bag b;
  341.  
  342.   b.changed = b.expanded = FALSE;
  343.   b.out = 0;            /* put the first entry in the bag */
  344.   b.in = b.size = 1;
  345.   b.bag[0] = store_string(f);
  346. #if tos                /* case insensitive: do all lower case */
  347.   strlwr(b.bag[0]);
  348. #endif
  349. /* Note for OS2: HPFS is case insensitive but case preserving. */
  350.  
  351.   do                /* expand till nothing to expand */
  352.   { b.changed = FALSE;  
  353.     TRY( expandBag(&b) );
  354.   } while( b.changed );
  355.  
  356.   { char **r = argv;
  357.  
  358.     *argc = b.size;
  359.     for( ; b.out != b.in; b.out = NextIndex(b.out) )
  360.       *r++ = change_string(b.bag[b.out], PrologPath(b.bag[b.out]));
  361.     *r = (char *) NULL;
  362.     qsort(argv, b.size, sizeof(char *), stringCompare);
  363.  
  364.     succeed;
  365.   }
  366. }
  367.  
  368. #if unix || EMX
  369. static bool
  370. Exists(path)
  371. char *path;
  372. { struct stat buf;
  373.   extern int stat();
  374.  
  375.   if ( stat(OsPath(path), &buf) == -1 )
  376.     fail;
  377.  
  378.   succeed;
  379. }
  380. #endif
  381.  
  382. #if tos
  383. static bool
  384. Exists(path)
  385. char *path;
  386. { struct ffblk buf;
  387.  
  388.   DEBUG(2, printf("Checking existence of %s ... ", path));
  389.   if ( findfirst(OsPath(path), &buf, SUBDIR|HIDDEN) == 0 )
  390.   { DEBUG(2, printf("yes\n"));
  391.     succeed;
  392.   }
  393.   DEBUG(2, printf("no\n"));
  394.  
  395.   fail;
  396. }
  397. #endif
  398.  
  399. static char *
  400. change_string(old, new)
  401. char *old, *new;
  402. { return store_string(new);
  403. }
  404.  
  405. static bool
  406. expandBag(b)
  407. struct bag *b;
  408. { int high = b->in;
  409.  
  410.   for( ; b->out != high; b->out = NextIndex(b->out) )
  411.   { char *head = b->bag[b->out];
  412.     char *tail;
  413.     register char *s = head;
  414.     
  415.     for(;;)
  416.     { switch( *s++ )
  417.       { case EOS:                /* no special characters */
  418.       if ( b->expanded == FALSE || Exists(b->bag[b->out]) )
  419.       { b->bag[b->in] = b->bag[b->out];
  420.         b->in = NextIndex(b->in);
  421.       } else
  422.       { b->size--;
  423.       }
  424.       goto next_bag;
  425. #if tos || OS2
  426.     case '\\':
  427. #endif
  428.     case '/':                /* no specials sofar */
  429.       head = s;
  430.       continue;
  431.     case '[':                /* meta characters: expand */
  432.     case '{':
  433.     case '?':
  434.     case '*':
  435.       break;
  436.     default:
  437.       continue;
  438.       }
  439.       break;
  440.     }
  441.  
  442.     b->expanded = b->changed = TRUE;
  443.     b->size--;
  444.     for( tail=s; *tail && !IS_DIR_SEPARATOR(*tail); tail++ )
  445.       ;
  446.  
  447. /*  By now, head points to the start of the path holding meta characters,
  448.     while tail points to the tail:
  449.  
  450.     ..../meta*path/....
  451.      ^        ^
  452.        head     tail
  453. */
  454.  
  455.     { char prefix[MAXPATHLEN];
  456.       char expanded[MAXPATHLEN];
  457.       char *path;
  458.       char *s, *q;
  459.       int dot;
  460.  
  461.       for( q=prefix, s=b->bag[b->out]; s < head; )
  462.     *q++ = *s++;
  463.       *q = EOS;
  464.       path = (prefix[0] == EOS ? "." : prefix);
  465.  
  466.       for( q=expanded, s=head; s < tail; )
  467.         *q++ = *s++;
  468.       *q = EOS;
  469.  
  470.       if ( compilePattern(expanded) == FALSE )        /* syntax error */
  471.         fail;
  472.       dot = (expanded[0] == '.');            /* do dots as well */
  473.  
  474. #if unix || EMX
  475.       { DIR *d;
  476. #if O_STRUCT_DIRECT
  477.     struct direct *e;
  478.     extern struct direct *readdir();
  479. #else
  480.     struct dirent *e;
  481.     extern struct dirent *readdir();
  482. #endif
  483.     extern DIR *opendir();
  484.  
  485.     if ( (d = opendir(OsPath(path))) != (DIR *)NULL )
  486.     { for(e=readdir(d); e; e = readdir(d))
  487.       { if ( (dot || e->d_name[0] != '.') && matchPattern(e->d_name) )
  488.         { strcpy(expanded, prefix);
  489.           strcat(expanded, e->d_name);
  490.           strcat(expanded, tail);
  491.  
  492.           b->bag[b->in] = change_string(b->bag[b->out], expanded);
  493.           b->in = NextIndex(b->in);
  494.           b->size++;
  495.           if ( b->in == b->out )
  496.         return warning("Too many matches");
  497.         }
  498.       }
  499.       closedir(d);
  500.     }
  501.       }
  502. #endif
  503.  
  504. #if tos
  505.       { char dpat[MAXPATHLEN];
  506.     struct ffblk buf;
  507.     int r;
  508.  
  509.     strcpy(dpat, path);
  510.     strcat(dpat, "\\*.*");
  511.  
  512.     DEBUG(2, printf("match path = %s\n", dpat));
  513.     for(r=findfirst(OsPath(dpat), &buf, SUBDIR|HIDDEN); r == 0; r=findnext(&buf))
  514.     { char *name = buf.ff_name;
  515.       strlwr(name);        /* match at lower case */
  516.  
  517.       DEBUG(2, printf("found %s\n", name));
  518.       if ( (dot || name[0] != '.') && matchPattern(name) )
  519.       { strcpy(expanded, prefix);
  520.         strcat(expanded, name);
  521.         strcat(expanded, tail);
  522.  
  523.         DEBUG(2, printf("%s matches pattern\n", name));
  524.         b->bag[b->in] = change_string(b->bag[b->out], expanded);
  525.         b->in = NextIndex(b->in);
  526.         b->size++;
  527.         if ( b->in == b->out )
  528.           return warning("Too many matches");
  529.       }
  530.     }
  531.       }
  532. #endif /* tos */
  533.     }
  534.   next_bag:;
  535.   }
  536.  
  537.   succeed;
  538. }
  539.