sys/src/cmd/dict/dict.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <bio.h>
   4 #include <regexp.h>
   5 #include <ctype.h>
   6 #include "dict.h"
   7
   8 /*
   9  * Assumed index file structure: lines of form
  10  *      [^\t]+\t[0-9]+
  11  * First field is key, second is byte offset into dictionary.
  12  * Should be sorted with args -u -t'    ' +0f -1 +0 -1 +1n -2
  13  */
  14 typedef struct Addr Addr;
  15
  16 struct Addr {
  17         int     n;              /* number of offsets */
  18         int     cur;            /* current position within doff array */
  19         int     maxn;           /* actual current size of doff array */
  20         ulong   doff[1];        /* doff[maxn], with 0..n-1 significant */
  21 };
  22
  23 Biobuf  binbuf;
  24 Biobuf  boutbuf;
  25 Biobuf  *bin = &binbuf;         /* user cmd input */
  26 Biobuf  *bout = &boutbuf;       /* output */
  27 Biobuf  *bdict;                 /* dictionary */
  28 Biobuf  *bindex;                /* index file */
  29 long    indextop;               /* index offset at end of file */
  30 int     lastcmd;                /* last executed command */
  31 Addr    *dot;                   /* "current" address */
  32 Dict    *dict;                  /* current dictionary */
  33 int     linelen;
  34 int     breaklen = 60;
  35 int     outinhibit;
  36 int     debug;
  37
  38 void    execcmd(int);
  39 int     getpref(char*, Rune*);
  40 Entry   getentry(int);
  41 int     getfield(Rune*);
  42 long    locate(Rune*);
  43 int     parseaddr(char*, char**);
  44 int     parsecmd(char*);
  45 int     search(char*, int);
  46 long    seeknextline(Biobuf*, long);
  47 void    setdotnext(void);
  48 void    setdotprev(void);
  49 void    sortaddr(Addr*);
  50 void    usage(void);
  51
  52 enum {
  53         Plen=300,       /* max length of a search pattern */
  54         Fieldlen=200,   /* max length of an index field */
  55         Aslots=10,      /* initial number of slots in an address */
  56 };
  57
  58 void
  59 main(int argc, char **argv)
  60 {
  61         int i, cmd, kflag;
  62         char *line, *p;
  63
  64         Binit(&binbuf, 0, OREAD);
  65         Binit(&boutbuf, 1, OWRITE);
  66         kflag = 0;
  67         line = 0;
  68         dict = 0;
  69         for(i=0; dicts[i].name; i++){
  70                 if(access(dicts[i].path, 0)>=0 && access(dicts[i].indexpath, 0)>=0){
  71                         dict = &dicts[i];
  72                         break;
  73                 }
  74         }
  75         ARGBEGIN {
  76                 case 'd':
  77                         p = EARGF(usage());
  78                         dict = 0;
  79                         for(i=0; dicts[i].name; i++)
  80                                 if(strcmp(p, dicts[i].name)==0) {
  81                                         dict = &dicts[i];
  82                                         break;
  83                                 }
  84                         if(!dict)
  85                                 usage();
  86                         break;
  87                 case 'c':
  88                         line = EARGF(usage());
  89                         break;
  90                 case 'k':
  91                         kflag++;
  92                         break;
  93                 case 'D':
  94                         debug++;
  95                         break;
  96                 default:
  97                         usage();
  98         }ARGEND
  99         if(dict == 0){
 100                 err("no dictionaries present on this system");
 101                 exits("nodict");
 102         }
 103
 104         if(kflag) {
 105                 (*dict->printkey)();
 106                 exits(0);
 107         }
 108         if(argc > 1)
 109                 usage();
 110         else if(argc == 1) {
 111                 if(line)
 112                         usage();
 113                 p = argv[0];
 114                 line = malloc(strlen(p)+5);
 115                 sprint(line, "/%s/P\n", p);
 116         }
 117         bdict = Bopen(dict->path, OREAD);
 118         if(!bdict) {
 119                 err("can't open dictionary %s", dict->path);
 120                 exits("nodict");
 121         }
 122         bindex = Bopen(dict->indexpath, OREAD);
 123         if(!bindex) {
 124                 err("can't open index %s", dict->indexpath);
 125                 exits("noindex");
 126         }
 127         indextop = Bseek(bindex, 0L, 2);
 128
 129         dot = malloc(sizeof(Addr)+(Aslots-1)*sizeof(ulong));
 130         dot->n = 0;
 131         dot->cur = 0;
 132         dot->maxn = Aslots;
 133         lastcmd = 0;
 134
 135         if(line) {
 136                 cmd = parsecmd(line);
 137                 if(cmd)
 138                         execcmd(cmd);
 139         } else {
 140                 for(;;) {
 141                         Bprint(bout, "*");
 142                         Bflush(bout);
 143                         line = Brdline(bin, '\n');
 144                         linelen = 0;
 145                         if(!line)
 146                                 break;
 147                         cmd = parsecmd(line);
 148                         if(cmd) {
 149                                 execcmd(cmd);
 150                                 lastcmd = cmd;
 151                         }
 152                 }
 153         }
 154         exits(0);
 155 }
 156
 157 void
 158 usage(void)
 159 {
 160         int i;
 161         char *a, *b;
 162
 163         Bprint(bout, "usage: %s [-k] [-d dict] [-c cmd] [pattern]\n", argv0);
 164         Bprint(bout, "dictionaries (brackets mark dictionaries not present on this system):\n");
 165         for(i = 0; dicts[i].name; i++){
 166                 a = b = "";
 167                 if(access(dicts[i].path, 0)<0 || access(dicts[i].indexpath, 0)<0){
 168                         a = "[";
 169                         b = "]";
 170                 }
 171                 Bprint(bout, "   %s%s\t%s%s\n", a, dicts[i].name, dicts[i].desc, b);
 172         }
 173         exits("usage");
 174 }
 175
 176 int
 177 parsecmd(char *line)
 178 {
 179         char *e;
 180         int cmd, ans;
 181
 182         if(parseaddr(line, &e) >= 0)
 183                 line = e;
 184         else
 185                 return 0;
 186         cmd = *line;
 187         ans = cmd;
 188         if(isupper(cmd))
 189                 cmd = tolower(cmd);
 190         if(!(cmd == 'a' || cmd == 'h' || cmd == 'p' || cmd == 'r' ||
 191              cmd == '\n')) {
 192                 err("unknown command %c", cmd);
 193                 return 0;
 194         }
 195         if(cmd == '\n')
 196                 switch(lastcmd) {
 197                         case 0: ans = 'H'; break;
 198                         case 'H':       ans = 'p'; break;
 199                         default :       ans = lastcmd; break;
 200                 }
 201         else if(line[1] != '\n' && line[1] != 0)
 202                 err("extra stuff after command %c ignored", cmd);
 203         return ans;
 204 }
 205
 206 void
 207 execcmd(int cmd)
 208 {
 209         Entry e;
 210         int cur, doall;
 211
 212         if(isupper(cmd)) {
 213                 doall = 1;
 214                 cmd = tolower(cmd);
 215                 cur = 0;
 216         } else {
 217                 doall = 0;
 218                 cur = dot->cur;
 219         }
 220
 221         if(debug && doall && cmd == 'a')
 222                 Bprint(bout, "%d entries, cur=%d\n", dot->n, cur+1);
 223         for(;;){
 224                 if(cur >= dot->n)
 225                         break;
 226                 if(doall) {
 227                         Bprint(bout, "%d\t", cur+1);
 228                         linelen += 4 + (cur >= 10);
 229                 }
 230                 switch(cmd) {
 231                 case 'a':
 232                         Bprint(bout, "#%lud\n", dot->doff[cur]);
 233                         break;
 234                 case 'h':
 235                 case 'p':
 236                 case 'r':
 237                         e = getentry(cur);
 238                         (*dict->printentry)(e, cmd);
 239                         break;
 240                 }
 241                 cur++;
 242                 if(doall) {
 243                         if(cmd == 'p' || cmd == 'r') {
 244                                 Bputc(bout, '\n');
 245                                 linelen = 0;
 246                         }
 247                 } else
 248                         break;
 249         }
 250         if(cur >= dot->n)
 251                 cur = 0;
 252         dot->cur = cur;
 253 }
 254
 255 /*
 256  * Address syntax: ('.' | '/' re '/' | '!' re '!' | number | '#' number) ('+' | '-')*
 257  * Answer goes in dot.
 258  * Return -1 if address starts, but get error.
 259  * Return 0 if no address.
 260  */
 261 int
 262 parseaddr(char *line, char **eptr)
 263 {
 264         int delim, plen;
 265         ulong v;
 266         char *e;
 267         char pat[Plen];
 268
 269         if(*line == '/' || *line == '!') {
 270                 /* anchored regular expression match; '!' means no folding */
 271                 if(*line == '/') {
 272                         delim = '/';
 273                         e = strpbrk(line+1, "/\n");
 274                 } else {
 275                         delim = '!';
 276                         e = strpbrk(line+1, "!\n");
 277                 }
 278                 plen = e-line-1;
 279                 if(plen >= Plen-3) {
 280                         err("pattern too big");
 281                         return -1;
 282                 }
 283                 pat[0] = '^';
 284                 memcpy(pat+1, line+1, plen);
 285                 pat[plen+1] = '$';
 286                 pat[plen+2] = 0;
 287                 if(*e == '\n')
 288                         line = e;
 289                 else
 290                         line = e+1;
 291                 if(!search(pat, delim == '/')) {
 292                         err("pattern not found");
 293                         return -1;
 294                 }
 295         } else if(*line == '#') {
 296                 /* absolute byte offset into dictionary */
 297                 line++;
 298                 if(!isdigit(*line))
 299                         return -1;
 300                 v = strtoul(line, &e, 10);
 301                 line = e;
 302                 dot->doff[0] = v;
 303                 dot->n = 1;
 304                 dot->cur = 0;
 305         } else if(isdigit(*line)) {
 306                 v = strtoul(line, &e, 10);
 307                 line = e;
 308                 if(v < 1 || v > dot->n)
 309                         err(".%d not in range [1,%d], ignored",
 310                                 v, dot->n);
 311                 else
 312                         dot->cur = v-1;
 313         } else if(*line == '.') {
 314                 line++;
 315         } else {
 316                 *eptr = line;
 317                 return 0;
 318         }
 319         while(*line == '+' || *line == '-') {
 320                 if(*line == '+')
 321                         setdotnext();
 322                 else
 323                         setdotprev();
 324                 line++;
 325         }
 326         *eptr = line;
 327         return 1;
 328 }
 329
 330 /*
 331  * Index file is sorted by folded field1.
 332  * Method: find pre, a folded prefix of r.e. pat,
 333  * and then low = offset to beginning of
 334  * line in index file where first match of prefix occurs.
 335  * Then go through index until prefix no longer matches,
 336  * adding each line that matches real pattern to dot.
 337  * Finally, sort dot offsets (uniquing).
 338  * We know pat len < Plen, and that it is surrounded by ^..$
 339  */
 340 int
 341 search(char *pat, int dofold)
 342 {
 343         int needre, prelen, match, n;
 344         Reprog *re;
 345         long ioff, v;
 346         Rune pre[Plen];
 347         Rune lit[Plen];
 348         Rune entry[Fieldlen];
 349         char fpat[Plen];
 350
 351         prelen = getpref(pat+1, pre);
 352         if(pat[prelen+1] == 0 || pat[prelen+1] == '$') {
 353                 runestrcpy(lit, pre);
 354                 if(dofold)
 355                         fold(lit);
 356                 needre = 0;
 357                 SET(re);
 358         } else {
 359                 needre = 1;
 360                 if(dofold) {
 361                         foldre(fpat, pat);
 362                         re = regcomp(fpat);
 363                 } else
 364                         re = regcomp(pat);
 365         }
 366         fold(pre);
 367         ioff = locate(pre);
 368         if(ioff < 0)
 369                 return 0;
 370         dot->n = 0;
 371         Bseek(bindex, ioff, 0);
 372         for(;;) {
 373                 if(!getfield(entry))
 374                         break;
 375                 if(dofold)
 376                         fold(entry);
 377                 if(needre)
 378                         match = rregexec(re, entry, 0, 0);
 379                 else
 380                         match = (acomp(lit, entry) == 0);
 381                 if(match) {
 382                         if(!getfield(entry))
 383                                 break;
 384                         v = runetol(entry);
 385                         if(dot->n >= dot->maxn) {
 386                                 n = 2*dot->maxn;
 387                                 dot = realloc(dot,
 388                                         sizeof(Addr)+(n-1)*sizeof(long));
 389                                 if(dot == nil)
 390                                         sysfatal("realloc: %r");
 391                                 dot->maxn = n;
 392                         }
 393                         dot->doff[dot->n++] = v;
 394                 } else {
 395                         if(!dofold)
 396                                 fold(entry);
 397                         if(*pre) {
 398                                 n = acomp(pre, entry);
 399                                 if(n < -1 || (!needre && n < 0))
 400                                         break;
 401                         }
 402                         /* get to next index entry */
 403                         if(!getfield(entry))
 404                                 break;
 405                 }
 406         }
 407         sortaddr(dot);
 408         dot->cur = 0;
 409         return dot->n;
 410 }
 411
 412 /*
 413  * Return offset in index file of first line whose folded
 414  * first field has pre as a prefix.  -1 if none found.
 415  */
 416 long
 417 locate(Rune *pre)
 418 {
 419         long top, bot, mid;
 420         Rune entry[Fieldlen];
 421
 422         if(*pre == 0)
 423                 return 0;
 424         bot = 0;
 425         top = indextop;
 426         if(debug>1)
 427                 fprint(2, "locate looking for prefix %S\n", pre);
 428         for(;;) {
 429                 /*
 430                  * Loop invariant: foldkey(bot) < pre <= foldkey(top)
 431                  * and bot < top, and bot,top point at beginning of lines
 432                  */
 433                 mid = (top+bot) / 2;
 434                 mid = seeknextline(bindex, mid);
 435                 if(debug > 1)
 436                         fprint(2, "bot=%ld, mid=%ld->%ld, top=%ld\n",
 437                                 bot, (top+bot) / 2, mid, top);
 438                 if(mid == top || !getfield(entry))
 439                         break;
 440                 if(debug > 1)
 441                         fprint(2, "key=%S\n", entry);
 442                 /*
 443                  * here mid is strictly between bot and top
 444                  */
 445                 fold(entry);
 446                 if(acomp(pre, entry) <= 0)
 447                         top = mid;
 448                 else
 449                         bot = mid;
 450         }
 451         /*
 452          * bot < top, but they don't necessarily point at successive lines
 453          * Use linear search from bot to find first line that pre is a
 454          * prefix of
 455          */
 456         while((bot = seeknextline(bindex, bot)) <= top) {
 457                 if(!getfield(entry))
 458                         return -1;
 459                 if(debug > 1)
 460                         fprint(2, "key=%S\n", entry);
 461                 fold(entry);
 462                 switch(acomp(pre, entry)) {
 463                 case -2:
 464                         return -1;
 465                 case -1:
 466                 case 0:
 467                         return bot;
 468                 case 1:
 469                 case 2:
 470                         continue;
 471                 }
 472         }
 473         return -1;
 474
 475 }
 476
 477 /*
 478  * Get prefix of non re-metacharacters, runified, into pre,
 479  * and return length
 480  */
 481 int
 482 getpref(char *pat, Rune *pre)
 483 {
 484         int n, r;
 485         char *p;
 486
 487         p = pat;
 488         while(*p) {
 489                 n = chartorune(pre, p);
 490                 r = *pre;
 491                 switch(r) {
 492                 case L'.': case L'*': case L'+': case L'?':
 493                 case L'[': case L']': case L'(': case ')':
 494                 case L'|': case L'^': case L'$':
 495                         *pre = 0;
 496                         return p-pat;
 497                 case L'\\':
 498                         p += n;
 499                         p += chartorune(++pre, p);
 500                         pre++;
 501                         break;
 502                 default:
 503                         p += n;
 504                         pre++;
 505                 }
 506         }
 507         return p-pat;
 508 }
 509
 510 long
 511 seeknextline(Biobuf *b, long off)
 512 {
 513         long c;
 514
 515         Bseek(b, off, 0);
 516         do {
 517                 c = Bgetrune(b);
 518         } while(c>=0 && c!='\n');
 519         return Boffset(b);
 520 }
 521
 522 /*
 523  * Get next field out of index file (either tab- or nl- terminated)
 524  * Answer in *rp, assumed to be Fieldlen long.
 525  * Return 0 if read error first.
 526  */
 527 int
 528 getfield(Rune *rp)
 529 {
 530         long c;
 531         int n;
 532
 533         for(n=Fieldlen; n-- > 0; ) {
 534                 if ((c = Bgetrune(bindex)) < 0)
 535                         return 0;
 536                 if(c == '\t' || c == '\n') {
 537                         *rp = L'\0';
 538                         return 1;
 539                 }
 540                 *rp++ = c;
 541         }
 542         err("word too long");
 543         return 0;
 544 }
 545
 546 /*
 547  * A compare longs function suitable for qsort
 548  */
 549 static int
 550 longcmp(void *av, void *bv)
 551 {
 552         long v;
 553         long *a, *b;
 554
 555         a = av;
 556         b = bv;
 557
 558         v = *a - *b;
 559         if(v < 0)
 560                 return -1;
 561         else if(v == 0)
 562                 return 0;
 563         else
 564                 return 1;
 565 }
 566
 567 void
 568 sortaddr(Addr *a)
 569 {
 570         int i, j;
 571         long v;
 572
 573         if(a->n <= 1)
 574                 return;
 575
 576         qsort(a->doff, a->n, sizeof(long), longcmp);
 577
 578         /* remove duplicates */
 579         for(i=0, j=0; j < a->n; j++) {
 580                 v = a->doff[j];
 581                 if(i > 0 && v == a->doff[i-1])
 582                         continue;
 583                 a->doff[i++] = v;
 584         }
 585         a->n = i;
 586 }
 587
 588 Entry
 589 getentry(int i)
 590 {
 591         long b, e, n;
 592         static Entry ans;
 593         static int anslen = 0;
 594
 595         b = dot->doff[i];
 596         e = (*dict->nextoff)(b+1);
 597         ans.doff = b;
 598         if(e < 0) {
 599                 err("couldn't seek to entry");
 600                 ans.start = 0;
 601                 ans.end = 0;
 602         } else {
 603                 n = e-b;
 604                 if(n+1 > anslen) {
 605                         ans.start = realloc(ans.start, n+1);
 606                         if(ans.start == nil)
 607                                 sysfatal("realloc: %r");
 608                         anslen = n+1;
 609                 }
 610                 Bseek(bdict, b, 0);
 611                 n = Bread(bdict, ans.start, n);
 612                 ans.end = ans.start + n;
 613                 *ans.end = 0;
 614         }
 615         return ans;
 616 }
 617
 618 void
 619 setdotnext(void)
 620 {
 621         long b;
 622
 623         b = (*dict->nextoff)(dot->doff[dot->cur]+1);
 624         if(b < 0) {
 625                 err("couldn't find a next entry");
 626                 return;
 627         }
 628         dot->doff[0] = b;
 629         dot->n = 1;
 630         dot->cur = 0;
 631 }
 632
 633 void
 634 setdotprev(void)
 635 {
 636         int tryback;
 637         long here, last, p;
 638
 639         if(dot->cur < 0 || dot->cur >= dot->n)
 640                 return;
 641         tryback = 2000;
 642         here = dot->doff[dot->cur];
 643         last = 0;
 644         while(last == 0) {
 645                 p = here - tryback;
 646                 if(p < 0)
 647                         p = 0;
 648                 for(;;) {
 649                         p = (*dict->nextoff)(p+1);
 650                         if(p < 0)
 651                                 return; /* shouldn't happen */
 652                         if(p >= here)
 653                                 break;
 654                         last = p;
 655                 }
 656                 if(!last) {
 657                         if(here - tryback < 0) {
 658                                 err("can't find a previous entry");
 659                                 return;
 660                         }
 661                         tryback = 2*tryback;
 662                 }
 663         }
 664         dot->doff[0] = last;
 665         dot->n = 1;
 666         dot->cur = 0;
 667 }