I want to implement error messages that point out where in your source code a parse error or runtime error is. However, when I convert the token stream to my AST, I lose the information about the tokens' positions because of how I am structuring the tree nodes (nested Rust enums and structs). This makes it impossible to determine which token is causing a parse/evaluation error.
What methods are available to keeping track of source spans past the lexing phase?
My usual strategy for this is that every parse tree node holds on to the first token of the parse element from which it was constructed, and sometimes the last too. The initial token is definitely available at the point you begin parsing the syntactic element. This lets me identify at least the line and often the span of the syntax element in question; depending on the structure the tokens use I may be able to reconstruct the entire input source. I carry this over to any derived syntax tree nodes, so the token lifetime is the entire run of the program.
For structures where holding on to a reference to a token entity itself is infeasible, simply storing the index of the tokens into the stream is sufficient. You simply retain the token stream itself alongside. At the extreme, even a byte index is good enough if you still have access to the source text and can re-lex it. These values are cheap enough to add to any AST nodes, and definitely available at the time of parsing the tokens. Because errors are relatively rare, the cost of re-lexing (or even re-parsing!) is negligible.
In some cases, it may be cheaper to go in the other direction: if each token only produces to a single syntax tree node, the token can hold a reference to that node, and error reporting can walk the tokens to find the operative node. I'd expect this to be relatively uncommon, but a single-layer parse tree in Rust is one plausible case.
Error messages commonly only identify the line of the error; in this case, each node can also just hold on to the line number of one of the tokens contributing to it, and perhaps a character index, as integers. This is generally good enough for multi-line constructs, though it's not going to produce "good" error messages. This is a cheap option when the source will not be available at run time.
The final option is to have a separate collection of debug symbol information — either an array or dictionary in the runtime, or in a sidecar file — and save any relevant data indexed by a unique identifier for each syntax tree node. You may already have those identifiers, or can (re)construct them easily: even "the third if node in a pre-order depth-first traversal" is good enough as an identifier when it's for generating an error message, so you don't need to have any additional inline data within the nodes. The debug data can store byte or token indexes, or even the annotated source code itself: a text file of node identifier|source line pairs could do the job.
For a number of these options, a key aspect is that the token data is only used when reporting an error: this is a slow human-level operation anyway, so even doing extra processing all over again is cheap enough to be satisfactory. You can store the bare minimum information to reconstruct the lexical data for reporting, outside of the core loop of the system. In cases where it's hard to do, there's really no benefit in refactoring to achieve optimal performance for a rare and terminal case.
Have you considered ditching lexing altogether? It makes things significantly easier.
Using a lexerless parsing, e.g., PEG, you can simply embed location information into every AST node you're constructing, you can even do it implicitly to avoid writing any boilerplate code. Just store the location of the beginning and the end of the input stream that resulted in every given AST node.
More so, you can implicitly preserve this information through the further transforms from AST to various IRs. Only things like variable declaration locations, function arguments, etc. need special attention, and for expressions and statements you just implicitly copy the location data of the tree nodes when you rewrite them.
Of course, all the above is possible with a lexer too, just store the location data in every token. A bit less elegant, but still doable.
Source locations are typically represented to the user as a line and column number, but they don't need to be stored internally that way; it's faster to represent a source location as a simple index into the source string, and this only needs to be converted to a line and column number when there is an error to report.
If your compiler or interpreter loads multiple source files at once, then a source position can consist of an index and something indicating which source file; this could be a reference to the source file's path as a string, or a unique numerical ID assigned to that source file. Using numerical IDs is a good idea since they can take up less space than a reference to a string, and they avoid reference-counting operations that some host languages need for string objects. This matters because you're going to have a lot of source position values, so using a 64-bit reference instead of a 32-bit integer adds up fast. So a source span is then a struct with a source file ID, a start index, and an end index.
Then, you need to carry over the source span information from the tokens to the abstract syntax tree (AST). Each AST node will need a field for its span; you can either add this manually to each variant of your AST enum, or you can parameterise your AST to include a payload of some generic type T. (Parametrisation also allows you to change the payload as you transform the tree, e.g. to add type information to expressions.)
Finally, in the parser, in each place that you parse an AST node you want to hold onto the first and last tokens that represent that node, so that you can build the correct span for it. It's useful to have a helper method which merges two spans to make a new span covering the whole range between them.
