src/libs/libbib/index.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 <errno.h>
  24
  25 #include "posix.h"
  26 #include "cset.h"
  27 #include "cmap.h"
  28 #include "errarg.h"
  29 #include "error.h"
  30
  31 #include "refid.h"
  32 #include "search.h"
  33 #include "index.h"
  34 #include "defs.h"
  35
  36 #include "nonposix.h"
  37
  38 // Interface to mmap.
  39 extern "C" {
  40   void *mapread(int fd, int len);
  41   int unmap(void *, int len);
  42 }
  43
  44 #if 0
  45 const
  46 #endif
  47 int minus_one = -1;
  48
  49 int verify_flag = 0;
  50
  51 struct word_list;
  52
  53 class index_search_item : public search_item {
  54   search_item *out_of_date_files;
  55   index_header header;
  56   char *buffer;
  57   void *map_addr;
  58   int map_len;
  59   tag *tags;
  60   int *table;
  61   int *lists;
  62   char *pool;
  63   char *key_buffer;
  64   char *filename_buffer;
  65   int filename_buflen;
  66   char **common_words_table;
  67   int common_words_table_size;
  68   const char *ignore_fields;
  69   time_t mtime;
  70
  71   const char *do_verify();
  72   const int *search1(const char **pp, const char *end);
  73   const int *search(const char *ptr, int length, int **temp_listp);
  74   const char *munge_filename(const char *);
  75   void read_common_words_file();
  76   void add_out_of_date_file(int fd, const char *filename, int fid);
  77 public:
  78   index_search_item(const char *, int);
  79   ~index_search_item();
  80   int load(int fd);
  81   search_item_iterator *make_search_item_iterator(const char *);
  82   int verify();
  83   void check_files();
  84   int next_filename_id() const;
  85   friend class index_search_item_iterator;
  86 };
  87
  88 class index_search_item_iterator : public search_item_iterator {
  89   index_search_item *indx;
  90   search_item_iterator *out_of_date_files_iter;
  91   search_item *next_out_of_date_file;
  92   const int *found_list;
  93   int *temp_list;
  94   char *buf;
  95   int buflen;
  96   linear_searcher searcher;
  97   char *query;
  98   int get_tag(int tagno, const linear_searcher &, const char **, int *,
  99               reference_id *);
 100 public:
 101   index_search_item_iterator(index_search_item *, const char *);
 102   ~index_search_item_iterator();
 103   int next(const linear_searcher &, const char **, int *, reference_id *);
 104 };
 105
 106
 107 index_search_item::index_search_item(const char *filename, int fid)
 108 : search_item(filename, fid), out_of_date_files(0), buffer(0), map_addr(0),
 109   map_len(0), key_buffer(0), filename_buffer(0), filename_buflen(0),
 110   common_words_table(0)
 111 {
 112 }
 113
 114 index_search_item::~index_search_item()
 115 {
 116   if (buffer)
 117     free(buffer);
 118   if (map_addr) {
 119     if (unmap(map_addr, map_len) < 0)
 120       error("unmap: %1", strerror(errno));
 121   }
 122   while (out_of_date_files) {
 123     search_item *tem = out_of_date_files;
 124     out_of_date_files = out_of_date_files->next;
 125     delete tem;
 126   }
 127   a_delete filename_buffer;
 128   a_delete key_buffer;
 129   if (common_words_table) {
 130     for (int i = 0; i < common_words_table_size; i++)
 131       a_delete common_words_table[i];
 132     a_delete common_words_table;
 133   }
 134 }
 135
 136 class file_closer {
 137   int *fdp;
 138 public:
 139   file_closer(int &fd) : fdp(&fd) { }
 140   ~file_closer() { close(*fdp); }
 141 };
 142
 143 // Tell the compiler that a variable is intentionally unused.
 144 inline void unused(void *) { }
 145
 146 int index_search_item::load(int fd)
 147 {
 148   file_closer fd_closer(fd);    // close fd on return
 149   unused(&fd_closer);
 150   struct stat sb;
 151   if (fstat(fd, &sb) < 0) {
 152     error("can't fstat `%1': %2", name, strerror(errno));
 153     return 0;
 154   }
 155   if (!S_ISREG(sb.st_mode)) {
 156     error("`%1' is not a regular file", name);
 157     return 0;
 158   }
 159   mtime = sb.st_mtime;
 160   int size = int(sb.st_size);
 161   char *addr;
 162   map_addr = mapread(fd, size);
 163   if (map_addr) {
 164     addr = (char *)map_addr;
 165     map_len = size;
 166   }
 167   else {
 168     addr = buffer = (char *)malloc(size);
 169     if (buffer == 0) {
 170       error("can't allocate buffer for `%1'", name);
 171       return 0;
 172     }
 173     char *ptr = buffer;
 174     int bytes_to_read = size;
 175     while (bytes_to_read > 0) {
 176       int nread = read(fd, ptr, bytes_to_read);
 177       if (nread == 0) {
 178         error("unexpected EOF on `%1'", name);
 179         return 0;
 180       }
 181       if (nread < 0) {
 182         error("read error on `%1': %2", name, strerror(errno));
 183         return 0;
 184       }
 185       bytes_to_read -= nread;
 186       ptr += nread;
 187     }
 188   }
 189   header = *(index_header *)addr;
 190   if (header.magic != INDEX_MAGIC) {
 191     error("`%1' is not an index file: wrong magic number", name);
 192     return 0;
 193   }
 194   if (header.version != INDEX_VERSION) {
 195     error("version number in `%1' is wrong: was %2, should be %3",
 196           name, header.version, INDEX_VERSION);
 197     return 0;
 198   }
 199   int sz = (header.tags_size * sizeof(tag)
 200             + header.lists_size * sizeof(int)
 201             + header.table_size * sizeof(int)
 202             + header.strings_size
 203             + sizeof(header));
 204   if (sz != size) {
 205     error("size of `%1' is wrong: was %2, should be %3",
 206           name, size, sz);
 207     return 0;
 208   }
 209   tags = (tag *)(addr + sizeof(header));
 210   lists = (int *)(tags + header.tags_size);
 211   table = (int *)(lists + header.lists_size);
 212   pool = (char *)(table + header.table_size);
 213   ignore_fields = strchr(strchr(pool, '\0') + 1, '\0') + 1;
 214   key_buffer = new char[header.truncate];
 215   read_common_words_file();
 216   return 1;
 217 }
 218
 219 const char *index_search_item::do_verify()
 220 {
 221   if (tags == 0)
 222     return "not loaded";
 223   if (lists[header.lists_size - 1] >= 0)
 224     return "last list element not negative";
 225   int i;
 226   for (i = 0; i < header.table_size; i++) {
 227     int li = table[i];
 228     if (li >= header.lists_size)
 229       return "bad list index";
 230     if (li >= 0) {
 231       for (int *ptr = lists + li; *ptr >= 0; ptr++) {
 232         if (*ptr >= header.tags_size)
 233           return "bad tag index";
 234         if (*ptr >= ptr[1] && ptr[1] >= 0)
 235           return "list not ordered";
 236       }
 237     }
 238   }
 239   for (i = 0; i < header.tags_size; i++) {
 240     if (tags[i].filename_index >= header.strings_size)
 241       return "bad index in tags";
 242     if (tags[i].length < 0)
 243       return "bad length in tags";
 244     if (tags[i].start < 0)
 245       return "bad start in tags";
 246   }
 247   if (pool[header.strings_size - 1] != '\0')
 248     return "last character in pool not nul";
 249   return 0;
 250 }
 251
 252 int index_search_item::verify()
 253 {
 254   const char *reason = do_verify();
 255   if (!reason)
 256     return 1;
 257   error("`%1' is bad: %2", name, reason);
 258   return 0;
 259 }
 260
 261 int index_search_item::next_filename_id() const
 262 {
 263   return filename_id + header.strings_size + 1;
 264 }
 265
 266 search_item_iterator *index_search_item::make_search_item_iterator(
 267   const char *query)
 268 {
 269   return new index_search_item_iterator(this, query);
 270 }
 271
 272 search_item *make_index_search_item(const char *filename, int fid)
 273 {
 274   char *index_filename = new char[strlen(filename) + sizeof(INDEX_SUFFIX)];
 275   strcpy(index_filename, filename);
 276   strcat(index_filename, INDEX_SUFFIX);
 277   int fd = open(index_filename, O_RDONLY | O_BINARY);
 278   if (fd < 0)
 279     return 0;
 280   index_search_item *item = new index_search_item(index_filename, fid);
 281   a_delete index_filename;
 282   if (!item->load(fd)) {
 283     close(fd);
 284     delete item;
 285     return 0;
 286   }
 287   else if (verify_flag && !item->verify()) {
 288     delete item;
 289     return 0;
 290   }
 291   else {
 292     item->check_files();
 293     return item;
 294   }
 295 }
 296
 297
 298 index_search_item_iterator::index_search_item_iterator(index_search_item *ind,
 299                                                        const char *q)
 300 : indx(ind), out_of_date_files_iter(0), next_out_of_date_file(0), temp_list(0),
 301   buf(0), buflen(0),
 302   searcher(q, strlen(q), ind->ignore_fields, ind->header.truncate),
 303   query(strsave(q))
 304 {
 305   found_list = indx->search(q, strlen(q), &temp_list);
 306   if (!found_list) {
 307     found_list = &minus_one;
 308     warning("all keys would have been discarded in constructing index `%1'",
 309             indx->name);
 310   }
 311 }
 312
 313 index_search_item_iterator::~index_search_item_iterator()
 314 {
 315   a_delete temp_list;
 316   a_delete buf;
 317   a_delete query;
 318   delete out_of_date_files_iter;
 319 }
 320
 321 int index_search_item_iterator::next(const linear_searcher &,
 322                                      const char **pp, int *lenp,
 323                                      reference_id *ridp)
 324 {
 325   if (found_list) {
 326     for (;;) {
 327       int tagno = *found_list;
 328       if (tagno == -1)
 329         break;
 330       found_list++;
 331       if (get_tag(tagno, searcher, pp, lenp, ridp))
 332         return 1;
 333     }
 334     found_list = 0;
 335     next_out_of_date_file = indx->out_of_date_files;
 336   }
 337   while (next_out_of_date_file) {
 338     if (out_of_date_files_iter == 0)
 339       out_of_date_files_iter
 340         = next_out_of_date_file->make_search_item_iterator(query);
 341     if (out_of_date_files_iter->next(searcher, pp, lenp, ridp))
 342       return 1;
 343     delete out_of_date_files_iter;
 344     out_of_date_files_iter = 0;
 345     next_out_of_date_file = next_out_of_date_file->next;
 346   }
 347   return 0;
 348 }
 349
 350 int index_search_item_iterator::get_tag(int tagno,
 351                                         const linear_searcher &searchr,
 352                                         const char **pp, int *lenp,
 353                                         reference_id *ridp)
 354 {
 355   if (tagno < 0 || tagno >= indx->header.tags_size) {
 356     error("bad tag number");
 357     return 0;
 358   }
 359   tag *tp = indx->tags + tagno;
 360   const char *filename = indx->munge_filename(indx->pool + tp->filename_index);
 361   int fd = open(filename, O_RDONLY | O_BINARY);
 362   if (fd < 0) {
 363     error("can't open `%1': %2", filename, strerror(errno));
 364     return 0;
 365   }
 366   struct stat sb;
 367   if (fstat(fd, &sb) < 0) {
 368     error("can't fstat: %1", strerror(errno));
 369     close(fd);
 370     return 0;
 371   }
 372   time_t mtime = sb.st_mtime;
 373   if (mtime > indx->mtime) {
 374     indx->add_out_of_date_file(fd, filename,
 375                                indx->filename_id + tp->filename_index);
 376     return 0;
 377   }
 378   int res = 0;
 379   FILE *fp = fdopen(fd, FOPEN_RB);
 380   if (!fp) {
 381     error("fdopen failed");
 382     close(fd);
 383     return 0;
 384   }
 385   if (tp->start != 0 && fseek(fp, long(tp->start), 0) < 0)
 386     error("can't seek on `%1': %2", filename, strerror(errno));
 387   else {
 388     int length = tp->length;
 389     int err = 0;
 390     if (length == 0) {
 391       if (fstat(fileno(fp), &sb) < 0) {
 392         error("can't stat `%1': %2", filename, strerror(errno));
 393         err = 1;
 394       }
 395       else if (!S_ISREG(sb.st_mode)) {
 396         error("`%1' is not a regular file", filename);
 397         err = 1;
 398       }
 399       else
 400         length = int(sb.st_size);
 401     }
 402     if (!err) {
 403       if (length + 2 > buflen) {
 404         a_delete buf;
 405         buflen = length + 2;
 406         buf = new char[buflen];
 407       }
 408       if (fread(buf + 1, 1, length, fp) != (size_t)length)
 409         error("fread on `%1' failed: %2", filename, strerror(errno));
 410       else {
 411         buf[0] = '\n';
 412         // Remove the CR characters from CRLF pairs.
 413         int sidx = 1, didx = 1;
 414         for ( ; sidx < length + 1; sidx++, didx++)
 415           {
 416             if (buf[sidx] == '\r')
 417               {
 418                 if (buf[++sidx] != '\n')
 419                   buf[didx++] = '\r';
 420                 else
 421                   length--;
 422               }
 423             if (sidx != didx)
 424               buf[didx] = buf[sidx];
 425           }
 426         buf[length + 1] = '\n';
 427         res = searchr.search(buf + 1, buf + 2 + length, pp, lenp);
 428         if (res && ridp)
 429           *ridp = reference_id(indx->filename_id + tp->filename_index,
 430                                tp->start);
 431       }
 432     }
 433   }
 434   fclose(fp);
 435   return res;
 436 }
 437
 438 const char *index_search_item::munge_filename(const char *filename)
 439 {
 440   if (IS_ABSOLUTE(filename))
 441     return filename;
 442   const char *cwd = pool;
 443   int need_slash = (cwd[0] != 0
 444                     && strchr(DIR_SEPS, strchr(cwd, '\0')[-1]) == 0);
 445   int len = strlen(cwd) + strlen(filename) + need_slash + 1;
 446   if (len > filename_buflen) {
 447     a_delete filename_buffer;
 448     filename_buflen = len;
 449     filename_buffer = new char[len];
 450   }
 451   strcpy(filename_buffer, cwd);
 452   if (need_slash)
 453     strcat(filename_buffer, "/");
 454   strcat(filename_buffer, filename);
 455   return filename_buffer;
 456 }
 457
 458 const int *index_search_item::search1(const char **pp, const char *end)
 459 {
 460   while (*pp < end && !csalnum(**pp))
 461     *pp += 1;
 462   if (*pp >= end)
 463     return 0;
 464   const char *start = *pp;
 465   while (*pp < end && csalnum(**pp))
 466     *pp += 1;
 467   int len = *pp - start;
 468   if (len < header.shortest)
 469     return 0;
 470   if (len > header.truncate)
 471     len = header.truncate;
 472   int is_number = 1;
 473   for (int i = 0; i < len; i++)
 474     if (csdigit(start[i]))
 475       key_buffer[i] = start[i];
 476     else {
 477       key_buffer[i] = cmlower(start[i]);
 478       is_number = 0;
 479     }
 480   if (is_number && !(len == 4 && start[0] == '1' && start[1] == '9'))
 481     return 0;
 482   unsigned hc = hash(key_buffer, len);
 483   if (common_words_table) {
 484     for (int h = hc % common_words_table_size;
 485          common_words_table[h];
 486          --h) {
 487       if (strlen(common_words_table[h]) == (size_t)len
 488           && memcmp(common_words_table[h], key_buffer, len) == 0)
 489         return 0;
 490       if (h == 0)
 491         h = common_words_table_size;
 492     }
 493   }
 494   int li = table[int(hc % header.table_size)];
 495   return li < 0 ? &minus_one : lists + li;
 496 }
 497
 498 static void merge(int *result, const int *s1, const int *s2)
 499 {
 500   for (; *s1 >= 0; s1++) {
 501     while (*s2 >= 0 && *s2 < *s1)
 502       s2++;
 503     if (*s2 == *s1)
 504       *result++ = *s2;
 505   }
 506   *result++ = -1;
 507 }
 508
 509 const int *index_search_item::search(const char *ptr, int length,
 510                                      int **temp_listp)
 511 {
 512   const char *end = ptr + length;
 513   if (*temp_listp) {
 514     a_delete *temp_listp;
 515     *temp_listp = 0;
 516   }
 517   const int *first_list = 0;
 518   while (ptr < end && (first_list = search1(&ptr, end)) == 0)
 519     ;
 520   if (!first_list)
 521     return 0;
 522   if (*first_list < 0)
 523     return first_list;
 524   const int *second_list = 0;
 525   while (ptr < end && (second_list = search1(&ptr, end)) == 0)
 526     ;
 527   if (!second_list)
 528     return first_list;
 529   if (*second_list < 0)
 530     return second_list;
 531   const int *p;
 532   for (p = first_list; *p >= 0; p++)
 533     ;
 534   int len = p - first_list;
 535   for (p = second_list; *p >= 0; p++)
 536     ;
 537   if (p - second_list < len)
 538     len = p - second_list;
 539   int *matches = new int[len + 1];
 540   merge(matches, first_list, second_list);
 541   while (ptr < end) {
 542     const int *list = search1(&ptr, end);
 543     if (list != 0) {
 544       if (*list < 0) {
 545         a_delete matches;
 546         return list;
 547       }
 548       merge(matches, matches, list);
 549       if (*matches < 0) {
 550         a_delete matches;
 551         return &minus_one;
 552       }
 553     }
 554   }
 555   *temp_listp = matches;
 556   return matches;
 557 }
 558
 559 void index_search_item::read_common_words_file()
 560 {
 561   if (header.common <= 0)
 562     return;
 563   const char *common_words_file = munge_filename(strchr(pool, '\0') + 1);
 564   errno = 0;
 565   FILE *fp = fopen(common_words_file, "r");
 566   if (!fp) {
 567     error("can't open `%1': %2", common_words_file, strerror(errno));
 568     return;
 569   }
 570   common_words_table_size = 2*header.common + 1;
 571   while (!is_prime(common_words_table_size))
 572     common_words_table_size++;
 573   common_words_table = new char *[common_words_table_size];
 574   for (int i = 0; i < common_words_table_size; i++)
 575     common_words_table[i] = 0;
 576   int count = 0;
 577   int key_len = 0;
 578   for (;;) {
 579     int c = getc(fp);
 580     while (c != EOF && !csalnum(c))
 581       c = getc(fp);
 582     if (c == EOF)
 583       break;
 584     do {
 585       if (key_len < header.truncate)
 586         key_buffer[key_len++] = cmlower(c);
 587       c = getc(fp);
 588     } while (c != EOF && csalnum(c));
 589     if (key_len >= header.shortest) {
 590       int h = hash(key_buffer, key_len) % common_words_table_size;
 591       while (common_words_table[h]) {
 592         if (h == 0)
 593           h = common_words_table_size;
 594         --h;
 595       }
 596       common_words_table[h] = new char[key_len + 1];
 597       memcpy(common_words_table[h], key_buffer, key_len);
 598       common_words_table[h][key_len] = '\0';
 599     }
 600     if (++count >= header.common)
 601       break;
 602     key_len = 0;
 603     if (c == EOF)
 604       break;
 605   }
 606   fclose(fp);
 607 }
 608
 609 void index_search_item::add_out_of_date_file(int fd, const char *filename,
 610                                              int fid)
 611 {
 612   search_item **pp;
 613   for (pp = &out_of_date_files; *pp; pp = &(*pp)->next)
 614     if ((*pp)->is_named(filename))
 615       return;
 616   *pp = make_linear_search_item(fd, filename, fid);
 617   warning("`%1' modified since `%2' created", filename, name);
 618 }
 619
 620 void index_search_item::check_files()
 621 {
 622   const char *pool_end = pool + header.strings_size;
 623   for (const char *ptr = strchr(ignore_fields, '\0') + 1;
 624        ptr < pool_end;
 625        ptr = strchr(ptr, '\0') + 1) {
 626     const char *path = munge_filename(ptr);
 627     struct stat sb;
 628     if (stat(path, &sb) < 0)
 629       error("can't stat `%1': %2", path, strerror(errno));
 630     else if (sb.st_mtime > mtime) {
 631       int fd = open(path, O_RDONLY | O_BINARY);
 632       if (fd < 0)
 633         error("can't open `%1': %2", path, strerror(errno));
 634       else
 635         add_out_of_date_file(fd, path, filename_id + (ptr - pool));
 636     }
 637   }
 638 }