I want to ask if this is a correct approach to tokenizing shell arguments in Rust language. Previously, i did it through chars with a custom cursor, but i am not sure if that is what i should really do since a char type is a Unicode Scalar Value and the target Grammar needs only ASCII characters to tokenize (non ASCII chars are fine and just get pushed normally).
I want to know which way should i scan/tokenize, through &[u8] bytes or chars?
The Grammar works well enough with ASCII characters (and is fine with UTF-8 too, but doesn't need anything UTF-8ish), so i was wondering:
go with bytes &[u8] or String's chars for scanning?
is my buffer (Vec<u8>) the right approach or String with push(char) is?
since we take a &str as input, and tokenizer processes only onto ascii chars which are valid utf-8 characters, so given this invariant, should i use unsafe { String::from_utf8_unchecked() } to skip check since it would be guaranteed to be valid unless tokenizer code had a bug? Or keep it until i find a real performance issue? And hypothetically, lets say i do have one, would it then be recommended to use unsafe unchecked? Although a bug might appear in future code updates slightly that could potentially break the invariant.
Ah, i should have mentioned this: actually this is not really a shell tokenizer (although it follows some basic rules from POSIX) but general one which doesn't implement all of shell stuff. This helps if you're taking command-line arguments from another platform (like Discord, Telegram, etc.) to split arguments ready to be further parsed.
I guarantee UTF-8 since input source is &str, i am picking the design choice of keeping it UTF-8 only. No hassle of OsString or anything non UTF-8.
since now we know that it is a custom (self opinionated) tokenizer, i think error on invalid escape is approriate thing to do (although one can tell me if it isn't or any issues).
You should document what exactly escaping and splitting tokenizing means to your crate, and write tests to make sure it's working. It's hard to judge an algorithm implementation when the algorithm is unspecified, and hard to make confident modifications on top of that with no tests.
But I'll give it a go. Looks like you're breaking things up by ascii whitespace, but supporting escapes, single quotes, and double quotes (somewhat). You're also carrying a whole lot of supplemental information around. I think things would be cleaner if you refactored your methods to be per-state or per-token instead of (roughly) per-byte.
For example, as things are, your explicit state seems to be a stack consisting of either [Unquoted] or [Unquoted, *Quote]. Instead of storing this as part of a state machine, you could just use the call stack to hold your state: have a method which creates parsed tokens, which may call a couple other methods to append quoted spans. These methods only return when the quoted span is consumed (or due to errors). A lot of your other fields can also then be made implicit or method-local with this approach.
So my main advice can be summarized as: encapsulate states more in methods, and prefer making state data local to those methods when possible, instead of global fields in your state machine.
I also would advise switching to substring based processing, but that's basically a rewrite and not necessarily a very instructive review. So instead I decided to walk through making the state machine changes while sticking with your byte munching approach. It ended up quite long, so I'll put it in a collapsed section.
Expand to see a walkthrough of how your code could be reorganized
Preliminary note: I performed zero testing while writing this up, so there are likely some one-off errors and other bugs at some of the stages along the way (in fact I know there are). Just ignore those; I'm concentrating on the larger design.
I mentioned how your states are basically a stack. You also arguably already have a fourth state that you handle without storing a specific variant: Escape. You handle this one inline. Let's start out by encapsulating things a bit.
// in `handle_unquoted` and `handle_double_quote`
} else if byte == BACKSLASH {
self.handle_escape()?;
} else {
We could have handled this a different way: Add an explicit Escaped state, enter that state before calling the method, restore the current state after calling the method. We could have also tried to get the next byte first and had the possibility of being in this state in tokenize so that it would have to add the UnterminatedEscapeSequence error at the end-of-input, matching the other states. But the benefits of this design are that the state doesn't have to be explicit, the method handles its own end-of-input condition, and it also has all the information it needs locally (in contrast with dedicated fields in the state machine).
Let's work towards the other methods acting the same way: try to encapsulate our own error conditions, prefer local state over global state, and handle one larger "chunk" of work than a single byte (e.g. an entire quoted span).
We'll start by not calling next in the main tokenize loop, and letting each method handle the end-of-input condition for their state. Here's the result;tokenize is now quite trivial (I also moved the final flush_buffer into handle_unquoted). It probably doesn't seem like an improvement yet.
But let's pause to consider how your explicit states now work: we only enter the SingleQuote state in handle_unquoted. Then we return to tokenize, which immediately calls handle_single_quote in a loop until it resets to the state to Unquoted (or errors). And DoubleQuote works the same way.
If handle_unquoted called handle_*_quote in a loop instead, we don't even need the explicit state, similar to how handle_escaped works. Better yet, handle_*_quote can handle the loop themselves -- and now they really do handle (the entiretly of) their states. Here's an intermediate version. Our last changes now seem cleaner, because the logic of e.g. a single quote state is encapsulated in a single method: seach for the end quote, and if you don't find one before end-of-input, error.
state now never changes; we can get rid of it and State entirely. Another cleanup we can make is that the only time we read state_start_index is to create these UnterminatedQuote errors. But state_start_index is always set to self.cursor - 1 immediately before calling handle_*_quote. So we can instead just use self.cursor - 1 locally and get rid of that field, too. (This is also how handle_escaped already works.) And after that change, a lot of your if-else chains have single line bodies, and IMO work better as matches. Here's how things look after those cleanups.
handle_unquoted now stands out in that it still doesn't handle it's complete state. I'll come back to that, but first I want to make an aside about how you're handling empty tokens. In particular, I noticed that this assertion
assert!(!self.buffer.is_empty(), "buffer must not be empty");
fires on empty input, inputs like "''", leading whitespace, tailing whitespace, consecutive unquoted whitespace, etc. One possible change could be to just not create tokens in these cases, and another would be to have it be an error. However, I think '' resulting in an empty token is reasonable, so I'm going to forge ahead with that change-in-behavior.
Another thing to consider is what the spans of such tokens should be. I'd argue that they should be the entirety of the input that resulted in the token, so the single token from " '' " would have length two. I believe you already capture inner quotes in cases like "hi' there 'guy", anyway.
To make it explicit: let's have the start-of-token be the position of the first non-whitespace byte encountered when forming a token, and have the end-of-token be the position of the whitespace byte that terminates the token (or end-of-input). If the span is non-empty, we'll create a token, even if the token itself is empty.
With that decided, let's go back to making handle_unquoted more like the other methods. Since we need some per-token logic, let's have it handle the entirety of one token, instead of the entirety what used to be the Unquoted state (that's the entire run state). Our plan will be to:
Skip any leading whitespace, it's not part of our token span
If at end-of-string, return with no token
Record beginning of token
Loop until whitespace or end-of-string, which is our end of token
Create token
The last three bullets will be handle_unquoted, while the top part determines how long we loop in tokenize. That way, the beginning and end of token will be implicit in where the cursor is at the beginning and end of handle_unquoted, similar to the handle_*_quote error spans.
Here's an intermediate step. At this point, we only write to last_buffered_index and token_start_index, so we can get rid of them. Then append_to_buffer is a one-liner, so we can just inline that everywhere too. As you can see, we don't need the index from next most places any more either.
We're down to four global state machine fields. Two of them are buffer and tokens. buffer is always empty when we call handle_unquoted, then becomes a token we push into tokens at the end of handle_unquoted. That's also the only place tokens is modified.
So we can make these local state too, by creating and passing around buffer in the handle_unquoted call stack, and returning tokens to tokenizer for it to push into a local tokens vector. Here's what that looks like.
Finally, we can also change up the trim_start check by making a method wrapping handle_unquoted and returning an Option, like so:
What's the motivation here? Well, handle_token has the shape of an iterator, and now tokenize is basically performing a collect. So we might as well implement Iterator.
Then I did some final cleanups, actually called the function, fixed a one-off error, and here's the final playground of this walkthrough. (It's possible more errors remain as I only played with it trivially.)
impl Iterator for Tokenizer<'_> {
type Item = Result<TokenizedToken, TokenizerError>;
fn next(&mut self) -> Option<Self::Item> {
self.handle_token()
}
}
which has a pretty Rustic feel IMO. Aiming for an iterator shape can also be considered part of my advice.
How about processing substrings at a time instead of something as low level as bytes or chars? If we think about how the handle_* methods ended up in my walkthrough above, they are all basically:
Loop over bytes
Notable new state bytes? Call another method, continue loop
Notable end of state byte? Return successfully
Unnotable byte? Push to buffer
Handle end-of-input case
If you instead process in "notable byte separated slices", they become
For every prefix slicestr followed by a notable bytechar
push prefix string to buffer, then branch on the notable character:
Indicates new state? Call another method, continue loop
Indicates end of state? Return successfully
Unvisited str has no notable char before end-of-input; handle that case
Most your input is probably going to be unnotable, and you can handle large chunks of those substrings at once ().
To be honest, in my first attempt at a "review", I ended up following this idea (along with the "methods handle entire states" idea in the collapsed part above), but it basically just ended up being a rewrite and not an instructive review. At any rate, here's what that rewrite looks like. Ultimately it's not very different from where the collapsed walkthrough ended up.[1]
If you're going char by char or with substrings, push into a String.
If you're going byte by byte, I'd use Vec<u8> so you don't have to buffer bytes to create a char.
I'd avoid unsafe unless you know you really needed it. And if you really need it, better have plenty of tests.
It's a non-issue if your buffer is String from the start.
Now that I know the tokenizer is basically an iterator, it could be cleaned up to look more like the walkthrough, but I'm too lazy to bother right now. ↩︎
I do not know if my approach right, but there is shell arguments tokenization used for the Terminal. It uses a layering approach because an argument has several phases of extensions.
.
Unnotable byte? Push to buffer