Origin of fixed-point iteration name resolution

[matklad]

Rust import resolution fundamentally uses a fixed-point iteration algorithm. This is one of the toughest bits to support in IDE in a performant way, because fixed point makes laziness hard.

I am curious about how this bit of he language. Are there any relevant discussions of the issue? Was the iteration present from the first version, or was it added later?

[petrochenkov]

The important steps towards the current scheme were (from the most recent ones to the oldest):

• Macro modularization (RFC 1561, RFC 1560), required import resolution and macro expansion to interleave.
• Decision to support glob imports during stabilization of Rust 1.0. This didn’t happen through an RFC and I can’t find relevant issues/PRs right now, I only remember that it wasn’t entirely uncontroversial.
• If you remove macros and globs, the remaining system is much simpler and maybe doesn’t need a fixed-point iteration to resolve it, even considering that imports still can refer to other imports (immediate resolution for each individual import is known, but in the end you may discover that certain import chains do not lead anywhere).
  Or maybe it still does because use foo /* type only */; fn foo() {} still should resolve without conflict (and Rust always had type vs value namespace difference (?)), not sure.

[glaebhoerl]

This may be of historical interest: https://github.com/nikomatsakis/rust-name-resolution-algorithm

And this is (for obvious reasons) purely to satisfy my own curiosity, but: if recursive imports were forbidden, but all the other stuff was supported (macros scoped inside modules, macros defining modules and macros, etc.), would it still require fixpoint iteration?