I am building a API with a graph data structure inside. You can think
of the data structure like a piece of XML (actually, it serialises as
a piece of XML!). Mostly it's a tree, but with cross links which turn
it into a generalized graph. In the XML representation, URIs are used
to make the cross-links.
Now, I've been around the houses with representing this in rust. The
obvious way to represent this is as a graph data structure, but this
gets into lots of Rc
s and Box
es with Rust. This made the types
long and resulted in much fighting with the borrow checker. So, I
tried the alternative, when I add an URI to a graph, I swap the URI
for a usize
, which I can now copy around freely into multiple
places.
However, this causes it's own problem. URI is now a new type for a
usize
. So I have add to add quite substantial code for checking when I
add a subgraph that any URIs are already in the graph -- because they
could have come from another graph. In which case, I will get a
dangling usize
, unless I check.
More, comparing two graphs now becomes painful -- since the usize
that
represents each URI differs between graphs, I have to switch them all
back to String
to do the comparision.
So I have started to revisit my original design. What not make URI a
Rc<String>
? I can make a URICache which takes a String
and returns
a Rc<String>
. So I have tried this. I could even share the
URICache
between graphs. Except that I can't because that needs a
mutable reference, and rust's rules do not allow this.
To my question: should I be using usize
to represent URIs, accepting
the pain that goes with it? Or is the Rc<String>
approach more
sane. And if I do this, can I share a single cache between multiple
graphs. Or have I missed something else entirely?
As you might guess, this is my first Rust project. I'm enjoying many
parts of it, the docs, cargo and so forth. But the borrowing and
sharing rules are driving me a bit nuts.