Line data Source code
1 : /* Copyright (C) 1989-2020 Free Software Foundation, Inc.
2 : Written by James Clark (jjc@jclark.com)
3 :
4 : This file is part of groff, the GNU roff typesetting system.
5 :
6 : groff is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation, either version 3 of the License, or
9 : (at your option) any later version.
10 :
11 : groff is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with this program. If not, see <http://www.gnu.org/licenses/>. */
18 :
19 : #ifdef HAVE_CONFIG_H
20 : #include <config.h>
21 : #endif
22 :
23 : #include <assert.h>
24 : #include <errno.h>
25 : #include <string.h> // strchr(), strerror()
26 :
27 : #include "lib.h"
28 :
29 : #include "posix.h"
30 : #include "errarg.h"
31 : #include "error.h"
32 : #include "cset.h"
33 : #include "cmap.h"
34 : #include "nonposix.h"
35 :
36 : #include "refid.h"
37 : #include "search.h"
38 :
39 : class file_buffer {
40 : char *buffer;
41 : char *bufend;
42 : public:
43 : file_buffer();
44 : ~file_buffer();
45 : int load(int fd, const char *filename);
46 : const char *get_start() const;
47 : const char *get_end() const;
48 : };
49 :
50 : typedef unsigned char uchar;
51 :
52 : static uchar map[256];
53 : static uchar inv_map[256][3];
54 :
55 : struct map_init {
56 : map_init();
57 : };
58 :
59 : static map_init the_map_init;
60 :
61 6 : map_init::map_init()
62 : {
63 : int i;
64 1542 : for (i = 0; i < 256; i++)
65 1536 : map[i] = csalnum(i) ? cmlower(i) : '\0';
66 1542 : for (i = 0; i < 256; i++) {
67 1536 : if (cslower(i)) {
68 156 : inv_map[i][0] = i;
69 156 : inv_map[i][1] = cmupper(i);
70 156 : inv_map[i][2] = '\0';
71 : }
72 1380 : else if (csdigit(i)) {
73 60 : inv_map[i][0] = i;
74 60 : inv_map[i][1] = 0;
75 : }
76 : else
77 1320 : inv_map[i][0] = '\0';
78 : }
79 6 : }
80 :
81 :
82 : class bmpattern {
83 : char *pat;
84 : int len;
85 : int delta[256];
86 : public:
87 : bmpattern(const char *pattern, int pattern_length);
88 : ~bmpattern();
89 : const char *search(const char *p, const char *end) const;
90 : int length() const;
91 : };
92 :
93 0 : bmpattern::bmpattern(const char *pattern, int pattern_length)
94 0 : : len(pattern_length)
95 : {
96 0 : pat = new char[len];
97 : int i;
98 0 : for (i = 0; i < len; i++)
99 0 : pat[i] = map[uchar(pattern[i])];
100 0 : for (i = 0; i < 256; i++)
101 0 : delta[i] = len;
102 0 : for (i = 0; i < len; i++)
103 0 : for (const unsigned char *inv = inv_map[uchar(pat[i])]; *inv; inv++)
104 0 : delta[*inv] = len - i - 1;
105 0 : }
106 :
107 0 : const char *bmpattern::search(const char *buf, const char *end) const
108 : {
109 0 : int buflen = end - buf;
110 0 : if (len > buflen)
111 0 : return 0;
112 : const char *strend;
113 0 : if (buflen > len*4)
114 0 : strend = end - len*4;
115 : else
116 0 : strend = buf;
117 0 : const char *k = buf + len - 1;
118 0 : const int *del = delta;
119 0 : const char *pattern = pat;
120 : for (;;) {
121 0 : while (k < strend) {
122 0 : int t = del[uchar(*k)];
123 0 : if (!t)
124 0 : break;
125 0 : k += t;
126 0 : k += del[uchar(*k)];
127 0 : k += del[uchar(*k)];
128 : }
129 0 : while (k < end && del[uchar(*k)] != 0)
130 0 : k++;
131 0 : if (k == end)
132 0 : break;
133 0 : int j = len - 1;
134 0 : const char *s = k;
135 : for (;;) {
136 0 : if (j == 0)
137 0 : return s;
138 0 : if (map[uchar(*--s)] != uchar(pattern[--j]))
139 0 : break;
140 : }
141 0 : k++;
142 0 : }
143 0 : return 0;
144 : }
145 :
146 0 : bmpattern::~bmpattern()
147 : {
148 0 : delete[] pat;
149 0 : }
150 :
151 0 : inline int bmpattern::length() const
152 : {
153 0 : return len;
154 : }
155 :
156 :
157 : static const char *find_end(const char *bufend, const char *p);
158 :
159 0 : const char *linear_searcher::search_and_check(const bmpattern *key,
160 : const char *buf, const char *bufend, const char **start) const
161 : {
162 0 : assert(buf[-1] == '\n');
163 0 : assert(bufend[-1] == '\n');
164 0 : const char *ptr = buf;
165 : for (;;) {
166 0 : const char *found = key->search(ptr, bufend);
167 0 : if (!found)
168 0 : break;
169 0 : if (check_match(buf, bufend, found, key->length(), &ptr, start))
170 0 : return found;
171 0 : }
172 0 : return 0;
173 : }
174 :
175 0 : static const char *skip_field(const char *end, const char *p)
176 : {
177 : for (;;)
178 0 : if (*p++ == '\n') {
179 0 : if (p == end || *p == '%')
180 : break;
181 : const char *q;
182 0 : for (q = p; *q == ' ' || *q == '\t'; q++)
183 : ;
184 0 : if (*q == '\n')
185 0 : break;
186 0 : p = q + 1;
187 0 : }
188 0 : return p;
189 : }
190 :
191 0 : static const char *find_end(const char *bufend, const char *p)
192 : {
193 : for (;;)
194 0 : if (*p++ == '\n') {
195 0 : if (p == bufend)
196 0 : break;
197 : const char *q;
198 0 : for (q = p; *q == ' ' || *q == '\t'; q++)
199 : ;
200 0 : if (*q == '\n')
201 0 : break;
202 0 : p = q + 1;
203 0 : }
204 0 : return p;
205 : }
206 :
207 :
208 0 : int linear_searcher::check_match(const char *buf, const char *bufend,
209 : const char *match, int matchlen,
210 : const char **cont, const char **start) const
211 : {
212 0 : *cont = match + 1;
213 : // The user is required to supply only the first truncate_len characters
214 : // of the key. If truncate_len <= 0, he must supply all the key.
215 0 : if ((truncate_len <= 0 || matchlen < truncate_len)
216 0 : && map[uchar(match[matchlen])] != '\0')
217 0 : return 0;
218 :
219 : // The character before the match must not be an alphanumeric
220 : // character (unless the alphanumeric character follows one or two
221 : // percent characters at the beginning of the line), nor must it be
222 : // a percent character at the beginning of a line, nor a percent
223 : // character following a percent character at the beginning of a
224 : // line.
225 :
226 0 : switch (match - buf) {
227 0 : case 0:
228 0 : break;
229 0 : case 1:
230 0 : if (match[-1] == '%' || map[uchar(match[-1])] != '\0')
231 0 : return 0;
232 0 : break;
233 0 : case 2:
234 0 : if (map[uchar(match[-1])] != '\0' && match[-2] != '%')
235 0 : return 0;
236 0 : if (match[-1] == '%'
237 0 : && (match[-2] == '\n' || match[-2] == '%'))
238 0 : return 0;
239 0 : break;
240 0 : default:
241 0 : if (map[uchar(match[-1])] != '\0'
242 0 : && !(match[-2] == '%'
243 0 : && (match[-3] == '\n'
244 0 : || (match[-3] == '%' && match[-4] == '\n'))))
245 0 : return 0;
246 0 : if (match[-1] == '%'
247 0 : && (match[-2] == '\n'
248 0 : || (match[-2] == '%' && match[-3] == '\n')))
249 0 : return 0;
250 : }
251 :
252 0 : const char *p = match;
253 0 : int had_percent = 0;
254 : for (;;) {
255 0 : if (*p == '\n') {
256 0 : if (!had_percent && p[1] == '%') {
257 0 : if (p[2] != '\0' && strchr(ignore_fields, p[2]) != 0) {
258 0 : *cont = skip_field(bufend, match + matchlen);
259 0 : return 0;
260 : }
261 0 : if (!start)
262 0 : break;
263 0 : had_percent = 1;
264 : }
265 0 : if (p <= buf) {
266 0 : if (start)
267 0 : *start = p + 1;
268 0 : return 1;
269 : }
270 : const char *q;
271 0 : for (q = p - 1; *q == ' ' || *q == '\t'; q--)
272 : ;
273 0 : if (*q == '\n') {
274 0 : if (start)
275 0 : *start = p + 1;
276 0 : break;
277 : }
278 0 : p = q;
279 : }
280 0 : p--;
281 0 : }
282 0 : return 1;
283 : }
284 :
285 1 : file_buffer::file_buffer()
286 1 : : buffer(0), bufend(0)
287 : {
288 1 : }
289 :
290 2 : file_buffer::~file_buffer()
291 : {
292 1 : delete[] buffer;
293 1 : }
294 :
295 0 : const char *file_buffer::get_start() const
296 : {
297 0 : return buffer ? buffer + 4 : 0;
298 : }
299 :
300 0 : const char *file_buffer::get_end() const
301 : {
302 0 : return bufend;
303 : }
304 :
305 1 : int file_buffer::load(int fd, const char *filename)
306 : {
307 : struct stat sb;
308 1 : if (fstat(fd, &sb) < 0)
309 0 : error("can't fstat '%1': %2", filename, strerror(errno));
310 1 : else if (!S_ISREG(sb.st_mode))
311 0 : error("'%1' is not a regular file", filename);
312 : else {
313 : // We need one character extra at the beginning for an additional newline
314 : // used as a sentinel. We get 4 instead so that the read buffer will be
315 : // word-aligned. This seems to make the read slightly faster. We also
316 : // need one character at the end also for an additional newline used as a
317 : // sentinel.
318 1 : int size = int(sb.st_size);
319 1 : buffer = new char[size + 4 + 1];
320 1 : int nread = read(fd, buffer + 4, size);
321 1 : if (nread < 0)
322 0 : error("error reading '%1': %2", filename, strerror(errno));
323 1 : else if (nread != size)
324 0 : error("size of '%1' decreased", filename);
325 : else {
326 : char c;
327 1 : nread = read(fd, &c, 1);
328 1 : if (nread != 0)
329 0 : error("size of '%1' increased", filename);
330 1 : else if (memchr(buffer + 4, '\0', size < 1024 ? size : 1024) != 0)
331 0 : error("database '%1' is a binary file", filename);
332 : else {
333 1 : close(fd);
334 1 : buffer[3] = '\n';
335 1 : int sidx = 4, didx = 4;
336 178 : for ( ; sidx < size + 4; sidx++, didx++)
337 : {
338 177 : if (buffer[sidx] == '\r')
339 : {
340 0 : if (buffer[++sidx] != '\n')
341 0 : buffer[didx++] = '\r';
342 : else
343 0 : size--;
344 : }
345 177 : if (sidx != didx)
346 0 : buffer[didx] = buffer[sidx];
347 : }
348 1 : bufend = buffer + 4 + size;
349 1 : if (bufend[-1] != '\n')
350 0 : *bufend++ = '\n';
351 1 : return 1;
352 : }
353 : }
354 0 : delete[] buffer;
355 0 : buffer = 0;
356 : }
357 0 : close(fd);
358 0 : return 0;
359 : }
360 :
361 0 : linear_searcher::linear_searcher(const char *query, int query_len,
362 0 : const char *ign, int trunc)
363 0 : : ignore_fields(ign), truncate_len(trunc), keys(0), nkeys(0)
364 : {
365 0 : const char *query_end = query + query_len;
366 0 : int nk = 0;
367 : const char *p;
368 0 : for (p = query; p < query_end; p++)
369 0 : if (map[uchar(*p)] != '\0'
370 0 : && (p[1] == '\0' || map[uchar(p[1])] == '\0'))
371 0 : nk++;
372 0 : if (nk == 0)
373 0 : return;
374 0 : keys = new bmpattern*[nk];
375 0 : p = query;
376 : for (;;) {
377 0 : while (p < query_end && map[uchar(*p)] == '\0')
378 0 : p++;
379 0 : if (p == query_end)
380 0 : break;
381 0 : const char *start = p;
382 0 : while (p < query_end && map[uchar(*p)] != '\0')
383 0 : p++;
384 0 : keys[nkeys++] = new bmpattern(start, p - start);
385 0 : }
386 0 : assert(nkeys <= nk);
387 0 : if (nkeys == 0) {
388 0 : delete[] keys;
389 0 : keys = 0;
390 : }
391 : }
392 :
393 0 : linear_searcher::~linear_searcher()
394 : {
395 0 : for (int i = 0; i < nkeys; i++)
396 0 : delete keys[i];
397 0 : delete[] keys;
398 0 : }
399 :
400 0 : int linear_searcher::search(const char *buffer, const char *bufend,
401 : const char **startp, int *lengthp) const
402 : {
403 0 : assert(bufend - buffer > 0);
404 0 : assert(buffer[-1] == '\n');
405 0 : assert(bufend[-1] == '\n');
406 0 : if (nkeys == 0)
407 0 : return 0;
408 : for (;;) {
409 : const char *refstart;
410 0 : const char *found = search_and_check(keys[0], buffer, bufend, &refstart);
411 0 : if (!found)
412 0 : break;
413 0 : const char *refend = find_end(bufend, found + keys[0]->length());
414 : int i;
415 0 : for (i = 1; i < nkeys; i++)
416 0 : if (!search_and_check(keys[i], refstart, refend))
417 0 : break;
418 0 : if (i >= nkeys) {
419 0 : *startp = refstart;
420 0 : *lengthp = refend - refstart;
421 0 : return 1;
422 : }
423 0 : buffer = refend;
424 0 : }
425 0 : return 0;
426 : }
427 :
428 : class linear_search_item : public search_item {
429 : file_buffer fbuf;
430 : public:
431 : linear_search_item(const char *filename, int fid);
432 : ~linear_search_item();
433 : int load(int fd);
434 : search_item_iterator *make_search_item_iterator(const char *);
435 : friend class linear_search_item_iterator;
436 : };
437 :
438 : class linear_search_item_iterator : public search_item_iterator {
439 : linear_search_item *lsi;
440 : int pos;
441 : public:
442 : linear_search_item_iterator(linear_search_item *, const char *query);
443 : ~linear_search_item_iterator();
444 : int next(const linear_searcher &, const char **ptr, int *lenp,
445 : reference_id *ridp);
446 : };
447 :
448 1 : search_item *make_linear_search_item(int fd, const char *filename, int fid)
449 : {
450 1 : linear_search_item *item = new linear_search_item(filename, fid);
451 1 : if (!item->load(fd)) {
452 0 : delete item;
453 0 : return 0;
454 : }
455 : else
456 1 : return item;
457 : }
458 :
459 1 : linear_search_item::linear_search_item(const char *filename, int fid)
460 1 : : search_item(filename, fid)
461 : {
462 1 : }
463 :
464 2 : linear_search_item::~linear_search_item()
465 : {
466 2 : }
467 :
468 1 : int linear_search_item::load(int fd)
469 : {
470 1 : return fbuf.load(fd, name);
471 : }
472 :
473 0 : search_item_iterator *linear_search_item::make_search_item_iterator(
474 : const char *query)
475 : {
476 0 : return new linear_search_item_iterator(this, query);
477 : }
478 :
479 0 : linear_search_item_iterator::linear_search_item_iterator(
480 0 : linear_search_item *p, const char *)
481 0 : : lsi(p), pos(0)
482 : {
483 0 : }
484 :
485 0 : linear_search_item_iterator::~linear_search_item_iterator()
486 : {
487 0 : }
488 :
489 0 : int linear_search_item_iterator::next(const linear_searcher &searcher,
490 : const char **startp, int *lengthp,
491 : reference_id *ridp)
492 : {
493 0 : const char *bufstart = lsi->fbuf.get_start();
494 0 : const char *bufend = lsi->fbuf.get_end();
495 0 : const char *ptr = bufstart + pos;
496 0 : if (ptr < bufend && searcher.search(ptr, bufend, startp, lengthp)) {
497 0 : pos = *startp + *lengthp - bufstart;
498 0 : if (ridp)
499 0 : *ridp = reference_id(lsi->filename_id, *startp - bufstart);
500 0 : return 1;
501 : }
502 : else
503 0 : return 0;
504 : }
505 :
506 : // Local Variables:
507 : // fill-column: 72
508 : // mode: C++
509 : // End:
510 : // vim: set cindent noexpandtab shiftwidth=2 textwidth=72:
|
