1
0

glob.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848
  1. /* $OpenBSD: glob.c,v 1.25 2005/08/08 08:05:34 espie Exp $ */
  2. /*
  3. * Copyright (c) 1989, 1993
  4. * The Regents of the University of California. All rights reserved.
  5. *
  6. * This code is derived from software contributed to Berkeley by
  7. * Guido van Rossum.
  8. *
  9. * Redistribution and use in source and binary forms, with or without
  10. * modification, are permitted provided that the following conditions
  11. * are met:
  12. * 1. Redistributions of source code must retain the above copyright
  13. * notice, this list of conditions and the following disclaimer.
  14. * 2. Redistributions in binary form must reproduce the above copyright
  15. * notice, this list of conditions and the following disclaimer in the
  16. * documentation and/or other materials provided with the distribution.
  17. * 3. Neither the name of the University nor the names of its contributors
  18. * may be used to endorse or promote products derived from this software
  19. * without specific prior written permission.
  20. *
  21. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31. * SUCH DAMAGE.
  32. */
  33. /*
  34. * glob(3) -- a superset of the one defined in POSIX 1003.2.
  35. *
  36. * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  37. *
  38. * Optional extra services, controlled by flags not defined by POSIX:
  39. *
  40. * GLOB_QUOTE:
  41. * Escaping convention: \ inhibits any special meaning the following
  42. * character might have (except \ at end of string is retained).
  43. * GLOB_MAGCHAR:
  44. * Set in gl_flags if pattern contained a globbing character.
  45. * GLOB_NOMAGIC:
  46. * Same as GLOB_NOCHECK, but it will only append pattern if it did
  47. * not contain any magic characters. [Used in csh style globbing]
  48. * GLOB_ALTDIRFUNC:
  49. * Use alternately specified directory access functions.
  50. * GLOB_TILDE:
  51. * expand ~user/foo to the /home/dir/of/user/foo
  52. * GLOB_BRACE:
  53. * expand {1,2}{a,b} to 1a 1b 2a 2b
  54. * gl_matchc:
  55. * Number of matches in the current invocation of glob.
  56. */
  57. #ifdef __APPLE__
  58. #include <sys/param.h>
  59. #include <sys/stat.h>
  60. #include <ctype.h>
  61. #include <dirent.h>
  62. #include <errno.h>
  63. #include <glob.h>
  64. #include <pwd.h>
  65. #include <stdio.h>
  66. #include <stdlib.h>
  67. #include <string.h>
  68. #include <unistd.h>
  69. #define DOLLAR '$'
  70. #define DOT '.'
  71. #define EOS '\0'
  72. #define LBRACKET '['
  73. #define NOT '!'
  74. #define QUESTION '?'
  75. #define QUOTE '\\'
  76. #define RANGE '-'
  77. #define RBRACKET ']'
  78. #define SEP '/'
  79. #define STAR '*'
  80. #define TILDE '~'
  81. #define UNDERSCORE '_'
  82. #define LBRACE '{'
  83. #define RBRACE '}'
  84. #define SLASH '/'
  85. #define COMMA ','
  86. #ifndef DEBUG
  87. #define M_QUOTE 0x8000
  88. #define M_PROTECT 0x4000
  89. #define M_MASK 0xffff
  90. #define M_ASCII 0x00ff
  91. typedef u_short Char;
  92. #else
  93. #define M_QUOTE 0x80
  94. #define M_PROTECT 0x40
  95. #define M_MASK 0xff
  96. #define M_ASCII 0x7f
  97. typedef char Char;
  98. #endif
  99. #define CHAR(c) ((Char)((c)&M_ASCII))
  100. #define META(c) ((Char)((c)|M_QUOTE))
  101. #define M_ALL META('*')
  102. #define M_END META(']')
  103. #define M_NOT META('!')
  104. #define M_ONE META('?')
  105. #define M_RNG META('-')
  106. #define M_SET META('[')
  107. #define ismeta(c) (((c)&M_QUOTE) != 0)
  108. static int compare(const void *, const void *);
  109. static int g_Ctoc(const Char *, char *, u_int);
  110. static int g_lstat(Char *, struct stat *, glob_t *);
  111. static DIR *g_opendir(Char *, glob_t *);
  112. static const Char *g_strchr(const Char *, int);
  113. static int g_stat(Char *, struct stat *, glob_t *);
  114. static int glob0(const Char *, glob_t *);
  115. static int glob1(Char *, Char *, glob_t *, size_t *);
  116. static int glob2(Char *, Char *, Char *, Char *, Char *, Char *,
  117. glob_t *, size_t *);
  118. static int glob3(Char *, Char *, Char *, Char *, Char *, Char *,
  119. Char *, Char *, glob_t *, size_t *);
  120. static int globextend(const Char *, glob_t *, size_t *);
  121. static const Char *
  122. globtilde(const Char *, Char *, size_t, glob_t *);
  123. static int globexp1(const Char *, glob_t *);
  124. static int globexp2(const Char *, const Char *, glob_t *, int *);
  125. static int match(Char *, Char *, Char *);
  126. #ifdef DEBUG
  127. static void qprintf(const char *, Char *);
  128. #endif
  129. int
  130. glob(const char *pattern, int flags, int (*errfunc)(const char *, int),
  131. glob_t *pglob)
  132. {
  133. const u_char *patnext;
  134. int c;
  135. Char *bufnext, *bufend, patbuf[MAXPATHLEN];
  136. patnext = (const u_char *) pattern;
  137. if (!(flags & GLOB_APPEND)) {
  138. pglob->gl_pathc = 0;
  139. pglob->gl_pathv = NULL;
  140. if (!(flags & GLOB_DOOFFS))
  141. pglob->gl_offs = 0;
  142. }
  143. pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  144. pglob->gl_errfunc = errfunc;
  145. pglob->gl_matchc = 0;
  146. bufnext = patbuf;
  147. bufend = bufnext + MAXPATHLEN - 1;
  148. if (flags & GLOB_NOESCAPE)
  149. while (bufnext < bufend && (c = *patnext++) != EOS)
  150. *bufnext++ = c;
  151. else {
  152. /* Protect the quoted characters. */
  153. while (bufnext < bufend && (c = *patnext++) != EOS)
  154. if (c == QUOTE) {
  155. if ((c = *patnext++) == EOS) {
  156. c = QUOTE;
  157. --patnext;
  158. }
  159. *bufnext++ = c | M_PROTECT;
  160. } else
  161. *bufnext++ = c;
  162. }
  163. *bufnext = EOS;
  164. if (flags & GLOB_BRACE)
  165. return globexp1(patbuf, pglob);
  166. else
  167. return glob0(patbuf, pglob);
  168. }
  169. /*
  170. * Expand recursively a glob {} pattern. When there is no more expansion
  171. * invoke the standard globbing routine to glob the rest of the magic
  172. * characters
  173. */
  174. static int
  175. globexp1(const Char *pattern, glob_t *pglob)
  176. {
  177. const Char* ptr = pattern;
  178. int rv;
  179. /* Protect a single {}, for find(1), like csh */
  180. if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
  181. return glob0(pattern, pglob);
  182. while ((ptr = g_strchr(ptr, LBRACE)) != NULL)
  183. if (!globexp2(ptr, pattern, pglob, &rv))
  184. return rv;
  185. return glob0(pattern, pglob);
  186. }
  187. /*
  188. * Recursive brace globbing helper. Tries to expand a single brace.
  189. * If it succeeds then it invokes globexp1 with the new pattern.
  190. * If it fails then it tries to glob the rest of the pattern and returns.
  191. */
  192. static int
  193. globexp2(const Char *ptr, const Char *pattern, glob_t *pglob, int *rv)
  194. {
  195. int i;
  196. Char *lm, *ls;
  197. const Char *pe, *pm, *pl;
  198. Char patbuf[MAXPATHLEN];
  199. /* copy part up to the brace */
  200. for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
  201. ;
  202. *lm = EOS;
  203. ls = lm;
  204. /* Find the balanced brace */
  205. for (i = 0, pe = ++ptr; *pe; pe++)
  206. if (*pe == LBRACKET) {
  207. /* Ignore everything between [] */
  208. for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
  209. ;
  210. if (*pe == EOS) {
  211. /*
  212. * We could not find a matching RBRACKET.
  213. * Ignore and just look for RBRACE
  214. */
  215. pe = pm;
  216. }
  217. } else if (*pe == LBRACE)
  218. i++;
  219. else if (*pe == RBRACE) {
  220. if (i == 0)
  221. break;
  222. i--;
  223. }
  224. /* Non matching braces; just glob the pattern */
  225. if (i != 0 || *pe == EOS) {
  226. *rv = glob0(patbuf, pglob);
  227. return 0;
  228. }
  229. for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
  230. switch (*pm) {
  231. case LBRACKET:
  232. /* Ignore everything between [] */
  233. for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
  234. ;
  235. if (*pm == EOS) {
  236. /*
  237. * We could not find a matching RBRACKET.
  238. * Ignore and just look for RBRACE
  239. */
  240. pm = pl;
  241. }
  242. break;
  243. case LBRACE:
  244. i++;
  245. break;
  246. case RBRACE:
  247. if (i) {
  248. i--;
  249. break;
  250. }
  251. /* FALLTHROUGH */
  252. case COMMA:
  253. if (i && *pm == COMMA)
  254. break;
  255. else {
  256. /* Append the current string */
  257. for (lm = ls; (pl < pm); *lm++ = *pl++)
  258. ;
  259. /*
  260. * Append the rest of the pattern after the
  261. * closing brace
  262. */
  263. for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
  264. ;
  265. /* Expand the current pattern */
  266. #ifdef DEBUG
  267. qprintf("globexp2:", patbuf);
  268. #endif
  269. *rv = globexp1(patbuf, pglob);
  270. /* move after the comma, to the next string */
  271. pl = pm + 1;
  272. }
  273. break;
  274. default:
  275. break;
  276. }
  277. }
  278. *rv = 0;
  279. return 0;
  280. }
  281. /*
  282. * expand tilde from the passwd file.
  283. */
  284. static const Char *
  285. globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
  286. {
  287. struct passwd *pwd;
  288. char *h;
  289. const Char *p;
  290. Char *b, *eb;
  291. if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
  292. return pattern;
  293. /* Copy up to the end of the string or / */
  294. eb = &patbuf[patbuf_len - 1];
  295. for (p = pattern + 1, h = (char *) patbuf;
  296. h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
  297. ;
  298. *h = EOS;
  299. #if 0
  300. if (h == (char *)eb)
  301. return what;
  302. #endif
  303. if (((char *) patbuf)[0] == EOS) {
  304. /*
  305. * handle a plain ~ or ~/ by expanding $HOME
  306. * first and then trying the password file
  307. */
  308. if (issetugid() != 0 || (h = getenv("HOME")) == NULL) {
  309. if ((pwd = getpwuid(getuid())) == NULL)
  310. return pattern;
  311. else
  312. h = pwd->pw_dir;
  313. }
  314. } else {
  315. /*
  316. * Expand a ~user
  317. */
  318. if ((pwd = getpwnam((char*) patbuf)) == NULL)
  319. return pattern;
  320. else
  321. h = pwd->pw_dir;
  322. }
  323. /* Copy the home directory */
  324. for (b = patbuf; b < eb && *h; *b++ = *h++)
  325. ;
  326. /* Append the rest of the pattern */
  327. while (b < eb && (*b++ = *p++) != EOS)
  328. ;
  329. *b = EOS;
  330. return patbuf;
  331. }
  332. /*
  333. * The main glob() routine: compiles the pattern (optionally processing
  334. * quotes), calls glob1() to do the real pattern matching, and finally
  335. * sorts the list (unless unsorted operation is requested). Returns 0
  336. * if things went well, nonzero if errors occurred. It is not an error
  337. * to find no matches.
  338. */
  339. static int
  340. glob0(const Char *pattern, glob_t *pglob)
  341. {
  342. const Char *qpatnext;
  343. int c, err, oldpathc;
  344. Char *bufnext, patbuf[MAXPATHLEN];
  345. size_t limit = 0;
  346. qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
  347. oldpathc = pglob->gl_pathc;
  348. bufnext = patbuf;
  349. /* We don't need to check for buffer overflow any more. */
  350. while ((c = *qpatnext++) != EOS) {
  351. switch (c) {
  352. case LBRACKET:
  353. c = *qpatnext;
  354. if (c == NOT)
  355. ++qpatnext;
  356. if (*qpatnext == EOS ||
  357. g_strchr(qpatnext+1, RBRACKET) == NULL) {
  358. *bufnext++ = LBRACKET;
  359. if (c == NOT)
  360. --qpatnext;
  361. break;
  362. }
  363. *bufnext++ = M_SET;
  364. if (c == NOT)
  365. *bufnext++ = M_NOT;
  366. c = *qpatnext++;
  367. do {
  368. *bufnext++ = CHAR(c);
  369. if (*qpatnext == RANGE &&
  370. (c = qpatnext[1]) != RBRACKET) {
  371. *bufnext++ = M_RNG;
  372. *bufnext++ = CHAR(c);
  373. qpatnext += 2;
  374. }
  375. } while ((c = *qpatnext++) != RBRACKET);
  376. pglob->gl_flags |= GLOB_MAGCHAR;
  377. *bufnext++ = M_END;
  378. break;
  379. case QUESTION:
  380. pglob->gl_flags |= GLOB_MAGCHAR;
  381. *bufnext++ = M_ONE;
  382. break;
  383. case STAR:
  384. pglob->gl_flags |= GLOB_MAGCHAR;
  385. /* collapse adjacent stars to one,
  386. * to avoid exponential behavior
  387. */
  388. if (bufnext == patbuf || bufnext[-1] != M_ALL)
  389. *bufnext++ = M_ALL;
  390. break;
  391. default:
  392. *bufnext++ = CHAR(c);
  393. break;
  394. }
  395. }
  396. *bufnext = EOS;
  397. #ifdef DEBUG
  398. qprintf("glob0:", patbuf);
  399. #endif
  400. if ((err = glob1(patbuf, patbuf+MAXPATHLEN-1, pglob, &limit)) != 0)
  401. return(err);
  402. /*
  403. * If there was no match we are going to append the pattern
  404. * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
  405. * and the pattern did not contain any magic characters
  406. * GLOB_NOMAGIC is there just for compatibility with csh.
  407. */
  408. if (pglob->gl_pathc == oldpathc) {
  409. if ((pglob->gl_flags & GLOB_NOCHECK) ||
  410. ((pglob->gl_flags & GLOB_NOMAGIC) &&
  411. !(pglob->gl_flags & GLOB_MAGCHAR)))
  412. return(globextend(pattern, pglob, &limit));
  413. else
  414. return(GLOB_NOMATCH);
  415. }
  416. if (!(pglob->gl_flags & GLOB_NOSORT))
  417. qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  418. pglob->gl_pathc - oldpathc, sizeof(char *), compare);
  419. return(0);
  420. }
  421. static int
  422. compare(const void *p, const void *q)
  423. {
  424. return(strcmp(*(char *const *)p, *(char *const *)q));
  425. }
  426. static int
  427. glob1(Char *pattern, Char *pattern_last, glob_t *pglob, size_t *limitp)
  428. {
  429. Char pathbuf[MAXPATHLEN];
  430. /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  431. if (*pattern == EOS)
  432. return(0);
  433. return(glob2(pathbuf, pathbuf+MAXPATHLEN-1,
  434. pathbuf, pathbuf+MAXPATHLEN-1,
  435. pattern, pattern_last, pglob, limitp));
  436. }
  437. /*
  438. * The functions glob2 and glob3 are mutually recursive; there is one level
  439. * of recursion for each segment in the pattern that contains one or more
  440. * meta characters.
  441. */
  442. static int
  443. glob2(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
  444. Char *pattern, Char *pattern_last, glob_t *pglob, size_t *limitp)
  445. {
  446. struct stat sb;
  447. Char *p, *q;
  448. int anymeta;
  449. /*
  450. * Loop over pattern segments until end of pattern or until
  451. * segment with meta character found.
  452. */
  453. for (anymeta = 0;;) {
  454. if (*pattern == EOS) { /* End of pattern? */
  455. *pathend = EOS;
  456. if (g_lstat(pathbuf, &sb, pglob))
  457. return(0);
  458. if (((pglob->gl_flags & GLOB_MARK) &&
  459. pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
  460. (S_ISLNK(sb.st_mode) &&
  461. (g_stat(pathbuf, &sb, pglob) == 0) &&
  462. S_ISDIR(sb.st_mode)))) {
  463. if (pathend+1 > pathend_last)
  464. return (1);
  465. *pathend++ = SEP;
  466. *pathend = EOS;
  467. }
  468. ++pglob->gl_matchc;
  469. return(globextend(pathbuf, pglob, limitp));
  470. }
  471. /* Find end of next segment, copy tentatively to pathend. */
  472. q = pathend;
  473. p = pattern;
  474. while (*p != EOS && *p != SEP) {
  475. if (ismeta(*p))
  476. anymeta = 1;
  477. if (q+1 > pathend_last)
  478. return (1);
  479. *q++ = *p++;
  480. }
  481. if (!anymeta) { /* No expansion, do next segment. */
  482. pathend = q;
  483. pattern = p;
  484. while (*pattern == SEP) {
  485. if (pathend+1 > pathend_last)
  486. return (1);
  487. *pathend++ = *pattern++;
  488. }
  489. } else
  490. /* Need expansion, recurse. */
  491. return(glob3(pathbuf, pathbuf_last, pathend,
  492. pathend_last, pattern, pattern_last,
  493. p, pattern_last, pglob, limitp));
  494. }
  495. /* NOTREACHED */
  496. }
  497. static int
  498. glob3(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
  499. Char *pattern, Char *pattern_last __attribute__((unused)), Char *restpattern,
  500. Char *restpattern_last, glob_t *pglob, size_t *limitp)
  501. {
  502. struct dirent *dp;
  503. DIR *dirp;
  504. int err;
  505. char buf[MAXPATHLEN];
  506. /*
  507. * The readdirfunc declaration can't be prototyped, because it is
  508. * assigned, below, to two functions which are prototyped in glob.h
  509. * and dirent.h as taking pointers to differently typed opaque
  510. * structures.
  511. */
  512. struct dirent *(*readdirfunc)(void *);
  513. if (pathend > pathend_last)
  514. return (1);
  515. *pathend = EOS;
  516. errno = 0;
  517. if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
  518. /* TODO: don't call for ENOENT or ENOTDIR? */
  519. if (pglob->gl_errfunc) {
  520. if (g_Ctoc(pathbuf, buf, sizeof(buf)))
  521. return(GLOB_ABORTED);
  522. if (pglob->gl_errfunc(buf, errno) ||
  523. pglob->gl_flags & GLOB_ERR)
  524. return(GLOB_ABORTED);
  525. }
  526. return(0);
  527. }
  528. err = 0;
  529. /* Search directory for matching names. */
  530. if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  531. readdirfunc = pglob->gl_readdir;
  532. else
  533. readdirfunc = (struct dirent *(*)(void *))readdir;
  534. while ((dp = (*readdirfunc)(dirp))) {
  535. u_char *sc;
  536. Char *dc;
  537. /* Initial DOT must be matched literally. */
  538. if (dp->d_name[0] == DOT && *pattern != DOT)
  539. continue;
  540. dc = pathend;
  541. sc = (u_char *) dp->d_name;
  542. while (dc < pathend_last && (*dc++ = *sc++) != EOS)
  543. ;
  544. if (dc >= pathend_last) {
  545. *dc = EOS;
  546. err = 1;
  547. break;
  548. }
  549. if (!match(pathend, pattern, restpattern)) {
  550. *pathend = EOS;
  551. continue;
  552. }
  553. err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
  554. restpattern, restpattern_last, pglob, limitp);
  555. if (err)
  556. break;
  557. }
  558. if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  559. (*pglob->gl_closedir)(dirp);
  560. else
  561. closedir(dirp);
  562. return(err);
  563. }
  564. /*
  565. * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
  566. * add the new item, and update gl_pathc.
  567. *
  568. * This assumes the BSD realloc, which only copies the block when its size
  569. * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  570. * behavior.
  571. *
  572. * Return 0 if new item added, error code if memory couldn't be allocated.
  573. *
  574. * Invariant of the glob_t structure:
  575. * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  576. * gl_pathv points to (gl_offs + gl_pathc + 1) items.
  577. */
  578. static int
  579. globextend(const Char *path, glob_t *pglob, size_t *limitp)
  580. {
  581. char **pathv;
  582. int i;
  583. u_int newsize, len;
  584. char *copy;
  585. const Char *p;
  586. newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  587. pathv = pglob->gl_pathv ? realloc((char *)pglob->gl_pathv, newsize) :
  588. malloc(newsize);
  589. if (pathv == NULL) {
  590. if (pglob->gl_pathv) {
  591. free(pglob->gl_pathv);
  592. pglob->gl_pathv = NULL;
  593. }
  594. return(GLOB_NOSPACE);
  595. }
  596. if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  597. /* first time around -- clear initial gl_offs items */
  598. pathv += pglob->gl_offs;
  599. for (i = pglob->gl_offs; --i >= 0; )
  600. *--pathv = NULL;
  601. }
  602. pglob->gl_pathv = pathv;
  603. for (p = path; *p++;)
  604. ;
  605. len = (size_t)(p - path);
  606. *limitp += len;
  607. if ((copy = malloc(len)) != NULL) {
  608. if (g_Ctoc(path, copy, len)) {
  609. free(copy);
  610. return(GLOB_NOSPACE);
  611. }
  612. pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  613. }
  614. pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  615. if ((pglob->gl_flags & GLOB_LIMIT) &&
  616. newsize + *limitp >= ARG_MAX) {
  617. errno = 0;
  618. return(GLOB_NOSPACE);
  619. }
  620. return(copy == NULL ? GLOB_NOSPACE : 0);
  621. }
  622. /*
  623. * pattern matching function for filenames. Each occurrence of the *
  624. * pattern causes a recursion level.
  625. */
  626. static int
  627. match(Char *name, Char *pat, Char *patend)
  628. {
  629. int ok, negate_range;
  630. Char c, k;
  631. while (pat < patend) {
  632. c = *pat++;
  633. switch (c & M_MASK) {
  634. case M_ALL:
  635. if (pat == patend)
  636. return(1);
  637. do {
  638. if (match(name, pat, patend))
  639. return(1);
  640. } while (*name++ != EOS);
  641. return(0);
  642. case M_ONE:
  643. if (*name++ == EOS)
  644. return(0);
  645. break;
  646. case M_SET:
  647. ok = 0;
  648. if ((k = *name++) == EOS)
  649. return(0);
  650. if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
  651. ++pat;
  652. while (((c = *pat++) & M_MASK) != M_END)
  653. if ((*pat & M_MASK) == M_RNG) {
  654. if (c <= k && k <= pat[1])
  655. ok = 1;
  656. pat += 2;
  657. } else if (c == k)
  658. ok = 1;
  659. if (ok == negate_range)
  660. return(0);
  661. break;
  662. default:
  663. if (*name++ != c)
  664. return(0);
  665. break;
  666. }
  667. }
  668. return(*name == EOS);
  669. }
  670. /* Free allocated data belonging to a glob_t structure. */
  671. void
  672. globfree(glob_t *pglob)
  673. {
  674. int i;
  675. char **pp;
  676. if (pglob->gl_pathv != NULL) {
  677. pp = pglob->gl_pathv + pglob->gl_offs;
  678. for (i = pglob->gl_pathc; i--; ++pp)
  679. if (*pp)
  680. free(*pp);
  681. free(pglob->gl_pathv);
  682. pglob->gl_pathv = NULL;
  683. }
  684. }
  685. static DIR *
  686. g_opendir(Char *str, glob_t *pglob)
  687. {
  688. char buf[MAXPATHLEN];
  689. if (!*str)
  690. strlcpy(buf, ".", sizeof buf);
  691. else {
  692. if (g_Ctoc(str, buf, sizeof(buf)))
  693. return(NULL);
  694. }
  695. if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  696. return((*pglob->gl_opendir)(buf));
  697. return(opendir(buf));
  698. }
  699. static int
  700. g_lstat(Char *fn, struct stat *sb, glob_t *pglob)
  701. {
  702. char buf[MAXPATHLEN];
  703. if (g_Ctoc(fn, buf, sizeof(buf)))
  704. return(-1);
  705. if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  706. return((*pglob->gl_lstat)(buf, sb));
  707. return(lstat(buf, sb));
  708. }
  709. static int
  710. g_stat(Char *fn, struct stat *sb, glob_t *pglob)
  711. {
  712. char buf[MAXPATHLEN];
  713. if (g_Ctoc(fn, buf, sizeof(buf)))
  714. return(-1);
  715. if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  716. return((*pglob->gl_stat)(buf, sb));
  717. return(stat(buf, sb));
  718. }
  719. static const Char *
  720. g_strchr(const Char *str, int ch)
  721. {
  722. do {
  723. if (*str == ch)
  724. return (str);
  725. } while (*str++);
  726. return (NULL);
  727. }
  728. static int
  729. g_Ctoc(const Char *str, char *buf, u_int len)
  730. {
  731. while (len--) {
  732. if ((*buf++ = *str++) == EOS)
  733. return (0);
  734. }
  735. return (1);
  736. }
  737. #ifdef DEBUG
  738. static void
  739. qprintf(const char *str, Char *s)
  740. {
  741. Char *p;
  742. (void)printf("%s:\n", str);
  743. for (p = s; *p; p++)
  744. (void)printf("%c", CHAR(*p));
  745. (void)printf("\n");
  746. for (p = s; *p; p++)
  747. (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  748. (void)printf("\n");
  749. for (p = s; *p; p++)
  750. (void)printf("%c", ismeta(*p) ? '_' : ' ');
  751. (void)printf("\n");
  752. }
  753. #endif
  754. #endif