/**********************************************************************/
/*                                                                    */
/* find - Version 1.0                                                 */
/*                                                                    */
/* Copyright (c) 1988 - Rodney Lewis                                  */
/* This program is freely copyable and distributable. All copyrights  */
/* are reserved by the author. You may give copies of this program to */
/* anyone you wish but you may not sell it.                           */
/*                                                                    */
/* Pattern matching routine taken from Matt Dillon's csh program;     */
/* reproduced by permission.                                          */
/*                                                                    */
/**********************************************************************/

/**********************************************************************/
/*                                                                    */
/* find    - searches the directory hierachy looking for files that   */
/*           match a given boolean expression. Based  on  the  U**X   */
/*           find command.                                            */
/*                                                                    */
/**********************************************************************/

#include <exec/types.h>
#include <exec/memory.h>
#include <libraries/dosextens.h>
#include <stdio.h>
#include <functions.h>

#define MAXARGS		20
#define NULL_PRIM	(struct primary *) NULL
#define EQ(x,y)		(strcmp(x, y) == 0)
#define PROTECTION	(FIBF_READ | FIBF_WRITE | FIBF_EXECUTE | FIBF_DELETE)

/* boolean expression node structure */

struct node {
	unsigned long		type;
	struct node	*first;
	struct node	*second;
};

/* Node types - must be different from primary node types (below) */

#define OR	0x000000ff
#define AND	0x0000ff00
#define NOT	0x00ff0000

/* structure to hold interpreted primary information */

struct primary {
	unsigned long		type;
	unsigned long		size;
	char				*data[MAXARGS];
};

/* start of compiled expression tree */

struct node *node_head;

/* Primary types */

#define PRINT	0x00000001
#define NAME	0x00000002
#define SIZE	0x00000004
#define TYPE	0x00000008
#define EXEC	0x00000010
#define NEWER	0x00000020
#define MTIME	0x00000040
#define PERM	0x00000080
#define PRIMS	0x0000ffff

/* type qualifiers */

#define DIRECT	0x00010000		/* directory for -type */
#define PLAIN	0x00020000		/* plain file for -type */
#define PROMPT	0x00040000		/* prompt for EXEC */
#define LT		0x00080000		/* greater than */
#define GT		0x00100000		/* less than */
#define CHAR	0x00200000		/* use characters in -size check */
#define QUALS	0xffff0000

int breakflag = FALSE;

char path[80] = "";				/* memory to hold full path name */
struct DateStamp date;

/* manx releases the memory allocated by calloc when you call exit() */

extern char		*calloc();

main(argc, argv)
int argc;
char *argv[];
{
	register struct FileLock *start;
	register i;
	extern struct node *compile();

	DateStamp(&date);

	/* must be at least three arguments */

	if (argc < 3) {
		fprintf(stderr, "Usage: find <path-list> <expression>\n");
		exit(1);
	}

	/* find the start of the boolean expression */

	for (i = 1 ; argv[i][0] != '-' && argv[i][0] != '!' && argv[i][0] != '(' ; i++);
	if (i == 1) {
		/* no path name list */
		fprintf(stderr, "Usage: find <path-list> <expression>\n");
		exit(1);
	}

	/* compile the boolean expression */

	if (node_head = compile(argc - i, &argv[i])) {

		/* search each path-name specified */

		for (i = 1 ; argv[i][0] != '-' && argv[i][0] != '!' && argv[i][0] != '(' ; ++i) {
			start = Lock(argv[i], ACCESS_READ);
			if (start == NULL) {
				fprintf(stderr, "can't access '%s'\n", argv[i]);
				continue;
			}

			search(start);
			UnLock(start);
		}
	}

	exit(0);
}

/* search the given directory and for each file
 * execute the boolean expression.
 */

search(lock)
register struct FileLock *lock;
{
	register struct FileInfoBlock *fib;
	register struct FileLock *nlock;
	char *prev, file[80];

	fib = (struct FileInfoBlock *) AllocMem((long) sizeof(struct FileInfoBlock), MEMF_CLEAR);
	if (fib == NULL) {
		fprintf(stderr, "can't allocate file info block\n");
		return(0);
	}

	/* save current position in full path name */

	prev = path + strlen(path);

	if (*path == '\0' && pwd(ParentDir(lock)) == 0) {
		FreeMem(fib, (long) sizeof(struct FileInfoBlock));
		return(0);
	}

	/* examine initial path name */

	if (Examine(lock, fib)) {

		/* execute the expression on the inital path */

		execute(node_head, fib);

		if (fib->fib_DirEntryType > 0) {

			/* set up printable path name */

			if (*path) {
				strcat(path, fib->fib_FileName);
				strcat(path, "/");
			}
			else if (pwd(lock) == 0) {
				*prev = '\0';
				FreeMem(fib, (long) sizeof(struct FileInfoBlock));
				return(0);
			}
		}

		else {

			/* if initial path name is not a directory then we just return */

			*prev = '\0';
			FreeMem(fib, (long) sizeof(struct FileInfoBlock));
			return(0);
		}

		/* examine directory contents */

		while(ExNext(lock, fib)) {
			if (breakflag) break;

			/* recurse if we have found a directory */

			if (fib->fib_DirEntryType > 0) {
				strcpy(file, path);
				strcat(file, fib->fib_FileName);
				nlock = Lock(file, ACCESS_READ);
				if (nlock == NULL)
					fprintf(stderr, "locking error - %s\n", file);
				else {
					search(nlock);
					UnLock(nlock);
				}
			}
			else
				execute(node_head, fib);

			if (SetSignal(0L, 0L) & SIGBREAKF_CTRL_C) {
				breakflag = TRUE;
				break;
			}
		}
	}

	*prev = '\0';
	FreeMem(fib, (long) sizeof(struct FileInfoBlock));
}

/* execute the boolean expression on the given file */

execute(cnode, fib)
struct node *cnode;
struct FileInfoBlock *fib;
{
	register struct primary *prim;
	register long checksize;
	register j;
	register struct DateStamp *ds;
	char file[80], ok[10];
	char *av[MAXARGS];

	/* check node type */

	if (cnode->type == AND)
		if  (execute(cnode->first, fib))
			return(execute(cnode->second, fib));
		else
			return(0);

	else if (cnode->type == OR)
		if  (execute(cnode->first, fib))
			return(1);
		else
			return(execute(cnode->second, fib));

	else if (cnode->type == NOT)
		return(!execute(cnode->first, fib));

	else {

		/* we have an actual primary */

		prim = (struct primary *) cnode;
		switch (prim->type & PRIMS) {

		case PRINT:

			if (*path)
				printf("%s%s\n", path, fib->fib_FileName);
			else
				printf("%s:\n", fib->fib_FileName);
			return(1);

		case NAME:

			if (compare_ok(prim->data[0], fib->fib_FileName))
				return(1);
			else
				return(0);

		case SIZE:

			if (prim->type & CHAR)
				checksize = fib->fib_Size;
			else
				checksize = fib->fib_NumBlocks;

			if (((prim->type & GT) && (checksize > prim->size) ) ||
				((prim->type & LT) && (checksize < prim->size) ) ||
				((prim->type & (GT | LT)) == 0 && (checksize == prim->size)))
				return(1);
			else
				return(0);

		case TYPE:

			switch (prim->type & QUALS | (fib->fib_DirEntryType > 0)) {

			case DIRECT:
			case (PLAIN | 1):
				return(0);

			default:
				return(1);
			}

		case EXEC:

			for (j = 0 ; prim->data[j] ; j++)
				if (EQ("{}", prim->data[j])) {
					strcpy(file, path);
					strcat(file, fib->fib_FileName);
					av[j] = file;
				}
				else
					av[j] = prim->data[j];
			av[j] = NULL;

			if (!(prim->type & PROMPT) || (pr_cmd(av) && gets(ok) &&
				 ((ok[0] == 'y') || (ok[0] == 'Y')))) {
				if (fexecv(av[0], av) == -1)
					return(0);
				else if (wait())
					return(0);
				else
					return(1);
			}

		case NEWER:

			ds = (struct DateStamp *) prim->data[0];
			if (fib->fib_Date.ds_Days > ds->ds_Days)
				return(1);
			else if (fib->fib_Date.ds_Days == ds->ds_Days &&
					 fib->fib_Date.ds_Minute > ds->ds_Minute)
				return(1);
			else if (fib->fib_Date.ds_Days == ds->ds_Days &&
					 fib->fib_Date.ds_Minute == ds->ds_Minute &&
					 fib->fib_Date.ds_Tick > ds->ds_Tick)
				return(1);
			else
				return(0);

		case MTIME:

			checksize = date.ds_Days - fib->fib_Date.ds_Days;

			if (((prim->type & GT) && (checksize > prim->size) ) ||
				((prim->type & LT) && (checksize < prim->size) ) ||
				((prim->type & (GT | LT)) == 0 && (checksize == prim->size)))
				return(1);
			else
				return(0);

		case PERM:

			if ((fib->fib_Protection & PROTECTION) == prim->size)
				return(1);
			else
				return(0);

		}
		return(0);
	}
}

/* print the command to be executed on the screen */

pr_cmd(av)
char *av[];
{
	register j;

	printf("< ");
	for (j = 0 ; av[j] ; j++) printf("%s ", av[j]);
	printf("> ? ");
	return(1);
}

/* compile the boolean expression: returns a pointer to the start
 * of the compiled expression tree, or NULL if a failure occurs.
 */

struct node *
compile(argc, argv)
int argc;
char *argv[];
{
	register i, j, scan;
	register struct primary *prim;
	register struct node *node_head = (struct node *) NULL, *tmp_node;

	for(i = 0 ; i < argc ; i++) {

		prim = (struct primary *) calloc(1, sizeof(struct primary));
		if (prim == NULL_PRIM) {
			fprintf(stderr, "out memory in primary interpretation\n");
			exit(5);
		}


		if (EQ("-o", argv[i])) {
			free(prim);

			/* -o cannot be the first argument */

			if (node_head == NULL_PRIM) {
				fprintf(stderr, "misplaced 'or' operator ... ignored\n");
				continue;
			}

			else {

				/* create OR node */

				tmp_node = (struct node *) calloc(1, sizeof(struct node));
				if (tmp_node == NULL) {
					fprintf(stderr, "out of memory in expression compilation");
					exit(5);
				}
				tmp_node->type = OR;
				tmp_node->first = node_head;

				/* compile rest of expression and attach it to OR node */

				if ((tmp_node->second = compile(argc - i - 1, argv + i + 1)) == NULL) {
					free(tmp_node);
					return(node_head);
				}
				else
					return(tmp_node);
			}
		}

		else if (EQ("(", argv[i])) {
			free(prim);

			/* scan to matching brackets */

			for (j = 0, scan = 0 ; ++i < argc && (!EQ(")", argv[i]) || scan != 0) ; j++) {
				if (EQ("(", argv[i])) scan++;
				if (EQ(")", argv[i])) scan--;
			}

			if (i >= argc) {
				fprintf(stderr, "unmatched bracket\n");
				exit(5);
			}

			if (j == 0) {
				fprintf(stderr, "empty brackets ... ignored\n");
				continue;
			}

			/* compile what is in the brackets */

			if ((prim = (struct primary *) compile(j, argv + i - j)) == NULL)
				continue;
		}

		else if (EQ("!", argv[i])) {
			if (++i >= argc) {
				fprintf(stderr, "trailing '!' ignored\n");
				continue;
			}
			if (EQ("-o", argv[i])) {
				fprintf(stderr, "illegal 'or' operator placement\n");
				exit(5);
			}

			tmp_node = (struct node *) calloc(1, sizeof(struct node));
			if (tmp_node == NULL) {
				fprintf(stderr, "out of memory in expression compilation\n");
				exit(5);
			}
			tmp_node->type = NOT;

			if (EQ("(", argv[i])) {

				/* scan to matching bracket */

				for (j = 0, scan = 0 ; ++i < argc && (!EQ(")", argv[i]) || scan != 0) ; j++) {
					if (EQ("(", argv[i])) scan++;
					if (EQ(")", argv[i])) scan--;
				}

				if (i >= argc) {
					fprintf(stderr, "unmatched bracket\n");
					exit(5);
				}

				if (j == 0) {
					fprintf(stderr, "empty brackets ... ignored\n");
					free(tmp_node);
					continue;
				}

				/* compile what is in the brackets */

				if ((tmp_node->first = compile(j, argv + i - j)) == NULL)
					continue;
			}
			else {
				tmp_node->first = (struct node *) prim;
				i += interpret(prim, argc - i, argv + i);
			}
			prim = (struct primary *) tmp_node;
		}

		else
			i += interpret(prim, argc - i, argv + i);

		/* attach interpreted primary to expression tree */

		if (node_head == NULL)
			node_head = (struct node *) prim;
		else {
			tmp_node = (struct node *) calloc(1, sizeof(struct node));
			if (tmp_node == NULL) {
				fprintf(stderr, "out of memory in expression compilation\n");
				exit(5);
			}
			tmp_node->type   = AND;
			tmp_node->first  = node_head;
			tmp_node->second = (struct node *) prim;
			node_head        = tmp_node;
		}
	}

	return(node_head);
}

/* interpret a primary */

interpret(prim, argc, argv)
struct primary *prim;
char *argv[];
{
	register i, j;
	register struct FileLock *lock;
	register struct FileInfoBlock *fib;
	register struct DateStamp *ds;
	char *numstr;
	extern unsigned long atol();

	for (i = 0 ; i < argc ; i++) {

		if (EQ("-print", argv[i]))
			prim->type = PRINT;

		else if (EQ("-name", argv[i])) {
			prim->type = NAME;
			prim->data[0] = argv[++i];
		}

		else if (EQ("-size", argv[i])) {
			prim->type = SIZE;

			/* get required size */

			numstr = argv[++i];

			if (*numstr == '+') {
				prim->type |= GT;
				numstr++;
			}

			else if (*numstr == '-') {
				prim->type |= LT;
				numstr++;
			}

			if (numstr[strlen(numstr) - 1] == 'c') {
				prim->type |= CHAR;
				numstr[strlen(numstr) - 1] == '\0';
			}

			prim->size = atol(numstr);
		}

		else if (EQ("-type", argv[i])) {
			prim->type = TYPE;
			if (EQ(argv[++i], "d"))
				prim->type |= DIRECT;
			else if (EQ(argv[i], "f"))
				prim->type |= PLAIN;
			else {
				fprintf(stderr, "illegal file type specified\n");
				exit(5);
			}
		}

		else if (EQ("-exec", argv[i])) {
			prim->type = EXEC;

			/* scan to ending ';', saving pointers to arguments */

			for (j=0 ; (j<MAXARGS) && (++i < argc) && !EQ(";",argv[i]) ; j++)
				prim->data[j] = argv[i];

			if (i >= argc) {
				fprintf(stderr, "no ending ';' on command\n");
				exit(5);
			}

			else if (j >= MAXARGS) {
				fprintf(stderr, "command too long\n");
				exit(5);
			}

			else
				argv[j] = NULL;
		}

		else if (EQ("-ok", argv[i])) {
			prim->type = EXEC | PROMPT;

			/* scan to ending ';', saving pointers to arguments */

			for (j=0 ; (j<MAXARGS) && (++i < argc) && !EQ(";",argv[i]) ; j++)
				prim->data[j] = argv[i];

			if (i >= argc) {
				fprintf(stderr, "no ending ';' on command\n");
				exit(5);
			}

			else if (j >= MAXARGS) {
				fprintf(stderr, "command too long\n");
				exit(5);
			}

			else
				argv[j] = NULL;
		}

		else if (EQ("-newer", argv[i])) {
			prim->type = NEWER;

			if (lock = Lock(argv[++i])) {
				fib = (struct FileInfoBlock *) AllocMem((long) sizeof(struct FileInfoBlock), MEMF_CLEAR);
				if (fib == NULL) {
					fprintf(stderr, "no mem for -newer test\n");
					UnLock(lock);
					exit(5);
				}

				if (Examine(lock, fib) == 0) {
					fprintf(stderr, "could not examine %s\n", argv[i]);
					FreeMem(fib, (long) sizeof(struct FileInfoBlock));
					UnLock(lock);
					exit(5);
				}

				/* save date stamp of given file */

				ds = (struct DateStamp *) calloc(1, sizeof(struct DateStamp));
				if (ds == NULL) {
					fprintf(stderr, "no mem for DateStamp on %s\n", argv[i]);
					FreeMem(fib, (long) sizeof(struct FileInfoBlock));
					UnLock(lock);
					exit(5);
				}

				prim->data[0] = (char *) ds;
				*ds = fib->fib_Date;

				FreeMem(fib, (long) sizeof(struct FileInfoBlock));
				UnLock(lock);
			}

			else {
				fprintf(stderr, "unable to access %s\n", argv[i]);
				exit(5);
			}
		}

		else if (EQ("-mtime", argv[i])) {
			prim->type = MTIME;

			/* get required number of days */

			numstr = argv[++i];

			if (*numstr == '+') {
				prim->type |= GT;
				numstr++;
			}
			else if (*numstr == '-') {
				prim->type |= LT;
				numstr++;
			}

			prim->size = atol(numstr);
		}

		else if (EQ("-perm", argv[i])) {
			prim->type = PERM;
			prim->size = PROTECTION;

			/* assemble desired protection bits */

			for(i++, j = 0 ; argv[i][j] ; j++) {
				switch(argv[i][j]) {

				case 'n':
					prim->size = PROTECTION;
					return(i);

				case 'r':
					prim->size &= ~FIBF_READ;
					break;

				case 'w':
					prim->size &= ~FIBF_WRITE;
					break;

				case 'e':
					prim->size &= ~FIBF_EXECUTE;
					break;

				case 'd':
					prim->size &= ~FIBF_DELETE;
					break;

				default:
					fprintf(stderr, "unknown code '%c' ... ignored\n", argv[i][j]);
					break;
				}
			}
		}

		else {
			fprintf(stderr, "unknown primary: %s\n", argv[i]);
			exit(5);
		}

		return(i);
	}
}

/* find the full path name of the given lock */

pwd(dir)
register struct FileLock *dir;
{
	register struct FileLock *par;
	register struct FileInfoBlock *fib;

	if (dir == NULL) {
		*path = '\0';
		return(1);
	}

	fib = (struct FileInfoBlock *) AllocMem((long) sizeof(struct FileInfoBlock), MEMF_CLEAR);
	if (fib == NULL) {
		fprintf(stderr, "pwd: can't allocate a FileInfoBlock\n");
		return(0);
	}

	if (!Examine(dir, fib)) {
		fprintf(stderr, "pwd: examine failed\n");
		FreeMem(fib, (long) sizeof(struct FileInfoBlock));
		return(0);
	}

	if (par = ParentDir(dir)) {

		/* find full path name of parent */

		if (pwd(par) == 0) {
			FreeMem(fib, (long) sizeof(struct FileInfoBlock));
			return(0);
		}

		/* add current name */

		strcat(path, fib->fib_FileName);
		strcat(path, "/");
	}
	else {

		/* found the root name */

		strcpy(path, fib->fib_FileName);
		strcat(path, ":");
	}

	FreeMem(fib, (long) sizeof(struct FileInfoBlock));
	return(1);
}

/*
 * Compare a wild card name with a normal name.
 * Taken from Matt Dillon's csh program.
 */

#define MAXB   8

compare_ok(wild, name)
char *wild, *name;
{
   register char *w = wild;
   register char *n = name;
   char *back[MAXB][2];
   register char s1, s2;
   int	bi = 0;

   while (*n || *w) {
      switch (*w) {
      case '*':
	 if (bi == MAXB) {
	    fprintf(stderr,"Too many levels of '*'\n");
	    return (0);
	 }
	 back[bi][0] = w;
	 back[bi][1] = n;
	 ++bi;
	 ++w;
	 continue;
goback:
	 --bi;
	 while (bi >= 0 && *back[bi][1] == '\0')
	    --bi;
	 if (bi < 0)
	    return (0);
	 w = back[bi][0] + 1;
	 n = ++back[bi][1];
	 ++bi;
	 continue;
      case '?':
	 if (!*n) {
	    if (bi)
	       goto goback;
	    return (0);
	 }
	 break;
      default:
	 s1 = (*n >= 'A' && *n <= 'Z') ? *n - 'A' + 'a' : *n;
	 s2 = (*w >= 'A' && *w <= 'Z') ? *w - 'A' + 'a' : *w;
	 if (s1 != s2) {
	    if (bi)
	       goto goback;
	    return (0);
	 }
	 break;
      }
      if (*n)  ++n;
      if (*w)  ++w;
   }
   return (1);
}