Rust backend?

[pmetzger]

I saw some references in auxiliary materials on re2c.org to a desire to have a rust backend. Has any work been done on this? If not, would help on it be welcome? (And where is the code that handles particular languages located?)

[skvadrik]

Has any work been done on this?

No work so far. I don't know Rust well enough, and I only did a brief investigation to confirm that it is feasible. One of the obstacles is that Rust doesn't have goto, but it is easy to overcome by having an integer state variable and a state switch at the beginning of the generated lexer.

If not, would help on it be welcome?

Definitely yes!

And where is the code that handles particular languages located?

That would be mostly in https://github.com/skvadrik/re2c/tree/master/src/codegen. Supported languages are defined here, so generally you can find most of the language-specific places by searching for text LANG_.

• The program is represented as a list of blocks, which correspond to /*!re2c ... */ blocks and directives and the source code in-between. Each block may belong either to the main output file, or to the output header.

• Each block has a number of indented Code elements, which can be one of the few program constructs defined by the CodeKind enum.

• The main code generation driver is here.

• The generated code goes through a number of code generation passes, when re2c gradually expands the program control flow graph. Some Code elements accumulate whole-program information, so they cannot be generated straight away. Such elements are expanded later.

• At last there is a "rendering" pass where most of the language-specific split is done.

• Each language backend has a set of examples, which should give the idea of the basic functionality that should be covered.

• Documentation also needs to handle multiple languages (that is done with the help of a simple script).

As the previous work on the Go backend has shown, adding a new backend requires a lot of testing with different combinations of existing re2c features. But it is ok to start with something simple and get it working. Some features or special cases may not work out; that is fine, as long as the main cases are working. The Rust work should be done on a branch, as we try to keep master in a mostly stable and consistent state. Help is welcome, including any insights or examples.

[pmetzger]

FYI, it appears LLVM has just added a hack that optimizes DFAs created with loop-around-switch style constructs. See https://reviews.llvm.org/rG02077da7e7a8 which will presumably be in a release in a few months. So Rust won't suffer too much for the lack of goto statements.

I don't recall seeing an option in the manual for constructing a loop with embedded switch style of code generation, so I suppose that would need to be done afresh. However, I also presume that could optionally be used by both the C and Go backends as well, so one way to test that particular thing would be to generate C code of that form and then make sure all the tests still pass?

[skvadrik]

Jump threading is useful. But even without it I don't expect the performance to be worse than a hand-written or a table-based lexer in Rust. That is only my intuition, of course.

I don't recall seeing an option in the manual for constructing a loop with embedded switch style of code generation, so I suppose that would need to be done afresh. However, I also presume that could optionally be used by both the C and Go backends as well, so one way to test that particular thing would be to generate C code of that form and then make sure all the tests still pass?

Right, re2c doesn't have an option for that. I don't think it would generate faster code for C and Go backends, but it would be interesting to try, if only to estimate the difference between this and the usual goto-based lexer. It is a good idea to implement it for C first.

And sorry for a late reply!

[pmetzger]

Even ignoring the performance estimation (which would be interesting), it seems like it would be easier to build the loop-and-switch code for Rust if it was already built for C. (Also of interest at some point might be a tail recursive version; several C compilers now have annotations to force tail recursion. Unfortunately the Rust compiler does not yet have tail recursion optimization.)

[Raekye]

Hi, this would be of interest to me too. Is there any update or existing work on this? If not, I might give a shot at it sometime. Regarding the gotos <-> loop-switch transformation, I was wondering how much of re2c depends on "falling through" states/labels? Off the top of my head, that seems like it could be troublesome (for Rust)

[skvadrik]

Is there any update or existing work on this?

Not on my side.

I was wondering how much of re2c depends on "falling through" states/labels?

switch statements always have an explicit goto, and if/else statements may omit goto if the branch target happens to be the next state, but this logic can be turned off (the relevant code is here, the == next conditions).

Can you give an example of what would be a problem? I'm not sure I understand correctly.

[pmetzger]

I haven't really been working on this. I'll freely admit my C++ is too, er, rusty.

One thing that might make sense would be for me to hand convert a generated lexer from C to Rust to provide an example of what the target state needs to look like, but I'm not sure that would really be of much help in practice?

[skvadrik]

I'm not sure that would really be of much help in practice

It would, because my knowledge of Rust is lacking and having an example makes it easier. That's how the Go backend started: #272.

[pmetzger]

@skvadrik: tell me which lexer I should start with hand converting and I'll get to it this
weekend. Note that it would be best if it was simple and looked as much like a loop around a switch on a state variable as possible, though I don't think a code generator for that style currently exists?

[skvadrik]

@pmetzger Take any of the examples, for example the simplest one, see the generated code for the C backend and the the Go backend. Examples cover different re2c features. The most interesting part is input buffer management: using pointers or indices in an array of characters, detecting end of input, buffer refilling, etc., so the next examples to convert would be those related to YYFILL. When adding Rust support, the goal would be to make all examples work for Rust. Examples are also explained in the online manual.

There is no code generator based on a loop, but if you have trouble with that part just take some extremely simple example like /*!re2c [a] {} */ and generate C code for it --- it will have only a few states with very simple control flow.

[Raekye]

switch statements always have an explicit goto, and if/else statements may omit goto if the branch target happens to be the next state, but this logic can be turned off (the relevant code is here, the == next conditions).

Can you give an example of what would be a problem? I'm not sure I understand correctly.

I just double checked the generated lexer for my project, and it has code like:

yyc_newline:
        if (((self->buffer + self->length + YYMAXFILL) - (self->cursor)) < 2) yyfill(2);
        yych = *(self->cursor);
        switch (yych) {
        case '\t':      goto yy4;
        case '\n':      goto yy7;
        case '\r':      goto yy9;
        case ' ':       goto yy10;
        case '#':       goto yy13;
        default:        goto yy2;
        }
yy2:
        ++(self->cursor);
yy3:
// more code

Hopefully I'm not missing something stupid - but the label/state yy2 depends on falling through to yy3 correct? Off the top of my head, translating this to a loop-switch in C seems pretty straightforward since a switch really just contains labels with the same fall-through semantics. To make sure I'm on the same page, it would look something like this:

enum label_t {
    yyc_newline,
    yyc_2,
    yyc_3,
   // ...
};

label_t current_label = ...;
while 1 {
    switch current_label {
    case yyc_newline:
        if (((self->buffer + self->length + YYMAXFILL) - (self->cursor)) < 2) yyfill(2);
            yych = *(self->cursor);
            switch (yych) {
            case '\t':      current_label = yy4; continue;
            case '\n':      current_label = yy7; continue;
            case '\r':      current_label = yy9; continue;
            case ' ':       current_label = yy10; continue;
            case '#':       current_label = yy13; continue;
            default:        current_label = yy2; continue;
            }
        }
    case yy2:
        ++(self->cursor);
        // this still falls through to yy3 as in the original code
    case yy3:
        // more code
    }
}

Basically, I would turn goto xxx; into current_label = xxx; continue;.

But in Rust, besides not having gotos, its match construct (the closest thing to a C switch) does not fall-through. I only took a quick look at code_goto.cc; I'm not familiar with exactly where/how it's used, but are you saying by disabling the == next, label yy2 would get an explicit goto yy3?

I'm far from a Rust expert, but I have been coding in it as my primary language for about 6 months (I would say it's not particularly hard to pick up once you're forced to use it) - I don't think we need anything too fancy so hopefully I can answer any basic Rust questions!

[skvadrik]

Ah, I see. You can avoid fallthrough like this:

while 1 {
 switch current_label {
    // ...
    case yy2:
        ++(self->cursor);
        current_label = yy3;
        continue;
    case yy3:
        // more code
    }
}

Essentially fallthrough from yy2 to yy3 is like a switch where all cases have a goto yy3, so they are omitted for brevity. But you can bring the goto yy3 back and it will not change anything. In Rust it will be more work because we have to reiterate on the state variable.

hopefully I can answer any basic Rust questions!

Great!

[Raekye]

Essentially fallthrough from yy2 to yy3 is like a switch where all cases have a goto yy3, so they are omitted for brevity. But you can bring the goto yy3 back and it will not change anything. In Rust it will be more work because we have to reiterate on the state variable.

To be sure, this behaviour is exactly controlled by the == next in code_goto.cc? Again forgive me I'm not too familiar with the code - it seems that file is language-agnostic. Naively, I would want to just guard ... == next with && opts->lang != LANG_RUST (of course, we could just propagate that information into this function, but then it would nolonger be language-agnostic).

I'm not sure that would really be of much help in practice

It would, because my knowledge of Rust is lacking and having an example makes it easier. That's how the Go backend started: #272.

Does this mean you will be attempting a Rust backend, given examples? I.e. would you recommend attempting a Rust backend on my own, or would it be best to just provide more examples?

[Raekye]

I started looking at implementing things since I was excited 😅

The program is represented as a list of blocks, which correspond to /*!re2c ... */ blocks and directives and the source code in-between. Each block may belong either to the main output file, or to the output header.

From my understanding, we need to wrap each /*!re2c ... */ block with (in C):

// initializers
while (1) {
    switch (current_label) {
    case ...:
        // code following the label
        // goto xxx;
        // becomes
        current_label = xxx;
        continue;
    }
}

In Rust, it would look something like this:

// initializers
'yyloop: loop {
    match current_label {
        label1 => {
            // body
            current_label = xxx;
            continue 'yyloop;
        },
        label2 => {
            // body
            current_label = xxx;
            continue 'yyloop;
        },
    }
}

In particular, the the code after each label needs to be wrapped in a block; each "label"/state has an associated "body". However, it's not so obvious to me that there's a distinction in re2c currently - as in, the code following a label is simply outputted without concern for the label it's under. I'm not sure if I'm making myself clear. But if so, how would you recommend approaching this?

Also, it seems to me that conceptually each start condition generates a DFA? In code.h, is it true that NLABEL corresponds to a label within a DFA/start condition, whereas SLABEL corresponds to the different DFAs/start conditions?

[skvadrik]

To be sure, this behaviour is exactly controlled by the == next in code_goto.cc?

Yes. You can pretend that == next condition is never satisfied by commenting out the cases that have it (temporarily). For Rust this particular function will not be used at all, since it generates if/else statements and we will probably not need them.

Does this mean you will be attempting a Rust backend, given examples? I.e. would you recommend attempting a Rust backend on my own, or would it be best to just provide more examples?

If I have some examples to start with, I can work on the Rust backend (this is something I wanted to do for a while, but kept delaying). But if you want to do it yourself, I can surely help. It's not easy --- you'll need to learn the codegen subsytem in re2c to understand its architecture, as it will most likely need some restructuring. It is also completely fine if you try and abandon it later, I can resume the work.

I started looking at implementing things since I was excited

\o/

The simplest thing to start with (as @pmetzger suggested) is to change the C backend to use the loop-switch approach that we will need for Rust. This is not necessary, but it's a good exercise and it will allow you to familiarize with the codebase and see if you want to work on it at all. You don't have to make loop-switch work for all the cases, just hack existing code enough to make some simple examples work.

The first thing for a Rust backend is still to have a few complete examples of lexers in Rust, just to know what code we will need to generate. Otherwise it may turn out later that we forgot about some crucial language feature that blocks all the previous work and requires major restructuring of the code.

In particular, the the code after each label needs to be wrapped in a block; each "label"/state has an associated "body". However, it's not so obvious to me that there's a distinction in re2c currently - as in, the code following a label is simply outputted without concern for the label it's under. I'm not sure if I'm making myself clear. But if so, how would you recommend approaching this?

There is a CodeBlock construct: https://github.com/skvadrik/re2c/blob/master/src/codegen/code.h#L248-L257. It can have different formatting options, including WRAPPED which is rendered as indented block wrapped in curly braces (this is what you need). For examples of usage see https://github.com/skvadrik/re2c/search?q=WRAPPED.

Also, it seems to me that conceptually each start condition generates a DFA?

Correct. The loop https://github.com/skvadrik/re2c/blob/master/src/codegen/gen_dfa.cc#L142 handles it. I recommend that you don't worry about conditions (-c flag) now, this is a more complex mode that can be handled later.

In code.h, is it true that NLABEL corresponds to a label within a DFA/start condition, whereas SLABEL corresponds to the different DFAs/start conditions?

As it is implemented now, yes: NLABEL is a DFA state label like yy3, yy12345 and SLABEL is some special label like a custom user-defined start label. More generally NLABEL is a numeric label, and SLABEL is a string label.