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                 if (state->node != tk->node)
1072                         tk->txt.len = tk->node->code.len - (tk->txt.txt - tk->node->code.txt);
1073                 else
1074                         tk->txt.len = (state->node->code.txt + state->offset)
1075                                       - tk->txt.txt;
1076         }
1077
1078         static void reset_token(struct token_state *state, struct token *tok)
1079         {
1080                 state->prev_line = tok->line;
1081                 state->prev_col = tok->col;
1082                 state->prev_offset = tok->txt.txt - state->node->code.txt;
1083                 unget_char(state);
1084                 tok->txt.len = 0;
1085         }
1086
1087
1088 Tokens make not cross into the next `code_node`, and some tokens can
1089 include the newline at the and of a `code_node`, we must be able to
1090 easily check if we have reached the end.  Equally we need to know if
1091 we are at the start of a node, as white space is treated a little
1092 differently there.
1093
1094 ###### internal functions
1095
1096         static int at_son(struct token_state *state)
1097         {
1098                 return state->offset == 0;
1099         }
1100
1101         static int at_eon(struct token_state *state)
1102         {
1103                 // at end-of-node ??
1104                 return state->node == NULL ||
1105                        state->offset >= state->node->code.len;
1106         }
1107
1108 ### Find a known word
1109
1110 As the known-word list is sorted we can use a simple binary search.
1111 Following the pattern established in "mdcode", we will use a `struct
1112 text` with start and length to represent the code fragment we are
1113 searching for.
1114
1115 ###### internal functions
1116         static int find_known(struct token_config *conf, struct text txt)
1117         {
1118                 int lo = 0;
1119                 int hi = conf->known_count;
1120
1121                 while (lo + 1 < hi) {
1122                         int mid = (lo + hi) / 2;
1123                         int cmp = strncmp(conf->words_marks[mid],
1124                                           txt.txt, txt.len);
1125                         if (cmp == 0 && conf->words_marks[mid][txt.len])
1126                                 cmp = 1;
1127                         if (cmp <= 0)
1128                                 lo = mid;
1129                         else
1130                                 hi = mid;
1131                 }
1132                 if (strncmp(conf->words_marks[lo],
1133                            txt.txt, txt.len) == 0
1134                     && conf->words_marks[lo][txt.len] == 0)
1135                         return lo;
1136                 else
1137                         return -1;
1138         }
1139
1140 ### Bringing it all together
1141
1142 Now we have all the bits there is just one section missing:  combining
1143 all the token parsing code into one block.
1144
1145 The handling of delayed tokens (Newlines, INs, OUTs) must come
1146 first before we try getting another character.
1147
1148 Then we parse all the test, making sure that we check for known marks
1149 before strings and comments, but unknown marks after strings and comments.
1150
1151 This block of code will either return a token, or will choose to
1152 ignore one, in which case it will `continue` around to the top of the
1153 loop.
1154
1155 ###### one token
1156         ## delayed tokens
1157
1158         ch = get_char(state);
1159
1160         ## white space
1161         ## parse number
1162         ## parse word
1163         ## parse mark
1164
1165 ### Start and stop
1166
1167 As well as getting tokens, we need to be able to create the
1168 `token_state` to start with, and discard it later.
1169
1170 ###### includes
1171         #include <malloc.h>
1172
1173 ###### main functions
1174         struct token_state *token_open(struct code_node *code, struct
1175                                        token_config *conf)
1176         {
1177                 struct token_state *state = malloc(sizeof(*state));
1178                 memset(state, 0, sizeof(*state));
1179                 state->node = code;
1180                 state->line = code->line_no;
1181                 state->col = do_strip(state);
1182                 state->conf = conf;
1183                 return state;
1184         }
1185         void token_close(struct token_state *state)
1186         {
1187                 free(state);
1188         }
1189
1190 ###### exported functions
1191         struct token_state *token_open(struct code_node *code, struct
1192                                        token_config *conf);
1193         void token_close(struct token_state *state);
1194
1195 ### Trace tokens
1196
1197 Getting tokens is the main thing but it is also useful to be able to
1198 print out token information, particularly for tracing and testing.
1199
1200 Known tokens are printed verbatim.  Other tokens are printed as
1201 `type(content)` where content is truncated to a given number of characters.
1202
1203 The function for printing a truncated string (`text_dump`) is also exported
1204 so that it can be used to tracing processed strings too.
1205
1206 ###### includes
1207         #include <stdio.h>
1208
1209 ###### exported functions
1210         void token_trace(FILE *f, struct token tok, int max);
1211         void text_dump(FILE *f, struct text t, int max);
1212
1213 ###### main functions
1214
1215         void text_dump(FILE *f, struct text txt, int max)
1216         {
1217                 int i;
1218                 if (txt.len > max)
1219                         max -= 2;
1220                 else
1221                         max = txt.len;
1222                 for (i = 0; i < max; i++) {
1223                         char c = txt.txt[i];
1224                         if (c < ' ' || c > '~')
1225                                 fprintf(f, "\\x%02x", c & 0xff);
1226                         else if (c == '\\')
1227                                 fprintf(f, "\\\\");
1228                         else
1229                                 fprintf(f, "%c", c);
1230                 }
1231                 if (i < txt.len)
1232                         fprintf(f, "..");
1233         }
1234
1235         void token_trace(FILE *f, struct token tok, int max)
1236         {
1237                 static char *types[] = {
1238                         [TK_ident] = "ident",
1239                         [TK_mark] = "mark",
1240                         [TK_number] = "number",
1241                         [TK_string] = "string",
1242                         [TK_multi_string] = "mstring",
1243                         [TK_line_comment] = "lcomment",
1244                         [TK_block_comment] = "bcomment",
1245                         [TK_in] = "in",
1246                         [TK_out] = "out",
1247                         [TK_newline] = "newline",
1248                         [TK_eof] = "eof",
1249                         [TK_error] = "ERROR",
1250                         };
1251
1252                 switch (tok.num) {
1253                 default: /* known word or mark */
1254                         fprintf(f, "%.*s", tok.txt.len, tok.txt.txt);
1255                         break;
1256                 case TK_in:
1257                 case TK_out:
1258                 case TK_newline:
1259                 case TK_eof:
1260                         /* No token text included */
1261                         fprintf(f, "%s()", types[tok.num]);
1262                         break;
1263                 case TK_ident:
1264                 case TK_mark:
1265                 case TK_number:
1266                 case TK_string:
1267                 case TK_multi_string:
1268                 case TK_line_comment:
1269                 case TK_block_comment:
1270                 case TK_error:
1271                         fprintf(f, "%s(", types[tok.num]);
1272                         text_dump(f, tok.txt, max);
1273                         fprintf(f, ")");
1274                         break;
1275                 }
1276         }
1277
1278 ### And there we have it
1279
1280 We now have all the library functions defined for reading and printing
1281 tokens.  Now we just need C files to store them, and a mk file to make them.
1282
1283 ###### File: scanner.h
1284         ## public types
1285         ## exported functions
1286
1287 ###### File: libscanner.c
1288         ## includes
1289         #include "scanner.h"
1290         ## private types
1291         ## internal functions
1292         ## main functions
1293
1294 ###### File: scanner.mk
1295
1296         CFLAGS += -Wall -g
1297         all ::
1298         scanner.mk scanner.h libscanner.c : scanner.mdc
1299                 ./md2c scanner.mdc
1300         all :: libscanner.o
1301         libscanner.o : libscanner.c
1302                 $(CC) $(CFLAGS) -c libscanner.c
1303
1304 ## Processing numbers
1305
1306 Converting a `TK_number` token to a numerical value is a slightly
1307 higher level task than lexical analysis, and slightly lower than
1308 grammar parsing, so put it here - as an index if you like.
1309
1310 Importantly it will be used by the same testing rig that is used for
1311 testing the token scanner.
1312
1313 The numeric value that we will convert all numbers into is the `mpq_t`
1314 from the GNU high precision number library "libgmp".
1315
1316 ###### number includes
1317         #include <gmp.h>
1318         #include "mdcode.h"
1319
1320 Firstly we need to be able to parse a string of digits in a given base
1321 and possibly with a decimal marker.  We store this in an `mpz_t`
1322 integer and report the number of digits after the decimal mark.
1323
1324 On error we return zero and ensure that the 'mpz_t' has been freed, or
1325 had never been initialised.
1326
1327 ###### number functions
1328
1329         static int parse_digits(mpz_t num, struct text tok, int base,
1330                                 int *placesp)
1331         {
1332                 /* Accept digits up to 'base', ignore '_' and
1333                  * ' ' if they appear between two legal digits,
1334                  * and if `placesp` is not NULL, allow a single
1335                  * '.' or ',' and report the number of digits
1336                  * beyond there.
1337                  * Return number of characters processed (p),
1338                  * or 0 if something illegal was found.
1339                  */
1340                 int p;
1341                 int decimal = -1; // digits after marker
1342                 enum {Digit, Space, Other} prev = Other;
1343                 int digits = 0;
1344
1345                 for (p = 0; p < tok.len; p++) {
1346                         int dig;
1347                         char c = tok.txt[p];
1348
1349                         if (c == '_' || c == ' ') {
1350                                 if (prev != Digit)
1351                                         goto bad;
1352                                 prev = Space;
1353                                 continue;
1354                         }
1355                         if (c == '.' || c == ',') {
1356                                 if (prev != Digit)
1357                                         goto bad;
1358                                 if (!placesp || decimal >= 0)
1359                                         return p-1;
1360                                 decimal = 0;
1361                                 prev = Other;
1362                                 continue;
1363                         }
1364                         if (isdigit(c))
1365                                 dig = c - '0';
1366                         else if (isupper(c))
1367                                 dig = 10 + c - 'A';
1368                         else if (islower(c))
1369                                 dig = 10 + c - 'a';
1370                         else
1371                                 dig = base;
1372                         if (dig >= base) {
1373                                 if (prev == Space)
1374                                         p--;
1375                                 break;
1376                         }
1377                         prev = Digit;
1378                         if (digits)
1379                                 mpz_mul_ui(num, num, base);
1380                         else
1381                                 mpz_init(num);
1382                         digits += 1;
1383                         mpz_add_ui(num, num, dig);
1384                         if (decimal >= 0)
1385                                 decimal++;
1386                 }
1387                 if (digits == 0)
1388                         return 0;
1389                 if (placesp) {
1390                         if (decimal >= 0)
1391                                 *placesp = decimal;
1392                         else
1393                                 *placesp = 0;
1394                 }
1395                 return p;
1396         bad:
1397                 if (digits)
1398                         mpz_clear(num);
1399                 return 0;
1400         }
1401
1402 ###### number includes
1403         #include <ctype.h>
1404
1405 To parse a full number we need to consider the optional base, the
1406 mantissa, and the optional exponent.  We will treat these one at a
1407 time.
1408
1409 The base is indicated by a letter after a leading zero, which must be
1410 followed by a base letter or a period.  The base also determines the
1411 character which will mark an exponent.
1412
1413 ###### number vars
1414         int base = 10;
1415         char expc = 'e';
1416
1417 ###### parse base
1418
1419         if (tok.txt[0] == '0' && tok.len > 1) {
1420                 int skip = 0;
1421                 switch(tok.txt[1]) {
1422                 case 'x':
1423                 case 'X':
1424                         base = 16;
1425                         skip = 2;
1426                         expc = 'p';
1427                         break;
1428                 case 'o':
1429                 case 'O':
1430                         base = 8;
1431                         skip = 2;
1432                         expc = 'p';
1433                         break;
1434                 case 'b':
1435                 case 'B':
1436                         base = 2;
1437                         skip = 2;
1438                         expc = 'p';
1439                         break;
1440                 case '0':
1441                 case '1':
1442                 case '2':
1443                 case '3':
1444                 case '4':
1445                 case '5':
1446                 case '6':
1447                 case '7':
1448                 case '8':
1449                 case '9':
1450                 case '_':
1451                 case ' ':
1452                         // another digit is not permitted
1453                         // after a zero.
1454                         return 0;
1455                 default:
1456                         // must be decimal marker or trailing
1457                         // letter, which are OK;
1458                         break;
1459                 }
1460                 tok.txt += skip;
1461                 tok.len -= skip;
1462         }
1463
1464 After the base is the mantissa, which may contain a decimal mark, so
1465 we need to record the number of places.  We won't impose the number of
1466 places until we have the exponent as well.
1467
1468 ###### number vars
1469         int places =0;
1470         mpz_t mant;
1471         int d;
1472
1473 ###### parse mantissa
1474
1475         d = parse_digits(mant, tok, base, &places);
1476         if (d == 0)
1477                 return 0;
1478         tok.txt += d;
1479         tok.len -= d;
1480         mpq_init(num);
1481         mpq_set_z(num, mant);
1482         mpz_clear(mant);
1483
1484 After the mantissa number may come an exponent which may be positive
1485 or negative.  We assume at this point that we have seen the exponent
1486 character `expc`.
1487
1488 ###### number vars
1489         long lexp = 0;
1490         mpz_t exp;
1491         int esign = 1;
1492
1493 ###### parse exponent
1494         if (tok.len > 1) {
1495                 if (tok.txt[0] == '+') {
1496                         tok.txt++;
1497                         tok.len--;
1498                 } else if (tok.txt[0] == '-') {
1499                         esign = -1;
1500                         tok.txt++;
1501                         tok.len--;
1502                 }
1503         }
1504         d = parse_digits(exp, tok, 10, NULL);
1505         if (d == 0) {
1506                 mpq_clear(num);
1507                 return 0;
1508         }
1509         if (!mpz_fits_slong_p(exp)) {
1510                 mpq_clear(num);
1511                 mpz_clear(exp);
1512                 return 0;
1513         }
1514         lexp = mpz_get_si(exp) * esign;
1515         mpz_clear(exp);
1516         tok.txt += d;
1517         tok.len -= d;
1518
1519
1520 Now that we have the mantissa and the exponent we can multiply them
1521 together, also allowing for the number of digits after the decimal
1522 mark.
1523
1524 For base 10, we simply subtract the decimal places from the exponent.
1525 For the other bases, as the exponent is alway based on 2, even for
1526 octal and hex, we need a bit more detail.
1527 We then recover the sign from the exponent, as division is quite
1528 different from multiplication.
1529
1530 ###### calc exponent
1531         switch (base) {
1532         case 10:
1533         case 2:
1534                 lexp -= places;
1535                 break;
1536         case 16:
1537                 lexp -= 4*places;
1538                 break;
1539         case 8:
1540                 lexp -= 3*places;
1541                 break;
1542         }
1543         if (lexp < 0) {
1544                 lexp = -lexp;
1545                 esign = -1;
1546         } else
1547                 esign = 1;
1548
1549 Imposing the exponent on the number is also very different for base 10
1550 than for the others.  For the binary shift `gmp` provides a simple
1551 function.  For base 10 we use something like Russian Peasant
1552 Multiplication.
1553
1554 ###### calc exponent
1555         if (expc == 'e') {
1556                 mpq_t tens;
1557                 mpq_init(tens);
1558                 mpq_set_ui(tens, 10, 1);
1559                 while (1) {
1560                         if (lexp & 1) {
1561                                 if (esign > 0)
1562                                         mpq_mul(num, num, tens);
1563                                 else
1564                                         mpq_div(num, num, tens);
1565                         }
1566                         lexp >>= 1;
1567                         if (lexp == 0)
1568                                 break;
1569                         mpq_mul(tens, tens, tens);
1570                 }
1571                 mpq_clear(tens);
1572         } else {
1573                 if (esign > 0)
1574                         mpq_mul_2exp(num, num, lexp);
1575                 else
1576                         mpq_div_2exp(num, num, lexp);
1577         }
1578
1579 Now we are ready to parse a number: the base, mantissa, and exponent.
1580 If all goes well we check for the possible trailing letters and
1581 return.  Return value is 1 for success and 0 for failure.
1582
1583
1584 ###### number functions
1585         int number_parse(mpq_t num, char tail[3], struct text tok)
1586         {
1587                 ## number vars
1588                 int i;
1589
1590                 ## parse base
1591                 ## parse mantissa
1592                 if (tok.len > 1 && (tok.txt[0] == expc ||
1593                                     tok.txt[0] == toupper(expc))) {
1594                         tok.txt++;
1595                         tok.len--;
1596                         ## parse exponent
1597                 }
1598                 ## calc exponent
1599
1600                 for (i = 0; i < 2; i++) {
1601                         if (tok.len <= i)
1602                                 break;
1603                         if (!isalpha(tok.txt[i]))
1604                                 goto err;
1605                         tail[i] = tok.txt[i];
1606                 }
1607                 tail[i] = 0;
1608                 if (i == tok.len)
1609                         return 1;
1610         err:
1611                 mpq_clear(num);
1612                 return 0;
1613         }
1614
1615 Number parsing goes in `libnumber.c`
1616
1617 ###### File: libnumber.c
1618
1619         #include <unistd.h>
1620         #include <stdlib.h>
1621
1622         ## number includes
1623         ## number functions
1624
1625 ###### File: number.h
1626         int number_parse(mpq_t num, char tail[3], struct text tok);
1627
1628 ###### File: scanner.mk
1629         all :: libnumber.o
1630         libnumber.o : libnumber.c
1631                 $(CC) $(CFLAGS) -c libnumber.c
1632
1633 ## Processing strings
1634
1635 Both `TK_string` and `TK_multi_string` require post-processing which
1636 can be one of two types: literal or with escapes processed.
1637 Even literal processing is non-trivial as the file may contain indents
1638 which need to be stripped.
1639
1640 Errors can only occur when processing escapes.  Any unrecognised
1641 character following the escape character will cause an error.
1642
1643 Processing escapes and striping indents can only make the string
1644 shorter, not longer, so we allocate a buffer which is the same size as
1645 the string and process into that.
1646
1647 To request escape processing, we pass the character we want to use for
1648 quoting, usually '`\`'.  To avoid escape processing we pass a zero.
1649
1650 ###### string main
1651         int string_parse(struct token *tok, char escape,
1652                          struct text *str, char tail[3])
1653         {
1654                 ## string vars
1655                 struct text t = tok->txt;
1656
1657                 str->txt = NULL;
1658                 ## strip tail
1659                 if (tok->num == TK_string) {
1660                         ## strip single
1661                 } else {
1662                         ## strip multi
1663                 }
1664                 str->txt = malloc(t.len);
1665                 str->len = 0;
1666
1667                 ## process string
1668                 return 1;
1669         err:
1670                 free(str->txt);
1671                 str->txt = NULL;
1672                 return 0;
1673         }
1674
1675 ### strip tail
1676
1677 The tail of the string can be 0, 1, or 2 letters
1678
1679         i = t.len;
1680         if (i >= 0 && isalpha(t.txt[i-1]))
1681                 i -= 1;
1682         if (i >= 0 && isalpha(t.txt[i-1]))
1683                 i -= 1;
1684         strncpy(tail, t.txt+i, t.len-i);
1685         tail[t.len-i] = 0;
1686         t.len = i;
1687
1688 ###### string vars
1689         int i;
1690
1691 ### strip single
1692
1693 Stripping the quote of a single-line string is trivial.
1694 The only part that is at all interesting is that quote character must
1695 be remembered.
1696
1697         quote = t.txt[0];
1698         if (t.txt[t.len-1] != quote)
1699                 goto err;
1700         t.txt += 1;
1701         t.len -= 2;
1702
1703 ###### string vars
1704         char quote;
1705
1706 ### strip multi
1707
1708 For a multi-line string we have a little more work to do.  We need to
1709 remove 3 quotes, not 1, and need to count the indent of the close
1710 quote as it will need to be stripped from all lines.
1711
1712         quote = t.txt[0];
1713         if (t.len < 7 ||
1714             t.txt[1] != quote || t.txt[2] != quote ||
1715             !is_newline(t.txt[3]))
1716                 goto err;
1717         t.txt += 4;
1718         t.len -= 4;
1719         i = t.len;
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         if (i <= 0 || t.txt[i-1] != quote)
1727                 goto err;
1728         i -= 1;
1729         t.len = i;
1730         while (i > 0 && !is_newline(t.txt[i-1]))
1731                 i--;
1732         indent = 0;
1733         while (i < t.len) {
1734                 if (t.txt[i] == ' ')
1735                         indent += 1;
1736                 if (t.txt[i] == '\t')
1737                         indent = indent_tab(indent);
1738                 i++;
1739         }
1740
1741 ###### string vars
1742         int indent = 0;
1743
1744 ### process string
1745
1746 Now we just take one byte at a time. trans-ASCII unicode won't look
1747 like anything we are interested in so it will just be copied byte by
1748 byte.
1749
1750         cp = str->txt;
1751         at_sol = 1;
1752         for (i = 0; i < t.len; i++) {
1753                 char c;
1754                 if (at_sol) {
1755                         at_sol = 0;
1756                         ## strip indent
1757                         if (i >= t.len)
1758                                 break;
1759                 }
1760                 c = t.txt[i];
1761                 if (c != escape) {
1762                         *cp = c;
1763                         cp += 1;
1764                         if (is_newline(c))
1765                                 at_sol = 1;
1766                 } else if (i+1 >= t.len) {
1767                         // escape and end of string
1768                         goto err;
1769                 } else {
1770                         i += 1;
1771                         c = t.txt[i];
1772                         ## parse escape
1773                 }
1774         }
1775         str->len = cp - str->txt;
1776
1777 ###### string vars
1778         char *cp;
1779         int at_sol;
1780
1781 ### strip indent
1782
1783 Every time we find a start of line, we strip spaces and tabs until the
1784 required indent is found.
1785
1786         int skipped = 0;
1787         while (i < t.len && skipped < indent) {
1788                 c = t.txt[i];
1789                 if (c == ' ')
1790                         skipped += 1;
1791                 else if (c == '\t')
1792                         skipped = indent_tab(skipped);
1793                 else
1794                         break;
1795                 i+= 1;
1796         }
1797
1798 ### parse escape
1799         switch (c) {
1800         case 'n':
1801                 *cp++ = '\n'; break;
1802         case 'r':
1803                 *cp++ = '\r'; break;
1804         case 't':
1805                 *cp++ = '\t'; break;
1806         case 'b':
1807                 *cp++ = '\b'; break;
1808         case 'q':
1809                 *cp++ = quote; break;
1810         case 'f':
1811                 *cp++ = '\f'; break;
1812         case 'v':
1813                 *cp++ = '\v'; break;
1814         case 'a':
1815                 *cp++ = '\a'; break;
1816         case '0':
1817         case '1':
1818         case '2':
1819         case '3':
1820                 // 3 digit octal number
1821                 if (i+2 >= t.len)
1822                         goto err;
1823                 if (t.txt[i+1] < '0' || t.txt[i+1] > '7' ||
1824                     t.txt[i+2] < '0' || t.txt[i+1] > '7')
1825                         goto err;
1826                 n = (t.txt[i  ]-'0') * 64 +
1827                     (t.txt[i+1]-'0') *  8 +
1828                     (t.txt[i+2]-'0') *  1;
1829                 *cp++ = n;
1830                 i += 2;
1831                 break;
1832         case 'x':
1833                 // 2 hex digits
1834                 n = take_hex(2, t.txt+i+1, t.len-i-1);
1835                 if (n < 0)
1836                         goto err;
1837                 *cp++ = n;
1838                 i += 2;
1839                 break;
1840         case 'u':
1841         case 'U':
1842                 // 4 or 8 hex digits for unicode
1843                 n = take_hex(c == 'u'?4:8, t.txt+i+1, t.len-i-1);
1844                 if (n < 0)
1845                         goto err;
1846                 memset(&pstate, 0, sizeof(pstate));
1847                 n = wcrtomb(cp, n, &pstate);
1848                 if (n <= 0)
1849                         goto err;
1850                 cp += n;
1851                 i += c == 'u' ? 4 : 8;
1852                 break;
1853         default:
1854                 if (c == escape)
1855                         *cp++ = c;
1856                 else if (is_newline(c))
1857                         at_sol = 1;
1858                 else
1859                         goto err;
1860         }
1861
1862 ###### string vars
1863         long n;
1864         mbstate_t pstate;
1865
1866 For `\x` `\u` and `\U` we need to collect a specific number of
1867 hexadecimal digits
1868
1869 ###### string functions
1870
1871         static long take_hex(int digits, char *cp, int l)
1872         {
1873                 long n = 0;
1874                 if (l < digits)
1875                         return -1;
1876                 while (digits) {
1877                         char  c = *cp;
1878                         int d;
1879                         if (!isxdigit(c))
1880                                 return -1;
1881                         if (isdigit(c))
1882                                 d = c - '0';
1883                         else if (isupper(c))
1884                                 d = 10 + c - 'A';
1885                         else
1886                                 d = 10 + c - 'a';
1887                         n = n * 16 + d;
1888                         digits--;
1889                         cp++;
1890                 }
1891                 return n;
1892         }
1893
1894 #### File: libstring.c
1895
1896 String parsing goes in `libstring.c`
1897
1898         #include <unistd.h>
1899         #include <stdlib.h>
1900         #include <stdio.h>
1901         #include <string.h>
1902         #include <ctype.h>
1903         #include <wchar.h>
1904         #include "mdcode.h"
1905         #include "scanner.h"
1906         ## string functions
1907         ## string main
1908
1909 ###### File: string.h
1910         int string_parse(struct token *tok, char escape,
1911                          struct text *str, char tail[3]);
1912
1913 ###### File: scanner.mk
1914         all :: libstring.o
1915         libstring.o : libstring.c
1916                 $(CC) $(CFLAGS) -c libstring.c
1917
1918
1919 ## Testing
1920
1921 As "untested code is buggy code" we need a program to easily test
1922 the scanner library.  This will simply parse a given file and report
1923 the tokens one per line.
1924
1925 ###### File: scanner.c
1926
1927         #include <unistd.h>
1928         #include <stdlib.h>
1929         #include <fcntl.h>
1930         #include <errno.h>
1931         #include <sys/mman.h>
1932         #include <string.h>
1933         #include <stdio.h>
1934         #include <gmp.h>
1935         #include <locale.h>
1936         #include "mdcode.h"
1937         #include "scanner.h"
1938         #include "number.h"
1939         #include "string.h"
1940
1941         static int errs;
1942         static void pr_err(char *msg)
1943         {
1944                 errs++;
1945                 fprintf(stderr, "%s\n", msg);
1946         }
1947
1948         int main(int argc, char *argv[])
1949         {
1950                 int fd;
1951                 int len;
1952                 char *file;
1953                 struct token_state *state;
1954                 const char *known[] = {
1955                         "==",
1956                         "else",
1957                         "if",
1958                         "then",
1959                         "while",
1960                         "{",
1961                         "}",
1962                 };
1963                 struct token_config conf = {
1964                         .word_start = "_$",
1965                         .word_cont = "",
1966                         .words_marks = known,
1967                         .number_chars = "., _+-",
1968                         .known_count = sizeof(known)/sizeof(known[0]),
1969                         .ignored = (0 << TK_line_comment)
1970                                   |(0 << TK_block_comment),
1971                 };
1972                 struct section *table, *s, *prev;
1973                 setlocale(LC_ALL,"");
1974                 if (argc != 2) {
1975                         fprintf(stderr, "Usage: scanner file\n");
1976                         exit(2);
1977                 }
1978                 fd = open(argv[1], O_RDONLY);
1979                 if (fd < 0) {
1980                         fprintf(stderr, "scanner: cannot open %s: %s\n",
1981                                 argv[1], strerror(errno));
1982                         exit(1);
1983                 }
1984                 len = lseek(fd, 0, 2);
1985                 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
1986                 table = code_extract(file, file+len, pr_err);
1987
1988                 for (s = table; s;
1989                         (code_free(s->code), prev = s, s = s->next, free(prev))) {
1990                         printf("Tokenizing: %.*s\n", s->section.len,
1991                                 s->section.txt);
1992                         state = token_open(s->code, &conf);
1993                         while(1) {
1994                                 struct token tk = token_next(state);
1995                                 printf("%d:%d ", tk.line, tk.col);
1996                                 token_trace(stdout, tk, 20);
1997                                 if (tk.num == TK_number) {
1998                                         mpq_t num;
1999                                         char tail[3];
2000                                         if (number_parse(num, tail,tk.txt)) {
2001                                                 printf(" %s ", tail);
2002                                                 mpq_out_str(stdout, 10, num);
2003                                                 mpq_clear(num);
2004                                         } else
2005                                                 printf(" BAD NUMBER");
2006                                 }
2007                                 if (tk.num == TK_string ||
2008                                     tk.num == TK_multi_string) {
2009                                         char esc = '\\';
2010                                         struct text str;
2011                                         char tail[3];
2012                                         if (tk.txt.txt[0] == '`')
2013                                                 esc = 0;
2014                                         if (string_parse(&tk, esc,
2015                                                          &str, tail)) {
2016                                                 printf(" %s ", tail);
2017                                                 text_dump(stdout, str, 20);
2018                                                 free(str.txt);
2019                                         } else
2020                                                 printf(" BAD STRING");
2021                                 }
2022                                 printf("\n");
2023                                 if (tk.num == TK_error)
2024                                         errs = 1;
2025                                 if (tk.num == TK_eof)
2026                                         break;
2027                         }
2028                 }
2029                 exit(!!errs);
2030         }
2031 ###### File: scanner.mk
2032         scanner.c : scanner.mdc
2033                 ./md2c scanner.mdc
2034         all :: scanner
2035         scanner : scanner.o scanner.h libscanner.o libmdcode.o mdcode.h
2036                 $(CC) $(CFLAGS) -o scanner scanner.o libscanner.o \
2037                         libmdcode.o libnumber.o libstring.o -licuuc -lgmp
2038         scanner.o : scanner.c
2039                 $(CC) $(CFLAGS) -c scanner.c