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