[kythe] Figure out potential scoping ambiguity

[hzeller]

In #1184 there was a scoping ambiguity detected in a performance improvement that did not entirely capture the previous implementation semantics (but, it is also not clear if the semantics were correct in the first place - no tests covered the expectation)

For an example see the comments in that PR, in particular this: https://github.com/chipsalliance/verible/pull/1184#issuecomment-1032140815

[MinaToma]

Hello @hzeller, @ivan444 and @fangism,

It's my honor to be able to help with this project again. I am really sorry for this late reply but I am spending my military service period right now and I don't have access to nearly anything (mobile, gmail, etc...) so I couldn't reply earlier.

Regarding this: https://github.com/chipsalliance/verible/pull/1184#issuecomment-1032140815

I spent some time exploring this and I think I found what makes the indexer output the tow references #A# and #A#A# so let me try to illustrate it.

Let's split what happens into two iterations because the indexer iterates until it doesn't find any more facts Code Pointer

Let's begin with the first iteration: This should be ScopeContext before indexing this line import A::*; note: the names may not be exactly the same but the idea still holds.

{ // The global scope of the file we are trying to index
   #file#node#,
   #file#x#,
   #file#A#,
} 

Now let's index import A::*: ScopeResolver traverses the above ScopeContext in reverse order and tries to find anything that ends with A. and in this case it finds #file#A# and emits the RefEdge to the package definition.

After this according to this line we append the scope of the imported package to our scope to be able to reference the variables inside it from our current scope. ScopeResolver after the import statement becomes:

{ // The global scope of the file we are trying to index
   #file#node#,
   #file#x#,
   #file#A#,
   #file#A#A#,  // this is where the second reference comes from (more details below)
   #file#A#B#,
   #file#A#C#,
    .....
} 

and with this we finish the first iteration but before we finish we save the scope of the file we generated during this iteration according to this line

Now the second iterations begins: At the beginning of the indexing we load the scope we had during the previous iteration Code Pointer and according to this we start the indexing with this ScopeContext :

{ // The global scope of the file we are trying to index
   #file#node#,
   #file#x#,
   #file#A#,
   #file#A#A#, 
   #file#A#B#,
   #file#A#C#,
    .....
} 

Now when we index the import A::* again we search ScopeContext in reverse order for something that ends with A and we find the #file#A#A# and create the EdgeRef.

I am not sure if it's right or wrong to have the enum named like the package but this causes one more problem: This issue #1128 and I think this line was the fix for that issue. The reason why this is crashing is because we don't have a scope for #file#A#A# and hence we have a nullptr scope so we can't append the scope in this line.

I hope this covers what you have doubt about. I am always happy to help you with anything and please feel free to mention me anytime and I will reply whenever I could.

Best regards to all of you. Mina

[ivan444]

Thanks Mina! We'll have to revisit the scope resolution (make it sublinear & closer to Verilog specs).