# RFC - compiler refactoring - spans **URL:** \ **Category:** internals\ **Created:** [January 18, 2015, 10:15pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357 "2015-01-18T22:15:39Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [January 18, 2015, 10:15pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/1 "2015-01-18T22:15:39Z")
(I mean RFC literally, I would like comments, rather than this adheres to our RFC format or that it will end up in the RFC process). I would like to refactor the way that the compiler stores spans, in particular I would like to move spans out of the AST and in to a side table. I’m not sure if that is the best plan, but I do think we need to do something. ## Motivation Which nodes in the AST have spans is ad hoc - we basically have them where we need them for errors in the compiler. In the near future I hope more tools than just the compiler will use libsyntax and its AST and span info. Different tools will require different nodes to have spans and storing spans for everything is wasteful of memory in the common case of plain old compilation. Spans pollute the AST. Syntax extensions and other tools which manipulate the AST have to deal with spans on AST nodes where they really shouldn’t have to. ## Proposal Remove all spans from the AST. Keep a hashtable mapping raw pointers to spans. Use the address of an AST node, to look up its span in the hashtable. (This will involve a bunch of casting to raw pointers, because there is no Node type for nodes in the AST, using ‘node’ in the loosest sense here, not any particulat Rust type. I.e., we want spans for idents, paths, expressions, items, and so forth). I think using AST pointers as indices in to the hashtable is OK, because due to the ownership structure of our AST, an address will never be reused for another AST node. So we can use addresses for lookups even after the node itself has been deleted. Question: how can we make this work for idents and things which are stored by value in the AST? Question where is the best place to store a pointer to this hashtable in the compiler? In each of the various contexts? TLS? ## Disadvantages Finding a span for a node becomes a bit more code. I think this is a worthwhile trade-off since we don’t do it _that_ often. Macro expansion will have to be more careful to make sure all spans for expanded nodes are computed properly. Having the span in the node means the compiler enforces that expansion at least does something with the span. With the spans in a side table, they could just be forgotten. Is there a better way to do this? ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [January 20, 2015, 2:57am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/2 "2015-01-20T02:57:05Z")
I don’t have a concrete opinion and haven’t looked at libsyntax well enough to have one, but I am curious if you have experience with how other compilers with reusable syntax libraries do this same thing? Like perhaps, how does clang deal with this concern? ---
**Author:** ![sanxiyn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sanxiyn/32/8824_2.png) [@sanxiyn](https://internals.rust-lang.org/u/sanxiyn)\ **Post date:** [January 20, 2015, 6:05am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/3 "2015-01-20T06:05:31Z")
If you haven’t already, [Clang AST documentation](http://clang.llvm.org/docs/IntroductionToTheClangAST.html) is worth reading. @ahmedcharles, current libsyntax design is largely similar to Clang’s. Primary difference is Clang uses locations instead of spans. Clang stores locations directly in AST, and deals with memory issue by careful encoding. (Even ignoring span vs location design below, our spans are larger than Clang’s.) Spans (called ranges in Clang) are constructed on demand from locations. For example, `a.x` would store 6 offsets in a span based system, compared to 4 offsets in a location based system. ```rust Field( Path(a, Span(0, 1)), Ident(x, Span(2, 3)), Span(0, 3)) ``` ```rust Field( Path(a, Loc(0), Loc(1)), Ident(x, Loc(2), Loc(3))) ``` In a location based system, spans for fields are constructed on demand like the following: ```rust impl Field { fn span(&self) -> Span { Span(self.path.start, self.ident.end) } } ``` ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [January 20, 2015, 7:38am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/4 "2015-01-20T07:38:20Z")
Thanks for the info, though to clarify, my question was more along the lines of: What design guidelines do the clang devs use to determine when to add location support for something? If it’s expensive to keep this information around when it’s not used, then clang is unlikely to keep all of it around. ---
**Author:** ![sanxiyn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sanxiyn/32/8824_2.png) [@sanxiyn](https://internals.rust-lang.org/u/sanxiyn)\ **Post date:** [January 20, 2015, 8:43am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/5 "2015-01-20T08:43:20Z")
Ah I see. Clang always keeps locations, period. It is not free, but they try very, very hard to make it not expensive. Since parsing is so fast (parsing entire rustc crate takes less than 0.3 seconds) the cost is primarily memory. Whether we go for optional locations or not, we probably should copy some of tricks to keep locations not expensive from Clang. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [January 21, 2015, 10:31am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/6 "2015-01-21T10:31:21Z")
I’ll need to take a look at the span system in the near future too because we need to store span information to crate metadata in order to allow for proper debuginfo for cross-crate generics. Are you sure that memory addresses are never re-used for AST nodes? I was under the impression that folding over the AST multiple times could cause addresses being re-used–but maybe something has changed in libsyntax since I last took a closer look at it. I’d be OK with putting spans in a sidetable but I definitely would want the key into this table to be something stable that can be serialized to metadata. The current `ast::NodeId` seems like a good candidate. But that would mean adding a `NodeId` to everything that can have a span. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [January 21, 2015, 11:59am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/7 "2015-01-21T11:59:51Z")
While I agree that getting spans out of the AST seems like a good idea, and a sidetable seems reasonable, using raw pointers from the AST doesn’t seem like a very good idea – for one thing, the information will get lost during folding! The same is true for indices, unfortunately. This certainly requires some thought. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [January 21, 2015, 1:32pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/8 "2015-01-21T13:32:34Z")
Do we have any data on how much memory spans actually take up? It seems to me that putting things into side tables always makes it easy for them to go out of sync. Having spans on everything, directly in the AST, might make handling them correctly much easier – and it might not be that wasteful when looking at the big picture. ---
**Author:** ![sanxiyn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sanxiyn/32/8824_2.png) [@sanxiyn](https://internals.rust-lang.org/u/sanxiyn)\ **Post date:** [January 21, 2015, 1:59pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/9 "2015-01-21T13:59:28Z")
> Do we have any data on how much memory spans actually take up? @huon did the exercise in July 2014 ([#15594](https://github.com/rust-lang/rust/issues/15594)). Spans took up 12% of maximum resident memory in entire compilation for a synthetic benchmark. This probably is worth doing again in a little more rigorous manner. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [January 24, 2015, 10:16am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/10 "2015-01-24T10:16:21Z")
Thanks for the link @sanxiyn. I’ve tried to collect some more data (which I posted [there](https://github.com/rust-lang/rust/issues/15594#issuecomment-71033243)). ---
**Author:** ![Ericson2314](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ericson2314/32/246_2.png) [@Ericson2314](https://internals.rust-lang.org/u/Ericson2314)\ **Post date:** [January 24, 2015, 9:07pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/11 "2015-01-24T21:07:49Z")
Not to be broken record, but with a polymorphic IR/AST, plugins that ignore spans are guaranteed via parametricity not to mess with them by mistake. This seems much cleaner than a side table to me. ---
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [March 2, 2015, 9:37pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/12 "2015-03-02T21:37:09Z")
It seems from the comments that a side table is a bad idea. I see more and more reasons to want more spans though. So, it seems to me that the way forward is to have spans for each node in the AST and optimise the way we store spans. This could also be a good opportunity to improve the AST. ## Proposal for the AST Every node in the AST would be a ```rust struct AstNode { node: T, span: Span, } ``` Perhaps we should add an `id: NodeId` field too, since it might be nice for every node to have an id. This is very close to the existing `Spanned` struct. The only real difference with this proposal is that it is more uniform - every node is an `AstNode` (even lead nodes in idents, etc.) and there are no nodes which have a span anywhere except in an `AstNode`. The formal type parameter would be `Item` or `Expr`, etc., the same nodes as we have today. This has the advantage that we can convert the AST gradually, rather than in one enormous refactoring. ## Optimising spans In order to make this not use a tonne more memory, we need to optimise our spans. If we have spans for every node then I believe there are some interesting optimisations we can do. Currently a span in 12 bytes, which with padding is most likely to be 16 bytes in most uses. (Three u32s - a start and end location (index into the codemap) and an expansion id, which indexes into an expansion table for storing information about macro expansion). I propose making a span a trait (or its implementation a trait) with implementations `LeafSpan`, `InnerSpan`, and `ZeroSpan`. Leaf spans would store a start location (u32) and an offset (u16). Since these are leaf nodes, it is very unlikely the length of the span would overflow a u16 (we should of course check this at runtime). However, this is only useful if we can get away with a u16 expansion id (see discussion of this below), otherwise, this is still likely to get padded up to 16 bytes in most cases. If we can get away with u16 expansion ids, then we get 8 bytes with padding. `InnerSpan`s are used for internal nodes of the AST. These are represented as two u16 offsets from the child nodes, plus the expansion id, so always 8 bytes. E.g., an inner node with three child leaf nodes (they could of course also be inner nodes in real life) ```rust inner ::= 'foo' child1 ':' child2 child3 ';' foo a: bar b; - --- - child spans ------------- inner spans ``` The child spans are represented as (4, 1), (7, 3), (11, 1). The inner span is stored as a negative offset from the start of the first child span and a positive offset from the end of the last child span, in this case -4 and 1. `ZeroSpan` is an optimisation of `InnerSpan` where both offsets are 0, this is common enough to be useful, for example in paths. These spans are just the size of the expansion id. Finally, we might choose to support the current optimisation of eliding some spans by having a zero sized `NoSpan` implementation. This would allow us to ensure that we didn’t ever use unnecessary memory on spans, but make it much easier to add spans where they are needs (changing a generic parameter is much easier than changing the AST structure. (I would be against though, just mentioning that it is possible). This would require changing the `AstNode` struct to be generic in the kind of span. In order to avoid a bunch of type parameters all over the place, I propose having a system of macros and typedefs to create a type with no type parameters for each kind of AST node, e.g., `type ItemNode = AstNode;`. ### Expansion ids These are currently a u32 in each span. I don’t know enough about how these are used to know how exactly they can be optimised. I assume that simply reducing the id size to u16 is not practical since it might overflow (note that far from every span in a program has a useful expansion id, any span which is a direct reference to a span in the source has expansion id 0). We could use one bit of the id to denote whether it is a direct id, this only gets set once we get close to overflow, at which point we fall back to hashing the span (including the expansion id, which other than the ‘overflow’ bit continues to be incremented, so that we can distinguish spans with the same start and end points) and looking up the expansion id from a hashtable. Hopefully we hit \> 2^15 expansion ids rarely enough that this does not cause significant slowdown. It might also be good to avoid expansion ids completely in spans that can never be the result of macro expansion. I’m not sure if that is a worthwhile optimisation though. ---
**Author:** ![huon](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/huon/32/3698_2.png) [@huon](https://internals.rust-lang.org/u/huon)\ **Post date:** [March 3, 2015, 4:11am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/13 "2015-03-03T04:11:43Z")
At some point the past, we had more things be `Spanned`, but we (partially) moved away from it, for some reason that I cannot remember. > [@nrc](#): > > Leaf spans would store a start location (u32) and an offset (u16). Since these are leaf nodes, it is very unlikely the length of the span would overflow a u16 (we should of course check this at runtime). However, this is only useful if we can get away with a u16 expansion id (see discussion of this below), otherwise, this is still likely to get padded up to 16 bytes in most cases. If we can get away with u16 expansion ids, then we get 8 bytes with padding. I'm somewhat nervous about this... what's the strategy if the span does overflow? (e.g. `tables::normalization::{canonical_table, compatibility_table}` in `libunicode` are both more than 65kB of source, although I suppose that `ast::Expr` is probably considered internal, rather than a leaf?) > [@nrc](#): > > It might also be good to avoid expansion ids completely in spans that can never be the result of macro expansion. I'm not sure if that is a worthwhile optimisation though. I don't think there are any such spans, since a macro can expand to `mod foo { ... }` (which can contain any AST nodes, AFAICT) and hence set the expansion id of anything it contains. ---
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [March 3, 2015, 4:18am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/14 "2015-03-03T04:18:43Z")
Yeah, `expr` is certainly an internal node. Leaf nodes would be idents and literals, basically (perhaps a few other such things). The only thing I can think of that might break this is string literals - it seems possible to have a string literal longer than 2^16 bytes long. I’d be fairly happy just making that an error though. If that is not possible we could just make it a bad span of some kind - a span of that size is not really useful either for the compiler or most tools. Good to know about the expansion ids. I wonder if there is a completely different scheme we could use which would be more memory efficient? ---
**Author:** ![DanielKeep](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/danielkeep/32/1332_2.png) [@DanielKeep](https://internals.rust-lang.org/u/DanielKeep)\ **Post date:** [March 3, 2015, 7:20am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/15 "2015-03-03T07:20:47Z")
Quick thought: it seems to me that there will be far more “small” spans than large spans. Also, most source files will not be larger than a few megabytes, realistically. The largest single file in the Rust source code is ~717kB (`libunicode/tables.rs`). 5031 are less than 64kB, with 41 larger. So let’s say that by default, we use `u16` for the offset and length, with `u31` for the expansion ID. The LSB of the structure can be _unset_ to indicate that the `Span` is actually a `Box` (assuming at least even alignment), which contains full-size fields. That makes `Span` 64-bit in the AST nodes. Of course, the exact division of bits _should_ be derived from more comprehensive statistics. Ideally, there’d be an instrumented compiler dumping stats on the number of bits needed for each of those fields for all spans for, say, Servo and `rustc`, then divvy the storage up to minimise the number of spans that would need to be pushed out to the heap. ---
**Author:** ![llogiq](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/llogiq/32/13692_2.png) [@llogiq](https://internals.rust-lang.org/u/llogiq)\ **Post date:** [March 3, 2015, 9:00am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/16 "2015-03-03T09:00:25Z")
Another possible optimization: If the spans of two neighboring nodes join at one location — if we keep whitespace nodes, this could be the default — the end location would basically be duplicated. In this case, we could do away with the length altogether. However, this requires that each node knows its next neighbor. ---
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [March 3, 2015, 9:13am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/17 "2015-03-03T09:13:36Z")
Yeah, I considered optimisations based on knowing the parent or siblings, but that means adding a pointer to each node, so it seems like that would use more memory than it saves. We also don’t keep whitespace nodes (or comments, etc.). ---
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [March 3, 2015, 9:15am UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/18 "2015-03-03T09:15:53Z")
Bare in mind that the offsets are per crate, not per file (and items from other crates can be added into that codemap, and I think (not sure about this) can be used in spans), which could definitely put us over the 2^16 mark. Definitely worth doing some research to figure out the exact numbers to see if there is an opportunity here though. ---
**Author:** ![DanielKeep](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/danielkeep/32/1332_2.png) [@DanielKeep](https://internals.rust-lang.org/u/DanielKeep)\ **Post date:** [March 3, 2015, 1:25pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/19 "2015-03-03T13:25:49Z")
Some follow up stats: summing the byte sizes of the source files for the crates in `rustc` yields: ```nohighlight 680 driver 5,756 libflate 12,180 grammar 15,200 librustc_bitflags 19,245 libarena 20,963 libfmt_macros 28,899 liblog 29,039 rustbook 30,810 libgraphviz 49,305 librbml 51,781 libgetopts 66,328 librustc_privacy 73,581 libtest 73,734 libterm 83,186 liballoc 103,189 compiletest 103,865 librustc_llvm 121,622 librustc_driver 122,824 libcoretest 129,016 librand 132,838 librustc_back 173,439 libserialize 229,755 librustc_borrowck 242,461 liblibc 270,359 librustc_resolve 369,664 librustdoc 670,832 libcore 771,639 libunicode 819,990 libcollections 834,098 librustc_typeck 1,295,922 librustc_trans 1,375,285 libsyntax 2,072,684 librustc 2,191,542 libstd ``` Comparing that to bitsize of offset/length in terms of how many crates would be “covered” without having to go to heap spans: ```nohighlight u16: 11 / 34 (32%) u17: 20 / 34 (59%) u18: 24 / 34 (71%) u19: 26 / 34 (76%) u20: 30 / 34 (88%) u21: 33 / 34 (97%) u22: 34 / 34 (100%) ``` So `{ offset: u21, length: u21, exp_id: u21, not_heap: u1 }` would (at least for the first two) cover all but one crate in `rustc`. I don’t have servo, so I can’t check that. ---
**Author:** ![nrc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nrc/32/126_2.png) [@nrc](https://internals.rust-lang.org/u/nrc)\ **Post date:** [March 3, 2015, 11:19pm UTC](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/20 "2015-03-03T23:19:30Z")
Awesome, thanks for collecting that data! I think we need to build in a fair amount of leeway here, which suggests to me that offset does need to be u32 (or possibly u31/u30). I suspect we would get a far higher number of spans in the inline format by making the offset larger than the length. I like that your proposed scheme is simpler in that there is only one kind of span, although the amount of bit-twiddling that will be needed makes it a little more error prone. Whether it is more efficient probably depends on the number of `ZeroSpan` cases we hit under my scheme. It would be interesting to know how hight expansion ids get for each crate too. [Next page](https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357.md?page=2)