toys/pending/find.c - platform_external_toybox - Gitiles

 /* 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 [fcdl]       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
 */

 /* To Do:
  * -exec action
  */

 #include "toys.h"

 #define SECONDS_PER_DAY (24*60*60)

 int have_action;

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

 static struct filter_node *filter_root;

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

 #define LPAREN		4
 #define RPAREN		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 TEST_LT		0
 #define TEST_EQ		1
 #define TEST_GT		2

 /* executes the command for a filter node
  * return the program return value (0=success)
  */
 static int do_exec(struct filter_node *filter, struct dirtree *node)
 {
 	char *path;
 	int plen;
 	char **arg_array;
 	pid_t pid;
 	int ccode;
 	int status;

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

 	pid = fork();
 	if (!pid) {
 		/* child */
 		xexec(arg_array);
 	} else {
 		/* parent */
 		/* wait for child */
 		waitpid(pid, &status, 0);
 		ccode = WEXITSTATUS(status);
 	}
 	free(path);

 	return ccode;
 }

 /* 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;
 	char *path;
 	int plen = 0;
 	struct stat st_buf;
 	time_t node_time;
 	char terminator;

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

 	if (filter->op==OP_NOT) {
 		return !evaluate(filter->next, node, fnext);
 	}
 	if (filter->op==OP_OR) {
 		return evaluate(filter->next, node, fnext) || evaluate(*fnext, node, fnext);
 	}
 	if (filter->op==OP_AND) {
 		return evaluate(filter->next, node, fnext) && evaluate(*fnext, node, fnext);
 	}
 	/* we're down to single operations, mark our position */
 	*fnext = filter->next;
 	if (filter->op==CHECK_NAME) {
 		// TODO: Do a regex comparison
 		return !strcmp(filter->data.name_regex, node->name);
 	}
 	if (filter->op==CHECK_MTIME) {
 		/* do mtime check */
 		path = dirtree_path(node, &plen);
 		result = stat(path,  &st_buf);
 		free(path);
 		if (result<0) {
 			return 0;
 		}
 		node_time = st_buf.st_mtime/SECONDS_PER_DAY;
 		result = 1;
 		switch (filter->data.t.time_op) {
 			/* do time compare here */
 			case TEST_LT:
 				/* FIXTHIS - should result be < or <= ?*/
 				if (node_time > filter->data.t.time)
 					result = 0;
 				break;
 			case TEST_GT:
 				if (node_time < filter->data.t.time)
 					result = 0;
 				break;
 			case TEST_EQ:
 				if (node_time != filter->data.t.time)
 					result = 0;
 				break;
 			default:
 				/* how'd I get here? */
 				result = 0;
 				break;
 		}
 		return result;

 	}
 	if (filter->op==CHECK_TYPE) {
 		path = dirtree_path(node, &plen);
 		result = lstat(path,  &st_buf);
 		free(path);
 		if (result<0) {
 			return 0;
 		}
 		return (st_buf.st_mode & S_IFMT) == filter->data.type;
 	}


 	if (filter->op==ACTION_PRINT || filter->op==ACTION_PRINT0) {
 		if (filter->op==ACTION_PRINT) {
 			terminator = '\n';
 		} else {
 			terminator = 0;
 		}
 		path = dirtree_path(node, &plen);
 		printf("%s%c", path, terminator);
 		free(path);
 		return 1;
 	}

 	if (filter->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)
 {
 	char *path;
 	int plen = 0;
 	int result;
 	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;

 	result = evaluate(filter_root, node, &junk);
 	if (result & !have_action) {
 		/* default action is just print the path */
 		path = dirtree_path(node, &plen);
 		printf("%s\n", path);
 		free(path);
 	}
 	return DIRTREE_RECURSE;
 }


 static void build_filter_list(void)
 {
 	struct filter_node *node_list;
 	struct filter_node *op_stack;
 	struct filter_node *node, *op_node;
 	struct filter_node *next;

 	char *arg, **arg_array;
 	int i, j;

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

 	node_list = NULL;
 	toybuf[0] = 0;
 	have_action = 0;
 	for(i=0; toys.optargs[i]; i++) {
 		node = (struct filter_node *)
 			xmalloc(sizeof(struct filter_node));
 		node->op = OP_UNKNOWN;
 		arg = toys.optargs[i];
 		if (!strcmp(arg, "-o")) {
 			node->op = OP_OR;
 		}
 		if (!strcmp(arg, "-a")) {
 			node->op = OP_AND;
 		}
 		if (!strcmp(arg, "!")) {
 			node->op = OP_NOT;
 		}
 		if (!strcmp(arg, "(")) {
 			node->op = LPAREN;
 		}
 		if (!strcmp(arg, ")")) {
 			node->op = RPAREN;
 		}

 		if (!strcmp(arg, "-name")) {
 			node->op = CHECK_NAME;
 			arg = toys.optargs[++i];
 			if (!arg) error_exit("Missing argument to -name\n");
 			node->data.name_regex = arg;
 		}

 		if (!strcmp(arg, "-mtime")) {
 			node->op = CHECK_MTIME;
 			arg = toys.optargs[++i];
 			if (!arg) error_exit("Missing argument to -mtime\n");
 			switch(arg[0]) {
 				case '+':
 					node->data.t.time_op=TEST_GT;
 					arg++;
 					break;
 				case '-':
 					node->data.t.time_op=TEST_LT;
 					arg++;
 					break;
 				default:
 					node->data.t.time_op=TEST_EQ;
 					break;
 			}
 			/* convert to days (very crudely) */
 			node->data.t.time = atoi(arg)/SECONDS_PER_DAY;
 		}

 		if (!strcmp(arg, "-type")) {
 			node->op = CHECK_TYPE;
 			arg = toys.optargs[++i];
 			if (!arg) error_exit("Missing argument to -type\n");
 			switch(arg[0]) {
 				case 'f':
 					node->data.type = S_IFREG;
 					break;
 				case 'd':
 					node->data.type = S_IFDIR;
 					break;
 				case 'c':
 					node->data.type = S_IFCHR;
 					break;
 				case 'b':
 					node->data.type = S_IFBLK;
 					break;
 				case 'l':
 					node->data.type = S_IFLNK;
 					break;
 				case 's':
 					node->data.type = S_IFSOCK;
 					break;
 				case 'p':
 					/* named pipe */
 					node->data.type = S_IFIFO;
 					break;
 				default:
 					error_exit("Unknown file type '%s'\n", arg);
 			}
 		}
 		if (!strcmp(arg, "-print")) {
 			node->op = ACTION_PRINT;
 			have_action = 1;
 		}
 		if (!strcmp(arg, "-print0")) {
 			node->op = ACTION_PRINT0;
 			have_action = 1;
 		}
 		if (!strcmp(arg, "-exec")) {
 			node->op = ACTION_EXEC;
 			have_action = 1;
 			arg_array = xmalloc(sizeof(char *));
 			arg = toys.optargs[++i];
 			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 = toys.optargs[++i];
 			}
 			if (!arg) error_exit("Missing ';' in exec command\n");
 			arg_array[j] = 0;
 			node->data.e.exec_args = arg_array;
 		}
 		if (node->op == OP_UNKNOWN) {
 			if (arg[0] == '-') error_exit("Unknown option '%s'\n", arg);
 			else {
 				/* use toybuf as start directory */
 				strcpy(toybuf, arg);
 			}
 		}  else {
 			/* push node */
 			node->next = node_list;;
 			node_list = node;
 		}

 	}

 	/* now convert from infix to prefix */
 	filter_root = NULL;
 	op_stack = NULL;
 	node = node_list;
 	while( node ) {
 		next = node->next;
 		switch( node->op ) {
 			case OP_AND:
 			case OP_OR:
 			case OP_NOT:
 			case RPAREN:
 				/* push to opstack */
 				node->next = op_stack;
 				op_stack = node;
 				break;
 			case LPAREN:
 				free(node);
 				/* pop opstack to output (up to rparen) */
 				op_node = op_stack;
 				while (op_node && op_node->op != RPAREN) {
 					/* remove from op_stack */
 					op_stack = op_node->next;
 					/* push to output */
 					op_node->next = filter_root;
 					filter_root = op_node;
 					/* get next node */
 					op_node = op_stack;
 				}
 				/* rparen should be on op_stack */
 				if (!op_stack) error_exit("Missing right paren\n");
 				/* remove rparen from op_stack */
 				op_stack = op_stack->next;
 				free(op_node);
 				break;
 			default:
 				/* push to output */
 				node->next = filter_root;
 				filter_root = node;
 				break;
 		}
 		node = next;
 	}
 	/* end of input - push opstack to output */
 	/* pop opstack to output till empty */
 	op_node = op_stack;
 	while (op_node) {
 		/*if (op_node->op == RPAREN || op_node->op == LPAREN)  {
 			error_exit("Error: extra paren found\n");
 		}
 		*/
 		op_stack = op_node->next;
 		op_node->next = filter_root;
 		filter_root = op_node;
 		op_node = op_stack;
 	}
 }

 void find_main(void)
 {
 	/* parse filters, if present */
 	/* also, fill toybuf with the directory to start in, if present */
 	build_filter_list();

 	/* FIXTHIS - parse actions, if present */

 	if (!toybuf[0]) {
 		strcpy(toybuf, ".");
 	}
 	dirtree_read(toybuf, 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 [fcdl] 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
	*/

	/* To Do:
	* -exec action
	*/

	#include "toys.h"

	#define SECONDS_PER_DAY (246060)

	int have_action;

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

	static struct filter_node *filter_root;

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

	#define LPAREN 4
	#define RPAREN 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 TEST_LT 0
	#define TEST_EQ 1
	#define TEST_GT 2

	/* executes the command for a filter node
	* return the program return value (0=success)
	*/
	static int do_exec(struct filter_node filter, struct dirtree node)
	{
	char *path;
	int plen;
	char **arg_array;
	pid_t pid;
	int ccode;
	int status;

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

	pid = fork();
	if (!pid) {
	/* child */
	xexec(arg_array);
	} else {
	/* parent */
	/* wait for child */
	waitpid(pid, &status, 0);
	ccode = WEXITSTATUS(status);
	}
	free(path);

	return ccode;
	}

	/* 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;
	char *path;
	int plen = 0;
	struct stat st_buf;
	time_t node_time;
	char terminator;

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

	if (filter->op==OP_NOT) {
	return !evaluate(filter->next, node, fnext);
	}
	if (filter->op==OP_OR) {
	return evaluate(filter->next, node, fnext) \|\| evaluate(*fnext, node, fnext);
	}
	if (filter->op==OP_AND) {
	return evaluate(filter->next, node, fnext) && evaluate(*fnext, node, fnext);
	}
	/* we're down to single operations, mark our position */
	*fnext = filter->next;
	if (filter->op==CHECK_NAME) {
	// TODO: Do a regex comparison
	return !strcmp(filter->data.name_regex, node->name);
	}
	if (filter->op==CHECK_MTIME) {
	/* do mtime check */
	path = dirtree_path(node, &plen);
	result = stat(path, &st_buf);
	free(path);
	if (result<0) {
	return 0;
	}
	node_time = st_buf.st_mtime/SECONDS_PER_DAY;
	result = 1;
	switch (filter->data.t.time_op) {
	/* do time compare here */
	case TEST_LT:
	/* FIXTHIS - should result be < or <= ?*/
	if (node_time > filter->data.t.time)
	result = 0;
	break;
	case TEST_GT:
	if (node_time < filter->data.t.time)
	result = 0;
	break;
	case TEST_EQ:
	if (node_time != filter->data.t.time)
	result = 0;
	break;
	default:
	/* how'd I get here? */
	result = 0;
	break;
	}
	return result;

	}
	if (filter->op==CHECK_TYPE) {
	path = dirtree_path(node, &plen);
	result = lstat(path, &st_buf);
	free(path);
	if (result<0) {
	return 0;
	}
	return (st_buf.st_mode & S_IFMT) == filter->data.type;
	}


	if (filter->op==ACTION_PRINT \|\| filter->op==ACTION_PRINT0) {
	if (filter->op==ACTION_PRINT) {
	terminator = '\n';
	} else {
	terminator = 0;
	}
	path = dirtree_path(node, &plen);
	printf("%s%c", path, terminator);
	free(path);
	return 1;
	}

	if (filter->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)
	{
	char *path;
	int plen = 0;
	int result;
	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;

	result = evaluate(filter_root, node, &junk);
	if (result & !have_action) {
	/* default action is just print the path */
	path = dirtree_path(node, &plen);
	printf("%s\n", path);
	free(path);
	}
	return DIRTREE_RECURSE;
	}


	static void build_filter_list(void)
	{
	struct filter_node *node_list;
	struct filter_node *op_stack;
	struct filter_node node, op_node;
	struct filter_node *next;

	char arg, *arg_array;
	int i, j;

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

	node_list = NULL;
	toybuf[0] = 0;
	have_action = 0;
	for(i=0; toys.optargs[i]; i++) {
	node = (struct filter_node *)
	xmalloc(sizeof(struct filter_node));
	node->op = OP_UNKNOWN;
	arg = toys.optargs[i];
	if (!strcmp(arg, "-o")) {
	node->op = OP_OR;
	}
	if (!strcmp(arg, "-a")) {
	node->op = OP_AND;
	}
	if (!strcmp(arg, "!")) {
	node->op = OP_NOT;
	}
	if (!strcmp(arg, "(")) {
	node->op = LPAREN;
	}
	if (!strcmp(arg, ")")) {
	node->op = RPAREN;
	}

	if (!strcmp(arg, "-name")) {
	node->op = CHECK_NAME;
	arg = toys.optargs[++i];
	if (!arg) error_exit("Missing argument to -name\n");
	node->data.name_regex = arg;
	}

	if (!strcmp(arg, "-mtime")) {
	node->op = CHECK_MTIME;
	arg = toys.optargs[++i];
	if (!arg) error_exit("Missing argument to -mtime\n");
	switch(arg[0]) {
	case '+':
	node->data.t.time_op=TEST_GT;
	arg++;
	break;
	case '-':
	node->data.t.time_op=TEST_LT;
	arg++;
	break;
	default:
	node->data.t.time_op=TEST_EQ;
	break;
	}
	/* convert to days (very crudely) */
	node->data.t.time = atoi(arg)/SECONDS_PER_DAY;
	}

	if (!strcmp(arg, "-type")) {
	node->op = CHECK_TYPE;
	arg = toys.optargs[++i];
	if (!arg) error_exit("Missing argument to -type\n");
	switch(arg[0]) {
	case 'f':
	node->data.type = S_IFREG;
	break;
	case 'd':
	node->data.type = S_IFDIR;
	break;
	case 'c':
	node->data.type = S_IFCHR;
	break;
	case 'b':
	node->data.type = S_IFBLK;
	break;
	case 'l':
	node->data.type = S_IFLNK;
	break;
	case 's':
	node->data.type = S_IFSOCK;
	break;
	case 'p':
	/* named pipe */
	node->data.type = S_IFIFO;
	break;
	default:
	error_exit("Unknown file type '%s'\n", arg);
	}
	}
	if (!strcmp(arg, "-print")) {
	node->op = ACTION_PRINT;
	have_action = 1;
	}
	if (!strcmp(arg, "-print0")) {
	node->op = ACTION_PRINT0;
	have_action = 1;
	}
	if (!strcmp(arg, "-exec")) {
	node->op = ACTION_EXEC;
	have_action = 1;
	arg_array = xmalloc(sizeof(char *));
	arg = toys.optargs[++i];
	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 = toys.optargs[++i];
	}
	if (!arg) error_exit("Missing ';' in exec command\n");
	arg_array[j] = 0;
	node->data.e.exec_args = arg_array;
	}
	if (node->op == OP_UNKNOWN) {
	if (arg[0] == '-') error_exit("Unknown option '%s'\n", arg);
	else {
	/* use toybuf as start directory */
	strcpy(toybuf, arg);
	}
	} else {
	/* push node */
	node->next = node_list;;
	node_list = node;
	}

	}

	/* now convert from infix to prefix */
	filter_root = NULL;
	op_stack = NULL;
	node = node_list;
	while( node ) {
	next = node->next;
	switch( node->op ) {
	case OP_AND:
	case OP_OR:
	case OP_NOT:
	case RPAREN:
	/* push to opstack */
	node->next = op_stack;
	op_stack = node;
	break;
	case LPAREN:
	free(node);
	/* pop opstack to output (up to rparen) */
	op_node = op_stack;
	while (op_node && op_node->op != RPAREN) {
	/* remove from op_stack */
	op_stack = op_node->next;
	/* push to output */
	op_node->next = filter_root;
	filter_root = op_node;
	/* get next node */
	op_node = op_stack;
	}
	/* rparen should be on op_stack */
	if (!op_stack) error_exit("Missing right paren\n");
	/* remove rparen from op_stack */
	op_stack = op_stack->next;
	free(op_node);
	break;
	default:
	/* push to output */
	node->next = filter_root;
	filter_root = node;
	break;
	}
	node = next;
	}
	/* end of input - push opstack to output */
	/* pop opstack to output till empty */
	op_node = op_stack;
	while (op_node) {
	/*if (op_node->op == RPAREN \|\| op_node->op == LPAREN) {
	error_exit("Error: extra paren found\n");
	}
	*/
	op_stack = op_node->next;
	op_node->next = filter_root;
	filter_root = op_node;
	op_node = op_stack;
	}
	}

	void find_main(void)
	{
	/* parse filters, if present */
	/* also, fill toybuf with the directory to start in, if present */
	build_filter_list();

	/* FIXTHIS - parse actions, if present */

	if (!toybuf[0]) {
	strcpy(toybuf, ".");
	}
	dirtree_read(toybuf, check_node_callback);
	}