ocean-lang.org Git - ocean/blob - csrc/scanner.mdc

   1 # Lexical Scanner #
   2
   3 ## The Task at Hand ##
   4
   5 The main task of the lexical scanner is to convert a stream of
   6 characters into a stream of tokens.  The tokens are then typically
   7 used by a parser to extract the syntactic structure.
   8
   9 The stream of characters are assumed to be in memory identified by a
  10 linked list of blocks, such as provided by the "[mdcode][]" literate
  11 program extractor.  A single token may never cross a block boundary.
  12
  13 [mdcode]: mdcode.html
  14
  15 ###### includes
  16         #include "mdcode.h"
  17
  18 The text is assumed to be UTF-8 though some matching assumes the
  19 ASCII subset.  If the text provided does not conform to UTF-8 an error
  20 will be reported and some number of bytes will be skipped.
  21
  22 ###### public types
  23         #include <wchar.h>
  24         #include <wctype.h>
  25         #include <unicode/uchar.h>
  26
  27 Tokens are returned by successive calls to the main interface
  28 function: `token_next()` which has a `state` structure to keep track
  29 of where it is up to.  Each token carries not just a numeric
  30 identifier but also the code block, the line and character within that
  31 block, and the actual start and length using the `struct text` from
  32 "mdcode".
  33
  34 ###### public types
  35         struct token {
  36                 int               num;
  37                 struct code_node *node;
  38                 struct text       txt;
  39                 int               line, col;
  40         };
  41         struct token_state;
  42
  43 ###### private types
  44         struct token_state {
  45                 ## state fields
  46         };
  47
  48 ###### exported functions
  49         struct token token_next(struct token_state *state);
  50
  51 ###### main functions
  52         struct token token_next(struct token_state *state)
  53         {
  54                 ## token_next init
  55                 while (1) {
  56                         wint_t ch;
  57                         struct token tk;
  58
  59                         ## one token
  60                 }
  61         }
  62
  63 The `line` and `col` offsets are useful for reporting errors.
  64 The `txt` provides the content when that is important.
  65
  66 ### Token types and configuration ##
  67
  68 The scanner is not completely general, yet not completely specified.
  69 There are a fixed set of token types, though particular tokens within
  70 those types can be distinguish via configuration.
  71
  72 Most token types may be explicitly ignored, as typically comments
  73 would be.  The exact consequence of ignoring each token type varies
  74 from token to token.
  75
  76 ###### public types
  77         struct token_config {
  78                 int ignored;    // bit set of ignored tokens.
  79                 ## token config parameters
  80         };
  81
  82 ###### state fields
  83         struct token_config *conf;
  84
  85 ###### token_next init
  86         int ignored = state->conf->ignored;
  87
  88
  89 The different tokens are numbers, words, marks, strings, comments,
  90 newlines, EOF, and indents, each of which is examined in detail below.
  91
  92 There are various cases where no token can be found in part of the
  93 input.  All of these will be reported as a `TK_error` token.
  94
  95 It is possible to declare a number of strings which form distinct
  96 tokens (rather than being grouped as e.g. 'word').  These are given
  97 token numbers from `TK_reserved` upwards.
  98
  99 ###### public types
 100         enum token_num {
 101                 TK_error,
 102                 ## token types
 103                 TK_reserved
 104         };
 105
 106 ### Numbers
 107
 108 Numbers are the messiest tokens to parse, primarily because they can
 109 contain characters that also have meaning outside of numbers and,
 110 particularly, immediately after numbers.
 111
 112 The obvious example is the '`-`' sign.  It can come inside a number for
 113 a negative exponent, or after a number as a subtraction operator.  To
 114 be sure we have parsed as best as possible we need to only allow the
 115 '`-`' inside a number if it is after an exponent character.  This can be
 116 `e` or `p` (for hex exponents), but `e` can also be a hexadecimal
 117 digit, so we don't allow '`-`' after just any `e`.
 118
 119 To make matters worse, our language designer has decided to experiment
 120 with allowing commas to be used as the decimal indicator, and spaces
 121 to be used to separate groups of digits in large numbers.  Both of
 122 these can reasonably be restricted to appear between two digits, so we
 123 have to add that condition to our tests.
 124
 125 So we cannot just treat numbers as starting with a digit and being
 126 followed by some set of characters.  We need more structure than that.
 127
 128 So:
 129
 130 - Numbers must start with a digit.
 131 - If the first digit is zero, the next character must be a base
 132   signifier (one of `xob`) or a decimal marker (`.` or `,`).
 133   In the first case the first `p` or `P` may be followed by a sign.
 134 - If the number doesn't start with `0` followed by one of `xob`, the
 135   first `e` may be followed by a sign.
 136 - Any digit or hex digit may be followed by a space or underscore
 137   providing that the subsequence character is also a (hex) digit.
 138   This rule will require an extra level of 'unget' to be
 139   supported when handling characters.
 140 - Otherwise any digits or ASCII letters are allowed.  We do not at
 141   this point check that the digits given are permitted by the base.
 142   That will happen when the token is converted to a number.
 143
 144 To allow easy configuration, the various non alphanumeric characters
 145 are only permitted if they are listed in a configuration parameter.
 146
 147 ###### token config parameters
 148         char *number_chars;
 149
 150 Note that numbers may not start with a period, so `.75` is not a
 151 number.  This is not the norm, but is not unheard of.  Excluding these
 152 numbers simplifies the rule at very little cost.
 153
 154 ###### token types
 155         TK_number,
 156
 157 If TK_number is ignored, digits will result in an error unless they
 158 are declared to be a start character for words.
 159
 160 ###### includes
 161
 162         #include <string.h>
 163
 164 ###### parse number
 165
 166         if (iswdigit(ch) && !(ignored & (1<<TK_number))) {
 167                 int prev_special = 0;
 168                 int expect_p = 0;
 169                 int decimal_mark = 0;
 170                 if (ch == '0') {
 171                         wchar_t ch2 = get_char(state);
 172                         if (strchr("xobXOB", ch2) != NULL)
 173                                 expect_p = 1;
 174                         unget_char(state);
 175                 }
 176                 while (1) {
 177                         int sign_ok = 0;
 178                         switch(expect_p) {
 179                         case 0:
 180                                 if (ch == 'e' || ch == 'E')
 181                                         sign_ok = 1;
 182                                 break;
 183                         case 1:
 184                                 if (ch == 'p' || ch == 'P')
 185                                         sign_ok = 1;
 186                                 break;
 187                         }
 188                         save_unget_state(state);
 189                         ch = get_char(state);
 190                         if (iswalnum(ch)) {
 191                                 prev_special = 0;
 192                                 continue;
 193                         }
 194                         if (ch == '+' || ch == '-') {
 195                                 if (!sign_ok)
 196                                         break;
 197                                 expect_p = -1;
 198                         }
 199                         if (ch == '.' || ch == ',') {
 200                                 if (decimal_mark)
 201                                         break;
 202                                 decimal_mark = 1;
 203                         }
 204                         if (prev_special) {
 205                                 /* Don't allow that special char,
 206                                  * need two 'ungets'
 207                                  */
 208                                 restore_unget_state(state);
 209                                 break;
 210                         }
 211                         if (strchr(state->conf->number_chars, ch)) {
 212                                 prev_special = 1;
 213                                 continue;
 214                         }
 215                         /* non-number char */
 216                         break;
 217                 }
 218                 /* We seem to have a "number" token */
 219                 unget_char(state);
 220                 close_token(state, &tk);
 221                 tk.num = TK_number;
 222                 return tk;
 223         }
 224
 225 ### Words
 226 Words start with a "start" character followed by the longest
 227 sequence of "continue" characters.  The Unicode ID_START and
 228 ID_CONTINUE sets are always permitted, but other ASCII characters
 229 can be added to these sets.
 230
 231 ###### token config parameters
 232         char *word_start;
 233         char *word_cont;
 234
 235 ###### internal functions
 236         static int is_word_start(wchar_t ch, struct token_config *conf)
 237         {
 238                 return iswalpha(ch) ||
 239                        strchr(conf->word_start, ch) != NULL ||
 240                        u_hasBinaryProperty(ch, UCHAR_ID_START);
 241         }
 242
 243         static int is_word_continue(wchar_t ch, struct token_config *conf)
 244         {
 245                 return iswalnum(ch) ||
 246                        strchr(conf->word_cont, ch) != NULL ||
 247                        u_hasBinaryProperty(ch, UCHAR_ID_CONTINUE);
 248         }
 249
 250 Words can be either known or unknown.  Known words are referred to as
 251 "reserved words" and get a unique token number.  Unknown words are
 252 "identifiers" and are syntactically a single token.
 253
 254 ###### token types
 255         TK_ident,
 256
 257 A list of known words must be provided.  This list is shared with the
 258 "marks" which are described next.  The list must be lexically sorted
 259 and the length of the list must be given (`known_count`).
 260 Tokens matching these known words are reported as the index of the
 261 list added to `TK_reserved`.
 262
 263 If identifiers are ignored, then any word which is not listed as a
 264 known word results in an error.
 265
 266 ###### token config parameters
 267         const char **words_marks;
 268         int known_count;
 269
 270 ###### parse word
 271
 272         if (is_word_start(ch, state->conf)) {
 273                 int n;
 274                 /* A word: identifier or reserved */
 275                 do
 276                         ch = get_char(state);
 277                 while (is_word_continue(ch, state->conf));
 278                 unget_char(state);
 279                 close_token(state, &tk);
 280                 tk.num = TK_ident;
 281                 if (ignored & (1<<TK_ident))
 282                         tk.num = TK_error;
 283                 n = find_known(state->conf, tk.txt);
 284                 if (n >= 0)
 285                         tk.num = TK_reserved + n;
 286                 return tk;
 287         }
 288
 289 ### Marks
 290
 291 Marks are generally one or more punctuation marks joined together.  It
 292 would be nice to use the term "symbol" for these, but that causes
 293 confusion in a subsequent discussion of the grammar, which has terminal
 294 symbols and non-terminal symbols which are conceptually quite
 295 different.  So strings of punctuation characters will be marks.
 296
 297 A "mark" consists of ASCII characters that are not white space, are not
 298 "start" characters for words, and are not digits.
 299 These will collectively be called mark characters.
 300
 301 ###### internal functions
 302         static int is_mark(wchar_t ch, struct token_config *conf)
 303         {
 304                 return ch > ' ' &&
 305                        ch < 0x7f &&
 306                        !iswalnum(ch) &&
 307                        strchr(conf->word_start, ch) == NULL;
 308         }
 309
 310 As with words, there can be known and unknown marks, though the rules
 311 are slightly different.
 312
 313 Two marks do not need to be separated by a non-mark characters.  This
 314 is different from words which do need to be separated by at least one
 315 non-continue character.
 316
 317 The scanner will normally prefer longer sequences of mark characters,
 318 but will more strongly prefer known marks over unknown marks.  So if
 319 it finds a known mark where adding one more character does not result
 320 in a known mark, it will return that first known mark.
 321
 322 If no known mark is found we will test against strings and comments
 323 below before giving up and assuming an unknown mark.
 324
 325 If an unknown mark contains a quote character or a comment marker, and
 326 that token is not being ignored, then we terminate the unknown mark
 327 before that quote or comment.  This ensures that an unknown mark
 328 immediately before a string is handled correctly.
 329
 330 If the first character of a comment marker (i.e. '/') is a known mark,
 331 the above rules would suggest that the start of a comment would be
 332 parsed as that mark, which is not what is wanted.  So the introductory
 333 sequences for a comment ("//" and "/*") are treated as
 334 partially-known.  They prevent the leading "/" from being a mark by
 335 itself, but do not actually constitute a stand-alone mark.
 336
 337 If `TK_mark` is ignored, then unknown marks are returned as errors.
 338
 339 ###### token types
 340         TK_mark,
 341
 342 Known marks are included in the same list as the list of known words.
 343
 344 ###### parse mark
 345         tk.num = TK_error;
 346         while (is_mark(ch, state->conf)) {
 347                 int n;
 348                 wchar_t prev;
 349                 close_token(state, &tk);
 350                 n = find_known(state->conf, tk.txt);
 351                 if (n >= 0)
 352                         tk.num = TK_reserved + n;
 353                 else if (tk.num != TK_error) {
 354                         /* found a longest-known-mark, still need to
 355                          * check for comments
 356                          */
 357                         if (tk.txt.len == 2 && tk.txt.txt[0] == '/' &&
 358                             (ch == '/' || ch == '*')) {
 359                                 /* Yes, this is a comment, not a '/' */
 360                                 restore_unget_state(state);
 361                                 tk.num = TK_error;
 362                                 break;
 363                         }
 364                         unget_char(state);
 365                         close_token(state, &tk);
 366                         return tk;
 367                 }
 368                 prev = ch;
 369                 save_unget_state(state);
 370                 ch = get_char(state);
 371                 if (!(ignored && (1<<TK_string)) && is_quote(ch))
 372                         break;
 373                 if (prev == '#' && n < 0)
 374                         /* '#' is not a known mark, so assume it is a comment */
 375                         break;
 376                 if (prev == '/' && ch == '/' && tk.txt.len == 1 && n < 0) {
 377                         close_token(state, &tk);
 378                         restore_unget_state(state);
 379                         break;
 380                 }
 381                 if (prev == '/' && ch == '*' && tk.txt.len == 1 && n < 0) {
 382                         close_token(state, &tk);
 383                         restore_unget_state(state);
 384                         break;
 385                 }
 386         }
 387         unget_char(state);
 388         if (tk.num != TK_error) {
 389                 close_token(state, &tk);
 390                 return tk;
 391         }
 392
 393 If we don't find a known mark, we will check for strings and comments
 394 before assuming that we have an unknown mark
 395
 396 ###### parse mark
 397         ## parse string
 398         ## parse comment
 399         ## unknown mark
 400
 401 ###### unknown mark
 402         if (tk.txt.len) {
 403                 if (ignored & (1<<TK_mark))
 404                         tk.num = TK_error;
 405                 else
 406                         tk.num = TK_mark;
 407                 return tk;
 408         }
 409
 410 ### Strings
 411
 412 Strings start with one of single quote, double quote, or back quote
 413 and continue until a matching character on the same line.  Any of
 414 these characters can be included in the list of known marks and then
 415 they will not be used for identifying strings.
 416
 417 Immediately following the close quote, one or two ASCII letters may
 418 appear.  These are somewhat like the arbitrary letters allowed in
 419 "Numbers" above.  They can be used by the language in various ways.
 420
 421 If 3 identical quote characters appear in a row and are
 422 followed by a newline, then this forms a multi-line string which
 423 continues until an identical triple quote appears on a line preceded
 424 only by whitespace and followed immediately by 0-2 ASCII letters and a newline.
 425
 426 Multi-line strings may not extend beyond the end of the `code_node` in
 427 which they start.
 428
 429 Normal strings and multi-line strings are encoded as two different
 430 token types.
 431
 432 ###### token types
 433         TK_string,
 434         TK_multi_string,
 435
 436 ###### internal functions
 437         static int is_quote(wchar_t ch)
 438         {
 439                 return ch == '\'' || ch == '"' || ch == '`';
 440         }
 441
 442 #### Multi-line strings
 443
 444 The multi-line string is checked for first.  If they are being
 445 ignored, we fall through and treat a triple quote as an empty string
 446 followed by the start of a new string.
 447
 448 ###### parse string
 449         if (tk.txt.len == 3 &&
 450             !(ignored & (1 << TK_multi_string)) &&
 451             is_quote(tk.txt.txt[0]) &&
 452             memcmp(tk.txt.txt, tk.txt.txt+1, 2) == 0 &&
 453             is_newline(tk.txt.txt[3])) {
 454                 // triple quote
 455                 wchar_t first = tk.txt.txt[0];
 456                 int qseen = 0;
 457                 int at_sol = 1;
 458                 while (!at_eon(state) && qseen < 3) {
 459                         ch = get_char(state);
 460                         if (is_newline(ch)) {
 461                                 at_sol = 1;
 462                                 qseen = 0;
 463                         } else if (at_sol && ch == first) {
 464                                 qseen += 1;
 465                         } else if (ch != ' ' && ch != '\t') {
 466                                 at_sol = 0;
 467                                 qseen = 0;
 468                         }
 469                 }
 470                 if (qseen != 3) {
 471                         /* Hit end of node - error.
 472                          * unget so the newline is seen,
 473                          * but return rest of string as an error.
 474                          */
 475                         if (is_newline(ch))
 476                                 unget_char(state);
 477                         close_token(state, &tk);
 478                         tk.num = TK_error;
 479                         return tk;
 480                 }
 481                 /* 2 letters are allowed */
 482                 ch = get_char(state);
 483                 if (iswalpha(ch))
 484                         ch = get_char(state);
 485                 if (iswalpha(ch))
 486                         ch = get_char(state);
 487                 /* Now we must have a newline, but we don't return it
 488                  * whatever it is.*/
 489                 unget_char(state);
 490                 close_token(state, &tk);
 491                 tk.num = TK_multi_string;
 492                 if (!is_newline(ch))
 493                         tk.num = TK_error;
 494                 return tk;
 495         }
 496
 497 #### Single-line strings
 498
 499 The sequence of marks collected may be more than a single-line
 500 string, so we reset to the start and collect characters until
 501 we find a close quote or a newline.
 502
 503 If `TK_string` is ignored, then quote characters will appear as `TK_mark`s.
 504
 505 ###### parse string
 506         if (tk.txt.len && is_quote(tk.txt.txt[0]) &&
 507             !(ignored & (1<<TK_string))) {
 508                 wchar_t first = tk.txt.txt[0];
 509                 reset_token(state, &tk);
 510                 ch = get_char(state);
 511                 tk.num = TK_error;
 512                 while (!at_eon(state) && !is_newline(ch)) {
 513                         ch = get_char(state);
 514                         if (ch == first) {
 515                                 tk.num = TK_string;
 516                                 break;
 517                         }
 518                         if (is_newline(ch)) {
 519                                 unget_char(state);
 520                                 break;
 521                         }
 522                 }
 523                 while (!at_eon(state) && (ch = get_char(state)) &&
 524                                           iswalpha(ch))
 525                         ;
 526                 unget_char(state);
 527                 close_token(state, &tk);
 528                 return tk;
 529         }
 530
 531 ### Comments
 532
 533 Single line comments may start with '`//`' or '`#`' providing that these
 534 are not known marks.  They continue to the end of the line.
 535
 536 Block comments start with '`/*`' if this is not a known mark.  They
 537 continue to the first occurrence of '`*/`' and may not contain any
 538 occurrence of '`/*`'.
 539
 540 Block comments can be wholly within one line or can continue over
 541 multiple lines.  The multi-line version should be followed immediately
 542 by a newline.  The Linux kernel contains over 285000 multi-line
 543 comments are only 34 are followed by characters other than white space
 544 (which should be removed) or a backslash (only needed in macros).  So
 545 it would not suffer from this rule.
 546
 547 These two comment types are reported as two separate token types, and
 548 consequently can be ignored separately.  When ignored a comment is
 549 still parsed, but is discarded.
 550
 551 ###### token types
 552         TK_line_comment,
 553         TK_block_comment,
 554
 555 ###### internal functions
 556         static int is_line_comment(struct text txt)
 557         {
 558                 return (txt.len >= 1 && txt.txt[0] == '#') ||
 559                        (txt.len >= 2 && txt.txt[0] == '/' &&
 560                                         txt.txt[1] == '/');
 561         }
 562
 563         static int is_block_comment(struct text txt)
 564         {
 565                 return txt.len >= 2 && txt.txt[0] == '/' &&
 566                        txt.txt[1] == '*';
 567         }
 568
 569 #### Single line comments
 570
 571 A single-line comment continues up to, but not including the newline
 572 or end of node.
 573
 574 ###### parse comment
 575
 576         if (is_line_comment(tk.txt)) {
 577                 while (!is_newline(ch) && !at_eon(state))
 578                         ch = get_char(state);
 579                 if (is_newline(ch))
 580                         unget_char(state);
 581                 close_token(state, &tk);
 582                 tk.num = TK_line_comment;
 583                 if (ignored & (1 << TK_line_comment))
 584                         continue;
 585                 return tk;
 586         }
 587
 588 #### Block comments
 589
 590 The token text collected so far could exceed the comment, so we need
 591 to reset it first.
 592
 593 If we find an embedded `/*` we reset to just before the '/' and report
 594 an error.  That way the next thing to be parsed will be the rest of
 595 the comment.  This requires a double unget, so we need to save/restore
 596 the unget state (explained later).
 597
 598 ###### parse comment
 599
 600         if (is_block_comment(tk.txt)) {
 601                 wchar_t prev;
 602                 int newlines = 0;
 603                 reset_token(state, &tk);
 604                 get_char(state);
 605                 get_char(state);
 606                 save_unget_state(state);
 607                 ch = get_char(state);
 608                 prev = 0;
 609                 while (!at_eon(state) &&
 610                        (prev != '/' || ch != '*') &&
 611                        (prev != '*' || ch != '/')) {
 612                         if (is_newline(ch))
 613                                 newlines = 1;
 614                         prev = ch;
 615                         save_unget_state(state);
 616                         ch = get_char(state);
 617                 }
 618                 close_token(state, &tk);
 619                 if (at_eon(state)) {
 620                         tk.num = TK_error;
 621                         return tk;
 622                 }
 623                 if (prev == '/') {
 624                         /* embedded.  Need to unget twice! */
 625                         restore_unget_state(state);
 626                         unget_char(state);
 627                         tk.num = TK_error;
 628                         return tk;
 629                 }
 630                 tk.num = TK_block_comment;
 631                 if (newlines && !(ignored & (1<<TK_newline))) {
 632                         /* next char must be newline */
 633                         ch = get_char(state);
 634                         unget_char(state);
 635                         if (!is_newline(ch))
 636                                 tk.num = TK_error;
 637                 }
 638                 if (tk.num == TK_error ||
 639                     !(ignored & (1 << TK_block_comment)))
 640                         return tk;
 641                 continue;
 642         }
 643
 644 ### Indents, Newlines, and White Space.
 645
 646 Normally white space is ignored.  However newlines can be important as
 647 can indents, which are either after a newline or at the start of a
 648 node (detected by `at_son()`);
 649
 650 ###### exported functions
 651         static inline int is_newline(wchar_t ch)
 652         {
 653                 return ch == '\n' || ch == '\f' || ch == '\v';
 654         }
 655
 656 ###### white space
 657         if (ch <= ' ' && !is_newline(ch)
 658             && ! at_son(state))
 659                 continue;
 660
 661 If a line starts with more white-space than the previous non-blank
 662 line - or if the first non-blank line in the document starts with any
 663 white-space - then an "IN" is reported at the start of the line.
 664
 665 Before the next non-blank line which starts with less white space, or
 666 at the latest at the end of the document, a matching "OUT" token
 667 is reported.  There will always be an exact match between "IN" and
 668 "OUT" tokens.
 669
 670 It is possible for "OUT" to be followed (almost) immediately by an
 671 "IN".  This happens if, for example, the indent of three consecutive
 672 lines are 0, 8, 4 spaces.  Before the second line we report an
 673 "IN".  Before the third line we must report an "OUT", as 4 is less
 674 than 8, then also an Ident as 4 is greater than 0.
 675
 676 ###### token types
 677         TK_in,
 678         TK_out,
 679
 680 For the purpose of measuring the length of white space, a tab adds at
 681 least one space, and rounds up to a multiple of 8.
 682
 683 ###### exported functions
 684         static inline int indent_tab(int indent)
 685         {
 686                 return (indent|7)+1;
 687         }
 688
 689 We need to track the current levels of indent.  This requires some
 690 sort of stack as indent levels are pushed on and popped off.  In
 691 practice this stack is unlikely to often exceed 5 so we will used a
 692 fixed stack of 20 indent levels.  More than this will be silently
 693 ignored.
 694
 695 ###### state fields
 696         int     indent_level;
 697         int     indent_sizes[20];
 698
 699 #### Newlines
 700
 701 Newlines can optionally be reported.  Newlines within a block comment
 702 or a multi-line string are not reported separately, but each of these
 703 must be followed immediately by a newline so these constructs cannot
 704 hide the fact that a newline was present.
 705
 706 When indents are being reported, the Newline which would normally be
 707 reported immediately before the "IN" is delayed until after the
 708 matching "OUT".  This makes an indented section act like a
 709 continuation of the previous line to some extent.
 710
 711 A blank line would normally be reported simply as two consecutive Newline
 712 tokens.  However if the subsequent line is indented (and indents are being
 713 reported) then the right thing to do is less obvious as Newlines should be
 714 delayed - but how many Newlines?
 715
 716 The approach we will take is to report the extra Newlines immediately after
 717 the IN token, so the blank line is treated as though it were an indented
 718 blank line.
 719
 720 ###### token types
 721         TK_newline,
 722
 723 If we find a newline or white space at the start of a block, we keep
 724 collecting spaces, tabs, and newlines until we find some real text.
 725 Then depending on the indent we generate some number of tokens.  These
 726 will be a sequence of "Newline OUT" pairs representing a decrease
 727 in indent, then either a Newline or an IN depending on whether the
 728 next line is indented, then zero or more Newlines representing all the
 729 blank lines that have been skipped.
 730
 731 When a Newline leads to the next block of code there is a question of
 732 whether the various Newline and OUT/IN tokens should appear to
 733 pbelong to the earlier or later block.  This is addressed by processing
 734 the tokens in two stages based on the relative indent levels of the
 735 two blocks (each block has a base indent to which the actual indents
 736 are added).
 737
 738 Any "Newline OUT" pairs needed to reduce the current indent to the
 739 maximum of the base indents of the old and new blocks are generated
 740 against the old block.  Then if the next block does not have an
 741 increased indent, one more "Newline" is generated.
 742
 743 If further "Newline OUT" pairs are needed to get to the indent
 744 level of the 'next' block, they are generated against that block,
 745 though the first Newline is suppressed (it having already been
 746 generated).
 747
 748 Finally the Newline or IN for the first line of the new block is
 749 generated, unless the Newline needs to be suppressed because it
 750 appeared at the end of the previous block.
 751
 752 This means that a block may start with an OUT or an IN, but
 753 will only start with a Newline if it actually starts with a blank
 754 line.
 755
 756 We will need to represent in the `token_state` where in this sequence
 757 of delayed tokens we are.  As `state.col` records the target indent we
 758 don't need to record how many OUTs or INs are needed.  We do
 759 need to record the number of blank lines, and which of Newline and
 760 OUT is needed next in the initial sequence of pairs.
 761
 762 For this we store one more than the number of blank lines as
 763 `delayed_lines` and a flag for `out_next`.
 764
 765 ###### state fields
 766         int check_indent;
 767         int delayed_lines;
 768         int out_next;
 769
 770 Generating these tokens involve two separate pieces of code.
 771
 772 Firstly we need to recognise white space and count the indents and
 773 newlines.  These are recorded in the above state fields.
 774
 775 Separately we need, on each call to `token_next`, we need to check if
 776 there are some delayed tokens and if so we need to advance the state
 777 information and return one token.
 778
 779 ###### white space
 780         if (is_newline(ch) || (at_son(state) && ch <= ' ')) {
 781                 int newlines = 0;
 782                 int was_son = at_son(state);
 783                 if (ignored & (1<<TK_in)) {
 784                         if (!is_newline(ch))
 785                                 continue;
 786                         if (ignored & (1<<TK_newline))
 787                                 continue;
 788                         tk.num = TK_newline;
 789                         close_token(state, &tk);
 790                         return tk;
 791                 }
 792                 // Indents are needed, so check all white space.
 793                 while (ch <= ' ' && !at_eon(state)) {
 794                         if (is_newline(ch))
 795                                 newlines += 1;
 796                         ch = get_char(state);
 797                 }
 798                 if (at_eon(state)) {
 799                         newlines += 1;
 800                         if (state->node->next &&
 801                             state->node->next->indent > state->node->indent)
 802                                 state->col = state->node->next->indent;
 803                         else
 804                                 state->col = state->node->indent;
 805                 } else
 806                         unget_char(state);
 807                 state->delayed_lines = newlines;
 808                 state->out_next = was_son;
 809                 state->check_indent = 1;
 810                 continue;
 811         }
 812
 813
 814 ###### delayed tokens
 815
 816         if (state->check_indent || state->delayed_lines) {
 817                 if (state->col < state->indent_sizes[state->indent_level]) {
 818                         if (!state->out_next &&
 819                             !(ignored & (1<<TK_newline))) {
 820                                 state->out_next = 1;
 821                                 tk.num = TK_newline;
 822                                 return tk;
 823                         }
 824                         state->indent_level -= 1;
 825                         state->out_next = 0;
 826                         tk.num = TK_out;
 827                         return tk;
 828                 }
 829                 if (state->col > state->indent_sizes[state->indent_level] &&
 830                     state->indent_level < sizeof(state->indent_sizes)-1) {
 831                         state->indent_level += 1;
 832                         state->indent_sizes[state->indent_level] = state->col;
 833                         state->delayed_lines -= 1;
 834                         tk.num = TK_in;
 835                         return tk;
 836                 }
 837                 state->check_indent = 0;
 838                 if (state->delayed_lines && !(ignored & (1<<TK_newline))) {
 839                         tk.num = TK_newline;
 840                         state->delayed_lines -= 1;
 841                         return tk;
 842                 }
 843                 state->delayed_lines = 0;
 844                 continue;
 845         }
 846
 847 ### End of File
 848
 849 After the last newline in the file has been processed, a special
 850 end-of-file token will be returned.  any further attempts to get more
 851 tokens will continue to return the same end-of-file token.
 852
 853 ###### token types
 854         TK_eof,
 855
 856
 857 ###### white space
 858         if (ch == WEOF) {
 859                 if (state->col) {
 860                         state->col = 0;
 861                         state->check_indent = 1;
 862                         continue;
 863                 }
 864                 tk.num = TK_eof;
 865                 return tk;
 866         }
 867
 868 ### Unknown Marks, or errors.
 869
 870 We have now handled all the possible known mark-like tokens.
 871 If the token we have is not empty and `TK_mark` is allowed,
 872 we have an unknown mark, otherwise this must be an error.
 873
 874 ###### unknown mark
 875         /* one unknown character */
 876         close_token(state, &tk);
 877         tk.num = TK_error;
 878         return tk;
 879
 880 ## Tools For The Task
 881
 882 You may have noticed that are few gaps we left in the above -
 883 functions used without first defining them.  Doing so above would have
 884 broken the flow.
 885
 886 ### Character by character
 887
 888 As we walk through the various `code_node`s we need to process whole
 889 Unicode codepoints, and keep track of which line and column we are on.
 890 We will assume for now that any printing character uses one column,
 891 though that is not true in general.
 892
 893 As the text in a `code_node` may include an indent that identifies it as
 894 being code, we need to be careful to strip that.  The `code_node` has
 895 a flag that tells us whether or not we need to strip.
 896
 897 ###### includes
 898         #include <memory.h>
 899
 900 ###### state fields
 901         struct code_node *node;
 902         int    offset;
 903         int    line;
 904         int    col;
 905
 906 ###### internal functions
 907
 908         static int do_strip(struct token_state *state)
 909         {
 910                 int indent = 0;
 911                 if (state->node->needs_strip) {
 912                         int n = 4;
 913                         while (n && state->node->code.txt[state->offset] == ' ') {
 914                                 indent += 1;
 915                                 state->offset += 1;
 916                                 n -= 1;
 917                         }
 918                         while (n == 4 && state->node->code.txt[state->offset] == '\t') {
 919                                 indent = indent_tab(indent);
 920                                 state->offset += 1;
 921                                 n -= 4;
 922                         }
 923                 }
 924                 return indent;
 925         }
 926
 927         static wint_t get_char(struct token_state *state)
 928         {
 929                 wchar_t next;
 930                 size_t n;
 931                 mbstate_t mbstate;
 932
 933                 if (state->node == NULL)
 934                         return WEOF;
 935                 if (state->node->code.len <= state->offset) {
 936                         do
 937                                 state->node = state->node->next;
 938                         while (state->node && state->node->code.txt == NULL);
 939                         state->offset = 0;
 940                         if (state->node == NULL)
 941                                 return WEOF;
 942                         state->line = state->node->line_no;
 943                         state->col = do_strip(state);
 944                 }
 945
 946                 ## before get_char
 947
 948                 memset(&mbstate, 0, sizeof(mbstate));
 949
 950                 n = mbrtowc(&next, state->node->code.txt + state->offset,
 951                             state->node->code.len - state->offset,
 952                             &mbstate);
 953                 if (n == -2 || n == 0) {
 954                         /* Not enough bytes - not really possible */
 955                         next = '\n';
 956                         state->offset = state->node->code.len;
 957                 } else if (n == -1) {
 958                         /* error */
 959                         state->offset += 1;
 960                         next = 0x7f; // an illegal character
 961                 } else
 962                         state->offset += n;
 963
 964                 if (next >= ' ') {
 965                         state->col += 1;
 966                 } else if (is_newline(next)) {
 967                         state->line += 1;
 968                         state->col = do_strip(state);
 969                 } else if (next == '\t') {
 970                         state->col = indent_tab(state->col);
 971                 }
 972                 return next;
 973         }
 974
 975 We will sometimes want to "unget" the last character as it needs to be
 976 considered again as part of the next token.  So we need to store a
 977 'previous' version of all metadata.
 978
 979 ###### state fields
 980         int    prev_offset;
 981         int    prev_line;
 982         int    prev_col;
 983
 984 ###### before get_char
 985         state->prev_offset = state->offset;
 986         state->prev_line   = state->line;
 987         state->prev_col    = state->col;
 988
 989 ###### internal functions
 990
 991         static void unget_char(struct token_state *state)
 992         {
 993                 if (state->node) {
 994                         state->offset = state->prev_offset;
 995                         state->line   = state->prev_line;
 996                         state->col    = state->prev_col;
 997                 }
 998         }
 999
1000 We occasionally need a double-unget, particularly for numbers and
1001 block comments.  We don't impose this cost on all scanning, but
1002 require those code sections that need it to call `save_unget_state`
1003 before each `get_char`, and then `restore_unget_state` when a
1004 double-unget is needed.
1005
1006 ###### state fields
1007         int     prev_offset2;
1008         int     prev_line2;
1009         int     prev_col2;
1010
1011 ###### internal functions
1012         static void save_unget_state(struct token_state *state)
1013         {
1014                 state->prev_offset2 = state->prev_offset;
1015                 state->prev_line2 = state->prev_line;
1016                 state->prev_col2 = state->prev_col;
1017         }
1018
1019         static void restore_unget_state(struct token_state *state)
1020         {
1021                 state->prev_offset = state->prev_offset2;
1022                 state->prev_line = state->prev_line2;
1023                 state->prev_col = state->prev_col2;
1024         }
1025
1026 At the start of a token we don't want to be at the end of a code block
1027 if we can help it.  To avoid this possibility, we 'get' and 'unget' a
1028 single character.  This will move into the next non-empty code block
1029 and leave the current pointer at the start of it.
1030
1031 This has to happen _after_ dealing with delayed tokens as some of them
1032 must appear in the previous node.  When we do this, we need to reset
1033 the data in the token.
1034
1035 ###### delayed tokens
1036         if (at_eon(state)) {
1037                 get_char(state);
1038                 unget_char(state);
1039                 tk.node = state->node;
1040                 if (state->node)
1041                         tk.txt.txt = state->node->code.txt + state->offset;
1042                 tk.line = state->line;
1043                 tk.col = state->col;
1044                 tk.txt.len = 0;
1045         }
1046
1047 ### Managing tokens
1048
1049 The current token is initialized to line up with the first character
1050 that we 'get' for each token.  When we have, or might have, a full
1051 token we can call `close_token` to set the `len` of the token
1052 appropriately.  This can safely be called multiple times.
1053
1054 Finally we occasionally (for single-line strings and block comments)
1055 need to reset to the beginning of the current token as we might have
1056 parsed too much already.  For that there is `reset_token`.
1057
1058 ###### one token
1059         tk.node = state->node;
1060         if (state->node)
1061                 tk.txt.txt = state->node->code.txt + state->offset;
1062         tk.line = state->line;
1063         tk.col = state->col;
1064         tk.txt.len = 0;
1065
1066 ###### internal functions
1067
1068         static void close_token(struct token_state *state,
1069                                 struct token *tk)
1070         {
1071                 tk->txt.len = (state->node->code.txt + state->offset)
1072                               - tk->txt.txt;
1073         }
1074
1075         static void reset_token(struct token_state *state, struct token *tok)
1076         {
1077                 state->prev_line = tok->line;
1078                 state->prev_col = tok->col;
1079                 state->prev_offset = tok->txt.txt - state->node->code.txt;
1080                 unget_char(state);
1081                 tok->txt.len = 0;
1082         }
1083
1084
1085 Tokens make not cross into the next `code_node`, and some tokens can
1086 include the newline at the and of a `code_node`, we must be able to
1087 easily check if we have reached the end.  Equally we need to know if
1088 we are at the start of a node, as white space is treated a little
1089 differently there.
1090
1091 ###### internal functions
1092
1093         static int at_son(struct token_state *state)
1094         {
1095                 return state->offset == 0;
1096         }
1097
1098         static int at_eon(struct token_state *state)
1099         {
1100                 // at end-of-node ??
1101                 return state->node == NULL ||
1102                        state->offset >= state->node->code.len;
1103         }
1104
1105 ### Find a known word
1106
1107 As the known-word list is sorted we can use a simple binary search.
1108 Following the pattern established in "mdcode", we will use a `struct
1109 text` with start and length to represent the code fragment we are
1110 searching for.
1111
1112 ###### internal functions
1113         static int find_known(struct token_config *conf, struct text txt)
1114         {
1115                 int lo = 0;
1116                 int hi = conf->known_count;
1117
1118                 while (lo + 1 < hi) {
1119                         int mid = (lo + hi) / 2;
1120                         int cmp = strncmp(conf->words_marks[mid],
1121                                           txt.txt, txt.len);
1122                         if (cmp == 0 && conf->words_marks[mid][txt.len])
1123                                 cmp = 1;
1124                         if (cmp <= 0)
1125                                 lo = mid;
1126                         else
1127                                 hi = mid;
1128                 }
1129                 if (strncmp(conf->words_marks[lo],
1130                            txt.txt, txt.len) == 0
1131                     && conf->words_marks[lo][txt.len] == 0)
1132                         return lo;
1133                 else
1134                         return -1;
1135         }
1136
1137 ### Bringing it all together
1138
1139 Now we have all the bits there is just one section missing:  combining
1140 all the token parsing code into one block.
1141
1142 The handling of delayed tokens (Newlines, INs, OUTs) must come
1143 first before we try getting another character.
1144
1145 Then we parse all the test, making sure that we check for known marks
1146 before strings and comments, but unknown marks after strings and comments.
1147
1148 This block of code will either return a token, or will choose to
1149 ignore one, in which case it will `continue` around to the top of the
1150 loop.
1151
1152 ###### one token
1153         ## delayed tokens
1154
1155         ch = get_char(state);
1156
1157         ## white space
1158         ## parse number
1159         ## parse word
1160         ## parse mark
1161
1162 ### Start and stop
1163
1164 As well as getting tokens, we need to be able to create the
1165 `token_state` to start with, and discard it later.
1166
1167 ###### includes
1168         #include <malloc.h>
1169
1170 ###### main functions
1171         struct token_state *token_open(struct code_node *code, struct
1172                                        token_config *conf)
1173         {
1174                 struct token_state *state = malloc(sizeof(*state));
1175                 memset(state, 0, sizeof(*state));
1176                 state->node = code;
1177                 state->line = code->line_no;
1178                 state->col = do_strip(state);
1179                 state->conf = conf;
1180                 return state;
1181         }
1182         void token_close(struct token_state *state)
1183         {
1184                 free(state);
1185         }
1186
1187 ###### exported functions
1188         struct token_state *token_open(struct code_node *code, struct
1189                                        token_config *conf);
1190         void token_close(struct token_state *state);
1191
1192 ### Trace tokens
1193
1194 Getting tokens is the main thing but it is also useful to be able to
1195 print out token information, particularly for tracing and testing.
1196
1197 Known tokens are printed verbatim.  Other tokens are printed as
1198 `type(content)` where content is truncated to a given number of characters.
1199
1200 The function for printing a truncated string (`text_dump`) is also exported
1201 so that it can be used to tracing processed strings too.
1202
1203 ###### includes
1204         #include <stdio.h>
1205
1206 ###### exported functions
1207         void token_trace(FILE *f, struct token tok, int max);
1208         void text_dump(FILE *f, struct text t, int max);
1209
1210 ###### main functions
1211
1212         void text_dump(FILE *f, struct text txt, int max)
1213         {
1214                 int i;
1215                 if (txt.len > max)
1216                         max -= 2;
1217                 else
1218                         max = txt.len;
1219                 for (i = 0; i < max; i++) {
1220                         char c = txt.txt[i];
1221                         if (c < ' ' || c > '~')
1222                                 fprintf(f, "\\x%02x", c & 0xff);
1223                         else if (c == '\\')
1224                                 fprintf(f, "\\\\");
1225                         else
1226                                 fprintf(f, "%c", c);
1227                 }
1228                 if (i < txt.len)
1229                         fprintf(f, "..");
1230         }
1231
1232         void token_trace(FILE *f, struct token tok, int max)
1233         {
1234                 static char *types[] = {
1235                         [TK_ident] = "ident",
1236                         [TK_mark] = "mark",
1237                         [TK_number] = "number",
1238                         [TK_string] = "string",
1239                         [TK_multi_string] = "mstring",
1240                         [TK_line_comment] = "lcomment",
1241                         [TK_block_comment] = "bcomment",
1242                         [TK_in] = "in",
1243                         [TK_out] = "out",
1244                         [TK_newline] = "newline",
1245                         [TK_eof] = "eof",
1246                         [TK_error] = "ERROR",
1247                         };
1248
1249                 switch (tok.num) {
1250                 default: /* known word or mark */
1251                         fprintf(f, "%.*s", tok.txt.len, tok.txt.txt);
1252                         break;
1253                 case TK_in:
1254                 case TK_out:
1255                 case TK_newline:
1256                 case TK_eof:
1257                         /* No token text included */
1258                         fprintf(f, "%s()", types[tok.num]);
1259                         break;
1260                 case TK_ident:
1261                 case TK_mark:
1262                 case TK_number:
1263                 case TK_string:
1264                 case TK_multi_string:
1265                 case TK_line_comment:
1266                 case TK_block_comment:
1267                 case TK_error:
1268                         fprintf(f, "%s(", types[tok.num]);
1269                         text_dump(f, tok.txt, max);
1270                         fprintf(f, ")");
1271                         break;
1272                 }
1273         }
1274
1275 ### And there we have it
1276
1277 We now have all the library functions defined for reading and printing
1278 tokens.  Now we just need C files to store them, and a mk file to make them.
1279
1280 ###### File: scanner.h
1281         ## public types
1282         ## exported functions
1283
1284 ###### File: libscanner.c
1285         ## includes
1286         #include "scanner.h"
1287         ## private types
1288         ## internal functions
1289         ## main functions
1290
1291 ###### File: scanner.mk
1292
1293         CFLAGS += -Wall -g
1294         all ::
1295         scanner.mk scanner.h libscanner.c : scanner.mdc
1296                 ./md2c scanner.mdc
1297         all :: libscanner.o
1298         libscanner.o : libscanner.c
1299                 $(CC) $(CFLAGS) -c libscanner.c
1300
1301 ## Processing numbers
1302
1303 Converting a `TK_number` token to a numerical value is a slightly
1304 higher level task than lexical analysis, and slightly lower than
1305 grammar parsing, so put it here - as an index if you like.
1306
1307 Importantly it will be used by the same testing rig that is used for
1308 testing the token scanner.
1309
1310 The numeric value that we will convert all numbers into is the `mpq_t`
1311 from the GNU high precision number library "libgmp".
1312
1313 ###### number includes
1314         #include <gmp.h>
1315         #include "mdcode.h"
1316
1317 Firstly we need to be able to parse a string of digits in a given base
1318 and possibly with a decimal marker.  We store this in an `mpz_t`
1319 integer and report the number of digits after the decimal mark.
1320
1321 On error we return zero and ensure that the 'mpz_t' has been freed, or
1322 had never been initialised.
1323
1324 ###### number functions
1325
1326         static int parse_digits(mpz_t num, struct text tok, int base,
1327                                 int *placesp)
1328         {
1329                 /* Accept digits up to 'base', ignore '_' and
1330                  * ' ' if they appear between two legal digits,
1331                  * and if `placesp` is not NULL, allow a single
1332                  * '.' or ',' and report the number of digits
1333                  * beyond there.
1334                  * Return number of characters processed (p),
1335                  * or 0 if something illegal was found.
1336                  */
1337                 int p;
1338                 int decimal = -1; // digits after marker
1339                 enum {Digit, Space, Other} prev = Other;
1340                 int digits = 0;
1341
1342                 for (p = 0; p < tok.len; p++) {
1343                         int dig;
1344                         char c = tok.txt[p];
1345
1346                         if (c == '_' || c == ' ') {
1347                                 if (prev != Digit)
1348                                         goto bad;
1349                                 prev = Space;
1350                                 continue;
1351                         }
1352                         if (c == '.' || c == ',') {
1353                                 if (prev != Digit)
1354                                         goto bad;
1355                                 if (!placesp || decimal >= 0)
1356                                         return p-1;
1357                                 decimal = 0;
1358                                 prev = Other;
1359                                 continue;
1360                         }
1361                         if (isdigit(c))
1362                                 dig = c - '0';
1363                         else if (isupper(c))
1364                                 dig = 10 + c - 'A';
1365                         else if (islower(c))
1366                                 dig = 10 + c - 'a';
1367                         else
1368                                 dig = base;
1369                         if (dig >= base) {
1370                                 if (prev == Space)
1371                                         p--;
1372                                 break;
1373                         }
1374                         prev = Digit;
1375                         if (digits)
1376                                 mpz_mul_ui(num, num, base);
1377                         else
1378                                 mpz_init(num);
1379                         digits += 1;
1380                         mpz_add_ui(num, num, dig);
1381                         if (decimal >= 0)
1382                                 decimal++;
1383                 }
1384                 if (digits == 0)
1385                         return 0;
1386                 if (placesp) {
1387                         if (decimal >= 0)
1388                                 *placesp = decimal;
1389                         else
1390                                 *placesp = 0;
1391                 }
1392                 return p;
1393         bad:
1394                 if (digits)
1395                         mpz_clear(num);
1396                 return 0;
1397         }
1398
1399 ###### number includes
1400         #include <ctype.h>
1401
1402 To parse a full number we need to consider the optional base, the
1403 mantissa, and the optional exponent.  We will treat these one at a
1404 time.
1405
1406 The base is indicated by a letter after a leading zero, which must be
1407 followed by a base letter or a period.  The base also determines the
1408 character which will mark an exponent.
1409
1410 ###### number vars
1411         int base = 10;
1412         char expc = 'e';
1413
1414 ###### parse base
1415
1416         if (tok.txt[0] == '0' && tok.len > 1) {
1417                 int skip = 0;
1418                 switch(tok.txt[1]) {
1419                 case 'x':
1420                 case 'X':
1421                         base = 16;
1422                         skip = 2;
1423                         expc = 'p';
1424                         break;
1425                 case 'o':
1426                 case 'O':
1427                         base = 8;
1428                         skip = 2;
1429                         expc = 'p';
1430                         break;
1431                 case 'b':
1432                 case 'B':
1433                         base = 2;
1434                         skip = 2;
1435                         expc = 'p';
1436                         break;
1437                 case '0':
1438                 case '1':
1439                 case '2':
1440                 case '3':
1441                 case '4':
1442                 case '5':
1443                 case '6':
1444                 case '7':
1445                 case '8':
1446                 case '9':
1447                 case '_':
1448                 case ' ':
1449                         // another digit is not permitted
1450                         // after a zero.
1451                         return 0;
1452                 default:
1453                         // must be decimal marker or trailing
1454                         // letter, which are OK;
1455                         break;
1456                 }
1457                 tok.txt += skip;
1458                 tok.len -= skip;
1459         }
1460
1461 After the base is the mantissa, which may contain a decimal mark, so
1462 we need to record the number of places.  We won't impose the number of
1463 places until we have the exponent as well.
1464
1465 ###### number vars
1466         int places =0;
1467         mpz_t mant;
1468         int d;
1469
1470 ###### parse mantissa
1471
1472         d = parse_digits(mant, tok, base, &places);
1473         if (d == 0)
1474                 return 0;
1475         tok.txt += d;
1476         tok.len -= d;
1477         mpq_init(num);
1478         mpq_set_z(num, mant);
1479         mpz_clear(mant);
1480
1481 After the mantissa number may come an exponent which may be positive
1482 or negative.  We assume at this point that we have seen the exponent
1483 character `expc`.
1484
1485 ###### number vars
1486         long lexp = 0;
1487         mpz_t exp;
1488         int esign = 1;
1489
1490 ###### parse exponent
1491         if (tok.len > 1) {
1492                 if (tok.txt[0] == '+') {
1493                         tok.txt++;
1494                         tok.len--;
1495                 } else if (tok.txt[0] == '-') {
1496                         esign = -1;
1497                         tok.txt++;
1498                         tok.len--;
1499                 }
1500         }
1501         d = parse_digits(exp, tok, 10, NULL);
1502         if (d == 0) {
1503                 mpq_clear(num);
1504                 return 0;
1505         }
1506         if (!mpz_fits_slong_p(exp)) {
1507                 mpq_clear(num);
1508                 mpz_clear(exp);
1509                 return 0;
1510         }
1511         lexp = mpz_get_si(exp) * esign;
1512         mpz_clear(exp);
1513         tok.txt += d;
1514         tok.len -= d;
1515
1516
1517 Now that we have the mantissa and the exponent we can multiply them
1518 together, also allowing for the number of digits after the decimal
1519 mark.
1520
1521 For base 10, we simply subtract the decimal places from the exponent.
1522 For the other bases, as the exponent is alway based on 2, even for
1523 octal and hex, we need a bit more detail.
1524 We then recover the sign from the exponent, as division is quite
1525 different from multiplication.
1526
1527 ###### calc exponent
1528         switch (base) {
1529         case 10:
1530         case 2:
1531                 lexp -= places;
1532                 break;
1533         case 16:
1534                 lexp -= 4*places;
1535                 break;
1536         case 8:
1537                 lexp -= 3*places;
1538                 break;
1539         }
1540         if (lexp < 0) {
1541                 lexp = -lexp;
1542                 esign = -1;
1543         } else
1544                 esign = 1;
1545
1546 Imposing the exponent on the number is also very different for base 10
1547 than for the others.  For the binary shift `gmp` provides a simple
1548 function.  For base 10 we use something like Russian Peasant
1549 Multiplication.
1550
1551 ###### calc exponent
1552         if (expc == 'e') {
1553                 mpq_t tens;
1554                 mpq_init(tens);
1555                 mpq_set_ui(tens, 10, 1);
1556                 while (1) {
1557                         if (lexp & 1) {
1558                                 if (esign > 0)
1559                                         mpq_mul(num, num, tens);
1560                                 else
1561                                         mpq_div(num, num, tens);
1562                         }
1563                         lexp >>= 1;
1564                         if (lexp == 0)
1565                                 break;
1566                         mpq_mul(tens, tens, tens);
1567                 }
1568                 mpq_clear(tens);
1569         } else {
1570                 if (esign > 0)
1571                         mpq_mul_2exp(num, num, lexp);
1572                 else
1573                         mpq_div_2exp(num, num, lexp);
1574         }
1575
1576 Now we are ready to parse a number: the base, mantissa, and exponent.
1577 If all goes well we check for the possible trailing letters and
1578 return.  Return value is 1 for success and 0 for failure.
1579
1580
1581 ###### number functions
1582         int number_parse(mpq_t num, char tail[3], struct text tok)
1583         {
1584                 ## number vars
1585                 int i;
1586
1587                 ## parse base
1588                 ## parse mantissa
1589                 if (tok.len > 1 && (tok.txt[0] == expc ||
1590                                     tok.txt[0] == toupper(expc))) {
1591                         tok.txt++;
1592                         tok.len--;
1593                         ## parse exponent
1594                 }
1595                 ## calc exponent
1596
1597                 for (i = 0; i < 2; i++) {
1598                         if (tok.len <= i)
1599                                 break;
1600                         if (!isalpha(tok.txt[i]))
1601                                 goto err;
1602                         tail[i] = tok.txt[i];
1603                 }
1604                 tail[i] = 0;
1605                 if (i == tok.len)
1606                         return 1;
1607         err:
1608                 mpq_clear(num);
1609                 return 0;
1610         }
1611
1612 Number parsing goes in `libnumber.c`
1613
1614 ###### File: libnumber.c
1615
1616         #include <unistd.h>
1617         #include <stdlib.h>
1618
1619         ## number includes
1620         ## number functions
1621
1622 ###### File: number.h
1623         int number_parse(mpq_t num, char tail[3], struct text tok);
1624
1625 ###### File: scanner.mk
1626         all :: libnumber.o
1627         libnumber.o : libnumber.c
1628                 $(CC) $(CFLAGS) -c libnumber.c
1629
1630 ## Processing strings
1631
1632 Both `TK_string` and `TK_multi_string` require post-processing which
1633 can be one of two types: literal or with escapes processed.
1634 Even literal processing is non-trivial as the file may contain indents
1635 which need to be stripped.
1636
1637 Errors can only occur when processing escapes.  Any unrecognised
1638 character following the escape character will cause an error.
1639
1640 Processing escapes and striping indents can only make the string
1641 shorter, not longer, so we allocate a buffer which is the same size as
1642 the string and process into that.
1643
1644 To request escape processing, we pass the character we want to use for
1645 quoting, usually '`\`'.  To avoid escape processing we pass a zero.
1646
1647 ###### string main
1648         int string_parse(struct token *tok, char escape,
1649                          struct text *str, char tail[3])
1650         {
1651                 ## string vars
1652                 struct text t = tok->txt;
1653
1654                 str->txt = NULL;
1655                 ## strip tail
1656                 if (tok->num == TK_string) {
1657                         ## strip single
1658                 } else {
1659                         ## strip multi
1660                 }
1661                 str->txt = malloc(t.len);
1662                 str->len = 0;
1663
1664                 ## process string
1665                 return 1;
1666         err:
1667                 free(str->txt);
1668                 str->txt = NULL;
1669                 return 0;
1670         }
1671
1672 ### strip tail
1673
1674 The tail of the string can be 0, 1, or 2 letters
1675
1676         i = t.len;
1677         if (i >= 0 && isalpha(t.txt[i-1]))
1678                 i -= 1;
1679         if (i >= 0 && isalpha(t.txt[i-1]))
1680                 i -= 1;
1681         strncpy(tail, t.txt+i, t.len-i);
1682         tail[t.len-i] = 0;
1683         t.len = i;
1684
1685 ###### string vars
1686         int i;
1687
1688 ### strip single
1689
1690 Stripping the quote of a single-line string is trivial.
1691 The only part that is at all interesting is that quote character must
1692 be remembered.
1693
1694         quote = t.txt[0];
1695         if (t.txt[t.len-1] != quote)
1696                 goto err;
1697         t.txt += 1;
1698         t.len -= 2;
1699
1700 ###### string vars
1701         char quote;
1702
1703 ### strip multi
1704
1705 For a multi-line string we have a little more work to do.  We need to
1706 remove 3 quotes, not 1, and need to count the indent of the close
1707 quote as it will need to be stripped from all lines.
1708
1709         quote = t.txt[0];
1710         if (t.len < 7 ||
1711             t.txt[1] != quote || t.txt[2] != quote ||
1712             !is_newline(t.txt[3]))
1713                 goto err;
1714         t.txt += 4;
1715         t.len -= 4;
1716         i = t.len;
1717         if (i <= 0 || t.txt[i-1] != quote)
1718                 goto err;
1719         i -= 1;
1720         if (i <= 0 || t.txt[i-1] != quote)
1721                 goto err;
1722         i -= 1;
1723         if (i <= 0 || t.txt[i-1] != quote)
1724                 goto err;
1725         i -= 1;
1726         t.len = i;
1727         while (i > 0 && !is_newline(t.txt[i-1]))
1728                 i--;
1729         indent = 0;
1730         while (i < t.len) {
1731                 if (t.txt[i] == ' ')
1732                         indent += 1;
1733                 if (t.txt[i] == '\t')
1734                         indent = indent_tab(indent);
1735                 i++;
1736         }
1737
1738 ###### string vars
1739         int indent = 0;
1740
1741 ### process string
1742
1743 Now we just take one byte at a time. trans-ASCII unicode won't look
1744 like anything we are interested in so it will just be copied byte by
1745 byte.
1746
1747         cp = str->txt;
1748         at_sol = 1;
1749         for (i = 0; i < t.len; i++) {
1750                 char c;
1751                 if (at_sol) {
1752                         at_sol = 0;
1753                         ## strip indent
1754                         if (i >= t.len)
1755                                 break;
1756                 }
1757                 c = t.txt[i];
1758                 if (c != escape) {
1759                         *cp = c;
1760                         cp += 1;
1761                         if (is_newline(c))
1762                                 at_sol = 1;
1763                 } else if (i+1 >= t.len) {
1764                         // escape and end of string
1765                         goto err;
1766                 } else {
1767                         i += 1;
1768                         c = t.txt[i];
1769                         ## parse escape
1770                 }
1771         }
1772         str->len = cp - str->txt;
1773
1774 ###### string vars
1775         char *cp;
1776         int at_sol;
1777
1778 ### strip indent
1779
1780 Every time we find a start of line, we strip spaces and tabs until the
1781 required indent is found.
1782
1783         int skipped = 0;
1784         while (i < t.len && skipped < indent) {
1785                 c = t.txt[i];
1786                 if (c == ' ')
1787                         skipped += 1;
1788                 else if (c == '\t')
1789                         skipped = indent_tab(skipped);
1790                 else
1791                         break;
1792                 i+= 1;
1793         }
1794
1795 ### parse escape
1796         switch (c) {
1797         case 'n':
1798                 *cp++ = '\n'; break;
1799         case 'r':
1800                 *cp++ = '\r'; break;
1801         case 't':
1802                 *cp++ = '\t'; break;
1803         case 'b':
1804                 *cp++ = '\b'; break;
1805         case 'q':
1806                 *cp++ = quote; break;
1807         case 'f':
1808                 *cp++ = '\f'; break;
1809         case 'v':
1810                 *cp++ = '\v'; break;
1811         case 'a':
1812                 *cp++ = '\a'; break;
1813         case '0':
1814         case '1':
1815         case '2':
1816         case '3':
1817                 // 3 digit octal number
1818                 if (i+2 >= t.len)
1819                         goto err;
1820                 if (t.txt[i+1] < '0' || t.txt[i+1] > '7' ||
1821                     t.txt[i+2] < '0' || t.txt[i+1] > '7')
1822                         goto err;
1823                 n = (t.txt[i  ]-'0') * 64 +
1824                     (t.txt[i+1]-'0') *  8 +
1825                     (t.txt[i+2]-'0') *  1;
1826                 *cp++ = n;
1827                 i += 2;
1828                 break;
1829         case 'x':
1830                 // 2 hex digits
1831                 n = take_hex(2, t.txt+i+1, t.len-i-1);
1832                 if (n < 0)
1833                         goto err;
1834                 *cp++ = n;
1835                 i += 2;
1836                 break;
1837         case 'u':
1838         case 'U':
1839                 // 4 or 8 hex digits for unicode
1840                 n = take_hex(c == 'u'?4:8, t.txt+i+1, t.len-i-1);
1841                 if (n < 0)
1842                         goto err;
1843                 memset(&pstate, 0, sizeof(pstate));
1844                 n = wcrtomb(cp, n, &pstate);
1845                 if (n <= 0)
1846                         goto err;
1847                 cp += n;
1848                 i += c == 'u' ? 4 : 8;
1849                 break;
1850         default:
1851                 if (c == escape)
1852                         *cp++ = c;
1853                 else if (is_newline(c))
1854                         at_sol = 1;
1855                 else
1856                         goto err;
1857         }
1858
1859 ###### string vars
1860         long n;
1861         mbstate_t pstate;
1862
1863 For `\x` `\u` and `\U` we need to collect a specific number of
1864 hexadecimal digits
1865
1866 ###### string functions
1867
1868         static long take_hex(int digits, char *cp, int l)
1869         {
1870                 long n = 0;
1871                 if (l < digits)
1872                         return -1;
1873                 while (digits) {
1874                         char  c = *cp;
1875                         int d;
1876                         if (!isxdigit(c))
1877                                 return -1;
1878                         if (isdigit(c))
1879                                 d = c - '0';
1880                         else if (isupper(c))
1881                                 d = 10 + c - 'A';
1882                         else
1883                                 d = 10 + c - 'a';
1884                         n = n * 16 + d;
1885                         digits--;
1886                         cp++;
1887                 }
1888                 return n;
1889         }
1890
1891 #### File: libstring.c
1892
1893 String parsing goes in `libstring.c`
1894
1895         #include <unistd.h>
1896         #include <stdlib.h>
1897         #include <stdio.h>
1898         #include <string.h>
1899         #include <ctype.h>
1900         #include <wchar.h>
1901         #include "mdcode.h"
1902         #include "scanner.h"
1903         ## string functions
1904         ## string main
1905
1906 ###### File: string.h
1907         int string_parse(struct token *tok, char escape,
1908                          struct text *str, char tail[3]);
1909
1910 ###### File: scanner.mk
1911         all :: libstring.o
1912         libstring.o : libstring.c
1913                 $(CC) $(CFLAGS) -c libstring.c
1914
1915
1916 ## Testing
1917
1918 As "untested code is buggy code" we need a program to easily test
1919 the scanner library.  This will simply parse a given file and report
1920 the tokens one per line.
1921
1922 ###### File: scanner.c
1923
1924         #include <unistd.h>
1925         #include <stdlib.h>
1926         #include <fcntl.h>
1927         #include <errno.h>
1928         #include <sys/mman.h>
1929         #include <string.h>
1930         #include <stdio.h>
1931         #include <gmp.h>
1932         #include <locale.h>
1933         #include "mdcode.h"
1934         #include "scanner.h"
1935         #include "number.h"
1936         #include "string.h"
1937
1938         static int errs;
1939         static void pr_err(char *msg)
1940         {
1941                 errs++;
1942                 fprintf(stderr, "%s\n", msg);
1943         }
1944
1945         int main(int argc, char *argv[])
1946         {
1947                 int fd;
1948                 int len;
1949                 char *file;
1950                 struct token_state *state;
1951                 const char *known[] = {
1952                         "==",
1953                         "else",
1954                         "if",
1955                         "then",
1956                         "while",
1957                         "{",
1958                         "}",
1959                 };
1960                 struct token_config conf = {
1961                         .word_start = "_$",
1962                         .word_cont = "",
1963                         .words_marks = known,
1964                         .number_chars = "., _+-",
1965                         .known_count = sizeof(known)/sizeof(known[0]),
1966                         .ignored = (0 << TK_line_comment)
1967                                   |(0 << TK_block_comment),
1968                 };
1969                 struct section *table, *s, *prev;
1970                 setlocale(LC_ALL,"");
1971                 if (argc != 2) {
1972                         fprintf(stderr, "Usage: scanner file\n");
1973                         exit(2);
1974                 }
1975                 fd = open(argv[1], O_RDONLY);
1976                 if (fd < 0) {
1977                         fprintf(stderr, "scanner: cannot open %s: %s\n",
1978                                 argv[1], strerror(errno));
1979                         exit(1);
1980                 }
1981                 len = lseek(fd, 0, 2);
1982                 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
1983                 table = code_extract(file, file+len, pr_err);
1984
1985                 for (s = table; s;
1986                         (code_free(s->code), prev = s, s = s->next, free(prev))) {
1987                         printf("Tokenizing: %.*s\n", s->section.len,
1988                                 s->section.txt);
1989                         state = token_open(s->code, &conf);
1990                         while(1) {
1991                                 struct token tk = token_next(state);
1992                                 printf("%d:%d ", tk.line, tk.col);
1993                                 token_trace(stdout, tk, 20);
1994                                 if (tk.num == TK_number) {
1995                                         mpq_t num;
1996                                         char tail[3];
1997                                         if (number_parse(num, tail,tk.txt)) {
1998                                                 printf(" %s ", tail);
1999                                                 mpq_out_str(stdout, 10, num);
2000                                                 mpq_clear(num);
2001                                         } else
2002                                                 printf(" BAD NUMBER");
2003                                 }
2004                                 if (tk.num == TK_string ||
2005                                     tk.num == TK_multi_string) {
2006                                         char esc = '\\';
2007                                         struct text str;
2008                                         char tail[3];
2009                                         if (tk.txt.txt[0] == '`')
2010                                                 esc = 0;
2011                                         if (string_parse(&tk, esc,
2012                                                          &str, tail)) {
2013                                                 printf(" %s ", tail);
2014                                                 text_dump(stdout, str, 20);
2015                                                 free(str.txt);
2016                                         } else
2017                                                 printf(" BAD STRING");
2018                                 }
2019                                 printf("\n");
2020                                 if (tk.num == TK_error)
2021                                         errs = 1;
2022                                 if (tk.num == TK_eof)
2023                                         break;
2024                         }
2025                 }
2026                 exit(!!errs);
2027         }
2028 ###### File: scanner.mk
2029         scanner.c : scanner.mdc
2030                 ./md2c scanner.mdc
2031         all :: scanner
2032         scanner : scanner.o scanner.h libscanner.o libmdcode.o mdcode.h
2033                 $(CC) $(CFLAGS) -o scanner scanner.o libscanner.o \
2034                         libmdcode.o libnumber.o libstring.o -licuuc -lgmp
2035         scanner.o : scanner.c
2036                 $(CC) $(CFLAGS) -c scanner.c