Annotation of src/usr.bin/mandoc/mansearch.c, Revision 1.11
1.11 ! schwarze 1: /* $Id: mansearch.c,v 1.10 2014/01/06 03:52:05 schwarze Exp $ */
1.1 schwarze 2: /*
3: * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
1.4 schwarze 4: * Copyright (c) 2013, 2014 Ingo Schwarze <schwarze@openbsd.org>
1.1 schwarze 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 AUTHOR DISCLAIMS ALL WARRANTIES
11: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR 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 <assert.h>
19: #include <fcntl.h>
20: #include <getopt.h>
21: #include <limits.h>
22: #include <regex.h>
23: #include <stdio.h>
24: #include <stdint.h>
25: #include <stddef.h>
26: #include <stdlib.h>
27: #include <string.h>
28: #include <unistd.h>
29:
30: #include <ohash.h>
31: #include <sqlite3.h>
32:
33: #include "mandoc.h"
34: #include "manpath.h"
35: #include "mansearch.h"
36:
1.11 ! schwarze 37: extern int mansearch_keymax;
! 38: extern const char *const mansearch_keynames[];
! 39:
1.1 schwarze 40: #define SQL_BIND_TEXT(_db, _s, _i, _v) \
41: do { if (SQLITE_OK != sqlite3_bind_text \
42: ((_s), (_i)++, (_v), -1, SQLITE_STATIC)) \
43: fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
44: } while (0)
45: #define SQL_BIND_INT64(_db, _s, _i, _v) \
46: do { if (SQLITE_OK != sqlite3_bind_int64 \
47: ((_s), (_i)++, (_v))) \
48: fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
49: } while (0)
50: #define SQL_BIND_BLOB(_db, _s, _i, _v) \
51: do { if (SQLITE_OK != sqlite3_bind_blob \
52: ((_s), (_i)++, (&_v), sizeof(_v), SQLITE_STATIC)) \
53: fprintf(stderr, "%s\n", sqlite3_errmsg((_db))); \
54: } while (0)
55:
56: struct expr {
57: uint64_t bits; /* type-mask */
58: const char *substr; /* to search for, if applicable */
59: regex_t regexp; /* compiled regexp, if applicable */
1.4 schwarze 60: int open; /* opening parentheses before */
61: int and; /* logical AND before */
62: int close; /* closing parentheses after */
1.1 schwarze 63: struct expr *next; /* next in sequence */
64: };
65:
66: struct match {
67: uint64_t id; /* identifier in database */
68: int form; /* 0 == catpage */
69: };
70:
1.8 schwarze 71: static void buildnames(struct manpage *, sqlite3 *,
1.10 schwarze 72: sqlite3_stmt *, uint64_t,
73: const char *, int form);
1.3 schwarze 74: static char *buildoutput(sqlite3 *, sqlite3_stmt *,
75: uint64_t, uint64_t);
1.1 schwarze 76: static void *hash_alloc(size_t, void *);
77: static void hash_free(void *, size_t, void *);
78: static void *hash_halloc(size_t, void *);
79: static struct expr *exprcomp(const struct mansearch *,
80: int, char *[]);
81: static void exprfree(struct expr *);
1.6 schwarze 82: static struct expr *exprspec(struct expr *, uint64_t,
83: const char *, const char *);
1.1 schwarze 84: static struct expr *exprterm(const struct mansearch *, char *, int);
1.4 schwarze 85: static void sql_append(char **sql, size_t *sz,
86: const char *newstr, int count);
1.1 schwarze 87: static void sql_match(sqlite3_context *context,
88: int argc, sqlite3_value **argv);
89: static void sql_regexp(sqlite3_context *context,
90: int argc, sqlite3_value **argv);
1.6 schwarze 91: static char *sql_statement(const struct expr *);
1.1 schwarze 92:
93: int
94: mansearch(const struct mansearch *search,
1.3 schwarze 95: const struct manpaths *paths,
96: int argc, char *argv[],
97: const char *outkey,
1.1 schwarze 98: struct manpage **res, size_t *sz)
99: {
1.11 ! schwarze 100: int fd, rc, c, indexbit;
1.1 schwarze 101: int64_t id;
1.11 ! schwarze 102: uint64_t outbit, iterbit;
1.1 schwarze 103: char buf[PATH_MAX];
1.2 schwarze 104: char *sql;
1.1 schwarze 105: struct manpage *mpage;
106: struct expr *e, *ep;
107: sqlite3 *db;
1.3 schwarze 108: sqlite3_stmt *s, *s2;
1.1 schwarze 109: struct match *mp;
110: struct ohash_info info;
111: struct ohash htab;
112: unsigned int idx;
113: size_t i, j, cur, maxres;
114:
115: memset(&info, 0, sizeof(struct ohash_info));
116:
117: info.halloc = hash_halloc;
118: info.alloc = hash_alloc;
119: info.hfree = hash_free;
120: info.key_offset = offsetof(struct match, id);
121:
122: *sz = cur = maxres = 0;
123: sql = NULL;
124: *res = NULL;
125: fd = -1;
126: e = NULL;
127: rc = 0;
128:
129: if (0 == argc)
130: goto out;
131: if (NULL == (e = exprcomp(search, argc, argv)))
132: goto out;
133:
1.3 schwarze 134: outbit = 0;
135: if (NULL != outkey) {
1.11 ! schwarze 136: for (indexbit = 0, iterbit = 1;
! 137: indexbit < mansearch_keymax;
! 138: indexbit++, iterbit <<= 1) {
! 139: if (0 == strcasecmp(outkey,
! 140: mansearch_keynames[indexbit])) {
! 141: outbit = iterbit;
1.3 schwarze 142: break;
143: }
144: }
145: }
146:
1.1 schwarze 147: /*
148: * Save a descriptor to the current working directory.
149: * Since pathnames in the "paths" variable might be relative,
150: * and we'll be chdir()ing into them, we need to keep a handle
151: * on our current directory from which to start the chdir().
152: */
153:
154: if (NULL == getcwd(buf, PATH_MAX)) {
155: perror(NULL);
156: goto out;
157: } else if (-1 == (fd = open(buf, O_RDONLY, 0))) {
158: perror(buf);
159: goto out;
160: }
161:
1.6 schwarze 162: sql = sql_statement(e);
1.1 schwarze 163:
164: /*
165: * Loop over the directories (containing databases) for us to
166: * search.
167: * Don't let missing/bad databases/directories phase us.
168: * In each, try to open the resident database and, if it opens,
169: * scan it for our match expression.
170: */
171:
172: for (i = 0; i < paths->sz; i++) {
173: if (-1 == fchdir(fd)) {
174: perror(buf);
175: free(*res);
176: break;
177: } else if (-1 == chdir(paths->paths[i])) {
178: perror(paths->paths[i]);
179: continue;
180: }
181:
182: c = sqlite3_open_v2
183: (MANDOC_DB, &db,
184: SQLITE_OPEN_READONLY, NULL);
185:
186: if (SQLITE_OK != c) {
187: perror(MANDOC_DB);
188: sqlite3_close(db);
189: continue;
190: }
191:
192: /*
193: * Define the SQL functions for substring
194: * and regular expression matching.
195: */
196:
197: c = sqlite3_create_function(db, "match", 2,
198: SQLITE_ANY, NULL, sql_match, NULL, NULL);
199: assert(SQLITE_OK == c);
200: c = sqlite3_create_function(db, "regexp", 2,
201: SQLITE_ANY, NULL, sql_regexp, NULL, NULL);
202: assert(SQLITE_OK == c);
203:
204: j = 1;
205: c = sqlite3_prepare_v2(db, sql, -1, &s, NULL);
206: if (SQLITE_OK != c)
207: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
208:
209: for (ep = e; NULL != ep; ep = ep->next) {
210: if (NULL == ep->substr) {
211: SQL_BIND_BLOB(db, s, j, ep->regexp);
212: } else
213: SQL_BIND_TEXT(db, s, j, ep->substr);
214: SQL_BIND_INT64(db, s, j, ep->bits);
215: }
216:
217: memset(&htab, 0, sizeof(struct ohash));
218: ohash_init(&htab, 4, &info);
219:
220: /*
221: * Hash each entry on its [unique] document identifier.
222: * This is a uint64_t.
223: * Instead of using a hash function, simply convert the
224: * uint64_t to a uint32_t, the hash value's type.
225: * This gives good performance and preserves the
226: * distribution of buckets in the table.
227: */
228: while (SQLITE_ROW == (c = sqlite3_step(s))) {
1.9 schwarze 229: id = sqlite3_column_int64(s, 1);
1.1 schwarze 230: idx = ohash_lookup_memory
231: (&htab, (char *)&id,
232: sizeof(uint64_t), (uint32_t)id);
233:
234: if (NULL != ohash_find(&htab, idx))
235: continue;
236:
237: mp = mandoc_calloc(1, sizeof(struct match));
238: mp->id = id;
1.9 schwarze 239: mp->form = sqlite3_column_int(s, 0);
1.1 schwarze 240: ohash_insert(&htab, idx, mp);
241: }
242:
243: if (SQLITE_DONE != c)
244: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
245:
246: sqlite3_finalize(s);
247:
248: c = sqlite3_prepare_v2(db,
249: "SELECT * FROM mlinks WHERE pageid=?",
250: -1, &s, NULL);
251: if (SQLITE_OK != c)
252: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
253:
1.3 schwarze 254: c = sqlite3_prepare_v2(db,
255: "SELECT * FROM keys WHERE pageid=? AND bits & ?",
256: -1, &s2, NULL);
257: if (SQLITE_OK != c)
258: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
259:
1.1 schwarze 260: for (mp = ohash_first(&htab, &idx);
261: NULL != mp;
262: mp = ohash_next(&htab, &idx)) {
263: if (cur + 1 > maxres) {
264: maxres += 1024;
265: *res = mandoc_realloc
266: (*res, maxres * sizeof(struct manpage));
267: }
268: mpage = *res + cur;
269: mpage->form = mp->form;
1.10 schwarze 270: buildnames(mpage, db, s, mp->id,
271: paths->paths[i], mp->form);
1.3 schwarze 272: mpage->output = outbit ?
273: buildoutput(db, s2, mp->id, outbit) : NULL;
1.1 schwarze 274:
275: free(mp);
276: cur++;
277: }
278:
279: sqlite3_finalize(s);
1.3 schwarze 280: sqlite3_finalize(s2);
1.1 schwarze 281: sqlite3_close(db);
282: ohash_delete(&htab);
283: }
284: rc = 1;
285: out:
286: exprfree(e);
287: if (-1 != fd)
288: close(fd);
289: free(sql);
290: *sz = cur;
291: return(rc);
1.2 schwarze 292: }
293:
1.8 schwarze 294: static void
295: buildnames(struct manpage *mpage, sqlite3 *db, sqlite3_stmt *s,
1.10 schwarze 296: uint64_t id, const char *path, int form)
1.2 schwarze 297: {
1.8 schwarze 298: char *newnames;
1.10 schwarze 299: const char *oldnames, *sep1, *name, *sec, *sep2, *arch, *fsec;
1.2 schwarze 300: size_t i;
301: int c;
302:
1.8 schwarze 303: mpage->names = NULL;
1.2 schwarze 304: i = 1;
305: SQL_BIND_INT64(db, s, i, id);
306: while (SQLITE_ROW == (c = sqlite3_step(s))) {
1.8 schwarze 307:
308: /* Assemble the list of names. */
309:
310: if (NULL == mpage->names) {
1.2 schwarze 311: oldnames = "";
312: sep1 = "";
313: } else {
1.8 schwarze 314: oldnames = mpage->names;
1.2 schwarze 315: sep1 = ", ";
316: }
1.10 schwarze 317: sec = sqlite3_column_text(s, 0);
318: arch = sqlite3_column_text(s, 1);
319: name = sqlite3_column_text(s, 2);
1.2 schwarze 320: sep2 = '\0' == *arch ? "" : "/";
321: if (-1 == asprintf(&newnames, "%s%s%s(%s%s%s)",
322: oldnames, sep1, name, sec, sep2, arch)) {
323: perror(0);
324: exit((int)MANDOCLEVEL_SYSERR);
325: }
1.8 schwarze 326: free(mpage->names);
327: mpage->names = newnames;
328:
329: /* Also save the first file name encountered. */
330:
331: if (NULL != mpage->file)
332: continue;
333:
1.10 schwarze 334: if (form) {
335: sep1 = "man";
336: fsec = sec;
337: } else {
338: sep1 = "cat";
339: fsec = "0";
340: }
341: if (-1 == asprintf(&mpage->file, "%s/%s%s%s%s/%s.%s",
342: path, sep1, sec, sep2, arch, name, fsec)) {
1.8 schwarze 343: perror(0);
344: exit((int)MANDOCLEVEL_SYSERR);
345: }
1.2 schwarze 346: }
347: if (SQLITE_DONE != c)
348: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
349: sqlite3_reset(s);
1.3 schwarze 350: }
351:
352: static char *
353: buildoutput(sqlite3 *db, sqlite3_stmt *s, uint64_t id, uint64_t outbit)
354: {
355: char *output, *newoutput;
356: const char *oldoutput, *sep1, *data;
357: size_t i;
358: int c;
359:
360: output = NULL;
361: i = 1;
362: SQL_BIND_INT64(db, s, i, id);
363: SQL_BIND_INT64(db, s, i, outbit);
364: while (SQLITE_ROW == (c = sqlite3_step(s))) {
365: if (NULL == output) {
366: oldoutput = "";
367: sep1 = "";
368: } else {
369: oldoutput = output;
370: sep1 = " # ";
371: }
372: data = sqlite3_column_text(s, 1);
373: if (-1 == asprintf(&newoutput, "%s%s%s",
374: oldoutput, sep1, data)) {
375: perror(0);
376: exit((int)MANDOCLEVEL_SYSERR);
377: }
378: free(output);
379: output = newoutput;
380: }
381: if (SQLITE_DONE != c)
382: fprintf(stderr, "%s\n", sqlite3_errmsg(db));
383: sqlite3_reset(s);
384: return(output);
1.1 schwarze 385: }
386:
387: /*
388: * Implement substring match as an application-defined SQL function.
389: * Using the SQL LIKE or GLOB operators instead would be a bad idea
390: * because that would require escaping metacharacters in the string
391: * being searched for.
392: */
393: static void
394: sql_match(sqlite3_context *context, int argc, sqlite3_value **argv)
395: {
396:
397: assert(2 == argc);
398: sqlite3_result_int(context, NULL != strcasestr(
399: (const char *)sqlite3_value_text(argv[1]),
400: (const char *)sqlite3_value_text(argv[0])));
401: }
402:
403: /*
404: * Implement regular expression match
405: * as an application-defined SQL function.
406: */
407: static void
408: sql_regexp(sqlite3_context *context, int argc, sqlite3_value **argv)
409: {
410:
411: assert(2 == argc);
412: sqlite3_result_int(context, !regexec(
413: (regex_t *)sqlite3_value_blob(argv[0]),
414: (const char *)sqlite3_value_text(argv[1]),
415: 0, NULL, 0));
416: }
417:
1.4 schwarze 418: static void
419: sql_append(char **sql, size_t *sz, const char *newstr, int count)
420: {
421: size_t newsz;
422:
423: newsz = 1 < count ? (size_t)count : strlen(newstr);
424: *sql = mandoc_realloc(*sql, *sz + newsz + 1);
425: if (1 < count)
426: memset(*sql + *sz, *newstr, (size_t)count);
427: else
428: memcpy(*sql + *sz, newstr, newsz);
429: *sz += newsz;
430: (*sql)[*sz] = '\0';
431: }
432:
1.1 schwarze 433: /*
434: * Prepare the search SQL statement.
435: */
436: static char *
1.6 schwarze 437: sql_statement(const struct expr *e)
1.1 schwarze 438: {
439: char *sql;
440: size_t sz;
1.4 schwarze 441: int needop;
1.1 schwarze 442:
1.4 schwarze 443: sql = mandoc_strdup("SELECT * FROM mpages WHERE ");
1.1 schwarze 444: sz = strlen(sql);
445:
1.4 schwarze 446: for (needop = 0; NULL != e; e = e->next) {
447: if (e->and)
448: sql_append(&sql, &sz, " AND ", 1);
449: else if (needop)
450: sql_append(&sql, &sz, " OR ", 1);
451: if (e->open)
452: sql_append(&sql, &sz, "(", e->open);
453: sql_append(&sql, &sz, NULL == e->substr ?
454: "id IN (SELECT pageid FROM keys "
455: "WHERE key REGEXP ? AND bits & ?)" :
456: "id IN (SELECT pageid FROM keys "
457: "WHERE key MATCH ? AND bits & ?)", 1);
458: if (e->close)
459: sql_append(&sql, &sz, ")", e->close);
460: needop = 1;
1.1 schwarze 461: }
462:
463: return(sql);
464: }
465:
466: /*
467: * Compile a set of string tokens into an expression.
468: * Tokens in "argv" are assumed to be individual expression atoms (e.g.,
469: * "(", "foo=bar", etc.).
470: */
471: static struct expr *
472: exprcomp(const struct mansearch *search, int argc, char *argv[])
473: {
1.4 schwarze 474: int i, toopen, logic, igncase, toclose;
1.1 schwarze 475: struct expr *first, *next, *cur;
476:
477: first = cur = NULL;
1.6 schwarze 478: logic = igncase = toclose = 0;
479: toopen = 1;
1.1 schwarze 480:
481: for (i = 0; i < argc; i++) {
1.4 schwarze 482: if (0 == strcmp("(", argv[i])) {
483: if (igncase)
484: goto fail;
485: toopen++;
486: toclose++;
487: continue;
488: } else if (0 == strcmp(")", argv[i])) {
489: if (toopen || logic || igncase || NULL == cur)
490: goto fail;
491: cur->close++;
492: if (0 > --toclose)
493: goto fail;
494: continue;
495: } else if (0 == strcmp("-a", argv[i])) {
496: if (toopen || logic || igncase || NULL == cur)
497: goto fail;
498: logic = 1;
499: continue;
500: } else if (0 == strcmp("-o", argv[i])) {
501: if (toopen || logic || igncase || NULL == cur)
502: goto fail;
503: logic = 2;
504: continue;
505: } else if (0 == strcmp("-i", argv[i])) {
506: if (igncase)
507: goto fail;
508: igncase = 1;
509: continue;
1.1 schwarze 510: }
1.4 schwarze 511: next = exprterm(search, argv[i], !igncase);
512: if (NULL == next)
513: goto fail;
514: next->open = toopen;
515: next->and = (1 == logic);
1.1 schwarze 516: if (NULL != first) {
517: cur->next = next;
518: cur = next;
519: } else
520: cur = first = next;
1.4 schwarze 521: toopen = logic = igncase = 0;
1.1 schwarze 522: }
1.6 schwarze 523: if (toopen || logic || igncase || toclose)
524: goto fail;
525:
526: cur->close++;
527: cur = exprspec(cur, TYPE_arch, search->arch, "^(%s|any)$");
528: exprspec(cur, TYPE_sec, search->sec, "^%s$");
529:
530: return(first);
531:
1.4 schwarze 532: fail:
533: if (NULL != first)
534: exprfree(first);
535: return(NULL);
1.1 schwarze 536: }
537:
538: static struct expr *
1.6 schwarze 539: exprspec(struct expr *cur, uint64_t key, const char *value,
540: const char *format)
541: {
542: char errbuf[BUFSIZ];
543: char *cp;
544: int irc;
545:
546: if (NULL == value)
547: return(cur);
548:
549: if (-1 == asprintf(&cp, format, value)) {
550: perror(0);
551: exit((int)MANDOCLEVEL_SYSERR);
552: }
553: cur->next = mandoc_calloc(1, sizeof(struct expr));
554: cur = cur->next;
555: cur->and = 1;
556: cur->bits = key;
557: if (0 != (irc = regcomp(&cur->regexp, cp,
558: REG_EXTENDED | REG_NOSUB | REG_ICASE))) {
559: regerror(irc, &cur->regexp, errbuf, sizeof(errbuf));
560: fprintf(stderr, "regcomp: %s\n", errbuf);
561: cur->substr = value;
562: }
563: free(cp);
564: return(cur);
565: }
566:
567: static struct expr *
1.1 schwarze 568: exprterm(const struct mansearch *search, char *buf, int cs)
569: {
1.6 schwarze 570: char errbuf[BUFSIZ];
1.1 schwarze 571: struct expr *e;
572: char *key, *v;
1.11 ! schwarze 573: uint64_t iterbit;
! 574: int i, irc;
1.1 schwarze 575:
576: if ('\0' == *buf)
577: return(NULL);
578:
579: e = mandoc_calloc(1, sizeof(struct expr));
580:
581: /*"whatis" mode uses an opaque string and default fields. */
582:
583: if (MANSEARCH_WHATIS & search->flags) {
584: e->substr = buf;
585: e->bits = search->deftype;
586: return(e);
587: }
588:
589: /*
590: * If no =~ is specified, search with equality over names and
591: * descriptions.
592: * If =~ begins the phrase, use name and description fields.
593: */
594:
595: if (NULL == (v = strpbrk(buf, "=~"))) {
596: e->substr = buf;
597: e->bits = search->deftype;
598: return(e);
599: } else if (v == buf)
600: e->bits = search->deftype;
601:
602: if ('~' == *v++) {
1.6 schwarze 603: if (0 != (irc = regcomp(&e->regexp, v,
604: REG_EXTENDED | REG_NOSUB | (cs ? 0 : REG_ICASE)))) {
605: regerror(irc, &e->regexp, errbuf, sizeof(errbuf));
606: fprintf(stderr, "regcomp: %s\n", errbuf);
1.1 schwarze 607: free(e);
608: return(NULL);
609: }
610: } else
611: e->substr = v;
612: v[-1] = '\0';
613:
614: /*
615: * Parse out all possible fields.
616: * If the field doesn't resolve, bail.
617: */
618:
619: while (NULL != (key = strsep(&buf, ","))) {
620: if ('\0' == *key)
621: continue;
1.11 ! schwarze 622: for (i = 0, iterbit = 1;
! 623: i < mansearch_keymax;
! 624: i++, iterbit <<= 1) {
! 625: if (0 == strcasecmp(key,
! 626: mansearch_keynames[i])) {
! 627: e->bits |= iterbit;
! 628: break;
! 629: }
! 630: }
! 631: if (i == mansearch_keymax) {
! 632: if (strcasecmp(key, "any")) {
! 633: free(e);
! 634: return(NULL);
! 635: }
! 636: e->bits |= ~0ULL;
1.1 schwarze 637: }
638: }
639:
640: return(e);
641: }
642:
643: static void
644: exprfree(struct expr *p)
645: {
646: struct expr *pp;
647:
648: while (NULL != p) {
649: pp = p->next;
650: free(p);
651: p = pp;
652: }
653: }
654:
655: static void *
656: hash_halloc(size_t sz, void *arg)
657: {
658:
659: return(mandoc_calloc(sz, 1));
660: }
661:
662: static void *
663: hash_alloc(size_t sz, void *arg)
664: {
665:
666: return(mandoc_malloc(sz));
667: }
668:
669: static void
670: hash_free(void *p, size_t sz, void *arg)
671: {
672:
673: free(p);
674: }