Type checking analysis pass

[nblei]

Dalance,

I would like to add a type checking pass which has a primary goal of evaluating the size (in bits) and packedness of each datatype.

The way I see this working is that a graph whose nodes are types, and whose edges represent dependencies.

For example,

type k = logic<2>;
struct m {
  a: k,
}

Would contain three nodes and two edges:
(logic<2>) -> (k) -> (m).

In addition to allowing us to identify the packed size of m, this also allows us to do dependency analysis. The type-graph should be a DAG. If a cycle exists, we have a problem. However, currently

package p {
    struct m {
        a: logic,
        n: n,
    }
    struct n {
        b: logic,
        m: m,
    }
}

passes on this mutually recurssive, but not inductive package p.

Any thoughts on this approach?

[nblei]

Another note:

Currently, veryl allows declaration of variably lengthed logic vectors:

module foo
{
    var a: u32;
    var _b: logic<a>;
}

produces

module veryl_testcase_foo;
    int unsigned         a ;
    logic        [a-1:0] _b;
endmodule

I think this is likely because the struct Type's width and array fields:

pub struct Type {
    pub modifier: Vec<TypeModifier>,
    pub kind: TypeKind,
    pub width: Vec<syntax_tree::Expression>,
    pub array: Vec<syntax_tree::Expression>,
}

These are arbitrary expressions, and no checking is done to determine if they are evaluable, either directly into an explicit constant natural number, or parametrically.

[dalance]

A primitive type evaluation is implemented at https://github.com/dalance/veryl/blob/master/crates/analyzer/src/handlers/check_enum.rs.
It evaluates the size of enum members and checks whether the size is over the enum size.

I implemented it as a checker, but I think it should be more generic framework.
For example,

• Create SymbolTable ( already implemented )
• Create Type DAG from the SymbolTable
• Evaluate size of each entry of the DAG
• Check relationship between each entry like enum, union

About cycle of DAG, I think it should be reported as error at creating DAG phase.
Variably lengthed logic may be checked at evaluating phase too.

The current implementation of evaluator https://github.com/dalance/veryl/blob/master/crates/analyzer/src/evaluator.rs can handle fixed value only.
It is required to extend to support parameterized value.

[nblei]

How is the symbol table currently used? greping the analyzer crate shows that symbol_table::get_all() is only used in analyzer::check_symbol_table, and symbol_table::get is only used in the symbol_table crate's test module.

It looks like to use the symbol table in a separate pass, I would need to implement VerylGrammarTrait functions for all syntactical structures which can push to SymbolPath and Namespace. However, this is something very easy to mistake.

Perhaps a trait VerylGrammarContextTrait : VerylGrammarTrat is called for. This subtrait would implement default functions which push/pop symbol path / namespace as required.

Does this make sense?

[dalance]

The symbol table is used at some analyzer handlers and language server.
For example,

https://github.com/dalance/veryl/blob/9571195d062834f9c0b365e06344660c45c31191/crates/analyzer/src/handlers/check_function.rs#L39
https://github.com/dalance/veryl/blob/9571195d062834f9c0b365e06344660c45c31191/crates/analyzer/src/handlers/check_instance.rs#L45

It looks like to use the symbol table in a separate pass, I would need to implement VerylGrammarTrait functions for all syntactical structures which can push to SymbolPath and Namespace. However, this is something very easy to mistake.

To avoid re-implementation of pushing/poping SymbolPath and Namespace, I implemented namespace_table.
https://github.com/dalance/veryl/blob/master/crates/analyzer/src/namespace_table.rs

It holds pairs of TokenId, and Namespace which is belonged by the token.
It is created at creating symbol table, and namespace can be resolved without push/pop after the creation.
symbol_table::resolve internally calls the namespace_table like below:

https://github.com/dalance/veryl/blob/9571195d062834f9c0b365e06344660c45c31191/crates/analyzer/src/symbol_table.rs#L130-L135

[nblei]

Hey @dalance , any changes you'd like me to make to #383?

[dalance]

Sorry for the late reply.
I'ii check it by this weekend.