Need design help with object tree (well, DAG)

(background: I am trying to reimplement something I have a decent grasp on from earlier, (in a very different language), so it's not all vibes)

What I want to make is a graph of objects with references to other objects, because that's what makes sense when you're dealing with the actual objects, which is what I want to be the focus. (e.g. Bike -> Frame -> SeatPost ... )

The problem comes in when I have (potentially) conflicting design goals:

  • The object graph needs to be iterable as dyn T:s (ok)
  • Concrete object types can just have other objects. (ok)
  • Adding concrete object types should be possible without changing the core (so it can be in crate of its own) (ok)
  • I need to be able to tell if two objects are the same or not (?)
  • Concrete object type implementations should not have to worry too much about the graph implementation details. (not really ok rn, but possibly manageable)

Where I am now is using Rc<dyn T> to deal with the objects generically. This works, I have a topological sort iterator that is (while shockingly ugly) actually working. (afaict, anyway)

I've tried to read a bit about the problems of dyn reference pointer comparisons, but I don't feel much wiser.(*1) Do I need to have a trait method that returns a concrete type pointer, cast to * const (), or can it be done more elegantly? Is it even guaranteed to work?

A lot of the design issues I'm seeing seem to stem from the compiler's freedom to generate and/or merge vtable:s at will, rendering fat pointers nondeterministic.

In a similar vein, this can't be a default trait implementation, but it can be the same everywhere:

    fn as_any_rc(self: Rc<Self>) -> Rc<dyn Any> {
        self
    }

This is needed because I can't just (thing as Rc<dyn Any>) where I'd use that, because Tracking issue for dyn upcasting coercion #65991.

I could hide that in a derive macro, I guess, but it's starting to feel dodgy.

I'm all in favour of appeasing the Cosmic Horror of Compiler Chaos, because it gives us some very nice things, but the nihilism does seem to occasionally take away things I was hoping to use.

*1:

You might find @quinedot's Tour of dyn Trait useful.


You can use a helper trait with blanket implementation to make this work in the meantime. This approach can be extended to support full equality testing as well.

trait MyTrait: AsAnyRc {
    // whatever
}

trait AsAnyRc: 'static {
    fn as_any_rc(self: Rc<Self>) -> Rc<dyn Any>;
}

impl<T: MyTrait> AsAnyRc for T {
    fn as_any_rc(self: Rc<Self>) -> Rc<dyn Any> {
        self
    }
}
3 Likes

Newcomers to Rust are sometimes surprised this passes:

    let a = 0;
    let b = 0;
    assert_eq!(&a, &b);
    
    let a = Rc::new(a);
    let b = Rc::new(b);
    assert_eq!(a, b);

It passes because equality in Rust is generally defined in a value/semantic fashion. If that's what you want for your DAG, and a 'static constraint is ok, the approach in my repo will work.

Object identity is challenging in Rust generally, due to having zero-sized types, and not having everything-is-boxed or comparable vtables or RTTI-for-everything.[1] However, in the case where everything is an Rc, you can probably use ptr_eq for this purpose.

So if object identity is what you want, that may be a viable alternative (but see the caveat below).

OTOH since you're topologically sorting, perhaps you need something stronger than equality/identity anyway.


The reason is that every Rc is a separate non-zero-sized allocation in order to hold the counters along side the value, and that as of 1.72 ptr_eq ignores pointer metadata (like vtables).

Note that technically, however, it's not guaranteed. The layout is an implementation detail and technically Rc could switch to allocating the counters and values separately with ptr_eq comparing the latter, and thus reintroduce the barriers to complete object identity.

So you'll be pulling a Hyrum, assuming this isn't just a lack of explicitness in the documentation.


  1. "Challenging" as in I don't think there's a fully general solution. ↩ī¸Ž

1 Like

Well, so, the problem I (believe I) have, is that I want to ask if these references refer to the same object. The reason is that I want to be able to match two identical objects on one side with two identical objects on the other, one-to-one. (That is, e.g. (aA, bB) or (aB, bA), but never (aA, bA) with B orphaned).

I get that the compiler gets freaky with values in zero or more 'locations', and that's OK, but also, I have my problem.

So far, the objects are just objects and all I ask is that they can give me references to the objects they depend on. This makes the graph stuff the concern of the framework side, that cares about it, which is good. I have been toying with the idea of making a derive macro that handles some of these things, since there are other issues. Like, what if I need to change Rc for something else, idk, Arc? A whole X<Y<Z<Thing>>> totem pole? There's also the expectation that all object types will have some of the same fields, e.g. name.

I guess I could add a(n otherwise useless) serial number to the objects, but that feels icky somehow. I could make a struct Meta that's the first field in every struct? (The struct embedding style in Golang would be nice here, but that's minor.) Then I could have some facility for generating serial numbers in that, but then that would need to be passed around... And around and around we go.

I'm trying (successfully, so far) to avoid having some sort of mothership ("context", whatever) that needs to be present to do anything.

As for having a mothership, that would also make the graph easy, just use petgraph (or similar) and all objects have their child node references be (graph, index) and access be something rather involved hiding in the getter. It would also be, uh, unaesthetic. And it would put complexity on the object side instead of on the graph side.

An irony of this is that these objects are designed to be immutable and so ought to play well with the compiler trickery, but the identical-but-separate problem is a conundrum.

:thinking: It may be possible to require that objects, however unrelated in the dimension of implementer, must be constructed in a single phase, where a counter (or Meta factory, ig) gets passed around, but it still feels baroque compared to comparing pointers.

I could demand that everyone that has this identical-but-separate problem include their own nonce field, but that feels like a fine-print footgun.