toys/pending/find.c - third_party/toybox - Git at Google

 /* vi: set sw=4 ts=4:
  *
  * find.c - find files matching a criteria
  *
  * Copyright 2012 Tim Bird <tbird20d@gmail.com>
  *
  * See http://opengroup.org/onlinepubs/9699919799/utilities/find.html

 USE_FIND(NEWTOY(find, "?", TOYFLAG_USR|TOYFLAG_BIN))

 config FIND
   bool "find"
   default n
   help
     usage: find [DIR] [<options>]

     -name <pattern>    match pattern
     -type [bcdflps]    match file type
     !, -a, -o          not, and , or
     (, )               group expressions
     -mtime [-+]n       match file modification time (to within 24 hours)
     \t\t               +=greater (older) than, -=less (younger) than

     File types:
     b  block device  d  directory     l  symlink  s  socket
     c  char device   f  regular file  p  FIFO
 */

 /* To Do:
  * -exec action
  */

 #define FOR_find
 #include "toys.h"

 struct filter_node {
   struct filter_node *next;
   int op;
   union {
     char *name_regex;
     struct {
       int sign;
       time_t time;
     } t;
     mode_t type;
     struct {
       int arg_path_index;
       char **exec_args;
     } e;
   } data;
 };

 GLOBALS(
   char *dir;
   struct filter_node *filter_root;
   time_t itime;
 )

 /* filter operation types */
 #define OP_UNKNOWN	0
 #define OP_OR		2
 #define OP_AND		3
 #define OP_NOT		4

 #define LPAREN		1
 #define RPAREN		5

 #define MAX_OP		5

 #define CHECK_NAME	7
 #define CHECK_MTIME	8
 #define CHECK_TYPE	9

 #define ACTION_PRINT	20
 #define ACTION_PRINT0	21
 #define ACTION_EXEC	22

 #define IS_ACTION(x)    (x >= 20)

 /* executes the command for a filter node
    returns 0 for failure or 1 for success
  */
 static int do_exec(struct filter_node *filter, struct dirtree *node)
 {
   char *path = NULL;
   char **arg_array;
   pid_t pid;
   int status;

   arg_array = filter->data.e.exec_args;
   if (filter->data.e.arg_path_index) {
     int plen;
     path = dirtree_path(node, &plen);
     arg_array[filter->data.e.arg_path_index] = path;
   }

   if (!(pid = fork())) xexec(arg_array);
   free(path);
   waitpid(pid, &status, 0);

   return !WEXITSTATUS(status);
 }

 /* prefix evaluator */
 /* returns 0 for failure or 1 for success */
 static int evaluate(struct filter_node *filter, struct dirtree *node,
   struct filter_node **fnext)
 {
   int result;
   int op;
   static int skip = 0;

   /* if no filters, success */
   if (!filter) {
     *fnext = NULL;
     return 1;
   }
   op = filter->op;

   if (op==OP_NOT) return !evaluate(filter->next, node, fnext);

   if (op==OP_OR || op==OP_AND) {
     result = evaluate(filter->next, node, fnext);
     if(!skip) {
       if (op==OP_OR) {
         skip = result;
         result = evaluate(*fnext, node, fnext) || result;
       } else {
         skip = !result;
         result = evaluate(*fnext, node, fnext) && result;
       }
       skip = 0;
     }
     else result = evaluate(*fnext, node, fnext);
     return result;
   }

   // we're down to single operations, mark our position
   *fnext = filter->next;
   if(skip) return 0;

   // TODO: Do a regex comparison
   if (op==CHECK_NAME)
     return !strcmp(filter->data.name_regex, node->name);

   if (op==CHECK_MTIME) {
     long delta = (long)(((double)TT.itime - node->st.st_mtime) / 86400)
                  -filter->data.t.time;
     return filter->data.t.sign == (delta > 0) - (delta < 0);
   }
   if (op==CHECK_TYPE) return (node->st.st_mode & S_IFMT) == filter->data.type;


   if (op==ACTION_PRINT || op==ACTION_PRINT0) {
     char *path;
     int plen = 0;
     char terminator = (op==ACTION_PRINT)*'\n';

     path = dirtree_path(node, &plen);
     printf("%s%c", path, terminator);
     free(path);
     return 1;
   }

   if (op==ACTION_EXEC) return !do_exec(filter, node);

   error_msg("Ran out of operations in filter list!");
   return 1;
 }

 static int check_node_callback(struct dirtree *node)
 {
   struct filter_node *junk;

   /* only recurse on "." at the root */
   /* so, don't recurse on 1) non-root "." and 2) any ".." */

   if (node->name[0] == '.' &&
     ((!node->name[1] && node->parent) ||
     (node->name[1]=='.' && !node->name[2])))
     return 0;

   evaluate(TT.filter_root, node, &junk);
   return DIRTREE_RECURSE;
 }


 static void build_filter_list(void)
 {
   struct filter_node *node_list, *op_stack, *node, *op_node, *next;
   char **arg;
   int j;
   int prevop = 0;
   int have_action = 0;

   /* part optargs here and build a filter list in prefix format */

   TT.dir = ".";
   node_list = NULL;
   for (arg = toys.optargs; *arg; arg++) {
     struct {
       char *arg;
       int op;
       int extrarg;
     } arg_map[] = {{"-o", OP_OR, 0},
                    {"-a", OP_AND, 0},
                    {"!", OP_NOT, 0},
                    {"(", LPAREN, 0},
                    {")", RPAREN, 0},
                    {"-name", CHECK_NAME, 1},
                    {"-mtime", CHECK_MTIME, 1},
                    {"-type", CHECK_TYPE, 1},
                    {"-print", ACTION_PRINT, 0},
                    {"-print0", ACTION_PRINT0, 0},
                    {"-exec", ACTION_EXEC, 1}
     };
     mode_t types[]={S_IFREG,S_IFDIR,S_IFCHR,S_IFBLK,S_IFLNK,S_IFSOCK,S_IFIFO};
     char **arg_array;
     node = (struct filter_node *) xmalloc(sizeof(struct filter_node));
     node->op = OP_UNKNOWN;
     for (j=0; j < sizeof(arg_map)/sizeof(*arg_map); j++) {
       if (!strcmp(*arg, arg_map[j].arg)) {
         node->op = arg_map[j].op;
         if (arg_map[j].extrarg && !*(++arg))
 	   error_exit("Missing argument to %s", arg_map[j].arg);
 	break;
       }
     }

     switch(node->op) {
       case CHECK_NAME:
         node->data.name_regex = *arg;
         break;
       case CHECK_MTIME:
         switch(**arg) {
           case '+':
             node->data.t.sign=+1;
             (*arg)++;
             break;
           case '-':
             node->data.t.sign=-1;
             (*arg)++;
             break;
           default:
             node->data.t.sign=0;
             break;
         }
         node->data.t.time = atoi(*arg);
         break;
       case CHECK_TYPE:
         if (-1 == (j = stridx("fdcblsp", **arg)))
           error_exit("bad type '%s'", *arg);
         else node->data.type = types[j];
         break;
       case ACTION_EXEC:
         arg_array = xmalloc(sizeof(char *));
         for (j = 0; *arg && strcmp(*arg, ";"); j++) {
           /* new method */
           arg_array = xrealloc(arg_array, sizeof(char *) * (j+2));
           arg_array[j] = *arg;
           if (!strcmp(*arg, "{}")) node->data.e.arg_path_index = j;

           arg++;
         }
         if (!*arg) error_exit("need ';' in exec");
         arg_array[j] = 0;
         node->data.e.exec_args = arg_array;
         break;
     }

     have_action |= IS_ACTION(node->op);

     if (node->op == OP_UNKNOWN) {
       if (**arg == '-') error_exit("bad option '%s'", *arg);
       else TT.dir = *arg;
     }  else {
       // add OP_AND where necessary
       if (node_list) {
         int o1 = node_list->op, o2 = node->op;
         if ((o1>MAX_OP && o2>MAX_OP) ||
            (o1==RPAREN && o2>=OP_NOT && o2!=RPAREN) ||
            (o1>=OP_NOT && o1!=LPAREN && o2==LPAREN)) {
           struct filter_node *n = (struct filter_node *)
                                   xmalloc(sizeof(struct filter_node));
           n->op = OP_AND;
           n->next = node_list;
           node_list = n;
         }
       }
       /* push node */
       node->next = node_list;;
       node_list = node;
     }

   }

   /* now convert from infix to prefix */
   if(have_action) TT.filter_root = NULL;
   else TT.filter_root = &(struct filter_node){0, ACTION_PRINT};
   op_stack = NULL;
   node = node_list;
   while( node ) {
     int op = node->op;
     next = node->next;
     if (op==LPAREN || op==RPAREN) {
       free(node);
       node = 0;
     }
     if (op<=MAX_OP) {
       if (prevop > op) {
         /* pop opstack to output */
         op_node = op_stack;
         while (op_node) {
           /* remove from op_stack */
           op_stack = op_node->next;
           /* push to output */
           op_node->next = TT.filter_root;
           TT.filter_root = op_node;
           /* get next node */
           op_node = op_stack;
         }
       }
       if (node) {
         /* push to opstack */
         node->next = op_stack;
         op_stack = node;
       }
       prevop = op*(op!=RPAREN);
     }
     else {
         /* push to output */
         node->next = TT.filter_root;
         TT.filter_root = node;
     }
     node = next;
   }
   /* end of input - push opstack to output */
   /* pop opstack to output till empty */
   op_node = op_stack;
   while (op_node) {
     op_stack = op_node->next;
     op_node->next = TT.filter_root;
     TT.filter_root = op_node;
     op_node = op_stack;
   }
   if(!have_action) {
     node = TT.filter_root;
     TT.filter_root = (struct filter_node*) xmalloc(sizeof(struct filter_node));
     TT.filter_root->next = node;
     TT.filter_root->op = OP_AND;
   }
 }

 void find_main(void)
 {
   TT.itime = time(NULL);
   /* parse filters, if present */
   build_filter_list();

   /* FIXTHIS - parse actions, if present */

   dirtree_read(TT.dir, check_node_callback);
 }
	/* vi: set sw=4 ts=4:
	*
	* find.c - find files matching a criteria
	*
	* Copyright 2012 Tim Bird <tbird20d@gmail.com>
	*
	* See http://opengroup.org/onlinepubs/9699919799/utilities/find.html

	USE_FIND(NEWTOY(find, "?", TOYFLAG_USR\|TOYFLAG_BIN))

	config FIND
	bool "find"
	default n
	help
	usage: find [DIR] [<options>]

	-name <pattern> match pattern
	-type [bcdflps] match file type
	!, -a, -o not, and , or
	(, ) group expressions
	-mtime [-+]n match file modification time (to within 24 hours)
	\t\t +=greater (older) than, -=less (younger) than

	File types:
	b block device d directory l symlink s socket
	c char device f regular file p FIFO
	*/

	/* To Do:
	* -exec action
	*/

	#define FOR_find
	#include "toys.h"

	struct filter_node {
	struct filter_node *next;
	int op;
	union {
	char *name_regex;
	struct {
	int sign;
	time_t time;
	} t;
	mode_t type;
	struct {
	int arg_path_index;
	char **exec_args;
	} e;
	} data;
	};

	GLOBALS(
	char *dir;
	struct filter_node *filter_root;
	time_t itime;
	)

	/* filter operation types */
	#define OP_UNKNOWN 0
	#define OP_OR 2
	#define OP_AND 3
	#define OP_NOT 4

	#define LPAREN 1
	#define RPAREN 5

	#define MAX_OP 5

	#define CHECK_NAME 7
	#define CHECK_MTIME 8
	#define CHECK_TYPE 9

	#define ACTION_PRINT 20
	#define ACTION_PRINT0 21
	#define ACTION_EXEC 22

	#define IS_ACTION(x) (x >= 20)

	/* executes the command for a filter node
	returns 0 for failure or 1 for success
	*/
	static int do_exec(struct filter_node filter, struct dirtree node)
	{
	char *path = NULL;
	char **arg_array;
	pid_t pid;
	int status;

	arg_array = filter->data.e.exec_args;
	if (filter->data.e.arg_path_index) {
	int plen;
	path = dirtree_path(node, &plen);
	arg_array[filter->data.e.arg_path_index] = path;
	}

	if (!(pid = fork())) xexec(arg_array);
	free(path);
	waitpid(pid, &status, 0);

	return !WEXITSTATUS(status);
	}

	/* prefix evaluator */
	/* returns 0 for failure or 1 for success */
	static int evaluate(struct filter_node filter, struct dirtree node,
	struct filter_node **fnext)
	{
	int result;
	int op;
	static int skip = 0;

	/* if no filters, success */
	if (!filter) {
	*fnext = NULL;
	return 1;
	}
	op = filter->op;

	if (op==OP_NOT) return !evaluate(filter->next, node, fnext);

	if (op==OP_OR \|\| op==OP_AND) {
	result = evaluate(filter->next, node, fnext);
	if(!skip) {
	if (op==OP_OR) {
	skip = result;
	result = evaluate(*fnext, node, fnext) \|\| result;
	} else {
	skip = !result;
	result = evaluate(*fnext, node, fnext) && result;
	}
	skip = 0;
	}
	else result = evaluate(*fnext, node, fnext);
	return result;
	}

	// we're down to single operations, mark our position
	*fnext = filter->next;
	if(skip) return 0;

	// TODO: Do a regex comparison
	if (op==CHECK_NAME)
	return !strcmp(filter->data.name_regex, node->name);

	if (op==CHECK_MTIME) {
	long delta = (long)(((double)TT.itime - node->st.st_mtime) / 86400)
	-filter->data.t.time;
	return filter->data.t.sign == (delta > 0) - (delta < 0);
	}
	if (op==CHECK_TYPE) return (node->st.st_mode & S_IFMT) == filter->data.type;


	if (op==ACTION_PRINT \|\| op==ACTION_PRINT0) {
	char *path;
	int plen = 0;
	char terminator = (op==ACTION_PRINT)*'\n';

	path = dirtree_path(node, &plen);
	printf("%s%c", path, terminator);
	free(path);
	return 1;
	}

	if (op==ACTION_EXEC) return !do_exec(filter, node);

	error_msg("Ran out of operations in filter list!");
	return 1;
	}

	static int check_node_callback(struct dirtree *node)
	{
	struct filter_node *junk;

	/* only recurse on "." at the root */
	/* so, don't recurse on 1) non-root "." and 2) any ".." */

	if (node->name[0] == '.' &&
	((!node->name[1] && node->parent) \|\|
	(node->name[1]=='.' && !node->name[2])))
	return 0;

	evaluate(TT.filter_root, node, &junk);
	return DIRTREE_RECURSE;
	}


	static void build_filter_list(void)
	{
	struct filter_node node_list, op_stack, node, op_node, *next;
	char **arg;
	int j;
	int prevop = 0;
	int have_action = 0;

	/* part optargs here and build a filter list in prefix format */

	TT.dir = ".";
	node_list = NULL;
	for (arg = toys.optargs; *arg; arg++) {
	struct {
	char *arg;
	int op;
	int extrarg;
	} arg_map[] = {{"-o", OP_OR, 0},
	{"-a", OP_AND, 0},
	{"!", OP_NOT, 0},
	{"(", LPAREN, 0},
	{")", RPAREN, 0},
	{"-name", CHECK_NAME, 1},
	{"-mtime", CHECK_MTIME, 1},
	{"-type", CHECK_TYPE, 1},
	{"-print", ACTION_PRINT, 0},
	{"-print0", ACTION_PRINT0, 0},
	{"-exec", ACTION_EXEC, 1}
	};
	mode_t types[]={S_IFREG,S_IFDIR,S_IFCHR,S_IFBLK,S_IFLNK,S_IFSOCK,S_IFIFO};
	char **arg_array;
	node = (struct filter_node *) xmalloc(sizeof(struct filter_node));
	node->op = OP_UNKNOWN;
	for (j=0; j < sizeof(arg_map)/sizeof(*arg_map); j++) {
	if (!strcmp(*arg, arg_map[j].arg)) {
	node->op = arg_map[j].op;
	if (arg_map[j].extrarg && !*(++arg))
	error_exit("Missing argument to %s", arg_map[j].arg);
	break;
	}
	}

	switch(node->op) {
	case CHECK_NAME:
	node->data.name_regex = *arg;
	break;
	case CHECK_MTIME:
	switch(**arg) {
	case '+':
	node->data.t.sign=+1;
	(*arg)++;
	break;
	case '-':
	node->data.t.sign=-1;
	(*arg)++;
	break;
	default:
	node->data.t.sign=0;
	break;
	}
	node->data.t.time = atoi(*arg);
	break;
	case CHECK_TYPE:
	if (-1 == (j = stridx("fdcblsp", **arg)))
	error_exit("bad type '%s'", *arg);
	else node->data.type = types[j];
	break;
	case ACTION_EXEC:
	arg_array = xmalloc(sizeof(char *));
	for (j = 0; arg && strcmp(arg, ";"); j++) {
	/* new method */
	arg_array = xrealloc(arg_array, sizeof(char ) (j+2));
	arg_array[j] = *arg;
	if (!strcmp(*arg, "{}")) node->data.e.arg_path_index = j;

	arg++;
	}
	if (!*arg) error_exit("need ';' in exec");
	arg_array[j] = 0;
	node->data.e.exec_args = arg_array;
	break;
	}

	have_action \|= IS_ACTION(node->op);

	if (node->op == OP_UNKNOWN) {
	if (*arg == '-') error_exit("bad option '%s'", arg);
	else TT.dir = *arg;
	} else {
	// add OP_AND where necessary
	if (node_list) {
	int o1 = node_list->op, o2 = node->op;
	if ((o1>MAX_OP && o2>MAX_OP) \|\|
	(o1==RPAREN && o2>=OP_NOT && o2!=RPAREN) \|\|
	(o1>=OP_NOT && o1!=LPAREN && o2==LPAREN)) {
	struct filter_node n = (struct filter_node )
	xmalloc(sizeof(struct filter_node));
	n->op = OP_AND;
	n->next = node_list;
	node_list = n;
	}
	}
	/* push node */
	node->next = node_list;;
	node_list = node;
	}

	}

	/* now convert from infix to prefix */
	if(have_action) TT.filter_root = NULL;
	else TT.filter_root = &(struct filter_node){0, ACTION_PRINT};
	op_stack = NULL;
	node = node_list;
	while( node ) {
	int op = node->op;
	next = node->next;
	if (op==LPAREN \|\| op==RPAREN) {
	free(node);
	node = 0;
	}
	if (op<=MAX_OP) {
	if (prevop > op) {
	/* pop opstack to output */
	op_node = op_stack;
	while (op_node) {
	/* remove from op_stack */
	op_stack = op_node->next;
	/* push to output */
	op_node->next = TT.filter_root;
	TT.filter_root = op_node;
	/* get next node */
	op_node = op_stack;
	}
	}
	if (node) {
	/* push to opstack */
	node->next = op_stack;
	op_stack = node;
	}
	prevop = op*(op!=RPAREN);
	}
	else {
	/* push to output */
	node->next = TT.filter_root;
	TT.filter_root = node;
	}
	node = next;
	}
	/* end of input - push opstack to output */
	/* pop opstack to output till empty */
	op_node = op_stack;
	while (op_node) {
	op_stack = op_node->next;
	op_node->next = TT.filter_root;
	TT.filter_root = op_node;
	op_node = op_stack;
	}
	if(!have_action) {
	node = TT.filter_root;
	TT.filter_root = (struct filter_node*) xmalloc(sizeof(struct filter_node));
	TT.filter_root->next = node;
	TT.filter_root->op = OP_AND;
	}
	}

	void find_main(void)
	{
	TT.itime = time(NULL);
	/* parse filters, if present */
	build_filter_list();

	/* FIXTHIS - parse actions, if present */

	dirtree_read(TT.dir, check_node_callback);
	}