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