lr.c 52.8 KB
Newer Older
Christian Neukirchen's avatar
Christian Neukirchen committed
1 2
/* lr - a better recursive ls/find */

3
/*
Leah Neukirchen's avatar
Leah Neukirchen committed
4
 * Copyright (C) 2015-2017 Leah Neukirchen <purl.org/net/chneukirchen>
Christian Neukirchen's avatar
Christian Neukirchen committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 * Parts of code derived from musl libc, which is
 * Copyright (C) 2005-2014 Rich Felker, et al.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
27 28

/*
Christian Neukirchen's avatar
Christian Neukirchen committed
29
##% gcc -Os -Wall -g -o $STEM $FILE -Wno-switch -Wextra -Wwrite-strings
30 31
*/

Christian Neukirchen's avatar
Christian Neukirchen committed
32
#define _GNU_SOURCE
33 34 35 36 37

#include <sys/param.h>
#include <sys/stat.h>
#include <sys/types.h>

38
#ifdef __linux__
Christian Neukirchen's avatar
Christian Neukirchen committed
39
#include <sys/xattr.h>
40 41
#endif

42 43 44
#include <ctype.h>
#include <dirent.h>
#include <errno.h>
Christian Neukirchen's avatar
Christian Neukirchen committed
45
#include <fnmatch.h>
Christian Neukirchen's avatar
Christian Neukirchen committed
46
#include <grp.h>
47
#include <limits.h>
Leah Neukirchen's avatar
Leah Neukirchen committed
48
#include <locale.h>
49
#include <paths.h>
Christian Neukirchen's avatar
Christian Neukirchen committed
50
#include <pwd.h>
Christian Neukirchen's avatar
Christian Neukirchen committed
51
#include <regex.h>
52
#include <stdarg.h>
53
#include <stdint.h>
54 55 56 57 58 59
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

60 61 62 63 64 65 66 67 68 69
#ifdef __has_include
  #if __has_include(<stdnoreturn.h>)
    #include <stdnoreturn.h>
  #else
    #define noreturn /**/
  #endif
#else
  #define noreturn /**/
#endif

70 71 72 73 74
/* For Solaris. */
#if !defined(FNM_CASEFOLD) && defined(FNM_IGNORECASE)
#define FNM_CASEFOLD FNM_IGNORECASE
#endif

75 76 77 78 79
/* For Hurd. */
#if !defined(PATH_MAX)
#define PATH_MAX 4096
#endif

80 81 82
struct fitree;
struct idtree;

83
static int Bflag;
84 85
static int Cflag;
static char *Cflags[64];
86
static int Gflag;
87
static int Dflag;
Christian Neukirchen's avatar
Christian Neukirchen committed
88 89
static int Hflag;
static int Lflag;
90
static int Qflag;
91
static int Pflag;
Christian Neukirchen's avatar
Christian Neukirchen committed
92
static int Uflag;
93
static int Xflag;
94
static int hflag;
Christian Neukirchen's avatar
Christian Neukirchen committed
95 96
static int lflag;
static int sflag;
97
static int xflag;
98
static char Tflag = 'T';
Christian Neukirchen's avatar
Christian Neukirchen committed
99 100 101 102 103

static char *argv0;
static char *format;
static char *ordering;
static struct expr *expr;
104
static int prune;
105
static size_t prefixl;
106
static char input_delim = '\n';
107
static int current_color;
108
static int status;
109
static char *basepath;
110
static char host[1024];
111

Christian Neukirchen's avatar
Christian Neukirchen committed
112 113 114
static char default_ordering[] = "n";
static char default_format[] = "%p\\n";
static char type_format[] = "%p%F\\n";
115
static char long_format[] = "%M%x %n %u %g %s %\324F %\324R %p%F%l\n";
Christian Neukirchen's avatar
Christian Neukirchen committed
116
static char zero_format[] = "%p\\0";
117
static char stat_format[] = "%D %i %M %n %u %g %R %s \"%Ab %Ad %AT %AY\" \"%Tb %Td %TT %TY\" \"%Cb %Cd %CT %CY\" %b %p\n";
Christian Neukirchen's avatar
Christian Neukirchen committed
118

119 120
static struct fitree *root;
static struct fitree *new_root;
121

122 123 124 125
static struct idtree *users;
static struct idtree *groups;
static struct idtree *filesystems;
static int scanned_filesystems;
126

127
static int need_stat;
128 129 130
static int need_group;
static int need_user;
static int need_fstype;
131
static int need_xattr;
132 133 134 135 136 137 138

static dev_t maxdev;
static ino_t maxino;
static nlink_t maxnlink;
static uid_t maxuid;
static gid_t maxgid;
static dev_t maxrdev;
Christian Neukirchen's avatar
Christian Neukirchen committed
139
static off_t maxsize;
140
static blkcnt_t maxblocks;
141
static unsigned int maxxattr;
142

143
static int bflag_depth;
144
static int maxdepth;
145
static int uwid, gwid, fwid;
146

147
static time_t now;
148
static mode_t default_mask;
149

150 151 152 153 154 155 156 157
// [^a-zA-Z0-9~._/-]
static char rfc3986[128] = {
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,
	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1
};

158 159
struct fileinfo {
	char *fpath;
160
	size_t prefixl;
161
	int depth;
162
	ino_t entries;
163
	struct stat sb;
164
	off_t total;
165
	char xattr[4];
166
	int color;
167 168 169
};

enum op {
Christian Neukirchen's avatar
Christian Neukirchen committed
170
	EXPR_OR = 1,
171
	EXPR_AND,
172
	EXPR_COND,
173 174 175 176
	EXPR_NOT,
	EXPR_LT,
	EXPR_LE,
	EXPR_EQ,
Christian Neukirchen's avatar
Christian Neukirchen committed
177
	EXPR_NEQ,
178 179
	EXPR_GE,
	EXPR_GT,
Christian Neukirchen's avatar
Christian Neukirchen committed
180 181
	EXPR_STREQ,
	EXPR_STREQI,
182
	EXPR_GLOB,
Christian Neukirchen's avatar
Christian Neukirchen committed
183
	EXPR_GLOBI,
Christian Neukirchen's avatar
Christian Neukirchen committed
184 185
	EXPR_REGEX,
	EXPR_REGEXI,
186
	EXPR_PRUNE,
187
	EXPR_PRINT,
188
	EXPR_COLOR,
Christian Neukirchen's avatar
Christian Neukirchen committed
189
	EXPR_TYPE,
190
	EXPR_ALLSET,
191
	EXPR_ANYSET,
192
	EXPR_CHMOD,
193 194 195
};

enum prop {
Christian Neukirchen's avatar
Christian Neukirchen committed
196
	PROP_ATIME = 1,
197 198 199
	PROP_CTIME,
	PROP_DEPTH,
	PROP_DEV,
200
	PROP_ENTRIES,
201
	PROP_FSTYPE,
202 203
	PROP_GID,
	PROP_GROUP,
204 205 206 207 208 209
	PROP_INODE,
	PROP_LINKS,
	PROP_MODE,
	PROP_MTIME,
	PROP_NAME,
	PROP_PATH,
Christian Neukirchen's avatar
Christian Neukirchen committed
210
	PROP_RDEV,
211
	PROP_SIZE,
212 213
	PROP_TARGET,
	PROP_TOTAL,
214 215
	PROP_UID,
	PROP_USER,
216
	PROP_XATTR,
Christian Neukirchen's avatar
Christian Neukirchen committed
217 218 219 220 221 222 223 224 225 226
};

enum filetype {
	TYPE_BLOCK = 'b',
	TYPE_CHAR = 'c',
	TYPE_DIR = 'd',
	TYPE_FIFO = 'p',
	TYPE_REGULAR = 'f',
	TYPE_SOCKET = 's',
	TYPE_SYMLINK = 'l',
227 228 229 230 231 232
};

struct expr {
	enum op op;
	union {
		enum prop prop;
Christian Neukirchen's avatar
Christian Neukirchen committed
233
		enum filetype filetype;
234 235
		struct expr *expr;
		char *string;
236
		int64_t num;
Christian Neukirchen's avatar
Christian Neukirchen committed
237
		regex_t *regex;
238
	} a, b, c;
239 240 241 242
};

static char *pos;

243
noreturn static void
244
parse_error(const char *msg, ...)
245
{
246 247 248 249 250
	va_list ap;
	va_start(ap, msg);
	fprintf(stderr, "%s: parse error: ", argv0);
	vfprintf(stderr, msg, ap);
	fprintf(stderr, "\n");
251 252 253
	exit(2);
}

254 255 256 257 258 259 260 261 262 263 264 265
int
test_chmod(char *c, mode_t oldmode)
{
	mode_t newmode = oldmode;
	mode_t whom, what;
	char op;

	do {
		whom = 0;
		what = 0;

		while (1) {
Leah Neukirchen's avatar
Leah Neukirchen committed
266
			switch (*c) {
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
			case 'u': whom |= 04700; break;
			case 'g': whom |= 02070; break;
			case 'o': whom |= 01007; break;
			case 'a': whom |= 07777; break;
			default: goto op;
			}
			c++;
		}
op:
		if (whom == 0)
			whom = default_mask;
		op = *c++;
		if (!(op == '-' || op == '+' || op == '='))
			parse_error("invalid mode operator");

Leah Neukirchen's avatar
Leah Neukirchen committed
282
		switch (*c) {
283 284 285
		case 'u': what = 00111 * ((newmode >> 6) & 0007); c++; break;
		case 'g': what = 00111 * ((newmode >> 3) & 0007); c++; break;
		case 'o': what = 00111 * ((newmode     ) & 0007); c++; break;
286 287
		default:
			while (1) {
Leah Neukirchen's avatar
Leah Neukirchen committed
288
				switch (*c) {
289 290 291
				case 'r': what |= 00444; break;
				case 'w': what |= 00222; break;
				case 'x': what |= 00111; break;
292
				case 'X': if (oldmode & 00111) what |= 00111; break;
293 294 295 296 297 298 299 300 301 302 303 304
				case 's': what |= 06000; break;
				case 't': what |= 01000; break;
				case ',': case 0: goto doit;
				default: parse_error("invalid permission");
				}
				c++;
			}
		}
doit:
		switch (op) {
		case '-': newmode &= ~(whom & what); break;
		case '+': newmode |= (whom & what); break;
305
		case '=': newmode = (newmode & ~whom) | (whom & what); break;
306 307 308 309 310 311 312 313 314
		}
	} while (*c == ',' && c++);

	if (*c)
		parse_error("trailing garbage in mode string '%s'", c);

	return newmode == oldmode;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
315
static struct expr *
316 317
mkexpr(enum op op)
{
Christian Neukirchen's avatar
Christian Neukirchen committed
318
	struct expr *e = malloc(sizeof (struct expr));
319 320 321 322 323 324
	if (!e)
		parse_error("out of memory");
	e->op = op;
	return e;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
325
static void
326 327
ws()
{
328
	while (isspace((unsigned char)*pos))
329 330 331
		pos++;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
332
static int
333 334 335 336 337 338 339 340 341 342 343
token(const char *token)
{
	if (strncmp(pos, token, strlen(token)) == 0) {
		pos += strlen(token);
		ws();
		return 1;
	} else {
		return 0;
	}
}

344
static int64_t
345
parse_num(int64_t *r)
346
{
347
	char *s = pos;
348
	if (isdigit((unsigned char)*pos)) {
349 350
		int64_t n;

351
		for (n = 0; isdigit((unsigned char)*pos) && n <= INT64_MAX / 10 - 10; pos++)
Christian Neukirchen's avatar
Christian Neukirchen committed
352
			n = 10 * n + (*pos - '0');
353
		if (isdigit((unsigned char)*pos))
354
			parse_error("number too big: %s", s);
Christian Neukirchen's avatar
Christian Neukirchen committed
355
		if (token("c"))      ;
356 357 358 359 360
		else if (token("b")) n *= 512LL;
		else if (token("k")) n *= 1024LL;
		else if (token("M")) n *= 1024LL * 1024;
		else if (token("G")) n *= 1024LL * 1024 * 1024;
		else if (token("T")) n *= 1024LL * 1024 * 1024 * 1024;
361 362 363 364 365 366 367 368
		ws();
		*r = n;
		return 1;
	} else {
		return 0;
	}
}

369 370 371
int
parse_octal(long *r)
{
372
	char *s = pos;
373 374 375 376 377 378
	if (*pos >= '0' && *pos <= '7') {
		long n = 0;
		while (*pos >= '0' && *pos <= '7') {
			n *= 8;
			n += *pos - '0';
			pos++;
Christian Neukirchen's avatar
Christian Neukirchen committed
379
			if (n > 07777)
380
				parse_error("number to big: %s", s);
381 382 383 384 385 386 387 388 389
		}
		ws();
		*r = n;
		return 1;
	} else {
		return 0;
	}
}

Christian Neukirchen's avatar
Christian Neukirchen committed
390
static enum op
391 392 393 394 395 396 397 398 399 400
parse_op()
{
	if (token("<="))
		return EXPR_LE;
	else if (token("<"))
		return EXPR_LT;
	else if (token(">="))
		return EXPR_GE;
	else if (token(">"))
		return EXPR_GT;
401
	else if (token("==") || token("="))
402
		return EXPR_EQ;
Christian Neukirchen's avatar
Christian Neukirchen committed
403 404
	else if (token("!="))
		return EXPR_NEQ;
405 406 407 408

	return 0;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
409
static struct expr *parse_cmp();
410
static struct expr *parse_cond();
Christian Neukirchen's avatar
Christian Neukirchen committed
411

Christian Neukirchen's avatar
Christian Neukirchen committed
412
static struct expr *
413 414 415
parse_inner()
{
	if (token("prune")) {
416
		struct expr *e = mkexpr(EXPR_PRUNE);
417
		return e;
418 419 420
	} else if (token("print")) {
		struct expr *e = mkexpr(EXPR_PRINT);
		return e;
421 422 423 424 425
	} else if (token("skip")) {
		struct expr *e = mkexpr(EXPR_PRINT);
		struct expr *not = mkexpr(EXPR_NOT);
		not->a.expr = e;
		return not;
426 427 428 429 430 431 432 433 434 435
	} else if (token("color")) {
		struct expr *e = mkexpr(EXPR_COLOR);
		int64_t n;
		if (parse_num(&n) && n >= 0 && n <= 255) {
			e->a.num = n;
			return e;
		} else {
			parse_error("invalid 256-color at '%.15s'", pos);
			return 0;
		}
Christian Neukirchen's avatar
Christian Neukirchen committed
436 437
	} else if (token("!")) {
		struct expr *e = parse_cmp();
438
		struct expr *not = mkexpr(EXPR_NOT);
Christian Neukirchen's avatar
Christian Neukirchen committed
439 440
		not->a.expr = e;
		return not;
Christian Neukirchen's avatar
Christian Neukirchen committed
441
	} else if (token("(")) {
442
		struct expr *e = parse_cond();
Christian Neukirchen's avatar
Christian Neukirchen committed
443 444
		if (token(")"))
			return e;
445
		parse_error("missing ) at '%.15s'", pos);
Christian Neukirchen's avatar
Christian Neukirchen committed
446
		return 0;
447
	} else {
448
		parse_error("unknown expression at '%.15s'", pos);
449
		return 0;
450
	}
451 452
}

Christian Neukirchen's avatar
Christian Neukirchen committed
453
static struct expr *
Christian Neukirchen's avatar
Christian Neukirchen committed
454 455
parse_type()
{
Christian Neukirchen's avatar
Christian Neukirchen committed
456 457
	int negate = 0;

Christian Neukirchen's avatar
Christian Neukirchen committed
458
	if (token("type")) {
Christian Neukirchen's avatar
Christian Neukirchen committed
459 460
		if (token("==") || token("=")
		    || (token("!=") && ++negate)) {
461
			struct expr *e = mkexpr(EXPR_TYPE);
Christian Neukirchen's avatar
Christian Neukirchen committed
462 463 464 465 466 467 468 469 470 471 472 473 474 475
			if (token("b"))
				e->a.filetype = TYPE_BLOCK;
			else if (token("c"))
				e->a.filetype = TYPE_CHAR;
			else if (token("d"))
				e->a.filetype = TYPE_DIR;
			else if (token("p"))
				e->a.filetype = TYPE_FIFO;
			else if (token("f"))
				e->a.filetype = TYPE_REGULAR;
			else if (token("l"))
				e->a.filetype = TYPE_SYMLINK;
			else if (token("s"))
				e->a.filetype = TYPE_SOCKET;
476 477
			else if (*pos)
				parse_error("invalid file type '%c'", *pos);
Christian Neukirchen's avatar
Christian Neukirchen committed
478
			else
479
				parse_error("no file type given");
Christian Neukirchen's avatar
Christian Neukirchen committed
480 481 482 483 484 485 486
			if (negate) {
				struct expr *not = mkexpr(EXPR_NOT);
				not->a.expr = e;
				return not;
			} else {
				return e;
			}
487
		} else {
488 489
			parse_error("invalid file type comparison at '%.15s'",
			    pos);
Christian Neukirchen's avatar
Christian Neukirchen committed
490 491 492 493 494 495
		}
	}

	return parse_inner();
}

Christian Neukirchen's avatar
Christian Neukirchen committed
496
static int
Christian Neukirchen's avatar
Christian Neukirchen committed
497 498
parse_string(char **s)
{
499 500 501 502
	char *buf = 0;
	size_t bufsiz = 0;
	size_t len = 0;

Christian Neukirchen's avatar
Christian Neukirchen committed
503 504
	if (*pos == '"') {
		pos++;
505 506
		while (*pos &&
		    (*pos != '"' || (*pos == '"' && *(pos+1) == '"'))) {
507 508 509 510 511 512 513 514 515 516
			if (len >= bufsiz) {
				bufsiz = 2*bufsiz + 16;
				buf = realloc(buf, bufsiz);
				if (!buf)
					parse_error("string too long");
			}
			if (*pos == '"')
				pos++;
			buf[len++] = *pos++;
		}
517 518
		if (!*pos)
			parse_error("unterminated string");
519 520 521
		if (buf)
			buf[len] = 0;
		pos++;
Christian Neukirchen's avatar
Christian Neukirchen committed
522
		ws();
523
		*s = buf ? buf : (char *)"";
Christian Neukirchen's avatar
Christian Neukirchen committed
524
		return 1;
525 526 527 528
	} else if (*pos == '$') {
		char t;
		char *e = ++pos;

529
		while (isalnum((unsigned char)*pos) || *pos == '_')
530 531 532 533 534 535 536 537
			pos++;
		if (e == pos)
			parse_error("invalid environment variable name");

		t = *pos;
		*pos = 0;
		*s = getenv(e);
		if (!*s)
Leah Neukirchen's avatar
Leah Neukirchen committed
538
			*s = (char *)"";
539 540 541
		*pos = t;
		ws();
		return 1;
Christian Neukirchen's avatar
Christian Neukirchen committed
542 543 544 545 546
	}

	return 0;
}

547 548 549 550 551 552 553 554 555 556
static int
parse_dur(int64_t *n)
{
	char *s, *r;
	if (!parse_string(&s))
		return 0;

	if (*s == '/' || *s == '.') {
		struct stat st;
		if (stat(s, &st) < 0)
557 558
			parse_error("can't stat file '%s': %s",
			    s, strerror(errno));
559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619
		*n = st.st_mtime;
		return 1;
	}

	struct tm tm = { 0 };
	r = strptime(s, "%Y-%m-%d %H:%M:%S", &tm);
	if (r && !*r) {
		*n = mktime(&tm);
		return 1;
	}
	r = strptime(s, "%Y-%m-%d", &tm);
	if (r && !*r) {
		tm.tm_hour = tm.tm_min = tm.tm_sec = 0;
		*n = mktime(&tm);
		return 1;
	}
	r = strptime(s, "%H:%M:%S", &tm);
	if (r && !*r) {
		struct tm *tmnow = localtime(&now);
		tm.tm_year = tmnow->tm_year;
		tm.tm_mon = tmnow->tm_mon;
		tm.tm_mday = tmnow->tm_mday;
		*n = mktime(&tm);
		return 1;
	}
	r = strptime(s, "%H:%M", &tm);
	if (r && !*r) {
		struct tm *tmnow = localtime(&now);
		tm.tm_year = tmnow->tm_year;
		tm.tm_mon = tmnow->tm_mon;
		tm.tm_mday = tmnow->tm_mday;
		tm.tm_sec = 0;
		*n = mktime(&tm);
		return 1;
	}

	if (*s == '-') {
		s++;

		errno = 0;
		int64_t d;
		d = strtol(s, &r, 10);
		if (errno == 0 && r[0] == 'd' && !r[1]) {
			struct tm *tmnow = localtime(&now);
			tmnow->tm_mday -= d;
			tmnow->tm_hour = tmnow->tm_min = tmnow->tm_sec = 0;
			*n = mktime(tmnow);
			return 1;
		}
		if (errno == 0 && r[0] == 'h' && !r[1]) {
			*n = now - (d*60*60);
			return 1;
		}
		if (errno == 0 && r[0] == 'm' && !r[1]) {
			*n = now - (d*60);
			return 1;
		}
		if (errno == 0 && r[0] == 's' && !r[1]) {
			*n = now - d;
			return 1;
		}
620
		parse_error("invalid relative time format '%s'", s-1);
621 622
	}

623
	parse_error("invalid time format '%s'", s);
624 625 626
	return 0;
}

627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658
static struct expr *
mkstrexpr(enum prop prop, enum op op, char *s, int negate)
{
	int r = 0;
	struct expr *e = mkexpr(op);
	e->a.prop = prop;
	if (op == EXPR_REGEX) {
		e->b.regex = malloc(sizeof (regex_t));
		r = regcomp(e->b.regex, s, REG_EXTENDED | REG_NOSUB);
	} else if (op == EXPR_REGEXI) {
		e->b.regex = malloc(sizeof (regex_t));
		r = regcomp(e->b.regex, s, REG_EXTENDED | REG_NOSUB | REG_ICASE);
	} else {
		e->b.string = s;
	}

	if (r != 0) {
		char msg[256];
		regerror(r, e->b.regex, msg, sizeof msg);
		parse_error("invalid regex '%s': %s", s, msg);
		exit(2);
	}

	if (negate) {
		struct expr *not = mkexpr(EXPR_NOT);
		not->a.expr = e;
		return not;
	}

	return e;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
659
static struct expr *
Christian Neukirchen's avatar
Christian Neukirchen committed
660 661 662 663
parse_strcmp()
{
	enum prop prop;
	enum op op;
Leah Neukirchen's avatar
Leah Neukirchen committed
664
	int negate = 0;
Christian Neukirchen's avatar
Christian Neukirchen committed
665

666 667 668
	if (token("fstype"))
		prop = PROP_FSTYPE;
	else if (token("group"))
669 670
		prop = PROP_GROUP;
	else if (token("name"))
Christian Neukirchen's avatar
Christian Neukirchen committed
671 672 673 674 675
		prop = PROP_NAME;
	else if (token("path"))
		prop = PROP_PATH;
	else if (token("target"))
		prop = PROP_TARGET;
676 677
	else if (token("user"))
		prop = PROP_USER;
678 679
	else if (token("xattr"))
		prop = PROP_XATTR;
Christian Neukirchen's avatar
Christian Neukirchen committed
680 681 682
	else
		return parse_type();

683
	if (token("~~~"))
Christian Neukirchen's avatar
Christian Neukirchen committed
684 685 686
		op = EXPR_GLOBI;
	else if (token("~~"))
		op = EXPR_GLOB;
Christian Neukirchen's avatar
Christian Neukirchen committed
687 688 689 690
	else if (token("=~~"))
		op = EXPR_REGEXI;
	else if (token("=~"))
		op = EXPR_REGEX;
691 692 693 694 695 696
	else if (token("==="))
		op = EXPR_STREQI;
	else if (token("=="))
		op = EXPR_STREQ;
	else if (token("="))
		op = EXPR_STREQ;
Leah Neukirchen's avatar
Leah Neukirchen committed
697 698 699 700 701 702 703 704 705 706 707 708
	else if (token("!~~~"))
		negate = 1, op = EXPR_GLOBI;
	else if (token("!~~"))
		negate = 1, op = EXPR_GLOB;
	else if (token("!=~~"))
		negate = 1, op = EXPR_REGEXI;
	else if (token("!=~") || token("!~"))
		negate = 1, op = EXPR_REGEX;
	else if (token("!==="))
		negate = 1, op = EXPR_STREQI;
	else if (token("!==") || token("!="))
		negate = 1, op = EXPR_STREQ;
Christian Neukirchen's avatar
Christian Neukirchen committed
709
	else
710
		parse_error("invalid string operator at '%.15s'", pos);
Christian Neukirchen's avatar
Christian Neukirchen committed
711 712

	char *s;
713 714
	if (parse_string(&s))
		return mkstrexpr(prop, op, s, negate);
Christian Neukirchen's avatar
Christian Neukirchen committed
715

716
	parse_error("invalid string at '%.15s'", pos);
Christian Neukirchen's avatar
Christian Neukirchen committed
717
	return 0;
Christian Neukirchen's avatar
Christian Neukirchen committed
718 719
}

Christian Neukirchen's avatar
Christian Neukirchen committed
720
static struct expr *
721 722
parse_mode()
{
723
	struct expr *e = mkexpr(0);
724
	long n;
725
	char *s;
726 727 728

	e->a.prop = PROP_MODE;

729
	if (token("==") || token("=")) {
730 731 732 733 734 735
		e->op = EXPR_EQ;
	} else if (token("&")) {
		e->op = EXPR_ALLSET;
	} else if (token("|")) {
		e->op = EXPR_ANYSET;
	} else {
736
		parse_error("invalid mode comparison at '%.15s'", pos);
737 738 739 740
	}

	if (parse_octal(&n)) {
		e->b.num = n;
Christian Neukirchen's avatar
Christian Neukirchen committed
741
	} else if (e->op == EXPR_EQ && parse_string(&s)) {
742 743
		e->op = EXPR_CHMOD;
		e->b.string = s;
744
		umask(default_mask = 07777 & ~umask(0));  /* for future usage */
745
		test_chmod(s, 0);  /* run once to check for syntax */
746
	} else {
747
		parse_error("invalid mode at '%.15s'", pos);
748 749 750 751 752
	}

	return e;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
753
static struct expr *
754 755 756 757 758
parse_cmp()
{
	enum prop prop;
	enum op op;

759
	if (token("depth"))
760 761 762
		prop = PROP_DEPTH;
	else if (token("dev"))
		prop = PROP_DEV;
763 764
	else if (token("entries"))
		prop = PROP_ENTRIES;
765 766
	else if (token("gid"))
		prop = PROP_GID;
767 768 769 770 771
	else if (token("inode"))
		prop = PROP_INODE;
	else if (token("links"))
		prop = PROP_LINKS;
	else if (token("mode"))
772
		return parse_mode();
Christian Neukirchen's avatar
Christian Neukirchen committed
773 774
	else if (token("rdev"))
		prop = PROP_RDEV;
775 776
	else if (token("size"))
		prop = PROP_SIZE;
777 778
	else if (token("total"))
		prop = PROP_TOTAL;
779 780
	else if (token("uid"))
		prop = PROP_UID;
781
	else
Christian Neukirchen's avatar
Christian Neukirchen committed
782
		return parse_strcmp();
Christian Neukirchen's avatar
Christian Neukirchen committed
783

784 785
	op = parse_op();
	if (!op)
786
		parse_error("invalid comparison at '%.15s'", pos);
787

788
	int64_t n;
789
	if (parse_num(&n)) {
790
		struct expr *e = mkexpr(op);
791 792 793 794 795 796 797 798
		e->a.prop = prop;
		e->b.num = n;
		return e;
	}

	return 0;
}

799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815
static struct expr *
parse_timecmp()
{
	enum prop prop;
	enum op op;

	if (token("atime"))
		prop = PROP_ATIME;
	else if (token("ctime"))
		prop = PROP_CTIME;
	else if (token("mtime"))
		prop = PROP_MTIME;
	else
		return parse_cmp();

	op = parse_op();
	if (!op)
816
		parse_error("invalid comparison at '%.15s'", pos);
817 818 819 820 821 822 823 824 825 826 827 828

	int64_t n;
	if (parse_num(&n) || parse_dur(&n)) {
		struct expr *e = mkexpr(op);
		e->a.prop = prop;
		e->b.num = n;
		return e;
	}

	return 0;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
829
static struct expr *
830 831 832
chain(struct expr *e1, enum op op, struct expr *e2)
{
	struct expr *i, *j, *e;
833 834
	if (!e1)
		return e2;
835 836
	if (!e2)
		return e1;
837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852
	for (j = 0, i = e1; i->op == op; j = i, i = i->b.expr)
		;
	if (!j) {
		e = mkexpr(op);
		e->a.expr = e1;
		e->b.expr = e2;
		return e;
	} else {
		e = mkexpr(op);
		e->a.expr = i;
		e->b.expr = e2;
		j->b.expr = e;
		return e1;
	}
}

Christian Neukirchen's avatar
Christian Neukirchen committed
853
static struct expr *
854 855
parse_and()
{
856
	struct expr *e1 = parse_timecmp();
857 858 859
	struct expr *r = e1;

	while (token("&&")) {
860
		struct expr *e2 = parse_timecmp();
861
		r = chain(r, EXPR_AND, e2);
862
	}
Christian Neukirchen's avatar
Christian Neukirchen committed
863

864 865 866
	return r;
}

867

Christian Neukirchen's avatar
Christian Neukirchen committed
868
static struct expr *
869 870 871 872 873 874 875
parse_or()
{
	struct expr *e1 = parse_and();
	struct expr *r = e1;

	while (token("||")) {
		struct expr *e2 = parse_and();
876
		r = chain(r, EXPR_OR, e2);
877
	}
Christian Neukirchen's avatar
Christian Neukirchen committed
878

879 880 881
	return r;
}

882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904
static struct expr *
parse_cond()
{
	struct expr *e1 = parse_or();

	if (token("?")) {
		struct expr *e2 = parse_or();
		if (token(":")) {
			struct expr *e3 = parse_cond();
			struct expr *r = mkexpr(EXPR_COND);
			r->a.expr = e1;
			r->b.expr = e2;
			r->c.expr = e3;

			return r;
		} else {
			parse_error(": expected at '%.15s'", pos);
		}
	}

	return e1;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
905
static struct expr *
906
parse_expr(const char *s)
907
{
Christian Neukirchen's avatar
Christian Neukirchen committed
908
	pos = (char *)s;
909
	struct expr *e = parse_cond();
910
	if (*pos)
911
		parse_error("trailing garbage at '%.15s'", pos);
912
	return e;
913 914
}

Christian Neukirchen's avatar
Christian Neukirchen committed
915
static const char *
Christian Neukirchen's avatar
Christian Neukirchen committed
916 917 918 919 920 921
basenam(const char *s)
{
	char *r = strrchr(s, '/');
	return r ? r + 1 : s;
}

Christian Neukirchen's avatar
Christian Neukirchen committed
922 923 924 925 926 927 928 929 930 931
static const char *
extnam(const char *s)
{
	char *r = strrchr(s, '/');
	char *e = strrchr(s, '.');
	if (!r || r < e)
		return e ? e + 1 : "";
	return "";
}

Christian Neukirchen's avatar
Christian Neukirchen committed
932
static const char *
Christian Neukirchen's avatar
Christian Neukirchen committed
933 934 935
readlin(const char *p, const char *alt)
{
	static char b[PATH_MAX];
936 937
	ssize_t r = readlink(p, b, sizeof b - 1);
	if (r < 0 || (size_t)r >= sizeof b - 1)
Christian Neukirchen's avatar
Christian Neukirchen committed
938 939 940 941 942
		return alt;
	b[r] = 0;
	return b;
}

943 944 945 946 947 948 949 950 951 952 953 954
//// AA-tree implementation, adapted from https://github.com/ccxvii/minilibs
struct idtree {
	long id;
	char *name;
	struct idtree *left, *right;
	int level;
};

static struct idtree idtree_sentinel = { 0, 0, &idtree_sentinel, &idtree_sentinel, 0 };

static struct idtree *
idtree_make(long id, char *name)
955
{
956 957 958 959 960 961 962
	struct idtree *node = malloc(sizeof (struct idtree));
	node->id = id;
	node->name = name;
	node->left = node->right = &idtree_sentinel;
	node->level = 1;
	return node;
}
963

964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
char *
idtree_lookup(struct idtree *node, long id)
{
	if (node) {
		while (node != &idtree_sentinel) {
			if (id == node->id)
				return node->name;
			else if (id < node->id)
				node = node->left;
			else
				node = node->right;
		}
	}

	return 0;
}

static struct idtree *
idtree_skew(struct idtree *node)
{
	if (node->left->level == node->level) {
		struct idtree *save = node;
		node = node->left;
		save->left = node->right;
		node->right = save;
	}
	return node;
}

static struct idtree *
idtree_split(struct idtree *node)
{
	if (node->right->right->level == node->level) {
		struct idtree *save = node;
		node = node->right;
		save->right = node->left;
		node->left = save;
		node->level++;
	}
	return node;
}

struct idtree *
idtree_insert(struct idtree *node, long id, char *name)
{
	if (node && node != &idtree_sentinel) {
		if (id == node->id)
			return node;
		else if (id < node->id)
			node->left = idtree_insert(node->left, id, name);
		else
			node->right = idtree_insert(node->right, id, name);
		node = idtree_skew(node);
		node = idtree_split(node);
		return node;
	}
	return idtree_make(id, name);
1021
}
1022
////
1023 1024 1025 1026 1027

static char *
strid(long id)
{
	static char buf[32];
1028
	snprintf(buf, sizeof buf, "%ld", id);
1029 1030 1031 1032 1033 1034
	return buf;
}

static char *
groupname(gid_t gid)
{
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
	char *name = idtree_lookup(groups, gid);

	if (name)
		return name;

	struct group *g = getgrgid(gid);
	if (g) {
		if ((int)strlen(g->gr_name) > gwid)
			gwid = strlen(g->gr_name);
		char *name = strdup(g->gr_name);
		groups = idtree_insert(groups, gid, name);
		return name;
1047 1048
	}

1049
	return strid(gid);
1050 1051 1052 1053 1054
}

static char *
username(uid_t uid)
{
1055 1056 1057 1058
	char *name = idtree_lookup(users, uid);

	if (name)
		return name;
1059

1060 1061 1062 1063 1064 1065 1066
	struct passwd *p = getpwuid(uid);
	if (p) {
		if ((int)strlen(p->pw_name) > uwid)
			uwid = strlen(p->pw_name);
		char *name = strdup(p->pw_name);
		users = idtree_insert(users, uid, name);
		return name;
1067
	}
1068

1069
	return strid(uid);
1070 1071
}

1072
#if defined(__linux__) || defined(__CYGWIN__)
1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083
#include <mntent.h>
void
scan_filesystems()
{
	FILE *mtab;
	struct mntent *mnt;
	struct stat st;

	/* Approach: iterate over mtab and memorize st_dev for each mountpoint.
	 * this will fail if we are not allowed to read the mountpoint, but then
	 * we should not have to look up this st_dev value... */
1084
	mtab = setmntent(_PATH_MOUNTED, "r");
1085 1086
	if (!mtab && errno == ENOENT)
		mtab = setmntent("/proc/mounts", "r");
1087 1088 1089 1090 1091 1092
	if (!mtab)
		return;

	while ((mnt = getmntent(mtab))) {
		if (stat(mnt->mnt_dir, &st) < 0)
			continue;
1093 1094
		filesystems = idtree_insert(filesystems,
		    st.st_dev, strdup(mnt->mnt_type));
1095 1096 1097 1098 1099 1100
	};

	endmntent(mtab);

	scanned_filesystems = 1;
}
1101 1102 1103 1104 1105 1106 1107 1108 1109
#elif defined(__SVR4)
#include <sys/mnttab.h>
void
scan_filesystems()
{
	FILE *mtab;
	struct mnttab mnt;
	struct stat st;

1110
	mtab = fopen(MNTTAB, "r");
1111 1112 1113 1114 1115 1116
	if (!mtab)
		return;

	while (getmntent(mtab, &mnt) == 0) {
		if (stat(mnt.mnt_mountp, &st) < 0)
			continue;
1117 1118
		filesystems = idtree_insert(filesystems,
		    st.st_dev, strdup(mnt->mnt_fstype));
1119 1120 1121 1122 1123 1124
	};

	fclose(mtab);

	scanned_filesystems = 1;
}
1125
#elif defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__DragonFly__) || (defined(__APPLE__) && defined(__MACH__))
Leah Neukirchen's avatar
Leah Neukirchen committed
1126
#include <sys/mount.h>
1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138
#include <sys/param.h>
#include <sys/ucred.h>
void
scan_filesystems()
{
	struct statfs *mnt;
	struct stat st;
	int i = getmntinfo(&mnt, MNT_NOWAIT);

	while (i-- > 0) {
		if (stat(mnt->f_mntonname, &st) < 0)
			continue;
1139 1140
		filesystems = idtree_insert(filesystems,
		    st.st_dev, strdup(mnt->f_fstypename));
1141 1142 1143 1144 1145
		mnt++;
	};

	scanned_filesystems = 1;
}
Christian Neukirchen's avatar
Christian Neukirchen committed
1146 1147
#elif defined(__NetBSD__)
#include <sys/statvfs.h>
Leah Neukirchen's avatar
Leah Neukirchen committed
1148
#include <sys/types.h>
Christian Neukirchen's avatar
Christian Neukirchen committed
1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
void
scan_filesystems()
{
	struct statvfs *mnt;
	struct stat st;
	int i = getmntinfo(&mnt, MNT_NOWAIT);

	while (i-- > 0) {
		if (stat(mnt->f_mntonname, &st) < 0)
			continue;
1159 1160
		filesystems = idtree_insert(filesystems,
		    st.st_dev, strdup(mnt->f_fstypename));
Christian Neukirchen's avatar
Christian Neukirchen committed
1161 1162 1163 1164 1165
		mnt++;
	};

	scanned_filesystems = 1;
}
1166
#else
1167
#warning fstype lookup not implemented on this platform, keeping st_dev as number
1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
void
scan_filesystems()
{
}
#endif

static char *
fstype(dev_t devid)
{
	if (!scanned_filesystems)
		scan_filesystems();

1180 1181 1182 1183 1184 1185
	char *name = idtree_lookup(filesystems, devid);
	if (name) {
		if ((int)strlen(name) > fwid)
			fwid = strlen(name);
		return name;
	}
1186

1187
	return strid(devid);
1188 1189
}

1190
static char *
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229
xattr_string(const char *f)
{
#ifdef __linux__
	char xattr[1024];
	int i, r;
	int have_xattr = 0, have_cap = 0, have_acl = 0;

	if (Lflag)
		r = listxattr(f, xattr, sizeof xattr);
	else
		r = llistxattr(f, xattr, sizeof xattr);
	if (r < 0 && errno == ERANGE) {
		/* just look at prefix */
		r = sizeof xattr;
		xattr[r-1] = 0;
	}
	// ignoring ENOTSUP or r == 0

	for (i = 0; i < r; i += strlen(xattr+i) + 1)
		if (strcmp(xattr+i, "security.capability") == 0)
			have_cap = 1;
		else if (strcmp(xattr+i, "system.posix_acl_access") == 0 ||
		    strcmp(xattr+i, "system.posix_acl_default") == 0)
			have_acl = 1;
		else
			have_xattr = 1;

	static char buf[4];
	char *c = buf;
	if (have_cap)
		*c++ = '#';
	if (have_acl)
		*c++ = '+';
	if (have_xattr)
		*c++ = '@';
	*c = 0;

	return buf;
#else
1230
	static char empty[] = "";
1231
	(void)f;
Leah Neukirchen's avatar
Leah Neukirchen committed
1232
	return empty;           // No support for xattrs on this platform.
1233 1234 1235
#endif
}

1236
static ino_t
1237 1238
count_entries(struct fileinfo *fi)
{
1239
	ino_t c = 0;
1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253
	struct dirent *de;
	DIR *d;

	if (Dflag)
		return fi->entries;

	if (!S_ISDIR(fi->sb.st_mode))
		return 0;

	d = opendir(fi->fpath);
	if (!d)
		return 0;
	while ((de = readdir(d))) {
		if (de->d_name[0] == '.' &&
Leah Neukirchen's avatar
Leah Neukirchen committed
1254
		    (!de->d_name[1] || (de->d_name[1] == '.' && !de->d_name[2])))
1255 1256 1257 1258 1259 1260 1261 1262
			continue;
		c++;
	}
	closedir(d);

	return c;
}

1263 1264 1265
int
eval(struct expr *e, struct fileinfo *fi)
{
Leah Neukirchen's avatar
Leah Neukirchen committed
1266 1267 1268
	long v = 0;
	const char *s = "";

1269 1270 1271 1272 1273
	switch (e->op) {
	case EXPR_OR:
		return eval(e->a.expr, fi) || eval(e->b.expr, fi);
	case EXPR_AND:
		return eval(e->a.expr, fi) && eval(e->b.expr, fi);
1274 1275 1276 1277
	case EXPR_COND:
		return eval(e->a.expr, fi)
		    ? eval(e->b.expr, fi)
		    : eval(e->c.expr, fi);
1278 1279 1280 1281
	case EXPR_NOT:
		return !eval(e->a.expr, fi);
	case EXPR_PRUNE:
		prune = 1;
1282
		return 1;
1283 1284
	case EXPR_PRINT:
		return 1;
1285 1286 1287
	case EXPR_COLOR:
		fi->color = e->a.num;
		return 1;
1288 1289 1290
	case EXPR_LT:
	case EXPR_LE:
	case EXPR_EQ:
Christian Neukirchen's avatar
Christian Neukirchen committed
1291
	case EXPR_NEQ:
1292 1293
	case EXPR_GE:
	case EXPR_GT:
1294
	case EXPR_ALLSET:
Leah Neukirchen's avatar
Leah Neukirchen committed
1295
	case EXPR_ANYSET:
1296 1297 1298 1299 1300
		switch (e->a.prop) {
		case PROP_ATIME: v = fi->sb.st_atime; break;
		case PROP_CTIME: v = fi->sb.st_ctime; break;
		case PROP_DEPTH: v = fi->depth; break;
		case PROP_DEV: v = fi->sb.st_dev; break;
1301
		case PROP_ENTRIES: v = count_entries(fi); break;
1302 1303
		case PROP_GID: v = fi->sb.st_gid; break;
		case PROP_INODE: v = fi->sb.st_ino; break;
1304
		case PROP_LINKS: v = fi->sb.st_nlink; break;
1305
		case PROP_MODE: v = fi->sb.st_mode & 07777; break;
1306
		case PROP_MTIME: v = fi->sb.st_mtime; break;
Christian Neukirchen's avatar
Christian Neukirchen committed
1307
		case PROP_RDEV: v = fi->sb.st_rdev; break;
1308
		case PROP_SIZE: v = fi->sb.st_size; break;
1309
		case PROP_TOTAL: v = fi->total; break;
1310
		case PROP_UID: v = fi->sb.st_uid; break;
Leah Neukirchen's avatar
Leah Neukirchen committed
1311
		default: parse_error("unknown property");
1312 1313 1314 1315 1316
		}
		switch (e->op) {
		case EXPR_LT: return v < e->b.num;
		case EXPR_LE: return v <= e->b.num;
		case EXPR_EQ: return v == e->b.num;
Christian Neukirchen's avatar
Christian Neukirchen committed
1317
		case EXPR_NEQ: return v != e->b.num;
1318 1319
		case EXPR_GE: return v >= e->b.num;
		case EXPR_GT: return v > e->b.num;
1320 1321
		case EXPR_ALLSET: return (v & e->b.num) == e->b.num;
		case EXPR_ANYSET: return (v & e->b.num) > 0;
Leah Neukirchen's avatar
Leah Neukirchen committed
1322
		default: parse_error("invalid operator");
1323
		}
1324 1325
	case EXPR_CHMOD:
		return test_chmod(e->b.string, fi->sb.st_mode & 07777);
Leah Neukirchen's avatar
Leah Neukirchen committed
1326
	case EXPR_TYPE:
Christian Neukirchen's avatar
Christian Neukirchen committed
1327 1328 1329 1330 1331 1332 1333 1334
		switch (e->a.filetype) {
		case TYPE_BLOCK: return S_ISBLK(fi->sb.st_mode);
		case TYPE_CHAR: return S_ISCHR(fi->sb.st_mode);
		case TYPE_DIR: return S_ISDIR(fi->sb.st_mode);
		case TYPE_FIFO: return S_ISFIFO(fi->sb.st_mode);
		case TYPE_REGULAR: return S_ISREG(fi->sb.st_mode);
		case TYPE_SOCKET: return S_ISSOCK(fi->sb.st_mode);
		case TYPE_SYMLINK: return S_ISLNK(fi->sb.st_mode);
Leah Neukirchen's avatar
Leah Neukirchen committed
1335
		default: parse_error("invalid file type");
Christian Neukirchen's avatar
Christian Neukirchen committed
1336
		}
Christian Neukirchen's avatar
Christian Neukirchen committed
1337 1338 1339 1340
	case EXPR_STREQ:
	case EXPR_STREQI:
	case EXPR_GLOB:
	case EXPR_GLOBI:
Christian Neukirchen's avatar
Christian Neukirchen committed
1341
	case EXPR_REGEX:
Leah Neukirchen's avatar
Leah Neukirchen committed
1342
	case EXPR_REGEXI:
Leah Neukirchen's avatar
Leah Neukirchen committed
1343
		switch (e->a.prop) {
1344
		case PROP_FSTYPE: s = fstype(fi->sb.st_dev); break;
1345
		case PROP_GROUP: s = groupname(fi->sb.st_gid); break;
Christian Neukirchen's avatar
Christian Neukirchen committed
1346 1347 1348
		case PROP_NAME: s = basenam(fi->fpath); break;
		case PROP_PATH: s = fi->fpath; break;
		case PROP_TARGET: s = readlin(fi->fpath, ""); break;
1349
		case PROP_USER: s = username(fi->sb.st_uid); break;
1350
		case PROP_XATTR: s = xattr_string(fi->fpath); break;
Leah Neukirchen's avatar
Leah Neukirchen committed
1351
		default: parse_error("unknown property");
Christian Neukirchen's avatar
Christian Neukirchen committed
1352 1353
		}
		switch (e->op) {
1354 1355 1356 1357
		case EXPR_STREQ: return strcmp(e->b.string, s) == 0;
		case EXPR_STREQI: return strcasecmp(e->b.string, s) == 0;
		case EXPR_GLOB: return fnmatch(e->b.string, s, 0) == 0;
		case EXPR_GLOBI: return fnmatch(e->b.string, s, FNM_CASEFOLD) == 0;
Christian Neukirchen's avatar
Christian Neukirchen committed
1358
		case EXPR_REGEX:
1359
		case EXPR_REGEXI: return regexec(e->b.regex, s, 0, 0, 0) == 0;
Leah Neukirchen's avatar
Leah Neukirchen committed
1360
		default: parse_error("invalid operator");
Christian Neukirchen's avatar
Christian Neukirchen committed
1361
		}
1362 1363
	default:
		parse_error("invalid operation %d, please file a bug.", e->op);
1364 1365 1366 1367 1368
	}

	return 0;
}

1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392
int
dircmp(char *a, char *b)
{
	char *ea = strrchr(a, '/');
	char *eb = strrchr(b, '/');
	if (!ea)
		ea = a + strlen(a);
	if (!eb)
		eb = b + strlen(b);

	while (a != ea && b != eb && *a == *b) {
		a++;
		b++;
	}

	if (a == ea && b == eb)
		return 0;
	if (a == ea)
		return -1;
	if (b == eb)
		return 1;
	return *a - *b;
}

1393 1394 1395 1396 1397 1398 1399 1400 1401 1402
// taken straight from musl@a593414
int mystrverscmp(const char *l0, const char *r0)
{
	const unsigned char *l = (const void *)l0;
	const unsigned char *r = (const void *)r0;
	size_t i, dp, j;
	int z = 1;

	/* Find maximal matching prefix and track its maximal digit
	 * suffix and whether those digits are all zeros. */
Leah Neukirchen's avatar
Leah Neukirchen committed
1403
	for (dp = i = 0; l[i] == r[i]; i++) {
1404 1405
		int c = l[i];
		if (!c) return 0;
Leah Neukirchen's avatar
Leah Neukirchen committed
1406 1407
		if (!isdigit(c)) dp = i+1, z = 1;
		else if (c != '0') z = 0;
1408 1409
	}

Leah Neukirchen's avatar
Leah Neukirchen committed
1410
	if (l[dp] != '0' && r[dp] != '0') {
1411 1412
		/* If we're not looking at a digit sequence that began
		 * with a zero, longest digit string is greater. */
Leah Neukirchen's avatar
Leah Neukirchen committed
1413
		for (j = i; isdigit(l[j]); j++)
1414 1415
			if (!isdigit(r[j])) return 1;
		if (isdigit(r[j])) return -1;
Leah Neukirchen's avatar
Leah Neukirchen committed
1416
	} else if (z && dp < i && (isdigit(l[i]) || isdigit(r[i]))) {
1417 1418 1419 1420 1421 1422 1423 1424
		/* Otherwise, if common prefix of digit sequence is
		 * all zeros, digits order less than non-digits. */
		return (unsigned char)(l[i]-'0') - (unsigned char)(r[i]-'0');
	}

	return l[i] - r[i];
}

1425 1426
#define CMP(a, b) if ((a) == (b)) break; else if ((a) < (b)) return -1; else return 1
#define STRCMP(a, b) if (strcmp(a, b) == 0) break; else return (strcmp(a, b));
1427
#define DIRCMP(a, b) { int r = dircmp(a, b); if (r == 0) break; else return r; };
1428
#define VERCMP(a, b) if (mystrverscmp(a, b) == 0) break; else return (mystrverscmp(a, b));
1429 1430 1431 1432

int
order(const void *a, const void *b)
{
Christian Neukirchen's avatar
Christian Neukirchen committed
1433 1434
	struct fileinfo *fa = (struct fileinfo *)a;
	struct fileinfo *fb = (struct fileinfo *)b;
1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447
	char *s;

	for (s = ordering; *s; s++) {
		switch (*s) {
		// XXX use nanosecond timestamps
		case 'c': CMP(fa->sb.st_ctime, fb->sb.st_ctime);
		case 'C': CMP(fb->sb.st_ctime, fa->sb.st_ctime);
		case 'a': CMP(fa->sb.st_atime, fb->sb.st_atime);
		case 'A': CMP(fb->sb.st_atime, fa->sb.st_atime);
		case 'm': CMP(fa->sb.st_mtime, fb->sb.st_mtime);
		case 'M': CMP(fb->sb.st_mtime, fa->sb.st_mtime);
		case 's': CMP(fa->sb.st_size, fb->sb.st_size);
		case 'S': CMP(fb->sb.st_size, fa->sb.st_size);
Christian Neukirchen's avatar
Christian Neukirchen committed
1448 1449
		case 'i': CMP(fa->sb.st_ino, fb->sb.st_ino);
		case 'I': CMP(fb->sb.st_ino, fa->sb.st_ino);
1450 1451
		case 'd': CMP(fa->depth, fb->depth);
		case 'D': CMP(fb->depth, fa->depth);
Christian Neukirchen's avatar
Christian Neukirchen committed
1452 1453 1454 1455
		case 't': CMP("ZZZZAZZZZZZZZZZZ"[(fa->sb.st_mode >> 12) & 0x0f],
		              "ZZZZAZZZZZZZZZZZ"[(fb->sb.st_mode >> 12) & 0x0f]);
		case 'T': CMP("ZZZZAZZZZZZZZZZZ"[(fb->sb.st_mode >> 12) & 0x0f],
		              "ZZZZAZZZZZZZZZZZ"[(fa->sb.st_mode >> 12) & 0x0f]);
1456 1457