1 /* @(#)expand.c 1.58 19/06/26 Copyright 1985-2019 J. Schilling */
2 #include <schily/mconfig.h>
3 #ifndef lint
4 static UConst char sccsid[] =
5 "@(#)expand.c 1.58 19/06/26 Copyright 1985-2019 J. Schilling";
6 #endif
7 /*
8 * Expand a pattern (do shell name globbing)
9 *
10 * Copyright (c) 1985-2019 J. Schilling
11 */
12 /*
13 * The contents of this file are subject to the terms of the
14 * Common Development and Distribution License, Version 1.0 only
15 * (the "License"). You may not use this file except in compliance
16 * with the License.
17 *
18 * See the file CDDL.Schily.txt in this distribution for details.
19 * A copy of the CDDL is also available via the Internet at
20 * http://www.opensource.org/licenses/cddl1.txt
21 *
22 * When distributing Covered Code, include this CDDL HEADER in each
23 * file and include the License file CDDL.Schily.txt from this distribution.
24 */
25
26 #include <schily/fcntl.h>
27 #include <schily/stdio.h>
28 #include <schily/string.h>
29 #include <schily/stdlib.h>
30 #include <schily/dirent.h> /* Must be before bsh.h/schily.h/libport.h */
31 #include <schily/patmatch.h>
32 #include "bsh.h"
33 #include "node.h"
34 #include "str.h"
35 #include "strsubs.h"
36
37 #ifdef DEBUG
38 #define EDEBUG(a) printf a
39 #else
40 #define EDEBUG(a)
41 #endif
42
43 static char mchars[] = "!#%*{}[]?\\";
44
45 #define exp _exp /* Some compilers do not like exp() */
46
47 LOCAL int dncmp __PR((char *s1, char *s2));
48 LOCAL char *save_base __PR((char *s, char *endptr));
49 EXPORT BOOL any_match __PR((char *s));
50 LOCAL Tnode *mklist __PR((Tnode *l));
51 LOCAL int xcmp __PR((char *s1, char *s2));
52 LOCAL void xsort __PR((char **from, char **to));
53 LOCAL Tnode *exp __PR((char *n, int i, Tnode * l, BOOL patm));
54 EXPORT Tnode *expand __PR((char *s));
55 EXPORT Tnode *bexpand __PR((char *s));
56 EXPORT int bsh_hop_dirs __PR((char *name, char **np));
57 LOCAL DIR *lopendir __PR((char *name));
58
59 LOCAL int
dncmp(s1,s2)60 dncmp(s1, s2)
61 register char *s1;
62 register char *s2;
63 {
64 for (; *s1 == *s2; s1++, s2++) {
65 if (*s1 == '\0')
66 return (0);
67 }
68 if (*s1 == '\0' && *s2 == '/')
69 return (0);
70 return (*s1 - *s2);
71 }
72
73 LOCAL char *
save_base(s,endptr)74 save_base(s, endptr)
75 register char *s;
76 register char *endptr;
77 {
78 register char *tmp;
79 register char *r;
80
81 tmp = malloc((size_t)(endptr-s+1));
82 if (tmp == (char *)NULL)
83 return (tmp);
84 for (r = tmp; s < endptr; )
85 *r++ = *s++;
86 *r = '\0';
87 return (tmp);
88 }
89
90 EXPORT BOOL
any_match(s)91 any_match(s)
92 register char *s;
93 {
94 register char *rm = mchars;
95
96 while (*s && !strchr(rm, *s))
97 s++;
98 return ((BOOL)*s);
99 }
100
101 LOCAL Tnode *
mklist(l)102 mklist(l)
103 Tnode *l;
104 {
105 register int ac;
106 register char **p;
107 register Tnode *l1;
108 register Argvec *vp;
109
110 if (l == (Tnode *)NULL)
111 return ((Tnode *)NULL);
112
113 ac = listlen(l);
114 vp = allocvec(ac);
115 if (vp == (Argvec *)NULL) {
116 freetree(l);
117 return ((Tnode *)NULL);
118 }
119 vp->av_ac = ac;
120 for (l1 = l, p = &vp->av_av[0]; --ac >= 0; ) {
121 *p++ = l1->tn_left.tn_str;
122 l1->tn_type = STRING; /* Type LSTRING -> STRING */
123 l1 = l1->tn_right.tn_node;
124 }
125 xsort(&vp->av_av[0], &vp->av_av[vp->av_ac]);
126
127 ac = vp->av_ac;
128
129 for (l1 = l, p = &vp->av_av[0]; --ac >= 0; ) {
130 l1->tn_left.tn_str = *p++;
131 l1 = l1->tn_right.tn_node;
132 }
133 free((char *)vp);
134 return (l);
135 }
136
137 LOCAL int
xcmp(s1,s2)138 xcmp(s1, s2)
139 register char *s1;
140 register char *s2;
141 {
142 while (*s1++ == *s2)
143 if (*s2++ == 0)
144 return (0);
145 return (*--s1 - *s2);
146 }
147
148 #define USE_QSORT
149 #ifdef USE_QSORT
150 /*
151 * quicksort algorithm
152 * on array of elsize elements from lowp to hip-1
153 */
154 #define exchange(a, b) { register char *p = *(a); *(a) = *(b); *(b) = p; }
155
156 LOCAL void
xsort(lowp,hip)157 xsort(lowp, hip)
158 register char *lowp[];
159 register char *hip[];
160 {
161 register char **olp;
162 register char **ohp;
163 register char **pivp;
164
165 hip--;
166
167 while (hip > lowp) {
168 if (hip == (lowp + 1)) { /* two elements */
169 if (xcmp(*hip, *lowp) < 0)
170 exchange(lowp, hip);
171 return;
172 }
173 olp = lowp;
174 ohp = hip;
175
176 pivp = lowp+((((unsigned)(hip-lowp))+1)/2);
177 exchange(pivp, hip);
178 pivp = hip;
179 hip--; /* point past pivot element */
180
181 while (lowp <= hip) {
182 while ((hip >= lowp) && (xcmp(*hip, *pivp) >= 0))
183 hip--;
184 while ((lowp <= hip) && (xcmp(*lowp, *pivp) < 0))
185 lowp++;
186 if (lowp < hip) {
187 exchange(lowp, hip);
188 hip--;
189 lowp++;
190 }
191 }
192 /*
193 * now lowp points at first member not in low set
194 * and hip points at first member not in high set.
195 * Since high set contains the pivot element (by
196 * definition) it has at least one element.
197 * low set might not. check for this and make the
198 * pivot element part of the low set if its is empty.
199 * sort smaller of remaining pieces
200 * then larger, to cut down on recursion
201 */
202 if (lowp == olp) { /* its empty */
203 exchange(lowp, pivp);
204 lowp++; /* point past sigle element(pivot) */
205 hip = ohp;
206 } else if ((olp - lowp-1) > (hip+1 - ohp)) {
207 xsort(hip+1, ohp+1);
208 /* hip = lowp - elsize; set right alread */
209 lowp = olp;
210 } else {
211 xsort(olp, lowp);
212 /* lowp = hip+elsize; set right already */
213 hip = ohp;
214 }
215
216 }
217 }
218 #else
219 /*
220 * shellsort algorithm
221 * on array of elsize elements from lowp to hip-1
222 */
223 LOCAL void
xsort(from,to)224 xsort(from, to)
225 char *from[];
226 char *to[];
227 {
228 register int i;
229 register int j;
230 int k;
231 int m;
232 int n;
233
234 if ((n = to - from) <= 1) /* Nothing to sort. */
235 return;
236
237 for (j = 1; j <= n; j *= 2)
238 ;
239
240 for (m = 2 * j - 1; m /= 2; ) {
241 k = n - m;
242 for (j = 0; j < k; j++) {
243 for (i = j; i >= 0; i -= m) {
244 register char **fromi;
245 #ifdef cmplocal
246 register char *s1;
247 register char *s2;
248 #endif
249
250 fromi = &from[i];
251 #ifdef cmplocal
252 s1 = fromi[m];
253 s2 = fromi[0];
254
255 /* schneller als strcmp() ??? */
256
257 while (*s1++ == *s2) {
258 if (*s2++ == 0) {
259 --s2;
260 break;
261 }
262 }
263 if ((*--s1 - *s2) > 0) {
264 #else
265 if (xcmp(fromi[m], fromi[0]) > 0) {
266 #endif
267 break;
268 } else {
269 char *s;
270
271 s = fromi[m];
272 fromi[m] = fromi[0];
273 fromi[0] = s;
274 }
275 }
276 }
277 }
278 }
279 #endif
280
281 LOCAL Tnode *
exp(n,i,l,patm)282 exp(n, i, l, patm)
283 char *n; /* name to rescan */
284 int i; /* index in name to start rescan */
285 Tnode *l; /* list of Tnodes already found */
286 BOOL patm; /* use pattern matching not strbeg */
287 {
288 register char *cp;
289 register char *dp; /* pointer past end of current dir */
290 char *dir = NULL;
291 char *tmp;
292 register char *cname; /* concatenated name dir+d_ent */
293 DIR *dirp;
294 struct dirent *dent;
295 int *aux;
296 int *state;
297 register int patlen;
298 register int alt;
299 int rescan = 0;
300 Tnode *l1 = l;
301
302 cp = dp = &n[i];
303
304 EDEBUG(("name: '%s' i: %d dp: '%s'\n", n, i, dp));
305
306 if (patm) {
307 while (*cp && !strchr(mchars, *cp)) /* go past non glob parts */
308 if (*cp++ == '/')
309 dp = cp;
310
311 while (*cp && *cp != '/') /* find end of name component */
312 cp++;
313
314 patlen = cp-dp;
315 i = dp - n; /* make &n[i] == dp (pattern start) */
316
317 /*
318 * Prepare to use the pattern matcher.
319 */
320 EDEBUG(("patlen: %d pattern: '%.*s'\n", patlen, patlen, dp));
321
322 aux = malloc((size_t)patlen*(sizeof (int)));
323 state = malloc((size_t)(patlen+1)*(sizeof (int)));
324 if (aux == (int *)NULL || state == (int *)NULL)
325 goto cannot;
326 if ((alt = patcompile((unsigned char *)dp, patlen, aux)) == 0 &&
327 patlen != 0) {
328 EDEBUG(("Bad pattern\n"));
329 free((char *)aux);
330 free((char *)state);
331 return (l1);
332 }
333 } else { /* Non-pattern matching variant */
334 alt = 0;
335 aux = NULL;
336 state = NULL;
337
338 while (*cp) { /* go past directory parts */
339 if (*cp++ == '/')
340 dp = cp;
341 }
342
343 patlen = cp-dp;
344 i = dp - n; /* make &n[i] == dp (pattern start) */
345 }
346
347 dir = save_base(n, dp); /* get dirname part */
348 if (dir == (char *)NULL ||
349 (dirp = lopendir(dp == n ? "." : dir)) == (DIR *)NULL)
350 goto cannot;
351
352 EDEBUG(("dir: '%s' match: '%.*s'\n", dp == n?".":dir, patlen, dp));
353 if (patlen == 0 && patm) {
354 /*
355 * match auf /pattern/ Daher kein Match wenn keine
356 * Directory! opendir() Test ist daher notwendig.
357 * Fuer libshedit (ohne patm) wird aber die Directory
358 * komplett expandiert.
359 */
360 l1 = allocnode(STRING, (Tnode *)makestr(dir), l1);
361
362 } else while ((dent = readdir(dirp)) != 0 && !ctlc) {
363 int namlen;
364 char *name = dent->d_name;
365
366 /*
367 * Skip the following names: "", ".", "..".
368 */
369 if (name[name[0] != '.' ? 0 : name[1] != '.' ? 1 : 2] == '\0') {
370 /*
371 * Do not skip . and .. if there is a plain match.
372 * We need this to let ..TAB expand to ../ in the
373 * command line editor.
374 */
375 if ((name[0] == '.' && dp[0] == '.') &&
376 ((name[1] == '\0' && dp[1] == '\0') ||
377 ((name[1] == '.' && dp[1] == '.') &&
378 (name[2] == '\0' && dp[2] =='\0')))) {
379 /* EMPTY */;
380 } else {
381 continue;
382 }
383 }
384
385 /*
386 * Are we interested in files starting with '.'?
387 */
388 if (name[0] == '.' && *dp != '.')
389 continue;
390 namlen = DIR_NAMELEN(dent);
391 if (patm) {
392 tmp = (char *)patmatch((unsigned char *)dp, aux,
393 (unsigned char *)name, 0, namlen,
394 alt, state);
395 } else {
396 if (strstr(name, dp) == name)
397 tmp = "";
398 else
399 tmp = NULL;
400 }
401
402 #ifdef DEBUG
403 if (tmp != NULL || (name[0] == dp[0] &&
404 patlen == namlen))
405 EDEBUG(("match? '%s' end: '%s'\n", name, tmp));
406 #endif
407 /*
408 * *tmp == '\0' is a result of an exact pattern match.
409 *
410 * dncmp(dent->d_name, dp) == 0 happens when
411 * a pattern contains a pattern matcher special
412 * character (e.g. "foo#1"), but the pattern would not
413 * match itself using regular expressions. We use a
414 * literal compare in this case.
415 */
416
417 if ((tmp != NULL && *tmp == '\0') ||
418 (patlen == namlen &&
419 name[0] == dp[0] &&
420 dncmp(name, dp) == 0)) {
421 EDEBUG(("found: '%s'\n", name));
422
423 cname = concat(dir, name, cp, (char *)NULL);
424 if (*cp == '/') {
425 EDEBUG(("rescan: '%s'\n", cname));
426 rescan++;
427 }
428 if (cname) {
429 l1 = allocnode(sxnlen(i+namlen),
430 (Tnode *)cname, l1);
431 } else {
432 EDEBUG(("cannot concat: '%s%s%s'\n",
433 /* EDEBUG */ dir, name, cp));
434 break;
435 }
436 }
437 }
438 closedir(dirp);
439 cannot:
440 if (dir)
441 free(dir);
442 if (aux)
443 free((char *)aux);
444 if (state)
445 free((char *)state);
446
447 if (rescan > 0 && l1 != (Tnode *)NULL) {
448 for (alt = rescan; --alt >= 0; ) {
449 register Tnode *l2;
450
451 l = exp(l1->tn_left.tn_str, nlen(l1), l, patm);
452 free(l1->tn_left.tn_str);
453 l2 = l1->tn_right.tn_node;
454 free(l1);
455 l1 = l2;
456 }
457 return (l);
458 }
459
460 return (l1);
461 }
462
463 /*
464 * The expand function used for globbing
465 */
466 EXPORT Tnode *
expand(s)467 expand(s)
468 char *s;
469 {
470 if (!any_match(s))
471 return ((Tnode *)NULL);
472 else
473 return (mklist(exp(s, 0, (Tnode *)NULL, TRUE)));
474 }
475
476 /*
477 * Begin expand, used for file name completion
478 */
479 EXPORT Tnode *
bexpand(s)480 bexpand(s)
481 char *s;
482 {
483 return (mklist(exp(s, 0, (Tnode *)NULL, FALSE)));
484 }
485
486 #ifdef HAVE_FCHDIR
487 EXPORT int
bsh_hop_dirs(name,np)488 bsh_hop_dirs(name, np)
489 char *name;
490 char **np;
491 {
492 char *p;
493 char *p2;
494 int fd;
495 int dfd;
496 int err;
497
498 p = name;
499 fd = AT_FDCWD;
500 if (*p == '/') {
501 fd = openat(fd, "/", O_SEARCH|O_DIRECTORY|O_NDELAY);
502 while (*p == '/')
503 p++;
504 }
505 while (*p) {
506 if ((p2 = strchr(p, '/')) != NULL) {
507 if (p2[1] == '\0')
508 break;
509 *p2 = '\0';
510 } else {
511 break; /* No slash remains, return the prefix fd */
512 }
513 if ((dfd = openat(fd, p, O_SEARCH|O_DIRECTORY|O_NDELAY)) < 0) {
514 err = geterrno();
515
516 close(fd);
517 if (err == EMFILE)
518 seterrno(err);
519 else
520 seterrno(ENAMETOOLONG);
521 *p2 = '/';
522 return (dfd);
523 }
524 close(fd); /* Don't care about AT_FDCWD, it is negative */
525 fd = dfd;
526 *p2++ = '/'; /* p2 is always != NULL here */
527 while (*p2 == '/')
528 p2++;
529 p = p2;
530 }
531 *np = p;
532 return (fd);
533 }
534 #endif
535
536 LOCAL DIR *
lopendir(name)537 lopendir(name)
538 char *name;
539 {
540 #ifdef HAVE_FCHDIR
541 char *p;
542 int fd;
543 int dfd;
544 #endif
545 DIR *ret = NULL;
546
547 if ((ret = opendir(name)) == NULL && geterrno() != ENAMETOOLONG)
548 return ((DIR *)NULL);
549
550 #ifdef HAVE_FCHDIR
551 if (ret)
552 return (ret);
553
554 fd = bsh_hop_dirs(name, &p);
555 if ((dfd = openat(fd, p, O_RDONLY|O_DIRECTORY|O_NDELAY)) < 0) {
556 close(fd);
557 return ((DIR *)NULL);
558 }
559 close(fd);
560 ret = fdopendir(dfd);
561 #endif
562 return (ret);
563 }
564