lib/misc/fts/trie-fd.c

   1 /*
   2  * libjsongit2 - trie file functions
   3  *
   4  * Copyright (C) 2018 Andy Green <andy@warmcat.com>
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation:
   9  *  version 2.1 of the License.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19  *  MA  02110-1301  USA
  20  */
  21
  22 #include "core/private.h"
  23 #include "misc/fts/private.h"
  24
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <assert.h>
  28 #include <fcntl.h>
  29 #include <sys/types.h>
  30 #include <sys/stat.h>
  31
  32 #define AC_COUNT_STASHED_CHILDREN 8
  33
  34 struct ch {
  35         jg2_file_offset ofs;
  36         char name[64];
  37         int inst;
  38         int child_agg;
  39         int name_length;
  40         int effpos;
  41         int descendents;
  42 };
  43
  44 struct wac {
  45         struct ch ch[AC_COUNT_STASHED_CHILDREN];
  46
  47         jg2_file_offset self;
  48         jg2_file_offset tifs;
  49         int child_count;
  50         int child;
  51
  52         int agg;
  53         int desc;
  54         char done_children;
  55         char once;
  56 };
  57
  58 struct linetable {
  59         struct linetable *next;
  60
  61         int chunk_line_number_start;
  62         int chunk_line_number_count;
  63
  64         off_t chunk_filepos_start;
  65
  66         off_t vli_ofs_in_index;
  67 };
  68
  69 static uint32_t
  70 b32(unsigned char *b)
  71 {
  72         return (b[0] << 24) | (b[1] << 16) | (b[2] << 8) | b[3];
  73 }
  74
  75 static uint16_t
  76 b16(unsigned char *b)
  77 {
  78         return (b[0] << 8) | b[1];
  79 }
  80
  81 static int
  82 lws_fts_filepath(struct lws_fts_file *jtf, int filepath_index, char *result,
  83                  size_t len, uint32_t *ofs_linetable, uint32_t *lines)
  84 {
  85         unsigned char buf[256 + 15];
  86         uint32_t flen;
  87         int ra, bp = 0;
  88         size_t m;
  89         off_t o;
  90
  91         if (filepath_index > jtf->filepaths)
  92                 return 1;
  93
  94         if (lseek(jtf->fd, jtf->filepath_table + (4 * filepath_index),
  95                         SEEK_SET) < 0) {
  96                 lwsl_err("%s: unable to seek\n", __func__);
  97
  98                 return 1;
  99         }
 100
 101         ra = read(jtf->fd, buf, 4);
 102         if (ra < 0)
 103                 return 1;
 104
 105         o = (unsigned int)b32(buf);
 106         if (lseek(jtf->fd, o, SEEK_SET) < 0) {
 107                 lwsl_err("%s: unable to seek\n", __func__);
 108
 109                 return 1;
 110         }
 111
 112         ra = read(jtf->fd, buf, sizeof(buf));
 113         if (ra < 0)
 114                 return 1;
 115
 116         if (ofs_linetable)
 117                 bp += rq32(&buf[bp], ofs_linetable);
 118         else
 119                 bp += rq32(&buf[bp], &flen);
 120         if (lines)
 121                 bp += rq32(&buf[bp], lines);
 122         else
 123                 bp += rq32(&buf[bp], &flen);
 124         bp += rq32(&buf[bp], &flen);
 125
 126         m = flen;
 127         if (len - 1 < m)
 128                 m = flen - 1;
 129
 130         strncpy(result, (char *)&buf[bp], m);
 131         result[m] = '\0';
 132         result[len - 1] = '\0';
 133
 134         return 0;
 135 }
 136
 137 /*
 138  * returns -1 for fail or fd open on the trie file.
 139  *
 140  * *root is set to the position of the root trie entry.
 141  * *flen is set to the length of the whole file
 142  */
 143
 144 int
 145 lws_fts_adopt(struct lws_fts_file *jtf)
 146 {
 147         unsigned char buf[256];
 148         off_t ot;
 149
 150         if (read(jtf->fd, buf, TRIE_FILE_HDR_SIZE) != TRIE_FILE_HDR_SIZE) {
 151                 lwsl_err("%s: unable to read file header\n", __func__);
 152                 goto bail;
 153         }
 154
 155         if (buf[0] != 0xca || buf[1] != 0x7a ||
 156             buf[2] != 0x5f || buf[3] != 0x75) {
 157                 lwsl_err("%s: bad magic %02X %02X %02X %02X\n", __func__,
 158                          buf[0], buf[1], buf[2], buf[3]);
 159                 goto bail;
 160         }
 161
 162         jtf->root = b32(&buf[4]);
 163
 164         ot = lseek(jtf->fd, 0, SEEK_END);
 165         if (ot < 0) {
 166                 lwsl_err("%s: unable to seek\n", __func__);
 167
 168                 goto bail;
 169         }
 170         jtf->flen = ot;
 171
 172         if (jtf->flen != b32(&buf[8])) {
 173                 lwsl_err("%s: file size doesn't match expected\n", __func__);
 174
 175                 goto bail;
 176         }
 177
 178         jtf->filepath_table = b32(&buf[12]);
 179         jtf->filepaths = b32(&buf[16]);
 180
 181         return jtf->fd;
 182
 183 bail:
 184         return -1;
 185 }
 186
 187 struct lws_fts_file *
 188 lws_fts_open(const char *filepath)
 189 {
 190         struct lws_fts_file *jtf;
 191
 192         jtf = lws_malloc(sizeof(*jtf), "fts open");
 193         if (!jtf)
 194                 goto bail1;
 195
 196         jtf->fd = open(filepath, O_RDONLY);
 197         if (jtf->fd < 0) {
 198                 lwsl_err("%s: unable to open %s\n", __func__, filepath);
 199                 goto bail2;
 200         }
 201
 202         if (lws_fts_adopt(jtf) < 0)
 203                 goto bail3;
 204
 205         return jtf;
 206
 207 bail3:
 208         close(jtf->fd);
 209 bail2:
 210         lws_free(jtf);
 211 bail1:
 212         return NULL;
 213 }
 214
 215 void
 216 lws_fts_close(struct lws_fts_file *jtf)
 217 {
 218         close(jtf->fd);
 219         lws_free(jtf);
 220 }
 221
 222 #define grab(_pos, _size) { \
 223                 bp = 0; \
 224                 if (lseek(jtf->fd, _pos, SEEK_SET) < 0) { \
 225                         lwsl_err("%s: unable to seek\n", __func__); \
 226 \
 227                         goto bail; \
 228                 } \
 229 \
 230                 ra = read(jtf->fd, buf, _size); \
 231                 if (ra < 0) \
 232                         goto bail; \
 233 }
 234
 235 static struct linetable *
 236 lws_fts_cache_chunktable(struct lws_fts_file *jtf, uint32_t ofs_linetable,
 237                          struct lwsac **linetable_head)
 238 {
 239         struct linetable *lt, *first = NULL, **prev = NULL;
 240         unsigned char buf[8];
 241         int line = 1, bp, ra;
 242         off_t cfs = 0;
 243
 244         *linetable_head = NULL;
 245
 246         do {
 247                 grab(ofs_linetable, sizeof(buf));
 248
 249                 lt = lwsac_use(linetable_head, sizeof(*lt), 0);
 250                 if (!lt)
 251                         goto bail;
 252                 if (!first)
 253                         first = lt;
 254
 255                 lt->next = NULL;
 256                 if (prev)
 257                         *prev = lt;
 258                 prev = &lt->next;
 259
 260                 lt->chunk_line_number_start = line;
 261                 lt->chunk_line_number_count = b16(&buf[bp + 2]);
 262                 lt->vli_ofs_in_index = ofs_linetable + 8;
 263                 lt->chunk_filepos_start = cfs;
 264
 265                 line += lt->chunk_line_number_count;
 266
 267                 cfs += b32(&buf[bp + 4]);
 268                 ofs_linetable += b16(&buf[bp]);
 269
 270         } while (b16(&buf[bp]));
 271
 272         return first;
 273
 274 bail:
 275         lwsac_free(linetable_head);
 276
 277         return NULL;
 278 }
 279
 280 static int
 281 lws_fts_getfileoffset(struct lws_fts_file *jtf, struct linetable *ltstart,
 282                       int line, off_t *_ofs)
 283 {
 284         struct linetable *lt = ltstart;
 285         unsigned char buf[LWS_FTS_LINES_PER_CHUNK * 5];
 286         uint32_t ll;
 287         off_t ofs;
 288         int bp, ra;
 289
 290         /* first figure out which chunk */
 291
 292         do {
 293                 if (line >= lt->chunk_line_number_start &&
 294                     line < lt->chunk_line_number_start +
 295                             lt->chunk_line_number_count)
 296                         break;
 297
 298                 lt = lt->next;
 299         } while (lt);
 300
 301         if (!lt)
 302                 goto bail;
 303
 304         /* we know it's in this chunk */
 305
 306         ofs = lt->chunk_filepos_start;
 307         line -= lt->chunk_line_number_start;
 308
 309         grab(lt->vli_ofs_in_index, sizeof(buf));
 310
 311         bp = 0;
 312         while (line) {
 313                 bp += rq32(&buf[bp], &ll);
 314                 ofs += ll;
 315                 line--;
 316         }
 317
 318         /* we know the offset it is at in the original file */
 319
 320         *_ofs = ofs;
 321
 322         return 0;
 323
 324 bail:
 325         lwsl_info("%s: bail %d\n", __func__, line);
 326
 327         return 1;
 328 }
 329
 330 static int
 331 ac_record(struct lws_fts_file *jtf, struct lwsac **results_head,
 332           const char *needle, int pos, struct wac *s, int sp,
 333           uint32_t instances, uint32_t agg_instances, uint32_t children,
 334           struct lws_fts_result_autocomplete ***ppac)
 335 {
 336         struct lws_fts_result_autocomplete *ac;
 337         int n, m;
 338         char *p;
 339
 340         if (!instances && !agg_instances)
 341                 return 1;
 342
 343         m = pos;
 344         for (n = 1; n <= sp; n++)
 345                 m += s[n].ch[s[n].child - 1].name_length;
 346
 347         ac = lwsac_use(results_head, sizeof(*ac) + m + 1, 0);
 348         if (!ac)
 349                 return -1;
 350
 351         p = (char *)(ac + 1);
 352
 353         **ppac = ac;
 354         ac->next = NULL;
 355         *ppac = &ac->next;
 356         ac->instances = instances;
 357         ac->agg_instances = agg_instances;
 358         ac->ac_length = m;
 359         ac->has_children = !!children;
 360         ac->elided = 0;
 361
 362         memcpy(p, needle, pos);
 363         p += pos;
 364
 365         for (n = 1; n <= sp; n++) {
 366                 int w = s[n].child - 1;
 367
 368                 memcpy(p, s[n].ch[w].name, s[n].ch[w].name_length);
 369                 p += s[n].ch[w].name_length;
 370         }
 371         p = (char *)(ac + 1);
 372         p[m] = '\0';
 373
 374         /*
 375          * deduct this child's instance weight from his antecdents to track
 376          * relative path attractiveness dynamically, after we already used its
 377          * best results (children are sorted best-first)
 378          */
 379         for (n = sp; n >= 0; n--) {
 380                 s[n].ch[s[n].child - 1].child_agg -= instances;
 381                 s[n].agg -= instances;
 382         }
 383
 384         return 0;
 385 }
 386
 387 struct lws_fts_result *
 388 lws_fts_search(struct lws_fts_file *jtf, struct lws_fts_search_params *ftsp)
 389 {
 390         uint32_t children, instances, co, sl, agg, slt, chunk,
 391                  fileofs_tif_start, desc, agg_instances;
 392         int pos = 0, n, m, nl, bp, base = 0, ra, palm, budget, sp, ofd = -1;
 393         unsigned long long tf = lws_now_usecs();
 394         struct lws_fts_result_autocomplete **pac = NULL;
 395         char stasis, nac = 0, credible, needle[32];
 396         struct lws_fts_result_filepath *fp;
 397         struct lws_fts_result *result;
 398         unsigned char buf[4096];
 399         off_t o, child_ofs;
 400         struct wac s[128];
 401
 402         ftsp->results_head = NULL;
 403
 404         if (!ftsp->needle)
 405                 return NULL;
 406
 407         nl = (int)strlen(ftsp->needle);
 408         if ((size_t)nl > sizeof(needle) - 2)
 409                 return NULL;
 410
 411         result = lwsac_use(&ftsp->results_head, sizeof(*result), 0);
 412         if (!result)
 413                 return NULL;
 414
 415         /* start with no results... */
 416
 417         result->autocomplete_head = NULL;
 418         pac = &result->autocomplete_head;
 419         result->filepath_head = NULL;
 420         result->duration_ms = 0;
 421         result->effective_flags = ftsp->flags;
 422
 423         palm = 0;
 424
 425         for (n = 0; n < nl; n++)
 426                 needle[n] = tolower(ftsp->needle[n]);
 427         needle[nl] = '\0';
 428
 429         o = jtf->root;
 430         do {
 431                 bp = 0;
 432                 base = 0;
 433
 434                 grab(o, sizeof(buf));
 435
 436                 child_ofs = o + bp;
 437                 bp += rq32(&buf[bp], &fileofs_tif_start);
 438                 bp += rq32(&buf[bp], &children);
 439                 bp += rq32(&buf[bp], &instances);
 440                 bp += rq32(&buf[bp], &agg_instances);
 441                 palm = pos;
 442
 443                 /* the children follow here */
 444
 445                 if (pos == nl) {
 446
 447                         nac = 0;
 448                         if (!fileofs_tif_start)
 449                                 /*
 450                                  * we matched, but there are no instances of
 451                                  * this, it's actually an intermediate
 452                                  */
 453
 454                                 goto autocomp;
 455
 456                         /* we leave with bp positioned at the instance list */
 457
 458                         o = fileofs_tif_start;
 459                         grab(o, sizeof(buf));
 460                         break;
 461                 }
 462
 463                 if (ra - bp < 1024) {
 464
 465                         /*
 466                          * We don't have enough.  So reload the buffer starting
 467                          * at where we got to.
 468                          */
 469
 470                         base += bp;
 471                         grab(o + base, sizeof(buf));
 472                 }
 473
 474                 /* gets set if any child COULD match needle if it went on */
 475
 476                 credible = 0;
 477                 for (n = 0; (uint32_t)n < children; n++) {
 478                         uint32_t inst;
 479
 480                         bp += rq32(&buf[bp], &co);
 481                         bp += rq32(&buf[bp], &inst);
 482                         bp += rq32(&buf[bp], &agg);
 483                         bp += rq32(&buf[bp], &desc);
 484                         bp += rq32(&buf[bp], &sl);
 485
 486                         if (sl > (uint32_t)(nl - pos)) {
 487
 488                                 /*
 489                                  * it can't be a match because it's longer than
 490                                  * our needle string (but that leaves it as a
 491                                  * perfectly fine autocomplete candidate)
 492                                  */
 493                                 size_t g = nl - pos;
 494
 495                                 /*
 496                                  * "credible" means at least one child matches
 497                                  * all the chars in needle up to as many as it
 498                                  * has.  If not "credible" this path cannot
 499                                  * match.
 500                                  */
 501                                 if (!strncmp((char *)&buf[bp], &needle[pos], g))
 502                                         credible = 1;
 503                                 else
 504                                         /*
 505                                          * deflate the parent agg using the
 506                                          * knowledge this child is not on the
 507                                          * path shown by the remainder of needle
 508                                          */
 509                                         agg_instances -= agg;
 510
 511                                 nac = 0;
 512                                 bp += sl;
 513                                 slt = 0;
 514                                 pos = palm;
 515                                 goto ensure;
 516                         }
 517
 518                         /* the comparison string potentially has huge length */
 519
 520                         slt = sl;
 521                         while (slt) {
 522
 523                                 /*
 524                                  * the strategy is to compare whatever we have
 525                                  * lying around, then bring in more if it didn't
 526                                  * fail to match yet.  That way we don't bring
 527                                  * in anything we could already have known was
 528                                  * not needed due to a match fail.
 529                                  */
 530
 531                                 chunk = ra - bp;
 532                                 if (chunk > slt)
 533                                         chunk = slt;
 534
 535                                 if ((chunk == 1 && needle[pos] != buf[bp]) ||
 536                                     (chunk != 1 &&
 537                                      memcmp(&needle[pos], &buf[bp], chunk))) {
 538
 539                                         /*
 540                                          * it doesn't match... so nothing can
 541                                          * autocomplete this...
 542                                          */
 543                                         bp += slt;
 544                                         slt = 0;
 545                                         nac = 1;
 546                                         goto ensure;
 547                                 }
 548
 549                                 slt -= chunk;
 550                                 pos += chunk;
 551                                 bp += chunk;
 552
 553                                 /* so far, it matches */
 554
 555                                 if (!slt) {
 556                                         /* we matched the whole thing */
 557                                         o = co;
 558                                         if (!co)
 559                                                 goto bail;
 560                                         n = (int)children;
 561                                         credible = 1;
 562                                 }
 563
 564 ensure:
 565                                 /*
 566                                  * do we have at least buf more to match, or the
 567                                  * remainder of the string, whichever is less?
 568                                  *
 569                                  * bp may exceed sizeof(buf) on no match path
 570                                  */
 571                                 chunk = sizeof(buf);
 572                                 if (slt < chunk)
 573                                         chunk = slt;
 574
 575                                 if (ra - bp >= (int)chunk)
 576                                         continue;
 577
 578                                 /*
 579                                  * We don't have enough.  So reload buf starting
 580                                  * at where we got to.
 581                                  */
 582                                 base += bp;
 583                                 grab(o + base, sizeof(buf));
 584
 585                         } /* while we are still comparing */
 586
 587                 } /* for each child */
 588
 589                 if ((uint32_t)n == children) {
 590                         if (!credible)
 591                                 goto bail;
 592
 593                         nac = 0;
 594                         goto autocomp;
 595                 }
 596         } while(1);
 597
 598         result->duration_ms = (int)((lws_now_usecs() - tf) / 1000);
 599
 600         if (!instances && !children)
 601                 return result;
 602
 603         /* the match list may easily exceed one read buffer load ... */
 604
 605         o += bp;
 606
 607         /*
 608          * Only do the file match list if it was requested in the search flags
 609          */
 610
 611         if (!(ftsp->flags & LWSFTS_F_QUERY_FILES))
 612                 goto autocomp;
 613
 614         do {
 615                 uint32_t fi, tot, line, ro, ofs_linetable, lines, fplen,
 616                         *u, _o;
 617                 struct lwsac *lt_head = NULL;
 618                 struct linetable *ltst;
 619                 char path[256], *pp;
 620                 int footprint;
 621                 off_t fo;
 622
 623                 ofd = -1;
 624                 grab(o, sizeof(buf));
 625
 626                 ro = o;
 627                 bp += rq32(&buf[bp], &_o);
 628                 o = _o;
 629
 630                 assert(!o || o > TRIE_FILE_HDR_SIZE);
 631
 632                 bp += rq32(&buf[bp], &fi);
 633                 bp += rq32(&buf[bp], &tot);
 634
 635                 if (lws_fts_filepath(jtf, fi, path, sizeof(path) - 1,
 636                                      &ofs_linetable, &lines)) {
 637                         lwsl_err("can't get filepath index %d\n", fi);
 638                         goto bail;
 639                 }
 640
 641                 if (ftsp->only_filepath && strcmp(path, ftsp->only_filepath))
 642                         continue;
 643
 644                 ltst = lws_fts_cache_chunktable(jtf, ofs_linetable, &lt_head);
 645                 if (!ltst)
 646                         goto bail;
 647
 648                 if (ftsp->flags & LWSFTS_F_QUERY_QUOTE_LINE) {
 649                         ofd = open(path, O_RDONLY);
 650                         if (ofd < 0) {
 651                                 lwsac_free(&lt_head);
 652                                 goto bail;
 653                         }
 654                 }
 655
 656                 fplen = (int)strlen(path);
 657                 footprint = sizeof(*fp) + fplen + 1;
 658                 if (ftsp->flags & LWSFTS_F_QUERY_FILE_LINES) {
 659                         /* line number and offset in file */
 660                         footprint += 2 * sizeof(uint32_t) * tot;
 661
 662                         if (ftsp->flags & LWSFTS_F_QUERY_QUOTE_LINE)
 663                                 /* pointer to quote string */
 664                                 footprint += sizeof(void *) * tot;
 665                 }
 666
 667                 fp = lwsac_use(&ftsp->results_head, footprint, 0);
 668                 if (!fp) {
 669                         lwsac_free(&lt_head);
 670                         goto bail;
 671                 }
 672
 673                 fp->filepath_length = fplen;
 674                 fp->lines_in_file = lines;
 675                 fp->matches = tot;
 676                 fp->matches_length = footprint - sizeof(*fp) - (fplen + 1);
 677                 fp->next = result->filepath_head;
 678                 result->filepath_head = fp;
 679
 680                 /* line table first so it can be aligned */
 681
 682                 u = (uint32_t*)(fp + 1);
 683
 684                 if (ftsp->flags & LWSFTS_F_QUERY_FILE_LINES) {
 685
 686                         /* for each line number */
 687
 688                         for (n = 0; (uint32_t)n < tot; n++) {
 689
 690                                 unsigned char lbuf[256], *p;
 691                                 char ebuf[384];
 692                                 const char **v;
 693                                 int m;
 694
 695                                 if ((ra - bp) < 8) {
 696                                         base += bp;
 697                                         grab(ro + base, sizeof(buf));
 698                                 }
 699
 700                                 bp += rq32(&buf[bp], &line);
 701                                 *u++ = line;
 702
 703                                 if (lws_fts_getfileoffset(jtf, ltst, line, &fo))
 704                                         continue;
 705
 706                                 *u++ = (uint32_t)fo;
 707
 708                                 if (!(ftsp->flags & LWSFTS_F_QUERY_QUOTE_LINE))
 709                                         continue;
 710
 711                                 if (lseek(ofd, fo, SEEK_SET) < 0)
 712                                         continue;
 713
 714                                 m = read(ofd, lbuf, sizeof(lbuf) - 1);
 715                                 if (m < 0)
 716                                         continue;
 717                                 lbuf[sizeof(lbuf) - 1] = '\0';
 718
 719                                 p = (unsigned char *)strchr((char *)lbuf, '\n');
 720                                 if (p)
 721                                         m = lws_ptr_diff(p, lbuf);
 722                                 lbuf[m] = '\0';
 723                                 p = (unsigned char *)strchr((char *)lbuf, '\r');
 724                                 if (p)
 725                                         m = lws_ptr_diff(p, lbuf);
 726                                 lbuf[m] = '\0';
 727
 728                                 lws_json_purify(ebuf, (const char *)lbuf,
 729                                                 sizeof(ebuf) - 1);
 730                                 m = (int)strlen(ebuf);
 731
 732                                 p = lwsac_use(&ftsp->results_head, m + 1, 0);
 733                                 if (!p) {
 734                                         lwsac_free(&lt_head);
 735                                         goto bail;
 736                                 }
 737
 738                                 memcpy(p, ebuf, m);
 739                                 p[m] = '\0';
 740                                 v = (const char **)u;
 741                                 *v = (const char *)p;
 742                                 u += sizeof(const char *) / sizeof(uint32_t);
 743                         }
 744                 }
 745
 746                 pp = ((char *)&fp[1]) + fp->matches_length;
 747                 memcpy(pp, path, fplen);
 748                 pp[fplen] = '\0';
 749
 750                 if (ofd >= 0) {
 751                         close(ofd);
 752                         ofd = -1;
 753                 }
 754
 755                 lwsac_free(&lt_head);
 756
 757                 if (ftsp->only_filepath)
 758                         break;
 759
 760         } while (o);
 761
 762         /* sort the instance file list by results density */
 763
 764         do {
 765                 struct lws_fts_result_filepath **prf, *rf1, *rf2;
 766
 767                 stasis = 1;
 768
 769                 /* bubble sort keeps going until nothing changed */
 770
 771                 prf = &result->filepath_head;
 772                 while (*prf) {
 773
 774                         rf1 = *prf;
 775                         rf2 = rf1->next;
 776
 777                         if (rf2 && rf1->lines_in_file && rf2->lines_in_file &&
 778                             ((rf1->matches * 1000) / rf1->lines_in_file) <
 779                             ((rf2->matches * 1000) / rf2->lines_in_file)) {
 780                                 stasis = 0;
 781
 782                                 *prf = rf2;
 783                                 rf1->next = rf2->next;
 784                                 rf2->next = rf1;
 785                         }
 786
 787                         prf = &(*prf)->next;
 788                 }
 789
 790         } while (!stasis);
 791
 792 autocomp:
 793
 794         if (!(ftsp->flags & LWSFTS_F_QUERY_AUTOCOMPLETE) || nac)
 795                 return result;
 796
 797         /*
 798          * autocomplete (ie, the descendent paths that yield the most hits)
 799          *
 800          * We actually need to spider the earliest terminal descendents from
 801          * the child we definitely got past, and present the first n terminal
 802          * strings.  The descendents are already sorted in order of highest
 803          * aggregated hits in their descendents first, so simply collecting n
 804          * earliest leaf children is enough.
 805          *
 806          * The leaf children may be quite deep down in a stack however.  So we
 807          * have to go through all the walking motions collecting and retaining
 808          * child into for when we come back up the walk.
 809          *
 810          * We can completely ignore file instances for this, we just need the
 811          * earliest children.  And we can restrict how many children we stash
 812          * in each stack level to eg, 5.
 813          *
 814          * child_ofs comes in pointing at the start of the trie entry that is
 815          * to be the starting point for making suggestions.
 816          */
 817
 818         budget = ftsp->max_autocomplete;
 819         base = 0;
 820         bp = 0;
 821         pac = &result->autocomplete_head;
 822         sp = 0;
 823         if (pos > (int)sizeof(s[sp].ch[0].name) - 1)
 824                 pos = (int)sizeof(s[sp].ch[0].name) - 1;
 825
 826         memset(&s[sp], 0, sizeof(s[sp]));
 827
 828         s[sp].child = 1;
 829         s[sp].tifs = fileofs_tif_start;
 830         s[sp].self = child_ofs;
 831         s[sp].ch[0].effpos = pos;
 832
 833         if (pos == nl)
 834                 n = ac_record(jtf, &ftsp->results_head, needle, pos, s, 0,
 835                               instances, agg_instances, children, &pac);
 836
 837         while (sp >= 0 && budget) {
 838                 int nobump = 0;
 839                 struct ch *tch = &s[sp].ch[s[sp].child - 1];
 840
 841                 grab(child_ofs, sizeof(buf));
 842
 843                 bp += rq32(&buf[bp], &fileofs_tif_start);
 844                 bp += rq32(&buf[bp], &children);
 845                 bp += rq32(&buf[bp], &instances);
 846                 bp += rq32(&buf[bp], &agg_instances);
 847
 848                 if (sp > 0 && s[sp - 1].done_children &&
 849                     tch->effpos + tch->name_length >= nl &&
 850                     tch->inst && fileofs_tif_start) {
 851                         n = ac_record(jtf, &ftsp->results_head, needle, pos, s,
 852                                       sp, tch->inst, tch->child_agg,
 853                                       tch->descendents, &pac);
 854                         if (n < 0)
 855                                 goto bail;
 856                         if (!n)
 857                                 if (--budget == 0)
 858                                         break;
 859                 }
 860
 861                 if (!s[sp].done_children && children) {
 862                         s[sp].done_children = 1;
 863                         sp++;
 864                         memset(&s[sp], 0, sizeof(s[sp]));
 865                         s[sp].tifs = fileofs_tif_start;
 866                         s[sp].self = child_ofs;
 867
 868                         for (n = 0; n < (int)children && s[sp].child_count <
 869                                             (int)LWS_ARRAY_SIZE(s[0].ch); n++) {
 870                                 uint32_t slen, cho, agg, inst;
 871                                 int i = s[sp].child_count;
 872                                 struct ch *ch = &s[sp].ch[i];
 873                                 size_t max;
 874
 875                                 bp += rq32(&buf[bp], &cho);
 876                                 bp += rq32(&buf[bp], &inst);
 877                                 bp += rq32(&buf[bp], &agg);
 878                                 bp += rq32(&buf[bp], &desc);
 879                                 bp += rq32(&buf[bp], &slen);
 880
 881                                 max = slen;
 882                                 if (max > sizeof(ch->name) - 1)
 883                                         max = sizeof(ch->name) - 1;
 884
 885                                 strncpy(ch->name, (char *)&buf[bp], max);
 886                                 bp += slen;
 887
 888                                 ch->name_length = (int)max;
 889                                 ch->name[sizeof(ch->name) - 1] = '\0';
 890                                 ch->inst = inst;
 891                                 ch->effpos =
 892                                        s[sp - 1].ch[s[sp - 1].child - 1].effpos;
 893
 894                                 ch->child_agg = agg;
 895                                 ch->descendents = desc;
 896
 897                                 /*
 898                                  * if we have more needle chars than we matched
 899                                  * to get this far, we can only allow potential
 900                                  * matches that are consistent with the
 901                                  * additional unmatched character(s)...
 902                                  */
 903
 904                                 m = nl - ch->effpos;
 905                                 if (m > ch->name_length)
 906                                         m = ch->name_length;
 907
 908                                 if (m > 0 &&
 909                                     strncmp(&needle[ch->effpos], ch->name, m))
 910                                         continue;
 911
 912                                 ch->effpos += m;
 913                                 s[sp].ch[s[sp].child_count++].ofs = cho;
 914                         }
 915
 916                 }
 917
 918                 while (sp >= 0 && s[sp].child >= s[sp].child_count) {
 919                         s[sp].done_children = 0;
 920                         sp--;
 921                 }
 922
 923                 /*
 924                  * Compare parent remaining agg vs parent's next siblings' still
 925                  * intact original agg... if the next sibling has more, abandon
 926                  * the parent path and go with the sibling... this keeps the
 927                  * autocomplete results related to popularity.
 928                  */
 929
 930                 nobump = 0;
 931                 n = sp - 1;
 932                 while (n >= 0) {
 933                         struct lws_fts_result_autocomplete *ac =
 934                                 (struct lws_fts_result_autocomplete *)pac;
 935
 936                         if (s[n].child < s[n].child_count &&
 937                             s[n].ch[s[n].child - 1].child_agg <
 938                                     s[n].ch[s[n].child].child_agg) {
 939
 940                                 if (pac)
 941                                         /*
 942                                          * mark the autocomplete result that
 943                                          * there were more children down his
 944                                          * path that we skipped in these results
 945                                          */
 946                                         ac->elided = 1;
 947
 948                                 for (m = n; m < sp + 1; m++)
 949                                         s[m].done_children = 0;
 950                                 sp = n;
 951                                 child_ofs = s[sp].ch[s[sp].child++].ofs;
 952                                 nobump = 1;
 953                         }
 954
 955                         n--;
 956                 }
 957
 958                 if (nobump || sp < 0)
 959                         continue;
 960
 961                 child_ofs = s[sp].ch[s[sp].child++].ofs;
 962         }
 963
 964         /* let's do a final sort into agg order */
 965
 966         do {
 967                 struct lws_fts_result_autocomplete *ac1, *ac2;
 968
 969                 stasis = 1;
 970
 971                 /* bubble sort keeps going until nothing changed */
 972
 973                 pac = &result->autocomplete_head;
 974                 while (*pac) {
 975
 976                         ac1 = *pac;
 977                         ac2 = ac1->next;
 978
 979                         if (ac2 && ac1->instances < ac2->instances) {
 980                                 stasis = 0;
 981
 982                                 *pac = ac2;
 983                                 ac1->next = ac2->next;
 984                                 ac2->next = ac1;
 985                         }
 986
 987                         pac = &(*pac)->next;
 988                 }
 989
 990         } while (!stasis);
 991
 992         return result;
 993
 994 bail:
 995         if (ofd >= 0)
 996                 close(ofd);
 997
 998         lwsl_info("%s: search ended up at bail\n", __func__);
 999
1000         return result;
1001 }