/*
 * <n> can be N (exactly N), +N (more than N), or -N (less than N).
 *	-fstype <type>   [UNIMPLEMENTED]
 *	-name <glob-pattern>
 *	-qname <string>
 *	-path <glob-pattern>
 *	-qpath <string>
 *	-linkto <glob-pattern>
 *	-qlinkto <string>
 *	-perm <number>  [if st_mode&0777 == <number>]
 *	-perm -<number>  [if st_mode&017777&<number> == <number>]
 *	-perm <n1>/<n2> [if st_mode&<n1> == <n2>]
 *	-prune
 *	-type [bcdfpls]
 *	-links <n>
 *	-user <username>
 *	-nouser
 *	-group <groupname>
 *	-nogroup
 *	-size <n> [size in blocks]
 *	-size <n>c [size in bytes]
 *	-inum <n>
 *	-atime <n> [time is in days]
 *	-atime {+,-,}[#y][#m][#w][#d][#h][#m][#s][/quantum]
 *	-atime future
 *	-mtime <n>
 *	-mtime {+,-,}[#y][#m][#w][#d][#h][#m][#s][/quantum]
 *	-mtime future
 *	-ctime <n>
 *	-ctime {+,-,}[#y][#m][#w][#d][#h][#m][#s][/quantum]
 *	-ctime future
 *	-exec <command> ; [arg of {} replaced by pathname]
 *	-ok <command> ; [like exec]
 *	-print
 *	-print0
 *	-printn
 *	-count
 *	-tcount tag
 *	-ls [like ls -dilgs: inum/blksize/mode/links/user/group/size/mtime]
 *	-lsf <fmt> [fmt is a string chosen from bgilLmnNpsu, for blksize,
 *		group, inode, links, mtime, name, name, perm, size, user;
 *		whitespace is echoed, \ ' " are quotes, digits accumulate
 *		into field widths for letters, others are ignored.  n
 *		includes " -> link-to" for symlinks; N does not.  L is
 *		link-to (without " -> ") for symlinks, "?" for others.]
 *	-cpio <device> [write file to cpio archive]   [UNIMPLEMENTED]
 *	-ncpio <device> [write file to cpio -c archive]   [UNIMPLEMENTED]
 *	-newer <file>
 *	-xdev   [UNIMPLEMENTED]
 *	-depth
 *	-sortdirs
 *	( ... )
 *	! ...
 *	... ... [and]
 *	... -a ... [and]
 *	... -o ... [or]
 *
 * For -atime, -mtime, -ctime:
 *
 *	The leading + or - has the same meaning as for <n> arguments.
 *
 *	If the argument is "future", it matches for any time that's in
 *	the future.  The code is careful to not get confused by time
 *	changes after find starts but before it stats the file.
 *
 *	The m number letter clashes between "months" and "minutes".
 *	The interpretation rules:
 *		1) If there are more than two m numbers, an error
 *		   occurs.
 *		2) If there are exactly two m numbers, the first is
 *		   months and the second is minutes.
 *		3) If there are no m numbers, there's no problem.
 *		4) If a w, d, or h number is given, it disambiguates by
 *		   position: an m before it is months, after is
 *		   minutes.
 *		5) If y or s, but not both, is given, then y causes it
 *		   to be taken as months, s as minutes.
 *		6) If no other rule disambiguates, an error occurs.
 *	Letters, when given must appear in the order shown: ymdhms.
 *	The trailing /quantum, when given, specifies the granularity of
 *	the check.  It must follow the same format as the part before
 *	the slash (not including the sign).  Since all times are
 *	divided by the quantum before comparing, it is not usually
 *	useful for the portion before the slash to specify smaller
 *	units than the quantum.  If no quantum is given, the default is
 *	one of the smallest unit explicitly listed before the slash.
 *	For purposes of this syntax, a year is defined as 365.2425 days
 *	of 86400 seconds each, or 31556952 seconds; a month is 1/12 of
 *	this, or 2629746 seconds.
 *
 * This file is in the public domain.
 */

#ifdef __linux__
#define NO_D_NAMLEN /* Linux doesn't have d_namlen(!!) */
#endif

#include <pwd.h>
#include <grp.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <stdarg.h>
#include <unistd.h>
#include <strings.h>
#include <sys/dir.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/wait.h>

extern const char *__progname;

typedef enum {
	  EX_BAD = 0,
	  EX_FALSE,
	  EX_TRUE,
	  EX_NOT,
	  EX_AND,
	  EX_OR,
	  EX_FSTYPE,
	  EX_NAME,
	  EX_QNAME,
	  EX_PATH,
	  EX_QPATH,
	  EX_LINKTO,
	  EX_QLINKTO,
	  EX_PERM,
	  EX_PRUNE,
	  EX_TYPE,
	  EX_LINKS,
	  EX_USER,
	  EX_NOUSER,
	  EX_GROUP,
	  EX_NOGROUP,
	  EX_SIZE,
	  EX_INUM,
	  EX_ATIME,
	  EX_ATIME_F,
	  EX_MTIME,
	  EX_MTIME_F,
	  EX_CTIME,
	  EX_CTIME_F,
	  EX_EXEC,
	  EX_OK,
	  EX_PRINT,
	  EX_PRINT0,
	  EX_PRINTN,
	  EX_COUNT,
	  EX_LS,
	  EX_NEWER,
	  EX_XDEV
#define EX__LAST EX_XDEV
	  } XOP;

typedef struct expr EXPR;
typedef struct cache CACHE;
typedef struct dent DENT;
typedef struct counter COUNTER;

struct counter {
  COUNTER *link;
  char *tag;
  unsigned long long int count;
  } ;

struct dent {
  DENT *link;
  char name[0];
  } ;

struct expr {
  XOP op;
  union {
    EXPR *unary;
    struct {
      EXPR *lhs;
      EXPR *rhs;
      } binary;
    const char *fstype;
    const char *name;
    const char *path;
    const char *linkto;
    const char *facts;
    struct {
      unsigned short int mask;
      unsigned short int cmp;
      } perm;
    unsigned char type;
#define T_B 0x01
#define T_C 0x02
#define T_D 0x04
#define T_F 0x08
#define T_L 0x10
#define T_P 0x20
#define T_S 0x40
    struct {
      unsigned long int n;
      int (*cmp)(unsigned long int /*num*/, unsigned long int /*ref*/);
      } links, size, inum;
    struct tcstruct {
      unsigned long int n;
      unsigned long int divisor;
      int (*cmp)(unsigned long int /*num*/, unsigned long int /*ref*/);
      } atime, mtime, ctime;
    int user;
    int group;
    struct {
      int nargs;
      const char **args;
      } exec, ok;
    unsigned long int newer;
    COUNTER *count;
    } u;
  } ;

struct cache {
  CACHE *link;
  int id;
  const char *name;
  } ;

static int nfiles;
static char **files;

static char **args;
static int firstarg;
static int argptr;
static int lastarg;

static int errs;
static char parse_errmsg[1024];

#define argsleft() (lastarg+1-argptr)
#define moreargs() (argptr <= lastarg)
#define ntharg(n) (args[argptr+(n)])
#define consumen(n) ((void)(argptr+=(n)))
#define nextarg() ntharg(0)
#define consume() consumen(1)
#define unconsume() consumen(-1)

static EXPR *expression;

static int any_side_effects;
static time_t now;
static const char *curfn;
static int cur_len;
static const char *cur_lp;
static struct stat cur_stat;
static unsigned int have;
#define HAVE_LEN  0x00000001
#define HAVE_LP   0x00000002
#define HAVE_STAT 0x00000004
#define curlen curlen_()
#define curlp curlp_()
#define curstat curstat_()

static int depthfirst = 0;
static int sortdirs = 0;
static int pruned;
static COUNTER *counters = 0;

static EXPR **constexprs = 0;

#define UNUSED_ARG(arg) arg __attribute__((__unused__))

static COUNTER *lookup_counter(const char *tag)
{
 COUNTER *c;

 for (c=counters;c;c=c->link) if (tag ? !c->tag : (c->tag&&!strcmp(tag,c->tag))) return(c);
 c = malloc(sizeof(COUNTER));
 c->tag = tag ? strdup(tag) : 0;
 c->count = 0;
 c->link = counters;
 counters = c;
 return(c);
}

static EXPR *const_expr(XOP type)
{
 if ((((int)type) < 1) || (((int)type) > (int)EX__LAST)) abort();
 if (constexprs == 0)
  { int i;
    constexprs = malloc((((int)EX__LAST)+1)*sizeof(EXPR *));
    for (i=0;i<=(int)EX__LAST;i++) constexprs[i] = 0;
  }
 if (! constexprs[(int)type])
  { constexprs[(int)type] = malloc(sizeof(EXPR));
    constexprs[(int)type]->op = type;
  }
 return(constexprs[(int)type]);
}

static void free_expr(EXPR *e)
{
 if (! e) return;
 if (constexprs && (e == constexprs[(int)e->op])) return;
 switch (e->op)
  { case EX_NOT:
       free_expr(e->u.unary);
       break;
    case EX_AND:
    case EX_OR:
       free_expr(e->u.binary.lhs);
       free_expr(e->u.binary.rhs);
       break;
    default:
       break;
  }
 free(e);
}

static int numcmp_equal(unsigned long int num, unsigned long int ref)
{
 return(num==ref);
}

static int numcmp_more(unsigned long int num, unsigned long int ref)
{
 return(num>ref);
}

static int numcmp_less(unsigned long int num, unsigned long int ref)
{
 return(num<ref);
}

/* forward */
static EXPR *parse_primary(void);
static EXPR *parse_lowest(void);

static void parse_err(const char *fmt, ...)
{
 va_list ap;

 if (! errs)
  { va_start(ap,fmt);
    vsprintf(&parse_errmsg[0],fmt,ap);
    va_end(ap);
    errs ++;
  }
}

static void parse_penderr(const char *fmt, ...)
{
 va_list ap;

 if (! errs)
  { va_start(ap,fmt);
    vsprintf(&parse_errmsg[0],fmt,ap);
    va_end(ap);
  }
}

static EXPR *do_not(void)
{
 EXPR *rv;

 rv = malloc(sizeof(EXPR));
 rv->op = EX_NOT;
 rv->u.unary = parse_primary();
 if (! rv->u.unary)
  { parse_err("missing argument to ! operator");
    free(rv);
    rv = 0;
  }
 return(rv);
}

static EXPR *do_paren(void)
{
 EXPR *rv;

 rv = parse_lowest();
 if (! rv)
  { parse_err("missing expression inside ( )");
    return(0);
  }
 if (!moreargs() || strcmp(nextarg(),")"))
  { parse_err("unclosed (");
    return(0);
  }
 consume();
 return(rv);
}

static int do_fstype(EXPR *e)
{
 e->op = EX_FSTYPE;
 e->u.fstype = nextarg();
 return(1);
}

static int do_name(EXPR *e)
{
 e->op = EX_NAME;
 e->u.name = nextarg();
 return(1);
}

static int do_qname(EXPR *e)
{
 e->op = EX_QNAME;
 e->u.name = nextarg();
 return(1);
}

static int do_path(EXPR *e)
{
 e->op = EX_PATH;
 e->u.path = nextarg();
 return(1);
}

static int do_qpath(EXPR *e)
{
 e->op = EX_QPATH;
 e->u.path = nextarg();
 return(1);
}

static int do_linkto(EXPR *e)
{
 e->op = EX_LINKTO;
 e->u.linkto = nextarg();
 return(1);
}

static int do_qlinkto(EXPR *e)
{
 e->op = EX_QLINKTO;
 e->u.linkto = nextarg();
 return(1);
}

inline static int odigit(char c)
{
 return((c>='0')&&(c<='7'));
}

static int charinrange(unsigned char c, const char **rp)
#define UC unsigned char
#define r (*rp)
{
 int matched;

 r ++;
 matched = 0;
 do
  { if (! r[0])
     { fprintf(stderr,"%s: end of string inside [...] in pattern\n",__progname);
       errs ++;
       while (*r) r ++;
       return(0);
     }
    if ((r[1] == '-') && r[2] && ((UC)r[0] < (UC)r[2]))
     { if ((c >= (UC)r[0]) && (c <= (UC)r[2])) matched = 1;
       r += 3;
     }
    else
     { if (c == (UC)r[0]) matched = 1;
       r ++;
     }
  } while (*r != ']');
 r ++;
 return(matched);
}
#undef UC
#undef r

static int matchglob(const char *s, const char *p)
{
 while (1)
  { switch (*p)
     { case '\0':
	  return(!*s);
	  break;
       case '?':
	  if (*s)
	   { s ++;
	     p ++;
	   }
	  else
	   { return(0);
	   }
	  break;
       case '\\':
	  if (p[1] && (*s == p[1]))
	   { s ++;
	     p += 2;
	   }
	  else
	   { return(0);
	   }
	  break;
       case '*':
	  return( ( *s &&
		    ( matchglob(s+1,p) ||
		      matchglob(s+1,p+1) ) ) ||
		  matchglob(s,p+1) );
	  break;
       case '[':
	  if (! charinrange(*s,&p)) return(0);
	  s ++;
	  break;
       default:
	  if (*s == *p)
	   { s ++;
	     p ++;
	   }
	  else
	   { return(0);
	   }
	  break;
     }
  }
}

static int permission(const char *s, char term, unsigned int *vp, const char **rest)
{
 unsigned int v;
 char tmp[11];

 if (odigit(*s))
  { v = 0;
    while (odigit(*s))
     { v = (v << 3) | (*s - '0');
       s ++;
     }
    if (*s == term)
     { *vp = v;
       if (rest) *rest = s;
       return(1);
     }
    return(0);
  }
 if ( (strlen(s) >= 9) &&
      (s[9] == term) &&
      (bcopy(s,&tmp[0],9),(tmp[9]='\0'),1) &&
      matchglob(&tmp[0],"[-r][-w][-xsS][-r][-w][-xsS][-r][-w][-xtT]") )
  { *vp = (((s[2] == 's') || (s[2] == 'S')) << 11) |
	  (((s[5] == 's') || (s[5] == 'S')) << 10) |
	  (((s[8] == 't') || (s[8] == 'T')) <<  9) |
	  ((s[0] == 'r') << 8) |
	  ((s[1] == 'w') << 7) |
	  (((s[2] == 'x') || (s[2] == 's')) << 6) |
	  ((s[3] == 'r') << 5) |
	  ((s[4] == 'w') << 4) |
	  (((s[5] == 'x') || (s[5] == 's')) << 3) |
	  ((s[6] == 'r') << 2) |
	  ((s[7] == 'w') << 1) |
	  (((s[8] == 'x') || (s[8] == 't')) );
    if (rest) *rest = s + 9;
    return(1);
  }
 if ( (strlen(s) >= 10) &&
      (s[10] == term) &&
      (bcopy(s,&tmp[0],10),(tmp[10]='\0'),1) &&
      matchglob(&tmp[0],"[-bcdflps][-r][-w][-xsS][-r][-w][-xsS][-r][-w][-xtT]") )
  { v = (((s[3] == 's') || (s[3] == 'S')) << 11) |
	(((s[6] == 's') || (s[6] == 'S')) << 10) |
	(((s[9] == 't') || (s[9] == 'T')) <<  9) |
	((s[1] == 'r') << 8) |
	((s[2] == 'w') << 7) |
	(((s[3] == 'x') || (s[3] == 's')) << 6) |
	((s[4] == 'r') << 5) |
	((s[5] == 'w') << 4) |
	(((s[6] == 'x') || (s[6] == 's')) << 3) |
	((s[7] == 'r') << 2) |
	((s[8] == 'w') << 1) |
	(((s[9] == 'x') || (s[9] == 't')) );
    switch (s[0])
     { case 'b':           v |= S_IFBLK; break;
       case 'c':           v |= S_IFCHR; break;
       case 'd':           v |= S_IFDIR; break;
       case 'f': case '-': v |= S_IFREG; break;
       case 'l':           v |= S_IFLNK; break;
       case 'p':           v |= S_IFIFO; break;
       case 's':           v |= S_IFSOCK;break;
     }
    *vp = v;
    if (rest) *rest = s + 10;
    return(1);
  }
 return(0);
}

static int do_perm(EXPR *e)
{
 const char *s;
 const char *t;
 unsigned int n1;
 unsigned int n2;

 s = nextarg();
 e->op = EX_PERM;
 if (permission(s,'\0',&n1,0))
  { e->u.perm.mask = 0777;
    e->u.perm.cmp = n1 & 0777;
  }
 else if ((s[0] == '-') && permission(s+1,'\0',&n1,0))
  { n1 &= 017777;
    e->u.perm.mask = n1;
    e->u.perm.cmp = n1;
  }
 else if (permission(s,'/',&n1,&t) && permission(t+1,'\0',&n2,0))
  { e->u.perm.mask = n1;
    e->u.perm.cmp = n2;
  }
 else
  { fprintf(stderr,"%s: bad -perm argument `%s'\n",__progname,s);
    errs ++;
    return(0);
  }
 return(1);
}

static int do_type(EXPR *e)
{
 const char *s;

 e->op = EX_TYPE;
 e->u.type = 0;
 for (s=nextarg();*s;s++)
  { switch (*s)
     { case 'b': e->u.type |= T_B; break;
       case 'c': e->u.type |= T_C; break;
       case 'd': e->u.type |= T_D; break;
       case 'f': e->u.type |= T_F; break;
       case 'l': e->u.type |= T_L; break;
       case 'p': e->u.type |= T_P; break;
       case 's': e->u.type |= T_S; break;
       default:
	  fprintf(stderr,"%s: -type %c unknown\n",__progname,*s);
	  errs ++;
	  break;
     }
  }
 return(1);
}

static int do_links(EXPR *e)
{
 const char *s;

 e->op = EX_LINKS;
 s = nextarg();
 e->u.links.cmp = numcmp_equal;
 switch (*s)
  { case '+': s ++; e->u.links.cmp = numcmp_more; break;
    case '-': s ++; e->u.links.cmp = numcmp_less; break;
  }
 e->u.links.n = atol(s);
 return(1);
}

static int do_user(EXPR *e)
{
 const char *s;
 const char *t;
 struct passwd *pw;

 e->op = EX_USER;
 s = nextarg();
 for (t=s;(*t)&&isdigit((unsigned char)*t);t++) ;
 if (! *t)
  { e->u.user = atoi(s);
  }
 else
  { pw = getpwnam(s);
    if (pw == 0)
     { fprintf(stderr,"%s: -user %s unknown\n",__progname,s);
       errs ++;
       return(0);
     }
    e->u.user = pw->pw_uid;
  }
 return(1);
}

static int do_group(EXPR *e)
{
 const char *s;
 const char *t;
 struct group *gr;

 e->op = EX_GROUP;
 s = nextarg();
 for (t=s;(*t)&&isdigit((unsigned char)*t);t++) ;
 if (! *t)
  { e->u.group = atoi(s);
  }
 else
  { gr = getgrnam(s);
    if (gr == 0)
     { fprintf(stderr,"%s: -group %s unknown\n",__progname,s);
       errs ++;
       return(0);
     }
    e->u.group = gr->gr_gid;
  }
 return(1);
}

static int do_size(EXPR *e)
{
 const char *s;
 char *end;

 e->op = EX_SIZE;
 s = nextarg();
 e->u.size.cmp = numcmp_equal;
 switch (*s)
  { case '+': s ++; e->u.size.cmp = numcmp_more; break;
    case '-': s ++; e->u.size.cmp = numcmp_less; break;
  }
 e->u.size.n = strtol(s,&end,0);
 if (*end != 'c') e->u.size.n *= 512;
 return(1);
}

static int do_inum(EXPR *e)
{
 const char *s;

 e->op = EX_INUM;
 s = nextarg();
 e->u.inum.cmp = numcmp_equal;
 switch (*s)
  { case '+': s ++; e->u.inum.cmp = numcmp_more; break;
    case '-': s ++; e->u.inum.cmp = numcmp_less; break;
  }
 e->u.inum.n = atol(s);
 return(1);
}

static const char *parse_ymwdhms(const char *s, unsigned long int *valp, unsigned long int *unitp)
{
 static struct {
	  const char letter;
	  const unsigned long int mult;
	  unsigned long int n;
	  } units[] = { { 'y', 31556952 /* 365.2425*24*60*60 */ },
#define YEAR 0
			{ 'm', 2629746 /* year/12 */ },
#define MONTH 1
			{ 'w', 7*24*60*60 },
#define WEEK 2
			{ 'd', 24*60*60 },
#define DAY 3
			{ 'h', 60*60 },
#define HOUR 4
			{ 'm', 60 },
#define MINUTE 5
			{ 's', 1 } };
#define SECOND 6
#define NUNITS 7
 unsigned int given;
 int u;
 int v;
 char *tcp;
 const char *t;

 given = 0;
 u = 0;
 while (1)
  { v = strtol(s,&tcp,10);
    t = tcp;
    if (s == t) break;
    if (u >= NUNITS)
     { fprintf(stderr,"%s: too many numbers in time value\n",__progname);
       return(0);
     }
    while ((u < NUNITS) && (units[u].letter != *t)) u ++;
    if (u >= NUNITS)
     { fprintf(stderr,"%s: invalid unit letter in time value\n",__progname);
       return(0);
     }
    units[u].n = v;
    given |= 1 << u;
    u ++;
    s = t + 1;
  }
 if (u == 0)
  { fprintf(stderr,"%s: no number in time value\n",__progname);
    return(0);
  }
 switch (given)
  { case (1<<MONTH):
    case (1<<YEAR)|(1<<MONTH)|(1<<SECOND):
       fprintf(stderr,"%s: ambiguous unit: month or minute?\n",__progname);
       return(0);
       break;
    case (1<<MONTH)|(1<<SECOND):
       units[MINUTE].n = units[MONTH].n;
       given = (1<<MINUTE)|(1<<SECOND);
       break;
  }
 if (unitp) *unitp = units[u].mult;
 v = 0;
 for (u=0;u<NUNITS;u++) if (given & (1<<u)) v += units[u].n * units[u].mult;
 *valp = v;
 return(s);
}

static int timecvt(const char *s, unsigned long int *valp, unsigned long int *divp)
{
 unsigned long int val;
 unsigned long int div;
 const char *t;
 char *tcp;

 val = strtol(s,&tcp,10);
 if (! *tcp)
  { *valp = val * 24 * 60 * 60;
    *divp = 24 * 60 * 60;
    return(1);
  }
 t = parse_ymwdhms(s,&val,&div);
 if (! t)
  { fprintf(stderr,"%s: invalid time value `%s'\n",__progname,s);
    return(0);
  }
 if (*t == '/')
  { t = parse_ymwdhms(t+1,&div,0);
    if (! t)
     { fprintf(stderr,"%s: missing/invalid quantum in time value `%s'\n",__progname,s);
       return(0);
     }
    if (*t)
     { fprintf(stderr,"%s: junk at end of time value `%s'\n",__progname,s);
       return(0);
     }
  }
 else if (*t)
  { fprintf(stderr,"%s: junk at end of time value `%s'\n",__progname,s);
    return(0);
  }
 *valp = val;
 *divp = div;
 return(1);
}

static int do_atime(EXPR *e)
{
 const char *s;

 e->op = EX_ATIME;
 s = nextarg();
 if (!strcmp(s,"future"))
  { e->op = EX_ATIME_F;
    return(1);
  }
 else
  { e->u.atime.cmp = numcmp_equal;
    switch(*s)
     { case '+': s ++; e->u.atime.cmp = numcmp_more; break;
       case '-': s ++; e->u.atime.cmp = numcmp_less; break;
     }
    return(timecvt(s,&e->u.atime.n,&e->u.atime.divisor));
  }
}

static int do_mtime(EXPR *e)
{
 const char *s;

 e->op = EX_MTIME;
 s = nextarg();
 if (!strcmp(s,"future"))
  { e->op = EX_MTIME_F;
    return(1);
  }
 else
  { e->u.mtime.cmp = numcmp_equal;
    switch(*s)
     { case '+': s ++; e->u.mtime.cmp = numcmp_more; break;
       case '-': s ++; e->u.mtime.cmp = numcmp_less; break;
     }
    return(timecvt(s,&e->u.mtime.n,&e->u.mtime.divisor));
  }
}

static int do_ctime(EXPR *e)
{
 const char *s;

 e->op = EX_CTIME;
 s = nextarg();
 if (!strcmp(s,"future"))
  { e->op = EX_CTIME_F;
    return(1);
  }
 else
  { e->u.ctime.cmp = numcmp_equal;
    switch(*s)
     { case '+': s ++; e->u.ctime.cmp = numcmp_more; break;
       case '-': s ++; e->u.ctime.cmp = numcmp_less; break;
     }
    return(timecvt(s,&e->u.ctime.n,&e->u.ctime.divisor));
  }
}

static EXPR *do_exec(void)
{
 EXPR *e;
 const char *s;

 e = malloc(sizeof(EXPR));
 e->op = EX_EXEC;
 e->u.exec.nargs = 0;
 e->u.exec.args = 0;
 while (1)
  { if (! moreargs())
     { fprintf(stderr,"%s: missing or unterminated -exec command\n",__progname);
       errs ++;
       free(e->u.exec.args);
       free(e);
       return(const_expr(EX_FALSE));
     }
    s = nextarg();
    if (!strcmp(s,";")) break;
    e->u.exec.nargs ++;
    e->u.exec.args = realloc(e->u.exec.args,e->u.exec.nargs*sizeof(const char *));
    e->u.exec.args[e->u.exec.nargs-1] = s;
    consume();
  }
 consume();
 return(e);
}

static EXPR *do_ok(void)
{
 EXPR *e;
 const char *s;

 e = malloc(sizeof(EXPR));
 e->op = EX_OK;
 e->u.ok.nargs = 0;
 e->u.ok.args = 0;
 while (1)
  { if (! moreargs())
     { fprintf(stderr,"%s: missing or unterminated -ok command\n",__progname);
       errs ++;
       free(e->u.ok.args);
       free(e);
       return(const_expr(EX_FALSE));
     }
    s = nextarg();
    if (!strcmp(s,";")) break;
    e->u.ok.nargs ++;
    e->u.ok.args = realloc(e->u.ok.args,e->u.ok.nargs*sizeof(const char *));
    e->u.ok.args[e->u.ok.nargs-1] = s;
    consume();
  }
 consume();
 return(e);
}

static int do_lsf(UNUSED_ARG(EXPR *e))
{
 e->op = EX_LS;
 e->u.facts = nextarg();
 return(1);
}

static int do_cpio(UNUSED_ARG(EXPR *e))
{
 fprintf(stderr,"%s: -cpio unimplemented\n",__progname);
 return(0);
}

static int do_ncpio(UNUSED_ARG(EXPR *e))
{
 fprintf(stderr,"%s: -ncpio unimplemented\n",__progname);
 return(0);
}

static int do_newer(EXPR *e)
{
 struct stat stb;

 if (stat(nextarg(),&stb) < 0)
  { fprintf(stderr,"%s: can't stat -newer file %s: %s\n",__progname,nextarg(),strerror(errno));
    errs ++;
    return(0);
  }
 e->op = EX_NEWER;
 e->u.newer = stb.st_mtime;
 return(1);
}

static EXPR *do_ls(void)
{
 EXPR *e;

 e = malloc(sizeof(EXPR));
 e->op = EX_LS;
 e->u.facts = "6i 4b p 2l -8u -8g 8s m n";
 return(e);
}

static int do_count(EXPR *e)
{
 e->op = EX_COUNT;
 e->u.count = lookup_counter(0);
 return(1);
}

static int do_tcount(EXPR *e)
{
 e->op = EX_COUNT;
 e->u.count = lookup_counter(nextarg());
 return(1);
}

static EXPR *do_simple(int (*fn)(EXPR *), int argsneeded)
{
 EXPR *e;

 if (argsleft() < argsneeded)
  { fprintf(stderr,"%s: missing %s to %s\n",__progname,(argsneeded==1)?"argument":"arguments",ntharg(-1));
    consumen(argsleft());
    errs ++;
    return(const_expr(EX_FALSE));
  }
 e = malloc(sizeof(EXPR));
 e->op = EX_BAD;
 if ((*fn)(e))
  { if (e->op == EX_BAD)
     { fprintf(stderr,"%s: op BAD after do_simple call\n",__progname);
       abort();
     }
    consumen(argsneeded);
    return(e);
  }
 free(e);
 errs ++;
 return(const_expr(EX_FALSE));
}

static EXPR *parse_primary(void)
{
 const char *arg;

 if (! moreargs()) return(0);
 arg = nextarg();
 consume();
      if (!strcmp(arg,"!")) return(do_not());
 else if (!strcmp(arg,"(")) return(do_paren());
 else if (!strcmp(arg,"-fstype")) return(do_simple(do_fstype,1));
 else if (!strcmp(arg,"-name")) return(do_simple(do_name,1));
 else if (!strcmp(arg,"-qname")) return(do_simple(do_qname,1));
 else if (!strcmp(arg,"-path")) return(do_simple(do_path,1));
 else if (!strcmp(arg,"-qpath")) return(do_simple(do_qpath,1));
 else if (!strcmp(arg,"-linkto")) return(do_simple(do_linkto,1));
 else if (!strcmp(arg,"-qlinkto")) return(do_simple(do_qlinkto,1));
 else if (!strcmp(arg,"-perm")) return(do_simple(do_perm,1));
 else if (!strcmp(arg,"-prune")) return(const_expr(EX_PRUNE));
 else if (!strcmp(arg,"-type")) return(do_simple(do_type,1));
 else if (!strcmp(arg,"-links")) return(do_simple(do_links,1));
 else if (!strcmp(arg,"-user")) return(do_simple(do_user,1));
 else if (!strcmp(arg,"-nouser")) return(const_expr(EX_NOUSER));
 else if (!strcmp(arg,"-group")) return(do_simple(do_group,1));
 else if (!strcmp(arg,"-nogroup")) return(const_expr(EX_NOGROUP));
 else if (!strcmp(arg,"-size")) return(do_simple(do_size,1));
 else if (!strcmp(arg,"-inum")) return(do_simple(do_inum,1));
 else if (!strcmp(arg,"-atime")) return(do_simple(do_atime,1));
 else if (!strcmp(arg,"-mtime")) return(do_simple(do_mtime,1));
 else if (!strcmp(arg,"-ctime")) return(do_simple(do_ctime,1));
 else if (!strcmp(arg,"-exec"))
  { any_side_effects = 1;
    return(do_exec());
  }
 else if (!strcmp(arg,"-ok"))
  { any_side_effects = 1;
    return(do_ok());
  }
 else if (!strcmp(arg,"-print"))
  { any_side_effects = 1;
    return(const_expr(EX_PRINT));
  }
 else if (!strcmp(arg,"-print0"))
  { any_side_effects = 1;
    return(const_expr(EX_PRINT0));
  }
 else if (!strcmp(arg,"-printn"))
  { any_side_effects = 1;
    return(const_expr(EX_PRINTN));
  }
 else if (!strcmp(arg,"-count"))
  { any_side_effects = 1;
    return(do_simple(&do_count,0));
  }
 else if (!strcmp(arg,"-tcount"))
  { any_side_effects = 1;
    return(do_simple(&do_tcount,1));
  }
 else if (!strcmp(arg,"-ls"))
  { any_side_effects = 1;
    return(do_ls());
  }
 else if (!strcmp(arg,"-lsf"))
  { any_side_effects = 1;
    return(do_simple(do_lsf,1));
  }
 else if (!strcmp(arg,"-cpio")) return(do_simple(do_cpio,1));
 else if (!strcmp(arg,"-ncpio")) return(do_simple(do_ncpio,1));
 else if (!strcmp(arg,"-newer")) return(do_simple(do_newer,1));
 else if (!strcmp(arg,"-xdev")) return(const_expr(EX_XDEV));
 else if (!strcmp(arg,"-depth"))
  { depthfirst = 1;
    return(const_expr(EX_TRUE));
  }
 else if (!strcmp(arg,"-sortdirs"))
  { sortdirs = 1;
    return(const_expr(EX_TRUE));
  }
 else
  { parse_penderr("unknown option `%s'\n",arg);
    unconsume();
    return(0);
  }
}

static EXPR *parse_and(void)
{
 EXPR *lhs;
 EXPR *rhs;
 EXPR *e;

 lhs = parse_primary();
 if (! lhs) return(0);
 while (1)
  { if (! moreargs()) return(lhs);
    if (!strcmp(nextarg(),"-a"))
     { consume();
       rhs = parse_primary();
       if (! rhs)
	{ free_expr(lhs);
	  parse_penderr("missing expression after -a");
	  return(0);
	}
     }
    else
     { rhs = parse_primary();
       if (! rhs) return(lhs);
     }
    e = malloc(sizeof(EXPR));
    e->op = EX_AND;
    e->u.binary.lhs = lhs;
    e->u.binary.rhs = rhs;
    lhs = e;
  }
}

static EXPR *parse_or(void)
{
 EXPR *lhs;
 EXPR *rhs;
 EXPR *e;

 lhs = parse_and();
 if (lhs == 0) return(0);
 while (1)
  { if (!moreargs() || strcmp(nextarg(),"-o")) return(lhs);
    consume();
    rhs = parse_and();
    if (rhs == 0)
     { free_expr(lhs);
       parse_penderr("missing expression after -o");
       return(0);
     }
    e = malloc(sizeof(EXPR));
    e->op = EX_OR;
    e->u.binary.lhs = lhs;
    e->u.binary.rhs = rhs;
    lhs = e;
  }
}

static EXPR *parse_lowest(void)
{
 return(parse_or());
}

static EXPR *append_print(EXPR *e)
{
 EXPR *rv;

 rv = malloc(sizeof(EXPR));
 rv->op = EX_AND;
 rv->u.binary.lhs = e;
 rv->u.binary.rhs = const_expr(EX_PRINT);
 return(rv);
}

static int exprarg(const char *s)
{
 switch (s[0])
  { case '-':
       return(1);
       break;
    case '!': case '(':
       return(!s[1]);
       break;
  }
 return(0);
}

static int get_curlen(void)
{
 cur_len = strlen(curfn);
 have |= HAVE_LEN;
 return(cur_len);
}

static const char *get_curlp(void)
{
 cur_lp = rindex(curfn,'/');
 if (cur_lp) cur_lp ++; else cur_lp = curfn;
 have |= HAVE_LP;
 return(cur_lp);
}

static struct stat get_curstat(void)
{
 if (lstat(curfn,&cur_stat) < 0)
  { fprintf(stderr,"%s: can't stat %s: %s\n",__progname,curfn,strerror(errno));
    errs ++;
    cur_stat.st_mode = 0;
  }
 have |= HAVE_STAT;
 return(cur_stat);
}

inline static int curlen_(void)
{
 return((have&HAVE_LEN) ? cur_len : get_curlen());
}

inline static const char *curlp_(void)
{
 return((have&HAVE_LP) ? cur_lp : get_curlp());
}

inline static struct stat curstat_(void)
{
 return((have&HAVE_STAT) ? cur_stat : get_curstat());
}

static const char *modestr(unsigned short int mode)
{
 static char buf[11];

 switch (mode & S_IFMT)
  { case S_IFBLK: buf[0] = 'b'; break;
    case S_IFCHR: buf[0] = 'c'; break;
    case S_IFDIR: buf[0] = 'd'; break;
    case S_IFREG: buf[0] = '-'; break;
    case S_IFLNK: buf[0] = 'l'; break;
    case S_IFIFO: buf[0] = 'p'; break;
    case S_IFSOCK:buf[0] = 's'; break;
    default:      buf[0] = '?'; break;
  }
 buf[1] = (mode & 0400) ? 'r' : '-';
 buf[2] = (mode & 0200) ? 'w' : '-';
 switch (mode & 04100)
  { case 04100: buf[3] = 's'; break;
    case 04000: buf[3] = 'S'; break;
    case 00100: buf[3] = 'x'; break;
    case 00000: buf[3] = '-'; break;
  }
 buf[4] = (mode & 0040) ? 'r' : '-';
 buf[5] = (mode & 0020) ? 'w' : '-';
 switch (mode & 02010)
  { case 02010: buf[6] = 's'; break;
    case 02000: buf[6] = 'S'; break;
    case 00010: buf[6] = 'x'; break;
    case 00000: buf[6] = '-'; break;
  }
 buf[7] = (mode & 0004) ? 'r' : '-';
 buf[8] = (mode & 0002) ? 'w' : '-';
 switch (mode & 01001)
  { case 01001: buf[9] = 't'; break;
    case 01000: buf[9] = 'T'; break;
    case 00001: buf[9] = 'x'; break;
    case 00000: buf[9] = '-'; break;
  }
 buf[10] = '\0';
 return(&buf[0]);
}

static int cache_lookup(CACHE **cachep, int id, const char **value)
{
 CACHE *c;
 CACHE *last;
 CACHE **lastp;

 last = 0;
 lastp = cachep;
 c = *cachep;
 while (c)
  { if (c->id == id)
     { *value = c->name;
       if (last)
	{ *lastp = c;
	  last->link = c->link;
	  c->link = last;
	}
       return(1);
     }
    if (last) lastp = &last->link;
    last = c;
    c = c->link;
  }
 return(0);
}

static void cache_enter(CACHE **cachep, int id, const char *value)
{
 CACHE *t;
 char *s;

 t = malloc(sizeof(CACHE));
 t->id = id;
 if (value)
  { s = malloc(strlen(value)+1);
    strcpy(s,value);
    t->name = s;
  }
 else
  { t->name = 0;
  }
 t->link = *cachep;
 *cachep = t;
}

static const char *name_for_uid(int uid)
{
 static CACHE *cache = 0;
 const char *val;
 struct passwd *pw;

 if (cache_lookup(&cache,uid,&val)) return(val);
 pw = getpwuid(uid);
 if (pw)
  { cache_enter(&cache,uid,pw->pw_name);
    return(pw->pw_name);
  }
 else
  { cache_enter(&cache,uid,0);
    return(0);
  }
}

static const char *name_for_gid(int gid)
{
 static CACHE *cache = 0;
 const char *val;
 struct group *gr;

 if (cache_lookup(&cache,gid,&val)) return(val);
 gr = getgrgid(gid);
 if (gr)
  { cache_enter(&cache,gid,gr->gr_name);
    return(gr->gr_name);
  }
 else
  { cache_enter(&cache,gid,0);
    return(0);
  }
}

static const char *userstr(int uid)
{
 static char buf[64];
 const char *s;

 s = name_for_uid(uid);
 if (! s)
  { sprintf(&buf[0],"%d",uid);
    s = &buf[0];
  }
 return(s);
}

static const char *groupstr(int gid)
{
 static char buf[64];
 const char *s;

 s = name_for_gid(gid);
 if (! s)
  { sprintf(&buf[0],"%d",gid);
    s = &buf[0];
  }
 return(s);
}

static char *getlinkname(UNUSED_ARG(const char *fn))
{
 char *t;
 int n;
#ifdef ultrix
 char linkto[10240];
#else
 int tsize;
#endif

#ifdef ultrix
 n = readlink(curfn,&linkto[0],sizeof(linkto));
 t = malloc(n+1);
 bcopy(&linkto[0],t,n);
#else
 tsize = 32;
 t = malloc(tsize);
 while (1)
  { n = readlink(curfn,t,tsize);
    if (n < tsize) break;
    free(t);
    t = malloc(tsize*=2);
  }
#endif
 t[n] = '\0';
 return(t);
}

static int exec_command(int nargs, const char **args)
{
 int i;
 int pid;
 int xs;
 const char *s;
 const char **av;

 av = malloc((nargs+1)*sizeof(const char *));
 for (i=0;i<nargs;i++)
  { s = args[i];
    if (!strcmp(s,"{}")) s = curfn;
    av[i] = s;
  }
 av[i] = 0;
 pid = fork();
 if (pid == 0)
  { execvp(av[0],(const void *)av);
    perror(av[0]);
    _exit(-1);
  }
 while (1)
  { i = wait(&xs);
    if (i < 0)
     { fprintf(stderr,"%s: lost child process %d?\n",__progname,pid);
       return(1);
     }
    if (i == pid) break;
  }
 return(WIFEXITED(xs)&&(WEXITSTATUS(xs)==0));
}

static int timecmp(struct tcstruct *s, time_t t)
{
 if (t > now) t = now;
 return((*s->cmp)((now-t)/s->divisor,s->n/s->divisor));
}

static int timefuture(time_t t)
{
 static time_t realnow = 0;

 if (t > realnow)
  { time(&realnow);
    if (t > realnow) return(1);
  }
 return(0);
}

static const char *timestr(time_t t)
{
 static char buf[13];
 char *tmp;

 tmp = ctime(&t);
 if ((now < t) || (now-t > 15778476)) /* 365.2425*24*60*60 / 2 */
  { sprintf(&buf[0],"%.6s  %.4s",tmp+4,tmp+20);
  }
 else
  { sprintf(&buf[0],"%.12s",tmp+4);
  }
 return(&buf[0]);
}

static void print_ls_output(const char *fmt)
{
 const char *fp;
 unsigned int q;
#define Q_B 1U
#define Q_S 2U
#define Q_D 4U
 int n;
 int nneg;
 int m;
 int mneg;

 q = 0;
 n = 0;
 nneg = 1;
 for (fp=fmt;*fp;fp++)
  { if (q & Q_B)
     { putchar(*fp);
       q &= ~Q_B;
       continue;
     }
    if (q)
     { if ( ((q & Q_S) && (*fp == '\'')) ||
	    ((q & Q_D) && (*fp == '"')) )
	{ q = 0;
	}
       else if (*fp == '\\')
	{ q |= Q_B;
	}
       else
	{ putchar(*fp);
	}
       continue;
     }
    m = n;
    mneg = nneg;
    n = 0;
    nneg = 1;
    switch (*fp)
     {     { long long int v;
	     /* if (0) */ {
       case 'b': v = curstat.st_blocks;
	     } if (0) { 
       case 'i': v = curstat.st_ino;
	     } if (0) { 
       case 'l': v = curstat.st_nlink;
	     } if (0) { 
       case 's': v = curstat.st_size;
	     }
	     m *= mneg;
		  if (m < 0) printf("%-*lld",-m,v);
	     else if (m > 0) printf("%*lld",m,v);
	     else            printf("%lld",v);
	   }
	  break;
	   { const char *s;
	     if (0) {
       case 'g': s = groupstr(curstat.st_gid);
	     } if (0) {
       case 'm': s = timestr(curstat.st_mtime);
	     } if (0) {
       case 'N': s = curfn;
	     } if (0) {
       case 'p': s = modestr(curstat.st_mode);
	     } if (0) {
       case 'u': s = userstr(curstat.st_uid);
	     }
	     m *= mneg;
		  if (m < 0) printf("%-*s",-m,s);
	     else if (m > 0) printf("%*s",m,s);
	     else            printf("%s",s);
	   }
	  break;
       case 'n':
	   { const char *s;
	     char *sfree;
	     if ((curstat.st_mode & S_IFMT) == S_IFLNK)
	      { char *t;
		t = getlinkname(curfn);
		sfree = malloc(strlen(curfn)+4+strlen(t)+1);
		sprintf(sfree,"%s -> %s",curfn,t);
		free(t);
		s = sfree;
	      }
	     else
	      { s = curfn;
		sfree = 0;
	      }
	     if (0)
	      {
       case 'L':
		if ((curstat.st_mode & S_IFMT) == S_IFLNK)
		 { sfree = getlinkname(curfn);
		   s = sfree;
		 }
		else
		 { s = "?";
		   sfree = 0;
		 }
	      }
	     m *= mneg;
		  if (m < 0) printf("%-*s",-m,s);
	     else if (m > 0) printf("%*s",m,s);
	     else            printf("%s",s);
	     if (sfree) free(sfree);
	   }
	  break;
       case ' ': case '\t':
	  putchar(*fp);
	  break;
       case '-':
	  nneg = 1;
	  break;
       case '0': case '1': case '2': case '3': case '4':
       case '5': case '6': case '7': case '8': case '9':
	  nneg = mneg;
	  n = (m * 10) + (*fp - '0');
	  break;
       case '\\': q |= Q_B; break;
       case '\'': q |= Q_S; break;
       case '"': q |= Q_D; break;
     }
  }
 printf("\n");
#undef Q_B
#undef Q_S
#undef Q_D
}

static const char *curlinkto(void)
{
 static int len = 0;
 static char *buf = 0;
 int n;

 if (len < 1)
  { len = 8;
    buf = malloc(len);
  }
 while (1)
  { n = readlink(curfn,buf,len);
    if (n < 0)
     { fprintf(stderr,"%s: %s: %s\n",__progname,curfn,(errno==EINVAL)?"Not a symbolic link":strerror(errno));
       return(0);
     }
    if (n < len)
     { buf[n] = '\0';
       return(buf);
     }
    else if (len > 40000)
     { fprintf(stderr,"%s: %s: link-to string overflow\n",__progname,curfn);
       return(0);
     }
    else
     { free(buf);
       len <<= 1;
       buf = malloc(len);
     }
  }
}

static int evalexpr(EXPR *e)
{
 switch (e->op)
  { case EX_BAD:
       fprintf(stderr,"%s: INTERNAL ERROR: bad expression op made it to eval\n",__progname);
       abort();
       break;
    case EX_FALSE:
       return(0);
       break;
    case EX_TRUE:
       return(1);
       break;
    case EX_NOT:
       return(!evalexpr(e->u.unary));
       break;
    case EX_AND:
       return(evalexpr(e->u.binary.lhs)&&evalexpr(e->u.binary.rhs));
       break;
    case EX_OR:
       return(evalexpr(e->u.binary.lhs)||evalexpr(e->u.binary.rhs));
       break;
    case EX_FSTYPE:
       fprintf(stderr,"%s: -fstype unimplemented\n",__progname);
       return(0);
       break;
    case EX_NAME:
       return(matchglob(curlp,e->u.name));
       break;
    case EX_QNAME:
       return(!strcmp(curlp,e->u.name));
       break;
    case EX_PATH:
       return(matchglob(curfn,e->u.path));
       break;
    case EX_QPATH:
       return(!strcmp(curfn,e->u.path));
       break;
    case EX_LINKTO:
	{ const char *lt;
	  if ((curstat.st_mode & S_IFMT) != S_IFLNK) return(0);
	  lt = curlinkto();
	  return(lt&&matchglob(lt,e->u.linkto));
	}
       break;
    case EX_QLINKTO:
	{ const char *lt;
	  if ((curstat.st_mode & S_IFMT) != S_IFLNK) return(0);
	  lt = curlinkto();
	  return(lt&&!strcmp(lt,e->u.linkto));
	}
       break;
    case EX_PERM:
       return((curstat.st_mode & e->u.perm.mask) == e->u.perm.cmp);
       break;
    case EX_PRUNE:
       pruned = 1;
       return(1);
       break;
    case EX_TYPE:
	{ int bit;
	  switch (curstat.st_mode & S_IFMT)
	   { case S_IFBLK: bit = T_B; break;
	     case S_IFCHR: bit = T_C; break;
	     case S_IFDIR: bit = T_D; break;
	     case S_IFREG: bit = T_F; break;
	     case S_IFIFO: bit = T_P; break;
	     case S_IFLNK: bit = T_L; break;
	     case S_IFSOCK:bit = T_S; break;
	     default:
		fprintf(stderr,"%s: %s: unknown mode %#o\n",__progname,curfn,curstat.st_mode);
		break;
	   }
	  return(e->u.type & bit);
	}
       break;
    case EX_LINKS:
       return((e->u.links.cmp)(curstat.st_nlink,e->u.links.n));
       break;
    case EX_USER:
       return(curstat.st_uid == e->u.user);
       break;
    case EX_NOUSER:
       return(!name_for_uid(curstat.st_uid));
       break;
    case EX_GROUP:
       return(curstat.st_gid == e->u.group);
       break;
    case EX_NOGROUP:
       return(!name_for_gid(curstat.st_gid));
       break;
    case EX_SIZE:
       return((e->u.size.cmp)(curstat.st_size,e->u.size.n));
       break;
    case EX_INUM:
       return((e->u.inum.cmp)(curstat.st_ino,e->u.inum.n));
       break;
    case EX_ATIME:
       return(timecmp(&e->u.atime,curstat.st_atime));
       break;
    case EX_ATIME_F:
       return(timefuture(curstat.st_atime));
       break;
    case EX_MTIME:
       return(timecmp(&e->u.mtime,curstat.st_mtime));
       break;
    case EX_MTIME_F:
       return(timefuture(curstat.st_mtime));
       break;
    case EX_CTIME:
       return(timecmp(&e->u.ctime,curstat.st_ctime));
       break;
    case EX_CTIME_F:
       return(timefuture(curstat.st_ctime));
       break;
    case EX_EXEC:
       return(exec_command(e->u.exec.nargs,e->u.exec.args));
       break;
    case EX_OK:
	{ int i;
	  int c1;
	  const char *s;
	  printf("<");
	  for (i=0;i<e->u.ok.nargs;i++)
	   { s = e->u.ok.args[i];
	     if (!strcmp(s,"{}")) s = curfn;
	     printf(" %s",s);
	   }
	  printf(" >? ");
	  c1 = getchar();
	  for (i=c1;(i!='\n')&&(i!=EOF);i=getchar()) ;
	  if (i == EOF) exit(0);
	  return((c1=='y')?exec_command(e->u.ok.nargs,e->u.ok.args):1);
	}
       break;
    case EX_PRINT:
       printf("%s\n",curfn);
       return(1);
       break;
    case EX_PRINT0:
       printf("%s%c",curfn,0);
       return(1);
       break;
    case EX_PRINTN:
       printf("%d %s\n",(int)strlen(curfn),curfn);
       return(1);
       break;
    case EX_COUNT:
       e->u.count->count ++;
       return(1);
       break;
    case EX_LS:
       print_ls_output(e->u.facts);
       return(1);
       break;
    case EX_NEWER:
       return(curstat.st_mtime > e->u.newer);
       break;
    case EX_XDEV:
       fprintf(stderr,"%s: -xdev unimplemented\n",__progname);
       return(0);
       break;
  }
 fprintf(stderr,"%s: INTERNAL ERROR: expression op %d\n",__progname,(int)e->op);
 abort();
}

/* forward */
static void process(const char *);

static void recurse(const char *name)
{
 char *buf;
 int l;
 const char *fmt;

 l = curlen + 1 + strlen(name) + 1;
 if ((curlen > 0) && (curfn[curlen-1] == '/'))
  { l --;
    fmt = "%s%s";
  }
 else
  { fmt = "%s/%s";
  }
 buf = malloc(l);
 sprintf(buf,fmt,curfn,name);
 process(buf);
 free(buf);
}

static DENT *sort_dents(DENT *list)
{
 DENT *a;
 DENT *b;
 DENT *t;
 DENT **lp;

 if (!list || !list->link) return(list);
 a = 0;
 b = 0;
 while (list)
  { t = list;
    list = t->link;
    t->link = a;
    a = b;
    b = t;
  }
 a = sort_dents(a);
 b = sort_dents(b);
 lp = &list;
 while (1)
  { if (a && (!b || (strcmp(&a->name[0],&b->name[0]) < 0)))
     { t = a;
       a = t->link;
     }
    else if (b)
     { t = b;
       b = t->link;
     }
    else
     { break;
     }
    *lp = t;
    lp = &t->link;
  }
 *lp = 0;
 return(list);
}

static void process(const char *fn)
{
 DENT *list;

 curfn = fn;
 have = 0;
 pruned = 0;
 list = 0;
 if (! depthfirst) evalexpr(expression);
 if (! pruned)
  { if ((curstat.st_mode & S_IFMT) == S_IFDIR)
     { DIR *dir;
       struct direct *d;
       dir = opendir(curfn);
       if (dir == 0)
	{ fprintf(stderr,"%s: can't recurse into %s\n",__progname,curfn);
	}
       else
	{ while ((d=readdir(dir)))
	   { if ( (d->d_fileno == 0) ||
		  ( (d->d_name[0] == '.') &&
		    (
#ifdef NO_D_NAMLEN
		      (d->d_name[1] == '\0')
#else
		      (d->d_namlen == 1)
#endif
					     ||
		      ( (d->d_name[1] == '.') &&
#ifdef NO_D_NAMLEN
			(d->d_name[2] == '\0')
#else
			(d->d_namlen == 2)
#endif
					       ) ) ) ) continue;
	     if (sortdirs)
	      { DENT *e;
#ifdef NO_D_NAMLEN
		e = malloc(sizeof(DENT)+strlen(&d->d_name[0])+1);
		strcpy(&e->name[0],&d->d_name[0]);
#else
		e = malloc(sizeof(DENT)+d->d_namlen+1);
		bcopy(&d->d_name[0],&e->name[0],d->d_namlen+1);
#endif
		e->link = list;
		list = e;
	      }
	     else
	      { curfn = fn;
		recurse(&d->d_name[0]);
	      }
	   }
	  closedir(dir);
	  if (sortdirs)
	   { list = sort_dents(list);
	     while (list)
	      { DENT *e;
		e = list;
		list = e->link;
		curfn = fn;
		recurse(&e->name[0]);
		free(e);
	      }
	   }
	}
     }
  }
 pruned = 0;
 if (depthfirst)
  { evalexpr(expression);
    if (pruned)
     { static int warned = 0;
       if (! warned)
	{ fprintf(stderr,"%s: warning: -prune has no effect with -depth\n",__progname);
	  warned = 1;
	}
     }
  }
}

static void top_process(const char *fn)
{
 process(fn);
}

int main(int, char **);
int main(int ac, char **av)
{
 int i;

 files = av + 1;
 for (i=1;(i<ac)&&!exprarg(av[i]);i++) ;
 nfiles = i - 1;
 if (nfiles < 1)
  { fprintf(stderr,"Usage: %s pathname [pathname...] expression\n",__progname);
    exit(1);
  }
 args = av;
 firstarg = i;
 argptr = i;
 lastarg = ac - 1;
 errs = 0;
 any_side_effects = 0;
 expression = parse_lowest();
 if ((expression == 0) || moreargs()) errs ++;
 if (errs)
  { fprintf(stderr,"%s: %s\n",__progname,&parse_errmsg[0]);
    exit(1);
  }
 if (! any_side_effects) expression = append_print(expression);
 time(&now);
 for (i=0;i<nfiles;i++) top_process(files[i]);
 if (counters)
  { COUNTER *c;
    for (c=counters;c;c=c->link) if (c->tag) printf("%llu %s\n",c->count,c->tag); else printf("%llu\n",c->count);
  }
 exit(0);
}