sabre.git
4 years agoMerge pull request #8 from ilammy/expand-abbreviations master
ilammy [Sat, 21 Jan 2017 18:56:36 +0000 (20:56 +0200)]
Merge pull request #8 from ilammy/expand-abbreviations

This finishes implementation of the basic parser.

As noted in the issue text, I have decided to leave the labeled data
alone. This branch only adds expansion of abbreviations and a minor
tweak of the test code layout.

4 years agoExpand abbreviations during parsing expand-abbreviations
ilammy [Sat, 21 Jan 2017 17:29:09 +0000 (19:29 +0200)]
Expand abbreviations during parsing

My original plan was to have a separate entity do the expansion of
abbreviations and dereferencing datum labels. However, it turned out
that datum labels are hard. It makes me even wonder why the heck do we
need them; apparently, they were lobbied into the R7RS by some purist
people. Well, whatever. They seem to be okay for reading just data, but
they may cause issues, for example, during macroexpansion. We'll deal
with this stuff later.

But for now we need to do something about the abbreviations. So I
decided to go ahead and simply expand them during parsing. This commit
removes the abbreviations from ScannedDatum/DatumValue, makes the parser
to expand them directly into appropriate proper lists, and fixes up the
surrounding code. Note that we now need access to string interner in
order to be able to use these "quote" and "unquote-splicing" strings.

4 years agoMake test utilities a module again
ilammy [Mon, 2 Jan 2017 14:15:11 +0000 (16:15 +0200)]
Make test utilities a module again

This is actually needed to be able to use test utilities in unit-tests
written inside libreader, so move them back as a module.

The module *is* publicly exported from the library, but it is hidden in
documentation and it is expected to be used only by the integration
tests.

4 years agoMerge pull request #7 from ilammy/basic-parser
ilammy [Fri, 30 Dec 2016 00:04:33 +0000 (02:04 +0200)]
Merge pull request #7 from ilammy/basic-parser

Implement basic parser.

This branch contains implementation of the basic parser.

The parser can handle all <datum> productions specified by R7RS, but it
does not expand abbreviations, nor does it check the label usage. The
parser also skips all comments (including s-expr ones).

I have run it through the test coverage review: all branches seem to be
visited at least once by the test suite. In fact, the coverge review
helped to uncover a bug with s-expr comment parsing.

The history is a bit dirty for a new feature, but I'm too lazy to
reorder and rehash the commits. They are mostly separated so it's fine.

4 years agoHandle unmatched closing parentheses basic-parser
ilammy [Thu, 29 Dec 2016 23:34:48 +0000 (01:34 +0200)]
Handle unmatched closing parentheses

This is the last unimplemented!() in the parser code. Handle this case
exactly as extra dots. The diagnostic is non-fatal because we can
recover from this condition by simply ignoring the extra parentheses.

Besides, this case is very unlikely to occur in practice as Scheme
programs are heavily nested and are usually edited with proper editors
which can display matching parentheses. So the user has to try extra
hard to make this mistake.

4 years agoFix parsing of s-expr comments as atmosphere
ilammy [Thu, 29 Dec 2016 22:10:23 +0000 (00:10 +0200)]
Fix parsing of s-expr comments as atmosphere

S-expr comments yield Ok(None) results which do not indicate parser
recovery. This is correctly handled by s-expr comment code itself, but
the parsers of abbreviations and labels did it wrong and produced wrong
parses (see *_interspersed_sexpr_comments() tests, they were broken).

To fix the issue move the code from parse_sexpr_comment() into a common
method and use it everwhere where we *need* to get a proper datum.

The original behavior was intended to produce only one diagnostic when
multiple quotes are placed consecutively without any data following
them. Now each of the quotes produces its own diagnostic. Update the
tests accordingly. This should be rare in practice so it's fine.

Also refactor datum conversion in labels and abbreviations:

- avoid using explicit ifs, use maps instead
- avoid unnecessary temporary variable, reorder initializers instead
  to please the borrow checker

(Note: this bug has been found by inspecting the coverage report.)

4 years agoSupport for s-expression comments
ilammy [Sat, 24 Dec 2016 20:41:46 +0000 (22:41 +0200)]
Support for s-expression comments

This adds skipping of #;(s-expression comments). They are pretty
straightforward if you do not count the cases with recursion which are
somewhat non-obvious, but logical. Thankfully, it is explained quite
well in SRFI 62.

Unfortunately, these comments are not handled by lexer and the parser
does not indicate their spans, so IDEs may have hard time guessing where
exactly the comments are. Though, I suppose they can use the following
hack: treat everything skipped by the parser as comments. Whitespace
will be whitespace, comments will be styled as comments, and
directives... well, even R7RS tells us to read them as comments
so who cares :)

4 years agoSupport for labels
ilammy [Sat, 24 Dec 2016 17:38:05 +0000 (19:38 +0200)]
Support for labels

This implements parsing of labels. Label references are similar to
simple data. Label marks are similar to abbreviations.

Note that the parser does not resolve nor check circular references.
This will done at some later stage. Currently we only accurately
represent the labeled locations and references to them.

As for the changes, one diagnostic was renamed to be more inclusive.
I think it will be used for datum comments as well because the error
is similar to what we have in abbreviations and labels.

One final thing that I would like to note is that only now is the
moment when I realised that the grammar maybe allows labels to have
spaces between their parts: "# 0 = ( 1 . # 0 # )" ought to be a
valid form of a circular list.

Consider the following:

    7.1.2. External representations

    <datum> --> <simple datum> | <compound datum>
             |  <label> = <datum>
     |  <label> #

    <label> --> # <uinteger 10>

    7.1.1. Lexical structure

    Intertoken space can occur on either side of any token,
    but not within a token.

If "#" and "=" are considered 'tokens' then the above string should be
valid. However, if only <token> is considered a token that can be
followed by intertoken space then it's fine.

Racket and SBCL do not allow this interspaced form, so I guess it's fine
to leave it as it is now (not allowing spaces). But to be honest I would
have left it alone anyway. Treating the lone hash and an identifier =
specially in some cases will be too bothersome.

4 years agoSupport for abbreviations
ilammy [Sat, 17 Dec 2016 20:56:43 +0000 (22:56 +0200)]
Support for abbreviations

This adds support for all four kinds of abbreviations. There is only
one real error here: missing data to be quoted. This happens when a
quote is followed by an EOF, closing paren, or a dot. Everything else
can start a valid datum.

4 years agoRefactor parsing for better error handling
ilammy [Sun, 18 Dec 2016 15:26:45 +0000 (17:26 +0200)]
Refactor parsing for better error handling

- Introduce finer error distinction by replacing Option<ScannedDatum>
  with Result<Option<ScannedDatum>, ()>. Now fatal errors are
  represented with an Err. None is used for recovered errors. There is
  only one fatal error now (unexpected EOF), so we use the unit type,
  but it can be easily changed.

- Now next_datum() bumps away all tokens that build up the datum it has
  parsed. Previously it was leaving the last token in self.cur. This
  caused recursive data parsing to be weird.

- Added more guardian asserts when bumping expected tokens.

- Now we generate only one fatal diagnostic for an unexpected EOF when
  scanning nested parenthised expressions. Parentheses are quite common
  in Lisp and there is no way to recover from a fatal error, so it does
  not make much sense to produce more than one error in this case.

4 years agoAllow adjacent dots in dotted lists
ilammy [Sat, 24 Dec 2016 11:19:25 +0000 (13:19 +0200)]
Allow adjacent dots in dotted lists

Fix a bug in dotted list verifications which treated lists like (1 .'2)
as proper ones. Now they are correctly recognized as dotted lists.

4 years agoSupport for dotted lists
ilammy [Sat, 17 Dec 2016 16:57:25 +0000 (18:57 +0200)]
Support for dotted lists

This adds support for dotted lists. We handle incorrect forms of dotted
lists by simply reporting all dots and falling back to treating the list
as a proper one.

Note that DatumValue::DottedList still contains just a Vec. It is
guaranteed that that vector contains at least two elements and the last
one is the cdr of the dotted list.

Also we remove some code duplication in datum test builders, and teach
them to accept IntoIterators rather than Vecs. This allows that fancy
implementation of line_sequence :)

4 years agoSupport for proper lists
ilammy [Thu, 15 Dec 2016 21:24:06 +0000 (23:24 +0200)]
Support for proper lists

This adds support for _proper_ lists. I.e., not the dotted ones. These
will come in the next commit.

4 years agoSupport for vectors
ilammy [Thu, 15 Dec 2016 20:55:29 +0000 (22:55 +0200)]
Support for vectors

This adds support for vector data. Nothing fancy here.

4 years agoSupport for bytevectors
ilammy [Sun, 11 Dec 2016 03:13:43 +0000 (05:13 +0200)]
Support for bytevectors

This adds parsing of bytevector literals. They are considered simple data
as they do not allow nesting of arbitrary expressions. Actually, they
allow only exact integer literals in [0; 255] range.

However, here we do not check whether the numbers fall into that range.
The numbers are stored as just atoms and their parsing and validation is
left for future. The reason for this is that Scheme has far too many forms
of numbers. For example, 500/5, #b#e1100100, 0.01e+4, #O144@0, +100-0i
all represent effectively the same number 100 which is obviously a valid
bytevector constituent.

We also do handle nested data (currently allowing only nested
bytevectors) in order to check for proper bracket usage.

In order to simplify further implementation of vectors the parser is
bestowed with a lookahead of 1 (one) token in the form of `self.cur`
field. This makes the parser similar to the scanner.

4 years agoBasic parser
ilammy [Sat, 26 Nov 2016 09:45:38 +0000 (11:45 +0200)]
Basic parser

This implements basic data parser and sketches its test suite.
The parser can recognize simple non-nested data.

Note that the parser does not expand abbreviations and does not handle
data self-references. I expect that checking self-references and
rewriting the data into expressions will be handled by some separate
step. This parser will only faithfully handle the <datum> production
from R7RS.

Test suite uses 'data builders' -- a collection of combinators which
construct the test data in a declarative way. Maybe I should rewrite
lexer tests to use the same approach instead of ad-hoc macros.

4 years agoDrop tree diff and pretty-printing support
ilammy [Sun, 11 Dec 2016 02:24:57 +0000 (04:24 +0200)]
Drop tree diff and pretty-printing support

I've spent around two weeks fruitlessly trying to write a common interface
that can be used for both diffing and pretty-printing tree-like things.
The goal was to get a good tooling for parser tests and avoid rewriting
stuff in future when we add more trees after parse trees.

However, it did not work well *but* did divert my attention from actually
doing shit that matters, like writing the actual parser instead of
tinkering with the 'generic' interfaces. It makes it obvious that I have
no clue what good interface is, so I'd like to just throw out this code
to not bother with this idea anymore. Not that the diffing code in the
lexer was very helpful either, to be frank.

4 years agoUse unboxed closures as comparators for diffs
ilammy [Fri, 2 Dec 2016 23:03:08 +0000 (01:03 +0200)]
Use unboxed closures as comparators for diffs

Previously we have been using actual closure trait objects because I suck
as Rust. Now we use idiomatic unboxed closures for better efficiency. The
actual type of comparator is now encoded into the type of diff() functions
which means that the optimizer can inline the closures as they have unique
distinct types.

Note that child_diff() accepts a reference to the closure. This is
required for recursion, but should not affect the performance in any way.

4 years agoImprove equality comparisons in diffs
ilammy [Fri, 2 Dec 2016 22:36:54 +0000 (00:36 +0200)]
Improve equality comparisons in diffs

1. Relax the requirement for sequence diffs to be just PartialEq.

We do not have any strict requirement for reflexiveness of the comparison
for diffing so just use PartialEq instead of Eq.

2. Introduce ShallowPartialEq trait and use it for tree diffs.

It is unreasonable to require PartialEq implementations to be shallow.
They are most likely to be #[derived] and defining them as deep
comparisons is very useful for testing by itself (like, assert_eq!
should use deep comparison).

Thus introduce a new trait for shallow comparisons and reformulate
tree diffs using it instead of Eq.

3. Remove the 'flat_' prefix from tree diffs.

I do not think that we'll ever need a more complex diff algorithm for
these tests so drop the useless prefix. Also reshuffle the docs a bit.

4 years agoMove test utilities to a separate crate
ilammy [Sat, 26 Nov 2016 22:29:27 +0000 (00:29 +0200)]
Move test utilities to a separate crate

We are going to add a new intergration test for a parser soon, and it is
becoming a hassle to rebuild these utilities for each module once (and run
their tests each time). Thus the utilities are moved into their own crate
which is going to be built only once.

One note about dependencies. Note that 'utils' is a dev-dependency of
the 'libreader' crate and 'libreader' crate is a dependency of 'utils'.
There is no dependency loop here because the latter libreader is actually
'libreader with #[cfg(test)]', a separate crate. It's incompatible with
the usual libreader. These utilities are for tests only.

4 years agoRelicense to dual MIT/Apache-2.0 license
ilammy [Sat, 19 Nov 2016 23:35:51 +0000 (01:35 +0200)]
Relicense to dual MIT/Apache-2.0 license

As the current sole owner of the project I would like to relicense
it under the dual license that is generally used in the Rust world.
Generally, I'm happy with just MIT, but having patent protection
from Apache is fine by me as well, and it will be easier to inter-
operate with third-party Rust code, so why not.

I would also like to be more friendly to *gasp* possible future
contributors, so the contribution terms are now spelled out in a way
that does not require any extra bureaucratic shit. I am not a lawyer,
but I am open for a constructive dialogue on the level I can understand.

- Add LICENSE.Apache and LICENSE.MIT files with actual legalese.
- Update the LICENSE file to clarify the policy of the project.
- Update the boilerplate comments all over the code to include
  the new licensing terms and depersonalize the copyright claims.
- Add a "license" property to the crates.

4 years agoMerge pull request #2 from ilammy/basic-reader
ilammy [Sat, 19 Nov 2016 21:15:59 +0000 (23:15 +0200)]
Merge pull request #2 from ilammy/basic-reader

Implement basic reader.

There is quite a bunch of work here, all to implement the basic scanner.
We will finally have some code in master, yay!

4 years agoMiscellaneous cleanup
ilammy [Sat, 19 Nov 2016 19:28:17 +0000 (21:28 +0200)]
Miscellaneous cleanup

- Drop dead code
- Unify test function naming
- Simplify "if self.ahead_is() { for { self.read() } }" sequence
- Use self.cur.map_or() instead of comparing to None or self.at_eof()
- Do not use unsafe (premature optimization)

4 years agoSimplify bytevector recovery
ilammy [Sat, 19 Nov 2016 20:09:45 +0000 (22:09 +0200)]
Simplify bytevector recovery

Stop treating bytevector as special 'hashed' token. Fall back to scanning
the token as a number with invalid prefix if we are not on a happy path.

Fixup the tests accordingly:

- read #u( as invalid identifier "#u" followed by a paren
- read #u16 and #U571 as integers with invalid prefix
- read #u90_ex.a@mp!le1 as a polar complex number with exponential
  parts and an invalid prefix
- read #8 as a label mark

Also drop some diagnostics and scan_unrecognized() which are no longer
needed. This achieves the goal of not using Token::Unrecognized for
anything but the most grave cases.

4 years agoTell Travis where our crates are
ilammy [Sat, 19 Nov 2016 19:19:51 +0000 (21:19 +0200)]
Tell Travis where our crates are

This should fix Travis CI build which uses default 'cargo test' run.
Currently we do not have any central crate, so they are built
separately.

4 years agoMerge branch 'unicode' into basic-reader
ilammy [Sat, 19 Nov 2016 17:10:21 +0000 (19:10 +0200)]
Merge branch 'unicode' into basic-reader

Support for Unicode identifiers. Identifiers are normalized to NFKC.
There is an option to disable Unicode, allowing only ASCII to be used
in identifiers.

4 years agoMake Unicode support optional
ilammy [Sat, 19 Nov 2016 11:29:43 +0000 (13:29 +0200)]
Make Unicode support optional

While I am a strong pro-Unicode advocate, it may be a legitimate use case
to disable Unicode identifier support in order to get rid of the large
Unicode tables from 'libunicode' that are required for proper Unicode
handling. This commit introduces the "unicode" feature in 'libreader'
crate. Disabling it will remove the libunicode dependency and support
for Unicode identifers with it.

However, note that this does not disable Unicode support entirely. The
scanner is still UTF-8-aware and is able to read Unicode character
literals, Unicode in strings, etc. Disabling Unicode just prohibits
its usage in non-escaped identifers which actually require processing
of Unicode text. Handling Unicode blobs does not require any tables.
NFKC normalization is disabled as well, which means that one cannot use
strings like #\ⓝⓤⓛⓛ which were previously folded into valid ASCII.

One point that I'm firm with is that (plain) identifiers *cannot* contain
non-ASCII characters if Unicode support is compiled out. Most non-Unicode
Schemes allow to use anything composed of non-ASCII bytes. This is wrong.
Either one processes Unicode right, or one does not process it at all.

Some unit-tests expect full Unicode support. These are disabled together
with the Unicode library. Error recovery works differently in the case as
well so new tests were added which are checking that.

4 years agoFold case of identifiers with toNFKC_Casefold
ilammy [Fri, 18 Nov 2016 23:55:26 +0000 (01:55 +0200)]
Fold case of identifiers with toNFKC_Casefold

Finally get rid of ASCII casefolding and replace it with a proper Unicode
implementation. This updates some normalization tests as characters are
now correctly transformed, not left as is.

4 years agoUnicode case folding
ilammy [Sun, 13 Nov 2016 15:45:27 +0000 (17:45 +0200)]
Unicode case folding

This adds case-folding functions to the Unicode library. Currently we need
only toNFKC_Casefold() transformation, so we implement only it.

I do not know what data format will be the best for case-folding tables.
This needs some additional research and a look at other Unicode
implementations, preferably the ones using UTF-8. The usual tries are used
here, but maybe they are suboptimal. Though, I believe this is the best we
can do for NFKC_Casefold mapping. Maybe other mappings could be reasonably
split into 1-to-1 simple mapping and a bunch of irregular mappings.

4 years agoNormalize identifiers to NFKC
ilammy [Fri, 11 Nov 2016 21:12:27 +0000 (23:12 +0200)]
Normalize identifiers to NFKC

This is somewhat controversial thing, but I have made a decision:
identifiers should be normalized to fold visual ambiguity, and the
normalization form should be NFKC.

Rationale:

1. Compatibility decomposition is favored over canonical one because
   it provides useful folding for letter ligatures, fullwidth forms,
   certain CJK ideographs, etc.

2. Compatibility decomposition is favored over canonical one because
   it provides more protection from visual spoofing.

3. Standard Unicode transformation should be favored over anything
   ad-hoc because it's predictable and more mature.

4. Normalization is a compromise between freedom of expression and
   ease of implementation. Source code is not prose, there are rules.

Here are some references to other languages:

    SRFI 52: http://srfi-email.schemers.org/srfi-52/
    Julia:   https://github.com/JuliaLang/julia/issues/5434
    Python:  http://bugs.python.org/issue10952
    Rust:    https://github.com/rust-lang/rust/issues/2253

Unfortunately, there aren't very many precedents and open discussions
about Unicode usage in programming languages, especially in languages
with very permissive identifier syntax (like Scheme).

Aside from identifiers there are more places where Unicode can be used:

* Characters are not normalized, not even to NFC. This may have been
  useful, for example, to recompose combining marks, but unfortunately
  NFC may do more transformations than that, so it is no go. We preserve
  the exact Unicode character.

* Character names, on the other hand, are case-sensitive identifiers,
  so they are normalized as such.

* Strings and escaped identifiers are left untouched in order to preserve
  the exact spelling as in the source code.

* Directives are case-insensitive identifiers and are normalized as such.

* Numbers should be composed from ASCII only so they are not normalized.
  Sometimes this produces weird parses because characters that look like
  signs are not treated as such. However, these characters are invalid in
  numbers, so it's somewhat justified.

* Peculiar identifiers are shit. I'm sorry. Because of NFKC is is possible
  to write a plain, unescaped identifier that will parse as a number after
  going through NFKC. It may even look exactly like a number without being
  one. There is not much we can do about this, so we produce a warning
  just in case.

* Datum labels are mostly numbers, so they are not normalized as well.
  Note that sometimes they can be treated as numbers with invalid prefix.

* Comments are ignored.

* Delimiters should be ASCII-only. No discussion on this. Unicode has
  various fancy whitespaces and line separators, but this is source
  code, not a rich text document in a word processor.

Also, currently case-folding is performed only for ASCII range.
Identifiers should use NFKC_casefold transformation. It will be
implemented later.

4 years agoSupport for Unicode identifiers
ilammy [Thu, 10 Nov 2016 21:59:19 +0000 (23:59 +0200)]
Support for Unicode identifiers

This allows usage of Unicode in plain, unescaped identifiers. The allowed
set of characters is based on recommendations of R7RS and UAX #31:

- The initial character must have General_Category Lu, Ll, Lt, Lm, Lo,
  Nl, No, Pd, Pc, Po, Sc, Sm, Sk, So, Co.

- Subsequent characters can have General_Category Mn, Mc, Me, Nd
  in addition to everything allowed as an initial character.

- Zero-width non-joiner and zero-width joiner characters are also allowed
  as subsequent characters. There are no script restrictions on their use.

- Default_Ignoreable_Codepoints (with the exception of ZWNJ and ZWJ)
  are not allowed in identifiers.

  As of Unicode 9.0.0, the following codepoints are allowed by R7RS,
  but they are excluded by this rule:

    Lo codepoints not valid as initial and subsequent:

      U+115F HANGUL CHOSEONG FILLER
      U+1160 HANGUL JUNGSEONG FILLER
      U+3164 HANGUL FILLER
      U+FFA0 HALFWIDTH HANGUL FILLER

    Mn codepoints not valid as subsequent:

      U+034F COMBINING GRAPHEME JOINER
      U+17B4 KHMER VOWEL INHERENT AQ
      U+17B5 KHMER VOWEL INHERENT AA
      U+180B MONGOLIAN FREE VARIATION SELECTOR ONE
      U+180C MONGOLIAN FREE VARIATION SELECTOR TWO
      U+180D MONGOLIAN FREE VARIATION SELECTOR THREE
      U+FE00 VARIATION SELECTOR-1
      . . . . . . . . . . . . . .
      U+FE0F VARIATION SELECTOR-16
      U+E0100 VARIATION SELECTOR-17
      . . . . . . . . . . . . . . .
      U+E01EF VARIATION SELECTOR-256

  R7RS allows restricting the character sets, so this is fine.

- Unicode identifier stability guarantees are in effect. This includes
  characters with properties Other_ID_Start and Other_ID_Continue into
  the allowed character sets:

    Mn codepoints valid as initial and subsequent:

      U+1885 MONGOLIAN LETTER ALI GALI BALUDA
      U+1886 MONGOLIAN LETTER ALI GALI THREE BALUDA

    Other grandfathered characters (as of Unicode 9.0.0) are already
    valid constituents.

  Provisions for future extension of the 'grandfathered' sets are made.
  These sets are empty as of the current Unicode 9.0.0.

- ASCII range of identifier characters is restricted to the portable
  character set explicitly specified by R7RS. Note that the <special-
  subsequent> characters '+', '-', '.', '@' are technically allowed
  to start an identifier as long as it is a peculiar identifier which
  cannot be parsed as number.

Obviously, this requires support of libunicode, so the generator script
has been updated to produce required tables. It also now has an option
to compare identifier sets for different Unicode versions. This should
be helpful for migration to newer versions of the Unicode Standard.

Note that escaped identifiers allow usage of any Unicode characters in
any possible combinations (as long as it is valid Unicode text as
defined by the Unicode Standard).

4 years agoUnicode normalization
ilammy [Wed, 9 Nov 2016 21:16:12 +0000 (23:16 +0200)]
Unicode normalization

This is the normalization code I originally wrote for Sash. It has been
thoroughly tested and optimized so I believe in it.

The only major change is in the generator script in Python. I cleaned it
up, optimized the computation times, and switched over to using JSON
instead of pickle for data cache as JSON loads much faster.

4 years agoMerge branch 'identifiers' into basic-reader
ilammy [Fri, 4 Nov 2016 23:37:04 +0000 (01:37 +0200)]
Merge branch 'identifiers' into basic-reader

This adds support for identifiers and rectifies their fallback in number
scanning code. Case-folding directives are also implemented.

Currently only ASCII is supported. Full Unicode support will be added
later. It requires many character tables, Unicode algorithms, etc.

4 years agoCase-folding support for ASCII
ilammy [Fri, 4 Nov 2016 20:46:32 +0000 (22:46 +0200)]
Case-folding support for ASCII

Initially I thought that character names are always case-sensitive, with
this assumption supported by items 6.6 and 7.1 of R7RS:

  Case is significant in #\<character> and in #<character name>,
  but not in #\<hex scalar value>.

  Case is not significant except in the definitions of <letter>,
  <character name> and <mnemonic escape>; for example, #x1A and
  #X1a are equivalent, but foo and Foo and #\space and #\Space
  are distinct.

However, here is how case-folding directives are described in item 2.1:

  The #!fold-case directive causes subsequent identifiers and
  character names to be case-folded as if by string-foldcase
  (see section 6.7). It has no effect on character literals.

Thus I assume that #!fold-case affects the case-folding of character
names as well.

Another somewhat important point is the case-folding of escaped
identifiers. R7RS does not specify this directly. Even more, it can
be read as implicitly assuming that escaped identifiers should be
case-folded as well:

  For example, the identifier |H\x65;llo| is the same identifier
  as Hello, <...>

But I believe that the case-folding behavior was included for
compatibility reasons and the escaped identifer form is explicitly
designed for writing verbatim symbols. Furthermore, I plan to apply
NFKC to non-verbatim identifiers in the future. Thus it makes sense
to case-fold only non-verbatim identifiers while leaving the verbatim
ones as is.

4 years agoSupport for directives
ilammy [Fri, 4 Nov 2016 20:10:28 +0000 (22:10 +0200)]
Support for directives

This only scans over them and handles errors. There are no side effects
on the identifier scanning now.

As you can see, directives do produce tangible tokens. This should be
easier to handle for external tools that have to filter out whitespace
and comments anyway, and it allows us to fully reconstruct the character
stream out of the token stream.

4 years agoSupport for ASCII identifiers
ilammy [Thu, 3 Nov 2016 18:56:56 +0000 (20:56 +0200)]
Support for ASCII identifiers

Finally, the last meaningful token!

This change has a couple of important points:

1. Unrecognized is not a catch-all token anymore. Scheme has very
   permissive identifier syntax and they make most of the source code,
   so it is pretty much expected to treat anything other that a delimiter
   as an identifier (albeit, possibly invalid one).

   So Unrecognized is still used in some contexts, and I still plan on
   leaving it (e.g., to replace tokens that produce too many diagonstics).
   But it's not a type of a pokemon now.

2. Peculiar identifiers are now Identifiers. This yields massive diff
   all over the number-scanning tests, but that's my payback.

4 years agoSupport for datum labels
ilammy [Wed, 2 Nov 2016 21:21:35 +0000 (23:21 +0200)]
Support for datum labels

This is simple as well. R7RS syntax is a bit ambiguous about whether these
tokens must be followed by an explicit delimiter, but the examples and the
wording in grammar suggest that they are not required. So we successfully
parse "#1##2#" as LabelRef("1"), LabelRef("2").

Some of the previous tests had to be updated as they actually include
invalid LabelMark tokens.

4 years agoSupport for boolean literals
ilammy [Wed, 2 Nov 2016 19:30:56 +0000 (21:30 +0200)]
Support for boolean literals

Easy and straightforward. My initial implementation of recovery has simply
bailed out to returning Unrecognized. However, I felt it was inconsistent
to treat invalid prefixed identifiers starting with T or F any different,
so now we do full lookahead to check for booleans and fall back to
scanning them as invalid numbers if we don't see exact boolean form.

4 years agoMerge branch 'complex-numbers' into basic-reader
ilammy [Tue, 1 Nov 2016 23:15:33 +0000 (01:15 +0200)]
Merge branch 'complex-numbers' into basic-reader

III    H   H   A  TTTTT EEEE    TTTTT H   H III  SSS,
 I     H   H  A A   T   E         T   H   H  I  S
 I     HHHHH A   A  T   EEEE      T   HHHHH  I   SSS
 I     H   H AAAAA  T   E         T   H   H  I  ,   S
III    H   H A   A  T   EEEE      T   H   H III  SSS

Really.

This is not the best syntax in the world. I'd say it's pure evil,
especially when paired with peculiar identifiers and these infnans
which break the idyllic idea that 'numbers are only digits'.

I'm glad that this should be it for the damned syntax of numbers of
Scheme, because it is even worse that characters.

Like, seriously:

  - everything up to numbers:    3684 lines changed
  - integers, floats, rationals: 1669 lines changed
  - complex numbers:             1467 lines changed

Changes for numbers are almost as massive as all the code before them
which actually includes a bulk of the test harness and the diffing code.

Though, I may be bitching around all the day, but this does not change
the fact that this is the R7RS syntax, and we should support it, no matter
how awful it is and how much I despise it. This is the power of legacy
and hysterical raisins, kids.

4 years agoAdditional tests for complex numbers
ilammy [Sat, 29 Oct 2016 17:34:34 +0000 (20:34 +0300)]
Additional tests for complex numbers

These are just to pimp up the coverage and to make sure that all dumb
compositions of delimiters are handled in some sane way. It may be not
perfect, but I'm simply sick of these complex numbers, so let it pass.

4 years agoRecover from multiple consecutive signs
ilammy [Sat, 29 Oct 2016 17:33:44 +0000 (20:33 +0300)]
Recover from multiple consecutive signs

We now treat multiple consecutive signs as one giant sign character rather
than scanning over the first of them, and treating the next one as a
starter of a new complex part. The signs may appear before a number and in
the exponents.

4 years agoRecover from complex numbers with multiple parts
ilammy [Sat, 29 Oct 2016 17:32:33 +0000 (20:32 +0300)]
Recover from complex numbers with multiple parts

This first change properly deals with the situation when a number contains
multiple complex parts and/or multiple exponents.

Extra complex number parts (imaginary and arguments) are now properly
detected and reported as such. Previously we expected only one such part,
now we handle unlimited number. As ComplexScanningMode::Imaginary is now
an inadequate description, it is renamed to Subsequent. It is still
slightly different from Argument mode in how 'i's are handled.

Also we implement scanning of multiple consecutive exponents. The
exponents can have an optional sign in them. We now treat this sign
as a part of an extra exponent that needs to be scanned over during
recovery, not treated as a start of a new complex part. Care must be taken
to handle exponents in every place where we are panic-scanning (such as
infnan suffixes, for example).

4 years agoSupport for rectangular form of complex numbers
ilammy [Sat, 29 Oct 2016 17:19:04 +0000 (20:19 +0300)]
Support for rectangular form of complex numbers

Now, this is hard. Mostly because the rectangular form uses + and - signs
as delimiters, and they are already used in multiple places in numbers.
Plus it has wacky special cases like '+i' and '-i', and infnans with their
suffixes require special treatment as well, and many more stuff.

However, this _is_ mostly the right thing. Though, the tests are currently
broken because of several deficiencies in handling sign characters. These
will be rectified in the next commits.

There are some changes in previous non-complex tests. They are related to
the fact that sign characters now mark the start of an imaginary part of
a complex number. So in these places they are not invalid characters
anymore, and we expect an 'i' to appear in the end.

This also adds recovery tests for complex numbers (including polar form).
Note how some of the strings are parsed as peculiar identifiers and woe.

4 years agoSupport for polar form of complex numbers
ilammy [Sat, 29 Oct 2016 17:18:24 +0000 (20:18 +0300)]
Support for polar form of complex numbers

This is actually the sanest form of complex numbers because it has
a distinct sigil in it which is not used anywhere else. Rectangular
form heavily uses signs so it is much harder to implement *and*
(mostly) to recover from errors.

Scanning of special characters will be controlled by the Complex-
ScanningMode enum. We only add success tests there as there isn't
much new recovery now.

4 years agoTreat +. as peculiar identifier
ilammy [Fri, 28 Oct 2016 22:40:08 +0000 (01:40 +0300)]
Treat +. as peculiar identifier

This is to be consistent with treatment of ".+". The grammar of Scheme
does not explicitly specify how to treat this sequence of characters
(presumably, it is invalid). However, we treat it as a peculiar identifier
of form <explicit-sign> <dot> <dot-subsequent> (class 3 as recognized
by peculiar_identifier_ahead).

Signs are pretty important delimiters in complex numbers, so getting this
straight is also important.

4 years agoMerge branch 'rational-numbers' into basic-reader
ilammy [Sat, 22 Oct 2016 07:54:45 +0000 (10:54 +0300)]
Merge branch 'rational-numbers' into basic-reader

This adds support for rational numbers (at last!) and includes some
refactoring of the number scanning code which should make implementation
of complex number support somewhat easier.

The implementation is in LL(1) spirit, with an exception for handling
infnans and peculiar identifiers which requires 5-character lookeahead.

4 years agoImprove handling of peculiar identifiers
ilammy [Tue, 18 Oct 2016 20:19:13 +0000 (23:19 +0300)]
Improve handling of peculiar identifiers

Yes, they are awful.

This improves handling of special identifiers like +, ..., and so on. All
of them start like a number while not being one in the end. To simplify
parsing of actual numbers we check for peculiar identifiers at start and
do not return to this question again. This allows us to assume that we are
scanning a valid number and anything invalid is an error, not an attempt
to write a peculiar identifier.

Except for special cases like '+inf.0', there is another special case for
recovery: a peculiar identifier followed by a number prefix. "#infinity",
for example. Previously we have been doing a quick check for numbers, but
now we do a quick check for peculiar identifiers in scan_number_literal(),
so we can just skip to there from the hash prefix scanning code.

The actual code for checking is a bit convoluted. Hopefully, the formal
grammar in the comments will be helpful in understanding it.

I am not particularly happy with the diagnostics produced by this
recovery, but they are okayish, considering the circumstances. It is
much better that spewing out an err_lexer_invalid_number_character
for every character of a token.

4 years agoImprove handling of infnans in numbers
ilammy [Sun, 16 Oct 2016 15:40:47 +0000 (18:40 +0300)]
Improve handling of infnans in numbers

Basically we are moving handling of explicit signs and infnans deeper
into the number scanning code. This simplifies their handling in the
case of rational numbers, and it should make implementation of complex
numbers easier.

For example, this allows us to detect and report infnans in denominators
instead of treating the whole rational number as an invalid suffix of
the initial infnan, or considering them simply invalid characters.

However, the tests are still broken due to bad handling of peculiar
identifiers (which cases like "+infinity" are). This is the evil part
of Scheme's grammar. I'm not responsible for this insanity that demands
"+inf.0/inf.0" to be treated as an invalid number, but "+inf.O/inf.O"
being a totally valid identifier. But, meh, legacy. I will make a rant
about it in comments later.

(Yes, infnan handling now requires 5-character lookahead, but it makes
the implementation so much easier and readble that I have decided to
leave it as is. Blame the peculiar identifiers and their syntax.)

4 years agoSupport for rational numbers
ilammy [Sat, 15 Oct 2016 19:53:55 +0000 (22:53 +0300)]
Support for rational numbers

This includes full support for correct rational numbers and some initial
implementation of recovery code. Aside from actual implementation there
are the following changes:

- `DigitScanningMode` struct is dropped in favor of explicit arguments.
  It is used only in one place so there was no real merit in having it.

- `is_fractional` is consistently renamed to `non_integer`. This is
  to reflect the fact that it also includes numbers with only exponent
  present. It will also include infnans as well in the future.

The tests are actually broken with this change. IEEE 754 specials
(aka infnans) will be properly handled in the next commit.

4 years agoMerge branch 'number-cleanup' into basic-reader
ilammy [Sat, 15 Oct 2016 19:16:32 +0000 (22:16 +0300)]
Merge branch 'number-cleanup' into basic-reader

This includes some refactoring and cleanup of the number scanning code
which should make it more amendable to further changes.

Previously I have tried an approach with an explicit state machine. It
worked, but looked quite ugly. So I have decided to go with the usual
pseudo-LL(1) approach which have been used before.

Also, this is now a merge of a series of commits rather than one giant
dump of changes. Hopefully this would be easier for people to review
(if anybody cares, lol).

4 years agoDo not treat # as a delimiter
ilammy [Sat, 15 Oct 2016 11:37:56 +0000 (14:37 +0300)]
Do not treat # as a delimiter

After all, R7RS says that # is *not* a delimiter. And we do not treat it
as such in number scanning code. Just quit pretending that it is a good
idea and do not treat # as a delimiter anywhere.

This makes chaining characters like #\t#\e#\s#\t invalid, update the
tests to reflect this fact.

One important note on this is that other separators are fine, so
things like #\t|he|,#\s"e" #\a(re) #\o;k.

Also introduce a helper function to check for whitespace
(scan_character_literal() looked ugly without it).

4 years agoCleanup prefix scanning recovery
ilammy [Sat, 15 Oct 2016 10:23:43 +0000 (13:23 +0300)]
Cleanup prefix scanning recovery

4 years agoUpdate infnan scanning
ilammy [Fri, 14 Oct 2016 21:48:09 +0000 (00:48 +0300)]
Update infnan scanning

- Allow inf.0 and nan.0 only after an explicit sign. This has kinda bad
  recovery code, but a proper implementation requires backtracking, and
  the most expected mistake 'inf.0' is a valid identifier anyway.
- Also factor out infnan scanning into methods to avoid copypasta.

4 years agoUpdate digit scannign interface
ilammy [Fri, 14 Oct 2016 21:14:33 +0000 (00:14 +0300)]
Update digit scannign interface

- Introduce scan_number_digits() to scan the digits (integer or
  fractional) and scan_number_value() to scan the digits *and*
  the optional exponent after them.
- Lower amount of copypasta in the code.
- Improve missing digits check to be more precise.

4 years agoSimplify exponent scanning
ilammy [Fri, 14 Oct 2016 17:07:39 +0000 (20:07 +0300)]
Simplify exponent scanning

- Allow exponents only in decimal-radix literals.

4 years agoCleanup core number scanning methods
ilammy [Fri, 14 Oct 2016 16:12:57 +0000 (19:12 +0300)]
Cleanup core number scanning methods

- Unify number scanning entry point to just scan_number_literal().
- Update prefix scanning interface to return data via out params.
- Improve prefix scanning recovery (and update tests accordingly).

4 years agoMake diff output more obvious
ilammy [Fri, 14 Oct 2016 21:02:42 +0000 (00:02 +0300)]
Make diff output more obvious

Invert diffs so that they tell the developer what needs to be changed
in the code. E.g., if you see a + then the thing needs to be added to
whatever the code is currently doing.

4 years agoCosmetic diagnostic rename
ilammy [Thu, 13 Oct 2016 22:15:29 +0000 (01:15 +0300)]
Cosmetic diagnostic rename

- Consistently use 'number radix' instead of 'number base'.
- Drop 'missing exponent' diagnostic in favor of more general
  'missing digits' diagnostic.

4 years agoSupport for float numbers
ilammy [Tue, 20 Sep 2016 20:38:55 +0000 (23:38 +0300)]
Support for float numbers

This adds support for float number forms of Scheme, including decimal
point floats, exponential (scientific) notation, and IEEE 754 special
values.

Again, terrible syntax and terrible workarounds, but this is also a
terrible implementation. I will be refactoring it in some next commit.
Now it is important to have some code that works.

4 years agoSupport for integer numbers
ilammy [Thu, 1 Sep 2016 19:08:01 +0000 (22:08 +0300)]
Support for integer numbers

This adds support for integer number forms of Scheme, including plain
decimal numbers, explicit signs, and base and exactness prefixes.

As with characters, the syntax is terribad, but this is even worse as
numbers are competing with identifiers which have very liberal syntax.
The disambiguation rule is literally if the prefix is a number then it
is a number, otherwise it is an identifier. But again, this is life.

Number prefixes start with a hash, so this change also updates recovery
in (byte)vector literals. These are not significant changes though.
The main point is that we now use self.peek() in scan_hash_token()
in order to leave self.cur == '#' when we call scan_number_prefixed().

Also, note that we do not parse numbers here (i.e., they all are flat
Token::Number, not Token::Number::Integer::DecimalImplicitPositive).
This is because the parser does not care for exact number types and
their values, and we will still have exact spelling of the tokens
when we will need it.

4 years agoSupport for escaped identifiers
ilammy [Wed, 31 Aug 2016 17:47:44 +0000 (20:47 +0300)]
Support for escaped identifiers

|This is the simplest identifier syntax in Scheme. By the way,
this whole paragraph is a single identifier, including the line
endings.|

Yes, this is kinda dumb, but R7RS says that "any character,
including whitespace characters, but excluding the backslash
and vertical line characters, can appear verbatim in such an
identifier". So we obey. Anything is allowed in there, except
for bare backslashes and vertical bars. We perform no line
ending conversion in identifiers. Also, line escapes are not
allowed there (they are treated as invalid escape sequences).

However, all other escape sequences can be used in identifiers:
traditional escapes like \n and Unicode escapes like \x1234;
It is also possible to write an empty identifier like ||.

4 years agoSupport for string literals
ilammy [Thu, 25 Aug 2016 19:57:49 +0000 (22:57 +0300)]
Support for string literals

This adds support for string literals and all escape sequences
permitted in them. This commit also adds the _intern pool_ to
the library as strings are the first tokens without immediate
representation. The pool will be used to store symbolic data
output by the scanner such as string values, identifier names,
exact number spelling, directive names, etc. The pool has some
details regarding its usage, refer to module documentation.

Support for all escape sequences is kinda bulky, especially for
the line escapes. But again, this is the same story as with
character literals: this is legacy and we have to deal with it.
I also like proper error recovery so we do that as well.

4 years agoSupport for character literals
ilammy [Sun, 21 Aug 2016 09:25:37 +0000 (12:25 +0300)]
Support for character literals

This adds support for all three forms of character literals:

- single-character literals like #\!
- named character literals like #\newline
- hexcoded Unicode literals like #\x200C

As noted in comments, such syntax is unbelievably ambiguous and
generally awful, but we have to deal with it because of raisins.
After all, string manipulation is not a design goal for Scheme.

Though, there are some points which I could not stand and opted
to digress from R7RS in order to implement a saner behavior.

For example, R7RS demands the following parses:

    "#\\ "    -> Character(' ')
    "#\\\t"   -> Character('\t')
    "#\\\n"   -> Character('\n')
    "#\\\r\n" -> unspecified lol,
                 supposedly Character('\r') + Whitespace

I find this extremely confusing and I believe that whitespace
should not matter outside of string literals and escaped
identifiers. Thus in this case we will produce a syntax error
and will return a placeholder character instead. The following
whitespace will be ignored then. We insist on using named
characters like #\space in these cases.

Also, delimiter rules have been tweaked a bit and applied to the
unrecogized sequence parser, so recovery test cases for vector
openers had to be updated.

4 years agoSupport for comments
ilammy [Sat, 20 Aug 2016 16:43:27 +0000 (19:43 +0300)]
Support for comments

This implements all three tokens of Scheme comments:

- ; line comments
- #|nested #|block comments|#|#
- #;(s-expression comments)

(S-expr-comments will be actually handled by the parser.)

4 years agoSupport for fixed tokens
ilammy [Fri, 19 Aug 2016 23:53:13 +0000 (02:53 +0300)]
Support for fixed tokens

This adds support for simple fixed-character tokens like (, ), #u8(.
Note that bytevector syntax is always case-insensitive as per R7RS.

scan_unrecognized() now takes the starting point as an argument,
as only its caller knows the starting point of a garbage token.

4 years agoInitial scanner implementation + utilities
ilammy [Thu, 18 Aug 2016 21:08:52 +0000 (00:08 +0300)]
Initial scanner implementation + utilities

This includes an initial scanner than can handle only whitespace,
basic error reporting facility, a test harness for the scanner,
and a shitload of inherited utilities. Fly safe.

4 years agoInitial commit. README, LICENSE, and stuff
ilammy [Fri, 12 Aug 2016 23:13:41 +0000 (02:13 +0300)]
Initial commit. README, LICENSE, and stuff