Question: A good idea to call line_col at every node?

[arjunguha]

This is really a question, and not an issue:

I am building an AST and want to store a source location at every node. The simplest approach is to store the result of
line_col. However, skimming the code suggests that this may not be a good idea. I believe each call to line_col may scan over every prior newline in the file:

grmtools/lrlex/src/lib/lexer.rs

Line 339 in 5d37c36

fn line_col(&self, span: Span) -> ((usize, usize), (usize, usize)) {

Is that accurate? If so, I suppose the smart approach is to store a Span, and only invoke line_col when I need to print a location.

[ltratt]

Hello Arjun :)

If so, I suppose the smart approach is to store a Span, and only invoke line_col when I need to print a location.

It depends a bit on your use case, but commonly "yes". If you only ever want to print line/column for a subset of spans and you rarely do so more than once for each Span, then calling line_col lazily is likely to pay off. Indeed, that's why Span exists: it's a more compact representation than the four usizes that line_col returns, on the expectation that most Spans are thrown away without being converted to line/columns. [At some point, I might even pack Span down into a single machine word, but I haven't had the need to descend to that level of micro-optimisation yet.]

There are probably some use cases where the cost of repeated line_col calls isn't worth it, but I expect they're fairly rare. Also, at least in theory, line_col should have a worst case of O(n) where n is the number of lines in the file, although the current implementation is actually O(2n). If that factor of 2 becomes a bottleneck, reducing it to genuinely O(n) won't be difficult.

[ltratt]

#229 partially addresses this (and it turns out I got the complexity wrong -- it was worse than I first realised!). I think, in general, line_col is now adequately fast. It could be further optimised, ever so slightly, but I think we're now firmly in the land of diminishing returns for this function. Hopefully it's fast enough to convince people that it's OK to use :)

[arjunguha]

Wow! Thanks! And yes, log time is perfectly fine for the kind of thing I'm doing. I am happy storing spans for the moment, but I look forward to using your patch. :)