Add collision prevention to `HandleId::random()`

[BGR360]

Background

Background

At the time of writing the Bevy version is 0.6.1.

Here is the implementation of HandleId::random():

bevy/crates/bevy_asset/src/handle.rs

Lines 53 to 55 in 544b6df

	pub fn random<T: Asset>() -> Self {
	HandleId::Id(T::TYPE_UUID, rand::random())
	}

Here is where the method is used in bevy_asset:

bevy/crates/bevy_asset/src/assets.rs

Lines 77 to 88 in 544b6df

	/// Adds an asset to the collection, returning a Strong handle to that asset.
	///
	/// # Events
	/// * [`AssetEvent::Created`]
	pub fn add(&mut self, asset: T) -> Handle<T> {
	let id = HandleId::random::<T>();
	self.assets.insert(id, asset);
	self.events.send(AssetEvent::Created {
	handle: Handle::weak(id),
	});
	self.get_handle(id)
	}

I use this method manually to immediately return a handle to an asset that I will generate asynchronously, and then later use Assets::set_untracked to place the generated asset into the collection.

What problem does this solve or what need does it fill?

Problem: It's possible (although unlikely) for HandleId::random() to produce a HandleId that is already in use by an existing asset in the Assets collection. This would result in overwriting the existing asset rather than adding a new one. This would be confusing for the user and very difficult to root-cause (and nearly impossible to reproduce).

What solution would you like?

Require users to provide a &Assets<T> reference so that collisions can be detected and the dice can be re-rolled:

fn random<T: TypeUuid>(assets: &Assets<T>) -> Self {
    loop {
        let handle_id = HandleId::Id(T::TYPE_UUID, rand::random());
        if !assets.contains(handle_id) {
            return handle_id;
        }
    }
}

What alternative(s) have you considered?

Implement the suggestion above, but do so as an additional method and call it something like random_unique().

Additional context

We may well decide that the likelihood of this is so low that it's not worth bothering.

See also a short Discord conversation here: https://discord.com/channels/691052431525675048/749332104487108618/944733810577264720

[mockersf]

I think adding the check would be better in

bevy/crates/bevy_asset/src/assets.rs

Lines 81 to 88 in 544b6df

	pub fn add(&mut self, asset: T) -> Handle<T> {
	let id = HandleId::random::<T>();
	self.assets.insert(id, asset);
	self.events.send(AssetEvent::Created {
	handle: Handle::weak(id),
	});
	self.get_handle(id)
	}

[bjorn3]

That will not help set() with HandleId::random().

[aloucks]

The whole point of v4 (random) UUIDs is so you don't to perform these kinds of checks, assuming that you don't cripple your entropy.

https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)

For example, the number of random version-4 UUIDs which need to be generated in order to have a 50% probability of at least one collision is 2.71 quintillion, computed as follows:[22]

This number is equivalent to generating 1 billion UUIDs per second for about 85 years. A file containing this many UUIDs, at 16 bytes per UUID, would be about 45 exabytes.

[BGR360]

@aloucks Asset handles don't use UUIDs. They use pseudorandom 64-bit numbers. Generating a UUID for each asset sounds prohibitively expensive.

[aloucks]

@aloucks Asset handles don't use UUIDs. They use pseudorandom 64-bit numbers. Generating a UUID for each asset sounds prohibitively expensive.

Ah, I see it's using the UUID of the Type combined with the random u64. My mistake!

[MalpenZibo]

It's not an elegant solution but in my engine that it's heavily inspired by bevy I use an AtomicU64 to manually generate an id instead of HandleId::random().

The idea is to create (using a derive macro) a static {ASSET_NAME}_COUNTER: AtomicU64 = AtomicU64::new(0) for each Asset and implement the next_counter function using that AtomicU64.

pub trait Asset: Downcast + Send + Sync + std::fmt::Debug + 'static {
    fn next_counter() -> u64
    where
        Self: Sized;
}

....

#[proc_macro_derive(Asset)]
pub fn asset_macro_derive(input: TokenStream) -> TokenStream {
    let input = parse_macro_input!(input as DeriveInput);
    
    let name = input.ident;
    let asset_counter = format_ident!("{}_COUNTER", name.to_string().to_uppercase());
    let (impl_generics, ty_generics, where_clause) = input.generics.split_for_impl();

    let expanded = quote! {
        static #asset_counter: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
        impl #impl_generics Asset for #name #ty_generics #where_clause {
            fn next_counter() -> u64
            where
                Self: Sized,
            {
                #asset_counter.fetch_add(1, std::sync::atomic::Ordering::Relaxed)
            }
        }
    };

    TokenStream::from(expanded)
}

usage

let next_id = TestAsset::next_counter();
let handle_id = HandleId::new_from_u64::<TestAsset>(next_id);

[james7132]

HandleId no longer exists, and AssetId, there is no randomized initialization option anymore. Is this issue still relevant?