src/libs/libbib/linear.cpp

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