Cyclic references in the type hierarchy

[straight-shoota]

When walking the program's type hierarchy, visitors usualy start with Program and recursively iterate nested types (i.e. the types defined within its scope). Usually, you would expect the hierarchy to be non-cyclic. It's not possible to redefine a type within itself. Reopening is possible, but then it is already defined in a higher scope, so there's no cycle.

There are however some issues with aliases.

AliasType#types delegates to the aliased type. The nested types for type Foo (with alias Foo = Bar) would be the nested types of Bar.

struct Bar
  alias Foo = Bar
end

If the alias is defined inside its target, it creates a cyclic reference: The nested types of Bar include an alias Foo. Resolving the alias leads to Bar and iterating its nested types yields Foo again.

This behaviour leads to infinite recursion in crystal tool unreachable (see #14034). As it turns out, many other type hierarchy walkers have explicit conditions to avoid this (see #14034 (comment)). UnreachableVisitor was "just" missing this (and others as well: #15065 (comment)). This is easy to fix, but I'd consider this a workaround for an API flaw.

The root cause is that when walking the type hierarchy, you don't expect to visit the same type multiple times. Every time we walk the hierarchy, we need to take non-obvious extra precautions. That's unintuitive and error-prone.
The type hierarchy has no inherent reason to be cyclic. I think all existing cycles are a mistake.

The other major use case of AliasType#types besides walking the tree is to lookup nested types by name. For this it makes sense to delegate to the aliased type because, well, resolving names is what aliases are for.
If we separate these use cases "walk the type hierarchy" and "lookup nested types" in the API, both can be implemented cleanly and without surprises.

There's another issue related to aliases: I didn't even know you could reopen a type through an alias (it's possible in Ruby, too). But if you do this within the scope of the aliased type, it creates another cycle:

class Foo
  alias Bar = Foo

  class Bar
  end
end

This code even brings down the compiler itself, not just some of the tools. This appears to be a simple error in the top level visitor for ClassDef (i.e. modules are not affected). It should be easy to fix🤞 (#15067)