src/preproc/refer/label.ypp

   1 /* -*- C++ -*-
   2    Copyright (C) 1989-2018 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 %{
  21
  22 #include "refer.h"
  23 #include "refid.h"
  24 #include "ref.h"
  25 #include "token.h"
  26
  27 int yylex();
  28 void yyerror(const char *);
  29 int yyparse();
  30
  31 static const char *format_serial(char c, int n);
  32
  33 struct label_info {
  34   int start;
  35   int length;
  36   int count;
  37   int total;
  38   label_info(const string &);
  39 };
  40
  41 label_info *lookup_label(const string &label);
  42
  43 struct expression {
  44   enum {
  45     // Does the tentative label depend on the reference?
  46     CONTAINS_VARIABLE = 01,
  47     CONTAINS_STAR = 02,
  48     CONTAINS_FORMAT = 04,
  49     CONTAINS_AT = 010
  50   };
  51   virtual ~expression() { }
  52   virtual void evaluate(int, const reference &, string &,
  53                         substring_position &) = 0;
  54   virtual unsigned analyze() { return 0; }
  55 };
  56
  57 class at_expr : public expression {
  58 public:
  59   at_expr() { }
  60   void evaluate(int, const reference &, string &, substring_position &);
  61   unsigned analyze() { return CONTAINS_VARIABLE|CONTAINS_AT; }
  62 };
  63
  64 class format_expr : public expression {
  65   char type;
  66   int width;
  67   int first_number;
  68 public:
  69   format_expr(char c, int w = 0, int f = 1)
  70     : type(c), width(w), first_number(f) { }
  71   void evaluate(int, const reference &, string &, substring_position &);
  72   unsigned analyze() { return CONTAINS_FORMAT; }
  73 };
  74
  75 class field_expr : public expression {
  76   int number;
  77   char name;
  78 public:
  79   field_expr(char nm, int num) : number(num), name(nm) { }
  80   void evaluate(int, const reference &, string &, substring_position &);
  81   unsigned analyze() { return CONTAINS_VARIABLE; }
  82 };
  83
  84 class literal_expr : public expression {
  85   string s;
  86 public:
  87   literal_expr(const char *ptr, int len) : s(ptr, len) { }
  88   void evaluate(int, const reference &, string &, substring_position &);
  89 };
  90
  91 class unary_expr : public expression {
  92 protected:
  93   expression *expr;
  94 public:
  95   unary_expr(expression *e) : expr(e) { }
  96   ~unary_expr() { delete expr; }
  97   void evaluate(int, const reference &, string &, substring_position &) = 0;
  98   unsigned analyze() { return expr ? expr->analyze() : 0; }
  99 };
 100
 101 // This caches the analysis of an expression.
 102
 103 class analyzed_expr : public unary_expr {
 104   unsigned flags;
 105 public:
 106   analyzed_expr(expression *);
 107   void evaluate(int, const reference &, string &, substring_position &);
 108   unsigned analyze() { return flags; }
 109 };
 110
 111 class star_expr : public unary_expr {
 112 public:
 113   star_expr(expression *e) : unary_expr(e) { }
 114   void evaluate(int, const reference &, string &, substring_position &);
 115   unsigned analyze() {
 116     return ((expr ? (expr->analyze() & ~CONTAINS_VARIABLE) : 0)
 117             | CONTAINS_STAR);
 118   }
 119 };
 120
 121 typedef void map_func(const char *, const char *, string &);
 122
 123 class map_expr : public unary_expr {
 124   map_func *func;
 125 public:
 126   map_expr(expression *e, map_func *f) : unary_expr(e), func(f) { }
 127   void evaluate(int, const reference &, string &, substring_position &);
 128 };
 129
 130 typedef const char *extractor_func(const char *, const char *, const char **);
 131
 132 class extractor_expr : public unary_expr {
 133   int part;
 134   extractor_func *func;
 135 public:
 136   enum { BEFORE = +1, MATCH = 0, AFTER = -1 };
 137   extractor_expr(expression *e, extractor_func *f, int pt)
 138     : unary_expr(e), part(pt), func(f) { }
 139   void evaluate(int, const reference &, string &, substring_position &);
 140 };
 141
 142 class truncate_expr : public unary_expr {
 143   int n;
 144 public:
 145   truncate_expr(expression *e, int i) : unary_expr(e), n(i) { }
 146   void evaluate(int, const reference &, string &, substring_position &);
 147 };
 148
 149 class separator_expr : public unary_expr {
 150 public:
 151   separator_expr(expression *e) : unary_expr(e) { }
 152   void evaluate(int, const reference &, string &, substring_position &);
 153 };
 154
 155 class binary_expr : public expression {
 156 protected:
 157   expression *expr1;
 158   expression *expr2;
 159 public:
 160   binary_expr(expression *e1, expression *e2) : expr1(e1), expr2(e2) { }
 161   ~binary_expr() { delete expr1; delete expr2; }
 162   void evaluate(int, const reference &, string &, substring_position &) = 0;
 163   unsigned analyze() {
 164     return (expr1 ? expr1->analyze() : 0) | (expr2 ? expr2->analyze() : 0);
 165   }
 166 };
 167
 168 class alternative_expr : public binary_expr {
 169 public:
 170   alternative_expr(expression *e1, expression *e2) : binary_expr(e1, e2) { }
 171   void evaluate(int, const reference &, string &, substring_position &);
 172 };
 173
 174 class list_expr : public binary_expr {
 175 public:
 176   list_expr(expression *e1, expression *e2) : binary_expr(e1, e2) { }
 177   void evaluate(int, const reference &, string &, substring_position &);
 178 };
 179
 180 class substitute_expr : public binary_expr {
 181 public:
 182   substitute_expr(expression *e1, expression *e2) : binary_expr(e1, e2) { }
 183   void evaluate(int, const reference &, string &, substring_position &);
 184 };
 185
 186 class ternary_expr : public expression {
 187 protected:
 188   expression *expr1;
 189   expression *expr2;
 190   expression *expr3;
 191 public:
 192   ternary_expr(expression *e1, expression *e2, expression *e3)
 193     : expr1(e1), expr2(e2), expr3(e3) { }
 194   ~ternary_expr() { delete expr1; delete expr2; delete expr3; }
 195   void evaluate(int, const reference &, string &, substring_position &) = 0;
 196   unsigned analyze() {
 197     return ((expr1 ? expr1->analyze() : 0)
 198             | (expr2 ? expr2->analyze() : 0)
 199             | (expr3 ? expr3->analyze() : 0));
 200   }
 201 };
 202
 203 class conditional_expr : public ternary_expr {
 204 public:
 205   conditional_expr(expression *e1, expression *e2, expression *e3)
 206     : ternary_expr(e1, e2, e3) { }
 207   void evaluate(int, const reference &, string &, substring_position &);
 208 };
 209
 210 static expression *parsed_label = 0;
 211 static expression *parsed_date_label = 0;
 212 static expression *parsed_short_label = 0;
 213
 214 static expression *parse_result;
 215
 216 string literals;
 217
 218 %}
 219
 220 %union {
 221   int num;
 222   expression *expr;
 223   struct { int ndigits; int val; } dig;
 224   struct { int start; int len; } str;
 225 }
 226
 227 /* uppercase or lowercase letter */
 228 %token <num> TOKEN_LETTER
 229 /* literal characters */
 230 %token <str> TOKEN_LITERAL
 231 /* digit */
 232 %token <num> TOKEN_DIGIT
 233
 234 %type <expr> conditional
 235 %type <expr> alternative
 236 %type <expr> list
 237 %type <expr> string
 238 %type <expr> substitute
 239 %type <expr> optional_conditional
 240 %type <num> number
 241 %type <dig> digits
 242 %type <num> optional_number
 243 %type <num> flag
 244
 245 %%
 246
 247 expr:
 248         optional_conditional
 249                 { parse_result = ($1 ? new analyzed_expr($1) : 0); }
 250         ;
 251
 252 conditional:
 253         alternative
 254                 { $$ = $1; }
 255         | alternative '?' optional_conditional ':' conditional
 256                 { $$ = new conditional_expr($1, $3, $5); }
 257         ;
 258
 259 optional_conditional:
 260         /* empty */
 261                 { $$ = 0; }
 262         | conditional
 263                 { $$ = $1; }
 264         ;
 265
 266 alternative:
 267         list
 268                 { $$ = $1; }
 269         | alternative '|' list
 270                 { $$ = new alternative_expr($1, $3); }
 271         | alternative '&' list
 272                 { $$ = new conditional_expr($1, $3, 0); }
 273         ;
 274
 275 list:
 276         substitute
 277                 { $$ = $1; }
 278         | list substitute
 279                 { $$ = new list_expr($1, $2); }
 280         ;
 281
 282 substitute:
 283         string
 284                 { $$ = $1; }
 285         | substitute '~' string
 286                 { $$ = new substitute_expr($1, $3); }
 287         ;
 288
 289 string:
 290         '@'
 291                 { $$ = new at_expr; }
 292         | TOKEN_LITERAL
 293                 {
 294                   $$ = new literal_expr(literals.contents() + $1.start,
 295                                         $1.len);
 296                 }
 297         | TOKEN_LETTER
 298                 { $$ = new field_expr($1, 0); }
 299         | TOKEN_LETTER number
 300                 { $$ = new field_expr($1, $2 - 1); }
 301         | '%' TOKEN_LETTER
 302                 {
 303                   switch ($2) {
 304                   case 'I':
 305                   case 'i':
 306                   case 'A':
 307                   case 'a':
 308                     $$ = new format_expr($2);
 309                     break;
 310                   default:
 311                     command_error("unrecognized format '%1'", char($2));
 312                     $$ = new format_expr('a');
 313                     break;
 314                   }
 315                 }
 316
 317         | '%' digits
 318                 {
 319                   $$ = new format_expr('0', $2.ndigits, $2.val);
 320                 }
 321         | string '.' flag TOKEN_LETTER optional_number
 322                 {
 323                   switch ($4) {
 324                   case 'l':
 325                     $$ = new map_expr($1, lowercase);
 326                     break;
 327                   case 'u':
 328                     $$ = new map_expr($1, uppercase);
 329                     break;
 330                   case 'c':
 331                     $$ = new map_expr($1, capitalize);
 332                     break;
 333                   case 'r':
 334                     $$ = new map_expr($1, reverse_name);
 335                     break;
 336                   case 'a':
 337                     $$ = new map_expr($1, abbreviate_name);
 338                     break;
 339                   case 'y':
 340                     $$ = new extractor_expr($1, find_year, $3);
 341                     break;
 342                   case 'n':
 343                     $$ = new extractor_expr($1, find_last_name, $3);
 344                     break;
 345                   default:
 346                     $$ = $1;
 347                     command_error("unknown function '%1'", char($4));
 348                     break;
 349                   }
 350                 }
 351
 352         | string '+' number
 353                 { $$ = new truncate_expr($1, $3); }
 354         | string '-' number
 355                 { $$ = new truncate_expr($1, -$3); }
 356         | string '*'
 357                 { $$ = new star_expr($1); }
 358         | '(' optional_conditional ')'
 359                 { $$ = $2; }
 360         | '<' optional_conditional '>'
 361                 { $$ = new separator_expr($2); }
 362         ;
 363
 364 optional_number:
 365         /* empty */
 366                 { $$ = -1; }
 367         | number
 368                 { $$ = $1; }
 369         ;
 370
 371 number:
 372         TOKEN_DIGIT
 373                 { $$ = $1; }
 374         | number TOKEN_DIGIT
 375                 { $$ = $1*10 + $2; }
 376         ;
 377
 378 digits:
 379         TOKEN_DIGIT
 380                 { $$.ndigits = 1; $$.val = $1; }
 381         | digits TOKEN_DIGIT
 382                 { $$.ndigits = $1.ndigits + 1; $$.val = $1.val*10 + $2; }
 383         ;
 384
 385
 386 flag:
 387         /* empty */
 388                 { $$ = 0; }
 389         | '+'
 390                 { $$ = 1; }
 391         | '-'
 392                 { $$ = -1; }
 393         ;
 394
 395 %%
 396
 397 /* bison defines const to be empty unless __STDC__ is defined, which it
 398 isn't under cfront */
 399
 400 #ifdef const
 401 #undef const
 402 #endif
 403
 404 const char *spec_ptr;
 405 const char *spec_end;
 406 const char *spec_cur;
 407
 408 static char uppercase_array[] = {
 409   'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
 410   'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
 411   'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
 412   'Y', 'Z',
 413 };
 414
 415 static char lowercase_array[] = {
 416   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
 417   'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
 418   'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
 419   'y', 'z',
 420 };
 421
 422 int yylex()
 423 {
 424   while (spec_ptr < spec_end && csspace(*spec_ptr))
 425     spec_ptr++;
 426   spec_cur = spec_ptr;
 427   if (spec_ptr >= spec_end)
 428     return 0;
 429   unsigned char c = *spec_ptr++;
 430   if (csalpha(c)) {
 431     yylval.num = c;
 432     return TOKEN_LETTER;
 433   }
 434   if (csdigit(c)) {
 435     yylval.num = c - '0';
 436     return TOKEN_DIGIT;
 437   }
 438   if (c == '\'') {
 439     yylval.str.start = literals.length();
 440     for (; spec_ptr < spec_end; spec_ptr++) {
 441       if (*spec_ptr == '\'') {
 442         if (++spec_ptr < spec_end && *spec_ptr == '\'')
 443           literals += '\'';
 444         else {
 445           yylval.str.len = literals.length() - yylval.str.start;
 446           return TOKEN_LITERAL;
 447         }
 448       }
 449       else
 450         literals += *spec_ptr;
 451     }
 452     yylval.str.len = literals.length() - yylval.str.start;
 453     return TOKEN_LITERAL;
 454   }
 455   return c;
 456 }
 457
 458 int set_label_spec(const char *label_spec)
 459 {
 460   spec_cur = spec_ptr = label_spec;
 461   spec_end = strchr(label_spec, '\0');
 462   literals.clear();
 463   if (yyparse())
 464     return 0;
 465   delete parsed_label;
 466   parsed_label = parse_result;
 467   return 1;
 468 }
 469
 470 int set_date_label_spec(const char *label_spec)
 471 {
 472   spec_cur = spec_ptr = label_spec;
 473   spec_end = strchr(label_spec, '\0');
 474   literals.clear();
 475   if (yyparse())
 476     return 0;
 477   delete parsed_date_label;
 478   parsed_date_label = parse_result;
 479   return 1;
 480 }
 481
 482 int set_short_label_spec(const char *label_spec)
 483 {
 484   spec_cur = spec_ptr = label_spec;
 485   spec_end = strchr(label_spec, '\0');
 486   literals.clear();
 487   if (yyparse())
 488     return 0;
 489   delete parsed_short_label;
 490   parsed_short_label = parse_result;
 491   return 1;
 492 }
 493
 494 void yyerror(const char *message)
 495 {
 496   if (spec_cur < spec_end)
 497     command_error("label specification %1 before '%2'", message, spec_cur);
 498   else
 499     command_error("label specification %1 at end of string",
 500                   message, spec_cur);
 501 }
 502
 503 void at_expr::evaluate(int tentative, const reference &ref,
 504                        string &result, substring_position &)
 505 {
 506   if (tentative)
 507     ref.canonicalize_authors(result);
 508   else {
 509     const char *end, *start = ref.get_authors(&end);
 510     if (start)
 511       result.append(start, end - start);
 512   }
 513 }
 514
 515 void format_expr::evaluate(int tentative, const reference &ref,
 516                            string &result, substring_position &)
 517 {
 518   if (tentative)
 519     return;
 520   const label_info *lp = ref.get_label_ptr();
 521   int num = lp == 0 ? ref.get_number() : lp->count;
 522   if (type != '0')
 523     result += format_serial(type, num + 1);
 524   else {
 525     const char *ptr = i_to_a(num + first_number);
 526     int pad = width - strlen(ptr);
 527     while (--pad >= 0)
 528       result += '0';
 529     result += ptr;
 530   }
 531 }
 532
 533 static const char *format_serial(char c, int n)
 534 {
 535   assert(n > 0);
 536   static char buf[128]; // more than enough.
 537   switch (c) {
 538   case 'i':
 539   case 'I':
 540     {
 541       char *p = buf;
 542       // troff uses z and w to represent 10000 and 5000 in Roman
 543       // numerals; I can find no historical basis for this usage
 544       const char *s = c == 'i' ? "zwmdclxvi" : "ZWMDCLXVI";
 545       if (n >= 40000)
 546         return i_to_a(n);
 547       while (n >= 10000) {
 548         *p++ = s[0];
 549         n -= 10000;
 550       }
 551       for (int i = 1000; i > 0; i /= 10, s += 2) {
 552         int m = n/i;
 553         n -= m*i;
 554         switch (m) {
 555         case 3:
 556           *p++ = s[2];
 557           /* falls through */
 558         case 2:
 559           *p++ = s[2];
 560           /* falls through */
 561         case 1:
 562           *p++ = s[2];
 563           break;
 564         case 4:
 565           *p++ = s[2];
 566           *p++ = s[1];
 567           break;
 568         case 8:
 569           *p++ = s[1];
 570           *p++ = s[2];
 571           *p++ = s[2];
 572           *p++ = s[2];
 573           break;
 574         case 7:
 575           *p++ = s[1];
 576           *p++ = s[2];
 577           *p++ = s[2];
 578           break;
 579         case 6:
 580           *p++ = s[1];
 581           *p++ = s[2];
 582           break;
 583         case 5:
 584           *p++ = s[1];
 585           break;
 586         case 9:
 587           *p++ = s[2];
 588           *p++ = s[0];
 589         }
 590       }
 591       *p = 0;
 592       break;
 593     }
 594   case 'a':
 595   case 'A':
 596     {
 597       char *p = buf;
 598       // this is derived from troff/reg.c
 599       while (n > 0) {
 600         int d = n % 26;
 601         if (d == 0)
 602           d = 26;
 603         n -= d;
 604         n /= 26;
 605         *p++ = c == 'a' ? lowercase_array[d - 1] :
 606                                uppercase_array[d - 1];
 607       }
 608       *p-- = 0;
 609       // Reverse it.
 610       char *q = buf;
 611       while (q < p) {
 612         char temp = *q;
 613         *q = *p;
 614         *p = temp;
 615         --p;
 616         ++q;
 617       }
 618       break;
 619     }
 620   default:
 621     assert(0);
 622   }
 623   return buf;
 624 }
 625
 626 void field_expr::evaluate(int, const reference &ref,
 627                           string &result, substring_position &)
 628 {
 629   const char *end;
 630   const char *start = ref.get_field(name, &end);
 631   if (start) {
 632     start = nth_field(number, start, &end);
 633     if (start)
 634       result.append(start, end - start);
 635   }
 636 }
 637
 638 void literal_expr::evaluate(int, const reference &,
 639                             string &result, substring_position &)
 640 {
 641   result += s;
 642 }
 643
 644 analyzed_expr::analyzed_expr(expression *e)
 645 : unary_expr(e), flags(e ? e->analyze() : 0)
 646 {
 647 }
 648
 649 void analyzed_expr::evaluate(int tentative, const reference &ref,
 650                              string &result, substring_position &pos)
 651 {
 652   if (expr)
 653     expr->evaluate(tentative, ref, result, pos);
 654 }
 655
 656 void star_expr::evaluate(int tentative, const reference &ref,
 657                          string &result, substring_position &pos)
 658 {
 659   const label_info *lp = ref.get_label_ptr();
 660   if (!tentative
 661       && (lp == 0 || lp->total > 1)
 662       && expr)
 663     expr->evaluate(tentative, ref, result, pos);
 664 }
 665
 666 void separator_expr::evaluate(int tentative, const reference &ref,
 667                               string &result, substring_position &pos)
 668 {
 669   int start_length = result.length();
 670   int is_first = pos.start < 0;
 671   if (expr)
 672     expr->evaluate(tentative, ref, result, pos);
 673   if (is_first) {
 674     pos.start = start_length;
 675     pos.length = result.length() - start_length;
 676   }
 677 }
 678
 679 void map_expr::evaluate(int tentative, const reference &ref,
 680                         string &result, substring_position &)
 681 {
 682   if (expr) {
 683     string temp;
 684     substring_position temp_pos;
 685     expr->evaluate(tentative, ref, temp, temp_pos);
 686     (*func)(temp.contents(), temp.contents() + temp.length(), result);
 687   }
 688 }
 689
 690 void extractor_expr::evaluate(int tentative, const reference &ref,
 691                               string &result, substring_position &)
 692 {
 693   if (expr) {
 694     string temp;
 695     substring_position temp_pos;
 696     expr->evaluate(tentative, ref, temp, temp_pos);
 697     const char *end, *start = (*func)(temp.contents(),
 698                                       temp.contents() + temp.length(),
 699                                       &end);
 700     switch (part) {
 701     case BEFORE:
 702       if (start)
 703         result.append(temp.contents(), start - temp.contents());
 704       else
 705         result += temp;
 706       break;
 707     case MATCH:
 708       if (start)
 709         result.append(start, end - start);
 710       break;
 711     case AFTER:
 712       if (start)
 713         result.append(end, temp.contents() + temp.length() - end);
 714       break;
 715     default:
 716       assert(0);
 717     }
 718   }
 719 }
 720
 721 static void first_part(int len, const char *ptr, const char *end,
 722                           string &result)
 723 {
 724   for (;;) {
 725     const char *token_start = ptr;
 726     if (!get_token(&ptr, end))
 727       break;
 728     const token_info *ti = lookup_token(token_start, ptr);
 729     int counts = ti->sortify_non_empty(token_start, ptr);
 730     if (counts && --len < 0)
 731       break;
 732     if (counts || ti->is_accent())
 733       result.append(token_start, ptr - token_start);
 734   }
 735 }
 736
 737 static void last_part(int len, const char *ptr, const char *end,
 738                       string &result)
 739 {
 740   const char *start = ptr;
 741   int count = 0;
 742   for (;;) {
 743     const char *token_start = ptr;
 744     if (!get_token(&ptr, end))
 745       break;
 746     const token_info *ti = lookup_token(token_start, ptr);
 747     if (ti->sortify_non_empty(token_start, ptr))
 748       count++;
 749   }
 750   ptr = start;
 751   int skip = count - len;
 752   if (skip > 0) {
 753     for (;;) {
 754       const char *token_start = ptr;
 755       if (!get_token(&ptr, end))
 756         assert(0);
 757       const token_info *ti = lookup_token(token_start, ptr);
 758       if (ti->sortify_non_empty(token_start, ptr) && --skip < 0) {
 759         ptr = token_start;
 760         break;
 761       }
 762     }
 763   }
 764   first_part(len, ptr, end, result);
 765 }
 766
 767 void truncate_expr::evaluate(int tentative, const reference &ref,
 768                              string &result, substring_position &)
 769 {
 770   if (expr) {
 771     string temp;
 772     substring_position temp_pos;
 773     expr->evaluate(tentative, ref, temp, temp_pos);
 774     const char *start = temp.contents();
 775     const char *end = start + temp.length();
 776     if (n > 0)
 777       first_part(n, start, end, result);
 778     else if (n < 0)
 779       last_part(-n, start, end, result);
 780   }
 781 }
 782
 783 void alternative_expr::evaluate(int tentative, const reference &ref,
 784                                 string &result, substring_position &pos)
 785 {
 786   int start_length = result.length();
 787   if (expr1)
 788     expr1->evaluate(tentative, ref, result, pos);
 789   if (result.length() == start_length && expr2)
 790     expr2->evaluate(tentative, ref, result, pos);
 791 }
 792
 793 void list_expr::evaluate(int tentative, const reference &ref,
 794                          string &result, substring_position &pos)
 795 {
 796   if (expr1)
 797     expr1->evaluate(tentative, ref, result, pos);
 798   if (expr2)
 799     expr2->evaluate(tentative, ref, result, pos);
 800 }
 801
 802 void substitute_expr::evaluate(int tentative, const reference &ref,
 803                                string &result, substring_position &pos)
 804 {
 805   int start_length = result.length();
 806   if (expr1)
 807     expr1->evaluate(tentative, ref, result, pos);
 808   if (result.length() > start_length && result[result.length() - 1] == '-') {
 809     // ought to see if pos covers the -
 810     result.set_length(result.length() - 1);
 811     if (expr2)
 812       expr2->evaluate(tentative, ref, result, pos);
 813   }
 814 }
 815
 816 void conditional_expr::evaluate(int tentative, const reference &ref,
 817                                 string &result, substring_position &pos)
 818 {
 819   string temp;
 820   substring_position temp_pos;
 821   if (expr1)
 822     expr1->evaluate(tentative, ref, temp, temp_pos);
 823   if (temp.length() > 0) {
 824     if (expr2)
 825       expr2->evaluate(tentative, ref, result, pos);
 826   }
 827   else {
 828     if (expr3)
 829       expr3->evaluate(tentative, ref, result, pos);
 830   }
 831 }
 832
 833 void reference::pre_compute_label()
 834 {
 835   if (parsed_label != 0
 836       && (parsed_label->analyze() & expression::CONTAINS_VARIABLE)) {
 837     label.clear();
 838     substring_position temp_pos;
 839     parsed_label->evaluate(1, *this, label, temp_pos);
 840     label_ptr = lookup_label(label);
 841   }
 842 }
 843
 844 void reference::compute_label()
 845 {
 846   label.clear();
 847   if (parsed_label)
 848     parsed_label->evaluate(0, *this, label, separator_pos);
 849   if (short_label_flag && parsed_short_label)
 850     parsed_short_label->evaluate(0, *this, short_label, short_separator_pos);
 851   if (date_as_label) {
 852     string new_date;
 853     if (parsed_date_label) {
 854       substring_position temp_pos;
 855       parsed_date_label->evaluate(0, *this, new_date, temp_pos);
 856     }
 857     set_date(new_date);
 858   }
 859   if (label_ptr)
 860     label_ptr->count += 1;
 861 }
 862
 863 void reference::immediate_compute_label()
 864 {
 865   if (label_ptr)
 866     label_ptr->total = 2;       // force use of disambiguator
 867   compute_label();
 868 }
 869
 870 int reference::merge_labels(reference **v, int n, label_type type,
 871                             string &result)
 872 {
 873   if (abbreviate_label_ranges)
 874     return merge_labels_by_number(v, n, type, result);
 875   else
 876     return merge_labels_by_parts(v, n, type, result);
 877 }
 878
 879 int reference::merge_labels_by_number(reference **v, int n, label_type type,
 880                                       string &result)
 881 {
 882   if (n <= 1)
 883     return 0;
 884   int num = get_number();
 885   // Only merge three or more labels.
 886   if (v[0]->get_number() != num + 1
 887       || v[1]->get_number() != num + 2)
 888     return 0;
 889   int i;
 890   for (i = 2; i < n; i++)
 891     if (v[i]->get_number() != num + i + 1)
 892       break;
 893   result = get_label(type);
 894   result += label_range_indicator;
 895   result += v[i - 1]->get_label(type);
 896   return i;
 897 }
 898
 899 const substring_position &reference::get_separator_pos(label_type type) const
 900 {
 901   if (type == SHORT_LABEL && short_label_flag)
 902     return short_separator_pos;
 903   else
 904     return separator_pos;
 905 }
 906
 907 const string &reference::get_label(label_type type) const
 908 {
 909   if (type == SHORT_LABEL && short_label_flag)
 910     return short_label;
 911   else
 912     return label;
 913 }
 914
 915 int reference::merge_labels_by_parts(reference **v, int n, label_type type,
 916                                      string &result)
 917 {
 918   if (n <= 0)
 919     return 0;
 920   const string &lb = get_label(type);
 921   const substring_position &sp = get_separator_pos(type);
 922   if (sp.start < 0
 923       || sp.start != v[0]->get_separator_pos(type).start
 924       || memcmp(lb.contents(), v[0]->get_label(type).contents(),
 925                 sp.start) != 0)
 926     return 0;
 927   result = lb;
 928   int i = 0;
 929   do {
 930     result += separate_label_second_parts;
 931     const substring_position &s = v[i]->get_separator_pos(type);
 932     int sep_end_pos = s.start + s.length;
 933     result.append(v[i]->get_label(type).contents() + sep_end_pos,
 934                   v[i]->get_label(type).length() - sep_end_pos);
 935   } while (++i < n
 936            && sp.start == v[i]->get_separator_pos(type).start
 937            && memcmp(lb.contents(), v[i]->get_label(type).contents(),
 938                      sp.start) == 0);
 939   return i;
 940 }
 941
 942 string label_pool;
 943
 944 label_info::label_info(const string &s)
 945 : start(label_pool.length()), length(s.length()), count(0), total(1)
 946 {
 947   label_pool += s;
 948 }
 949
 950 static label_info **label_table = 0;
 951 static int label_table_size = 0;
 952 static int label_table_used = 0;
 953
 954 label_info *lookup_label(const string &label)
 955 {
 956   if (label_table == 0) {
 957     label_table = new label_info *[17];
 958     label_table_size = 17;
 959     for (int i = 0; i < 17; i++)
 960       label_table[i] = 0;
 961   }
 962   unsigned h = hash_string(label.contents(), label.length()) % label_table_size;
 963   label_info **ptr;
 964   for (ptr = label_table + h;
 965        *ptr != 0;
 966        (ptr == label_table)
 967        ? (ptr = label_table + label_table_size - 1)
 968        : ptr--)
 969     if ((*ptr)->length == label.length()
 970         && memcmp(label_pool.contents() + (*ptr)->start, label.contents(),
 971                   label.length()) == 0) {
 972       (*ptr)->total += 1;
 973       return *ptr;
 974     }
 975   label_info *result = *ptr = new label_info(label);
 976   if (++label_table_used * 2 > label_table_size) {
 977     // Rehash the table.
 978     label_info **old_table = label_table;
 979     int old_size = label_table_size;
 980     label_table_size = next_size(label_table_size);
 981     label_table = new label_info *[label_table_size];
 982     int i;
 983     for (i = 0; i < label_table_size; i++)
 984       label_table[i] = 0;
 985     for (i = 0; i < old_size; i++)
 986       if (old_table[i]) {
 987         h = hash_string(label_pool.contents() + old_table[i]->start,
 988                         old_table[i]->length);
 989         label_info **p;
 990         for (p = label_table + (h % label_table_size);
 991              *p != 0;
 992              (p == label_table)
 993              ? (p = label_table + label_table_size - 1)
 994              : --p)
 995             ;
 996         *p = old_table[i];
 997         }
 998     a_delete old_table;
 999   }
1000   return result;
1001 }
1002
1003 void clear_labels()
1004 {
1005   for (int i = 0; i < label_table_size; i++) {
1006     delete label_table[i];
1007     label_table[i] = 0;
1008   }
1009   label_table_used = 0;
1010   label_pool.clear();
1011 }
1012
1013 static void consider_authors(reference **start, reference **end, int i);
1014
1015 void compute_labels(reference **v, int n)
1016 {
1017   if (parsed_label
1018       && (parsed_label->analyze() & expression::CONTAINS_AT)
1019       && sort_fields.length() >= 2
1020       && sort_fields[0] == 'A'
1021       && sort_fields[1] == '+')
1022     consider_authors(v, v + n, 0);
1023   for (int i = 0; i < n; i++)
1024     v[i]->compute_label();
1025 }
1026
1027
1028 /* A reference with a list of authors <A0,A1,...,AN> _needs_ author i
1029 where 0 <= i <= N if there exists a reference with a list of authors
1030 <B0,B1,...,BM> such that <A0,A1,...,AN> != <B0,B1,...,BM> and M >= i
1031 and Aj = Bj for 0 <= j < i. In this case if we can't say "A0,
1032 A1,...,A(i-1) et al" because this would match both <A0,A1,...,AN> and
1033 <B0,B1,...,BM>.  If a reference needs author i we only have to call
1034 need_author(j) for some j >= i such that the reference also needs
1035 author j. */
1036
1037 /* This function handles 2 tasks:
1038 determine which authors are needed (cannot be elided with et al.);
1039 determine which authors can have only last names in the labels.
1040
1041 References >= start and < end have the same first i author names.
1042 Also they're sorted by A+. */
1043
1044 static void consider_authors(reference **start, reference **end, int i)
1045 {
1046   if (start >= end)
1047     return;
1048   reference **p = start;
1049   if (i >= (*p)->get_nauthors()) {
1050     for (++p; p < end && i >= (*p)->get_nauthors(); p++)
1051       ;
1052     if (p < end && i > 0) {
1053       // If we have an author list <A B C> and an author list <A B C D>,
1054       // then both lists need C.
1055       for (reference **q = start; q < end; q++)
1056         (*q)->need_author(i - 1);
1057     }
1058     start = p;
1059   }
1060   while (p < end) {
1061     reference **last_name_start = p;
1062     reference **name_start = p;
1063     for (++p;
1064          p < end && i < (*p)->get_nauthors()
1065          && same_author_last_name(**last_name_start, **p, i);
1066          p++) {
1067       if (!same_author_name(**name_start, **p, i)) {
1068         consider_authors(name_start, p, i + 1);
1069         name_start = p;
1070       }
1071     }
1072     consider_authors(name_start, p, i + 1);
1073     if (last_name_start == name_start) {
1074       for (reference **q = last_name_start; q < p; q++)
1075         (*q)->set_last_name_unambiguous(i);
1076     }
1077     // If we have an author list <A B C D> and <A B C E>, then the lists
1078     // need author D and E respectively.
1079     if (name_start > start || p < end) {
1080       for (reference **q = last_name_start; q < p; q++)
1081         (*q)->need_author(i);
1082     }
1083   }
1084 }
1085
1086 int same_author_last_name(const reference &r1, const reference &r2, int n)
1087 {
1088   const char *ae1;
1089   const char *as1 = r1.get_sort_field(0, n, 0, &ae1);
1090   const char *ae2;
1091   const char *as2 = r2.get_sort_field(0, n, 0, &ae2);
1092   if (!as1 && !as2) return 1;   // they are the same
1093   if (!as1 || !as2) return 0;
1094   return ae1 - as1 == ae2 - as2 && memcmp(as1, as2, ae1 - as1) == 0;
1095 }
1096
1097 int same_author_name(const reference &r1, const reference &r2, int n)
1098 {
1099   const char *ae1;
1100   const char *as1 = r1.get_sort_field(0, n, -1, &ae1);
1101   const char *ae2;
1102   const char *as2 = r2.get_sort_field(0, n, -1, &ae2);
1103   if (!as1 && !as2) return 1;   // they are the same
1104   if (!as1 || !as2) return 0;
1105   return ae1 - as1 == ae2 - as2 && memcmp(as1, as2, ae1 - as1) == 0;
1106 }
1107
1108
1109 void int_set::set(int i)
1110 {
1111   assert(i >= 0);
1112   int bytei = i >> 3;
1113   if (bytei >= v.length()) {
1114     int old_length = v.length();
1115     v.set_length(bytei + 1);
1116     for (int j = old_length; j <= bytei; j++)
1117       v[j] = 0;
1118   }
1119   v[bytei] |= 1 << (i & 7);
1120 }
1121
1122 int int_set::get(int i) const
1123 {
1124   assert(i >= 0);
1125   int bytei = i >> 3;
1126   return bytei >= v.length() ? 0 : (v[bytei] & (1 << (i & 7))) != 0;
1127 }
1128
1129 void reference::set_last_name_unambiguous(int i)
1130 {
1131   last_name_unambiguous.set(i);
1132 }
1133
1134 void reference::need_author(int n)
1135 {
1136   if (n > last_needed_author)
1137     last_needed_author = n;
1138 }
1139
1140 const char *reference::get_authors(const char **end) const
1141 {
1142   if (!computed_authors) {
1143     ((reference *)this)->computed_authors = 1;
1144     string &result = ((reference *)this)->authors;
1145     int na = get_nauthors();
1146     result.clear();
1147     for (int i = 0; i < na; i++) {
1148       if (last_name_unambiguous.get(i)) {
1149         const char *e, *start = get_author_last_name(i, &e);
1150         assert(start != 0);
1151         result.append(start, e - start);
1152       }
1153       else {
1154         const char *e, *start = get_author(i, &e);
1155         assert(start != 0);
1156         result.append(start, e - start);
1157       }
1158       if (i == last_needed_author
1159           && et_al.length() > 0
1160           && et_al_min_elide > 0
1161           && last_needed_author + et_al_min_elide < na
1162           && na >= et_al_min_total) {
1163         result += et_al;
1164         break;
1165       }
1166       if (i < na - 1) {
1167         if (na == 2)
1168           result += join_authors_exactly_two;
1169         else if (i < na - 2)
1170           result += join_authors_default;
1171         else
1172           result += join_authors_last_two;
1173       }
1174     }
1175   }
1176   const char *start = authors.contents();
1177   *end = start + authors.length();
1178   return start;
1179 }
1180
1181 int reference::get_nauthors() const
1182 {
1183   if (nauthors < 0) {
1184     const char *dummy;
1185     int na;
1186     for (na = 0; get_author(na, &dummy) != 0; na++)
1187       ;
1188     ((reference *)this)->nauthors = na;
1189   }
1190   return nauthors;
1191 }