pintos-os.org Git - pspp/blob - src/language/lexer/scan.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2010, 2011, 2013 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include "language/lexer/scan.h"
  20
  21 #include <limits.h>
  22 #include <unistr.h>
  23
  24 #include "data/identifier.h"
  25 #include "language/lexer/token.h"
  26 #include "libpspp/assertion.h"
  27 #include "libpspp/cast.h"
  28 #include "libpspp/i18n.h"
  29
  30 #include "gl/c-ctype.h"
  31 #include "gl/c-strtod.h"
  32 #include "gl/xmemdup0.h"
  33
  34 #include "gettext.h"
  35 #define _(msgid) gettext (msgid)
  36
  37 enum
  38   {
  39     S_START,
  40     S_DASH,
  41     S_STRING
  42   };
  43
  44 #define SS_NL_BEFORE_PLUS (1u << 0)
  45 #define SS_PLUS           (1u << 1)
  46 #define SS_NL_AFTER_PLUS  (1u << 2)
  47
  48 /* Returns the integer value of (hex) digit C. */
  49 static int
  50 digit_value (int c)
  51 {
  52   switch (c)
  53     {
  54     case '0': return 0;
  55     case '1': return 1;
  56     case '2': return 2;
  57     case '3': return 3;
  58     case '4': return 4;
  59     case '5': return 5;
  60     case '6': return 6;
  61     case '7': return 7;
  62     case '8': return 8;
  63     case '9': return 9;
  64     case 'a': case 'A': return 10;
  65     case 'b': case 'B': return 11;
  66     case 'c': case 'C': return 12;
  67     case 'd': case 'D': return 13;
  68     case 'e': case 'E': return 14;
  69     case 'f': case 'F': return 15;
  70     default: return INT_MAX;
  71     }
  72 }
  73
  74 static bool
  75 scan_quoted_string__ (struct substring s, struct token *token)
  76 {
  77   int quote;
  78
  79   /* Trim ' or " from front and back. */
  80   quote = s.string[s.length - 1];
  81   s.string++;
  82   s.length -= 2;
  83
  84   ss_realloc (&token->string, token->string.length + s.length + 1);
  85
  86   for (;;)
  87     {
  88       size_t pos = ss_find_byte (s, quote);
  89       if (pos == SIZE_MAX)
  90         break;
  91
  92       memcpy (ss_end (token->string), s.string, pos + 1);
  93       token->string.length += pos + 1;
  94       ss_advance (&s, pos + 2);
  95     }
  96
  97   memcpy (ss_end (token->string), s.string, ss_length (s));
  98   token->string.length += ss_length (s);
  99
 100   return true;
 101 }
 102
 103 static bool
 104 scan_hex_string__ (struct substring s, struct token *token)
 105 {
 106   uint8_t *dst;
 107   size_t i;
 108
 109   /* Trim X' from front and ' from back. */
 110   s.string += 2;
 111   s.length -= 3;
 112
 113   if (s.length % 2 != 0)
 114     {
 115       token->type = SCAN_BAD_HEX_LENGTH;
 116       token->number = s.length;
 117       return false;
 118     }
 119
 120   ss_realloc (&token->string, token->string.length + s.length / 2 + 1);
 121   dst = CHAR_CAST (uint8_t *, ss_end (token->string));
 122   token->string.length += s.length / 2;
 123   for (i = 0; i < s.length; i += 2)
 124     {
 125       int hi = digit_value (s.string[i]);
 126       int lo = digit_value (s.string[i + 1]);
 127
 128       if (hi >= 16 || lo >= 16)
 129         {
 130           token->type = SCAN_BAD_HEX_DIGIT;
 131           token->number = s.string[hi >= 16 ? i : i + 1];
 132           return false;
 133         }
 134
 135       *dst++ = hi * 16 + lo;
 136     }
 137
 138   return true;
 139 }
 140
 141 static bool
 142 scan_unicode_string__ (struct substring s, struct token *token)
 143 {
 144   uint8_t *dst;
 145   ucs4_t uc;
 146   size_t i;
 147
 148   /* Trim U' from front and ' from back. */
 149   s.string += 2;
 150   s.length -= 3;
 151
 152   if (s.length < 1 || s.length > 8)
 153     {
 154       token->type = SCAN_BAD_UNICODE_LENGTH;
 155       token->number = s.length;
 156       return 0;
 157     }
 158
 159   ss_realloc (&token->string, token->string.length + 4 + 1);
 160
 161   uc = 0;
 162   for (i = 0; i < s.length; i++)
 163     {
 164       int digit = digit_value (s.string[i]);
 165       if (digit >= 16)
 166         {
 167           token->type = SCAN_BAD_UNICODE_DIGIT;
 168           token->number = s.string[i];
 169           return 0;
 170         }
 171       uc = uc * 16 + digit;
 172     }
 173
 174   if ((uc >= 0xd800 && uc < 0xe000) || uc > 0x10ffff)
 175     {
 176       token->type = SCAN_BAD_UNICODE_CODE_POINT;
 177       token->number = uc;
 178       return 0;
 179     }
 180
 181   dst = CHAR_CAST (uint8_t *, ss_end (token->string));
 182   token->string.length += u8_uctomb (dst, uc, 4);
 183
 184   return true;
 185 }
 186
 187 static enum scan_result
 188 scan_string_segment__ (struct scanner *scanner, enum segment_type type,
 189                        struct substring s, struct token *token)
 190 {
 191   bool ok;
 192
 193   switch (type)
 194     {
 195     case SEG_QUOTED_STRING:
 196       ok = scan_quoted_string__ (s, token);
 197       break;
 198
 199     case SEG_HEX_STRING:
 200       ok = scan_hex_string__ (s, token);
 201       break;
 202
 203     case SEG_UNICODE_STRING:
 204       ok = scan_unicode_string__ (s, token);
 205       break;
 206
 207     default:
 208       NOT_REACHED ();
 209     }
 210
 211   if (ok)
 212     {
 213       token->type = T_STRING;
 214       token->string.string[token->string.length] = '\0';
 215       scanner->state = S_STRING;
 216       scanner->substate = 0;
 217       return SCAN_SAVE;
 218     }
 219   else
 220     {
 221       /* The function we called above should have filled in token->type and
 222          token->number properly to describe the error. */
 223       ss_dealloc (&token->string);
 224       token->string = ss_empty ();
 225       return SCAN_DONE;
 226     }
 227
 228 }
 229
 230 static enum scan_result
 231 add_bit (struct scanner *scanner, unsigned int bit)
 232 {
 233   if (!(scanner->substate & bit))
 234     {
 235       scanner->substate |= bit;
 236       return SCAN_MORE;
 237     }
 238   else
 239     return SCAN_BACK;
 240 }
 241
 242 static enum scan_result
 243 scan_string__ (struct scanner *scanner, enum segment_type type,
 244                struct substring s, struct token *token)
 245 {
 246   switch (type)
 247     {
 248     case SEG_SPACES:
 249     case SEG_COMMENT:
 250       return SCAN_MORE;
 251
 252     case SEG_NEWLINE:
 253       if (scanner->substate & SS_PLUS)
 254         return add_bit (scanner, SS_NL_AFTER_PLUS);
 255       else
 256         return add_bit (scanner, SS_NL_BEFORE_PLUS);
 257
 258     case SEG_PUNCT:
 259       return (s.length == 1 && s.string[0] == '+'
 260               ? add_bit (scanner, SS_PLUS)
 261               : SCAN_BACK);
 262
 263     case SEG_QUOTED_STRING:
 264     case SEG_HEX_STRING:
 265     case SEG_UNICODE_STRING:
 266       return (scanner->substate & SS_PLUS
 267               ? scan_string_segment__ (scanner, type, s, token)
 268               : SCAN_BACK);
 269
 270     default:
 271       return SCAN_BACK;
 272     }
 273 }
 274
 275 static enum token_type
 276 scan_reserved_word__ (struct substring word)
 277 {
 278   switch (c_toupper (word.string[0]))
 279     {
 280     case 'B':
 281       return T_BY;
 282
 283     case 'E':
 284       return T_EQ;
 285
 286     case 'G':
 287       return c_toupper (word.string[1]) == 'E' ? T_GE : T_GT;
 288
 289     case 'L':
 290       return c_toupper (word.string[1]) == 'E' ? T_LE : T_LT;
 291
 292     case 'N':
 293       return word.length == 2 ? T_NE : T_NOT;
 294
 295     case 'O':
 296       return T_OR;
 297
 298     case 'T':
 299       return T_TO;
 300
 301     case 'A':
 302       return c_toupper (word.string[1]) == 'L' ? T_ALL : T_AND;
 303
 304     case 'W':
 305       return T_WITH;
 306     }
 307
 308   NOT_REACHED ();
 309 }
 310
 311 static enum token_type
 312 scan_punct1__ (char c0)
 313 {
 314   switch (c0)
 315     {
 316     case '(': return T_LPAREN;
 317     case ')': return T_RPAREN;
 318     case ',': return T_COMMA;
 319     case '=': return T_EQUALS;
 320     case '-': return T_DASH;
 321     case '[': return T_LBRACK;
 322     case ']': return T_RBRACK;
 323     case '&': return T_AND;
 324     case '|': return T_OR;
 325     case '+': return T_PLUS;
 326     case '/': return T_SLASH;
 327     case '*': return T_ASTERISK;
 328     case '<': return T_LT;
 329     case '>': return T_GT;
 330     case '~': return T_NOT;
 331     default: return T_MACRO_PUNCT;
 332     }
 333
 334   NOT_REACHED ();
 335 }
 336
 337 static enum token_type
 338 scan_punct2__ (char c0, char c1)
 339 {
 340   switch (c0)
 341     {
 342     case '*':
 343       return T_EXP;
 344
 345     case '<':
 346       return c1 == '=' ? T_LE : T_NE;
 347
 348     case '>':
 349       return T_GE;
 350
 351     case '~':
 352       return T_NE;
 353
 354     case '&':
 355       return T_AND;
 356
 357     case '|':
 358       return T_OR;
 359     }
 360
 361   NOT_REACHED ();
 362 }
 363
 364 static enum token_type
 365 scan_punct__ (struct substring s)
 366 {
 367   return (s.length == 1
 368           ? scan_punct1__ (s.string[0])
 369           : scan_punct2__ (s.string[0], s.string[1]));
 370 }
 371
 372 static double
 373 scan_number__ (struct substring s)
 374 {
 375   char buf[128];
 376   double number;
 377   char *p;
 378
 379   if (s.length < sizeof buf)
 380     {
 381       p = buf;
 382       memcpy (buf, s.string, s.length);
 383       buf[s.length] = '\0';
 384     }
 385   else
 386     p = xmemdup0 (s.string, s.length);
 387
 388   number = c_strtod (p, NULL);
 389
 390   if (p != buf)
 391     free (p);
 392
 393   return number;
 394 }
 395
 396 static enum scan_result
 397 scan_unexpected_char (const struct substring *s, struct token *token)
 398 {
 399   ucs4_t uc;
 400
 401   token->type = SCAN_UNEXPECTED_CHAR;
 402   u8_mbtouc (&uc, CHAR_CAST (const uint8_t *, s->string), s->length);
 403   token->number = uc;
 404
 405   return SCAN_DONE;
 406 }
 407
 408 const char *
 409 scan_type_to_string (enum scan_type type)
 410 {
 411   switch (type)
 412     {
 413 #define SCAN_TYPE(NAME) case SCAN_##NAME: return #NAME;
 414       SCAN_TYPES
 415 #undef SCAN_TYPE
 416
 417     default:
 418       return token_type_to_name ((enum token_type) type);
 419     }
 420 }
 421
 422 bool
 423 is_scan_type (enum scan_type type)
 424 {
 425   return type > SCAN_FIRST && type < SCAN_LAST;
 426 }
 427
 428 /* If TOKEN has the type of a scan error (a subset of those identified by
 429    is_scan_type()), returns an appropriate error message.  Otherwise, returns
 430    NULL. */
 431 char *
 432 scan_token_to_error (const struct token *token)
 433 {
 434   switch (token->type)
 435     {
 436     case SCAN_BAD_HEX_LENGTH:
 437       return xasprintf (_("String of hex digits has %d characters, which "
 438                           "is not a multiple of 2."), (int) token->number);
 439
 440     case SCAN_BAD_HEX_DIGIT:
 441     case SCAN_BAD_UNICODE_DIGIT:
 442       return xasprintf (_("`%c' is not a valid hex digit."),
 443                         (int) token->number);
 444
 445     case SCAN_BAD_UNICODE_LENGTH:
 446       return xasprintf (_("Unicode string contains %d bytes, which is "
 447                           "not in the valid range of 1 to 8 bytes."),
 448                         (int) token->number);
 449
 450     case SCAN_BAD_UNICODE_CODE_POINT:
 451       return xasprintf (_("U+%04X is not a valid Unicode code point."),
 452                         (int) token->number);
 453
 454     case SCAN_EXPECTED_QUOTE:
 455       return xasprintf (_("Unterminated string constant."));
 456
 457     case SCAN_EXPECTED_EXPONENT:
 458       return xasprintf (_("Missing exponent following `%s'."),
 459                         token->string.string);
 460
 461     case SCAN_UNEXPECTED_CHAR:
 462      {
 463       char c_name[16];
 464       return xasprintf (_("Bad character %s in input."),
 465                         uc_name (token->number, c_name));
 466      }
 467     }
 468
 469   return NULL;
 470 }
 471
 472 static enum scan_result
 473 scan_start__ (struct scanner *scanner, enum segment_type type,
 474               struct substring s, struct token *token)
 475 {
 476   switch (type)
 477     {
 478     case SEG_NUMBER:
 479       token->type = T_POS_NUM;
 480       token->number = scan_number__ (s);
 481       return SCAN_DONE;
 482
 483     case SEG_QUOTED_STRING:
 484     case SEG_HEX_STRING:
 485     case SEG_UNICODE_STRING:
 486       return scan_string_segment__ (scanner, type, s, token);
 487
 488     case SEG_UNQUOTED_STRING:
 489     case SEG_DO_REPEAT_COMMAND:
 490     case SEG_INLINE_DATA:
 491     case SEG_DOCUMENT:
 492     case SEG_MACRO_BODY:
 493       token->type = T_STRING;
 494       ss_alloc_substring (&token->string, s);
 495       return SCAN_DONE;
 496
 497     case SEG_RESERVED_WORD:
 498       token->type = scan_reserved_word__ (s);
 499       return SCAN_DONE;
 500
 501     case SEG_IDENTIFIER:
 502       token->type = T_ID;
 503       ss_alloc_substring (&token->string, s);
 504       return SCAN_DONE;
 505
 506     case SEG_MACRO_ID:
 507       token->type = T_MACRO_ID;
 508       ss_alloc_substring (&token->string, s);
 509       return SCAN_DONE;
 510
 511     case SEG_PUNCT:
 512       if (s.length == 1 && s.string[0] == '-')
 513         {
 514           scanner->state = S_DASH;
 515           return SCAN_SAVE;
 516         }
 517       else
 518         {
 519           token->type = scan_punct__ (s);
 520           if (token->type == T_MACRO_PUNCT)
 521             ss_alloc_substring (&token->string, s);
 522           return SCAN_DONE;
 523         }
 524
 525     case SEG_SHBANG:
 526     case SEG_SPACES:
 527     case SEG_COMMENT:
 528     case SEG_NEWLINE:
 529     case SEG_COMMENT_COMMAND:
 530       token->type = SCAN_SKIP;
 531       return SCAN_DONE;
 532
 533     case SEG_START_DOCUMENT:
 534       token->type = T_ID;
 535       ss_alloc_substring (&token->string, ss_cstr ("DOCUMENT"));
 536       return SCAN_DONE;
 537
 538     case SEG_START_COMMAND:
 539     case SEG_SEPARATE_COMMANDS:
 540     case SEG_END_COMMAND:
 541       token->type = T_ENDCMD;
 542       return SCAN_DONE;
 543
 544     case SEG_END:
 545       token->type = T_STOP;
 546       return SCAN_DONE;
 547
 548     case SEG_EXPECTED_QUOTE:
 549       token->type = SCAN_EXPECTED_QUOTE;
 550       return SCAN_DONE;
 551
 552     case SEG_EXPECTED_EXPONENT:
 553       token->type = SCAN_EXPECTED_EXPONENT;
 554       ss_alloc_substring (&token->string, s);
 555       return SCAN_DONE;
 556
 557     case SEG_UNEXPECTED_CHAR:
 558       return scan_unexpected_char (&s, token);
 559     }
 560
 561   NOT_REACHED ();
 562 }
 563
 564 static enum scan_result
 565 scan_dash__ (enum segment_type type, struct substring s, struct token *token)
 566 {
 567   switch (type)
 568     {
 569     case SEG_SPACES:
 570     case SEG_COMMENT:
 571       return SCAN_MORE;
 572
 573     case SEG_NUMBER:
 574       token->type = T_NEG_NUM;
 575       token->number = -scan_number__ (s);
 576       return SCAN_DONE;
 577
 578     default:
 579       token->type = T_DASH;
 580       return SCAN_BACK;
 581     }
 582 }
 583
 584 /* Initializes SCANNER for scanning a token from a sequence of segments.
 585    Initializes TOKEN as the output token.  (The client retains ownership of
 586    TOKEN, but it must be preserved across subsequent calls to scanner_push()
 587    for SCANNER.)
 588
 589    A scanner only produces a single token.  To obtain the next token,
 590    re-initialize it by calling this function again.
 591
 592    A scanner does not contain any external references, so nothing needs to be
 593    done to destroy one.  For the same reason, scanners may be copied with plain
 594    struct assignment (or memcpy). */
 595 void
 596 scanner_init (struct scanner *scanner, struct token *token)
 597 {
 598   scanner->state = S_START;
 599   *token = (struct token) { .type = T_STOP };
 600 }
 601
 602 /* Adds the segment with type TYPE and UTF-8 text S to SCANNER.  TOKEN must be
 603    the same token passed to scanner_init() for SCANNER, or a copy of it.
 604    scanner_push() may modify TOKEN.  The client retains ownership of TOKEN,
 605
 606    The possible return values are:
 607
 608      - SCAN_DONE: All of the segments that have been passed to scanner_push()
 609        form the token now stored in TOKEN.  SCANNER is now "used up" and must
 610        be reinitialized with scanner_init() if it is to be used again.
 611
 612        Most tokens only consist of a single segment, so this is the most common
 613        return value.
 614
 615      - SCAN_MORE: The segments passed to scanner_push() don't yet determine a
 616        token.  The caller should call scanner_push() again with the next token.
 617        (This won't happen if TYPE is SEG_END indicating the end of input.)
 618
 619      - SCAN_SAVE: This is similar to SCAN_MORE, with one difference: the caller
 620        needs to "save its place" in the stream of segments for a possible
 621        future SCAN_BACK return.  This value can be returned more than once in a
 622        sequence of scanner_push() calls for SCANNER, but the caller only needs
 623        to keep track of the most recent position.
 624
 625      - SCAN_BACK: This is similar to SCAN_DONE, but the token consists of only
 626        the segments up to and including the segment for which SCAN_SAVE was
 627        most recently returned.  Segments following that one should be passed to
 628        the next scanner to be initialized.
 629 */
 630 enum scan_result
 631 scanner_push (struct scanner *scanner, enum segment_type type,
 632               struct substring s, struct token *token)
 633 {
 634   switch (scanner->state)
 635     {
 636     case S_START:
 637       return scan_start__ (scanner, type, s, token);
 638
 639     case S_DASH:
 640       return scan_dash__ (type, s, token);
 641
 642     case S_STRING:
 643       return scan_string__ (scanner, type, s, token);
 644     }
 645
 646   NOT_REACHED ();
 647 }
 648 \f
 649 /* Initializes SLEX for parsing INPUT, which is LENGTH bytes long, in the
 650    specified MODE.
 651
 652    SLEX has no internal state to free, but it retains a reference to INPUT, so
 653    INPUT must not be modified or freed while SLEX is still in use. */
 654 void
 655 string_lexer_init (struct string_lexer *slex, const char *input, size_t length,
 656                    enum segmenter_mode mode, bool is_snippet)
 657 {
 658   *slex = (struct string_lexer) {
 659     .input = input,
 660     .length = length,
 661     .offset = 0,
 662     .segmenter = segmenter_init (mode, is_snippet),
 663   };
 664 }
 665
 666 /*  */
 667 bool
 668 string_lexer_next (struct string_lexer *slex, struct token *token)
 669 {
 670   struct segmenter saved_segmenter;
 671   size_t saved_offset = 0;
 672
 673   struct scanner scanner;
 674
 675   scanner_init (&scanner, token);
 676   for (;;)
 677     {
 678       const char *s = slex->input + slex->offset;
 679       size_t left = slex->length - slex->offset;
 680       enum segment_type type;
 681       int n;
 682
 683       n = segmenter_push (&slex->segmenter, s, left, true, &type);
 684       assert (n >= 0);
 685
 686       slex->offset += n;
 687       switch (scanner_push (&scanner, type, ss_buffer (s, n), token))
 688         {
 689         case SCAN_BACK:
 690           slex->segmenter = saved_segmenter;
 691           slex->offset = saved_offset;
 692           /* Fall through. */
 693         case SCAN_DONE:
 694           return token->type != T_STOP;
 695
 696         case SCAN_MORE:
 697           break;
 698
 699         case SCAN_SAVE:
 700           saved_segmenter = slex->segmenter;
 701           saved_offset = slex->offset;
 702           break;
 703         }
 704     }
 705 }