0
\$\begingroup\$

I am working on a lexer in rust.
It has been through many different iterations, going from iterating over a Vec<char> to std::str::Chars to std::str::CharIndices,
from pushing chars onto a String to taking a slice of a &str.
i'm trying to speed up my implementations, so today i decided to ditch the Chars and instead have been experimenting with a &[u8] based approach.
The problem is, not all characters are ascii, and this makes indexing the &[u8] quite hard.
I've figured out a solution with u8::leading_ones but this still doesn't solve the problem of implementing take_while.
Right now it only works with ascii chars/u8s, but doesn't support unicode. The reason is, to check a predicate against a unicode char, i need to:

  1. get the character width using the leading ones of the first character
  2. take a slice of the &str
  3. ok, now what?

    The &str slice mentioned in step 2 can be implemented in take_while using &self.string[s..self.pos] however, this is still a &str and not a char.
    I could just get the character using .chars().next() however this seems too hacky and weird to me.
    The "WET" alternative would be to clone the code from take_while for every time i want to parse a token, and use a hacky approach when i actually want to check if a unicode character matches a predicate (e.g: parsing an identifier)
    Any ideas?
struct Cursor<'a> {
    bytes: &'a [u8],
    string: &'a str,
    pos: usize
}

impl<'a> Cursor<'a> {
    pub fn new(string: &'a str) -> Self {
        Self {
            bytes: string.as_bytes(),
            string,
            pos: 0
        }
    }

    pub fn next_char(&mut self) -> Option<&'a str> {
        let start = self.pos;
        if start >= self.string.len() {
            return None;
        }
        self.pos += self.bytes[start].leading_ones() as usize;
        if self.pos == start {
            self.pos += 1;
        }
        Some(&self.string[start..self.pos])
    }

    pub fn take(&mut self, amount: usize) -> Option<&'a str> {
        let start = self.pos;
        for _ in 0..amount {
            let s = self.pos;
            if self.pos >= self.string.len() {
                return None;
            }
            self.pos += self.bytes[self.pos].leading_ones() as usize;
            if self.pos == s {
                self.pos += 1;
            }
        }
        Some(&self.string[start..self.pos])
    }

    pub fn take_while<F: FnMut(u8) -> bool>(&mut self, mut pred: F) -> &'a str {
        let start = self.pos;
        loop {
            if self.pos >= self.string.len() - 1 {
                self.pos += 1;
                break
            }
            let s = self.pos;
            self.pos += self.bytes[self.pos].leading_ones() as usize;
            if self.pos == s {
                self.pos += 1;
                if !pred(self.bytes[self.pos]) {
                    break
                }
            }
        }
        &self.string[start..self.pos]
    }
}

fn main() {
    let mut cursor: Cursor<'_> = Cursor::new("123NowTheIntegerLiteralIsOver");
    println!("{}", cursor.take_while(|x| x.is_ascii_digit()));
}

(and yes, Cursor will impl Iterator in future, only in this case will yield &str or a possible Token type rather than char)

\$\endgroup\$
1
  • \$\begingroup\$ Note: Chars method is faster in release mode, but slice method is faster in debug \$\endgroup\$
    – xxxxxxxxxx
    Jan 7, 2023 at 21:45

1 Answer 1

1
\$\begingroup\$
struct Cursor<'a> {
    bytes: &'a [u8],
    string: &'a str,
    pos: usize
}

Having both bytes and string is redundant because they are both the same thing. In terms of memory layout &str and &[u8] are exactly the same. I think you do this so that you can slice the string:

&self.string[start..self.pos]

Both this doesn't do what you probably want. In particular, slicing a str does a runtime check for the validity of the slice indexes which rather defeats the purpose of operating at the u8 level. You probably want:

unsafe { std::str::from_utf8_unchecked(&self.bytes[start..self.pos]) }

This is unsafe because it is up to you to ensure the correctness of the slice indexes.

let s = self.pos;
self.pos += self.bytes[self.pos].leading_ones() as usize;
if self.pos == s {
    self.pos += 1;
}

I'd do:

self.pos += self.bytes[self.pos].leading_ones().max(1) as usize;

In general you can create a reusable function for moving forward in the stream:

fn move_forward(&mut self) -> bool {
    if self.pos >= self.string.len() {
        return false;
    }
    self.pos += self.bytes[self.pos].leading_ones().max(1) as usize;
    true
}

Then you can use it to get rid of most the repetition in your functions:

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.