/*	$OpenBSD: fts.c,v 1.58 2017/03/17 15:14:40 deraadt Exp $	*/

/*-

 * Copyright (c) 1990, 1993, 1994

 *	The Regents of the University of California.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. Neither the name of the University nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 */

#include <sys/param.h>	/* ALIGN */

#include <sys/stat.h>

#include <dirent.h>

#include <errno.h>

#include <fcntl.h>

#include <fts.h>

#include <limits.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))

static FTSENT	*fts_alloc(FTS *, char *, size_t);

static FTSENT	*fts_build(FTS *, int);

static void	 fts_lfree(FTSENT *);

static void	 fts_load(FTS *, FTSENT *);

static size_t	 fts_maxarglen(char * const *);

static void	 fts_padjust(FTS *, FTSENT *);

static int	 fts_palloc(FTS *, size_t);

static FTSENT	*fts_sort(FTS *, FTSENT *, int);

static u_short	 fts_stat(FTS *, FTSENT *, int, int);

static int	 fts_safe_changedir(FTS *, FTSENT *, int, char *);

#define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))

#define	CLR(opt)	(sp->fts_options &= ~(opt))

#define	ISSET(opt)	(sp->fts_options & (opt))

#define	SET(opt)	(sp->fts_options |= (opt))

#define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))

/* fts_build flags */

#define	BCHILD		1		/* fts_children */

#define	BNAMES		2		/* fts_children, names only */

#define	BREAD		3		/* fts_read */

FTS *

fts_open(char * const *argv, int options,

    int (*compar)(const FTSENT **, const FTSENT **))

{

	FTS *sp;

	FTSENT *p, *root;

	int nitems;

	FTSENT *parent, *prev;

	/* Options check. */

	}

	/* At least one path must be specified. */

	}

	/* Allocate/initialize the stream */

	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */

	/*

	 * Start out with 1K of path space, and enough, in any case,

	 * to hold the user's paths.

	 */

		goto mem1;

	/* Allocate/initialize root's parent. */

		goto mem2;

	/* Allocate/initialize root(s). */

			goto mem3;

		/* Command-line "." and ".." are real directories. */

		/*

		 * If comparison routine supplied, traverse in sorted

		 * order; otherwise traverse in the order specified.

		 */

			root = p;

			else

			prev = p;

		}

	}

	/*

	 * Allocate a dummy pointer and make fts_read think that we've just

	 * finished the node before the root(s); set p->fts_info to FTS_INIT

	 * so that everything about the "current" node is ignored.

	 */

		goto mem3;

	/*

	 * If using chdir(2), grab a file descriptor pointing to dot to ensure

	 * that we can get back here; this could be avoided for some paths,

	 * but almost certainly not worth the effort.  Slashes, symbolic links,

	 * and ".." are all fairly nasty problems.  Note, if we can't get the

	 * descriptor we run anyway, just more slowly.

	 */

DEF_WEAK(fts_open);

static void

fts_load(FTS *sp, FTSENT *p)

{

	size_t len;

	char *cp;

	/*

	 * Load the stream structure for the next traversal.  Since we don't

	 * actually enter the directory until after the preorder visit, set

	 * the fts_accpath field specially so the chdir gets done to the right

	 * place and the user can access the first node.  From fts_open it's

	 * known that the path will fit.

	 */

int

fts_close(FTS *sp)

{

	FTSENT *freep, *p;

	int rfd, error = 0;

	/*

	 * This still works if we haven't read anything -- the dummy structure

	 * points to the root list, so we step through to the end of the root

	 * list which has a valid parent pointer.

	 */

			freep = p;

		}

	}

	/* Stash the original directory fd if needed. */

	/* Free up child linked list, sort array, path buffer, stream ptr.*/

	/* Return to original directory, checking for error. */

		int saved_errno;

}

DEF_WEAK(fts_close);

/*

 * Special case of "/" at the end of the path so that slashes aren't

 * appended which would cause paths to be written as "....//foo".

 */

#define	NAPPEND(p)							\

	(p->fts_path[p->fts_pathlen - 1] == '/'				\

	    ? p->fts_pathlen - 1 : p->fts_pathlen)

FTSENT *

fts_read(FTS *sp)

{

	FTSENT *p, *tmp;

	int instr;

	char *t;

	int saved_errno;

	/* If finished or unrecoverable error, return NULL. */

	/* Set current node pointer. */

	p = sp->fts_cur;

	/* Save and zero out user instructions. */

	/* Any type of file may be re-visited; re-stat and re-turn. */

	}

	/*

	 * Following a symlink -- SLNONE test allows application to see

	 * SLNONE and recover.  If indirecting through a symlink, have

	 * keep a pointer to current location.  If unable to get that

	 * pointer, follow fails.

	 */

		}

	}

	/* Directory in pre-order. */

		/* If skipped or crossed mount point, do post-order visit. */

		}

		/* Rebuild if only read the names and now traversing. */

		}

		/*

		 * Cd to the subdirectory.

		 *

		 * If have already read and now fail to chdir, whack the list

		 * to make the names come out right, and set the parent errno

		 * so the application will eventually get an error condition.

		 * Set the FTS_DONTCHDIR flag so that when we logically change

		 * directories back to the parent we don't do a chdir.

		 *

		 * If haven't read do so.  If the read fails, fts_build sets

		 * FTS_STOP or the fts_info field of the node.

		 */

			}

		}

	}

	/* Move to the next node on this level. */

next:	tmp = p;

		/*

		 * If reached the top, return to the original directory (or

		 * the root of the tree), and load the paths for the next root.

		 */

			}

		}

		/*

		 * User may have called fts_set on the node.  If skipped,

		 * ignore.  If followed, get a file descriptor so we can

		 * get back if necessary.

		 */

			goto next;

			}

		}

	}

	/* Move up to the parent node. */

		/*

		 * Done; free everything up and set errno to 0 so the user

		 * can distinguish between error and EOF.

		 */

	}

	/* NUL terminate the pathname. */

	/*

	 * Return to the parent directory.  If at a root node or came through

	 * a symlink, go back through the file descriptor.  Otherwise, cd up

	 * one directory.

	 */

		}

		}

	}

DEF_WEAK(fts_read);

/*

 * Fts_set takes the stream as an argument although it's not used in this

 * implementation; it would be necessary if anyone wanted to add global

 * semantics to fts using fts_set.  An error return is allowed for similar

 * reasons.

 */

int

fts_set(FTS *sp, FTSENT *p, int instr)

{

	}

DEF_WEAK(fts_set);

FTSENT *

fts_children(FTS *sp, int instr)

{

	FTSENT *p;

	int fd;

	}

	/* Set current node pointer. */

	/*

	 * Errno set to 0 so user can distinguish empty directory from

	 * an error.

	 */

	/* Fatal errors stop here. */

	/* Return logical hierarchy of user's arguments. */

	/*

	 * If not a directory being visited in pre-order, stop here.  Could

	 * allow FTS_DNR, assuming the user has fixed the problem, but the

	 * same effect is available with FTS_AGAIN.

	 */

	/* Free up any previous child list. */

		instr = BNAMES;

		instr = BCHILD;

	/*

	 * If using chdir on a relative path and called BEFORE fts_read does

	 * its chdir to the root of a traversal, we can lose -- we need to

	 * chdir into the subdirectory, and we don't know where the current

	 * directory is, so we can't get back so that the upcoming chdir by

	 * fts_read will work.

	 */

	}

	(void)close(fd);

DEF_WEAK(fts_children);

/*

 * This is the tricky part -- do not casually change *anything* in here.  The

 * idea is to build the linked list of entries that are used by fts_children

 * and fts_read.  There are lots of special cases.

 *

 * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is

 * set and it's a physical walk (so that symbolic links can't be directories),

 * we can do things quickly.  First, if it's a 4.4BSD file system, the type

 * of the file is in the directory entry.  Otherwise, we assume that the number

 * of subdirectories in a node is equal to the number of links to the parent.

 * The former skips all stat calls.  The latter skips stat calls in any leaf

 * directories and for any files after the subdirectories in the directory have

 * been found, cutting the stat calls by about 2/3.

 */

static FTSENT *

fts_build(FTS *sp, int type)

{

	struct dirent *dp;

	FTSENT *p, *head;

	FTSENT *cur, *tail;

	DIR *dirp;

	void *oldaddr;

	size_t len, maxlen;

	int nitems, cderrno, descend, level, nlinks, nostat, doadjust;

	int saved_errno;

	char *cp;

	/* Set current node pointer. */

	/*

	 * Open the directory for reading.  If this fails, we're done.

	 * If being called from fts_read, set the fts_info field.

	 */

		}

	}

	/*

	 * Nlinks is the number of possible entries of type directory in the

	 * directory if we're cheating on stat calls, 0 if we're not doing

	 * any stat calls at all, -1 if we're doing stats on everything.

	 */

		nostat = 1;

		nlinks = -1;

		nostat = 0;

	}

#ifdef notdef

	(void)printf("nlinks == %d (cur: %u)\n", nlinks, cur->fts_nlink);

	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",

	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));

#endif

	/*

	 * If we're going to need to stat anything or we want to descend

	 * and stay in the directory, chdir.  If this fails we keep going,

	 * but set a flag so we don't chdir after the post-order visit.

	 * We won't be able to stat anything, but we can still return the

	 * names themselves.  Note, that since fts_read won't be able to

	 * chdir into the directory, it will have to return different path

	 * names than before, i.e. "a/b" instead of "b".  Since the node

	 * has already been visited in pre-order, have to wait until the

	 * post-order visit to return the error.  There is a special case

	 * here, if there was nothing to stat then it's not an error to

	 * not be able to stat.  This is all fairly nasty.  If a program

	 * needed sorted entries or stat information, they had better be

	 * checking FTS_NS on the returned nodes.

	 */

	cderrno = 0;

			descend = 0;

			dirp = NULL;

			descend = 1;

	} else

		descend = 0;

	/*

	 * Figure out the max file name length that can be stored in the

	 * current path -- the inner loop allocates more path as necessary.

	 * We really wouldn't have to do the maxlen calculations here, we

	 * could do them in fts_read before returning the path, but it's a

	 * lot easier here since the length is part of the dirent structure.

	 *

	 * If not changing directories set a pointer so that can just append

	 * each new name into the path.

	 */

	/*

	 * fts_level is signed so we must prevent it from wrapping

	 * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.

	 */

	/* Read the directory, attaching each entry to the `link' pointer. */

	doadjust = 0;

			continue;

			goto mem1;

				/*

				 * No more memory for path or structures.  Save

				 * errno, free up the current structure and the

				 * structures already allocated.

				 */

			}

			/* Did realloc() change the pointer? */

				doadjust = 1;

			}

		}

			/*

			 * If we wrap, free up the current structure and

			 * the structures already allocated, then error

			 * out with ENAMETOOLONG.

			 */

		}

#ifdef DT_DIR

#endif

		    ) {

			/* Build a file name for fts_stat to stat. */

			}

			/* Decrement link count if applicable. */

		}

		/* We walk in directory order so "ls -f" doesn't get upset. */

		else {

			tail = p;

		}

	}

	/*

	 * If realloc() changed the address of the path, adjust the

	 * addresses for the rest of the tree and the dir list.

	 */

	/*

	 * If not changing directories, reset the path back to original

	 * state.

	 */

	/*

	 * If descended after called from fts_children or after called from

	 * fts_read and nothing found, get back.  At the root level we use

	 * the saved fd; if one of fts_open()'s arguments is a relative path

	 * to an empty directory, we wind up here with no other way back.  If

	 * can't get back, we're done.

	 */

	}

	/* If didn't find anything, return NULL. */

	}

	/* Sort the entries. */

static u_short

fts_stat(FTS *sp, FTSENT *p, int follow, int dfd)

{

	FTSENT *t;

	dev_t dev;

	ino_t ino;

	int saved_errno;

	const char *path;

		dfd = AT_FDCWD;

	/* If user needs stat info, stat buffer already allocated. */

	/*

	 * If doing a logical walk, or application requested FTS_FOLLOW, do

	 * a stat(2).  If that fails, check for a non-existent symlink.  If

	 * fail, set the errno from the stat call.

	 */

			}

			p->fts_errno = saved_errno;

		}

	}

		/*

		 * Set the device/inode.  Used to find cycles and check for

		 * crossing mount points.  Also remember the link count, used

		 * in fts_build to limit the number of stat calls.  It is

		 * understood that these fields are only referenced if fts_info

		 * is set to FTS_D.

		 */

		/*

		 * Cycle detection is done by brute force when the directory

		 * is first encountered.  If the tree gets deep enough or the

		 * number of symbolic links to directories is high enough,

		 * something faster might be worthwhile.

		 */

			}

	}

static FTSENT *

fts_sort(FTS *sp, FTSENT *head, int nitems)

{

	FTSENT **ap, *p;

	/*

	 * Construct an array of pointers to the structures and call qsort(3).

	 * Reassemble the array in the order returned by qsort.  If unable to

	 * sort for memory reasons, return the directory entries in their

	 * current order.  Allocate enough space for the current needs plus

	 * 40 so don't realloc one entry at a time.

	 */

		struct _ftsent **a;

		}

static FTSENT *

fts_alloc(FTS *sp, char *name, size_t namelen)

{

	FTSENT *p;

	size_t len;

	/*

	 * The file name is a variable length array and no stat structure is

	 * necessary if the user has set the nostat bit.  Allocate the FTSENT

	 * structure, the file name and the stat structure in one chunk, but

	 * be careful that the stat structure is reasonably aligned.  Since the

	 * fts_name field is declared to be of size 1, the fts_name pointer is

	 * namelen + 2 before the first possible address of the stat structure.

	 */

static void

fts_lfree(FTSENT *head)

{

	FTSENT *p;

	/* Free a linked list of structures. */

	}

/*

 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.

 * Most systems will allow creation of paths much longer than PATH_MAX, even

 * though the kernel won't resolve them.  Add the size (not just what's needed)

 * plus 256 bytes so don't realloc the path 2 bytes at a time.

 */

static int

fts_palloc(FTS *sp, size_t more)

{

	char *p;

	/*

	 * Check for possible wraparound.

	 */