Deduplicate crates in crate graph

[Veykril]

It's incredible that we aren't actually doing this already. When we load a project that contains multiple workspaces we do not deduplicate equal crates in the crategraph! That means just for the sysroot alone that it is loaded multiple times into memory and queries executed on the sysroot of one workspace are not reused for another. It wouldn't surprise me if some of the high memory usage reports we get comes from projects that have a lot of cargo workspaces in them.

Here all we do is append crates, but we are not deduplicating them. Nor are we doing so after having built the final crategraph.

rust-analyzer/crates/base-db/src/input.rs

Lines 495 to 515 in 2365762

	/// Extends this crate graph by adding a complete disjoint second crate
	/// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
	///
	/// The ids of the crates in the `other` graph are shifted by the return
	/// amount.
	pub fn extend(&mut self, other: CrateGraph, proc_macros: &mut ProcMacroPaths) -> u32 {
	let start = self.arena.len() as u32;
	self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
	let new_id = id.shift(start);
	for dep in &mut data.dependencies {
	dep.crate_id = dep.crate_id.shift(start);
	}
	(new_id, data)
	}));
	*proc_macros = mem::take(proc_macros)
	.into_iter()
	.map(|(id, macros)| (id.shift(start), macros))
	.collect();
	start
	}

[bruno-ortiz]

@Veykril what would be the best aproach on this? I'm thinking in two ways of doing it.

1- Something like this:

pub fn extend(&mut self, other: CrateGraph, proc_macros: &mut ProcMacroPaths) -> u32 {
        let start = self.arena.len() as u32;
        let other: Vec<_> = other
            .arena
            .into_iter()
            .filter(|(_, data)| {
                !self.arena.iter().any(|(_, cd)| cd.root_file_id == data.root_file_id)
            })
            .map(|(_, mut data)| {
                for dep in &mut data.dependencies {
                    let new_crate_id = RawIdx::from(u32::from(dep.crate_id.into_raw()) + start);
                    dep.crate_id = CrateId::from_raw(new_crate_id);
                }
                data
            })
            .collect();

        self.arena.extend(other);
        *proc_macros = mem::take(proc_macros)
            .into_iter()
            .map(|(id, macros)| {
                (CrateId::from_raw(RawIdx::from(u32::from(id.into_raw()) + start)), macros)
            })
            .collect();
        start
    }

This applies depuplication only to the extend methods, dunno if we should worry of other points of insertion.

2- Making some sort of an ArenaSet, using an IndexSet instead of a Vec, this would implie that every 'T' should implement 'Hash', and I'm not sure if this would be worse performance wise, due to the hashing.

[Veykril]

CrateData can't implement Hash due to our usage of hashmaps inside of it, so that's not an option. Your proposed extend method doesn't work, we need to check whether the two CrateDatas are equal (which may in turns require checking that the dependencies field is the same even if they point to different crate ids (which are the same ids when deduplicated).

[bruno-ortiz]

Isn't the root_file_id always the same if pointed to the same path? And if it points to the same path doen't mean that it points to the same crate?
Maybe we should compare the crate's name and version to? Comparing the dependencies seems overkill if 2 crates have the same path, version, and name.
Maybe I'm wrong, I'm still learning my way through RA codebase.

[Veykril]

root_file_ids aren't unique, we could have crates pointing to the same root file with differing cfg's (this will become relevant once we duplicate crates for dev-dependency edges to resolve cycles #14475. But you are right that there are probably some things in the CrateData that we can ignore in terms of deduplication (basically we'd need to check what makes up the "key/identity" of a crate given a CrateData)

That aside the dependency crate id fix up in your code is wrong though, once we start deduplicating shifting ideas naively won't work, we'd need to keep a mapping from duplicate IDs to non-duplicate ID I believe, which in turns might make the order we process these in relevant.