0.11.1

Manual token disambiguation

Previously when two definitions computed could match the same input and were assigned the same priority, Logos would make an arbitrary choice about which token to produce. This behavior could produce unexpected results, it is therefore now considered a compile error, and will be reported as such.

Example

Consider two regexes, one matching [abc]+ while the other matches [cde]+. Both of those would have a computed priority of 1, and both could match any sequence of c.

Logos will now return a compile error with hints for solution in this case:

error: A definition of variant `Abc` can match the same input as another definition of variant `Cde`.

hint: Consider giving one definition a higher priority: #[regex(..., priority = 2)]
   --> tests/tests/edgecase.rs:410:17
    |
410 |         #[regex("[abc]+")]
    |                 ^^^^^^^^

error: A definition of variant `Cde` can match the same input as another definition of variant `Abc`.

hint: Consider giving one definition a higher priority: #[regex(..., priority = 2)]
   --> tests/tests/edgecase.rs:413:17
    |
413 |         #[regex("[cde]+")]
    |                 ^^^^^^^^

error: aborting due to 2 previous errors

Setting priority = 2 to either token will override the computed priority, allowing Logos to properly disambiguate the tokens.

Generic type parameters

Deriving Logos on an enum with type parameters like so:

    #[derive(Logos, Debug, PartialEq)]
    enum Token<S, N> {
        #[regex(r"[ \n\t\f]+", logos::skip)]
        #[error]
        Error,

        #[regex("[a-z]+")]
        Ident(S),

        #[regex("[0-9]+", |lex| lex.slice().parse())]
        Number(N)
    }

Will now produce following errors:

error: Generic type parameter without a concrete type

Define a concrete type Logos can use: #[logos(type S = Type)]
   --> tests/tests/edgecase.rs:339:16
    |
339 |     enum Token<S, N> {
    |                ^

error: Generic type parameter without a concrete type

Define a concrete type Logos can use: #[logos(type N = Type)]
   --> tests/tests/edgecase.rs:339:19
    |
339 |     enum Token<S, N> {
    |                   ^

It's now possible to define concrete types for the generic type parameters:

    #[derive(Logos, Debug, PartialEq)]
    #[logos(
        type S = &str,
        type N = u64,
    )]
    enum Token<S, N> {

This will derive the Logos trait for Token<&str, u64>. All reference types (like &str here) will automatically use the lifetime of the source.

Other changes:

• It's now possible to define callbacks using callback = ... syntax inside #[regex(...)] and #[token(...)] attributes. This allows for callback and priority to be placed arbitrarily within the attribute. All of these are now legal and equivalent:

  #[regex("[abc]+", my_callback, priority = 10)]
  #[regex("[abc]+", callback = my_callback, priority = 10)]
  #[regex("[abc]+", priority = 10, callback = my_callback)]

• Priority is now computed from an intermediate representation of the regex, before parsing it to the state machine graph.

0.11.0

New face, rehauled API

Logos has a new cute logo 🤓.

There is a number of breaking changes this release, aimed at reducing API surface and being more idiomatic, while adding some long awaited features, like the ability to put slices of the source or arbitrary values returned from callbacks directly into a token.

Most of the changes related to the #[derive] macro will trigger a compile error message with an explanation to aid migration from 0.10. Those will be removed in the future.

API changes

• 🔨 [breaking] LOGOS NO LONGER HANDLES WHITESPACE BY DEFAULT. The #[trivia] attribute has been removed. Whitespace handling is easily added by defining #[regex(r"[ \n\t\f]+", logos::skip)] on any token enum variant. Putting it along #[error] is recommended.
• 🔨 [breaking] Lexer no longer has the advance method, or publicly visible token field. Instead Lexer now implements the Iterator trait and has a next method that returns an Option of a token.
• 🔨 [breaking] #[end] attribute was removed since it became obsolete.
• 🔨 [breaking] #[regex = "..."] and #[token = "..."] definitions are no longer valid syntax and will error when used in this way. Those need to be transformed to #[regex("...")] or #[token("...")] respectively.
• 🔨 [breaking] Callbacks are now defined as a second parameter to either #[regex] or #[token]. Those can be either paths to functions defined elsewhere (#[token("...", my_callback)]), or inlined directly into the attribute using closure syntax (#[token("...", |lex| { ... })]).
• 🔨 [breaking] Extras trait has been removed. You can still associate a custom struct to the Lexer using #[logos(extras = MyExtras)] with any type that implements Default, and manipulate it using callbacks.
• 🔨 [breaking] #[callback] attribute was removed since it was just polluting attribute namespace while offering no advantages over attaching callbacks to #[regex] or #[token].
• 🔨 [breaking] Lexer::range has been renamed to span. span and slice methods continue to return information for the most recently returned token.
• ✨ [new] Lexer has a new spanned method takes the ownership of Lexer and returns an interator over (Token, Span) tuples.
• ✨ [new] Callbacks can return arbitrary values (or Options/Results of values) that can be put into token enum variants. Currently only a single value in a tuple-like variants is supported (Token::Variant(T)).
• ✨ [new] Logos will automatically populate Token::Variant(&str) with a matching str slice if no callback is provided.
• ✨ [new] Callback return values can be used to skip matches using the Skip type. It's also possible to dynamically skip matches using the Filter type.

Internals

• 🚀 Generated code is now more likely to produce optimized jump tables for complex branches.
• 🚀 Logos can now stack multiple boolean lookup tables into a single table, reducing the memory cost of using the tables by a factor of 8, and improving cache locality.
• 🚀 For narrow range boolean branches Logos can now produce a lookup table packed into a single u64.

0.10.0

Brand new #[derive]

The derive macro at heart of Logos has been rewritten virtually from scratch between 0.10.0-rc2 and now. The state machine is now built from a graph that permits arbitrary jumps between nodes, instead of a tree that needs to build up permutations of every possible path leading to a token match. This has fixed a whole number of old outstanding issues (#87, #81, #80, #79, #78, #70).

The new codebase is nearly 1k LOC shorter, compiles faster, outputs smaller code, is more cache friendly, and is already proving itself to be easier to debug and optimize. This new release also gets rid of a number of hacks that were previously introduced to manage token disambiguation and loops, which were a huge source of bugs. All nodes in the new state machine are indexed, and loops are described as circular state jumps. Jumps between states are realized by tail recursion calls in the generated code, which in most cases should have performance profile of goto in C.

No more CPU melting

A case that was breaking the old Logos was using a simple \w+ regex. This is a particularly devious regex flag, since it expands to cover codepoints for every Unicode alphabet, which was then further expand into corresponding byte sequences.

Old logos produced staggering 228k lines of Rust code just for that single pattern, which then usually failed to compile after rustc consumed all available memory. That's because a single \w produced a tree with 303 leaf nodes, which then had to be duplicated for every leaf to handle the loop, which in the end produced a monstrous tree with 91809 leaf nodes (not counting any branches leading to those).

By contrast, in the new version a single \w produces a graph with 278 nodes total, while \w+ produces a graph with 279 nodes. That is to say, we went from n ** 2 , to n + 1, which is a universe of a difference.

Token disambiguation

This release also improves the previously flaky token disambiguation, which is now properly defined and documented. It also leaves us with an option to provide different strategies in the future.

Future

I think the next minor/major release will do a clean-up of the API surface. Since Logos currently pollutes the attribute namespace quite a lot, using pretty generic labels like token or callback, it might be wise to wrap most if not all of them into #[logos(...)]. This should help to make the crate more future-proof, and play nicer with other custom derives that you might want to put on your token enums.

I'm very excited to have this release out, and have a whiteboard full of ideas of what can bet tweaked to improve the performance, before even touching SIMD (which is on the horizon somewhere).

API changes:

• Derive macro now allows discriminant values to be set, as long as they are greater than 0, and smaller than the total number of variants in the enum.
• Removed NulTermStr support. In turn, a lot of effort has been put to increase the performance using regular &str sources, which more than makes up for it.
• Logos no longer considers nul byte (0x00) to terminate input.
• It's now possible to define binary, non-Unicode token definitions (both as plain literals and regex). Doing so will force the lexer to use non-Unicode sources such as &[u8], and will fail to compile with &str.
• It's now possible to change the default trivia (whitespace), including the option to completely disable it (more documentation will follow).
• Removed the Split trait.
• Removed the Lexicon type alias. Logos::lexicon has been replaced by Logos::lex, which then implements all logic internally.

0.9.7

• Fixes a stack overflow introduced in 0.9.4 (#58).

0.9.6

• Fixing a bug in code generation where a valid token definition would sometimes produce an error variant instead of it's token variant (#59).

0.9.5

• Fixed a bug found out at #55.

0.9.4

• Added a fixed-width multi-byte reading option that fixes some corner cases where otherwise backtracking would be needed. For example having "." and "..." token definitions matching against ".." should produce two single-dot tokens.

0.9.3

• Fix a bug detected in the tests added in #49. The conditions for creating prefix-intersecting branches has been loosened up, so that adding new token definitions should not break things, while still preventing infinite recursion if a branch is followed by a Repeat fork.

0.9.2

• Fixes to the more complex case in #40 (test case added in #47).

0.9.1

• Properly fixes issue #40.