How to model object dependency?

[yongkyuns]

Hi!

I'm trying to write a program to draw objects (e.g. rectangle, triangle, etc.) on screen.

The problem I have is accessing dependent information between objects. For example, I want to keep position data separate from the frame of reference (i.e. position of object A is relative to object B).

pub struct Rectangle{
    position: Point, // x, y relative position
    origin: Option<Point>, // Some other object's position
    // Some other properties
}

If the parent or origin moves, the said object will move with it, while keeping it's position data constant.

What would be an appropriate way to model this in Rust? I am currently using Rc<RefCell<Point>> as position and having Weak<RefCell<Point>> as origin to track another object's position.

pub struct Rectangle{
    position: Rc<RefCell<Point>>, // x, y relative position
    origin: Weak<RefCell<Point>>, // Some other object's position
    // Some other properties
}

In terms of ergonomics, this works okay for me after grouping position & origin into it's own struct, and defining type alias and trait methods to operate on it. However, if the level of dependency or interaction grows (e.g. keeping reference to entire parent object), I think this approach can get challenging.

I looked into using arena type approach, in which I will only keep the index of parent object. However, I struggle to access parent object from arena while having mutable borrow of current object. Am I misunderstanding how arena (e.g. generational-arena) is supposed to be used?

Modelling inter-object relationship and dependency has been quite challenging for me in Rust, so I would really like to figure this out.

Thank you for any help in advance!

[droundy]

Is there a reason not to have each shape just own a Vec of child shapes?

[droundy]

@yongkyuns

I looked into using arena type approach, in which I will only keep the index of parent object. However, I struggle to access parent object from arena while having mutable borrow of current object. Am I misunderstanding how arena (e.g. generational-arena) is supposed to be used?

When using an arena like that, you never want &mut of your objects, only of the arena. So rather then fn f(&mut Square) ... you have fn f(&mut Arena, square: SquareRef) ... where SquareRef would be an integer index.

[JosephOsborn]

How are these objects and their positions changed and used? Are they written sparsely each frame, are they all read every frame? Do you need full backreferences to support eg inverse kinematics, or could you store a vec of local positions and a parallel vec of frame-of-reference positions (with the latter updated whenever parents are moved)?

The intent behind this question is, do you absolutely need object dependency? It can be more trouble than it’s worth in terms of maintaining invariants and pointer chasing/memory indirection.

I think as a rule of thumb it’s worth avoiding backreferences (whether through indices into a vec or &-references) unless you have a highly random and sparse access pattern since you’ll spend more time reading from memory than doing useful processing. In eg 3D animation you might need to compute the position of every vertex, and much of the object is changing, so going forward from the roots and “mapping” from the animation data and model and transform to per vertex world space coordinates makes sense; but I could imagine other applications with other access patterns. One useful invariant here is “parents always appear before children in the vec”.

(Aside: Sometimes you need different logic for root and non root objects, so it might be worth either sorting all the roots to the beginning (topological sorts are awesome) or keeping two separate vecs.)

[yongkyuns]

@JosephOsborn

How are these objects and their positions changed and used? Are they written sparsely each frame, are they all read every frame? Do you need full backreferences to support eg inverse kinematics, or could you store a vec of local positions and a parallel vec of frame-of-reference positions (with the latter updated whenever parents are moved)?

I'm trying to write APIs that allow users to configure animations with them. After user-defined objects are instantiated and corresponding animation details are specified by user, an update loop will refresh drawing at each frame. At the moment I'm not sure if full back-reference will be necessary.

@droundy

Is there a reason not to have each shape just own a Vec of child shapes?

In your suggested approach @droundy and @JosephOsborn , would I pass any dependent information (in this case parent's position) down to child item for any child functions that need it, as shown below?

struct Square {
    position: Point,
    pub children: Vec<Square>,
}

impl Square {
    fn print_position(&self, origin: Point) {
        let global_position = origin + self.position;
        println!("{:?}", global_position);
    }
}

One reason I want to allow child ownership to remain unchanged regardless of establishing object dependency is because I want to allow user-generated object to retain ownership after defining dependency so they can still call more methods on it.

Also, if there is more than one such dependence (e.g. get child's origin from parent1, and get it's color from parent 2), how can I implement this functionality with this approach?

@droundy

When using an arena like that, you never want &mut of your objects, only of the arena. So rather then fn f(&mut Square) ... you have fn f(&mut Arena, square: SquareRef) ... where SquareRef would be an integer index.

Could you elaborate on this a little bit more? Here's how I tried to use it:

struct Square {
    pub position: Point,
    pub origin: Point,
    parent: Option<Index>,
}
fn main() {
    // Initialize objects and insert
    let mut arena = Arena::<Square>::new();
    let parent_idx = arena.insert(Square::new()); 
    let child_idx = arena.insert(Square::new()); 

    // To set the origin using parent's position
    let mut child = arena.get_mut(parent_idx).unwrap(); // Returns &mut Square
    let parent = arena.get(parent_idx).unwrap(); // this is the problem

    child.origin = parent.position.clone();
}

So if I only want to keep &mut to arena, how can I access methods of Square that need another Square to perform any operation and mutate it's existing states?

@JosephOsborn and @droundy Thank you for your kind replies and very helpful suggestions!

[droundy]

@yongkyuns

So if I only want to keep &mut to arena, how can I access methods of Square that need another Square to perform any operation and mutate it's existing states?

My point is to not create such methods. Instead create a corresponding method on the index type. If you like, you're pretending that the SquareIndex is the Square. It may be a little unfamiliar at first, and could involve extraneous lookups, but ultimately you're just treating your index as if it were a reference, which works fine. It helps to use the newtype pattern to create strongly typed indexes.

I'll also note that as I usually think of it, an arena is just a Vec, which works great as long as object deletion isn't important either because they aren't deleted or because they're small or because not too many are allocated.

[JosephOsborn]

@yongkyuns

I'm trying to write APIs that allow users to configure animations with them. After user-defined objects are instantiated and corresponding animation details are specified by user, an update loop will refresh drawing at each frame. At the moment I'm not sure if full back-reference will be necessary.

Thanks for the information about your use case. Am I right in thinking that the total number of objects being animated is likely to be fairly small, like 10-100 UI elements?

I think the trick might be that the API and data structures used to configure animations is not necessarily the same as the ones used to execute animations. It sounds like since components can inherit different properties from different parents, you’re not defining a tree but a number of trees or a labeled directed acyclic graph. So any approach based on structs owning data will have some friction.

One possible design supporting canceling and composing animations, just an idea

You can get around it using Rc or RefCell but I think it might be cleaner to use an API where you use something like an AnimationBuilder struct that can give you opaque identifiers to objects, and you can call anim.set(time, identifier, propertyvalue) or anim.inherit(child_id, parent_id, property) (ensuring that parent_id precedes child_id). That also gives you a nice way to describe different interpolations or synchronize the animations of two objects. Internally AnimationBuilder could store a vec of (f32, BTreeMap<Identifier, PropertyValue>) and a vec of inheritance records with either forward or backward links.

Once it’s all configured, you could call something like let animation = anim.build() to consume the animation builder and create a tickable animation structure, which could have a function like animation.tick(dt: f32, initial: &[Animatable], animated:&mut [Animatable]) if initial has an order compatible with the animation’s identifier tree and animated is at first a clone of initial. Then you can target the animation to any collection of animatable objects, and as the animation ticks the animated proxies are updated. The internal animation data could be the same vec of BTreeMaps from before, or some more optimized representation (e.g. turning backlinks into forward links, or separating animation tracks for different properties); tick could iterate through just the objects and properties that changed, or iterate through all objects and compute their properties.

This only needs forward propagation—when we calculate world position for object k, we also update inherited position data for inheritors of k’s position, which are guaranteed to be later in the animated vec. It also means you can cancel and compose animations.

If you really want to be able to treat the objects being animated as if they were the animation data too with all its non-tree-shaped ownership, you’ll probably need to use internal mutability somehow and be prepared for runtime panics if users mistakenly produce a cycle.

[droundy]

@yongkyuns

@droundy

Is there a reason not to have each shape just own a Vec of child shapes?

In your suggested approach @droundy and @JosephOsborn , would I pass any dependent information (in this case parent's position) down to child item for any child functions that need it, as shown below?

Yes, but I'd tend to give the information passed down a descriptive type like RenderingContext and put the needed methods on that

struct RenderingContext {
  origen: ...
}

impl RenderingContext {
  fn print_position(p: Point) {
        let global_position = origin + p;
        println!("{:?}", global_position);
  }
}

Then all uses of Point will go through a Context, and you can add new features to the context without changing all your code. e.g. if you want to introduce a scaling to fit feature later.

[yongkyuns]

Wow thanks for your thorough comment!

@JosephOsborn

I think the trick might be that the API and data structures used to configure animations is not necessarily the same as the ones used to execute animations. It sounds like since components can inherit different properties from different parents, you’re not defining a tree but a number of trees or a labeled directed acyclic graph. So any approach based on structs owning data will have some friction.

Yeah that is a very good point, I do feel the need to revise my approach significantly. With Rc<RefCell<T>> approach, I also had ergonomic issues with composing traits to extend the functionality of these objects, because I couldn't naturally impl trait methods as if these weren't Rc<RefCell<T>> (which they were ).

@JosephOsborn

I think it might be cleaner to use an API where you use something like an AnimationBuilder struct that can give you opaque identifiers to objects, and you can call anim.set(time, identifier, propertyvalue) or anim.inherit(child_id, parent_id, property) (ensuring that parent_id precedes child_id ).

This seems like a good idea which I should try to prototype for myself and see how this will actually look like and work for my use-case. I have no prior experience with BTreeMap, but I think I get the general idea of not mapping user-facing APIs to object data and trying to leverage a builder construct (maybe behind the scenes using drop?). Will provide more detail if I can get it to work for me!

@JosephOsborn

Then you can target the animation to any collection of animatable objects, and as the animation ticks the animated proxies are updated. The internal animation data could be the same vec of BTreeMaps from before, or some more optimized representation

Yeah I think it would be ideal to have animation-specific data and actual object decoupled. For the actual data structure, I would need to spend some time to figure out based on your comment.

Thank you again for your feedback. This has been much more productive than if I were to figure it all out on my own:)

[yongkyuns]

@droundy

create a corresponding method on the index type. If you like, you're pretending that the SquareIndex is the Square.

Thanks for the clarification! That is an interesting realization which didn't come to me immediately. I will try to prototype this approach and see if I understand your point correctly:)

@droundy

Yes, but I'd tend to give the information passed down a descriptive type like RenderingContext and put the needed methods on that

@droundy

Then all uses of Point will go through a Context, and you can add new features to the context without changing all your code. e.g. if you want to introduce a scaling to fit feature later.

Ah that is awesome, I didn't realize it could be done that way. Thank you for pointing it out to me!

[yongkyuns]

After converting to an Arena type approach, I could get the references to work in the same way as my original Rc<RefCell<T>> version. In addition to the above answers, I also found the following post very helpful to understand shared mutability and acyclic graphs:

Shared mutability in Rust (Part 2 of 3)

Thank you @JosephOsborn and @droundy for your great answers!