drivers/staging/ktap/userspace/lex.c

   1 /*
   2  * lex.c - ktap lexical analyzer
   3  *
   4  * This file is part of ktap by Jovi Zhangwei.
   5  *
   6  * Copyright (C) 2012-2013 Jovi Zhangwei <jovi.zhangwei@gmail.com>.
   7  *
   8  * Copyright (C) 1994-2013 Lua.org, PUC-Rio.
   9  *  - The part of code in this file is copied from lua initially.
  10  *  - lua's MIT license is compatible with GPL.
  11  *
  12  * ktap is free software; you can redistribute it and/or modify it
  13  * under the terms and conditions of the GNU General Public License,
  14  * version 2, as published by the Free Software Foundation.
  15  *
  16  * ktap is distributed in the hope it will be useful, but WITHOUT
  17  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  19  * more details.
  20  *
  21  * You should have received a copy of the GNU General Public License along with
  22  * this program; if not, write to the Free Software Foundation, Inc.,
  23  * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
  24  */
  25
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <locale.h>
  30 #include "../include/ktap_types.h"
  31 #include "../include/ktap_opcodes.h"
  32 #include "ktapc.h"
  33
  34 #define next(ls) (ls->current = *ls->ptr++)
  35
  36 #define currIsNewline(ls)       (ls->current == '\n' || ls->current == '\r')
  37
  38 #define KTAP_MINBUFFER   32
  39
  40 /* ORDER RESERVED */
  41 static const char *const ktap_tokens [] = {
  42         "trace", "trace_end", "argevent", "argname", "cdef",
  43         "arg1", "arg2", "arg3", "arg4", "arg5", "arg6", "arg7", "arg9", "arg9",
  44         "profile", "tick", "<<<",
  45         "and", "break", "do", "else", "elseif",
  46         "end", "false", "for", "function", "goto", "if",
  47         "in", "local", "nil", "not", "or", "repeat",
  48         "return", "then", "true", "until", "while",
  49         "..", "...", "==", ">=", "<=", "!=", "+=", "::", "<eof>",
  50         "<number>", "<name>", "<string>", "<symbol>"
  51 };
  52
  53 #define save_and_next(ls) (save(ls, ls->current), next(ls))
  54
  55 static void lexerror(ktap_lexstate *ls, const char *msg, int token);
  56
  57 static void save(ktap_lexstate *ls, int c)
  58 {
  59         ktap_mbuffer *b = ls->buff;
  60         if (mbuff_len(b) + 1 > mbuff_size(b)) {
  61                 size_t newsize;
  62                 if (mbuff_size(b) >= MAX_SIZET / 2)
  63                         lexerror(ls, "lexical element too long", 0);
  64                 newsize = mbuff_size(b) * 2;
  65                 mbuff_resize(b, newsize);
  66         }
  67         b->buffer[mbuff_len(b)++] = (char)c;
  68 }
  69
  70 void lex_init()
  71 {
  72         int i;
  73         for (i = 0; i < NUM_RESERVED; i++) {
  74                 ktap_string *ts = ktapc_ts_new(ktap_tokens[i]);
  75                 ts->tsv.extra = (u8)(i+1);  /* reserved word */
  76         }
  77 }
  78
  79 const char *lex_token2str(ktap_lexstate *ls, int token)
  80 {
  81         if (token < FIRST_RESERVED) {
  82                 ktap_assert(token == (unsigned char)token);
  83                 return (isprint(token)) ? ktapc_sprintf(KTAP_QL("%c"), token) :
  84                         ktapc_sprintf("char(%d)", token);
  85         } else {
  86                 const char *s = ktap_tokens[token - FIRST_RESERVED];
  87                 if (token < TK_EOS)
  88                         return ktapc_sprintf(KTAP_QS, s);
  89                 else
  90                         return s;
  91         }
  92 }
  93
  94 static const char *txtToken(ktap_lexstate *ls, int token)
  95 {
  96         switch (token) {
  97         case TK_NAME:
  98         case TK_STRING:
  99         case TK_NUMBER:
 100                 save(ls, '\0');
 101                 return ktapc_sprintf(KTAP_QS, mbuff(ls->buff));
 102         default:
 103                 return lex_token2str(ls, token);
 104         }
 105 }
 106
 107 static void lexerror(ktap_lexstate *ls, const char *msg, int token)
 108 {
 109         char buff[KTAP_IDSIZE];
 110         char *newmsg;
 111
 112         ktapc_chunkid(buff, getstr(ls->source), KTAP_IDSIZE);
 113         newmsg = ktapc_sprintf("%s:%d: %s", buff, ls->linenumber, msg);
 114         if (token)
 115                 newmsg = ktapc_sprintf("%s near %s", newmsg, txtToken(ls, token));
 116         printf("lexerror: %s\n", newmsg);
 117         exit(EXIT_FAILURE);
 118 }
 119
 120 void lex_syntaxerror(ktap_lexstate *ls, const char *msg)
 121 {
 122         lexerror(ls, msg, ls->t.token);
 123 }
 124
 125 /*
 126  * creates a new string and anchors it in function's table so that
 127  * it will not be collected until the end of the function's compilation
 128  * (by that time it should be anchored in function's prototype)
 129  */
 130 ktap_string *lex_newstring(ktap_lexstate *ls, const char *str, size_t l)
 131 {
 132         const ktap_value *o;  /* entry for `str' */
 133         ktap_value val;  /* entry for `str' */
 134         ktap_value tsv;
 135         ktap_string *ts = ktapc_ts_newlstr(str, l);  /* create new string */
 136         set_string(&tsv, ts);
 137         o = ktapc_table_get(ls->fs->h, &tsv);
 138         if (is_nil(o)) {  /* not in use yet? (see 'addK') */
 139                 /* boolean value does not need GC barrier;
 140                 table has no metatable, so it does not need to invalidate cache */
 141                 set_boolean(&val, 1);  /* t[string] = true */
 142                 ktapc_table_setvalue(ls->fs->h, &tsv, &val);
 143         }
 144         return ts;
 145 }
 146
 147 /*
 148  * increment line number and skips newline sequence (any of
 149  * \n, \r, \n\r, or \r\n)
 150  */
 151 static void inclinenumber(ktap_lexstate *ls)
 152 {
 153         int old = ls->current;
 154         ktap_assert(currIsNewline(ls));
 155         next(ls);  /* skip `\n' or `\r' */
 156         if (currIsNewline(ls) && ls->current != old)
 157                 next(ls);  /* skip `\n\r' or `\r\n' */
 158         if (++ls->linenumber >= MAX_INT)
 159                 lex_syntaxerror(ls, "chunk has too many lines");
 160 }
 161
 162 void lex_setinput(ktap_lexstate *ls, char *ptr, ktap_string *source, int firstchar)
 163 {
 164         ls->decpoint = '.';
 165         ls->current = firstchar;
 166         ls->lookahead.token = TK_EOS;  /* no look-ahead token */
 167         ls->ptr = ptr;
 168         ls->fs = NULL;
 169         ls->linenumber = 1;
 170         ls->lastline = 1;
 171         ls->source = source;
 172         ls->envn = ktapc_ts_new(KTAP_ENV);  /* create env name */
 173         mbuff_resize(ls->buff, KTAP_MINBUFFER);  /* initialize buffer */
 174 }
 175
 176 /*
 177  * =======================================================
 178  * LEXICAL ANALYZER
 179  * =======================================================
 180  */
 181 static int check_next(ktap_lexstate *ls, const char *set)
 182 {
 183         if (ls->current == '\0' || !strchr(set, ls->current))
 184                 return 0;
 185         save_and_next(ls);
 186         return 1;
 187 }
 188
 189 /*
 190  * change all characters 'from' in buffer to 'to'
 191  */
 192 static void buffreplace(ktap_lexstate *ls, char from, char to)
 193 {
 194         size_t n = mbuff_len(ls->buff);
 195         char *p = mbuff(ls->buff);
 196         while (n--)
 197                 if (p[n] == from) p[n] = to;
 198 }
 199
 200 #if !defined(getlocaledecpoint)
 201 #define getlocaledecpoint()     (localeconv()->decimal_point[0])
 202 #endif
 203
 204 #define mbuff2d(b,e)    ktapc_str2d(mbuff(b), mbuff_len(b) - 1, e)
 205
 206 /*
 207  * in case of format error, try to change decimal point separator to
 208  * the one defined in the current locale and check again
 209  */
 210 static void trydecpoint(ktap_lexstate *ls, ktap_seminfo *seminfo)
 211 {
 212         char old = ls->decpoint;
 213         ls->decpoint = getlocaledecpoint();
 214         buffreplace(ls, old, ls->decpoint);  /* try new decimal separator */
 215         if (!mbuff2d(ls->buff, &seminfo->r)) {
 216                 /* format error with correct decimal point: no more options */
 217                 buffreplace(ls, ls->decpoint, '.');  /* undo change (for error message) */
 218                 lexerror(ls, "malformed number", TK_NUMBER);
 219         }
 220 }
 221
 222 /*
 223  * this function is quite liberal in what it accepts, as 'ktapc_str2d'
 224  * will reject ill-formed numerals.
 225  */
 226 static void read_numeral(ktap_lexstate *ls, ktap_seminfo *seminfo)
 227 {
 228         const char *expo = "Ee";
 229         int first = ls->current;
 230
 231         ktap_assert(isdigit(ls->current));
 232         save_and_next(ls);
 233         if (first == '0' && check_next(ls, "Xx"))  /* hexadecimal? */
 234                 expo = "Pp";
 235         for (;;) {
 236                 if (check_next(ls, expo))  /* exponent part? */
 237                         check_next(ls, "+-");  /* optional exponent sign */
 238                 if (isxdigit(ls->current) || ls->current == '.')
 239                         save_and_next(ls);
 240                 else
 241                         break;
 242         }
 243         save(ls, '\0');
 244         buffreplace(ls, '.', ls->decpoint);  /* follow locale for decimal point */
 245         if (!mbuff2d(ls->buff, &seminfo->r))  /* format error? */
 246                 trydecpoint(ls, seminfo); /* try to update decimal point separator */
 247 }
 248
 249 /*
 250  * skip a sequence '[=*[' or ']=*]' and return its number of '='s or
 251  * -1 if sequence is malformed
 252  */
 253 static int skip_sep(ktap_lexstate *ls)
 254 {
 255         int count = 0;
 256         int s = ls->current;
 257
 258         ktap_assert(s == '[' || s == ']');
 259         save_and_next(ls);
 260         while (ls->current == '=') {
 261                 save_and_next(ls);
 262                 count++;
 263         }
 264         return (ls->current == s) ? count : (-count) - 1;
 265 }
 266
 267 static void read_long_string(ktap_lexstate *ls, ktap_seminfo *seminfo, int sep)
 268 {
 269         save_and_next(ls);  /* skip 2nd `[' */
 270         if (currIsNewline(ls))  /* string starts with a newline? */
 271                 inclinenumber(ls);  /* skip it */
 272         for (;;) {
 273                 switch (ls->current) {
 274                 case EOZ:
 275                         lexerror(ls, (seminfo) ? "unfinished long string" :
 276                                 "unfinished long comment", TK_EOS);
 277                         break;  /* to avoid warnings */
 278                 case ']': {
 279                         if (skip_sep(ls) == sep) {
 280                                 save_and_next(ls);  /* skip 2nd `]' */
 281                                 goto endloop;
 282                         }
 283                         break;
 284                 }
 285                 case '\n':
 286                 case '\r': {
 287                         save(ls, '\n');
 288                         inclinenumber(ls);
 289                         /* avoid wasting space */
 290                         if (!seminfo)
 291                                 mbuff_reset(ls->buff);
 292                         break;
 293                 }
 294                 default: {
 295                         if (seminfo)
 296                                 save_and_next(ls);
 297                         else
 298                                 next(ls);
 299                 }
 300                 }
 301         }
 302
 303  endloop:
 304         if (seminfo)
 305                 seminfo->ts = lex_newstring(ls, mbuff(ls->buff) + (2 + sep),
 306                         mbuff_len(ls->buff) - 2*(2 + sep));
 307 }
 308
 309 static void escerror(ktap_lexstate *ls, int *c, int n, const char *msg)
 310 {
 311         int i;
 312         mbuff_reset(ls->buff);  /* prepare error message */
 313         save(ls, '\\');
 314         for (i = 0; i < n && c[i] != EOZ; i++)
 315                 save(ls, c[i]);
 316         lexerror(ls, msg, TK_STRING);
 317 }
 318
 319 static int readhexaesc(ktap_lexstate *ls)
 320 {
 321         int c[3], i;  /* keep input for error message */
 322         int r = 0;  /* result accumulator */
 323         c[0] = 'x';  /* for error message */
 324         for (i = 1; i < 3; i++) {  /* read two hexa digits */
 325                 c[i] = next(ls);
 326                 if (!isxdigit(c[i]))
 327                         escerror(ls, c, i + 1, "hexadecimal digit expected");
 328                 r = (r << 4) + ktapc_hexavalue(c[i]);
 329         }
 330         return r;
 331 }
 332
 333 static int readdecesc(ktap_lexstate *ls)
 334 {
 335         int c[3], i;
 336         int r = 0;  /* result accumulator */
 337         for (i = 0; i < 3 && isdigit(ls->current); i++) {  /* read up to 3 digits */
 338                 c[i] = ls->current;
 339                 r = 10*r + c[i] - '0';
 340                 next(ls);
 341         }
 342         if (r > UCHAR_MAX)
 343                 escerror(ls, c, i, "decimal escape too large");
 344         return r;
 345 }
 346
 347 static void read_string(ktap_lexstate *ls, int del, ktap_seminfo *seminfo)
 348 {
 349         save_and_next(ls);  /* keep delimiter (for error messages) */
 350         while (ls->current != del) {
 351                 switch (ls->current) {
 352                 case EOZ:
 353                         lexerror(ls, "unfinished string", TK_EOS);
 354                         break;  /* to avoid warnings */
 355                 case '\n':
 356                 case '\r':
 357                         lexerror(ls, "unfinished string", TK_STRING);
 358                         break;  /* to avoid warnings */
 359                 case '\\': {  /* escape sequences */
 360                         int c;  /* final character to be saved */
 361                         next(ls);  /* do not save the `\' */
 362                         switch (ls->current) {
 363                         case 'a': c = '\a'; goto read_save;
 364                         case 'b': c = '\b'; goto read_save;
 365                         case 'f': c = '\f'; goto read_save;
 366                         case 'n': c = '\n'; goto read_save;
 367                         case 'r': c = '\r'; goto read_save;
 368                         case 't': c = '\t'; goto read_save;
 369                         case 'v': c = '\v'; goto read_save;
 370                         case 'x': c = readhexaesc(ls); goto read_save;
 371                         case '\n': case '\r':
 372                                 inclinenumber(ls); c = '\n'; goto only_save;
 373                         case '\\': case '\"': case '\'':
 374                                 c = ls->current; goto read_save;
 375                         case EOZ: goto no_save;  /* will raise an error next loop */
 376                         case 'z': {  /* zap following span of spaces */
 377                                 next(ls);  /* skip the 'z' */
 378                                 while (isspace(ls->current)) {
 379                                         if (currIsNewline(ls))
 380                                                 inclinenumber(ls);
 381                                         else
 382                                                 next(ls);
 383                                 }
 384                                 goto no_save;
 385                         }
 386                         default: {
 387                                 if (!isdigit(ls->current))
 388                                         escerror(ls, &ls->current, 1, "invalid escape sequence");
 389                                 /* digital escape \ddd */
 390                                 c = readdecesc(ls);
 391                                 goto only_save;
 392                         }
 393                         }
 394  read_save:
 395                         next(ls);  /* read next character */
 396  only_save:
 397                         save(ls, c);  /* save 'c' */
 398  no_save:
 399                         break;
 400                 }
 401                 default:
 402                         save_and_next(ls);
 403                 }
 404         }
 405         save_and_next(ls);  /* skip delimiter */
 406         seminfo->ts = lex_newstring(ls, mbuff(ls->buff) + 1, mbuff_len(ls->buff) - 2);
 407 }
 408
 409 static int llex(ktap_lexstate *ls, ktap_seminfo *seminfo)
 410 {
 411         mbuff_reset(ls->buff);
 412
 413         for (;;) {
 414                 switch (ls->current) {
 415                 case '\n': case '\r': {  /* line breaks */
 416                         inclinenumber(ls);
 417                         break;
 418                 }
 419                 case ' ': case '\f': case '\t': case '\v': {  /* spaces */
 420                         next(ls);
 421                         break;
 422                 }
 423                 case '#': {
 424                         while (!currIsNewline(ls) && ls->current != EOZ)
 425                                 next(ls);  /* skip until end of line (or end of file) */
 426                         break;
 427                 }
 428                 #if 0
 429                 case '-': {  /* '-' or '--' (comment) */
 430                         next(ls);
 431                         if (ls->current != '-')
 432                                 return '-';
 433                         /* else is a comment */
 434                         next(ls);
 435                         if (ls->current == '[') {  /* long comment? */
 436                                 int sep = skip_sep(ls);
 437                                 mbuff_reset(ls->buff);  /* `skip_sep' may dirty the buffer */
 438                                 if (sep >= 0) {
 439                                         read_long_string(ls, NULL, sep);  /* skip long comment */
 440                                         mbuff_reset(ls->buff);  /* previous call may dirty the buff. */
 441                                         break;
 442                                 }
 443                         }
 444                         /* else short comment */
 445                         while (!currIsNewline(ls) && ls->current != EOZ)
 446                                 next(ls);  /* skip until end of line (or end of file) */
 447                         break;
 448                 }
 449                 #endif
 450                 case '[': {  /* long string or simply '[' */
 451                         int sep = skip_sep(ls);
 452                         if (sep >= 0) {
 453                                 read_long_string(ls, seminfo, sep);
 454                                 return TK_STRING;
 455                         }
 456                         else if (sep == -1)
 457                                 return '[';
 458                         else
 459                                 lexerror(ls, "invalid long string delimiter", TK_STRING);
 460                 }
 461                 case '+': {
 462                         next(ls);
 463                         if (ls->current != '=')
 464                                 return '+';
 465                         else {
 466                                 next(ls);
 467                                 return TK_INCR;
 468                         }
 469                 }
 470                 case '=': {
 471                         next(ls);
 472                         if (ls->current != '=')
 473                                 return '=';
 474                         else {
 475                                 next(ls);
 476                                 return TK_EQ;
 477                         }
 478                 }
 479                 case '<': {
 480                         next(ls);
 481                         if (ls->current == '=')
 482                                 return TK_LE;
 483                         else if (ls->current == '<') {
 484                                 next(ls);
 485                                 if (ls->current == '<') {
 486                                         next(ls);
 487                                         return TK_AGGR_ASSIGN;
 488                                 }
 489                         } else {
 490                                 return '<';
 491                         }
 492                 }
 493                 case '>': {
 494                         next(ls);
 495                         if (ls->current != '=')
 496                                 return '>';
 497                         else {
 498                                 next(ls);
 499                                 return TK_GE;
 500                         }
 501                 }
 502                 case '!': {
 503                         next(ls);
 504                         if (ls->current != '=')
 505                                 return TK_NOT;
 506                         else {
 507                                 next(ls);
 508                                 return TK_NE;
 509                         }
 510                 }
 511                 case ':': {
 512                         next(ls);
 513                         if (ls->current != ':')
 514                                 return ':';
 515                         else {
 516                                 next(ls);
 517                                 return TK_DBCOLON;
 518                         }
 519                 }
 520                 case '"': case '\'': {  /* short literal strings */
 521                         read_string(ls, ls->current, seminfo);
 522                         return TK_STRING;
 523                 }
 524                 case '`': {  /* short literal kernel symbol */
 525                         read_string(ls, ls->current, seminfo);
 526                         return TK_KSYM;
 527                 }
 528                 case '.': {  /* '.', '..', '...', or number */
 529                         save_and_next(ls);
 530                         if (check_next(ls, ".")) {
 531                                 if (check_next(ls, "."))
 532                                         return TK_DOTS;   /* '...' */
 533                                 else
 534                                         return TK_CONCAT;   /* '..' */
 535                         }
 536                         else if (!isdigit(ls->current))
 537                                 return '.';
 538                         /* else go through */
 539                 }
 540                 case '0': case '1': case '2': case '3': case '4':
 541                 case '5': case '6': case '7': case '8': case '9': {
 542                         read_numeral(ls, seminfo);
 543                         return TK_NUMBER;
 544                 }
 545                 case EOZ: {
 546                         return TK_EOS;
 547                 }
 548                 case '&': {
 549                         next(ls);
 550                         if (ls->current != '&')
 551                                 return '&';
 552                         else {
 553                                 next(ls);
 554                                 return TK_AND;
 555                         }
 556                 }
 557                 case '|': {
 558                         next(ls);
 559                         if (ls->current != '|')
 560                                 return '|';
 561                         else {
 562                                 next(ls);
 563                                 return TK_OR;
 564                         }
 565                 }
 566                 default: {
 567                         if (islalpha(ls->current)) {
 568                                 /* identifier or reserved word? */
 569                                 ktap_string *ts;
 570                                 do {
 571                                         save_and_next(ls);
 572                                 } while (islalnum(ls->current));
 573                                 ts = lex_newstring(ls, mbuff(ls->buff),
 574                                                         mbuff_len(ls->buff));
 575                                 seminfo->ts = ts;
 576                                 if (isreserved(ts))  /* reserved word? */
 577                                         return ts->tsv.extra - 1 +
 578                                                 FIRST_RESERVED;
 579                                 else {
 580                                         return TK_NAME;
 581                                 }
 582                         } else {  /* single-char tokens (+ - / ...) */
 583                                 int c = ls->current;
 584                                 next(ls);
 585                                 return c;
 586                         }
 587                 }
 588                 }
 589         }
 590 }
 591
 592 void lex_read_string_until(ktap_lexstate *ls, int c)
 593 {
 594         ktap_string *ts;
 595         char errmsg[32];
 596
 597         mbuff_reset(ls->buff);
 598
 599         while (ls->current == ' ')
 600                 next(ls);
 601
 602         do {
 603                 save_and_next(ls);
 604         } while (ls->current != c && ls->current != EOZ);
 605
 606         if (ls->current != c) {
 607                 sprintf(errmsg, "expect %c", c);
 608                 lexerror(ls, errmsg, 0);
 609         }
 610
 611         ts = lex_newstring(ls, mbuff(ls->buff), mbuff_len(ls->buff));
 612         ls->t.seminfo.ts = ts;
 613         ls->t.token = TK_STRING;
 614 }
 615
 616 void lex_next(ktap_lexstate *ls)
 617 {
 618         ls->lastline = ls->linenumber;
 619         if (ls->lookahead.token != TK_EOS) {  /* is there a look-ahead token? */
 620                 ls->t = ls->lookahead;  /* use this one */
 621                 ls->lookahead.token = TK_EOS;  /* and discharge it */
 622         } else
 623                 ls->t.token = llex(ls, &ls->t.seminfo);  /* read next token */
 624 }
 625
 626 int lex_lookahead(ktap_lexstate *ls)
 627 {
 628         ktap_assert(ls->lookahead.token == TK_EOS);
 629         ls->lookahead.token = llex(ls, &ls->lookahead.seminfo);
 630         return ls->lookahead.token;
 631 }
 632