find.c revision 5e4787ea3144364983944c38eb2a5ab2f12351bc
1/* find.c - Search directories for matching files. 2 * 3 * Copyright 2014 Rob Landley <rob@landley.net> 4 * 5 * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/find.c 6 * 7 * Our "unspecified" behavior for no paths is to use "." 8 * Parentheses can only stack 4096 deep 9 * Not treating two {} as an error, but only using last 10 11USE_FIND(NEWTOY(find, "?^HL[-HL]", TOYFLAG_USR|TOYFLAG_BIN)) 12 13config FIND 14 bool "find" 15 default y 16 help 17 usage: find [-HL] [DIR...] [<options>] 18 19 Search directories for matching files. 20 Default: search "." match all -print all matches. 21 22 -H Follow command line symlinks -L Follow all symlinks 23 24 Match filters: 25 -name PATTERN filename with wildcards -iname case insensitive -name 26 -path PATTERN path name with wildcards -ipath case insensitive -path 27 -user UNAME belongs to user UNAME -nouser user not in /etc/passwd 28 -group GROUP belongs to group GROUP -nogroup group not in /etc/group 29 -perm [-]MODE permissons (-=at least) -prune ignore contents of dir 30 -size N[c] 512 byte blocks (c=bytes) -xdev stay in this filesystem 31 -links N hardlink count -atime N accessed N days ago 32 -ctime N created N days ago -mtime N modified N days ago 33 -newer FILE newer mtime than FILE -mindepth # at least # dirs down 34 -depth ignore contents of dir -maxdepth # at most # dirs down 35 -type [bcdflps] (block, char, dir, file, symlink, pipe, socket) 36 37 Numbers N may be prefixed by a - (less than) or + (greater than): 38 39 Combine matches with: 40 !, -a, -o, ( ) not, and, or, group expressions 41 42 Actions: 43 -print Print match with newline -print0 Print match with null 44 -exec Run command with path -execdir Run command in file's dir 45 -ok Ask before exec -okdir Ask before execdir 46 47 Commands substitute "{}" with matched file. End with ";" to run each file, 48 or "+" (next argument after "{}") to collect and run with multiple files. 49*/ 50 51#define FOR_find 52#include "toys.h" 53 54GLOBALS( 55 char **filter; 56 struct double_list *argdata; 57 int topdir, xdev, depth, envsize; 58 time_t now; 59) 60 61// None of this can go in TT because you can have more than one -exec 62struct exec_range { 63 char *next, *prev; 64 65 int dir, plus, arglen, argsize, curly, namecount, namesize; 66 char **argstart; 67 struct double_list *names; 68}; 69 70// Perform pending -exec (if any) 71static int flush_exec(struct dirtree *new, struct exec_range *aa) 72{ 73 struct double_list **dl; 74 char **newargs; 75 int rc; 76 77 if (!aa->namecount) return 0; 78 79 if (aa->dir && new->parent) dl = (void *)&new->parent->extra; 80 else dl = &aa->names; 81 dlist_terminate(*dl); 82 83 // switch to directory for -execdir, or back to top if we have an -execdir 84 // _and_ a normal -exec, or are at top of tree in -execdir 85 if (aa->dir && new->parent) fchdir(new->parent->data); 86 else if (TT.topdir != -1) fchdir(TT.topdir); 87 88 // execdir: accumulated execs in this directory's children. 89 newargs = xmalloc(sizeof(char *)*(aa->arglen+aa->namecount+1)); 90 if (aa->curly < 0) { 91 memcpy(newargs, aa->argstart, sizeof(char *)*aa->arglen); 92 newargs[aa->arglen] = 0; 93 } else { 94 struct double_list *dl2 = *dl; 95 int pos = aa->curly, rest = aa->arglen - aa->curly; 96 97 // Collate argument list 98 memcpy(newargs, aa->argstart, sizeof(char *)*pos); 99 for (dl2 = *dl; dl2; dl2 = dl2->next) newargs[pos++] = dl2->data; 100 rest = aa->arglen - aa->curly - 1; 101 memcpy(newargs+pos, aa->argstart+aa->curly+1, sizeof(char *)*rest); 102 newargs[pos+rest] = 0; 103 } 104 105 rc = xpclose(xpopen(newargs, 0), 0); 106 107 llist_traverse(*dl, llist_free_double); 108 *dl = 0; 109 aa->namecount = 0; 110 111 return rc; 112} 113 114// Return numeric value with explicit sign 115static int compare_numsign(long val, long units, char *str) 116{ 117 char sign = 0; 118 long myval; 119 120 if (*str == '+' || *str == '-') sign = *(str++); 121 else if (!isdigit(*str)) error_exit("%s not [+-]N", str); 122 myval = atolx(str); 123 if (units && isdigit(str[strlen(str)-1])) myval *= units; 124 125 if (sign == '+') return val > myval; 126 if (sign == '-') return val < myval; 127 return val == myval; 128} 129 130static void do_print(struct dirtree *new, char c) 131{ 132 char *s=dirtree_path(new, 0); 133 134 xprintf("%s%c", s, c); 135 free(s); 136} 137 138char *strlower(char *s) 139{ 140 char *try, *new; 141 142 if (!CFG_TOYBOX_I18N) { 143 try = new = xstrdup(s); 144 for (; *s; s++) *(new++) = tolower(*s); 145 } else { 146 // I can't guarantee the string _won't_ expand during reencoding, so...? 147 try = new = xmalloc(strlen(s)*2+1); 148 149 while (*s) { 150 wchar_t c; 151 int len = mbrtowc(&c, s, MB_CUR_MAX, 0); 152 153 if (len < 1) *(new++) = *(s++); 154 else { 155 s += len; 156 // squash title case too 157 c = towlower(c); 158 159 // if we had a valid utf8 sequence, convert it to lower case, and can't 160 // encode back to utf8, something is wrong with your libc. But just 161 // in case somebody finds an exploit... 162 len = wcrtomb(new, c, 0); 163 if (len < 1) error_exit("bad utf8 %x", c); 164 new += len; 165 } 166 } 167 *new = 0; 168 } 169 170 return try; 171} 172 173// Call this with 0 for first pass argument parsing and syntax checking (which 174// populates argdata). Later commands traverse argdata (in order) when they 175// need "do once" results. 176static int do_find(struct dirtree *new) 177{ 178 int pcount = 0, print = 0, not = 0, active = !!new, test = active, recurse; 179 struct double_list *argdata = TT.argdata; 180 char *s, **ss; 181 182 recurse = DIRTREE_COMEAGAIN|((toys.optflags&FLAG_L) ? DIRTREE_SYMFOLLOW : 0); 183 184 // skip . and .. below topdir, handle -xdev and -depth 185 if (new) { 186 if (new->parent) { 187 if (!dirtree_notdotdot(new)) return 0; 188 if (TT.xdev && new->st.st_dev != new->parent->st.st_dev) return 0; 189 } 190 if (S_ISDIR(new->st.st_mode)) { 191 if (!new->again) { 192 struct dirtree *n; 193 194 if (TT.depth) return recurse; 195 for (n = new->parent; n; n = n->parent) { 196 if (n->st.st_ino==new->st.st_ino && n->st.st_dev==new->st.st_dev) { 197 error_msg("'%s': loop detected", s = dirtree_path(new, 0)); 198 free(s); 199 200 return 0; 201 } 202 } 203 } else { 204 struct double_list *dl; 205 206 if (TT.topdir != -1) 207 for (dl = TT.argdata; dl; dl = dl->next) 208 if (dl->prev == (void *)1 || !new->parent) 209 toys.exitval |= flush_exec(new, (void *)dl); 210 211 return 0; 212 } 213 } 214 } 215 216 // pcount: parentheses stack depth (using toybuf bytes, 4096 max depth) 217 // test: result of most recent test 218 // active: if 0 don't perform tests 219 // not: a pending ! applies to this test (only set if performing tests) 220 // print: saw one of print/ok/exec, no need for default -print 221 222 if (TT.filter) for (ss = TT.filter; *ss; ss++) { 223 int check = active && test; 224 225 s = *ss; 226 227 // handle ! ( ) using toybuf as a stack 228 if (*s != '-') { 229 if (s[1]) goto error; 230 231 if (*s == '!') { 232 // Don't invert if we're not making a decision 233 if (check) not = !not; 234 235 // Save old "not" and "active" on toybuf stack. 236 // Deactivate this parenthetical if !test 237 // Note: test value should never change while !active 238 } else if (*s == '(') { 239 if (pcount == sizeof(toybuf)) goto error; 240 toybuf[pcount++] = not+(active<<1); 241 if (!check) active = 0; 242 not = 0; 243 244 // Pop status, apply deferred not to test 245 } else if (*s == ')') { 246 if (--pcount < 0) goto error; 247 // Pop active state, apply deferred not (which was only set if checking) 248 active = (toybuf[pcount]>>1)&1; 249 if (active && (toybuf[pcount]&1)) test = !test; 250 not = 0; 251 } else goto error; 252 253 continue; 254 } else s++; 255 256 if (!strcmp(s, "xdev")) TT.xdev = 1; 257 else if (!strcmp(s, "depth")) TT.depth = 1; 258 else if (!strcmp(s, "o") || !strcmp(s, "or")) { 259 if (not) goto error; 260 if (active) { 261 if (!test) test = 1; 262 else active = 0; // decision has been made until next ")" 263 } 264 } else if (!strcmp(s, "not")) { 265 if (check) not = !not; 266 // Mostly ignore NOP argument 267 } else if (!strcmp(s, "a") || !strcmp(s, "and")) { 268 if (not) goto error; 269 270 } else if (!strcmp(s, "print") || !strcmp("print0", s)) { 271 print++; 272 if (check) do_print(new, s[5] ? 0 : '\n'); 273 274 } else if (!strcmp(s, "nouser")) { 275 if (check) if (getpwuid(new->st.st_uid)) test = 0; 276 } else if (!strcmp(s, "nogroup")) { 277 if (check) if (getgrgid(new->st.st_gid)) test = 0; 278 } else if (!strcmp(s, "prune")) { 279 if (check && S_ISDIR(new->st.st_dev) && !TT.depth) recurse = 0; 280 281 // Remaining filters take an argument 282 } else { 283 if (!strcmp(s, "name") || !strcmp(s, "iname") 284 || !strcmp(s, "path") || !strcmp(s, "ipath")) 285 { 286 int i = (*s == 'i'); 287 char *arg = ss[1], *path = 0, *name = new->name; 288 289 // Handle path expansion and case flattening 290 if (new && s[i] == 'p') name = path = dirtree_path(new, 0); 291 if (i) { 292 if (check || !new) { 293 name = strlower(new ? name : arg); 294 if (!new) { 295 dlist_add(&TT.argdata, name); 296 free(path); 297 } else arg = ((struct double_list *)llist_pop(&argdata))->data; 298 } 299 } 300 301 if (check) { 302 test = !fnmatch(arg, name, FNM_PATHNAME*(s[i] == 'p')); 303 free(path); 304 if (i) free(name); 305 } 306 } else if (!strcmp(s, "perm")) { 307 if (check) { 308 char *m = ss[1]; 309 mode_t m1 = string_to_mode(m+(*m == '-'), 0), 310 m2 = new->st.st_dev & 07777; 311 312 if (*m != '-') m2 &= m1; 313 test = m1 == m2; 314 } 315 } else if (!strcmp(s, "type")) { 316 if (check) { 317 char c = stridx("bcdlpfs", *ss[1]); 318 int types[] = {S_IFBLK, S_IFCHR, S_IFDIR, S_IFLNK, S_IFIFO, 319 S_IFREG, S_IFSOCK}; 320 321 if ((new->st.st_mode & S_IFMT) != types[c]) test = 0; 322 } 323 324 } else if (!strcmp(s, "atime")) { 325 if (check) 326 test = compare_numsign(TT.now - new->st.st_atime, 86400, ss[1]); 327 } else if (!strcmp(s, "ctime")) { 328 if (check) 329 test = compare_numsign(TT.now - new->st.st_ctime, 86400, ss[1]); 330 } else if (!strcmp(s, "mtime")) { 331 if (check) 332 test = compare_numsign(TT.now - new->st.st_mtime, 86400, ss[1]); 333 } else if (!strcmp(s, "size")) { 334 if (check) 335 test = compare_numsign(new->st.st_size, 512, ss[1]); 336 } else if (!strcmp(s, "links")) { 337 if (check) test = compare_numsign(new->st.st_nlink, 0, ss[1]); 338 } else if (!strcmp(s, "mindepth") || !strcmp(s, "maxdepth")) { 339 if (check) { 340 struct dirtree *dt = new; 341 int i = 0, d = atolx(ss[1]); 342 343 while ((dt = dt->parent)) i++; 344 345 test = s[1] == 'i' ? i >= d : i <= d; 346 } 347 } else if (!strcmp(s, "user") || !strcmp(s, "group") 348 || !strcmp(s, "newer")) 349 { 350 struct { 351 void *next, *prev; 352 union { 353 uid_t uid; 354 gid_t gid; 355 struct timespec tm; 356 } u; 357 } *udl; 358 359 if (!new && ss[1]) { 360 udl = xmalloc(sizeof(*udl)); 361 dlist_add_nomalloc(&TT.argdata, (void *)udl); 362 363 if (*s == 'u') udl->u.uid = xgetpwnam(ss[1])->pw_uid; 364 else if (*s == 'g') udl->u.gid = xgetgrnam(ss[1])->gr_gid; 365 else { 366 struct stat st; 367 368 xstat(ss[1], &st); 369 udl->u.tm = st.st_mtim; 370 } 371 } else if (check) { 372 udl = (void *)llist_pop(&argdata); 373 if (*s == 'u') test = new->st.st_uid == udl->u.uid; 374 else if (*s == 'g') test = new->st.st_gid == udl->u.gid; 375 else { 376 test = new->st.st_mtim.tv_sec > udl->u.tm.tv_sec; 377 if (new->st.st_mtim.tv_sec == udl->u.tm.tv_sec) 378 test = new->st.st_mtim.tv_nsec > udl->u.tm.tv_nsec; 379 } 380 } 381 } else if (!strcmp(s, "exec") || !strcmp("ok", s) 382 || !strcmp(s, "execdir") || !strcmp(s, "okdir")) 383 { 384 struct exec_range *aa; 385 386 print++; 387 388 // Initial argument parsing pass 389 if (!new) { 390 int len; 391 392 // catch "-exec" with no args and "-exec \;" 393 if (!ss[1] || !strcmp(ss[1], ";")) error_exit("'%s' needs 1 arg", s); 394 395 dlist_add_nomalloc(&TT.argdata, (void *)(aa = xzalloc(sizeof(*aa)))); 396 aa->argstart = ++ss; 397 aa->curly = -1; 398 399 // Record command line arguments to -exec 400 for (len = 0; ss[len]; len++) { 401 if (!strcmp(ss[len], ";")) break; 402 else if (!strcmp(ss[len], "{}")) { 403 aa->curly = len; 404 if (!strcmp(ss[len+1], "+")) { 405 406 // Measure environment space 407 if (!TT.envsize) { 408 char **env; 409 410 for (env = environ; *env; env++) 411 TT.envsize += sizeof(char *) + strlen(*env) + 1; 412 TT.envsize += sizeof(char *); 413 } 414 aa->plus++; 415 len++; 416 break; 417 } 418 } else aa->argsize += sizeof(char *) + strlen(ss[len]) + 1; 419 } 420 if (!ss[len]) error_exit("-exec without \\;"); 421 ss += len; 422 aa->arglen = len; 423 aa->dir = !!strchr(s, 'd'); 424 if (aa->dir && TT.topdir == -1) TT.topdir = xopen(".", 0); 425 426 // collect names and execute commands 427 } else if (check) { 428 char *name, *ss1 = ss[1]; 429 struct double_list **ddl; 430 431 // Grab command line exec argument list 432 aa = (void *)llist_pop(&argdata); 433 ss += aa->arglen + 1; 434 435 // name is always a new malloc, so we can always free it. 436 name = aa->dir ? xstrdup(new->name) : dirtree_path(new, 0); 437 438 // Mark entry so COMEAGAIN can call flush_exec() in parent. 439 // This is never a valid pointer valud for prev to have otherwise 440 if (aa->dir) aa->prev = (void *)1; 441 442 if (*s == 'o') { 443 char *prompt = xmprintf("[%s] %s", ss1, name); 444 if(!(test = yesno(prompt, 0))) goto cont; 445 } 446 447 // Add next name to list (global list without -dir, local with) 448 if (aa->dir && new->parent) 449 ddl = (struct double_list **)&new->parent->extra; 450 else ddl = &aa->names; 451 452 // Is this + mode? 453 if (aa->plus) { 454 int size = sizeof(char *)+strlen(name)+1; 455 456 // Linux caps environment space (env vars + args) at 32 4k pages. 457 // todo: is there a way to probe this instead of constant here? 458 459 if (TT.envsize+aa->argsize+aa->namesize+size >= 131072) 460 toys.exitval |= flush_exec(new, aa); 461 aa->namesize += size; 462 } 463 dlist_add(ddl, name); 464 aa->namecount++; 465 if (!aa->plus) test = flush_exec(new, aa); 466 } 467 468 // Argument consumed, skip the check. 469 goto cont; 470 } else goto error; 471 472 // This test can go at the end because we do a syntax checking 473 // pass first. Putting it here gets the error message (-unknown 474 // vs -known noarg) right. 475 if (!*++ss) error_exit("'%s' needs 1 arg", --s); 476 } 477cont: 478 // Apply pending "!" to result 479 if (active && not) test = !test; 480 not = 0; 481 } 482 483 if (new) { 484 // If there was no action, print 485 if (!print && test) do_print(new, '\n'); 486 } else dlist_terminate(TT.argdata); 487 488 return recurse; 489 490error: 491 error_exit("bad arg '%s'", *ss); 492} 493 494void find_main(void) 495{ 496 int i, len; 497 char **ss = toys.optargs; 498 499 TT.topdir = -1; 500 501 // Distinguish paths from filters 502 for (len = 0; toys.optargs[len]; len++) 503 if (strchr("-!(", *toys.optargs[len])) break; 504 TT.filter = toys.optargs+len; 505 506 // use "." if no paths 507 if (!*ss || **ss == '-') { 508 ss = (char *[]){"."}; 509 len = 1; 510 } 511 512 // first pass argument parsing, verify args match up, handle "evaluate once" 513 TT.now = time(0); 514 do_find(0); 515 516 // Loop through paths 517 for (i = 0; i < len; i++) { 518 struct dirtree *new; 519 520 new = dirtree_add_node(0, ss[i], toys.optflags&(FLAG_H|FLAG_L)); 521 if (new) dirtree_handle_callback(new, do_find); 522 } 523 524 if (CFG_TOYBOX_FREE) { 525 close(TT.topdir); 526 llist_traverse(TT.argdata, free); 527 } 528} 529