]> git.cameronkatri.com Git - mandoc.git/blob - mansearch.c
Port ctags-style, less(1) :t internal searching from terminal output
[mandoc.git] / mansearch.c
1 /* $OpenBSD: mansearch.c,v 1.50 2016/07/09 15:23:36 schwarze Exp $ */
2 /*
3 * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
4 * Copyright (c) 2013, 2014, 2015, 2016 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, int32_t);
71 static size_t lstlen(const char *);
72 static void lstcat(char *, size_t *, 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 *res = NULL;
108
109 outkey = KEY_Nd;
110 if (search->outkey != NULL)
111 for (im = 0; im < KEY_MAX; im++)
112 if (0 == strcasecmp(search->outkey,
113 mansearch_keynames[im])) {
114 outkey = im;
115 break;
116 }
117
118 /*
119 * Remember the original working directory, if possible.
120 * This will be needed if the second or a later directory
121 * is given as a relative path.
122 * Do not error out if the current directory is not
123 * searchable: Maybe it won't be needed after all.
124 */
125
126 if (getcwd(buf, PATH_MAX) == NULL) {
127 getcwd_status = 0;
128 (void)strlcpy(buf, strerror(errno), sizeof(buf));
129 } else
130 getcwd_status = 1;
131
132 /*
133 * Loop over the directories (containing databases) for us to
134 * search.
135 * Don't let missing/bad databases/directories phase us.
136 * In each, try to open the resident database and, if it opens,
137 * scan it for our match expression.
138 */
139
140 chdir_status = 0;
141 for (i = 0; i < paths->sz; i++) {
142 if (chdir_status && paths->paths[i][0] != '/') {
143 if ( ! getcwd_status) {
144 warnx("%s: getcwd: %s", paths->paths[i], buf);
145 continue;
146 } else if (chdir(buf) == -1) {
147 warn("%s", buf);
148 continue;
149 }
150 }
151 if (chdir(paths->paths[i]) == -1) {
152 warn("%s", paths->paths[i]);
153 continue;
154 }
155 chdir_status = 1;
156
157 if (dbm_open(MANDOC_DB) == -1) {
158 warn("%s/%s", paths->paths[i], MANDOC_DB);
159 continue;
160 }
161
162 if ((htab = manmerge(e, NULL)) == NULL) {
163 dbm_close();
164 continue;
165 }
166
167 for (rp = ohash_first(htab, &slot); rp != NULL;
168 rp = ohash_next(htab, &slot)) {
169 page = dbm_page_get(rp->page);
170
171 if (lstmatch(search->sec, page->sect) == 0 ||
172 lstmatch(search->arch, page->arch) == 0)
173 continue;
174
175 if (cur + 1 > maxres) {
176 maxres += 1024;
177 *res = mandoc_reallocarray(*res,
178 maxres, sizeof(**res));
179 }
180 mpage = *res + cur;
181 mandoc_asprintf(&mpage->file, "%s/%s",
182 paths->paths[i], page->file + 1);
183 mpage->names = buildnames(page);
184 mpage->output = (int)outkey == KEY_Nd ?
185 mandoc_strdup(page->desc) :
186 buildoutput(outkey, page->addr);
187 mpage->ipath = i;
188 mpage->bits = rp->bits;
189 mpage->sec = *page->sect - '0';
190 if (mpage->sec < 0 || mpage->sec > 9)
191 mpage->sec = 10;
192 mpage->form = *page->file;
193 free(rp);
194 cur++;
195 }
196 ohash_delete(htab);
197 free(htab);
198 dbm_close();
199
200 /*
201 * In man(1) mode, prefer matches in earlier trees
202 * over matches in later trees.
203 */
204
205 if (cur && search->firstmatch)
206 break;
207 }
208 qsort(*res, cur, sizeof(struct manpage), manpage_compare);
209 if (chdir_status && getcwd_status && chdir(buf) == -1)
210 warn("%s", buf);
211 exprfree(e);
212 *sz = cur;
213 return 1;
214 }
215
216 /*
217 * Merge the results for the expression tree rooted at e
218 * into the the result list htab.
219 */
220 static struct ohash *
221 manmerge(struct expr *e, struct ohash *htab)
222 {
223 switch (e->type) {
224 case EXPR_TERM:
225 return manmerge_term(e, htab);
226 case EXPR_OR:
227 return manmerge_or(e->child, htab);
228 case EXPR_AND:
229 return manmerge_and(e->child, htab);
230 default:
231 abort();
232 }
233 }
234
235 static struct ohash *
236 manmerge_term(struct expr *e, struct ohash *htab)
237 {
238 struct dbm_res res, *rp;
239 uint64_t ib;
240 unsigned int slot;
241 int im;
242
243 if (htab == NULL) {
244 htab = mandoc_malloc(sizeof(*htab));
245 mandoc_ohash_init(htab, 4, offsetof(struct dbm_res, page));
246 }
247
248 for (im = 0, ib = 1; im < KEY_MAX; im++, ib <<= 1) {
249 if ((e->bits & ib) == 0)
250 continue;
251
252 switch (ib) {
253 case TYPE_arch:
254 dbm_page_byarch(&e->match);
255 break;
256 case TYPE_sec:
257 dbm_page_bysect(&e->match);
258 break;
259 case TYPE_Nm:
260 dbm_page_byname(&e->match);
261 break;
262 case TYPE_Nd:
263 dbm_page_bydesc(&e->match);
264 break;
265 default:
266 dbm_page_bymacro(im - 2, &e->match);
267 break;
268 }
269
270 /*
271 * When hashing for deduplication, use the unique
272 * page ID itself instead of a hash function;
273 * that is quite efficient.
274 */
275
276 for (;;) {
277 res = dbm_page_next();
278 if (res.page == -1)
279 break;
280 slot = ohash_lookup_memory(htab,
281 (char *)&res, sizeof(res.page), res.page);
282 if ((rp = ohash_find(htab, slot)) != NULL) {
283 rp->bits |= res.bits;
284 continue;
285 }
286 rp = mandoc_malloc(sizeof(*rp));
287 *rp = res;
288 ohash_insert(htab, slot, rp);
289 }
290 }
291 return htab;
292 }
293
294 static struct ohash *
295 manmerge_or(struct expr *e, struct ohash *htab)
296 {
297 while (e != NULL) {
298 htab = manmerge(e, htab);
299 e = e->next;
300 }
301 return htab;
302 }
303
304 static struct ohash *
305 manmerge_and(struct expr *e, struct ohash *htab)
306 {
307 struct ohash *hand, *h1, *h2;
308 struct dbm_res *res;
309 unsigned int slot1, slot2;
310
311 /* Evaluate the first term of the AND clause. */
312
313 hand = manmerge(e, NULL);
314
315 while ((e = e->next) != NULL) {
316
317 /* Evaluate the next term and prepare for ANDing. */
318
319 h2 = manmerge(e, NULL);
320 if (ohash_entries(h2) < ohash_entries(hand)) {
321 h1 = h2;
322 h2 = hand;
323 } else
324 h1 = hand;
325 hand = mandoc_malloc(sizeof(*hand));
326 mandoc_ohash_init(hand, 4, offsetof(struct dbm_res, page));
327
328 /* Keep all pages that are in both result sets. */
329
330 for (res = ohash_first(h1, &slot1); res != NULL;
331 res = ohash_next(h1, &slot1)) {
332 if (ohash_find(h2, ohash_lookup_memory(h2,
333 (char *)res, sizeof(res->page),
334 res->page)) == NULL)
335 free(res);
336 else
337 ohash_insert(hand, ohash_lookup_memory(hand,
338 (char *)res, sizeof(res->page),
339 res->page), res);
340 }
341
342 /* Discard the merged results. */
343
344 for (res = ohash_first(h2, &slot2); res != NULL;
345 res = ohash_next(h2, &slot2))
346 free(res);
347 ohash_delete(h2);
348 free(h2);
349 ohash_delete(h1);
350 free(h1);
351 }
352
353 /* Merge the result of the AND into htab. */
354
355 if (htab == NULL)
356 return hand;
357
358 for (res = ohash_first(hand, &slot1); res != NULL;
359 res = ohash_next(hand, &slot1)) {
360 slot2 = ohash_lookup_memory(htab,
361 (char *)res, sizeof(res->page), res->page);
362 if (ohash_find(htab, slot2) == NULL)
363 ohash_insert(htab, slot2, res);
364 else
365 free(res);
366 }
367
368 /* Discard the merged result. */
369
370 ohash_delete(hand);
371 free(hand);
372 return htab;
373 }
374
375 void
376 mansearch_free(struct manpage *res, size_t sz)
377 {
378 size_t i;
379
380 for (i = 0; i < sz; i++) {
381 free(res[i].file);
382 free(res[i].names);
383 free(res[i].output);
384 }
385 free(res);
386 }
387
388 static int
389 manpage_compare(const void *vp1, const void *vp2)
390 {
391 const struct manpage *mp1, *mp2;
392 int diff;
393
394 mp1 = vp1;
395 mp2 = vp2;
396 return (diff = mp2->bits - mp1->bits) ? diff :
397 (diff = mp1->sec - mp2->sec) ? diff :
398 strcasecmp(mp1->names, mp2->names);
399 }
400
401 static char *
402 buildnames(const struct dbm_page *page)
403 {
404 char *buf;
405 size_t i, sz;
406
407 sz = lstlen(page->name) + 1 + lstlen(page->sect) +
408 (page->arch == NULL ? 0 : 1 + lstlen(page->arch)) + 2;
409 buf = mandoc_malloc(sz);
410 i = 0;
411 lstcat(buf, &i, page->name);
412 buf[i++] = '(';
413 lstcat(buf, &i, page->sect);
414 if (page->arch != NULL) {
415 buf[i++] = '/';
416 lstcat(buf, &i, page->arch);
417 }
418 buf[i++] = ')';
419 buf[i++] = '\0';
420 assert(i == sz);
421 return buf;
422 }
423
424 /*
425 * Count the buffer space needed to print the NUL-terminated
426 * list of NUL-terminated strings, when printing two separator
427 * characters between strings.
428 */
429 static size_t
430 lstlen(const char *cp)
431 {
432 size_t sz;
433
434 for (sz = 0;; sz++) {
435 if (cp[0] == '\0') {
436 if (cp[1] == '\0')
437 break;
438 sz++;
439 } else if (cp[0] < ' ')
440 sz--;
441 cp++;
442 }
443 return sz;
444 }
445
446 /*
447 * Print the NUL-terminated list of NUL-terminated strings
448 * into the buffer, seperating strings with a comma and a blank.
449 */
450 static void
451 lstcat(char *buf, size_t *i, const char *cp)
452 {
453 for (;;) {
454 if (cp[0] == '\0') {
455 if (cp[1] == '\0')
456 break;
457 buf[(*i)++] = ',';
458 buf[(*i)++] = ' ';
459 } else if (cp[0] >= ' ')
460 buf[(*i)++] = cp[0];
461 cp++;
462 }
463 }
464
465 /*
466 * Return 1 if the string *want occurs in any of the strings
467 * in the NUL-terminated string list *have, or 0 otherwise.
468 * If either argument is NULL or empty, assume no filtering
469 * is desired and return 1.
470 */
471 static int
472 lstmatch(const char *want, const char *have)
473 {
474 if (want == NULL || have == NULL || *have == '\0')
475 return 1;
476 while (*have != '\0') {
477 if (strcasestr(have, want) != NULL)
478 return 1;
479 have = strchr(have, '\0') + 1;
480 }
481 return 0;
482 }
483
484 /*
485 * Build a list of values taken by the macro im
486 * in the manual page with big-endian address addr.
487 */
488 static char *
489 buildoutput(size_t im, int32_t addr)
490 {
491 const char *oldoutput, *sep;
492 char *output, *newoutput, *value;
493
494 output = NULL;
495 dbm_macro_bypage(im - 2, addr);
496 while ((value = dbm_macro_next()) != NULL) {
497 if (output == NULL) {
498 oldoutput = "";
499 sep = "";
500 } else {
501 oldoutput = output;
502 sep = " # ";
503 }
504 mandoc_asprintf(&newoutput, "%s%s%s", oldoutput, sep, value);
505 free(output);
506 output = newoutput;
507 }
508 return output;
509 }
510
511 /*
512 * Compile a set of string tokens into an expression.
513 * Tokens in "argv" are assumed to be individual expression atoms (e.g.,
514 * "(", "foo=bar", etc.).
515 */
516 static struct expr *
517 exprcomp(const struct mansearch *search, int argc, char *argv[], int *argi)
518 {
519 struct expr *parent, *child;
520 int needterm, nested;
521
522 if ((nested = *argi) == argc)
523 return NULL;
524 needterm = 1;
525 parent = child = NULL;
526 while (*argi < argc) {
527 if (strcmp(")", argv[*argi]) == 0) {
528 if (needterm)
529 warnx("missing term "
530 "before closing parenthesis");
531 needterm = 0;
532 if (nested)
533 break;
534 warnx("ignoring unmatched right parenthesis");
535 ++*argi;
536 continue;
537 }
538 if (strcmp("-o", argv[*argi]) == 0) {
539 if (needterm) {
540 if (*argi > 0)
541 warnx("ignoring -o after %s",
542 argv[*argi - 1]);
543 else
544 warnx("ignoring initial -o");
545 }
546 needterm = 1;
547 ++*argi;
548 continue;
549 }
550 needterm = 0;
551 if (child == NULL) {
552 child = expr_and(search, argc, argv, argi);
553 continue;
554 }
555 if (parent == NULL) {
556 parent = mandoc_calloc(1, sizeof(*parent));
557 parent->type = EXPR_OR;
558 parent->next = NULL;
559 parent->child = child;
560 }
561 child->next = expr_and(search, argc, argv, argi);
562 child = child->next;
563 }
564 if (needterm && *argi)
565 warnx("ignoring trailing %s", argv[*argi - 1]);
566 return parent == NULL ? child : parent;
567 }
568
569 static struct expr *
570 expr_and(const struct mansearch *search, int argc, char *argv[], int *argi)
571 {
572 struct expr *parent, *child;
573 int needterm;
574
575 needterm = 1;
576 parent = child = NULL;
577 while (*argi < argc) {
578 if (strcmp(")", argv[*argi]) == 0) {
579 if (needterm)
580 warnx("missing term "
581 "before closing parenthesis");
582 needterm = 0;
583 break;
584 }
585 if (strcmp("-o", argv[*argi]) == 0)
586 break;
587 if (strcmp("-a", argv[*argi]) == 0) {
588 if (needterm) {
589 if (*argi > 0)
590 warnx("ignoring -a after %s",
591 argv[*argi - 1]);
592 else
593 warnx("ignoring initial -a");
594 }
595 needterm = 1;
596 ++*argi;
597 continue;
598 }
599 if (needterm == 0)
600 break;
601 if (child == NULL) {
602 child = exprterm(search, argc, argv, argi);
603 if (child != NULL)
604 needterm = 0;
605 continue;
606 }
607 needterm = 0;
608 if (parent == NULL) {
609 parent = mandoc_calloc(1, sizeof(*parent));
610 parent->type = EXPR_AND;
611 parent->next = NULL;
612 parent->child = child;
613 }
614 child->next = exprterm(search, argc, argv, argi);
615 if (child->next != NULL) {
616 child = child->next;
617 needterm = 0;
618 }
619 }
620 if (needterm && *argi)
621 warnx("ignoring trailing %s", argv[*argi - 1]);
622 return parent == NULL ? child : parent;
623 }
624
625 static struct expr *
626 exprterm(const struct mansearch *search, int argc, char *argv[], int *argi)
627 {
628 char errbuf[BUFSIZ];
629 struct expr *e;
630 char *key, *val;
631 uint64_t iterbit;
632 int cs, i, irc;
633
634 if (strcmp("(", argv[*argi]) == 0) {
635 ++*argi;
636 e = exprcomp(search, argc, argv, argi);
637 if (*argi < argc) {
638 assert(strcmp(")", argv[*argi]) == 0);
639 ++*argi;
640 } else
641 warnx("unclosed parenthesis");
642 return e;
643 }
644
645 e = mandoc_calloc(1, sizeof(*e));
646 e->type = EXPR_TERM;
647 e->bits = 0;
648 e->next = NULL;
649 e->child = NULL;
650
651 if (search->argmode == ARG_NAME) {
652 e->bits = TYPE_Nm;
653 e->match.type = DBM_EXACT;
654 e->match.str = argv[(*argi)++];
655 return e;
656 }
657
658 /*
659 * Separate macro keys from search string.
660 * If needed, request regular expression handling.
661 */
662
663 cs = 1;
664 if (search->argmode == ARG_WORD) {
665 e->bits = TYPE_Nm;
666 e->match.type = DBM_REGEX;
667 #if HAVE_REWB_BSD
668 mandoc_asprintf(&val, "[[:<:]]%s[[:>:]]", argv[*argi]);
669 #elif HAVE_REWB_SYSV
670 mandoc_asprintf(&val, "\\<%s\\>", argv[*argi]);
671 #else
672 mandoc_asprintf(&val,
673 "(^|[^a-zA-Z01-9_])%s([^a-zA-Z01-9_]|$)", argv[*argi]);
674 #endif
675 cs = 0;
676 } else if ((val = strpbrk(argv[*argi], "=~")) == NULL) {
677 e->bits = TYPE_Nm | TYPE_Nd;
678 e->match.type = DBM_SUB;
679 e->match.str = argv[*argi];
680 } else {
681 if (val == argv[*argi])
682 e->bits = TYPE_Nm | TYPE_Nd;
683 if (*val == '=') {
684 e->match.type = DBM_SUB;
685 e->match.str = val + 1;
686 } else
687 e->match.type = DBM_REGEX;
688 *val++ = '\0';
689 if (strstr(argv[*argi], "arch") != NULL)
690 cs = 0;
691 }
692
693 /* Compile regular expressions. */
694
695 if (e->match.type == DBM_REGEX) {
696 e->match.re = mandoc_malloc(sizeof(*e->match.re));
697 irc = regcomp(e->match.re, val,
698 REG_EXTENDED | REG_NOSUB | (cs ? 0 : REG_ICASE));
699 if (irc) {
700 regerror(irc, e->match.re, errbuf, sizeof(errbuf));
701 warnx("regcomp /%s/: %s", val, errbuf);
702 }
703 if (search->argmode == ARG_WORD)
704 free(val);
705 if (irc) {
706 free(e->match.re);
707 free(e);
708 ++*argi;
709 return NULL;
710 }
711 }
712
713 if (e->bits) {
714 ++*argi;
715 return e;
716 }
717
718 /*
719 * Parse out all possible fields.
720 * If the field doesn't resolve, bail.
721 */
722
723 while (NULL != (key = strsep(&argv[*argi], ","))) {
724 if ('\0' == *key)
725 continue;
726 for (i = 0, iterbit = 1; i < KEY_MAX; i++, iterbit <<= 1) {
727 if (0 == strcasecmp(key, mansearch_keynames[i])) {
728 e->bits |= iterbit;
729 break;
730 }
731 }
732 if (i == KEY_MAX) {
733 if (strcasecmp(key, "any"))
734 warnx("treating unknown key "
735 "\"%s\" as \"any\"", key);
736 e->bits |= ~0ULL;
737 }
738 }
739
740 ++*argi;
741 return e;
742 }
743
744 static void
745 exprfree(struct expr *e)
746 {
747 if (e->next != NULL)
748 exprfree(e->next);
749 if (e->child != NULL)
750 exprfree(e->child);
751 free(e);
752 }