Motivation

Now that we have ancestor linearization, we can finally resolve constants properly. This PR implements the algorithm for constant resolution in Ruby - with a few twists due to the nature of lazy static analysis.

Implementation

We tried to document the code as much as possible. I'll describe the algorithm, which has essentially 3 distinct paths.

Top level references

module First
  module Second
    ::CONST
  end
end

Top level references are the simplest ones. The nesting is completely ignored. All we have to do is try to find the name in the index. We do need to account for aliases too since the top level reference can include a portion of the name that points to an alias.

Qualified references

module First
  module Second
    Third::CONST
  end
end

For qualified references, this is the order of resolution:

1. First, try to find the declaration within the exact namespace where we found the reference First::Second::Third::CONST
2. Then, try to find the declaration in ancestors of the namespace where we found the reference. We search all ancestors of First::Second
3. Then, try to find it in enclosing lexical scopes excluding the top level (which is always considered only as a fallback). We search First::Third::CONST
4. Finally, since we didn't find anything, search for Third::CONST in the top level

Unqualified references

module First
  module Second
    CONST
  end
end

Unqualified references have the order of operations swapped:

1. First, try to find the declaration within the exact namespace where we found the reference First::Second::CONST
2. Then, try to find it in enclosing lexical scopes before searching ancestors. This also excludes the top level. We search First::CONST
3. Then, try to find the declaration in ancestors of the namespace where we found the reference. We search all ancestors of First::Second
4. Finally, since we didn't find anything, search for CONST in the top level

Notes

1. Ruby never searches the ancestors of any enclosing lexical scope except the most specific one
2. We may want to create a cache for resolutions. Maybe a hash that maps the concatenated name + nesting and points to the resolved name. However, knowing when to invalidate the cache would be quite tricky. I recommend we avoid caching for now
3. Fun fact: thanks to the lazy nature of our static analysis, we are actually able to "properly" resolve circular references despite them being invalid Ruby code. See IndexTest#test_resolving_circular_alias and IndexTesttest_resolving_circular_alias_three_levels. This is why we need that seen_names array, which not only protects the index from infinite recursion, but also allows us to resolve these cases

Automated Tests

Added a bunch of tests for various constant reference scenarios, but if you can think of anything that we missed, please propose more tests.