6 ms·

Tokenizers usually need to retain some information about where each token came from, like the range in the source. In C++ I might do it like this: struct

Tokenizers usually need to retain some information about where each token came from, like the range in the source. In C++ I might do it like this: struct token { string::iterator start; string::iterator end; }; and then the range in the original source can be recovered via: size_t offset = tok.start - src.begin(); What is the preferred way to do this in Rust? Is there something better than using indexes? Rust doesn't appear to have a way to say "give me the location of this &str in that &str" (even though it seems like it would be safe).

steveklabnik 6y ago
My understanding of rust-analyzer's internals are limited, but I believe https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/parser/src/parser.rs#L163 https://github.com/rust-analyzer/rust-analyzer/blob/master/c... is what it does here; that is, it keeps track of the start and ending positions as it goes https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/parser/src/parser.rs#L297 https://github.com/rust-analyzer/rust-analyzer/blob/master/c...
masklinn 6y ago
> What is the preferred way to do this in Rust? Is there something better than using indexes? I don't think so. > Rust doesn't appear to have a way to say "give me the location of this &str in that &str" (even though it seems like it would be safe). 'course there is: str::find (https://doc.rust-lang.org/std/primitive.str.html#method.find https://doc.rust-lang.org/std/primitive.str.html#method.find) It looks a bit abstract because it takes a Pattern rather than an `&str`, but a char, a slice of chars, an &str, or a predicate function, are all patterns.
- couchand 6y ago
  Presumably the parent wasn't asking about searching for one during slice in another, but rather locating the original offset of a string slice derived from another.
  - masklinn 6y ago
    Ah I see, I'd misunderstood. But there's no guarantee that two &str have any sort of overlap, that relationship is not conserved by the language, so it either would be unsafe or would be failible, it'd basically be pointer-twiddling.
- ridiculous_fish 6y ago
  str::find performs a substring search, which is incorrect if the same token appears more than once. What I want is the literal offset of a string slice in another, aka pointer arithmetic in C: fn derp() -> usize { let src = "xxxxxxx"; let tok = &src[3..4]; let offset = tok.as_ptr() - src.as_ptr(); offset // should be 3 } this should be doable safely; I think it's just an annoying hole in the API.
  - steveklabnik 6y ago
    cast both of those as_ptr()s to usize and this does what you want.
    - defen 6y ago
      I know it's just an example, but in case anyone tries to grab the code - it's worth noting that this will panic if you try to slice into the middle of a UTF-8 sequence, and will give byte offsets and not char offsets, so it might not give the answer you expect if src contains multibyte chars before tok. Also I'm fairly new to Rust so it's possible there's some other way to do it that I just don't know about.
  - masklinn 6y ago
    > What I want is the literal offset of a string slice in another, aka pointer arithmetic in C: I see, I'd misunderstood the original, sorry. > this should be doable safely The language doesn't know that there's any relationship between those two strings, so the method would probably need to be fallible, and be more convoluted than this.
- conradludgate 6y ago
  I think the point is to have a free method of doing so. Since a &str is a pointer and length, it contains all the information already of where it is inside the parent &str. This also covers the case of when the same token is repeated in the text. src = `let abc = "abc"` token = src[4..7] The 4 and 7 right there are the values we want. And if a str is a pointer and length, then those values should be retrievable with simple arithmetic, rather than a string search The only issue is if the str isn't a substring. The signature would need to be either `fn location(&self, &child) -> Option<(usize, usize)>` or `unsafe fn location_unchecked(&self, &child) -> (usize, usize) `
remram 6y ago
You should keep track of it in the way you want to present it, which in this case is probably the line and column numbers. I don't think it's much different in C++ and Rust.
- ridiculous_fish 6y ago
  Calculating line and column is expensive (think tabs and wcwidth) so it's better to defer that until you actually need it. Plus there are often very many tokens, so you want the size to be as small as possible. One common trick in C++ is to make source locations just a pointer. This gives you access to the token's contents (just dereference it), but you can also figure out which source buffer it came from, and where in that file, by comparing pointers.
  - remram 6y ago
    The size doesn't matter if you're using an iterator and throwing the tokens away, only storing/presenting them if there's an error. Computing the position might have some overhead, but it's probably better than going over the whole file from the top when you want to turn that pointer into line/column numbers. As for the content, in Rust this would be in your token structure (or rather in Rust your Token::StringLiteral enum variant), storing start/end pointers for each token seems weird to me. [edit: Rustc uses byte indexes though, so my intuition might have missed something important for the design of larger compilers: https://github.com/rust-lang/rust/blob/7bdb5dee7bac15458b10b148e9e24968e633053e/compiler/rustc_span/src/lib.rs#L285-L291 https://github.com/rust-lang/rust/blob/7bdb5dee7bac15458b10b...]
    - estebank 6y ago
      Computing the column/line pair would indeed be cheap on the Lexer as you could keep track of newlines easily. As for the token themselves, they (or at least their position/Span) will be used beyond parsing. Otherwise you won't be able to point at the right place when you have a type error, for example.
      - 6y ago
couchand 6y ago
> Rust doesn't appear to have a way to say "give me the location of this &str in that &str" (even though it seems like it would be safe). That's a fantastic idea. It seems like it would be not just safe, but quite efficient, too. fn offset_of(parent: &str, child: &str) -> Option<usize> { let cp = child.as_ptr(); let pp = parent.as_ptr(); if pp <= cp && cp <= pp + parent.len() { Some(cp as usize - pp as usize) } else { None } } (Edit: as can be expected, my hastily-thrown-together example code has several bugs in it. I think there's an off-by-one error in the ending condition, and I'm really not sure if it handles multi-byte characters properly.)
- estebank 6y ago
  You could do that, with the caveat that a lot of tokens won't be &strs, like numeric literals, so you will need an alternative way of keeping positions/Spans into the source code for those.
  - couchand 6y ago
    Well, if your tokenizer returns `impl Iterator<Item=&str>` (as in the OP), every token will in fact be a &str... In any case, this scheme is pretty limited, since you probably want other info in your token span like line numbers.
    - estebank 6y ago
      In `rustc` we keep `Span`s, which are byte offsets for start and end. We only compute line and columns when about to display diagnostics, not before, and at that we also account for "non-1-byte-to-1-col" chars (some are 0-visible-width, many other are 2 cols wide, and tabs are normalized to 4 cols wide, we need the normalization for accurate underlines). This reduces memory utilization (you don't store line/cols you will likely not need) and computation (you don't compute the line/cols you won't need). Both of these costs are actually quite low, but we also have a ton of `Span`s.
brundolf 6y ago
Where my mind personally goes is to return a Token struct on each iteration instead of a &str. This can still have the same lifetime guarantees, though: struct Token<'a> { s: &'a str, start_index: usize, } I believe you can get the len() of a &str, so you could just store the start index and derive the end index.
saagarjha 6y ago
Sounds like a solid case to use std::string_view.

steveklabnik 6y ago

My understanding of rust-analyzer's internals are limited, but I believe https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/parser/src/parser.rs#L163 https://github.com/rust-analyzer/rust-analyzer/blob/master/c... is what it does here; that is, it keeps track of the start and ending positions as it goes https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/parser/src/parser.rs#L297 https://github.com/rust-analyzer/rust-analyzer/blob/master/c...

masklinn 6y ago

> What is the preferred way to do this in Rust? Is there something better than using indexes? I don't think so. > Rust doesn't appear to have a way to say "give me the location of this &str in that &str" (even though it seems like it would be safe). 'course there is: str::find (https://doc.rust-lang.org/std/primitive.str.html#method.find https://doc.rust-lang.org/std/primitive.str.html#method.find) It looks a bit abstract because it takes a Pattern rather than an `&str`, but a char, a slice of chars, an &str, or a predicate function, are all patterns.

couchand 6y ago
Presumably the parent wasn't asking about searching for one during slice in another, but rather locating the original offset of a string slice derived from another.
- masklinn 6y ago
  Ah I see, I'd misunderstood. But there's no guarantee that two &str have any sort of overlap, that relationship is not conserved by the language, so it either would be unsafe or would be failible, it'd basically be pointer-twiddling.
ridiculous_fish 6y ago
str::find performs a substring search, which is incorrect if the same token appears more than once. What I want is the literal offset of a string slice in another, aka pointer arithmetic in C: fn derp() -> usize { let src = "xxxxxxx"; let tok = &src[3..4]; let offset = tok.as_ptr() - src.as_ptr(); offset // should be 3 } this should be doable safely; I think it's just an annoying hole in the API.
- steveklabnik 6y ago
  cast both of those as_ptr()s to usize and this does what you want.
  - defen 6y ago
    I know it's just an example, but in case anyone tries to grab the code - it's worth noting that this will panic if you try to slice into the middle of a UTF-8 sequence, and will give byte offsets and not char offsets, so it might not give the answer you expect if src contains multibyte chars before tok. Also I'm fairly new to Rust so it's possible there's some other way to do it that I just don't know about.
- masklinn 6y ago
  > What I want is the literal offset of a string slice in another, aka pointer arithmetic in C: I see, I'd misunderstood the original, sorry. > this should be doable safely The language doesn't know that there's any relationship between those two strings, so the method would probably need to be fallible, and be more convoluted than this.
conradludgate 6y ago
I think the point is to have a free method of doing so. Since a &str is a pointer and length, it contains all the information already of where it is inside the parent &str. This also covers the case of when the same token is repeated in the text. src = `let abc = "abc"` token = src[4..7] The 4 and 7 right there are the values we want. And if a str is a pointer and length, then those values should be retrievable with simple arithmetic, rather than a string search The only issue is if the str isn't a substring. The signature would need to be either `fn location(&self, &child) -> Option<(usize, usize)>` or `unsafe fn location_unchecked(&self, &child) -> (usize, usize) `

remram 6y ago

You should keep track of it in the way you want to present it, which in this case is probably the line and column numbers. I don't think it's much different in C++ and Rust.

ridiculous_fish 6y ago
Calculating line and column is expensive (think tabs and wcwidth) so it's better to defer that until you actually need it. Plus there are often very many tokens, so you want the size to be as small as possible. One common trick in C++ is to make source locations just a pointer. This gives you access to the token's contents (just dereference it), but you can also figure out which source buffer it came from, and where in that file, by comparing pointers.
- remram 6y ago
  The size doesn't matter if you're using an iterator and throwing the tokens away, only storing/presenting them if there's an error. Computing the position might have some overhead, but it's probably better than going over the whole file from the top when you want to turn that pointer into line/column numbers. As for the content, in Rust this would be in your token structure (or rather in Rust your Token::StringLiteral enum variant), storing start/end pointers for each token seems weird to me. [edit: Rustc uses byte indexes though, so my intuition might have missed something important for the design of larger compilers: https://github.com/rust-lang/rust/blob/7bdb5dee7bac15458b10b148e9e24968e633053e/compiler/rustc_span/src/lib.rs#L285-L291 https://github.com/rust-lang/rust/blob/7bdb5dee7bac15458b10b...]
  - estebank 6y ago
    Computing the column/line pair would indeed be cheap on the Lexer as you could keep track of newlines easily. As for the token themselves, they (or at least their position/Span) will be used beyond parsing. Otherwise you won't be able to point at the right place when you have a type error, for example.
    - 6y ago

couchand 6y ago

> Rust doesn't appear to have a way to say "give me the location of this &str in that &str" (even though it seems like it would be safe). That's a fantastic idea. It seems like it would be not just safe, but quite efficient, too. fn offset_of(parent: &str, child: &str) -> Option<usize> { let cp = child.as_ptr(); let pp = parent.as_ptr(); if pp <= cp && cp <= pp + parent.len() { Some(cp as usize - pp as usize) } else { None } } (Edit: as can be expected, my hastily-thrown-together example code has several bugs in it. I think there's an off-by-one error in the ending condition, and I'm really not sure if it handles multi-byte characters properly.)

estebank 6y ago
You could do that, with the caveat that a lot of tokens won't be &strs, like numeric literals, so you will need an alternative way of keeping positions/Spans into the source code for those.
- couchand 6y ago
  Well, if your tokenizer returns `impl Iterator<Item=&str>` (as in the OP), every token will in fact be a &str... In any case, this scheme is pretty limited, since you probably want other info in your token span like line numbers.
  - estebank 6y ago
    In `rustc` we keep `Span`s, which are byte offsets for start and end. We only compute line and columns when about to display diagnostics, not before, and at that we also account for "non-1-byte-to-1-col" chars (some are 0-visible-width, many other are 2 cols wide, and tabs are normalized to 4 cols wide, we need the normalization for accurate underlines). This reduces memory utilization (you don't store line/cols you will likely not need) and computation (you don't compute the line/cols you won't need). Both of these costs are actually quite low, but we also have a ton of `Span`s.

brundolf 6y ago

Where my mind personally goes is to return a Token struct on each iteration instead of a &str. This can still have the same lifetime guarantees, though: struct Token<'a> { s: &'a str, start_index: usize, } I believe you can get the len() of a &str, so you could just store the start index and derive the end index.

saagarjha 6y ago

Sounds like a solid case to use std::string_view.