Analysis order about rust_hdl HOT 5 CLOSED

I think it's very important for the analysis to be able to automatically process a set of files without being given a fixed compile order as input. Having said that, I'm not so sure about the importance of generating an explicit file dependency output for the user.
I think this task is needed seldomly enough that it's not warranted to compute it at each execution of the analyser.

This in combination with the mentioned potential of code duplication makes me fairly sceptic of Solution 1:
It's not clear to me how much work actually would be done twice to compute the dependencies and analyse the files afterwards. If it's a non-trivial amount of work, it
a) seems like a waste to do it twice and
b) might eat up a lot of the performance benefit of having a clear layout for parallel analysis.

Solution 2 seems like a simple choice for a first implemantation to get the analyser running.
I don't think that it's much of a problem to do the full analysis to get the order out of it. I'd hazard a guess that analysing VHDL code can be done fast enough for the use with a language server, even if the compile order is not cached between runs.
On the other hand, I agree that this solutions seems hard to do efficiently in parallel and I can imagine that it runs into performance issues on larger projects.
I have a hard time imagening a stack overflow on a real-world project, but there might be autogenerated filesets out there that are so huge that this becomes a problem.

With this in mind, I'd like to add a 3rd solution to the discussion:

3. Lazy evaluation of imports

This method relies on a tree of namespaced exported symbols that is shared between all involved design units.
Use clauses and context clauses are used to filter allowed import paths for their design unit.
All units to be analysed are stored in a queue and are popped out one at a time.
If the analyser can't resove a symbol (with the help of the exported symbols in the tree), the analysis of
this unit is paused and the unit is pushed back into the queue.
The analysis continues with the next unit in the queue, exporting declarations to the tree as it goes.
If a unit is fully analysed, it doesn't get push back to the queue.
If all units in the queue are paused without a new export to the tree, there is either a missing declaration / import, or a cyclical dependency.
Every time an symbol is imported from the table, the import location is added to the exported symbol.

pros

• Almost single pass (only unresolved symbols are analysed multiple times)
• Inherently simple to do in parallel
• Pretty much does Scope analysis as well
• Produces an import/export table wich can be used to generated an explicit dependency graph
• The import/export table can potentially be used to find outdated files in the case of incremental analysis
• Missing imports can be caught by searching the entire tree for symbols
• Dependencies are encoded implicetly, making the issues with the given use cases probably simpler.

cons

• More involved implementation (since it needs to be able to resume analysis from a stored state)
• Cyclical dependencies need to be checked explicitly
• Shared tree might become bottleneck for parallel execution (although I don't think it will)

from rust_hdl.

Users of explicit compile order are third party tools like GHDL or commericial simulators that want to have the files in compile order.

Option 3. is probably a better variant of option 2. but with an explicit stack/queue instead of using function call stack. I think it is worth to consider for the future.

Regarding option 1. I think it can be made very simple if you accept extra dependencies in the corner case above which I think is not a big practical problem. Thus I think option 1. is the simplest one to implement for the first version. Having the analysis order before analysis will make it less complex to implement than doing something like 3. Doing 3 could become an option in the future as either a performance optimization or if the corner case above becomes practically interesting.

I want to focus on getting analysis right before I try to optimize performance to much. It the old rule of first making it correct then making it fast.

from rust_hdl.

Users of explicit compile order are third party tools like GHDL or commericial simulators that want to have the files in compile order.

Right. I'm not arguing against the functionality of generating compile order outputs. I just think that it's not much of an issue to compute the compile order explicitely for this purpose, if it isn't needed in for the analysis itself (i.e. Option 2 & 3).

Option 3. is probably a better variant of option 2. but with an explicit stack/queue instead of using function call stack. I think it is worth to consider for the future.

Regarding option 1. I think it can be made very simple if you accept extra dependencies in the corner case above which I think is not a big practical problem. Thus I think option 1. is the simplest one to implement for the first version. Having the analysis order before analysis will make it less complex to implement than doing something like 3. Doing 3 could become an option in the future as either a performance optimization or if the corner case above becomes practically interesting.

I might be very wrong here, but I'm not so sure about option 1 being simple (even with the relaxed corner case dependency). It seems to me, that option 1 is by default harder to implement than option 2, since 1 models dependencies explicitly, while 2 (and 3) only care about the existence of the symbols they import.
For 2 you'd just call the analysis procedure on the design units that provide your use clauses.

I want to focus on getting analysis right before I try to optimize performance to much. It the old rule of first making it correct then making it fast.

I agree with this.
Option 3 is probably too much effort for an implementation to get things running.
But I also think that a later, more optimised implementation would probably go similar route as option 3, i.e. single pass without an explicit dependency representation.
This makes the architecture fairly different from option 1, making a conversion later on harder ,especially if user facing features like compile order files depend on this architecture.

from rust_hdl.

The hard thing with 3. is that you could be forced to swap out at any nested position where you could be in the middle of several declarative regions. For example in nested function definitions. You would have to keep track of the continue-position for each parent region so the continue-position cannot be a single value. With option 2. this is done implicitly with the loop counter for each region on the stack.

I have started going down the option 1 path now but I am still thinking about if option 2 is better. What I like about 1 is the separation of concerns in that I can isolate one part that only cares about dependencies between design units and another part that can analyse design units relying on that the order is already correct. Maybe 2 is better because I will not have to re-visit all names and recompute the visibility. I think I will try 2 and see how it feels.

from rust_hdl.

I have implemented option 2. now with on-demand analysis and circular dependency detection. It works well.

from rust_hdl.