SparseSet storage can cause malformed hierarchy asserts

[lloydparlee]

Bevy version

0.9.0

[Optional] Relevant system information

Mac OS 10.15.7 Intel
(I don't think this is OS related)

What you did

I upgraded my game to bevy 0.9 and found this bug triggered by my animation system which uses a sparse set component on entities that have parent-child hierarchies.

I saw these assertions about malformed hierarchies, even though I was never changing the hierarchy after spawning:

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `6v0`,
 right: `26v0`: Malformed hierarchy. This probably means that your hierarchy has been improperly maintained, or contains a cycle', /Users/xxxxx/.cargo/registry/src/github.com-1ecc6299db9ec823/bevy_render-0.9.0/src/view/visibility/mod.rs:312:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'Compute Task Pool (3)' panicked at 'assertion failed: `(left == right)`
  left: `6v0`,
 right: `26v0`: Malformed hierarchy. This probably means that your hierarchy has been improperly maintained, or contains a cycle', /Users/xxxxx/.cargo/registry/src/github.com-1ecc6299db9ec823/bevy_transform-0.9.0/src/systems.rs:69:9

What went wrong

This is a small repro that spawns 4 cubes; two of them are parents, and they each have one child. One of the parents has a sparse set component, and the other parent's child also has it. This repro crashes for me.

use bevy::prelude::*;

fn main() {
    App::new()
        .add_plugins(DefaultPlugins)
        .add_startup_system(startup)
        .run();
}

#[derive(Component)]
#[component(storage = "SparseSet")] // If you comment out this line it doesn't crash
struct MyComponent;

fn startup(
    mut commands: Commands,
    mut meshes: ResMut<Assets<Mesh>>,
    mut materials: ResMut<Assets<StandardMaterial>>,
) {
    let mesh = meshes.add(shape::Cube::default().into());
    let material = materials.add(StandardMaterial {
        base_color: Color::rgb(0.3, 0.3, 0.8),
        ..default()
    });

    // Spawn 4 cubes, 2 will be parents, 2 will be children
    let parent1 = commands
        .spawn(PbrBundle {
            mesh: mesh.clone(),
            material: material.clone(),
            transform: Transform::from_translation(Vec3::ZERO),
            ..default()
        })
        .insert(MyComponent) // Has my component
        .id();

    let child1 = commands
        .spawn(PbrBundle {
            mesh: mesh.clone(),
            material: material.clone(),
            transform: Transform::from_translation(Vec3::new(0., 0., 2.)),
            ..default()
        })
        // Doesn't have my component
        .id();

    let parent2 = commands
        .spawn(PbrBundle {
            mesh: mesh.clone(),
            material: material.clone(),
            transform: Transform::from_translation(Vec3::new(2., 0., 0.)),
            ..default()
        })
        // Doesn't have my component
        .id();

    let child2 = commands
        .spawn(PbrBundle {
            mesh: mesh.clone(),
            material: material.clone(),
            transform: Transform::from_translation(Vec3::new(0., 0., 2.)),
            ..default()
        })
        .insert(MyComponent) // Has my component
        .id();

    // Create parent child relationships
    commands.entity(parent1).add_child(child1);
    commands.entity(parent2).add_child(child2);

    // Light
    commands.spawn(DirectionalLightBundle {
        directional_light: DirectionalLight { ..default() },
        transform: Transform::from_translation(Vec3::new(0., 10., 20.))
            .looking_at(Vec3::ZERO, Vec3::Y),
        ..default()
    });

    // Camera
    commands.spawn(Camera3dBundle {
        transform: Transform::from_xyz(0., 10., 10.).looking_at(Vec3::ZERO, Vec3::Y),
        ..default()
    });
}

The assert I get on this example is:

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `0v0`,
 right: `2v0`: Malformed hierarchy. This probably means that your hierarchy has been improperly maintained, or contains a cycle', /Users/xxxxx/.cargo/registry/src/github.com-1ecc6299db9ec823/bevy_transform-0.9.0/src/systems.rs:69:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Additional information

If the component is changed to not use sparse set storage it doesn't crash.
Also if it uses sparse set storage, but both parents, both children, or only one entity has the component it won't crash.

So this bug is specific to when you have multiple entity hierarchies that have a sparse set component on some of the entities at different levels of the hierarchy.

Also note that the entities need to have PbrBundle (or possibly some other visual components) because the assert happens in visibility and/or transform propagation code.

[james7132]

Can you try with the latest main instead of the released 0.9.0? #6623 was fixed recently, and it looks awfully similar to this issue.

[lloydparlee]

Yes this is fixed on latest main, thanks.