The namespace module is responsible for keeping track of the name bindings in the compiled program, including bindings in external libraries. forc-pkg is responsible for building a Root struct which initially holds a copy of all external bindings, and is then passed to the compiler which populates the struct with bindings from the current package.

We used to do a lot of cloning of external library bindings, and #6291 eliminated quite a lot of that cloning. However, we still clone Root objects in quite a few places, and in particular we represent the dependency graph as a tree rather than a dag, with cloning of nodes with in-degree > 1 (see the illustration in #6291). In general this means that our dependency graph still has a potential exponential blowup in the number of dependencies.

The external packages in the dependency graph should instead be represented as a flat map from package names to Root structs. The externals should be made available to the Namespace struct, so that paths to external libraries can be resolved. This would make it possible to only have a single Root struct for each package, thus making the representation linear in the size of the dependency graph.

This would also fix the issue of paths leaking into packages where the paths no longer making sense, e.g.,

// package A
trait MyTrait { ... }  // path to MyTrait is A::MyTrait

// package B, which depends on A
pub use A::MyTrait;  // Makes MyTrait visible to B's dependents through the path B::MyTrait

// package C, which depends on B but not on A (expect for transitively through B)
impl B::MyTrait for MyType { ... } // Inserts the impl in the trait map using the path A::MyTrait

The path A::MyTrait doesn't make sense when viewed from package C because it doesn't know about package A. This could lead to problems with coherence, as well as potential name clashes if there are multiple libraries with the same name in the dependency graph.