1 /* $Id: mansearch.c,v 1.76 2017/08/02 13:29:04 schwarze Exp $ */
3 * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
4 * Copyright (c) 2013-2017 Ingo Schwarze <schwarze@openbsd.org>
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.
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.
21 #include <sys/types.h>
40 #include "mandoc_aux.h"
41 #include "mandoc_ohash.h"
43 #include "mansearch.h"
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
;
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"
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 *);
85 mansearch(const struct mansearch
*search
,
86 const struct manpaths
*paths
,
87 int argc
, char *argv
[],
88 struct manpage
**res
, size_t *sz
)
93 struct dbm_page
*page
;
94 struct manpage
*mpage
;
96 size_t cur
, i
, maxres
, outkey
;
98 int argi
, chdir_status
, getcwd_status
, im
;
101 if ((e
= exprcomp(search
, argc
, argv
, &argi
)) == NULL
) {
111 if (search
->outkey
!= NULL
)
112 for (im
= 0; im
< KEY_MAX
; im
++)
113 if (0 == strcasecmp(search
->outkey
,
114 mansearch_keynames
[im
])) {
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.
127 if (getcwd(buf
, PATH_MAX
) == NULL
) {
129 (void)strlcpy(buf
, strerror(errno
), sizeof(buf
));
134 * Loop over the directories (containing databases) for us to
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.
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
);
147 } else if (chdir(buf
) == -1) {
152 if (chdir(paths
->paths
[i
]) == -1) {
153 warn("%s", paths
->paths
[i
]);
158 if (dbm_open(MANDOC_DB
) == -1) {
160 warn("%s/%s", paths
->paths
[i
], MANDOC_DB
);
164 if ((htab
= manmerge(e
, NULL
)) == NULL
) {
169 for (rp
= ohash_first(htab
, &slot
); rp
!= NULL
;
170 rp
= ohash_next(htab
, &slot
)) {
171 page
= dbm_page_get(rp
->page
);
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
)))
183 if (cur
+ 1 > maxres
) {
185 *res
= mandoc_reallocarray(*res
,
186 maxres
, sizeof(**res
));
189 mandoc_asprintf(&mpage
->file
, "%s/%s",
190 paths
->paths
[i
], page
->file
+ 1);
191 mpage
->names
= buildnames(page
);
192 mpage
->output
= buildoutput(outkey
, page
);
194 mpage
->bits
= rp
->bits
;
195 mpage
->sec
= *page
->sect
- '0';
196 if (mpage
->sec
< 0 || mpage
->sec
> 9)
198 mpage
->form
= *page
->file
;
207 * In man(1) mode, prefer matches in earlier trees
208 * over matches in later trees.
211 if (cur
&& search
->firstmatch
)
215 qsort(*res
, cur
, sizeof(struct manpage
), manpage_compare
);
216 if (chdir_status
&& getcwd_status
&& chdir(buf
) == -1)
220 return res
!= NULL
|| cur
;
224 * Merge the results for the expression tree rooted at e
225 * into the the result list htab.
227 static struct ohash
*
228 manmerge(struct expr
*e
, struct ohash
*htab
)
232 return manmerge_term(e
, htab
);
234 return manmerge_or(e
->child
, htab
);
236 return manmerge_and(e
->child
, htab
);
242 static struct ohash
*
243 manmerge_term(struct expr
*e
, struct ohash
*htab
)
245 struct dbm_res res
, *rp
;
251 htab
= mandoc_malloc(sizeof(*htab
));
252 mandoc_ohash_init(htab
, 4, offsetof(struct dbm_res
, page
));
255 for (im
= 0, ib
= 1; im
< KEY_MAX
; im
++, ib
<<= 1) {
256 if ((e
->bits
& ib
) == 0)
261 dbm_page_byarch(&e
->match
);
264 dbm_page_bysect(&e
->match
);
267 dbm_page_byname(&e
->match
);
270 dbm_page_bydesc(&e
->match
);
273 dbm_page_bymacro(im
- 2, &e
->match
);
278 * When hashing for deduplication, use the unique
279 * page ID itself instead of a hash function;
280 * that is quite efficient.
284 res
= dbm_page_next();
287 slot
= ohash_lookup_memory(htab
,
288 (char *)&res
, sizeof(res
.page
), res
.page
);
289 if ((rp
= ohash_find(htab
, slot
)) != NULL
) {
290 rp
->bits
|= res
.bits
;
293 rp
= mandoc_malloc(sizeof(*rp
));
295 ohash_insert(htab
, slot
, rp
);
301 static struct ohash
*
302 manmerge_or(struct expr
*e
, struct ohash
*htab
)
305 htab
= manmerge(e
, htab
);
311 static struct ohash
*
312 manmerge_and(struct expr
*e
, struct ohash
*htab
)
314 struct ohash
*hand
, *h1
, *h2
;
316 unsigned int slot1
, slot2
;
318 /* Evaluate the first term of the AND clause. */
320 hand
= manmerge(e
, NULL
);
322 while ((e
= e
->next
) != NULL
) {
324 /* Evaluate the next term and prepare for ANDing. */
326 h2
= manmerge(e
, NULL
);
327 if (ohash_entries(h2
) < ohash_entries(hand
)) {
332 hand
= mandoc_malloc(sizeof(*hand
));
333 mandoc_ohash_init(hand
, 4, offsetof(struct dbm_res
, page
));
335 /* Keep all pages that are in both result sets. */
337 for (res
= ohash_first(h1
, &slot1
); res
!= NULL
;
338 res
= ohash_next(h1
, &slot1
)) {
339 if (ohash_find(h2
, ohash_lookup_memory(h2
,
340 (char *)res
, sizeof(res
->page
),
344 ohash_insert(hand
, ohash_lookup_memory(hand
,
345 (char *)res
, sizeof(res
->page
),
349 /* Discard the merged results. */
351 for (res
= ohash_first(h2
, &slot2
); res
!= NULL
;
352 res
= ohash_next(h2
, &slot2
))
360 /* Merge the result of the AND into htab. */
365 for (res
= ohash_first(hand
, &slot1
); res
!= NULL
;
366 res
= ohash_next(hand
, &slot1
)) {
367 slot2
= ohash_lookup_memory(htab
,
368 (char *)res
, sizeof(res
->page
), res
->page
);
369 if (ohash_find(htab
, slot2
) == NULL
)
370 ohash_insert(htab
, slot2
, res
);
375 /* Discard the merged result. */
383 mansearch_free(struct manpage
*res
, size_t sz
)
387 for (i
= 0; i
< sz
; i
++) {
396 manpage_compare(const void *vp1
, const void *vp2
)
398 const struct manpage
*mp1
, *mp2
;
399 const char *cp1
, *cp2
;
405 if ((diff
= mp2
->bits
- mp1
->bits
) ||
406 (diff
= mp1
->sec
- mp2
->sec
))
409 /* Fall back to alphabetic ordering of names. */
410 sz1
= strcspn(mp1
->names
, "(");
411 sz2
= strcspn(mp2
->names
, "(");
414 if ((diff
= strncasecmp(mp1
->names
, mp2
->names
, sz1
)))
417 /* For identical names and sections, prefer arch-dependent. */
418 cp1
= strchr(mp1
->names
+ sz1
, '/');
419 cp2
= strchr(mp2
->names
+ sz2
, '/');
420 return cp1
!= NULL
&& cp2
!= NULL
? strcasecmp(cp1
, cp2
) :
421 cp1
!= NULL
? -1 : cp2
!= NULL
? 1 : 0;
425 buildnames(const struct dbm_page
*page
)
430 sz
= lstlen(page
->name
, 2) + 1 + lstlen(page
->sect
, 2) +
431 (page
->arch
== NULL
? 0 : 1 + lstlen(page
->arch
, 2)) + 2;
432 buf
= mandoc_malloc(sz
);
434 lstcat(buf
, &i
, page
->name
, ", ");
436 lstcat(buf
, &i
, page
->sect
, ", ");
437 if (page
->arch
!= NULL
) {
439 lstcat(buf
, &i
, page
->arch
, ", ");
448 * Count the buffer space needed to print the NUL-terminated
449 * list of NUL-terminated strings, when printing sep separator
450 * characters between strings.
453 lstlen(const char *cp
, size_t sep
)
457 for (sz
= 0; *cp
!= '\0'; cp
++) {
459 /* Skip names appearing only in the SYNOPSIS. */
460 if (*cp
<= (char)(NAME_SYN
& NAME_MASK
)) {
466 /* Skip name class markers. */
470 /* Print a separator before each but the first string. */
474 /* Copy one string. */
475 while (*cp
!= '\0') {
484 * Print the NUL-terminated list of NUL-terminated strings
485 * into the buffer, seperating strings with sep.
488 lstcat(char *buf
, size_t *i
, const char *cp
, const char *sep
)
493 for (i_start
= *i
; *cp
!= '\0'; cp
++) {
495 /* Skip names appearing only in the SYNOPSIS. */
496 if (*cp
<= (char)(NAME_SYN
& NAME_MASK
)) {
502 /* Skip name class markers. */
506 /* Print a separator before each but the first string. */
513 /* Copy one string. */
521 * Return 1 if the string *want occurs in any of the strings
522 * in the NUL-terminated string list *have, or 0 otherwise.
523 * If either argument is NULL or empty, assume no filtering
524 * is desired and return 1.
527 lstmatch(const char *want
, const char *have
)
529 if (want
== NULL
|| have
== NULL
|| *have
== '\0')
531 while (*have
!= '\0') {
532 if (strcasestr(have
, want
) != NULL
)
534 have
= strchr(have
, '\0') + 1;
540 * Build a list of values taken by the macro im in the manual page.
543 buildoutput(size_t im
, struct dbm_page
*page
)
545 const char *oldoutput
, *sep
, *input
;
546 char *output
, *newoutput
, *value
;
551 return mandoc_strdup(page
->desc
);
569 sz
= lstlen(input
, 3) + 1;
570 output
= mandoc_malloc(sz
);
572 lstcat(output
, &i
, input
, " # ");
579 dbm_macro_bypage(im
- 2, page
->addr
);
580 while ((value
= dbm_macro_next()) != NULL
) {
581 if (output
== NULL
) {
588 mandoc_asprintf(&newoutput
, "%s%s%s", oldoutput
, sep
, value
);
596 * Compile a set of string tokens into an expression.
597 * Tokens in "argv" are assumed to be individual expression atoms (e.g.,
598 * "(", "foo=bar", etc.).
601 exprcomp(const struct mansearch
*search
, int argc
, char *argv
[], int *argi
)
603 struct expr
*parent
, *child
;
604 int needterm
, nested
;
606 if ((nested
= *argi
) == argc
)
609 parent
= child
= NULL
;
610 while (*argi
< argc
) {
611 if (strcmp(")", argv
[*argi
]) == 0) {
613 warnx("missing term "
614 "before closing parenthesis");
618 warnx("ignoring unmatched right parenthesis");
622 if (strcmp("-o", argv
[*argi
]) == 0) {
625 warnx("ignoring -o after %s",
628 warnx("ignoring initial -o");
636 child
= expr_and(search
, argc
, argv
, argi
);
639 if (parent
== NULL
) {
640 parent
= mandoc_calloc(1, sizeof(*parent
));
641 parent
->type
= EXPR_OR
;
643 parent
->child
= child
;
645 child
->next
= expr_and(search
, argc
, argv
, argi
);
648 if (needterm
&& *argi
)
649 warnx("ignoring trailing %s", argv
[*argi
- 1]);
650 return parent
== NULL
? child
: parent
;
654 expr_and(const struct mansearch
*search
, int argc
, char *argv
[], int *argi
)
656 struct expr
*parent
, *child
;
660 parent
= child
= NULL
;
661 while (*argi
< argc
) {
662 if (strcmp(")", argv
[*argi
]) == 0) {
664 warnx("missing term "
665 "before closing parenthesis");
669 if (strcmp("-o", argv
[*argi
]) == 0)
671 if (strcmp("-a", argv
[*argi
]) == 0) {
674 warnx("ignoring -a after %s",
677 warnx("ignoring initial -a");
686 child
= exprterm(search
, argc
, argv
, argi
);
692 if (parent
== NULL
) {
693 parent
= mandoc_calloc(1, sizeof(*parent
));
694 parent
->type
= EXPR_AND
;
696 parent
->child
= child
;
698 child
->next
= exprterm(search
, argc
, argv
, argi
);
699 if (child
->next
!= NULL
) {
704 if (needterm
&& *argi
)
705 warnx("ignoring trailing %s", argv
[*argi
- 1]);
706 return parent
== NULL
? child
: parent
;
710 exprterm(const struct mansearch
*search
, int argc
, char *argv
[], int *argi
)
718 if (strcmp("(", argv
[*argi
]) == 0) {
720 e
= exprcomp(search
, argc
, argv
, argi
);
722 assert(strcmp(")", argv
[*argi
]) == 0);
725 warnx("unclosed parenthesis");
729 if (strcmp("-i", argv
[*argi
]) == 0 && *argi
+ 1 < argc
) {
735 e
= mandoc_calloc(1, sizeof(*e
));
741 if (search
->argmode
== ARG_NAME
) {
743 e
->match
.type
= DBM_EXACT
;
744 e
->match
.str
= argv
[(*argi
)++];
749 * Separate macro keys from search string.
750 * If needed, request regular expression handling.
753 if (search
->argmode
== ARG_WORD
) {
755 e
->match
.type
= DBM_REGEX
;
757 mandoc_asprintf(&val
, "[[:<:]]%s[[:>:]]", argv
[*argi
]);
759 mandoc_asprintf(&val
, "\\<%s\\>", argv
[*argi
]);
761 mandoc_asprintf(&val
,
762 "(^|[^a-zA-Z01-9_])%s([^a-zA-Z01-9_]|$)", argv
[*argi
]);
765 } else if ((val
= strpbrk(argv
[*argi
], "=~")) == NULL
) {
766 e
->bits
= TYPE_Nm
| TYPE_Nd
;
767 e
->match
.type
= DBM_SUB
;
768 e
->match
.str
= argv
[*argi
];
770 if (val
== argv
[*argi
])
771 e
->bits
= TYPE_Nm
| TYPE_Nd
;
773 e
->match
.type
= DBM_SUB
;
774 e
->match
.str
= val
+ 1;
776 e
->match
.type
= DBM_REGEX
;
778 if (strstr(argv
[*argi
], "arch") != NULL
)
782 /* Compile regular expressions. */
784 if (e
->match
.type
== DBM_REGEX
) {
785 e
->match
.re
= mandoc_malloc(sizeof(*e
->match
.re
));
786 irc
= regcomp(e
->match
.re
, val
,
787 REG_EXTENDED
| REG_NOSUB
| (cs
? 0 : REG_ICASE
));
789 regerror(irc
, e
->match
.re
, errbuf
, sizeof(errbuf
));
790 warnx("regcomp /%s/: %s", val
, errbuf
);
792 if (search
->argmode
== ARG_WORD
)
808 * Parse out all possible fields.
809 * If the field doesn't resolve, bail.
812 while (NULL
!= (key
= strsep(&argv
[*argi
], ","))) {
815 for (i
= 0, iterbit
= 1; i
< KEY_MAX
; i
++, iterbit
<<= 1) {
816 if (0 == strcasecmp(key
, mansearch_keynames
[i
])) {
822 if (strcasecmp(key
, "any"))
823 warnx("treating unknown key "
824 "\"%s\" as \"any\"", key
);
834 exprfree(struct expr
*e
)
838 if (e
->child
!= NULL
)