Storing an Arena<AstNode<'_>> in a struct

[nic-hartley]

Hello! I'm trying to make something to the effect of:

struct SiteGenerator {
  arena: Arena<AstNode<'??>>,
  // ...
}

Cannot for the life of me figure out what the '?? should be, or lifetimes in return types, etc. (I tried adding a lifetime parameter, but predictably that didn't work; after all, the lifetime here isn't a parameter, it's the lifetime of the struct.) One option would be creating the arena externally and storing a &'a Arena<AstNode<'a>>, but that's... annoying? And I feel like there's a better way.

[rlidwka]

This should be a lifetime parameter of your struct (that's usual rust stuff):

struct SiteGenerator<'ast> {
  arena: Arena<AstNode<'ast>>,
  // ...
}

[nic-hartley]

I tried adding a lifetime parameter, but predictably that didn't work; after all, the lifetime here isn't a parameter, it's the lifetime of the struct.

Right, let me expand on that then. With 'ast as a lifetime parameter, how do you write a method like this?

fn parse_md(&self, contents: &str) -> &'?? AstNode<'ast> {
  parse_document(&self.arena, contents, &OPTIONS)
}

This is obviously very simplified from what I'm actually trying to write but the thing is, I'm trying to write something that returns an AstNode, and with a lifetime parameter that doesn't work. Because

the lifetime here isn't a parameter, it's the lifetime of the struct.

[rlidwka]

Can you show the actual code you're trying to write instead of individual code fragments?

As it is now, this would probably compile:

fn parse_md(&'ast self, contents: &str) -> &'ast AstNode<'ast> {}

[nic-hartley]

Unfortunately I can't easily show the actual code. It's not public (yet) and it's kinda weirdly interconnected.

That said, using &'ast self instead of &self everywhere does seem to work -- kinda surprised me, I thought lifetimes would conflict, but in retrospect it makes sense. A bit frustrating if this is the only way to store an Arena in a struct, though.

[nic-hartley]

Never mind, this does break how I thought it would -- just not in the toy example I started with. That said, I'm done messing around with this; I'll just pass in the Arena from outside and track it separately. In other use-cases it'd be a nightmare but here SiteGenerators are ephemeral and I can just do let a = Arena::new(); let sg = SiteGenerator::new(&a); and not have to worry about e.g. returning the SiteGenerator.

[kivikakk]

You certainly can store an Arena however you like, but I'm guessing the reason your non-example is breaking is because you're trying to store some state in the SiteGenerator which itself refers to something in the Arena. That then becomes a self-referential struct, which isn't generally possible in Rust (without e.g. pinning the struct); a move of the SiteGenerator would likewise move the Arena within it, which in turn would invalidate the member holding a reference to something in the Arena.

You could store the Arena in some higher-level struct, which SiteGenerators then refer to, but if the Arena's the only thing, might as well just do what you've decided on.

I'd suggest extracting your problematic case into something self-contained if you'd like help looking into it further, as diagnosing an unknown problem in an unknown construct is Hard.

[tvanderstad]

I experienced a similar challenge writing a markdown editor. I make an arena with:

let arena = Arena::new();

then I parse my document and get my root node with:

let root = comrak::parse_document(&arena, &text, &options);

but since root references arena, I can't store them in the same struct so I'm not sure how to preserve the result of parsing my document.

Ultimately, since my app is immediate mode, I just allocate a new arena re-parse the document every frame. Last I checked we could render a 750kb markdown document at 90fps and markdown parsing was not a significant portion of our CPU time. So, I'm not experiencing an issue, but the question makes sense to me 👍🏻

[kivikakk]

Mm, the question makes sense — it's just not possible to do with the data structures we're using (per #356 (reply in thread)), in particular:

you're trying to store some state in the SiteGenerator which itself refers to something in the Arena. That then becomes a self-referential struct […]; a move of the SiteGenerator would likewise move the Arena within it, which in turn would invalidate the member holding a reference to something in the Arena.

One neat library I've been using lately is Xot, whose DOM is unusual compared to most because it offers both write and parent node access — just like ours. Instead of using an arena tree with nodes that point directly into it like us, though, they use indextree, which means "node references" are really just numeric indices into the arena. To get a reference to the node's content, you pass the node reference into the arena.

The particularly neat part about this is that you can store node references anywhere, since they don't actually contain lifetime-bound references, not to mention no need for reference-counted RefCells.

I might have a go and see how amenable Comrak is to using this approach. :)

[tvanderstad]

Yeah, using numeric indices as references is my go-to way to take pointer safety into my own hands, so I'm open to that.

Maybe there's an alternative where comrak quickly re-parses a document if you're re-using the arena that you just used to parse that document? Kinda like how it's faster to check if a list is sorted than it is to sort it. Shouldn't require any API changes if possible.

[kivikakk]

So far it's not looking especially promising, perf-wise, but I'll try to finish it off and make sure I'm not missing anything obvious.

Maybe there's an alternative where comrak quickly re-parses a document if you're re-using the arena that you just used to parse that document?

Off the top of my head, there's no way to do this with the parser as it stands; the AST gets mutated a lot before it reaches its final form, so going through a second time you'd probably spend more effort trying to match it up to what you already have than actually just constructing things a second time. The separate block/inline stages and the difficulty of accurate sourcepos tracking also complicate this a lot.

Not to say there definitely isn't — it sounds like it might be worth exploring — but I'd be a little bit surprised if there was.

[tvanderstad]

Thanks for checking it out! Looks like from the release notes that comrak's 30% faster or so than when we started this conversation and I'm still having a fine time re-parsing files every frame or sometimes even multiple times a frame

[kivikakk]

Whee! I'm glad to hear it's working out good regardless/with the other improvements. Rising tide lifts all ships :)