xref: /illumos-gate/usr/src/cmd/mandoc/mansearch.c (revision 5bb0bdfe588c5df0f63ff8ac292cd608a5f4492a) 
1 /*	$Id: mansearch.c,v 1.77 2017/08/22 17:50:11 schwarze Exp $ */
2 /*
3  * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
4  * Copyright (c) 2013-2017 Ingo Schwarze <schwarze@openbsd.org>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 #include "config.h"
19 
20 #include <sys/mman.h>
21 #include <sys/types.h>
22 
23 #include <assert.h>
24 #if HAVE_ERR
25 #include <err.h>
26 #endif
27 #include <errno.h>
28 #include <fcntl.h>
29 #include <glob.h>
30 #include <limits.h>
31 #include <regex.h>
32 #include <stdio.h>
33 #include <stdint.h>
34 #include <stddef.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include <unistd.h>
38 
39 #include "mandoc.h"
40 #include "mandoc_aux.h"
41 #include "mandoc_ohash.h"
42 #include "manconf.h"
43 #include "mansearch.h"
44 #include "dbm.h"
45 
46 struct	expr {
47 	/* Used for terms: */
48 	struct dbm_match match;   /* Match type and expression. */
49 	uint64_t	 bits;    /* Type mask. */
50 	/* Used for OR and AND groups: */
51 	struct expr	*next;    /* Next child in the parent group. */
52 	struct expr	*child;   /* First child in this group. */
53 	enum { EXPR_TERM, EXPR_OR, EXPR_AND } type;
54 };
55 
56 const char *const mansearch_keynames[KEY_MAX] = {
57 	"arch",	"sec",	"Xr",	"Ar",	"Fa",	"Fl",	"Dv",	"Fn",
58 	"Ic",	"Pa",	"Cm",	"Li",	"Em",	"Cd",	"Va",	"Ft",
59 	"Tn",	"Er",	"Ev",	"Sy",	"Sh",	"In",	"Ss",	"Ox",
60 	"An",	"Mt",	"St",	"Bx",	"At",	"Nx",	"Fx",	"Lk",
61 	"Ms",	"Bsx",	"Dx",	"Rs",	"Vt",	"Lb",	"Nm",	"Nd"
62 };
63 
64 
65 static	struct ohash	*manmerge(struct expr *, struct ohash *);
66 static	struct ohash	*manmerge_term(struct expr *, struct ohash *);
67 static	struct ohash	*manmerge_or(struct expr *, struct ohash *);
68 static	struct ohash	*manmerge_and(struct expr *, struct ohash *);
69 static	char		*buildnames(const struct dbm_page *);
70 static	char		*buildoutput(size_t, struct dbm_page *);
71 static	size_t		 lstlen(const char *, size_t);
72 static	void		 lstcat(char *, size_t *, const char *, const char *);
73 static	int		 lstmatch(const char *, const char *);
74 static	struct expr	*exprcomp(const struct mansearch *,
75 				int, char *[], int *);
76 static	struct expr	*expr_and(const struct mansearch *,
77 				int, char *[], int *);
78 static	struct expr	*exprterm(const struct mansearch *,
79 				int, char *[], int *);
80 static	void		 exprfree(struct expr *);
81 static	int		 manpage_compare(const void *, const void *);
82 
83 
84 int
85 mansearch(const struct mansearch *search,
86 		const struct manpaths *paths,
87 		int argc, char *argv[],
88 		struct manpage **res, size_t *sz)
89 {
90 	char		 buf[PATH_MAX];
91 	struct dbm_res	*rp;
92 	struct expr	*e;
93 	struct dbm_page	*page;
94 	struct manpage	*mpage;
95 	struct ohash	*htab;
96 	size_t		 cur, i, maxres, outkey;
97 	unsigned int	 slot;
98 	int		 argi, chdir_status, getcwd_status, im;
99 
100 	argi = 0;
101 	if ((e = exprcomp(search, argc, argv, &argi)) == NULL) {
102 		*sz = 0;
103 		return 0;
104 	}
105 
106 	cur = maxres = 0;
107 	if (res != NULL)
108 		*res = NULL;
109 
110 	outkey = KEY_Nd;
111 	if (search->outkey != NULL)
112 		for (im = 0; im < KEY_MAX; im++)
113 			if (0 == strcasecmp(search->outkey,
114 			    mansearch_keynames[im])) {
115 				outkey = im;
116 				break;
117 			}
118 
119 	/*
120 	 * Remember the original working directory, if possible.
121 	 * This will be needed if the second or a later directory
122 	 * is given as a relative path.
123 	 * Do not error out if the current directory is not
124 	 * searchable: Maybe it won't be needed after all.
125 	 */
126 
127 	if (getcwd(buf, PATH_MAX) == NULL) {
128 		getcwd_status = 0;
129 		(void)strlcpy(buf, strerror(errno), sizeof(buf));
130 	} else
131 		getcwd_status = 1;
132 
133 	/*
134 	 * Loop over the directories (containing databases) for us to
135 	 * search.
136 	 * Don't let missing/bad databases/directories phase us.
137 	 * In each, try to open the resident database and, if it opens,
138 	 * scan it for our match expression.
139 	 */
140 
141 	chdir_status = 0;
142 	for (i = 0; i < paths->sz; i++) {
143 		if (chdir_status && paths->paths[i][0] != '/') {
144 			if ( ! getcwd_status) {
145 				warnx("%s: getcwd: %s", paths->paths[i], buf);
146 				continue;
147 			} else if (chdir(buf) == -1) {
148 				warn("%s", buf);
149 				continue;
150 			}
151 		}
152 		if (chdir(paths->paths[i]) == -1) {
153 			warn("%s", paths->paths[i]);
154 			continue;
155 		}
156 		chdir_status = 1;
157 
158 		if (dbm_open(MANDOC_DB) == -1) {
159 			if (errno != ENOENT)
160 				warn("%s/%s", paths->paths[i], MANDOC_DB);
161 			continue;
162 		}
163 
164 		if ((htab = manmerge(e, NULL)) == NULL) {
165 			dbm_close();
166 			continue;
167 		}
168 
169 		for (rp = ohash_first(htab, &slot); rp != NULL;
170 		    rp = ohash_next(htab, &slot)) {
171 			page = dbm_page_get(rp->page);
172 
173 			if (lstmatch(search->sec, page->sect) == 0 ||
174 			    lstmatch(search->arch, page->arch) == 0 ||
175 			    (search->argmode == ARG_NAME &&
176 			     rp->bits <= (int32_t)(NAME_SYN & NAME_MASK)))
177 				continue;
178 
179 			if (res == NULL) {
180 				cur = 1;
181 				break;
182 			}
183 			if (cur + 1 > maxres) {
184 				maxres += 1024;
185 				*res = mandoc_reallocarray(*res,
186 				    maxres, sizeof(**res));
187 			}
188 			mpage = *res + cur;
189 			mandoc_asprintf(&mpage->file, "%s/%s",
190 			    paths->paths[i], page->file + 1);
191 			if (access(chdir_status ? page->file + 1 :
192 			    mpage->file, R_OK) == -1) {
193 				warn("%s", mpage->file);
194 				warnx("outdated mandoc.db contains "
195 				    "bogus %s entry, run makewhatis %s",
196 				    page->file + 1, paths->paths[i]);
197 				free(mpage->file);
198 				free(rp);
199 				continue;
200 			}
201 			mpage->names = buildnames(page);
202 			mpage->output = buildoutput(outkey, page);
203 			mpage->ipath = i;
204 			mpage->bits = rp->bits;
205 			mpage->sec = *page->sect - '0';
206 			if (mpage->sec < 0 || mpage->sec > 9)
207 				mpage->sec = 10;
208 			mpage->form = *page->file;
209 			free(rp);
210 			cur++;
211 		}
212 		ohash_delete(htab);
213 		free(htab);
214 		dbm_close();
215 
216 		/*
217 		 * In man(1) mode, prefer matches in earlier trees
218 		 * over matches in later trees.
219 		 */
220 
221 		if (cur && search->firstmatch)
222 			break;
223 	}
224 	if (res != NULL)
225 		qsort(*res, cur, sizeof(struct manpage), manpage_compare);
226 	if (chdir_status && getcwd_status && chdir(buf) == -1)
227 		warn("%s", buf);
228 	exprfree(e);
229 	*sz = cur;
230 	return res != NULL || cur;
231 }
232 
233 /*
234  * Merge the results for the expression tree rooted at e
235  * into the the result list htab.
236  */
237 static struct ohash *
238 manmerge(struct expr *e, struct ohash *htab)
239 {
240 	switch (e->type) {
241 	case EXPR_TERM:
242 		return manmerge_term(e, htab);
243 	case EXPR_OR:
244 		return manmerge_or(e->child, htab);
245 	case EXPR_AND:
246 		return manmerge_and(e->child, htab);
247 	default:
248 		abort();
249 	}
250 }
251 
252 static struct ohash *
253 manmerge_term(struct expr *e, struct ohash *htab)
254 {
255 	struct dbm_res	 res, *rp;
256 	uint64_t	 ib;
257 	unsigned int	 slot;
258 	int		 im;
259 
260 	if (htab == NULL) {
261 		htab = mandoc_malloc(sizeof(*htab));
262 		mandoc_ohash_init(htab, 4, offsetof(struct dbm_res, page));
263 	}
264 
265 	for (im = 0, ib = 1; im < KEY_MAX; im++, ib <<= 1) {
266 		if ((e->bits & ib) == 0)
267 			continue;
268 
269 		switch (ib) {
270 		case TYPE_arch:
271 			dbm_page_byarch(&e->match);
272 			break;
273 		case TYPE_sec:
274 			dbm_page_bysect(&e->match);
275 			break;
276 		case TYPE_Nm:
277 			dbm_page_byname(&e->match);
278 			break;
279 		case TYPE_Nd:
280 			dbm_page_bydesc(&e->match);
281 			break;
282 		default:
283 			dbm_page_bymacro(im - 2, &e->match);
284 			break;
285 		}
286 
287 		/*
288 		 * When hashing for deduplication, use the unique
289 		 * page ID itself instead of a hash function;
290 		 * that is quite efficient.
291 		 */
292 
293 		for (;;) {
294 			res = dbm_page_next();
295 			if (res.page == -1)
296 				break;
297 			slot = ohash_lookup_memory(htab,
298 			    (char *)&res, sizeof(res.page), res.page);
299 			if ((rp = ohash_find(htab, slot)) != NULL) {
300 				rp->bits |= res.bits;
301 				continue;
302 			}
303 			rp = mandoc_malloc(sizeof(*rp));
304 			*rp = res;
305 			ohash_insert(htab, slot, rp);
306 		}
307 	}
308 	return htab;
309 }
310 
311 static struct ohash *
312 manmerge_or(struct expr *e, struct ohash *htab)
313 {
314 	while (e != NULL) {
315 		htab = manmerge(e, htab);
316 		e = e->next;
317 	}
318 	return htab;
319 }
320 
321 static struct ohash *
322 manmerge_and(struct expr *e, struct ohash *htab)
323 {
324 	struct ohash	*hand, *h1, *h2;
325 	struct dbm_res	*res;
326 	unsigned int	 slot1, slot2;
327 
328 	/* Evaluate the first term of the AND clause. */
329 
330 	hand = manmerge(e, NULL);
331 
332 	while ((e = e->next) != NULL) {
333 
334 		/* Evaluate the next term and prepare for ANDing. */
335 
336 		h2 = manmerge(e, NULL);
337 		if (ohash_entries(h2) < ohash_entries(hand)) {
338 			h1 = h2;
339 			h2 = hand;
340 		} else
341 			h1 = hand;
342 		hand = mandoc_malloc(sizeof(*hand));
343 		mandoc_ohash_init(hand, 4, offsetof(struct dbm_res, page));
344 
345 		/* Keep all pages that are in both result sets. */
346 
347 		for (res = ohash_first(h1, &slot1); res != NULL;
348 		    res = ohash_next(h1, &slot1)) {
349 			if (ohash_find(h2, ohash_lookup_memory(h2,
350 			    (char *)res, sizeof(res->page),
351 			    res->page)) == NULL)
352 				free(res);
353 			else
354 				ohash_insert(hand, ohash_lookup_memory(hand,
355 				    (char *)res, sizeof(res->page),
356 				    res->page), res);
357 		}
358 
359 		/* Discard the merged results. */
360 
361 		for (res = ohash_first(h2, &slot2); res != NULL;
362 		    res = ohash_next(h2, &slot2))
363 			free(res);
364 		ohash_delete(h2);
365 		free(h2);
366 		ohash_delete(h1);
367 		free(h1);
368 	}
369 
370 	/* Merge the result of the AND into htab. */
371 
372 	if (htab == NULL)
373 		return hand;
374 
375 	for (res = ohash_first(hand, &slot1); res != NULL;
376 	    res = ohash_next(hand, &slot1)) {
377 		slot2 = ohash_lookup_memory(htab,
378 		    (char *)res, sizeof(res->page), res->page);
379 		if (ohash_find(htab, slot2) == NULL)
380 			ohash_insert(htab, slot2, res);
381 		else
382 			free(res);
383 	}
384 
385 	/* Discard the merged result. */
386 
387 	ohash_delete(hand);
388 	free(hand);
389 	return htab;
390 }
391 
392 void
393 mansearch_free(struct manpage *res, size_t sz)
394 {
395 	size_t	 i;
396 
397 	for (i = 0; i < sz; i++) {
398 		free(res[i].file);
399 		free(res[i].names);
400 		free(res[i].output);
401 	}
402 	free(res);
403 }
404 
405 static int
406 manpage_compare(const void *vp1, const void *vp2)
407 {
408 	const struct manpage	*mp1, *mp2;
409 	const char		*cp1, *cp2;
410 	size_t			 sz1, sz2;
411 	int			 diff;
412 
413 	mp1 = vp1;
414 	mp2 = vp2;
415 	if ((diff = mp2->bits - mp1->bits) ||
416 	    (diff = mp1->sec - mp2->sec))
417 		return diff;
418 
419 	/* Fall back to alphabetic ordering of names. */
420 	sz1 = strcspn(mp1->names, "(");
421 	sz2 = strcspn(mp2->names, "(");
422 	if (sz1 < sz2)
423 		sz1 = sz2;
424 	if ((diff = strncasecmp(mp1->names, mp2->names, sz1)))
425 		return diff;
426 
427 	/* For identical names and sections, prefer arch-dependent. */
428 	cp1 = strchr(mp1->names + sz1, '/');
429 	cp2 = strchr(mp2->names + sz2, '/');
430 	return cp1 != NULL && cp2 != NULL ? strcasecmp(cp1, cp2) :
431 	    cp1 != NULL ? -1 : cp2 != NULL ? 1 : 0;
432 }
433 
434 static char *
435 buildnames(const struct dbm_page *page)
436 {
437 	char	*buf;
438 	size_t	 i, sz;
439 
440 	sz = lstlen(page->name, 2) + 1 + lstlen(page->sect, 2) +
441 	    (page->arch == NULL ? 0 : 1 + lstlen(page->arch, 2)) + 2;
442 	buf = mandoc_malloc(sz);
443 	i = 0;
444 	lstcat(buf, &i, page->name, ", ");
445 	buf[i++] = '(';
446 	lstcat(buf, &i, page->sect, ", ");
447 	if (page->arch != NULL) {
448 		buf[i++] = '/';
449 		lstcat(buf, &i, page->arch, ", ");
450 	}
451 	buf[i++] = ')';
452 	buf[i++] = '\0';
453 	assert(i == sz);
454 	return buf;
455 }
456 
457 /*
458  * Count the buffer space needed to print the NUL-terminated
459  * list of NUL-terminated strings, when printing sep separator
460  * characters between strings.
461  */
462 static size_t
463 lstlen(const char *cp, size_t sep)
464 {
465 	size_t	 sz;
466 
467 	for (sz = 0; *cp != '\0'; cp++) {
468 
469 		/* Skip names appearing only in the SYNOPSIS. */
470 		if (*cp <= (char)(NAME_SYN & NAME_MASK)) {
471 			while (*cp != '\0')
472 				cp++;
473 			continue;
474 		}
475 
476 		/* Skip name class markers. */
477 		if (*cp < ' ')
478 			cp++;
479 
480 		/* Print a separator before each but the first string. */
481 		if (sz)
482 			sz += sep;
483 
484 		/* Copy one string. */
485 		while (*cp != '\0') {
486 			sz++;
487 			cp++;
488 		}
489 	}
490 	return sz;
491 }
492 
493 /*
494  * Print the NUL-terminated list of NUL-terminated strings
495  * into the buffer, seperating strings with sep.
496  */
497 static void
498 lstcat(char *buf, size_t *i, const char *cp, const char *sep)
499 {
500 	const char	*s;
501 	size_t		 i_start;
502 
503 	for (i_start = *i; *cp != '\0'; cp++) {
504 
505 		/* Skip names appearing only in the SYNOPSIS. */
506 		if (*cp <= (char)(NAME_SYN & NAME_MASK)) {
507 			while (*cp != '\0')
508 				cp++;
509 			continue;
510 		}
511 
512 		/* Skip name class markers. */
513 		if (*cp < ' ')
514 			cp++;
515 
516 		/* Print a separator before each but the first string. */
517 		if (*i > i_start) {
518 			s = sep;
519 			while (*s != '\0')
520 				buf[(*i)++] = *s++;
521 		}
522 
523 		/* Copy one string. */
524 		while (*cp != '\0')
525 			buf[(*i)++] = *cp++;
526 	}
527 
528 }
529 
530 /*
531  * Return 1 if the string *want occurs in any of the strings
532  * in the NUL-terminated string list *have, or 0 otherwise.
533  * If either argument is NULL or empty, assume no filtering
534  * is desired and return 1.
535  */
536 static int
537 lstmatch(const char *want, const char *have)
538 {
539         if (want == NULL || have == NULL || *have == '\0')
540                 return 1;
541         while (*have != '\0') {
542                 if (strcasestr(have, want) != NULL)
543                         return 1;
544                 have = strchr(have, '\0') + 1;
545         }
546         return 0;
547 }
548 
549 /*
550  * Build a list of values taken by the macro im in the manual page.
551  */
552 static char *
553 buildoutput(size_t im, struct dbm_page *page)
554 {
555 	const char	*oldoutput, *sep, *input;
556 	char		*output, *newoutput, *value;
557 	size_t		 sz, i;
558 
559 	switch (im) {
560 	case KEY_Nd:
561 		return mandoc_strdup(page->desc);
562 	case KEY_Nm:
563 		input = page->name;
564 		break;
565 	case KEY_sec:
566 		input = page->sect;
567 		break;
568 	case KEY_arch:
569 		input = page->arch;
570 		if (input == NULL)
571 			input = "all\0";
572 		break;
573 	default:
574 		input = NULL;
575 		break;
576 	}
577 
578 	if (input != NULL) {
579 		sz = lstlen(input, 3) + 1;
580 		output = mandoc_malloc(sz);
581 		i = 0;
582 		lstcat(output, &i, input, " # ");
583 		output[i++] = '\0';
584 		assert(i == sz);
585 		return output;
586 	}
587 
588 	output = NULL;
589 	dbm_macro_bypage(im - 2, page->addr);
590 	while ((value = dbm_macro_next()) != NULL) {
591 		if (output == NULL) {
592 			oldoutput = "";
593 			sep = "";
594 		} else {
595 			oldoutput = output;
596 			sep = " # ";
597 		}
598 		mandoc_asprintf(&newoutput, "%s%s%s", oldoutput, sep, value);
599 		free(output);
600 		output = newoutput;
601 	}
602 	return output;
603 }
604 
605 /*
606  * Compile a set of string tokens into an expression.
607  * Tokens in "argv" are assumed to be individual expression atoms (e.g.,
608  * "(", "foo=bar", etc.).
609  */
610 static struct expr *
611 exprcomp(const struct mansearch *search, int argc, char *argv[], int *argi)
612 {
613 	struct expr	*parent, *child;
614 	int		 needterm, nested;
615 
616 	if ((nested = *argi) == argc)
617 		return NULL;
618 	needterm = 1;
619 	parent = child = NULL;
620 	while (*argi < argc) {
621 		if (strcmp(")", argv[*argi]) == 0) {
622 			if (needterm)
623 				warnx("missing term "
624 				    "before closing parenthesis");
625 			needterm = 0;
626 			if (nested)
627 				break;
628 			warnx("ignoring unmatched right parenthesis");
629 			++*argi;
630 			continue;
631 		}
632 		if (strcmp("-o", argv[*argi]) == 0) {
633 			if (needterm) {
634 				if (*argi > 0)
635 					warnx("ignoring -o after %s",
636 					    argv[*argi - 1]);
637 				else
638 					warnx("ignoring initial -o");
639 			}
640 			needterm = 1;
641 			++*argi;
642 			continue;
643 		}
644 		needterm = 0;
645 		if (child == NULL) {
646 			child = expr_and(search, argc, argv, argi);
647 			continue;
648 		}
649 		if (parent == NULL) {
650 			parent = mandoc_calloc(1, sizeof(*parent));
651 			parent->type = EXPR_OR;
652 			parent->next = NULL;
653 			parent->child = child;
654 		}
655 		child->next = expr_and(search, argc, argv, argi);
656 		child = child->next;
657 	}
658 	if (needterm && *argi)
659 		warnx("ignoring trailing %s", argv[*argi - 1]);
660 	return parent == NULL ? child : parent;
661 }
662 
663 static struct expr *
664 expr_and(const struct mansearch *search, int argc, char *argv[], int *argi)
665 {
666 	struct expr	*parent, *child;
667 	int		 needterm;
668 
669 	needterm = 1;
670 	parent = child = NULL;
671 	while (*argi < argc) {
672 		if (strcmp(")", argv[*argi]) == 0) {
673 			if (needterm)
674 				warnx("missing term "
675 				    "before closing parenthesis");
676 			needterm = 0;
677 			break;
678 		}
679 		if (strcmp("-o", argv[*argi]) == 0)
680 			break;
681 		if (strcmp("-a", argv[*argi]) == 0) {
682 			if (needterm) {
683 				if (*argi > 0)
684 					warnx("ignoring -a after %s",
685 					    argv[*argi - 1]);
686 				else
687 					warnx("ignoring initial -a");
688 			}
689 			needterm = 1;
690 			++*argi;
691 			continue;
692 		}
693 		if (needterm == 0)
694 			break;
695 		if (child == NULL) {
696 			child = exprterm(search, argc, argv, argi);
697 			if (child != NULL)
698 				needterm = 0;
699 			continue;
700 		}
701 		needterm = 0;
702 		if (parent == NULL) {
703 			parent = mandoc_calloc(1, sizeof(*parent));
704 			parent->type = EXPR_AND;
705 			parent->next = NULL;
706 			parent->child = child;
707 		}
708 		child->next = exprterm(search, argc, argv, argi);
709 		if (child->next != NULL) {
710 			child = child->next;
711 			needterm = 0;
712 		}
713 	}
714 	if (needterm && *argi)
715 		warnx("ignoring trailing %s", argv[*argi - 1]);
716 	return parent == NULL ? child : parent;
717 }
718 
719 static struct expr *
720 exprterm(const struct mansearch *search, int argc, char *argv[], int *argi)
721 {
722 	char		 errbuf[BUFSIZ];
723 	struct expr	*e;
724 	char		*key, *val;
725 	uint64_t	 iterbit;
726 	int		 cs, i, irc;
727 
728 	if (strcmp("(", argv[*argi]) == 0) {
729 		++*argi;
730 		e = exprcomp(search, argc, argv, argi);
731 		if (*argi < argc) {
732 			assert(strcmp(")", argv[*argi]) == 0);
733 			++*argi;
734 		} else
735 			warnx("unclosed parenthesis");
736 		return e;
737 	}
738 
739 	if (strcmp("-i", argv[*argi]) == 0 && *argi + 1 < argc) {
740 		cs = 0;
741 		++*argi;
742 	} else
743 		cs = 1;
744 
745 	e = mandoc_calloc(1, sizeof(*e));
746 	e->type = EXPR_TERM;
747 	e->bits = 0;
748 	e->next = NULL;
749 	e->child = NULL;
750 
751 	if (search->argmode == ARG_NAME) {
752 		e->bits = TYPE_Nm;
753 		e->match.type = DBM_EXACT;
754 		e->match.str = argv[(*argi)++];
755 		return e;
756 	}
757 
758 	/*
759 	 * Separate macro keys from search string.
760 	 * If needed, request regular expression handling.
761 	 */
762 
763 	if (search->argmode == ARG_WORD) {
764 		e->bits = TYPE_Nm;
765 		e->match.type = DBM_REGEX;
766 #if HAVE_REWB_BSD
767 		mandoc_asprintf(&val, "[[:<:]]%s[[:>:]]", argv[*argi]);
768 #elif HAVE_REWB_SYSV
769 		mandoc_asprintf(&val, "\\<%s\\>", argv[*argi]);
770 #else
771 		mandoc_asprintf(&val,
772 		    "(^|[^a-zA-Z01-9_])%s([^a-zA-Z01-9_]|$)", argv[*argi]);
773 #endif
774 		cs = 0;
775 	} else if ((val = strpbrk(argv[*argi], "=~")) == NULL) {
776 		e->bits = TYPE_Nm | TYPE_Nd;
777 		e->match.type = DBM_SUB;
778 		e->match.str = argv[*argi];
779 	} else {
780 		if (val == argv[*argi])
781 			e->bits = TYPE_Nm | TYPE_Nd;
782 		if (*val == '=') {
783 			e->match.type = DBM_SUB;
784 			e->match.str = val + 1;
785 		} else
786 			e->match.type = DBM_REGEX;
787 		*val++ = '\0';
788 		if (strstr(argv[*argi], "arch") != NULL)
789 			cs = 0;
790 	}
791 
792 	/* Compile regular expressions. */
793 
794 	if (e->match.type == DBM_REGEX) {
795 		e->match.re = mandoc_malloc(sizeof(*e->match.re));
796 		irc = regcomp(e->match.re, val,
797 		    REG_EXTENDED | REG_NOSUB | (cs ? 0 : REG_ICASE));
798 		if (irc) {
799 			regerror(irc, e->match.re, errbuf, sizeof(errbuf));
800 			warnx("regcomp /%s/: %s", val, errbuf);
801 		}
802 		if (search->argmode == ARG_WORD)
803 			free(val);
804 		if (irc) {
805 			free(e->match.re);
806 			free(e);
807 			++*argi;
808 			return NULL;
809 		}
810 	}
811 
812 	if (e->bits) {
813 		++*argi;
814 		return e;
815 	}
816 
817 	/*
818 	 * Parse out all possible fields.
819 	 * If the field doesn't resolve, bail.
820 	 */
821 
822 	while (NULL != (key = strsep(&argv[*argi], ","))) {
823 		if ('\0' == *key)
824 			continue;
825 		for (i = 0, iterbit = 1; i < KEY_MAX; i++, iterbit <<= 1) {
826 			if (0 == strcasecmp(key, mansearch_keynames[i])) {
827 				e->bits |= iterbit;
828 				break;
829 			}
830 		}
831 		if (i == KEY_MAX) {
832 			if (strcasecmp(key, "any"))
833 				warnx("treating unknown key "
834 				    "\"%s\" as \"any\"", key);
835 			e->bits |= ~0ULL;
836 		}
837 	}
838 
839 	++*argi;
840 	return e;
841 }
842 
843 static void
844 exprfree(struct expr *e)
845 {
846 	if (e->next != NULL)
847 		exprfree(e->next);
848 	if (e->child != NULL)
849 		exprfree(e->child);
850 	free(e);
851 }
852