glob.c (6534B)
1 /* glob.c: rc's (ugly) globber. This code is not elegant, but it works */ 2 3 #include "rc.h" 4 #include "stat.h" 5 6 /* Lifted from autoconf documentation.*/ 7 #if HAVE_DIRENT_H 8 # include <dirent.h> 9 # define NAMLEN(dirent) strlen((dirent)->d_name) 10 #else 11 # define dirent direct 12 # define NAMLEN(dirent) (dirent)->d_namlen 13 # if HAVE_SYS_NDIR_H 14 # include <sys/ndir.h> 15 # endif 16 # if HAVE_SYS_DIR_H 17 # include <sys/dir.h> 18 # endif 19 # if HAVE_NDIR_H 20 # include <ndir.h> 21 # endif 22 #endif 23 24 static List *dmatch(char *, char *, char *); 25 static List *doglob(char *, char *); 26 static List *lglob(List *, char *, char *, size_t); 27 static List *sort(List *); 28 29 /* 30 Matches a list of words s against a list of patterns p. Returns true iff 31 a pattern in p matches a word in s. () matches (), but otherwise null 32 patterns match nothing. 33 */ 34 35 extern bool lmatch(List *s, List *p) { 36 List *q; 37 if (s == NULL) { 38 if (p == NULL) /* null matches null */ 39 return TRUE; 40 for (; p != NULL; p = p->n) /* one or more stars match null */ 41 if (strspn(p->w, "*") == strlen(p->w) && 42 p->m != NULL && strlen(p->m) == strlen(p->w)) 43 return TRUE; 44 return FALSE; 45 } 46 for (; s != NULL; s = s->n) 47 for (q = p; q != NULL; q = q->n) 48 if (match(q->w, q->m, s->w)) 49 return TRUE; 50 return FALSE; 51 } 52 53 /* 54 Globs a list; checks to see if each element in the list has a metacharacter. If it 55 does, it is globbed, and the output is sorted. 56 */ 57 58 extern List *glob(List *s) { 59 List *top, *r; 60 bool meta; 61 for (r = s, meta = FALSE; r != NULL; r = r->n) 62 if (r->m != NULL) 63 meta = TRUE; 64 if (!meta) 65 return s; /* don't copy lists with no metacharacters in them */ 66 for (top = r = NULL; s != NULL; s = s->n) { 67 if (s->m == NULL) { /* no metacharacters; just tack on to the return list */ 68 if (top == NULL) 69 top = r = nnew(List); 70 else 71 r = r->n = nnew(List); 72 r->w = s->w; 73 } else { 74 if (top == NULL) 75 top = r = sort(doglob(s->w, s->m)); 76 else 77 r->n = sort(doglob(s->w, s->m)); 78 while (r->n != NULL) 79 r = r->n; 80 } 81 } 82 r->n = NULL; 83 return top; 84 } 85 86 /* Matches a pattern p against the contents of directory d */ 87 88 static List *dmatch(char *d, char *p, char *m) { 89 bool matched; 90 List *top, *r; 91 static DIR *dirp; 92 static struct dirent *dp; 93 static struct stat s; 94 int i; 95 96 /* 97 return a match if there are no metacharacters; allows globbing through 98 directories with no read permission. make sure the file exists, though. 99 */ 100 matched = TRUE; 101 if (m != NULL) 102 for (i = 0; p[i] != '\0'; i++) 103 if (m[i]) { 104 matched = FALSE; 105 break; 106 } 107 108 if (matched) { 109 char *path = nprint("%s/%s", d, p); 110 if (lstat(path, &s) < 0) 111 return NULL; 112 r = nnew(List); 113 r->w = ncpy(p); 114 r->m = NULL; 115 r->n = NULL; 116 return r; 117 } 118 119 top = r = NULL; 120 if (*d == '\0') d = "/"; 121 if ((dirp = opendir(d)) == NULL) 122 return NULL; 123 /* opendir succeeds on regular files on some systems, so the stat() call is necessary (sigh) */ 124 if (stat(d, &s) < 0 || (s.st_mode & S_IFMT) != S_IFDIR) { 125 closedir(dirp); 126 return NULL; 127 } 128 while ((dp = readdir(dirp)) != NULL) 129 if ((*dp->d_name != '.' || *p == '.') && match(p, m, dp->d_name)) { /* match ^. explicitly */ 130 matched = TRUE; 131 if (top == NULL) 132 top = r = nnew(List); 133 else 134 r = r->n = nnew(List); 135 r->w = ncpy(dp->d_name); 136 r->m = NULL; 137 } 138 closedir(dirp); 139 if (!matched) 140 return NULL; 141 r->n = NULL; 142 return top; 143 } 144 145 /* 146 lglob() globs a pattern against a list of directory roots. e.g., (/tmp /usr /bin) "*" 147 will return a list with all the files in /tmp, /usr, and /bin. NULL on no match. 148 slashcount indicates the number of slashes to stick between the directory and the 149 matched name. e.g., for matching ////tmp/////foo* 150 */ 151 152 static List *lglob(List *s, char *p, char *m, size_t slashcount) { 153 List *q, *r, *top, foo; 154 static struct { 155 List l; 156 size_t size; 157 } slash; 158 if (slashcount+1 > slash.size) { 159 slash.size = 2*(slashcount+1); 160 slash.l.w = erealloc(slash.l.w, slash.size); 161 } 162 slash.l.w[slashcount] = '\0'; 163 while (slashcount > 0) 164 slash.l.w[--slashcount] = '/'; 165 for (top = r = NULL; s != NULL; s = s->n) { 166 q = dmatch(s->w, p, m); 167 if (q != NULL) { 168 foo.w = s->w; 169 foo.m = NULL; 170 foo.n = NULL; 171 if (!(s->w[0] == '/' && s->w[1] == '\0')) /* need to separate */ 172 q = concat(&slash.l, q); /* dir/name with slash */ 173 q = concat(&foo, q); 174 if (r == NULL) 175 top = r = q; 176 else 177 r->n = q; 178 while (r->n != NULL) 179 r = r->n; 180 } 181 } 182 return top; 183 } 184 185 /* 186 Doglob globs a pathname in pattern form against a unix path. Returns the original 187 pattern (cleaned of metacharacters) on failure, or the globbed string(s). 188 */ 189 190 static List *doglob(char *w, char *m) { 191 static char *dir = NULL, *pattern = NULL, *metadir = NULL, *metapattern = NULL; 192 static size_t dsize = 0; 193 char *d, *p, *md, *mp; 194 size_t psize; 195 char *s = w; 196 List firstdir; 197 List *matched; 198 if ((psize = strlen(w) + 1) > dsize || dir == NULL) { 199 efree(dir); efree(pattern); efree(metadir); efree(metapattern); 200 dir = ealloc(psize); 201 pattern = ealloc(psize); 202 metadir = ealloc(psize); 203 metapattern = ealloc(psize); 204 dsize = psize; 205 } 206 d = dir; 207 p = pattern; 208 md = metadir; 209 mp = metapattern; 210 while (*s != '/' && *s != '\0') { 211 *d++ = *s++; /* get first directory component */ 212 *md++ = *m++; 213 } 214 *d = '\0'; 215 /* 216 Special case: no slashes in the pattern, i.e., open the current directory. 217 Remember that w cannot consist of slashes alone (the other way *s could be 218 zero) since doglob gets called iff there's a metacharacter to be matched 219 */ 220 if (*s == '\0') { 221 matched = dmatch(".", dir, metadir); 222 goto end; 223 } 224 if (*w == '/') { 225 firstdir.w = dir; 226 firstdir.m = metadir; 227 firstdir.n = NULL; 228 matched = &firstdir; 229 } else { 230 /* 231 we must glob against current directory, 232 since the first character is not a slash. 233 */ 234 matched = dmatch(".", dir, metadir); 235 } 236 do { 237 size_t slashcount; 238 sigchk(); 239 for (slashcount = 0; *s == '/'; s++, m++) 240 slashcount++; /* skip slashes */ 241 while (*s != '/' && *s != '\0') 242 *p++ = *s++, *mp++ = *m++; /* get pattern */ 243 *p = '\0'; 244 matched = lglob(matched, pattern, metapattern, slashcount); 245 p = pattern, mp = metapattern; 246 } while (*s != '\0'); 247 end: if (matched == NULL) { 248 matched = nnew(List); 249 matched->w = w; 250 matched->m = NULL; 251 matched->n = NULL; 252 } 253 return matched; 254 } 255 256 static List *sort(List *s) { 257 size_t nel = listnel(s); 258 if (nel > 1) { 259 char **a; 260 List *t; 261 qsort(a = list2array(s, FALSE), nel, sizeof(char *), starstrcmp); 262 for (t = s; t != NULL; t = t->n) 263 t->w = *a++; 264 } 265 return s; 266 }