1. 20

  2. 4

    When I’ve needed to implement a graph in Rust, I used an adjacency list. It worked pretty well, is there something that people find unidiomatic about it?

    1. 2

      Could you give an example? I know what an adjacency list looks like structurally, but I can’t imagine what an actual implementation of one in Rust would like like (e.g. to describe a tree).

      1. 2

        I think whether you use an adjacency list or not is orthogonal to the pattern described in the OP. For example, the petgraph crate uses indices but also an adjacency list representation.

        1. 1

          When I took English writing courses in school, any adjectives like these would get a big red mark and a “Stop trying to make it sound smarter than it is.”

          These are some implementations of tree and graph-like structures, that’s all. An adjacency list is as good as a whatever-the-hell else you like.

          1. 7

            I don’t think this response was very warranted; it seemed like a fine question to ask. English writing classes and technology discussion are quite different, and I think particularly with a still-fairly-new language like Rust, asking about idioms is a pretty smart thing to do.

        2. 4

          This approach with indexes into a Vec is no doubt fast enough and simplifies many memory issues:

          • The Vec gives us some control over heap fragmentation.

          • The use of indexes instead of pointers means that as the arena is resized, we don’t find ourselves running around rewriting pointers across the whole thing.

          However, what if I want honest-to-God pointers into a write-once arena? This actually seems really hard to do, even though we more or less have the constraint that the life of the pointer can be tied to the life of the structure.

          1. 3

            Maybe I’m missing something, and I haven’t written nearly as much Rust as I’d like to have (burn out and all that), but isn’t this straightforward? The arena is just Vec, and there aren’t any mutable references to it, then can’t you take as many immutable references into the Vec as you want (like you mentioned, as long as the references are tied to the lifetime of the Vec).

            I remember there being issues around borrowing elements from vectors, but I believe that was doing mutable borrows and it needing to borrow the entire Vec, not just the element.

            1. 3

              I think what you said is accurate assuming you’re just allocating everything you need up front. But usually the point of an arena is to get really fast allocation while possibly giving up memory efficiency. So if you loan out a borrow to something inside a vec, then you can’t naively expand that vec with new allocations because that requires mutable access and there’s an immutable borrow out for one of its elements.

              In my sibling comment, I linked to an implementation of an area that uses a bit of unsafe. The key safety principles are these two points (roughly taken from the comment in the code):

              1. The arena never gives out a mutable borrow to the same element more than once.
              2. The arena is careful not to let its internal Vec grow itself, since that would invalidate any existing borrows. In order to expand, it instead uses a Vec<Vec<...>>, where all of the interior Vecs remain the same size as when they were created.

              (This is kind of a dubious use of the Vec API, since I’m not sure we’ve actually guaranteed this behavior at the API level—namely that we won’t go doing unpredictably crazy things that muck with the stability of pointers into a vec—but I expect we couldn’t get away with changing it at this point. I think the original implementation of arenas that was in rustc itself didn’t use Vec, but it required more unsafe code.)

            2. 2

              This can be done and is actually available on crates.io. It does use a bit of unsafe internally but is otherwise reasonably simple. The code is here: https://github.com/SimonSapin/rust-typed-arena/blob/master/src/lib.rs