mansearch.c revision 1.44 
1/*	$OpenBSD: mansearch.c,v 1.44 2015/04/01 12:48:00 schwarze Exp $ */
2/*
3 * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
4 * Copyright (c) 2013, 2014, 2015 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
19#include <sys/mman.h>
20#include <sys/types.h>
21
22#include <assert.h>
23#include <errno.h>
24#include <fcntl.h>
25#include <getopt.h>
26#include <glob.h>
27#include <limits.h>
28#include <regex.h>
29#include <stdio.h>
30#include <stdint.h>
31#include <stddef.h>
32#include <stdlib.h>
33#include <string.h>
34#include <unistd.h>
35
36#include <ohash.h>
37#include <sqlite3.h>
38
39#include "mandoc.h"
40#include "mandoc_aux.h"
41#include "manconf.h"
42#include "mansearch.h"
43
44extern int mansearch_keymax;
45extern const char *const mansearch_keynames[];
46
47#define	SQL_BIND_TEXT(_db, _s, _i, _v) \
48	do { if (SQLITE_OK != sqlite3_bind_text \
49		((_s), (_i)++, (_v), -1, SQLITE_STATIC)) \
50		fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
51	} while (0)
52#define	SQL_BIND_INT64(_db, _s, _i, _v) \
53	do { if (SQLITE_OK != sqlite3_bind_int64 \
54		((_s), (_i)++, (_v))) \
55		fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
56	} while (0)
57#define	SQL_BIND_BLOB(_db, _s, _i, _v) \
58	do { if (SQLITE_OK != sqlite3_bind_blob \
59		((_s), (_i)++, (&_v), sizeof(_v), SQLITE_STATIC)) \
60		fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
61	} while (0)
62
63struct	expr {
64	regex_t		 regexp;  /* compiled regexp, if applicable */
65	const char	*substr;  /* to search for, if applicable */
66	struct expr	*next;    /* next in sequence */
67	uint64_t	 bits;    /* type-mask */
68	int		 equal;   /* equality, not subsring match */
69	int		 open;    /* opening parentheses before */
70	int		 and;	  /* logical AND before */
71	int		 close;   /* closing parentheses after */
72};
73
74struct	match {
75	uint64_t	 pageid; /* identifier in database */
76	uint64_t	 bits; /* name type mask */
77	char		*desc; /* manual page description */
78	int		 form; /* bit field: formatted, zipped? */
79};
80
81static	void		 buildnames(const struct mansearch *,
82				struct manpage *, sqlite3 *,
83				sqlite3_stmt *, uint64_t,
84				const char *, int form);
85static	char		*buildoutput(sqlite3 *, sqlite3_stmt *,
86				 uint64_t, uint64_t);
87static	void		*hash_alloc(size_t, void *);
88static	void		 hash_free(void *, void *);
89static	void		*hash_calloc(size_t, size_t, void *);
90static	struct expr	*exprcomp(const struct mansearch *,
91				int, char *[]);
92static	void		 exprfree(struct expr *);
93static	struct expr	*exprterm(const struct mansearch *, char *, int);
94static	int		 manpage_compare(const void *, const void *);
95static	void		 sql_append(char **sql, size_t *sz,
96				const char *newstr, int count);
97static	void		 sql_match(sqlite3_context *context,
98				int argc, sqlite3_value **argv);
99static	void		 sql_regexp(sqlite3_context *context,
100				int argc, sqlite3_value **argv);
101static	char		*sql_statement(const struct expr *);
102
103
104int
105mansearch_setup(int start)
106{
107	static void	*pagecache;
108	int		 c;
109
110#define	PC_PAGESIZE	1280
111#define	PC_NUMPAGES	256
112
113	if (start) {
114		if (NULL != pagecache) {
115			fprintf(stderr, "pagecache already enabled\n");
116			return((int)MANDOCLEVEL_BADARG);
117		}
118
119		pagecache = mmap(NULL, PC_PAGESIZE * PC_NUMPAGES,
120		    PROT_READ | PROT_WRITE,
121		    MAP_SHARED | MAP_ANON, -1, 0);
122
123		if (MAP_FAILED == pagecache) {
124			perror("mmap");
125			pagecache = NULL;
126			return((int)MANDOCLEVEL_SYSERR);
127		}
128
129		c = sqlite3_config(SQLITE_CONFIG_PAGECACHE,
130		    pagecache, PC_PAGESIZE, PC_NUMPAGES);
131
132		if (SQLITE_OK == c)
133			return((int)MANDOCLEVEL_OK);
134
135		fprintf(stderr, "pagecache: %s\n", sqlite3_errstr(c));
136
137	} else if (NULL == pagecache) {
138		fprintf(stderr, "pagecache missing\n");
139		return((int)MANDOCLEVEL_BADARG);
140	}
141
142	if (-1 == munmap(pagecache, PC_PAGESIZE * PC_NUMPAGES)) {
143		perror("munmap");
144		pagecache = NULL;
145		return((int)MANDOCLEVEL_SYSERR);
146	}
147
148	pagecache = NULL;
149	return((int)MANDOCLEVEL_OK);
150}
151
152int
153mansearch(const struct mansearch *search,
154		const struct manpaths *paths,
155		int argc, char *argv[],
156		struct manpage **res, size_t *sz)
157{
158	int64_t		 pageid;
159	uint64_t	 outbit, iterbit;
160	char		 buf[PATH_MAX];
161	char		*sql;
162	struct manpage	*mpage;
163	struct expr	*e, *ep;
164	sqlite3		*db;
165	sqlite3_stmt	*s, *s2;
166	struct match	*mp;
167	struct ohash_info info;
168	struct ohash	 htab;
169	unsigned int	 idx;
170	size_t		 i, j, cur, maxres;
171	int		 c, chdir_status, getcwd_status, indexbit;
172
173	if (argc == 0 || (e = exprcomp(search, argc, argv)) == NULL) {
174		*sz = 0;
175		return(0);
176	}
177
178	info.calloc = hash_calloc;
179	info.alloc = hash_alloc;
180	info.free = hash_free;
181	info.key_offset = offsetof(struct match, pageid);
182
183	cur = maxres = 0;
184	*res = NULL;
185
186	if (NULL != search->outkey) {
187		outbit = TYPE_Nd;
188		for (indexbit = 0, iterbit = 1;
189		     indexbit < mansearch_keymax;
190		     indexbit++, iterbit <<= 1) {
191			if (0 == strcasecmp(search->outkey,
192			    mansearch_keynames[indexbit])) {
193				outbit = iterbit;
194				break;
195			}
196		}
197	} else
198		outbit = 0;
199
200	/*
201	 * Remember the original working directory, if possible.
202	 * This will be needed if the second or a later directory
203	 * is given as a relative path.
204	 * Do not error out if the current directory is not
205	 * searchable: Maybe it won't be needed after all.
206	 */
207
208	if (getcwd(buf, PATH_MAX) == NULL) {
209		getcwd_status = 0;
210		(void)strlcpy(buf, strerror(errno), sizeof(buf));
211	} else
212		getcwd_status = 1;
213
214	sql = sql_statement(e);
215
216	/*
217	 * Loop over the directories (containing databases) for us to
218	 * search.
219	 * Don't let missing/bad databases/directories phase us.
220	 * In each, try to open the resident database and, if it opens,
221	 * scan it for our match expression.
222	 */
223
224	chdir_status = 0;
225	for (i = 0; i < paths->sz; i++) {
226		if (chdir_status && paths->paths[i][0] != '/') {
227			if ( ! getcwd_status) {
228				fprintf(stderr, "%s: getcwd: %s\n",
229				    paths->paths[i], buf);
230				continue;
231			} else if (chdir(buf) == -1) {
232				perror(buf);
233				continue;
234			}
235		}
236		if (chdir(paths->paths[i]) == -1) {
237			perror(paths->paths[i]);
238			continue;
239		}
240		chdir_status = 1;
241
242		c = sqlite3_open_v2(MANDOC_DB, &db,
243		    SQLITE_OPEN_READONLY, NULL);
244
245		if (SQLITE_OK != c) {
246			fprintf(stderr, "%s/%s: %s\n",
247			    paths->paths[i], MANDOC_DB, strerror(errno));
248			sqlite3_close(db);
249			continue;
250		}
251
252		/*
253		 * Define the SQL functions for substring
254		 * and regular expression matching.
255		 */
256
257		c = sqlite3_create_function(db, "match", 2,
258		    SQLITE_UTF8 | SQLITE_DETERMINISTIC,
259		    NULL, sql_match, NULL, NULL);
260		assert(SQLITE_OK == c);
261		c = sqlite3_create_function(db, "regexp", 2,
262		    SQLITE_UTF8 | SQLITE_DETERMINISTIC,
263		    NULL, sql_regexp, NULL, NULL);
264		assert(SQLITE_OK == c);
265
266		j = 1;
267		c = sqlite3_prepare_v2(db, sql, -1, &s, NULL);
268		if (SQLITE_OK != c)
269			fprintf(stderr, "%s\n", sqlite3_errmsg(db));
270
271		for (ep = e; NULL != ep; ep = ep->next) {
272			if (NULL == ep->substr) {
273				SQL_BIND_BLOB(db, s, j, ep->regexp);
274			} else
275				SQL_BIND_TEXT(db, s, j, ep->substr);
276			if (0 == ((TYPE_Nd | TYPE_Nm) & ep->bits))
277				SQL_BIND_INT64(db, s, j, ep->bits);
278		}
279
280		memset(&htab, 0, sizeof(struct ohash));
281		ohash_init(&htab, 4, &info);
282
283		/*
284		 * Hash each entry on its [unique] document identifier.
285		 * This is a uint64_t.
286		 * Instead of using a hash function, simply convert the
287		 * uint64_t to a uint32_t, the hash value's type.
288		 * This gives good performance and preserves the
289		 * distribution of buckets in the table.
290		 */
291		while (SQLITE_ROW == (c = sqlite3_step(s))) {
292			pageid = sqlite3_column_int64(s, 2);
293			idx = ohash_lookup_memory(&htab,
294			    (char *)&pageid, sizeof(uint64_t),
295			    (uint32_t)pageid);
296
297			if (NULL != ohash_find(&htab, idx))
298				continue;
299
300			mp = mandoc_calloc(1, sizeof(struct match));
301			mp->pageid = pageid;
302			mp->form = sqlite3_column_int(s, 1);
303			mp->bits = sqlite3_column_int64(s, 3);
304			if (TYPE_Nd == outbit)
305				mp->desc = mandoc_strdup((const char *)
306				    sqlite3_column_text(s, 0));
307			ohash_insert(&htab, idx, mp);
308		}
309
310		if (SQLITE_DONE != c)
311			fprintf(stderr, "%s\n", sqlite3_errmsg(db));
312
313		sqlite3_finalize(s);
314
315		c = sqlite3_prepare_v2(db,
316		    "SELECT sec, arch, name, pageid FROM mlinks "
317		    "WHERE pageid=? ORDER BY sec, arch, name",
318		    -1, &s, NULL);
319		if (SQLITE_OK != c)
320			fprintf(stderr, "%s\n", sqlite3_errmsg(db));
321
322		c = sqlite3_prepare_v2(db,
323		    "SELECT bits, key, pageid FROM keys "
324		    "WHERE pageid=? AND bits & ?",
325		    -1, &s2, NULL);
326		if (SQLITE_OK != c)
327			fprintf(stderr, "%s\n", sqlite3_errmsg(db));
328
329		for (mp = ohash_first(&htab, &idx);
330				NULL != mp;
331				mp = ohash_next(&htab, &idx)) {
332			if (cur + 1 > maxres) {
333				maxres += 1024;
334				*res = mandoc_reallocarray(*res,
335				    maxres, sizeof(struct manpage));
336			}
337			mpage = *res + cur;
338			mpage->ipath = i;
339			mpage->bits = mp->bits;
340			mpage->sec = 10;
341			mpage->form = mp->form;
342			buildnames(search, mpage, db, s, mp->pageid,
343			    paths->paths[i], mp->form);
344			if (mpage->names != NULL) {
345				mpage->output = TYPE_Nd & outbit ?
346				    mp->desc : outbit ?
347				    buildoutput(db, s2, mp->pageid, outbit) :
348				    NULL;
349				cur++;
350			}
351			free(mp);
352		}
353
354		sqlite3_finalize(s);
355		sqlite3_finalize(s2);
356		sqlite3_close(db);
357		ohash_delete(&htab);
358
359		/*
360		 * In man(1) mode, prefer matches in earlier trees
361		 * over matches in later trees.
362		 */
363
364		if (cur && search->firstmatch)
365			break;
366	}
367	qsort(*res, cur, sizeof(struct manpage), manpage_compare);
368	if (chdir_status && getcwd_status && chdir(buf) == -1)
369		perror(buf);
370	exprfree(e);
371	free(sql);
372	*sz = cur;
373	return(1);
374}
375
376void
377mansearch_free(struct manpage *res, size_t sz)
378{
379	size_t	 i;
380
381	for (i = 0; i < sz; i++) {
382		free(res[i].file);
383		free(res[i].names);
384		free(res[i].output);
385	}
386	free(res);
387}
388
389static int
390manpage_compare(const void *vp1, const void *vp2)
391{
392	const struct manpage	*mp1, *mp2;
393	int			 diff;
394
395	mp1 = vp1;
396	mp2 = vp2;
397	return(	(diff = mp2->bits - mp1->bits) ? diff :
398		(diff = mp1->sec - mp2->sec) ? diff :
399		strcasecmp(mp1->names, mp2->names));
400}
401
402static void
403buildnames(const struct mansearch *search, struct manpage *mpage,
404		sqlite3 *db, sqlite3_stmt *s,
405		uint64_t pageid, const char *path, int form)
406{
407	glob_t		 globinfo;
408	char		*firstname, *newnames, *prevsec, *prevarch;
409	const char	*oldnames, *sep1, *name, *sec, *sep2, *arch, *fsec;
410	size_t		 i;
411	int		 c, globres;
412
413	mpage->file = NULL;
414	mpage->names = NULL;
415	firstname = prevsec = prevarch = NULL;
416	i = 1;
417	SQL_BIND_INT64(db, s, i, pageid);
418	while (SQLITE_ROW == (c = sqlite3_step(s))) {
419
420		/* Decide whether we already have some names. */
421
422		if (NULL == mpage->names) {
423			oldnames = "";
424			sep1 = "";
425		} else {
426			oldnames = mpage->names;
427			sep1 = ", ";
428		}
429
430		/* Fetch the next name, rejecting sec/arch mismatches. */
431
432		sec = (const char *)sqlite3_column_text(s, 0);
433		if (search->sec != NULL && strcasecmp(sec, search->sec))
434			continue;
435		arch = (const char *)sqlite3_column_text(s, 1);
436		if (search->arch != NULL && *arch != '\0' &&
437		    strcasecmp(arch, search->arch))
438			continue;
439		name = (const char *)sqlite3_column_text(s, 2);
440
441		/* Remember the first section found. */
442
443		if (9 < mpage->sec && '1' <= *sec && '9' >= *sec)
444			mpage->sec = (*sec - '1') + 1;
445
446		/* If the section changed, append the old one. */
447
448		if (NULL != prevsec &&
449		    (strcmp(sec, prevsec) ||
450		     strcmp(arch, prevarch))) {
451			sep2 = '\0' == *prevarch ? "" : "/";
452			mandoc_asprintf(&newnames, "%s(%s%s%s)",
453			    oldnames, prevsec, sep2, prevarch);
454			free(mpage->names);
455			oldnames = mpage->names = newnames;
456			free(prevsec);
457			free(prevarch);
458			prevsec = prevarch = NULL;
459		}
460
461		/* Save the new section, to append it later. */
462
463		if (NULL == prevsec) {
464			prevsec = mandoc_strdup(sec);
465			prevarch = mandoc_strdup(arch);
466		}
467
468		/* Append the new name. */
469
470		mandoc_asprintf(&newnames, "%s%s%s",
471		    oldnames, sep1, name);
472		free(mpage->names);
473		mpage->names = newnames;
474
475		/* Also save the first file name encountered. */
476
477		if (mpage->file != NULL)
478			continue;
479
480		if (form & FORM_SRC) {
481			sep1 = "man";
482			fsec = sec;
483		} else {
484			sep1 = "cat";
485			fsec = "0";
486		}
487		sep2 = *arch == '\0' ? "" : "/";
488		mandoc_asprintf(&mpage->file, "%s/%s%s%s%s/%s.%s",
489		    path, sep1, sec, sep2, arch, name, fsec);
490		if (access(mpage->file, R_OK) != -1)
491			continue;
492
493		/* Handle unusual file name extensions. */
494
495		if (firstname == NULL)
496			firstname = mpage->file;
497		else
498			free(mpage->file);
499		mandoc_asprintf(&mpage->file, "%s/%s%s%s%s/%s.*",
500		    path, sep1, sec, sep2, arch, name);
501		globres = glob(mpage->file, 0, NULL, &globinfo);
502		free(mpage->file);
503		mpage->file = globres ? NULL :
504		    mandoc_strdup(*globinfo.gl_pathv);
505		globfree(&globinfo);
506	}
507	if (c != SQLITE_DONE)
508		fprintf(stderr, "%s\n", sqlite3_errmsg(db));
509	sqlite3_reset(s);
510
511	/* If none of the files is usable, use the first name. */
512
513	if (mpage->file == NULL)
514		mpage->file = firstname;
515	else if (mpage->file != firstname)
516		free(firstname);
517
518	/* Append one final section to the names. */
519
520	if (prevsec != NULL) {
521		sep2 = *prevarch == '\0' ? "" : "/";
522		mandoc_asprintf(&newnames, "%s(%s%s%s)",
523		    mpage->names, prevsec, sep2, prevarch);
524		free(mpage->names);
525		mpage->names = newnames;
526		free(prevsec);
527		free(prevarch);
528	}
529}
530
531static char *
532buildoutput(sqlite3 *db, sqlite3_stmt *s, uint64_t pageid, uint64_t outbit)
533{
534	char		*output, *newoutput;
535	const char	*oldoutput, *sep1, *data;
536	size_t		 i;
537	int		 c;
538
539	output = NULL;
540	i = 1;
541	SQL_BIND_INT64(db, s, i, pageid);
542	SQL_BIND_INT64(db, s, i, outbit);
543	while (SQLITE_ROW == (c = sqlite3_step(s))) {
544		if (NULL == output) {
545			oldoutput = "";
546			sep1 = "";
547		} else {
548			oldoutput = output;
549			sep1 = " # ";
550		}
551		data = (const char *)sqlite3_column_text(s, 1);
552		mandoc_asprintf(&newoutput, "%s%s%s",
553		    oldoutput, sep1, data);
554		free(output);
555		output = newoutput;
556	}
557	if (SQLITE_DONE != c)
558		fprintf(stderr, "%s\n", sqlite3_errmsg(db));
559	sqlite3_reset(s);
560	return(output);
561}
562
563/*
564 * Implement substring match as an application-defined SQL function.
565 * Using the SQL LIKE or GLOB operators instead would be a bad idea
566 * because that would require escaping metacharacters in the string
567 * being searched for.
568 */
569static void
570sql_match(sqlite3_context *context, int argc, sqlite3_value **argv)
571{
572
573	assert(2 == argc);
574	sqlite3_result_int(context, NULL != strcasestr(
575	    (const char *)sqlite3_value_text(argv[1]),
576	    (const char *)sqlite3_value_text(argv[0])));
577}
578
579/*
580 * Implement regular expression match
581 * as an application-defined SQL function.
582 */
583static void
584sql_regexp(sqlite3_context *context, int argc, sqlite3_value **argv)
585{
586
587	assert(2 == argc);
588	sqlite3_result_int(context, !regexec(
589	    (regex_t *)sqlite3_value_blob(argv[0]),
590	    (const char *)sqlite3_value_text(argv[1]),
591	    0, NULL, 0));
592}
593
594static void
595sql_append(char **sql, size_t *sz, const char *newstr, int count)
596{
597	size_t		 newsz;
598
599	newsz = 1 < count ? (size_t)count : strlen(newstr);
600	*sql = mandoc_realloc(*sql, *sz + newsz + 1);
601	if (1 < count)
602		memset(*sql + *sz, *newstr, (size_t)count);
603	else
604		memcpy(*sql + *sz, newstr, newsz);
605	*sz += newsz;
606	(*sql)[*sz] = '\0';
607}
608
609/*
610 * Prepare the search SQL statement.
611 */
612static char *
613sql_statement(const struct expr *e)
614{
615	char		*sql;
616	size_t		 sz;
617	int		 needop;
618
619	sql = mandoc_strdup(e->equal ?
620	    "SELECT desc, form, pageid, bits "
621		"FROM mpages NATURAL JOIN names WHERE " :
622	    "SELECT desc, form, pageid, 0 FROM mpages WHERE ");
623	sz = strlen(sql);
624
625	for (needop = 0; NULL != e; e = e->next) {
626		if (e->and)
627			sql_append(&sql, &sz, " AND ", 1);
628		else if (needop)
629			sql_append(&sql, &sz, " OR ", 1);
630		if (e->open)
631			sql_append(&sql, &sz, "(", e->open);
632		sql_append(&sql, &sz,
633		    TYPE_Nd & e->bits
634		    ? (NULL == e->substr
635			? "desc REGEXP ?"
636			: "desc MATCH ?")
637		    : TYPE_Nm == e->bits
638		    ? (NULL == e->substr
639			? "pageid IN (SELECT pageid FROM names "
640			  "WHERE name REGEXP ?)"
641			: e->equal
642			? "name = ? "
643			: "pageid IN (SELECT pageid FROM names "
644			  "WHERE name MATCH ?)")
645		    : (NULL == e->substr
646			? "pageid IN (SELECT pageid FROM keys "
647			  "WHERE key REGEXP ? AND bits & ?)"
648			: "pageid IN (SELECT pageid FROM keys "
649			  "WHERE key MATCH ? AND bits & ?)"), 1);
650		if (e->close)
651			sql_append(&sql, &sz, ")", e->close);
652		needop = 1;
653	}
654
655	return(sql);
656}
657
658/*
659 * Compile a set of string tokens into an expression.
660 * Tokens in "argv" are assumed to be individual expression atoms (e.g.,
661 * "(", "foo=bar", etc.).
662 */
663static struct expr *
664exprcomp(const struct mansearch *search, int argc, char *argv[])
665{
666	uint64_t	 mask;
667	int		 i, toopen, logic, igncase, toclose;
668	struct expr	*first, *prev, *cur, *next;
669
670	first = cur = NULL;
671	logic = igncase = toopen = toclose = 0;
672
673	for (i = 0; i < argc; i++) {
674		if (0 == strcmp("(", argv[i])) {
675			if (igncase)
676				goto fail;
677			toopen++;
678			toclose++;
679			continue;
680		} else if (0 == strcmp(")", argv[i])) {
681			if (toopen || logic || igncase || NULL == cur)
682				goto fail;
683			cur->close++;
684			if (0 > --toclose)
685				goto fail;
686			continue;
687		} else if (0 == strcmp("-a", argv[i])) {
688			if (toopen || logic || igncase || NULL == cur)
689				goto fail;
690			logic = 1;
691			continue;
692		} else if (0 == strcmp("-o", argv[i])) {
693			if (toopen || logic || igncase || NULL == cur)
694				goto fail;
695			logic = 2;
696			continue;
697		} else if (0 == strcmp("-i", argv[i])) {
698			if (igncase)
699				goto fail;
700			igncase = 1;
701			continue;
702		}
703		next = exprterm(search, argv[i], !igncase);
704		if (NULL == next)
705			goto fail;
706		if (NULL == first)
707			first = next;
708		else
709			cur->next = next;
710		prev = cur = next;
711
712		/*
713		 * Searching for descriptions must be split out
714		 * because they are stored in the mpages table,
715		 * not in the keys table.
716		 */
717
718		for (mask = TYPE_Nm; mask <= TYPE_Nd; mask <<= 1) {
719			if (mask & cur->bits && ~mask & cur->bits) {
720				next = mandoc_calloc(1,
721				    sizeof(struct expr));
722				memcpy(next, cur, sizeof(struct expr));
723				prev->open = 1;
724				cur->bits = mask;
725				cur->next = next;
726				cur = next;
727				cur->bits &= ~mask;
728			}
729		}
730		prev->and = (1 == logic);
731		prev->open += toopen;
732		if (cur != prev)
733			cur->close = 1;
734
735		toopen = logic = igncase = 0;
736	}
737	if ( ! (toopen || logic || igncase || toclose))
738		return(first);
739
740fail:
741	if (NULL != first)
742		exprfree(first);
743	return(NULL);
744}
745
746static struct expr *
747exprterm(const struct mansearch *search, char *buf, int cs)
748{
749	char		 errbuf[BUFSIZ];
750	struct expr	*e;
751	char		*key, *val;
752	uint64_t	 iterbit;
753	int		 i, irc;
754
755	if ('\0' == *buf)
756		return(NULL);
757
758	e = mandoc_calloc(1, sizeof(struct expr));
759
760	if (search->argmode == ARG_NAME) {
761		e->bits = TYPE_Nm;
762		e->substr = buf;
763		e->equal = 1;
764		return(e);
765	}
766
767	/*
768	 * Separate macro keys from search string.
769	 * If needed, request regular expression handling
770	 * by setting e->substr to NULL.
771	 */
772
773	if (search->argmode == ARG_WORD) {
774		e->bits = TYPE_Nm;
775		e->substr = NULL;
776		mandoc_asprintf(&val, "[[:<:]]%s[[:>:]]", buf);
777		cs = 0;
778	} else if ((val = strpbrk(buf, "=~")) == NULL) {
779		e->bits = TYPE_Nm | TYPE_Nd;
780		e->substr = buf;
781	} else {
782		if (val == buf)
783			e->bits = TYPE_Nm | TYPE_Nd;
784		if ('=' == *val)
785			e->substr = val + 1;
786		*val++ = '\0';
787		if (NULL != strstr(buf, "arch"))
788			cs = 0;
789	}
790
791	/* Compile regular expressions. */
792
793	if (NULL == e->substr) {
794		irc = regcomp(&e->regexp, val,
795		    REG_EXTENDED | REG_NOSUB | (cs ? 0 : REG_ICASE));
796		if (search->argmode == ARG_WORD)
797			free(val);
798		if (irc) {
799			regerror(irc, &e->regexp, errbuf, sizeof(errbuf));
800			fprintf(stderr, "regcomp: %s\n", errbuf);
801			free(e);
802			return(NULL);
803		}
804	}
805
806	if (e->bits)
807		return(e);
808
809	/*
810	 * Parse out all possible fields.
811	 * If the field doesn't resolve, bail.
812	 */
813
814	while (NULL != (key = strsep(&buf, ","))) {
815		if ('\0' == *key)
816			continue;
817		for (i = 0, iterbit = 1;
818		     i < mansearch_keymax;
819		     i++, iterbit <<= 1) {
820			if (0 == strcasecmp(key,
821			    mansearch_keynames[i])) {
822				e->bits |= iterbit;
823				break;
824			}
825		}
826		if (i == mansearch_keymax) {
827			if (strcasecmp(key, "any")) {
828				free(e);
829				return(NULL);
830			}
831			e->bits |= ~0ULL;
832		}
833	}
834
835	return(e);
836}
837
838static void
839exprfree(struct expr *p)
840{
841	struct expr	*pp;
842
843	while (NULL != p) {
844		pp = p->next;
845		free(p);
846		p = pp;
847	}
848}
849
850static void *
851hash_calloc(size_t nmemb, size_t sz, void *arg)
852{
853
854	return(mandoc_calloc(nmemb, sz));
855}
856
857static void *
858hash_alloc(size_t sz, void *arg)
859{
860
861	return(mandoc_malloc(sz));
862}
863
864static void
865hash_free(void *p, void *arg)
866{
867
868	free(p);
869}
870