1/***********************************************************************
2*                                                                      *
3*               This software is part of the ast package               *
4*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5*                      and is licensed under the                       *
6*                 Eclipse Public License, Version 1.0                  *
7*                    by AT&T Intellectual Property                     *
8*                                                                      *
9*                A copy of the License is available at                 *
10*          http://www.eclipse.org/org/documents/epl-v10.html           *
11*         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
12*                                                                      *
13*              Information and Software Systems Research               *
14*                            AT&T Research                             *
15*                           Florham Park NJ                            *
16*                                                                      *
17*                 Glenn Fowler <gsf@research.att.com>                  *
18*                  David Korn <dgk@research.att.com>                   *
19*                   Phong Vo <kpv@research.att.com>                    *
20*                                                                      *
21***********************************************************************/
22#pragma prototyped
23/*
24 * Phong Vo
25 * Glenn Fowler
26 * AT&T Research
27 *
28 * fts implementation unwound from the kpv ftwalk() of 1988-10-30
29 */
30
31#include <ast.h>
32#include <ast_dir.h>
33#include <error.h>
34#include <fs3d.h>
35#include <ls.h>
36
37struct Ftsent;
38
39typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*);
40typedef int (*Stat_f)(const char*, struct stat*);
41
42#define _fts_status	status
43#define _fts_statb	statb
44
45#define _FTS_PRIVATE_ \
46	FTSENT*		parent;			/* top parent		*/ \
47	FTSENT*		todo;			/* todo list		*/ \
48	FTSENT*		top;			/* top element		*/ \
49	FTSENT*		root;						   \
50	FTSENT*		bot;			/* bottom element	*/ \
51	FTSENT*		free;			/* free element		*/ \
52	FTSENT*		diroot;						   \
53	FTSENT*		curdir;						   \
54	FTSENT*		current;		/* current element	*/ \
55	FTSENT*		previous;		/* previous current	*/ \
56	FTSENT*		dotdot;						   \
57	FTSENT*		link;			/* real current fts_link*/ \
58	FTSENT*		pwd;			/* pwd parent		*/ \
59	DIR*		dir;			/* current dir stream	*/ \
60	Compar_f	comparf;		/* node comparison func	*/ \
61	size_t		baselen;		/* current strlen(base)	*/ \
62	size_t		homesize;		/* sizeof(home)		*/ \
63	int		cd;			/* chdir status		*/ \
64	int		cpname;						   \
65	int		flags;			/* fts_open() flags	*/ \
66	int		nd;						   \
67	unsigned char	children;					   \
68	unsigned char	fs3d;						   \
69	unsigned char	nostat;					   	   \
70	unsigned char	state;			/* fts_read() state	*/ \
71	char*		base;			/* basename in path	*/ \
72	char*		name;						   \
73	char*		path;			/* path workspace	*/ \
74	char*		home;			/* home/path buffer	*/ \
75	char*		endbase;		/* space to build paths */ \
76	char*		endbuf;			/* space to build paths */ \
77	char*		pad[2];			/* $0.02 to splain this	*/
78
79/*
80 * NOTE: <ftwalk.h> relies on status and statb being the first two elements
81 */
82
83#define _FTSENT_PRIVATE_ \
84	int		nd;			/* popdir() count	*/ \
85	FTSENT*		left;			/* left child		*/ \
86	FTSENT*		right;			/* right child		*/ \
87	FTSENT*		pwd;			/* pwd parent		*/ \
88	FTSENT*		stack;			/* getlist() stack	*/ \
89	long		nlink;			/* FTS_D link count	*/ \
90	unsigned char	must;			/* must stat		*/ \
91	unsigned char	type;			/* DT_* type		*/ \
92	unsigned char	symlink;		/* originally a symlink	*/ \
93	char		name[sizeof(int)];	/* fts_name data	*/
94
95#include <fts.h>
96
97#ifndef ENOSYS
98#define ENOSYS		EINVAL
99#endif
100
101
102#if MAXNAMLEN > 16
103#define MINNAME		32
104#else
105#define MINNAME		16
106#endif
107
108#define drop(p,f)	(((f)->fts_namelen < MINNAME) ? ((f)->fts_link = (p)->free, (p)->free = (f)) : (free(f), (p)->free))
109
110#define ACCESS(p,f)	((p)->cd==0?(f)->fts_name:(f)->fts_path)
111#define PATH(f,p,l)	((!((f)->flags&FTS_SEEDOTDIR)&&(l)>0&&(p)[0]=='.'&&(p)[1]=='/')?((p)+2):(p))
112#define SAME(one,two)	((one)->st_ino==(two)->st_ino&&(one)->st_dev==(two)->st_dev)
113#define SKIPLINK(p,f)	((f)->fts_parent->nlink == 0)
114
115#ifdef D_TYPE
116#define ISTYPE(f,t)	((f)->type == (t))
117#define TYPE(f,t)	((f)->type = (t))
118#define SKIP(p,f)	((f)->fts_parent->must == 0 && (((f)->type == DT_UNKNOWN) ? SKIPLINK(p,f) : ((f)->type != DT_DIR && ((f)->type != DT_LNK || ((p)->flags & FTS_PHYSICAL)))))
119#else
120#undef	DT_UNKNOWN
121#define DT_UNKNOWN	0
122#undef	DT_LNK
123#define DT_LNK		1
124#define ISTYPE(f,t)	((t)==DT_UNKNOWN)
125#define TYPE(f,d)
126#define SKIP(p,f)	((f)->fts_parent->must == 0 && SKIPLINK(p,f))
127#endif
128
129#ifndef D_FILENO
130#define D_FILENO(d)	(1)
131#endif
132
133/*
134 * NOTE: a malicious dir rename() could change .. underfoot so we
135 *	 must always verify; undef verify to enable the unsafe code
136 */
137
138#define verify		1
139
140/*
141 * FTS_NOSTAT requires a dir with
142 *	D_TYPE(&dirent_t)!=DT_UNKNOWN
143 *	    OR
144 *	st_nlink>=2
145 */
146
147#define FTS_children_resume	1
148#define FTS_children_return	2
149#define FTS_error		3
150#define FTS_popstack		4
151#define FTS_popstack_resume	5
152#define FTS_popstack_return	6
153#define FTS_preorder		7
154#define FTS_preorder_resume	8
155#define FTS_preorder_return	9
156#define FTS_readdir		10
157#define FTS_terminal		11
158#define FTS_todo		12
159#define FTS_top_return		13
160
161typedef int (*Notify_f)(FTS*, FTSENT*, void*);
162
163typedef struct Notify_s
164{
165	struct Notify_s*	next;
166	Notify_f		notifyf;
167	void*			context;
168} Notify_t;
169
170static Notify_t*		notify;
171
172/*
173 * allocate an FTSENT node
174 */
175
176static FTSENT*
177node(FTS* fts, FTSENT* parent, register char* name, register size_t namelen)
178{
179	register FTSENT*	f;
180	register size_t		n;
181
182	if (fts->free && namelen < MINNAME)
183	{
184		f = fts->free;
185		fts->free = f->fts_link;
186	}
187	else
188	{
189		n = (namelen < MINNAME ? MINNAME : namelen + 1) - sizeof(int);
190		if (!(f = newof(0, FTSENT, 1, n)))
191		{
192			fts->fts_errno = errno;
193			fts->state = FTS_error;
194			return 0;
195		}
196		f->fts = fts;
197	}
198	TYPE(f, DT_UNKNOWN);
199	f->status = 0;
200	f->symlink = 0;
201	f->fts_level = (f->fts_parent = parent)->fts_level + 1;
202#if __OBSOLETE__ < 20140101
203	f->_fts_level = (short)f->fts_level;
204#endif
205	f->fts_link = 0;
206	f->fts_pointer = 0;
207	f->fts_number = 0;
208	f->fts_errno = 0;
209	f->fts_namelen = namelen;
210#if __OBSOLETE__ < 20140101
211	f->_fts_namelen = (unsigned short)f->fts_namelen;
212#endif
213	f->fts_name = f->name;
214	f->fts_statp = &f->statb;
215	memcpy(f->fts_name, name, namelen + 1);
216	return f;
217}
218
219/*
220 * compare directories by device/inode
221 */
222
223static int
224statcmp(FTSENT* const* pf1, FTSENT* const* pf2)
225{
226	register const FTSENT*	f1 = *pf1;
227	register const FTSENT*	f2 = *pf2;
228
229	if (f1->statb.st_ino < f2->statb.st_ino)
230		return -1;
231	if (f1->statb.st_ino > f2->statb.st_ino)
232		return 1;
233	if (f1->statb.st_dev < f2->statb.st_dev)
234		return -1;
235	if (f1->statb.st_dev > f2->statb.st_dev)
236		return 1;
237
238	/*
239	 * hack for NFS where <dev,ino> may not uniquely identify objects
240	 */
241
242	if (f1->statb.st_mtime < f2->statb.st_mtime)
243		return -1;
244	if (f1->statb.st_mtime > f2->statb.st_mtime)
245		return 1;
246	return 0;
247}
248
249/*
250 * search trees with top-down splaying (a la Tarjan and Sleator)
251 * when used for insertion sort, this implements a stable sort
252 */
253
254#define RROTATE(r)	(t = r->left, r->left = t->right, t->right = r, r = t)
255#define LROTATE(r)	(t = r->right, r->right = t->left, t->left = r, r = t)
256
257static FTSENT*
258search(FTSENT* e, FTSENT* root, int(*comparf)(FTSENT* const*, FTSENT* const*), int insert)
259{
260	register int		cmp;
261	register FTSENT*	t;
262	register FTSENT*	left;
263	register FTSENT*	right;
264	register FTSENT*	lroot;
265	register FTSENT*	rroot;
266
267	left = right = lroot = rroot = 0;
268	while (root)
269	{
270		if (!(cmp = (*comparf)(&e, &root)) && !insert)
271			break;
272		if (cmp < 0)
273		{
274			/*
275			 * this is the left zig-zig case
276			 */
277
278			if (root->left && (cmp = (*comparf)(&e, &root->left)) <= 0)
279			{
280				RROTATE(root);
281				if (!cmp && !insert)
282					break;
283			}
284
285			/*
286			 * stick all things > e to the right tree
287			 */
288
289			if (right)
290				right->left = root;
291			else
292				rroot = root;
293			right = root;
294			root = root->left;
295			right->left = 0;
296		}
297		else
298		{
299			/*
300			 * this is the right zig-zig case
301			 */
302
303			if (root->right && (cmp = (*comparf)(&e, &root->right)) >= 0)
304			{
305				LROTATE(root);
306				if (!cmp && !insert)
307					break;
308			}
309
310			/*
311			 * stick all things <= e to the left tree
312			 */
313
314			if (left)
315				left->right = root;
316			else
317				lroot = root;
318			left = root;
319			root = root->right;
320			left->right = 0;
321		}
322	}
323	if (!root)
324		root = e;
325	else
326	{
327		if (right)
328			right->left = root->right;
329		else
330			rroot = root->right;
331		if (left)
332			left->right = root->left;
333		else
334			lroot = root->left;
335	}
336	root->left = lroot;
337	root->right = rroot;
338	return root;
339}
340
341/*
342 * delete the root element from the tree
343 */
344
345static FTSENT*
346deleteroot(register FTSENT* root)
347{
348	register FTSENT*	t;
349	register FTSENT*	left;
350	register FTSENT*	right;
351
352	right = root->right;
353	if (!(left = root->left))
354		root = right;
355	else
356	{
357		while (left->right)
358			LROTATE(left);
359		left->right = right;
360		root = left;
361	}
362	return root;
363}
364
365/*
366 * generate ordered fts_link list from binary tree at root
367 * FTSENT.stack instead of recursion to avoid blowing the real
368 * stack on big directories
369 */
370
371static void
372getlist(register FTSENT** top, register FTSENT** bot, register FTSENT* root)
373{
374	register FTSENT*	stack = 0;
375
376	for (;;)
377	{
378		if (root->left)
379		{
380			root->stack = stack;
381			stack = root;
382			root = root->left;
383		}
384		else
385		{
386			for (;;)
387			{
388				if (*top)
389					*bot = (*bot)->fts_link = root;
390				else
391					*bot = *top = root;
392				if (root->right)
393				{
394					root = root->right;
395					break;
396				}
397				if (!(root = stack))
398				{
399					(*bot)->fts_link = 0;
400					return;
401				}
402				stack = stack->stack;
403			}
404		}
405	}
406}
407
408/*
409 * set directory when curdir is lost in space
410 */
411
412static int
413setdir(register char* home, register char* path)
414{
415	register int	cdrv;
416
417	if (path[0] == '/')
418		cdrv = pathcd(path, NiL);
419	else
420	{
421		/*
422		 * note that path and home are in the same buffer
423		 */
424
425		path[-1] = '/';
426		cdrv = pathcd(home, NiL);
427		path[-1] = 0;
428	}
429	if (cdrv < 0)
430		pathcd(home, NiL);
431	return cdrv;
432}
433
434/*
435 * set to parent dir
436 */
437
438static int
439setpdir(register char* home, register char* path, register char* base)
440{
441	register int	c;
442	register int	cdrv;
443
444	if (base > path)
445	{
446		c = base[0];
447		base[0] = 0;
448		cdrv = setdir(home, path);
449		base[0] = c;
450	}
451	else
452		cdrv = pathcd(home, NiL);
453	return cdrv;
454}
455
456/*
457 * pop a set of directories
458 */
459static int
460popdirs(FTS* fts)
461{
462	register FTSENT*f;
463	register char*	s;
464	register char*	e;
465#ifndef verify
466	register int	verify;
467#endif
468	struct stat	sb;
469	char		buf[PATH_MAX];
470
471	if (!(f = fts->curdir) || f->fts_level < 0)
472		return -1;
473	e = buf + sizeof(buf) - 4;
474#ifndef verify
475	verify = 0;
476#endif
477	while (fts->nd > 0)
478	{
479		for (s = buf; s < e && fts->nd > 0; fts->nd--)
480		{
481			if (fts->pwd)
482			{
483#ifndef verify
484				verify |= fts->pwd->symlink;
485#endif
486				fts->pwd = fts->pwd->pwd;
487			}
488			*s++ = '.';
489			*s++ = '.';
490			*s++ = '/';
491		}
492		*s = 0;
493		if (chdir(buf))
494			return -1;
495	}
496	return (verify && (stat(".", &sb) < 0 || !SAME(&sb, f->fts_statp))) ? -1 : 0;
497}
498
499/*
500 * initialize st from path and fts_info from st
501 */
502
503static int
504info(FTS* fts, register FTSENT* f, const char* path, struct stat* sp, int flags)
505{
506	if (path)
507	{
508#ifdef S_ISLNK
509		if (!f->symlink && (ISTYPE(f, DT_UNKNOWN) || ISTYPE(f, DT_LNK)))
510		{
511			if (lstat(path, sp) < 0)
512				goto bad;
513		}
514		else
515#endif
516			if (stat(path, sp) < 0)
517				goto bad;
518	}
519#ifdef S_ISLNK
520 again:
521#endif
522	if (S_ISDIR(sp->st_mode))
523	{
524		if ((flags & FTS_NOSTAT) && !fts->fs3d)
525		{
526			f->fts_parent->nlink--;
527#ifdef D_TYPE
528			if ((f->nlink = sp->st_nlink) < 2)
529			{
530				f->must = 2;
531				f->nlink = 2;
532			}
533			else
534				f->must = 0;
535#else
536			if ((f->nlink = sp->st_nlink) >= 2)
537				f->must = 1;
538			else
539				f->must = 2;
540#endif
541		}
542		else
543			f->must = 2;
544		TYPE(f, DT_DIR);
545		f->fts_info = FTS_D;
546	}
547#ifdef S_ISLNK
548	else if (S_ISLNK((sp)->st_mode))
549	{
550		struct stat	sb;
551
552		f->symlink = 1;
553		if (flags & FTS_PHYSICAL)
554		{
555			TYPE(f, DT_LNK);
556			f->fts_info = FTS_SL;
557		}
558		else if (stat(path, &sb) >= 0)
559		{
560			*sp = sb;
561			flags = FTS_PHYSICAL;
562			goto again;
563		}
564		else
565		{
566			TYPE(f, DT_LNK);
567			f->fts_info = FTS_SLNONE;
568		}
569	}
570#endif
571	else
572	{
573		TYPE(f, DT_REG);
574		f->fts_info = FTS_F;
575	}
576	return 0;
577 bad:
578	TYPE(f, DT_UNKNOWN);
579	f->fts_info = FTS_NS;
580	return -1;
581}
582
583/*
584 * get top list of elements to process
585 * ordering delayed until first fts_read()
586 * to give caller a chance to set fts->handle
587 */
588
589static FTSENT*
590toplist(FTS* fts, register char* const* pathnames)
591{
592	register char*		path;
593	register FTSENT*	f;
594	register FTSENT*	top;
595	register FTSENT*	bot;
596	int			physical;
597	int			metaphysical;
598	char*			s;
599	struct stat		st;
600
601	if (fts->flags & FTS_NOSEEDOTDIR)
602		fts->flags &= ~FTS_SEEDOTDIR;
603	physical = (fts->flags & FTS_PHYSICAL);
604	metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
605	top = bot = 0;
606	while (path = *pathnames++)
607	{
608		/*
609		 * make elements
610		 */
611
612		if (!(f = node(fts, fts->parent, path, strlen(path))))
613			break;
614		path = f->fts_name;
615		if (!physical)
616			f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, strlen(path) + 1, 0) - path);
617		else if (*path != '.')
618		{
619			f->fts_namelen = strlen(path);
620			fts->flags |= FTS_SEEDOTDIR;
621		}
622		else
623		{
624			if (fts->flags & FTS_NOSEEDOTDIR)
625			{
626				fts->flags &= ~FTS_SEEDOTDIR;
627				s = path;
628				while (*s++ == '.' && *s++ == '/')
629				{
630					while (*s == '/')
631						s++;
632					if (!*s)
633						break;
634					path = f->fts_name;
635					while (*path++ = *s++);
636					path = f->fts_name;
637				}
638			}
639			else
640				fts->flags |= FTS_SEEDOTDIR;
641			for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
642			*s = 0;
643			f->fts_namelen = s - path;
644		}
645#if __OBSOLETE__ < 20140101
646		f->_fts_namelen = (unsigned short)f->fts_namelen;
647#endif
648		if (!*path)
649		{
650			errno = ENOENT;
651			f->fts_info = FTS_NS;
652		}
653		else
654			info(fts, f, path, f->fts_statp, fts->flags);
655#ifdef S_ISLNK
656
657		/*
658		 * don't let any standards committee get
659		 * away with calling your idea a hack
660		 */
661
662		if (metaphysical && f->fts_info == FTS_SL)
663		{
664			if (stat(path, &st) >= 0)
665			{
666				*f->fts_statp = st;
667				info(fts, f, NiL, f->fts_statp, 0);
668			}
669			else
670				f->fts_info = FTS_SLNONE;
671		}
672#endif
673		if (bot)
674		{
675			bot->fts_link = f;
676			bot = f;
677		}
678		else
679			top = bot = f;
680	}
681	return top;
682}
683
684/*
685 * order fts->todo if fts->comparf != 0
686 */
687
688static void
689order(FTS* fts)
690{
691	register FTSENT*	f;
692	register FTSENT*	root;
693	FTSENT*			top;
694	FTSENT*			bot;
695
696	top = bot = root = 0;
697	for (f = fts->todo; f; f = f->fts_link)
698		root = search(f, root, fts->comparf, 1);
699	getlist(&top, &bot, root);
700	fts->todo = top;
701}
702
703/*
704 * resize the path buffer
705 * note that free() is not used because we may need to chdir(fts->home)
706 * if there isn't enough space to continue
707 */
708
709static int
710resize(register FTS* fts, size_t inc)
711{
712	register char*	old;
713	register char*	newp;
714	register size_t	n_old;
715
716	/*
717	 * add space for "/." used in testing FTS_DNX
718	 */
719
720	n_old = fts->homesize;
721	fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
722	if (!(newp = newof(0, char, fts->homesize, 0)))
723	{
724		fts->fts_errno = errno;
725		fts->state = FTS_error;
726		return -1;
727	}
728	old = fts->home;
729	fts->home = newp;
730	memcpy(newp, old, n_old);
731	if (fts->endbuf)
732		fts->endbuf = newp + fts->homesize - 4;
733	if (fts->path)
734		fts->path = newp + (fts->path - old);
735	if (fts->base)
736		fts->base = newp + (fts->base - old);
737	free(old);
738	return 0;
739}
740
741/*
742 * open a new fts stream on pathnames
743 */
744
745FTS*
746fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
747{
748	register FTS*	fts;
749
750	if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
751		return 0;
752	fts->flags = flags;
753	fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
754	fts->comparf = comparf;
755	fts->fs3d = fs3d(FS3D_TEST);
756
757	/*
758	 * set up the path work buffer
759	 */
760
761	fts->homesize = 2 * PATH_MAX;
762	for (;;)
763	{
764		if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
765		{
766			free(fts);
767			return 0;
768		}
769		if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
770			break;
771		if (errno == ERANGE)
772			fts->homesize += PATH_MAX;
773		else
774			fts->cd = 1;
775	}
776	fts->endbuf = fts->home + fts->homesize - 4;
777
778	/*
779	 * initialize the tippity-top
780	 */
781
782	fts->parent = (FTSENT*)(fts + 1);
783	fts->parent->fts_info = FTS_D;
784	memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
785	fts->parent->fts_level = -1;
786#if __OBSOLETE__ < 20140101
787	fts->parent->_fts_level = (short)fts->parent->fts_level;
788#endif
789	fts->parent->fts_statp = &fts->parent->statb;
790	fts->parent->must = 2;
791	fts->parent->type = DT_UNKNOWN;
792	fts->path = fts->home + strlen(fts->home) + 1;
793
794	/*
795	 * make the list of top elements
796	 */
797
798	if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
799	{
800		char*	v[2];
801
802		v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
803		v[1] = 0;
804		fts->todo = toplist(fts, v);
805	}
806	else
807		fts->todo = toplist(fts, pathnames);
808#if _HUH_1997_01_07
809	if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
810#else
811	if (!fts->todo)
812#endif
813	{
814		fts_close(fts);
815		return 0;
816	}
817	return fts;
818}
819
820/*
821 * return the next FTS entry
822 */
823
824FTSENT*
825fts_read(register FTS* fts)
826{
827	register char*		s;
828	register int		n;
829	register FTSENT*	f;
830	struct dirent*		d;
831	size_t			i;
832	FTSENT*			t;
833	Notify_t*		p;
834#ifdef verify
835	struct stat		sb;
836#endif
837
838	for (;;)
839		switch (fts->state)
840		{
841
842		case FTS_top_return:
843
844			f = fts->todo;
845			t = 0;
846			while (f)
847				if (f->status == FTS_SKIP)
848				{
849					if (t)
850					{
851						t->fts_link = f->fts_link;
852						drop(fts, f);
853						f = t->fts_link;
854					}
855					else
856					{
857						fts->todo = f->fts_link;
858						drop(fts, f);
859						f = fts->todo;
860					}
861				}
862				else
863				{
864					t = f;
865					f = f->fts_link;
866				}
867			/*FALLTHROUGH*/
868
869		case 0:
870
871			if (!fts->state && fts->comparf)
872				order(fts);
873			if (!(f = fts->todo))
874				return 0;
875			/*FALLTHROUGH*/
876
877		case FTS_todo:
878
879			/*
880			 * process the top object on the stack
881			 */
882
883			fts->root = fts->top = fts->bot = 0;
884
885			/*
886			 * initialize the top level
887			 */
888
889			if (f->fts_level == 0)
890			{
891				fts->parent->fts_number = f->fts_number;
892				fts->parent->fts_pointer = f->fts_pointer;
893				fts->parent->fts_statp = f->fts_statp;
894				fts->parent->statb = *f->fts_statp;
895				f->fts_parent = fts->parent;
896				fts->diroot = 0;
897				if (fts->cd == 0)
898					pathcd(fts->home, NiL);
899				else if (fts->cd < 0)
900					fts->cd = 0;
901				fts->pwd = f->fts_parent;
902				fts->curdir = fts->cd ? 0 : f->fts_parent;
903				*(fts->base = fts->path) = 0;
904			}
905
906			/*
907			 * chdir to parent if asked for
908			 */
909
910			if (fts->cd < 0)
911			{
912				fts->cd = setdir(fts->home, fts->path);
913				fts->pwd = f->fts_parent;
914				fts->curdir = fts->cd ? 0 : f->fts_parent;
915			}
916
917			/*
918			 * add object's name to the path
919			 */
920
921			if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
922				return 0;
923			memcpy(fts->base, f->name, fts->baselen + 1);
924			fts->name = fts->cd ? fts->path : fts->base;
925			/*FALLTHROUGH*/
926
927		case FTS_preorder:
928
929			/*
930			 * check for cycle and open dir
931			 */
932
933			if (f->fts_info == FTS_D)
934			{
935				if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
936				{
937					f->fts_info = FTS_DC;
938					f->fts_cycle = fts->diroot;
939				}
940				else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
941				{
942					/*
943					 * buffer is known to be large enough here!
944					 */
945
946					if (fts->base[fts->baselen - 1] != '/')
947						memcpy(fts->base + fts->baselen, "/.", 3);
948					if (!(fts->dir = opendir(fts->name)))
949						f->fts_info = FTS_DNX;
950					fts->base[fts->baselen] = 0;
951					if (!fts->dir && !(fts->dir = opendir(fts->name)))
952						f->fts_info = FTS_DNR;
953				}
954			}
955			f->nd = f->fts_info & ~FTS_DNX;
956			if (f->nd || !(fts->flags & FTS_NOPREORDER))
957			{
958				fts->current = f;
959				fts->link = f->fts_link;
960				f->fts_link = 0;
961				f->fts_path = PATH(fts, fts->path, f->fts_level);
962				f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
963				f->fts_accpath = ACCESS(fts, f);
964				fts->state = FTS_preorder_return;
965				goto note;
966			}
967			/*FALLTHROUGH*/
968
969		case FTS_preorder_resume:
970
971			/*
972			 * prune
973			 */
974
975			if (!fts->dir || f->nd || f->status == FTS_SKIP)
976			{
977				if (fts->dir)
978				{
979					closedir(fts->dir);
980					fts->dir = 0;
981				}
982				fts->state = FTS_popstack;
983				continue;
984			}
985
986			/*
987			 * FTS_D or FTS_DNX, about to read children
988			 */
989
990			if (fts->cd == 0)
991			{
992				if ((fts->cd = chdir(fts->name)) < 0)
993					pathcd(fts->home, NiL);
994				else if (fts->pwd != f)
995				{
996					f->pwd = fts->pwd;
997					fts->pwd = f;
998				}
999				fts->curdir = fts->cd < 0 ? 0 : f;
1000			}
1001			fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
1002			fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
1003			fts->dotdot = 0;
1004			fts->endbase = fts->base + fts->baselen;
1005			if (fts->endbase[-1] != '/')
1006				*fts->endbase++ = '/';
1007			fts->current = f;
1008			/*FALLTHROUGH*/
1009
1010		case FTS_readdir:
1011
1012			while (d = readdir(fts->dir))
1013			{
1014				s = d->d_name;
1015				if (s[0] == '.')
1016				{
1017					if (s[1] == 0)
1018					{
1019						fts->current->nlink--;
1020						if (!(fts->flags & FTS_SEEDOT))
1021							continue;
1022						n = 1;
1023					}
1024					else if (s[1] == '.' && s[2] == 0)
1025					{
1026						fts->current->nlink--;
1027						if (fts->current->must == 1)
1028							fts->current->must = 0;
1029						if (!(fts->flags & FTS_SEEDOT))
1030							continue;
1031						n = 2;
1032					}
1033					else
1034						n = 0;
1035				}
1036				else
1037					n = 0;
1038
1039				/*
1040				 * make a new entry
1041				 */
1042
1043				i = D_NAMLEN(d);
1044				if (!(f = node(fts, fts->current, s, i)))
1045					return 0;
1046				TYPE(f, D_TYPE(d));
1047
1048				/*
1049				 * check for space
1050				 */
1051
1052				if (i >= fts->endbuf - fts->endbase)
1053				{
1054		   	   		if (resize(fts, i))
1055						return 0;
1056					fts->endbase = fts->base + fts->baselen;
1057					if (fts->endbase[-1] != '/')
1058						fts->endbase++;
1059				}
1060				if (fts->cpname)
1061				{
1062					memcpy(fts->endbase, s, i + 1);
1063					if (fts->cd)
1064						s = fts->path;
1065				}
1066				if (n)
1067				{
1068					/*
1069					 * don't recurse on . and ..
1070					 */
1071
1072					if (n == 1)
1073						f->fts_statp = fts->current->fts_statp;
1074					else
1075					{
1076						if (f->fts_info != FTS_NS)
1077							fts->dotdot = f;
1078						if (fts->current->fts_parent->fts_level < 0)
1079						{
1080							f->fts_statp = &fts->current->fts_parent->statb;
1081							info(fts, f, s, f->fts_statp, 0);
1082						}
1083						else
1084							f->fts_statp = fts->current->fts_parent->fts_statp;
1085					}
1086					f->fts_info = FTS_DOT;
1087				}
1088				else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
1089					f->statb.st_ino = D_FILENO(d);
1090				if (fts->comparf)
1091					fts->root = search(f, fts->root, fts->comparf, 1);
1092				else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
1093				{
1094					if (fts->top)
1095						fts->bot = fts->bot->fts_link = f;
1096					else
1097						fts->top = fts->bot = f;
1098				}
1099				else
1100				{
1101					/*
1102					 * terminal node
1103					 */
1104
1105					f->fts_path = PATH(fts, fts->path, 1);
1106					f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
1107					f->fts_accpath = ACCESS(fts, f);
1108					fts->previous = fts->current;
1109					fts->current = f;
1110					fts->state = FTS_terminal;
1111					goto note;
1112				}
1113			}
1114
1115			/*
1116			 * done with the directory
1117			 */
1118
1119			closedir(fts->dir);
1120			fts->dir = 0;
1121			if (fts->root)
1122				getlist(&fts->top, &fts->bot, fts->root);
1123			if (fts->children)
1124			{
1125				/*
1126				 * try moving back to parent dir
1127				 */
1128
1129				fts->base[fts->baselen] = 0;
1130				if (fts->cd <= 0)
1131				{
1132					f = fts->current->fts_parent;
1133					if (fts->cd < 0
1134					    || f != fts->curdir
1135					    || !fts->dotdot
1136					    || !SAME(f->fts_statp, fts->dotdot->fts_statp)
1137					    || fts->pwd && fts->pwd->symlink
1138					    || (fts->cd = chdir("..")) < 0
1139#ifdef verify
1140					    || stat(".", &sb) < 0
1141					    || !SAME(&sb, fts->dotdot->fts_statp)
1142#endif
1143					    )
1144						fts->cd = setpdir(fts->home, fts->path, fts->base);
1145					if (fts->pwd)
1146						fts->pwd = fts->pwd->pwd;
1147					fts->curdir = fts->cd ? 0 : f;
1148				}
1149				f = fts->current;
1150				fts->link = f->fts_link;
1151				f->fts_link = fts->top;
1152				f->fts_path = PATH(fts, fts->path, f->fts_level);
1153				f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1154				f->fts_accpath = ACCESS(fts, f);
1155				fts->state = FTS_children_return;
1156				goto note;
1157			}
1158			/*FALLTHROUGH*/
1159
1160		case FTS_children_resume:
1161
1162			fts->base[fts->baselen] = 0;
1163			if (fts->top)
1164			{
1165				fts->bot->fts_link = fts->todo;
1166				fts->todo = fts->top;
1167				fts->top = 0;
1168			}
1169			/*FALLTHROUGH*/
1170
1171		case FTS_popstack:
1172
1173			/*
1174			 * pop objects completely processed
1175			 */
1176
1177			fts->nd = 0;
1178			f = fts->current;
1179			/*FALLTHROUGH*/
1180
1181		case FTS_popstack_resume:
1182
1183			while (fts->todo && f == fts->todo)
1184			{
1185				t = f->fts_parent;
1186				if ((f->fts_info & FTS_DP) == FTS_D)
1187				{
1188					/*
1189					 * delete from <dev,ino> tree
1190					 */
1191
1192					if (f != fts->diroot)
1193						fts->diroot = search(f, fts->diroot, statcmp, 0);
1194					fts->diroot = deleteroot(fts->diroot);
1195					if (f == fts->curdir)
1196					{
1197						fts->nd++;
1198						fts->curdir = t;
1199					}
1200
1201					/*
1202					 * perform post-order processing
1203					 */
1204
1205					if (!(fts->flags & FTS_NOPOSTORDER) &&
1206					    f->status != FTS_SKIP &&
1207					    f->status != FTS_NOPOSTORDER)
1208					{
1209						/*
1210						 * move to parent dir
1211						 */
1212
1213						if (fts->nd > 0)
1214							fts->cd = popdirs(fts);
1215						if (fts->cd < 0)
1216							fts->cd = setpdir(fts->home, fts->path, fts->base);
1217						fts->curdir = fts->cd ? 0 : t;
1218						f->fts_info = FTS_DP;
1219						f->fts_path = PATH(fts, fts->path, f->fts_level);
1220						f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1221						f->fts_accpath = ACCESS(fts, f);
1222
1223						/*
1224						 * re-stat to update nlink/times
1225						 */
1226
1227						stat(f->fts_accpath, f->fts_statp);
1228						fts->link = f->fts_link;
1229						f->fts_link = 0;
1230						fts->state = FTS_popstack_return;
1231						goto note;
1232					}
1233				}
1234
1235				/*
1236				 * reset base
1237				 */
1238
1239				if (fts->base > fts->path + t->fts_namelen)
1240					fts->base--;
1241				*fts->base = 0;
1242				fts->base -= t->fts_namelen;
1243
1244				/*
1245				 * try again or delete from top of stack
1246				 */
1247
1248				if (f->status == FTS_AGAIN)
1249				{
1250					f->fts_info = FTS_D;
1251					f->status = 0;
1252				}
1253				else
1254				{
1255					fts->todo = fts->todo->fts_link;
1256					drop(fts, f);
1257				}
1258				f = t;
1259			}
1260
1261			/*
1262			 * reset current directory
1263			 */
1264
1265			if (fts->nd > 0 && popdirs(fts) < 0)
1266			{
1267				pathcd(fts->home, NiL);
1268				fts->curdir = 0;
1269				fts->cd = -1;
1270			}
1271			if (fts->todo)
1272			{
1273				if (*fts->base)
1274					fts->base += f->fts_namelen;
1275				if (*(fts->base - 1) != '/')
1276					*fts->base++ = '/';
1277				*fts->base = 0;
1278				f = fts->todo;
1279				fts->state = FTS_todo;
1280				continue;
1281			}
1282			return 0;
1283
1284		case FTS_children_return:
1285
1286			f = fts->current;
1287			f->fts_link = fts->link;
1288
1289			/*
1290			 * chdir down again
1291			 */
1292
1293			i = f->fts_info != FTS_DNX;
1294			n = f->status == FTS_SKIP;
1295			if (!n && fts->cd == 0)
1296			{
1297				if ((fts->cd = chdir(fts->base)) < 0)
1298					pathcd(fts->home, NiL);
1299				else if (fts->pwd != f)
1300				{
1301					f->pwd = fts->pwd;
1302					fts->pwd = f;
1303				}
1304				fts->curdir = fts->cd ? 0 : f;
1305			}
1306
1307			/*
1308			 * prune
1309			 */
1310
1311			if (fts->base[fts->baselen - 1] != '/')
1312				fts->base[fts->baselen] = '/';
1313			for (fts->bot = 0, f = fts->top; f; )
1314				if (n || f->status == FTS_SKIP)
1315				{
1316					if (fts->bot)
1317						fts->bot->fts_link = f->fts_link;
1318					else
1319						fts->top = f->fts_link;
1320					drop(fts, f);
1321					f = fts->bot ? fts->bot->fts_link : fts->top;
1322				}
1323				else
1324				{
1325					if (fts->children > 1 && i)
1326					{
1327						if (f->status == FTS_STAT)
1328							info(fts, f, NiL, f->fts_statp, 0);
1329						else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
1330						{
1331							s = f->fts_name;
1332							if (fts->cd)
1333							{
1334								memcpy(fts->endbase, s, f->fts_namelen + 1);
1335								s = fts->path;
1336							}
1337							info(fts, f, s, f->fts_statp, fts->flags);
1338						}
1339					}
1340					fts->bot = f;
1341					f = f->fts_link;
1342				}
1343			fts->children = 0;
1344			fts->state = FTS_children_resume;
1345			continue;
1346
1347		case FTS_popstack_return:
1348
1349			f = fts->todo;
1350			f->fts_link = fts->link;
1351			f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
1352			fts->state = FTS_popstack_resume;
1353			continue;
1354
1355		case FTS_preorder_return:
1356
1357			f = fts->current;
1358			f->fts_link = fts->link;
1359
1360			/*
1361			 * follow symlink if asked to
1362			 */
1363
1364			if (f->status == FTS_FOLLOW)
1365			{
1366				f->status = 0;
1367				if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1368				{
1369					info(fts, f, f->fts_accpath, f->fts_statp, 0);
1370					if (f->fts_info != FTS_SL)
1371					{
1372						fts->state = FTS_preorder;
1373						continue;
1374					}
1375				}
1376			}
1377
1378			/*
1379			 * about to prune this f and already at home
1380			 */
1381
1382			if (fts->cd == 0 && f->fts_level == 0 && f->nd)
1383				fts->cd = -1;
1384			fts->state = FTS_preorder_resume;
1385			continue;
1386
1387		case FTS_terminal:
1388
1389			f = fts->current;
1390			if (f->status == FTS_FOLLOW)
1391			{
1392				f->status = 0;
1393				if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1394				{
1395					info(fts, f, f->fts_accpath, f->fts_statp, 0);
1396					if (f->symlink && f->fts_info != FTS_SL)
1397					{
1398						if (!(f->fts_link = fts->top))
1399							fts->bot = f;
1400						fts->top = f;
1401						fts->current = fts->previous;
1402						fts->state = FTS_readdir;
1403						continue;
1404					}
1405				}
1406			}
1407			f = f->fts_parent;
1408			drop(fts, fts->current);
1409			fts->current = f;
1410			fts->state = FTS_readdir;
1411			continue;
1412
1413		case FTS_error:
1414
1415			return 0;
1416
1417		default:
1418
1419			fts->fts_errno = EINVAL;
1420			fts->state = FTS_error;
1421			return 0;
1422
1423		}
1424 note:
1425#if __OBSOLETE__ < 20140101
1426	f->_fts_pathlen = (unsigned short)f->fts_pathlen;
1427#endif
1428	for (p = notify; p; p = p->next)
1429		if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
1430			break;
1431		else if (n < 0)
1432		{
1433			fts->fts_errno = EINVAL;
1434			fts->state = FTS_error;
1435			return 0;
1436		}
1437	return f;
1438}
1439
1440/*
1441 * set stream or entry flags
1442 */
1443
1444int
1445fts_set(register FTS* fts, register FTSENT* f, int status)
1446{
1447	if (fts || !f || f->fts->current != f)
1448		return -1;
1449	switch (status)
1450	{
1451	case FTS_AGAIN:
1452		break;
1453	case FTS_FOLLOW:
1454		if (!(f->fts_info & FTS_SL))
1455			return -1;
1456		break;
1457	case FTS_NOPOSTORDER:
1458		break;
1459	case FTS_SKIP:
1460		if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
1461			return -1;
1462		break;
1463	default:
1464		return -1;
1465	}
1466	f->status = status;
1467	return 0;
1468}
1469
1470/*
1471 * return the list of child entries
1472 */
1473
1474FTSENT*
1475fts_children(register FTS* fts, int flags)
1476{
1477	register FTSENT*	f;
1478
1479	switch (fts->state)
1480	{
1481
1482	case 0:
1483
1484		if (fts->comparf)
1485			order(fts);
1486		fts->state = FTS_top_return;
1487		return fts->todo;
1488
1489	case FTS_preorder_return:
1490
1491		fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1;
1492		if (f = fts_read(fts))
1493			f = f->fts_link;
1494		return f;
1495
1496	}
1497	return 0;
1498}
1499
1500/*
1501 * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags
1502 * conditioned by astconf()
1503 */
1504
1505int
1506fts_flags(void)
1507{
1508	register char*	s;
1509
1510	s = astconf("PATH_RESOLVE", NiL, NiL);
1511	if (streq(s, "logical"))
1512		return FTS_LOGICAL;
1513	if (streq(s, "physical"))
1514		return FTS_PHYSICAL|FTS_SEEDOTDIR;
1515	return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR;
1516}
1517
1518/*
1519 * return 1 if ent is mounted on a local filesystem
1520 */
1521
1522int
1523fts_local(FTSENT* ent)
1524{
1525#ifdef ST_LOCAL
1526	struct statvfs	fs;
1527
1528	return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL);
1529#else
1530	return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE);
1531#endif
1532}
1533
1534/*
1535 * close an open fts stream
1536 */
1537
1538int
1539fts_close(register FTS* fts)
1540{
1541	register FTSENT*	f;
1542	register FTSENT*	x;
1543
1544	if (fts->dir)
1545		closedir(fts->dir);
1546	if (fts->cd == 0)
1547		pathcd(fts->home, NiL);
1548	free(fts->home);
1549	if (fts->state == FTS_children_return)
1550		fts->current->fts_link = fts->link;
1551	if (fts->top)
1552	{
1553		fts->bot->fts_link = fts->todo;
1554		fts->todo = fts->top;
1555	}
1556	for (f = fts->todo; f; f = x)
1557	{
1558		x = f->fts_link;
1559		free(f);
1560	}
1561	for (f = fts->free; f; f = x)
1562	{
1563		x = f->fts_link;
1564		free(f);
1565	}
1566	free(fts);
1567	return 0;
1568}
1569
1570/*
1571 * register function to be called for each fts_read() entry
1572 * context==0 => unregister notifyf
1573 */
1574
1575int
1576fts_notify(Notify_f notifyf, void* context)
1577{
1578	register Notify_t*	np;
1579	register Notify_t*	pp;
1580
1581	if (context)
1582	{
1583		if (!(np = newof(0, Notify_t, 1, 0)))
1584			return -1;
1585		np->notifyf = notifyf;
1586		np->context = context;
1587		np->next = notify;
1588		notify = np;
1589	}
1590	else
1591	{
1592		for (np = notify, pp = 0; np; pp = np, np = np->next)
1593			if (np->notifyf == notifyf)
1594			{
1595				if (pp)
1596					pp->next = np->next;
1597				else
1598					notify = np->next;
1599				free(np);
1600				return 0;
1601			}
1602		return -1;
1603	}
1604	return 0;
1605}
1606