xref: /netbsd-src/usr.sbin/mtree/spec.c (revision 2cc3d62fc0c95918b8048aaa3f6cb9421e8c1a73)
1 /*	$NetBSD: spec.c,v 1.92 2024/12/05 17:17:43 christos Exp $	*/
2 
3 /*-
4  * Copyright (c) 1989, 1993
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. Neither the name of the University nor the names of its contributors
16  *    may be used to endorse or promote products derived from this software
17  *    without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29  * SUCH DAMAGE.
30  */
31 
32 /*-
33  * Copyright (c) 2001-2004 The NetBSD Foundation, Inc.
34  * All rights reserved.
35  *
36  * This code is derived from software contributed to The NetBSD Foundation
37  * by Luke Mewburn of Wasabi Systems.
38  *
39  * Redistribution and use in source and binary forms, with or without
40  * modification, are permitted provided that the following conditions
41  * are met:
42  * 1. Redistributions of source code must retain the above copyright
43  *    notice, this list of conditions and the following disclaimer.
44  * 2. Redistributions in binary form must reproduce the above copyright
45  *    notice, this list of conditions and the following disclaimer in the
46  *    documentation and/or other materials provided with the distribution.
47  *
48  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
49  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
50  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
51  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
52  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
53  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
54  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
55  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
56  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
57  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
58  * POSSIBILITY OF SUCH DAMAGE.
59  */
60 
61 #if HAVE_NBTOOL_CONFIG_H
62 #include "nbtool_config.h"
63 #endif
64 
65 #include <sys/cdefs.h>
66 #if defined(__RCSID) && !defined(lint)
67 #if 0
68 static char sccsid[] = "@(#)spec.c	8.2 (Berkeley) 4/28/95";
69 #else
70 __RCSID("$NetBSD: spec.c,v 1.92 2024/12/05 17:17:43 christos Exp $");
71 #endif
72 #endif /* not lint */
73 
74 #include <sys/param.h>
75 #include <sys/stat.h>
76 
77 #include <assert.h>
78 #include <ctype.h>
79 #include <errno.h>
80 #include <grp.h>
81 #include <pwd.h>
82 #include <stdarg.h>
83 #include <stdio.h>
84 #include <stdint.h>
85 #include <stdlib.h>
86 #include <string.h>
87 #include <unistd.h>
88 #include <vis.h>
89 #include <util.h>
90 
91 #include "extern.h"
92 #include "pack_dev.h"
93 
94 size_t	mtree_lineno;			/* Current spec line number */
95 int	mtree_Mflag;			/* Merge duplicate entries */
96 int	mtree_Wflag;			/* Don't "whack" permissions */
97 int	mtree_Sflag;			/* Sort entries */
98 
99 static	dev_t	parsedev(char *);
100 static	void	replacenode(NODE *, NODE *);
101 static	void	set(char *, NODE *);
102 static	void	unset(char *, NODE *);
103 static	void	addchild(NODE *, NODE *);
104 static	int	nodecmp(const NODE *, const NODE *);
105 static	int	appendfield(FILE *, int, const char *, ...) __printflike(3, 4);
106 
107 #define REPLACEPTR(x,v)	do { if ((x)) free((x)); (x) = (v); } while (0)
108 
109 NODE *
110 spec(FILE *fp)
111 {
112 	NODE *centry, *last, *pathparent, *cur;
113 	char *p, *e, *next;
114 	NODE ginfo, *root;
115 	char *buf, *tname, *ntname;
116 	size_t tnamelen, plen;
117 
118 	root = NULL;
119 	centry = last = NULL;
120 	tname = NULL;
121 	tnamelen = 0;
122 	memset(&ginfo, 0, sizeof(ginfo));
123 	for (mtree_lineno = 0;
124 	    (buf = fparseln(fp, NULL, &mtree_lineno, NULL,
125 		FPARSELN_UNESCCOMM));
126 	    free(buf)) {
127 		/* Skip leading whitespace. */
128 		for (p = buf; *p && isspace((unsigned char)*p); ++p)
129 			continue;
130 
131 		/* If nothing but whitespace, continue. */
132 		if (!*p)
133 			continue;
134 
135 #ifdef DEBUG
136 		fprintf(stderr, "line %lu: {%s}\n",
137 		    (u_long)mtree_lineno, p);
138 #endif
139 		/* Grab file name, "$", "set", or "unset". */
140 		next = buf;
141 		while ((p = strsep(&next, " \t")) != NULL && *p == '\0')
142 			continue;
143 		if (p == NULL)
144 			mtree_err("missing field");
145 
146 		if (p[0] == '/') {
147 			if (strcmp(p + 1, "set") == 0)
148 				set(next, &ginfo);
149 			else if (strcmp(p + 1, "unset") == 0)
150 				unset(next, &ginfo);
151 			else
152 				mtree_err("invalid specification `%s'", p);
153 			continue;
154 		}
155 
156 		if (strcmp(p, "..") == 0) {
157 			/* Don't go up, if haven't gone down. */
158 			if (root == NULL)
159 				goto noparent;
160 			if (last->type != F_DIR || last->flags & F_DONE) {
161 				if (last == root)
162 					goto noparent;
163 				last = last->parent;
164 			}
165 			last->flags |= F_DONE;
166 			continue;
167 
168 noparent:		mtree_err("no parent node");
169 		}
170 
171 		plen = strlen(p) + 1;
172 		if (plen > tnamelen) {
173 			if ((ntname = realloc(tname, plen)) == NULL)
174 				mtree_err("realloc: %s", strerror(errno));
175 			tname = ntname;
176 			tnamelen = plen;
177 		}
178 		if (strunvis(tname, p) == -1)
179 			mtree_err("strunvis failed on `%s'", p);
180 		p = tname;
181 
182 		pathparent = NULL;
183 		if (strchr(p, '/') != NULL) {
184 			cur = root;
185 			for (; (e = strchr(p, '/')) != NULL; p = e+1) {
186 				if (p == e)
187 					continue;	/* handle // */
188 				*e = '\0';
189 				if (strcmp(p, ".") != 0) {
190 					while (cur &&
191 					    strcmp(cur->name, p) != 0) {
192 						cur = cur->next;
193 					}
194 				}
195 				if (cur == NULL || cur->type != F_DIR) {
196 					mtree_err("%s: %s", tname,
197 					"missing directory in specification");
198 				}
199 				*e = '/';
200 				pathparent = cur;
201 				cur = cur->child;
202 			}
203 			if (*p == '\0')
204 				mtree_err("%s: empty leaf element", tname);
205 		}
206 
207 		if ((centry = calloc(1, sizeof(NODE) + strlen(p))) == NULL)
208 			mtree_err("%s", strerror(errno));
209 		*centry = ginfo;
210 		centry->lineno = mtree_lineno;
211 		strcpy(centry->name, p);
212 #define	MAGIC	"?*["
213 		if (strpbrk(p, MAGIC))
214 			centry->flags |= F_MAGIC;
215 		set(next, centry);
216 
217 		if (root == NULL) {
218 				/*
219 				 * empty tree
220 				 */
221 			/*
222 			 * Allow a bare "." root node by forcing it to
223 			 * type=dir for compatibility with FreeBSD.
224 			 */
225 			if (strcmp(centry->name, ".") == 0 && centry->type == 0)
226 				centry->type = F_DIR;
227 			if (strcmp(centry->name, ".") != 0)
228 				mtree_err(
229 				    "root node must be the directory `.',"
230 				    " found `%s'", centry->name);
231 			if (centry->type != F_DIR)
232 				mtree_err(
233 				    "root node must type %#x != %#x",
234 				    F_DIR, centry->type);
235 			last = root = centry;
236 			root->parent = root;
237 		} else if (pathparent != NULL) {
238 				/*
239 				 * full path entry; add or replace
240 				 */
241 			centry->parent = pathparent;
242 			addchild(pathparent, centry);
243 			last = centry;
244 		} else if (strcmp(centry->name, ".") == 0) {
245 				/*
246 				 * duplicate "." entry; always replace
247 				 */
248 			replacenode(root, centry);
249 		} else if (last->type == F_DIR && !(last->flags & F_DONE)) {
250 				/*
251 				 * new relative child in current dir;
252 				 * add or replace
253 				 */
254 			centry->parent = last;
255 			addchild(last, centry);
256 			last = centry;
257 		} else {
258 				/*
259 				 * new relative child in parent dir
260 				 * (after encountering ".." entry);
261 				 * add or replace
262 				 */
263 			centry->parent = last->parent;
264 			addchild(last->parent, centry);
265 			last = centry;
266 		}
267 	}
268 	return (root);
269 }
270 
271 void
272 free_nodes(NODE *root)
273 {
274 	NODE	*cur, *next;
275 
276 	if (root == NULL)
277 		return;
278 
279 	next = NULL;
280 	for (cur = root; cur != NULL; cur = next) {
281 		next = cur->next;
282 		free_nodes(cur->child);
283 		REPLACEPTR(cur->slink, NULL);
284 		REPLACEPTR(cur->md5digest, NULL);
285 		REPLACEPTR(cur->rmd160digest, NULL);
286 		REPLACEPTR(cur->sha1digest, NULL);
287 		REPLACEPTR(cur->sha256digest, NULL);
288 		REPLACEPTR(cur->sha384digest, NULL);
289 		REPLACEPTR(cur->sha512digest, NULL);
290 		REPLACEPTR(cur->tags, NULL);
291 		REPLACEPTR(cur, NULL);
292 	}
293 }
294 
295 /*
296  * appendfield --
297  *	Like fprintf(), but output a space either before or after
298  *	the regular output, according to the pathlast flag.
299  */
300 static int
301 appendfield(FILE *fp, int pathlast, const char *fmt, ...)
302 {
303 	va_list ap;
304 	int result;
305 
306 	va_start(ap, fmt);
307 	if (!pathlast)
308 		fprintf(fp, " ");
309 	result = vprintf(fmt, ap);
310 	if (pathlast)
311 		fprintf(fp, " ");
312 	va_end(ap);
313 	return result;
314 }
315 
316 /*
317  * dump_nodes --
318  *	dump the NODEs from `cur', based in the directory `dir'.
319  *	if pathlast is none zero, print the path last, otherwise print
320  *	it first.
321  */
322 void
323 dump_nodes(FILE *fp, const char *dir, NODE *root, int pathlast)
324 {
325 	NODE	*cur;
326 	char	path[MAXPATHLEN];
327 	const char *name;
328 	char	*str;
329 	char	*p, *q;
330 
331 	for (cur = root; cur != NULL; cur = cur->next) {
332 		if (cur->type != F_DIR && !matchtags(cur))
333 			continue;
334 
335 		if (snprintf(path, sizeof(path), "%s%s%s",
336 		    dir, *dir ? "/" : "", cur->name)
337 		    >= (int)sizeof(path))
338 			mtree_err("Pathname too long.");
339 
340 		if (!pathlast)
341 			fprintf(fp, "%s", vispath(path));
342 
343 #define MATCHFLAG(f)	((keys & (f)) && (cur->flags & (f)))
344 		if (MATCHFLAG(F_TYPE))
345 			appendfield(fp, pathlast, "type=%s",
346 			    nodetype(cur->type));
347 		if (MATCHFLAG(F_UID | F_UNAME)) {
348 			if (keys & F_UNAME &&
349 			    (name = user_from_uid(cur->st_uid, 1)) != NULL)
350 				appendfield(fp, pathlast, "uname=%s", name);
351 			else
352 				appendfield(fp, pathlast, "uid=%u",
353 				    cur->st_uid);
354 		}
355 		if (MATCHFLAG(F_GID | F_GNAME)) {
356 			if (keys & F_GNAME &&
357 			    (name = group_from_gid(cur->st_gid, 1)) != NULL)
358 				appendfield(fp, pathlast, "gname=%s", name);
359 			else
360 				appendfield(fp, pathlast, "gid=%u",
361 				    cur->st_gid);
362 		}
363 		if (MATCHFLAG(F_MODE))
364 			appendfield(fp, pathlast, "mode=%#o", cur->st_mode);
365 		if (MATCHFLAG(F_DEV) &&
366 		    (cur->type == F_BLOCK || cur->type == F_CHAR))
367 			appendfield(fp, pathlast, "device=%#jx",
368 			    (uintmax_t)cur->st_rdev);
369 		if (MATCHFLAG(F_NLINK))
370 			appendfield(fp, pathlast, "nlink=%ju",
371 			    (uintmax_t)cur->st_nlink);
372 		if (MATCHFLAG(F_SLINK))
373 			appendfield(fp, pathlast, "link=%s",
374 			    vispath(cur->slink));
375 		if (MATCHFLAG(F_SIZE))
376 			appendfield(fp, pathlast, "size=%ju",
377 			    (uintmax_t)cur->st_size);
378 		if (MATCHFLAG(F_TIME))
379 			appendfield(fp, pathlast, "time=%jd.%09ld",
380 			    (intmax_t)cur->st_mtimespec.tv_sec,
381 			    cur->st_mtimespec.tv_nsec);
382 		if (MATCHFLAG(F_CKSUM))
383 			appendfield(fp, pathlast, "cksum=%lu", cur->cksum);
384 		if (MATCHFLAG(F_MD5))
385 			appendfield(fp, pathlast, "%s=%s", MD5KEY,
386 			    cur->md5digest);
387 		if (MATCHFLAG(F_RMD160))
388 			appendfield(fp, pathlast, "%s=%s", RMD160KEY,
389 			    cur->rmd160digest);
390 		if (MATCHFLAG(F_SHA1))
391 			appendfield(fp, pathlast, "%s=%s", SHA1KEY,
392 			    cur->sha1digest);
393 		if (MATCHFLAG(F_SHA256))
394 			appendfield(fp, pathlast, "%s=%s", SHA256KEY,
395 			    cur->sha256digest);
396 		if (MATCHFLAG(F_SHA384))
397 			appendfield(fp, pathlast, "%s=%s", SHA384KEY,
398 			    cur->sha384digest);
399 		if (MATCHFLAG(F_SHA512))
400 			appendfield(fp, pathlast, "%s=%s", SHA512KEY,
401 			    cur->sha512digest);
402 		if (MATCHFLAG(F_FLAGS)) {
403 			str = flags_to_string(cur->st_flags, "none");
404 			appendfield(fp, pathlast, "flags=%s", str);
405 			free(str);
406 		}
407 		if (MATCHFLAG(F_IGN))
408 			appendfield(fp, pathlast, "ignore");
409 		if (MATCHFLAG(F_OPT))
410 			appendfield(fp, pathlast, "optional");
411 		if (MATCHFLAG(F_TAGS)) {
412 			/* don't output leading or trailing commas */
413 			p = cur->tags;
414 			while (*p == ',')
415 				p++;
416 			q = p + strlen(p);
417 			while(q > p && q[-1] == ',')
418 				q--;
419 			appendfield(fp, pathlast, "tags=%.*s", (int)(q - p), p);
420 		}
421 		puts(pathlast ? vispath(path) : "");
422 
423 		if (cur->child)
424 			dump_nodes(fp, path, cur->child, pathlast);
425 	}
426 }
427 
428 /*
429  * vispath --
430  *	strsvis(3) encodes path, which must not be longer than MAXPATHLEN
431  *	characters long, and returns a pointer to a static buffer containing
432  *	the result.
433  */
434 char *
435 vispath(const char *path)
436 {
437 	static const char extra[] = { ' ', '\t', '\n', '\\', '#', '\0' };
438 	static const char extra_glob[] = { ' ', '\t', '\n', '\\', '#', '*',
439 	    '?', '[', '\0' };
440 	static char pathbuf[4*MAXPATHLEN + 1];
441 
442 	if (flavor == F_NETBSD6)
443 		strsvis(pathbuf, path, VIS_CSTYLE, extra);
444 	else
445 		strsvis(pathbuf, path, VIS_OCTAL, extra_glob);
446 	return pathbuf;
447 }
448 
449 
450 static dev_t
451 parsedev(char *arg)
452 {
453 #define MAX_PACK_ARGS	3
454 	u_long	numbers[MAX_PACK_ARGS];
455 	char	*p, *ep, *dev;
456 	int	argc;
457 	pack_t	*pack;
458 	dev_t	result;
459 	const char *error = NULL;
460 
461 	if ((dev = strchr(arg, ',')) != NULL) {
462 		*dev++='\0';
463 		if ((pack = pack_find(arg)) == NULL)
464 			mtree_err("unknown format `%s'", arg);
465 		argc = 0;
466 		while ((p = strsep(&dev, ",")) != NULL) {
467 			if (*p == '\0')
468 				mtree_err("missing number");
469 			numbers[argc++] = strtoul(p, &ep, 0);
470 			if (*ep != '\0')
471 				mtree_err("invalid number `%s'",
472 				    p);
473 			if (argc > MAX_PACK_ARGS)
474 				mtree_err("too many arguments");
475 		}
476 		if (argc < 2)
477 			mtree_err("not enough arguments");
478 		result = (*pack)(argc, numbers, &error);
479 		if (error != NULL)
480 			mtree_err("%s", error);
481 	} else {
482 		result = (dev_t)strtoul(arg, &ep, 0);
483 		if (*ep != '\0')
484 			mtree_err("invalid device `%s'", arg);
485 	}
486 	return (result);
487 }
488 
489 static void
490 replacenode(NODE *cur, NODE *new)
491 {
492 
493 #define REPLACE(x)	cur->x = new->x
494 #define REPLACESTR(x)	REPLACEPTR(cur->x,new->x)
495 
496 	if (cur->type != new->type) {
497 		if (mtree_Mflag) {
498 				/*
499 				 * merge entries with different types; we
500 				 * don't want children retained in this case.
501 				 */
502 			REPLACE(type);
503 			free_nodes(cur->child);
504 			cur->child = NULL;
505 		} else {
506 			mtree_err(
507 			    "existing entry for `%s', type `%s'"
508 			    " does not match type `%s'",
509 			    cur->name, nodetype(cur->type),
510 			    nodetype(new->type));
511 		}
512 	}
513 
514 	REPLACE(st_size);
515 	REPLACE(st_mtimespec);
516 	REPLACESTR(slink);
517 	if (cur->slink != NULL) {
518 		if ((cur->slink = strdup(new->slink)) == NULL)
519 			mtree_err("memory allocation error");
520 		if (strunvis(cur->slink, new->slink) == -1)
521 			mtree_err("strunvis failed on `%s'", new->slink);
522 		free(new->slink);
523 	}
524 	REPLACE(st_uid);
525 	REPLACE(st_gid);
526 	REPLACE(st_mode);
527 	REPLACE(st_rdev);
528 	REPLACE(st_flags);
529 	REPLACE(st_nlink);
530 	REPLACE(cksum);
531 	REPLACESTR(md5digest);
532 	REPLACESTR(rmd160digest);
533 	REPLACESTR(sha1digest);
534 	REPLACESTR(sha256digest);
535 	REPLACESTR(sha384digest);
536 	REPLACESTR(sha512digest);
537 	REPLACESTR(tags);
538 	REPLACE(lineno);
539 	REPLACE(flags);
540 	free(new);
541 }
542 
543 static void
544 set(char *t, NODE *ip)
545 {
546 	int	type, value;
547 	size_t	len;
548 	gid_t	gid;
549 	uid_t	uid;
550 	char	*kw, *val, *md, *ep;
551 	void	*m;
552 
553 	while ((kw = strsep(&t, "= \t")) != NULL) {
554 		if (*kw == '\0')
555 			continue;
556 		if (strcmp(kw, "all") == 0)
557 			mtree_err("invalid keyword `all'");
558 		ip->flags |= type = parsekey(kw, &value);
559 		if (!value)
560 			/* Just set flag bit (F_IGN and F_OPT) */
561 			continue;
562 		while ((val = strsep(&t, " \t")) != NULL && *val == '\0')
563 			continue;
564 		if (val == NULL)
565 			mtree_err("missing value");
566 		switch (type) {
567 		case F_CKSUM:
568 			ip->cksum = strtoul(val, &ep, 10);
569 			if (*ep)
570 				mtree_err("invalid checksum `%s'", val);
571 			break;
572 		case F_DEV:
573 			ip->st_rdev = parsedev(val);
574 			break;
575 		case F_FLAGS:
576 			if (strcmp("none", val) == 0)
577 				ip->st_flags = 0;
578 			else if (string_to_flags(&val, &ip->st_flags, NULL)
579 			    != 0)
580 				mtree_err("invalid flag `%s'", val);
581 			break;
582 		case F_GID:
583 			ip->st_gid = (gid_t)strtoul(val, &ep, 10);
584 			if (*ep)
585 				mtree_err("invalid gid `%s'", val);
586 			break;
587 		case F_GNAME:
588 			if (mtree_Wflag)	/* don't parse if whacking */
589 				break;
590 			if (gid_from_group(val, &gid) == -1)
591 				mtree_err("unknown group `%s'", val);
592 			ip->st_gid = gid;
593 			break;
594 		case F_MD5:
595 			if (val[0]=='0' && val[1]=='x')
596 				md=&val[2];
597 			else
598 				md=val;
599 			if ((ip->md5digest = strdup(md)) == NULL)
600 				mtree_err("memory allocation error");
601 			break;
602 		case F_MODE:
603 			if ((m = setmode(val)) == NULL)
604 				mtree_err("cannot set file mode `%s' (%s)",
605 				    val, strerror(errno));
606 			ip->st_mode = getmode(m, 0);
607 			free(m);
608 			break;
609 		case F_NLINK:
610 			ip->st_nlink = (nlink_t)strtoul(val, &ep, 10);
611 			if (*ep)
612 				mtree_err("invalid link count `%s'", val);
613 			break;
614 		case F_RMD160:
615 			if (val[0]=='0' && val[1]=='x')
616 				md=&val[2];
617 			else
618 				md=val;
619 			if ((ip->rmd160digest = strdup(md)) == NULL)
620 				mtree_err("memory allocation error");
621 			break;
622 		case F_SHA1:
623 			if (val[0]=='0' && val[1]=='x')
624 				md=&val[2];
625 			else
626 				md=val;
627 			if ((ip->sha1digest = strdup(md)) == NULL)
628 				mtree_err("memory allocation error");
629 			break;
630 		case F_SIZE:
631 			ip->st_size = (off_t)strtoll(val, &ep, 10);
632 			if (*ep)
633 				mtree_err("invalid size `%s'", val);
634 			break;
635 		case F_SLINK:
636 			if ((ip->slink = strdup(val)) == NULL)
637 				mtree_err("memory allocation error");
638 			if (strunvis(ip->slink, val) == -1)
639 				mtree_err("strunvis failed on `%s'", val);
640 			break;
641 		case F_TAGS:
642 			len = strlen(val) + 3;	/* "," + str + ",\0" */
643 			if ((ip->tags = malloc(len)) == NULL)
644 				mtree_err("memory allocation error");
645 			snprintf(ip->tags, len, ",%s,", val);
646 			break;
647 		case F_TIME:
648 			ip->st_mtimespec.tv_sec =
649 			    (time_t)strtoll(val, &ep, 10);
650 			if (*ep != '.')
651 				mtree_err("invalid time `%s'", val);
652 			val = ep + 1;
653 			ip->st_mtimespec.tv_nsec = strtol(val, &ep, 10);
654 			if (*ep)
655 				mtree_err("invalid time `%s'", val);
656 			break;
657 		case F_TYPE:
658 			ip->type = parsetype(val);
659 			break;
660 		case F_UID:
661 			ip->st_uid = (uid_t)strtoul(val, &ep, 10);
662 			if (*ep)
663 				mtree_err("invalid uid `%s'", val);
664 			break;
665 		case F_UNAME:
666 			if (mtree_Wflag)	/* don't parse if whacking */
667 				break;
668 			if (uid_from_user(val, &uid) == -1)
669 				mtree_err("unknown user `%s'", val);
670 			ip->st_uid = uid;
671 			break;
672 		case F_SHA256:
673 			if (val[0]=='0' && val[1]=='x')
674 				md=&val[2];
675 			else
676 				md=val;
677 			if ((ip->sha256digest = strdup(md)) == NULL)
678 				mtree_err("memory allocation error");
679 			break;
680 		case F_SHA384:
681 			if (val[0]=='0' && val[1]=='x')
682 				md=&val[2];
683 			else
684 				md=val;
685 			if ((ip->sha384digest = strdup(md)) == NULL)
686 				mtree_err("memory allocation error");
687 			break;
688 		case F_SHA512:
689 			if (val[0]=='0' && val[1]=='x')
690 				md=&val[2];
691 			else
692 				md=val;
693 			if ((ip->sha512digest = strdup(md)) == NULL)
694 				mtree_err("memory allocation error");
695 			break;
696 		default:
697 			mtree_err(
698 			    "set(): unsupported key type 0x%x (INTERNAL ERROR)",
699 			    type);
700 			/* NOTREACHED */
701 		}
702 	}
703 }
704 
705 static void
706 unset(char *t, NODE *ip)
707 {
708 	char *p;
709 
710 	while ((p = strsep(&t, " \t")) != NULL) {
711 		if (*p == '\0')
712 			continue;
713 		ip->flags &= ~parsekey(p, NULL);
714 	}
715 }
716 
717 /*
718  * addchild --
719  *	Add the centry node as a child of the pathparent node.	If
720  *	centry is a duplicate, call replacenode().  If centry is not
721  *	a duplicate, insert it into the linked list referenced by
722  *	pathparent->child.  Keep the list sorted if Sflag is set.
723  */
724 static void
725 addchild(NODE *pathparent, NODE *centry)
726 {
727 	NODE *samename;      /* node with the same name as centry */
728 	NODE *replacepos;    /* if non-NULL, centry should replace this node */
729 	NODE *insertpos;     /* if non-NULL, centry should be inserted
730 			      * after this node */
731 	NODE *cur;           /* for stepping through the list */
732 	NODE *last;          /* the last node in the list */
733 	int cmp;
734 
735 	samename = NULL;
736 	replacepos = NULL;
737 	insertpos = NULL;
738 	last = NULL;
739 	cur = pathparent->child;
740 	if (cur == NULL) {
741 		/* centry is pathparent's first and only child node so far */
742 		pathparent->child = centry;
743 		return;
744 	}
745 
746 	/*
747 	 * pathparent already has at least one other child, so add the
748 	 * centry node to the list.
749 	 *
750 	 * We first scan through the list looking for an existing node
751 	 * with the same name (setting samename), and also looking
752 	 * for the correct position to replace or insert the new node
753 	 * (setting replacepos and/or insertpos).
754 	 */
755 	for (; cur != NULL; last = cur, cur = cur->next) {
756 		if (strcmp(centry->name, cur->name) == 0) {
757 			samename = cur;
758 		}
759 		if (mtree_Sflag) {
760 			cmp = nodecmp(centry, cur);
761 			if (cmp == 0) {
762 				replacepos = cur;
763 			} else if (cmp > 0) {
764 				insertpos = cur;
765 			}
766 		}
767 	}
768 	if (! mtree_Sflag) {
769 		if (samename != NULL) {
770 			/* replace node with same name */
771 			replacepos = samename;
772 		} else {
773 			/* add new node at end of list */
774 			insertpos = last;
775 		}
776 	}
777 
778 	if (samename != NULL) {
779 		/*
780 		 * We found a node with the same name above.  Call
781 		 * replacenode(), which will either exit with an error,
782 		 * or replace the information in the samename node and
783 		 * free the information in the centry node.
784 		 */
785 		replacenode(samename, centry);
786 		if (samename == replacepos) {
787 			/* The just-replaced node was in the correct position */
788 			return;
789 		}
790 		if (samename == insertpos || samename->prev == insertpos) {
791 			/*
792 			 * We thought the new node should be just before
793 			 * or just after the replaced node, but that would
794 			 * be equivalent to just retaining the replaced node.
795 			 */
796 			return;
797 		}
798 
799 		/*
800 		 * The just-replaced node is in the wrong position in
801 		 * the list.  This can happen if sort order depends on
802 		 * criteria other than the node name.
803 		 *
804 		 * Make centry point to the just-replaced node.	 Unlink
805 		 * the just-replaced node from the list, and allow it to
806 		 * be insterted in the correct position later.
807 		 */
808 		centry = samename;
809 		if (centry->prev)
810 			centry->prev->next = centry->next;
811 		else {
812 			/* centry->next is the new head of the list */
813 			pathparent->child = centry->next;
814 			assert(centry->next != NULL);
815 		}
816 		if (centry->next)
817 			centry->next->prev = centry->prev;
818 		centry->prev = NULL;
819 		centry->next = NULL;
820 	}
821 
822 	if (insertpos == NULL) {
823 		/* insert centry at the beginning of the list */
824 		pathparent->child->prev = centry;
825 		centry->next = pathparent->child;
826 		centry->prev = NULL;
827 		pathparent->child = centry;
828 	} else {
829 		/* insert centry into the list just after insertpos */
830 		centry->next = insertpos->next;
831 		insertpos->next = centry;
832 		centry->prev = insertpos;
833 		if (centry->next)
834 			centry->next->prev = centry;
835 	}
836 	return;
837 }
838 
839 /*
840  * nodecmp --
841  *	used as a comparison function by addchild() to control the order
842  *	in which entries appear within a list of sibling nodes.	 We make
843  *	directories sort after non-directories, but otherwise sort in
844  *	strcmp() order.
845  *
846  * Keep this in sync with dcmp() below.
847  */
848 static int
849 nodecmp(const NODE *a, const NODE *b)
850 {
851 
852 	if ((a->type & F_DIR) != 0) {
853 		if ((b->type & F_DIR) == 0)
854 			return 1;
855 	} else if ((b->type & F_DIR) != 0) {
856 		return -1;
857 	}
858 	return strcmp(a->name, b->name);
859 }
860 
861 /*
862  * dcmp --
863  *    used as a comparison function passed to fts_open() to control
864  *    the order in which fts_read() returns results.    We make
865  *    directories sort after non-directories, but otherwise sort in
866  *    strcmp() order.
867  *
868  * Keep this in sync with nodecmp() above.
869  */
870 int
871 dcmp(const FTSENT *FTS_CONST *a, const FTSENT *FTS_CONST *b)
872 {
873 
874 	if (S_ISDIR((*a)->fts_statp->st_mode)) {
875 		if (!S_ISDIR((*b)->fts_statp->st_mode))
876 			return 1;
877 	} else if (S_ISDIR((*b)->fts_statp->st_mode)) {
878 		return -1;
879 	}
880 	return strcmp((*a)->fts_name, (*b)->fts_name);
881 }
882