4 ms·

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

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.
  - ridiculous_fish 6y ago
    > Computing the column/line pair would indeed be cheap on the Lexer Calculating line and column may be complicated if you're doing it for display. Perhaps the input has a flag emoji, with a variation selector, followed by a tab... So it makes sense to store the minimum you can and defer line/column calculation, especially if your parse is perf sensitive. One place this can go wrong is when you have to show a lot of source locations, e.g. you're printing a backtrace for a stack overflow in an interpreter. Here you can easily get into an N^2 situation. So you want to defer but also memoize.
    - estebank 6y ago
      For lines it is easy, you lex bare `\n` as a "token" and increment a counter, for columns you have to have a counter as well. You already have to account for Unicode codepoints to tokenize correctly. It is also true that there's a mismatch between displayed columns and the byte position for multibyte Unicode codepoints, but you also need to account for `\t` when doing so, which is plain old ASCII. Sadly this has to be a "best effort" action or you need to escape the output, otherwise you might get things like an underline shifted by the the difference between the anticipated visual width and the byte length, and this might change from under you when the underlying platform is updated. With all of that said, the approach taken in `rustc` is to have an arena of all `Span`s for everytokens and embed "pointers" (not actual pointers) to them. This is done because we embed `Span`s in everything in order to be able to give reasonable diagnostic messages.
      - remram 6y ago
        Codepoints do not match characters. You only need to deal with codepoints to tokenize, but to find the column you need to count characters, which require a unicode database. I think this is what the parent was referring to, though I suspect a lot of compilers simply ignore this issue.

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.
- ridiculous_fish 6y ago
  > Computing the column/line pair would indeed be cheap on the Lexer Calculating line and column may be complicated if you're doing it for display. Perhaps the input has a flag emoji, with a variation selector, followed by a tab... So it makes sense to store the minimum you can and defer line/column calculation, especially if your parse is perf sensitive. One place this can go wrong is when you have to show a lot of source locations, e.g. you're printing a backtrace for a stack overflow in an interpreter. Here you can easily get into an N^2 situation. So you want to defer but also memoize.
  - estebank 6y ago
    For lines it is easy, you lex bare `\n` as a "token" and increment a counter, for columns you have to have a counter as well. You already have to account for Unicode codepoints to tokenize correctly. It is also true that there's a mismatch between displayed columns and the byte position for multibyte Unicode codepoints, but you also need to account for `\t` when doing so, which is plain old ASCII. Sadly this has to be a "best effort" action or you need to escape the output, otherwise you might get things like an underline shifted by the the difference between the anticipated visual width and the byte length, and this might change from under you when the underlying platform is updated. With all of that said, the approach taken in `rustc` is to have an arena of all `Span`s for everytokens and embed "pointers" (not actual pointers) to them. This is done because we embed `Span`s in everything in order to be able to give reasonable diagnostic messages.
    - remram 6y ago
      Codepoints do not match characters. You only need to deal with codepoints to tokenize, but to find the column you need to count characters, which require a unicode database. I think this is what the parent was referring to, though I suspect a lot of compilers simply ignore this issue.