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