contrib/groff/src/preproc/refer/label.y

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