Beginner: How to approach storing mutable references with a complicated AST structure

[regal bolt]

Goal: Parse SQL query with sqlparser and develop a library that allows you to change table / column names etc.

This is the structure that sqlparser gives:

query: SELECT a FROM tbl
[src/main.rs:27] ast = [
 Query(
  Query {
   with: None,
   body: Select(
    Select {
     // --- snip ---
     projection: [
      UnnamedExpr(
       Identifier(
        Ident {
         value: "a",
         quote_style: None,
        },
       ),
      ),
     ],
     into: None,
     from: [
      TableWithJoins {
       relation: Table {
        name: ObjectName(
         [
          Ident {
           value: "tbl",
           quote_style: None,
          },
         ],
        ),
        // --- snip ---
       },
       joins: [],
      },
     ],
     // --- snip ---
    },
   ),
    // --- snip ---
  },
 ),
]

I'm most interested in Ident and Table structs. What are my options to store the location / reference for later use, so that I can do something like mapper.change_table_name('tbl', 'new_tbl') without traversing the whole tree again.

I think my options are:

• Refcell / Rc, but as far as i know that would mean I'd have to recreate the whole ast again to get it to accept Refcell/Rc
• Store the position somehow, but I have no idea how to do this with more complicated structures like enums
• Traverse the whole ast every time something needs to be changed. I'd rather not do this as it gets tricky when I'm trying to keep count which column belongs to which table
• Is there already a library that allows something like this?

[quasi echo]

You need the tree to explicitly support this, so if sqlparser doesn't then you'll need to convert their tree into your own custom tree type.

At which point, you can use rc/refcell in your tree, or use the standard "arena" trick: Put every element of the tree inside some data structure, and then use indices/keys/handles instead of pointers.

For a simplified example:

use slotmap::{SlotMap, DefaultKey as Key};

struct Table {
  name: Key, //instead of directly storing an ident, store a key that can be used to get one
}
struct Ident {
  value: "tbl",
  quote_style: Option<?>, //dunno what this is, lol
}
struct QueryTree {
   tables: SlotMap<Key, Table>,
   idents: SlotMap<Key, Ident>,
}
```If you do this, you can simply store the same key in multiple places. You can technically use `Vec` and `usize` indices for this too, but it won't work well if you ever need to remove entries.

(To make this harder to misuse, you could use `new_key_type!` to create things like `TableKey`, `IdentKey`, and so on, that can't be used interchangeably)