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 /* Returns the integer value of (hex) digit C. */
  38 static int
  39 digit_value (int c)
  40 {
  41   switch (c)
  42     {
  43     case '0': return 0;
  44     case '1': return 1;
  45     case '2': return 2;
  46     case '3': return 3;
  47     case '4': return 4;
  48     case '5': return 5;
  49     case '6': return 6;
  50     case '7': return 7;
  51     case '8': return 8;
  52     case '9': return 9;
  53     case 'a': case 'A': return 10;
  54     case 'b': case 'B': return 11;
  55     case 'c': case 'C': return 12;
  56     case 'd': case 'D': return 13;
  57     case 'e': case 'E': return 14;
  58     case 'f': case 'F': return 15;
  59     default: return INT_MAX;
  60     }
  61 }
  62
  63 static void
  64 scan_quoted_string (struct substring in, struct token *token)
  65 {
  66   /* Trim ' or " from front and back. */
  67   int quote = in.string[0];
  68   in.string++;
  69   in.length -= 2;
  70
  71   struct substring out = { .string = xmalloc (in.length + 1) };
  72
  73   for (;;)
  74     {
  75       size_t pos = ss_find_byte (in, quote);
  76       if (pos == SIZE_MAX)
  77         break;
  78
  79       memcpy (ss_end (out), in.string, pos + 1);
  80       out.length += pos + 1;
  81       ss_advance (&in, pos + 2);
  82     }
  83
  84   memcpy (ss_end (out), in.string, in.length);
  85   out.length += in.length;
  86   out.string[out.length] = '\0';
  87
  88   *token = (struct token) { .type = T_STRING, .string = out };
  89 }
  90
  91 static char *
  92 scan_hex_string__ (struct substring in, struct substring *out)
  93 {
  94   if (in.length % 2 != 0)
  95     return xasprintf (_("String of hex digits has %zu characters, which "
  96                         "is not a multiple of 2."), in.length);
  97
  98   ss_realloc (out, in.length / 2 + 1);
  99   uint8_t *dst = CHAR_CAST (uint8_t *, out->string);
 100   out->length = in.length / 2;
 101   for (size_t i = 0; i < in.length; i += 2)
 102     {
 103       int hi = digit_value (in.string[i]);
 104       int lo = digit_value (in.string[i + 1]);
 105
 106       if (hi >= 16 || lo >= 16)
 107         return xasprintf (_("`%c' is not a valid hex digit."),
 108                           in.string[hi >= 16 ? i : i + 1]);
 109
 110       *dst++ = hi * 16 + lo;
 111     }
 112
 113   return NULL;
 114 }
 115
 116 static char *
 117 scan_unicode_string__ (struct substring in, struct substring *out)
 118 {
 119   if (in.length < 1 || in.length > 8)
 120     return xasprintf (_("Unicode string contains %zu bytes, which is "
 121                         "not in the valid range of 1 to 8 bytes."),
 122                       in.length);
 123
 124   ucs4_t uc = 0;
 125   for (size_t i = 0; i < in.length; i++)
 126     {
 127       int digit = digit_value (in.string[i]);
 128       if (digit >= 16)
 129         return xasprintf (_("`%c' is not a valid hex digit."), in.string[i]);
 130       uc = uc * 16 + digit;
 131     }
 132
 133   if ((uc >= 0xd800 && uc < 0xe000) || uc > 0x10ffff)
 134     return xasprintf (_("U+%04llX is not a valid Unicode code point."),
 135                       (long long) uc);
 136
 137   ss_realloc (out, 4 + 1);
 138   out->length = u8_uctomb (CHAR_CAST (uint8_t *, ss_end (*out)), uc, 4);
 139
 140   return NULL;
 141 }
 142
 143 static enum token_type
 144 scan_reserved_word__ (struct substring word)
 145 {
 146   switch (c_toupper (word.string[0]))
 147     {
 148     case 'B':
 149       return T_BY;
 150
 151     case 'E':
 152       return T_EQ;
 153
 154     case 'G':
 155       return c_toupper (word.string[1]) == 'E' ? T_GE : T_GT;
 156
 157     case 'L':
 158       return c_toupper (word.string[1]) == 'E' ? T_LE : T_LT;
 159
 160     case 'N':
 161       return word.length == 2 ? T_NE : T_NOT;
 162
 163     case 'O':
 164       return T_OR;
 165
 166     case 'T':
 167       return T_TO;
 168
 169     case 'A':
 170       return c_toupper (word.string[1]) == 'L' ? T_ALL : T_AND;
 171
 172     case 'W':
 173       return T_WITH;
 174     }
 175
 176   NOT_REACHED ();
 177 }
 178
 179 static enum token_type
 180 scan_punct1__ (char c0)
 181 {
 182   switch (c0)
 183     {
 184     case '(': return T_LPAREN;
 185     case ')': return T_RPAREN;
 186     case ',': return T_COMMA;
 187     case '=': return T_EQUALS;
 188     case '-': return T_DASH;
 189     case '[': return T_LBRACK;
 190     case ']': return T_RBRACK;
 191     case '{': return T_LCURLY;
 192     case '}': return T_RCURLY;
 193     case '&': return T_AND;
 194     case '|': return T_OR;
 195     case '+': return T_PLUS;
 196     case '/': return T_SLASH;
 197     case '*': return T_ASTERISK;
 198     case '<': return T_LT;
 199     case '>': return T_GT;
 200     case '~': return T_NOT;
 201     case ';': return T_SEMICOLON;
 202     case ':': return T_COLON;
 203     default: return T_MACRO_PUNCT;
 204     }
 205
 206   NOT_REACHED ();
 207 }
 208
 209 static enum token_type
 210 scan_punct2__ (char c0, char c1)
 211 {
 212   switch (c0)
 213     {
 214     case '*':
 215       return T_EXP;
 216
 217     case '<':
 218       return c1 == '=' ? T_LE : T_NE;
 219
 220     case '>':
 221       return T_GE;
 222
 223     case '~':
 224       return T_NE;
 225
 226     case '&':
 227       return T_AND;
 228
 229     case '|':
 230       return T_OR;
 231     }
 232
 233   NOT_REACHED ();
 234 }
 235
 236 static enum token_type
 237 scan_punct__ (struct substring s)
 238 {
 239   return (s.length == 1
 240           ? scan_punct1__ (s.string[0])
 241           : scan_punct2__ (s.string[0], s.string[1]));
 242 }
 243
 244 static void
 245 scan_number__ (struct substring s, struct token *token)
 246 {
 247   char buf[128];
 248   char *p;
 249
 250   if (s.length < sizeof buf)
 251     {
 252       p = buf;
 253       memcpy (buf, s.string, s.length);
 254       buf[s.length] = '\0';
 255     }
 256   else
 257     p = xmemdup0 (s.string, s.length);
 258
 259   bool negative = *p == '-';
 260   double x = c_strtod (p + negative, NULL);
 261   *token = (struct token) {
 262     .type = negative ? T_NEG_NUM : T_POS_NUM,
 263     .number = negative ? -x : x,
 264   };
 265
 266   if (p != buf)
 267     free (p);
 268 }
 269 \f
 270 static void
 271 tokenize_error__ (struct token *token, char *error)
 272 {
 273   *token = (struct token) { .type = T_STRING, .string = ss_cstr (error) };
 274 }
 275
 276 static enum tokenize_result
 277 tokenize_string_segment__ (enum segment_type type,
 278                            struct substring s, struct token *token)
 279 {
 280   /* Trim X' or U' from front and ' from back. */
 281   s.string += 2;
 282   s.length -= 3;
 283
 284   struct substring out = SS_EMPTY_INITIALIZER;
 285   char *error = (type == SEG_HEX_STRING
 286                  ? scan_hex_string__ (s, &out)
 287                  : scan_unicode_string__ (s, &out));
 288   if (!error)
 289     {
 290       out.string[out.length] = '\0';
 291       *token = (struct token) { .type = T_STRING, .string = out };
 292       return TOKENIZE_TOKEN;
 293     }
 294   else
 295     {
 296       tokenize_error__ (token, error);
 297       ss_dealloc (&out);
 298       return TOKENIZE_ERROR;
 299     }
 300 }
 301
 302 static void
 303 tokenize_unexpected_char (const struct substring *s, struct token *token)
 304 {
 305   ucs4_t uc;
 306   u8_mbtouc (&uc, CHAR_CAST (const uint8_t *, s->string), s->length);
 307
 308   char c_name[16];
 309   tokenize_error__ (token, xasprintf (_("Bad character %s in input."),
 310                                       uc_name (uc, c_name)));
 311 }
 312
 313 enum tokenize_result
 314 token_from_segment (enum segment_type type, struct substring s,
 315                     struct token *token)
 316 {
 317   switch (type)
 318     {
 319     case SEG_NUMBER:
 320       scan_number__ (s, token);
 321       return TOKENIZE_TOKEN;
 322
 323     case SEG_QUOTED_STRING:
 324       scan_quoted_string (s, token);
 325       return TOKENIZE_TOKEN;
 326
 327     case SEG_HEX_STRING:
 328     case SEG_UNICODE_STRING:
 329       return tokenize_string_segment__ (type, s, token);
 330
 331     case SEG_UNQUOTED_STRING:
 332     case SEG_DO_REPEAT_COMMAND:
 333     case SEG_INLINE_DATA:
 334     case SEG_DOCUMENT:
 335     case SEG_MACRO_BODY:
 336     case SEG_MACRO_NAME:
 337       *token = (struct token) { .type = T_STRING, .string = ss_clone (s) };
 338       return TOKENIZE_TOKEN;
 339
 340     case SEG_RESERVED_WORD:
 341       *token = (struct token) { .type = scan_reserved_word__ (s) };
 342       return TOKENIZE_TOKEN;
 343
 344     case SEG_IDENTIFIER:
 345       *token = (struct token) { .type = T_ID, .string = ss_clone (s) };
 346       return TOKENIZE_TOKEN;
 347
 348     case SEG_MACRO_ID:
 349       *token = (struct token) { .type = T_MACRO_ID, .string = ss_clone (s)};
 350       return TOKENIZE_TOKEN;
 351
 352     case SEG_PUNCT:
 353       *token = (struct token) { .type = scan_punct__ (s) };
 354       if (token->type == T_MACRO_PUNCT)
 355         token->string = ss_clone (s);
 356       return TOKENIZE_TOKEN;
 357
 358     case SEG_SHBANG:
 359     case SEG_SPACES:
 360     case SEG_COMMENT:
 361     case SEG_NEWLINE:
 362     case SEG_COMMENT_COMMAND:
 363       return TOKENIZE_EMPTY;
 364
 365     case SEG_START_DOCUMENT:
 366       *token = (struct token) {
 367         .type = T_ID,
 368         .string = ss_clone (ss_cstr ("DOCUMENT"))
 369       };
 370       return TOKENIZE_TOKEN;
 371
 372     case SEG_START_COMMAND:
 373     case SEG_SEPARATE_COMMANDS:
 374     case SEG_END_COMMAND:
 375       *token = (struct token) { .type = T_ENDCMD };
 376       return TOKENIZE_TOKEN;
 377
 378     case SEG_END:
 379       *token = (struct token) { .type = T_STOP };
 380       return TOKENIZE_TOKEN;
 381
 382     case SEG_EXPECTED_QUOTE:
 383       tokenize_error__ (token, xasprintf (_("Unterminated string constant.")));
 384       return TOKENIZE_ERROR;
 385
 386     case SEG_EXPECTED_EXPONENT:
 387       tokenize_error__ (token,
 388                         xasprintf (_("Missing exponent following `%.*s'."),
 389                                    (int) s.length, s.string));
 390       return TOKENIZE_ERROR;
 391
 392     case SEG_UNEXPECTED_CHAR:
 393       tokenize_unexpected_char (&s, token);
 394       return TOKENIZE_ERROR;
 395     }
 396
 397   NOT_REACHED ();
 398 }
 399
 400 \f
 401 /* Initializes SLEX for parsing INPUT, which is LENGTH bytes long, in the
 402    specified MODE.
 403
 404    SLEX has no internal state to free, but it retains a reference to INPUT, so
 405    INPUT must not be modified or freed while SLEX is still in use. */
 406 void
 407 string_lexer_init (struct string_lexer *slex, const char *input, size_t length,
 408                    enum segmenter_mode mode, bool is_snippet)
 409 {
 410   *slex = (struct string_lexer) {
 411     .input = input,
 412     .length = length,
 413     .offset = 0,
 414     .segmenter = segmenter_init (mode, is_snippet),
 415   };
 416 }
 417
 418 /*  */
 419 enum string_lexer_result
 420 string_lexer_next (struct string_lexer *slex, struct token *token)
 421 {
 422   for (;;)
 423     {
 424       const char *s = slex->input + slex->offset;
 425       size_t left = slex->length - slex->offset;
 426       enum segment_type type;
 427       int n;
 428
 429       n = segmenter_push (&slex->segmenter, s, left, true, &type);
 430       assert (n >= 0);
 431
 432       slex->offset += n;
 433       switch (token_from_segment (type, ss_buffer (s, n), token))
 434         {
 435         case TOKENIZE_TOKEN:
 436           return token->type == T_STOP ? SLR_END : SLR_TOKEN;
 437
 438         case TOKENIZE_ERROR:
 439           return SLR_ERROR;
 440
 441         case TOKENIZE_EMPTY:
 442           break;
 443         }
 444     }
 445 }
 446
 447 static struct substring
 448 concat (struct substring a, struct substring b)
 449 {
 450   size_t length = a.length + b.length;
 451   struct substring out = { .string = xmalloc (length + 1), .length = length };
 452   memcpy (out.string, a.string, a.length);
 453   memcpy (out.string + a.length, b.string, b.length);
 454   out.string[length] = '\0';
 455   return out;
 456 }
 457
 458 /* Attempts to merge a sequence of tokens together into a single token.  The
 459    caller feeds tokens in one by one and the merger FSM reports progress.  The
 460    caller must supply a merger structure M that is set to MERGER_INIT before
 461    the first call.  The caller must also supply a token OUT for storage, which
 462    need not be initialized.
 463
 464    Returns:
 465
 466    * -1 if more tokens are needed.  Token OUT might be in use for temporary
 467       storage; to ensure that it is freed, continue calling merger_add() until
 468       it returns something other than -1.  (T_STOP or T_ENDCMD will make it do
 469       that.)
 470
 471    * 0 if the first token submitted to the merger is the output.  This is the
 472      common case for the first call, and it can be returned for subsequent
 473      calls as well.
 474
 475    * A positive number if OUT is initialized to the output token.  The return
 476      value is the number of tokens being merged to produce this one. */
 477 int
 478 merger_add (struct merger *m, const struct token *in, struct token *out)
 479 {
 480   /* We perform two different kinds of token merging:
 481
 482      - String concatenation, where syntax like "a" + "b" is converted into a
 483        single string token.  This is definitely needed because the parser
 484        relies on it.
 485
 486      - Negative number merging, where syntax like -5 is converted from a pair
 487        of tokens (T_DASH then T_POS_NUM) into a single token (T_NEG_NUM).  This
 488        might not be needed anymore because the segmenter directly treats a dash
 489        followed by a number, with optional intervening white space, as a
 490        negative number.  It's only needed if we want intervening comments to be
 491        allowed or for part of the negative number token to be produced by macro
 492        expansion. */
 493   switch (++m->state)
 494     {
 495     case 1:
 496       if (in->type == T_DASH || in->type == T_STRING)
 497         {
 498           *out = *in;
 499           return -1;
 500         }
 501       else
 502         return 0;
 503
 504     case 2:
 505       if (out->type == T_DASH)
 506         {
 507           if (in->type == T_POS_NUM)
 508             {
 509               *out = (struct token) {
 510                 .type = T_NEG_NUM,
 511                 .number = -in->number
 512               };
 513               return 2;
 514             }
 515           else
 516             return 0;
 517         }
 518       else
 519         return in->type == T_PLUS ? -1 : 0;
 520       NOT_REACHED ();
 521
 522     case 3:
 523       if (in->type == T_STRING)
 524         {
 525           out->string = concat (out->string, in->string);
 526           return -1;
 527         }
 528       else
 529         return 0;
 530       NOT_REACHED ();
 531
 532     default:
 533       if (!(m->state % 2))
 534         return in->type == T_PLUS ? -1 : m->state - 1;
 535       else
 536         {
 537           if (in->type == T_STRING)
 538             {
 539               struct substring s = concat (out->string, in->string);
 540               ss_swap (&s, &out->string);
 541               ss_dealloc (&s);
 542               return -1;
 543             }
 544           else
 545             return m->state - 2;
 546         }
 547       NOT_REACHED ();
 548     }
 549 }