Public API for traversing the design hierarchy / AST

[kraigher]

We need to create a stable public API to traverse the design hierarchy and the AST. I am hoping @Schottkyc137 and @skaupper can contribute their ideas and feedback here. My goal is to replace the Search trait and the Visitor trait with this implementation. First we need to gather some requirements than we can discuss the implementation.

Performance requirements

• Must not perform heap allocation

Public requirements

Library

• Must be able to get library by name
• Must be able to iterate over all libraries

Design units

• Must be able to iterate over all design units in a source file
• Must be able to get primary units from library by name
• Must be able to iterate over all primary units in a libary
• Must be able to iterate over secondary units of a primary unit
• Must be able to get context clause of a design unit

Declarations & Statements

• Must be able to iterate over all declarations, sequential statements, concurrent statements in a design unit
• Must be able to iterate over all declarations and statements nested within other declarations and statements
• Must be iterate over declarations and statements in the order they appear in the source file.

Navigation

• Get referenced named entity (AnyEnt) from source location
• Get referenced design unit/statement/declaration in AST from named entity (AnyEnt)
• Get all source locations referencing named entity (AnyEnt)

Private requirements

• Must be able to clear all references in the entire AST

[Schottkyc137]

Some preliminary thoughts from myself without getting too much into details:

• Tool Directives
  Currently, tool directives are tokenized, but ignored afterwards so that no false positives are detected. However, a public API should make some methods / traits available to hook into the tokenizing process so that third-parties can utilize vhdl_lang to perform tasks on tool directives. Potential use-cases include the protect tool directive and a potential vhdl_lang tool directive to mute listing errors

• Scope
  I believe that this discussion could benefit from first defining use-cases of vhdl_lang. In my opinion, the design of a public API will benefit from making this clear at first. I can think of the following use-cases which would be of interred for me but others will probably be interested in this as well:

  • Tool directives for third-parties (see above)
  • Code Formatters
  • Documentation extractor (Referring to @skaupper's work)
  • Linters (should linting not be a concern of a public API since it's already part of the private API?)
  • Testbench generation or other code generation from VHDL
  • Code inspection in general (See Feature request: expose tokenizer in public API #203 for example)
  • Integration with other HDL's / Language servers of other HDL's (There was interest in the Chat for some Verilog / VHDL shared language server)
  • Long-term goal: Simulator / full-fledged compiler for VHDL

Are any of these out of scope? Did I miss anything? What do you think?

[kraigher]

Regarding scope I am a believer in adding only what is currently needed. We can add more stuff in the future when there is a use case that can drive the design. I find one rarely gets the API right if you add everything up front.

For now I think the goal should be to have a nice API without duplication of Search/Visitor that supports completions, lsp and document generation as the initial scope.

[skaupper]

For navigation I want to add, that getting parents declarations from AST elements is important as well. Which may already be possible with AnyEnt (I have not looked into it too deeply).

Even if it is not immediately required, it would probably be good to ensure that AST elements are traversed in the order they appear in the source code, as that would probably be rather hard to rework after the fact. The current implementation does seem to do that as well.

I may encounter further things when I come around to play with the current implementation.

[kraigher]

For navigation I want to add, that getting parents declarations from AST elements is important as well. Which may already be possible with AnyEnt (I have not looked into it too deeply).

AnyEnt has a parent field. So this is already supported.

Even if it is not immediately required, it would probably be good to ensure that AST elements are traversed in the order they appear in the source code, as that would probably be rather hard to rework after the fact. The current implementation does seem to do that as well.

Yes this has always been a goal so that sorting on srcpos is not necessary. I add it as an explicit requirement above.

[kraigher]

There are two main things I have in mind for the API:

1. I think the API should offer a simple way to iterate over libraries, design units, statements and declarations. I think the client code needs some control over when the nesting happens when iterating recursively. The reason is I think it is likely that a client code would like to have some context where they keep track of where they are in the AST and this is not easy with a recursive visitor pattern as you have no control over the nesting of calls.

2. I think we do not need a general public visitor API to visit every small intermediate node in the AST below the statement/declaration level. For example why would we need a visitor function for a qualified expression? What is a client supposed to do with a visiting a qualified expression out of context? I think it is enough to have a way to find all references within an AST subtree and a way to go from SrcPos to a reference.

With these two things in mind I think we could create a type like this:

enum NodeRef<'a> {
   Declaration(&'a ast::Declaration),
   Sequential(&'a ast::Sequential),,
   Concurrent(&'a ast::Concurrent),
}

trait<'a> NodeVisitor<'a>  {
  // Only iterates over immediate children, not recursively
  fn for_each_child(&self, fun: FnMut(NodeRef<'a>));
  // An alternative is to use impl Iterator<Item = NodeRef<'a>> but I think the type inferred by impl Iterator would be complex to create without Box<dyn Iterator> however maybe the heap allocation is not so bad as @Schottkyc137 benchmarked.
}

The API on the top level would be the Root which I think could be created as a thin facade over the internal DesignRoot

impl <'a> Root<'a>  {
   fn libraries(&self) -> impl Iterator<item = Library<'a>> {}
   fn get_library(&self, sym: &Symbol) -> Option<Library<'a>> {}
}

impl <'a> Library<'a>  {
   fn primary_design_units(&self) -> impl Iterator<item = DesignUnit<'a>> {}
   fn get_primary_unit(&self, sym: &Symbol) -> Option<DesignUnit<'a>> {}
}

impl <'a> DesignUnit<'a>  {
   fn secondary_design_units(&self) -> impl Iterator<item = DesignUnit<'a>> {}
   fn get_secondary_unit(&self, sym: &Symbol) -> Option<DesignUnit<'a>> {}
   fn context_clause(&self) -> ContextClause<&'a> {}
}

impl<'a> NodeVisitor<'a> for DesignUnit {}

[skaupper]

What I really like about the current visitor implementation is that simple use cases require simple code. The use case Get all procedure declarations can be achieved by only implementing the visit_subprogram_declaration method of the Visitor trait. But I agree with you that more context/control over how the AST is traversed is probably needed.

Although I do not know how easy it is to use custom iterators, they would allow the user a great amount of control, if needed.

I could imagine uses like these:

let design_root = ...;
// Get all primary units from the design
let primary_units_iter = design_root.get_primary_units(); // impl Iterator<item = DesignUnit>
// Get all declarations from the design
let declarations_iter = design_root.get_declarations(); // impl Iterator<item = Declaration>

By using iterators where possible the user would have access to iterator functions like .map(...) and .filter(...).

The relevant traits could look like this:

trait PrimaryUnitVisitor {
    fn get_primary_units(&self) -> impl Iterator<item = PrimaryUnit>;
}

trait DeclarationVisitor {
    fn get_declarations(&self) -> impl Iterator<item = Declaration>;
}

By implementing them for the right types (DesignRoot, PrimaryRoot and even Iterator<item=PrimaryUnit>) I imagine that even the following might be possible:

// Get all declarations from all primary units (even .filter(...) might be possible between get_primary_units and get_declarations)
let declarations_iter = design_root.get_primary_units().get_declarations(); // impl Iterator<item = Declaration>

---

Please bear in mind that there may be some roadblocks I did not consider (because of lack of experience), but I think an iterator based API (if possible) would be quite versatile and powerful.

[kraigher]

@skaupper A context free vistor API could always be built as an utility on top of the API I proposed. I do not think we need a visitor function for every litte thing from day one though. I would rather have the use cases drive the design when they occur. Day one is enough with an API for the current use cases.

Regarding methods returning impl Iterator in traits I think it is not possible yet. Maybe works now with generic associated types, have to check. You have to use Box<dyn Iterator> otherwise

[skaupper]

Day one is enough with an API for the current use cases.

That's fine for me. I wasn't proposing a visitor API as it is now, just wanted to emphasize its simplicity in cases where context is not needed. For the initial design it should be sufficient to iterate declarations and statements.

Regarding methods returning impl Iterator in traits I think it is not possible yet

Too bad that is not possible as of right now.

I do like your API suggestion, though. Equivalent to primary_design_units, secondary_design_units etc. shouldn't the following be also possible?

impl <'a> DesignUnit<'a>  {
    fn children(&self) -> impl Iterator<item = NodeRef<'a>> {}
}

If possible, I would prefer it to write design_unit.children().for_each(...) instead of design_unit.for_each_child(...) because the user would still have access to all other Iterator functions (like map and filter) without being that much more verbose. What do you think?

[kraigher]

Maybe the right trade-off in this case is to sacrifice a little bit of performance and use a boxed dyn Iterator:

fn children(&self) -> Box<dyn Iterator<Item=NodeRef<'a>>>

It is at least better than using a Vec I think.

[kraigher]

As it seems the overall design is ok I will create an implementation of my proposal and make an PR so we can discuss more details.

[kraigher]

I made a first draft here: #228

[kraigher]

I added a benchmark that can be run with cargo bench on master so we can have something to compare with when we replace the Search trait with a new api.

[kraigher]

I am currently also working on a bottom-up refactor to bring the Searcher and the Visitor closer together. I already fixed that the Searcher does not need &mut on the AST. I use AtomicUsize to clear references instead.