The right approach to use slang as a formatter

[suzizecat]

Hi there !

I am currently starting to work on a SystemVerilog source formatter tool (alongside a language server) using slang.
For the time being, the idea would be to format the code to my liking (before adding any options).
So, to keep it simple:

• Perform indentation,
• Beautify spacing (remove multiple spaces, aligns statements, that sort of stuff).

I am also allowing myself to move around bits of code to make it easier on my eyes (one statement per line, in example) and easier to implement.

My approach is to use a custom visitor (class derived from slang::syntax::SyntaxVisitor ), reads the AST and actually rewrite the source code from this.

My problem is that it seems quite complicated to handle comments, empty lines and anything that is not directly represented by a token. (the trivia, I guess ?)
Moreover, I find it particularly tedious to handle all types of possible syntax node on each and every situation.
In example, for parameters declaration, the type of the parameter is a DataTypeSyntax which can be 8 different actual objects with various structures. I am aware of the SyntaxNode::toString() function, but it pose some challenges for formatting (newlines and leading spaces are kept).

While I am not surprised by the tediousness of the job, I am wondering if I am going down the right path or if someone did such thing with a more clever approach that I am not aware of.

Best regards !

[MikePopoloski]

The SyntaxRewriter class (which inherits from SyntaxVisitor) might be helpful here, but I agree that it's probably going to be some work to make it less tedious. Note that you don't necessarily have to write a handler for every type of syntax node; you can write handlers for the base classes (like DataTypeSyntax) and that will be called for all types of nodes that don't have more specific handlers.

If I were starting this project I would look at how clang-format works, and also probably how some of the C# auto-formatter tools work (slang's parser design is inspired by clang and the Roslyn C# compiler). If you want to add helpers / utilities / make upstream changes to make the job of writing the formatter easier I'm happy to take PRs.

[suzizecat]

Note that you don't necessarily have to write a handler for every type of syntax node; you can write handlers for the base classes (like DataTypeSyntax) and that will be called for all types of nodes that don't have more specific handlers.

I meant that rather in the formatting part rather than for the visitor. Like, I have to handle specifically if a parameter value is an integer, a numeric expression (3*4) a litteral string or whatever.

If I were starting this project I would look at how clang-format works, and also probably how some of the C# auto-formatter tools work (slang's parser design is inspired by clang and the Roslyn C# compiler)

Thanks for the pointers, I'll have a look.

By any chance, is there an easy way to have the raw list of typed tokens of a file (I believe just after lexing) ? Meaning a vector (or equivalent) of only Tokens annotated with their types. Ideally with whitespaces, newlines, comments and such still in a token form instead of trivia (to keep the order between such tokens and the "meaningful" / actual RTL tokens)
I am not sure how I will actually work so I am exploring a bit 🙂

[MikePopoloski]

Well you can certainly run just the lexer and get a list of tokens, but you won't know the larger language structures those tokens are a part of until you run the parser. Trivia (whitespace, comments, etc) are never in token form; they're always trivia. Tokens are only things that have actual impact on the parsing / semantics of the design.

[suzizecat]

Ok, thanks for the clear answers 🙂
Just to be sure, could you confirm that trivia are (always):

• Preceding the token on which they are "attached"
• Always stored "in order" (first trivia encountered is the first in the trivia list)

So that, in order to print the code as it was in the original file you could do something such as:

for (const Trivia& triv : token.trivia)
{
    cout << triv; // Trivia includes newlines
}
cout << token.rawText();

(This is simplified and all from memory since I don't have the actual slang documentation with me right now)

[MikePopoloski]

Yes, that's right. That's basically what the SyntaxPrinter class does.

[suzizecat]

Hello again,

For reference, after fiddling around quite a bit, I found the following code structure to perform fairly well for my goal (Here, attaching an end of line commend to a port declaration) in a module declaration such as

module instruction_counter #(
	parameter K_ADWIDTH = 855, //! Address width
	parameter int K_DWIDTH_IS_VERY_VERY_LONG = 8 + 35, K_TOTO = 5
) (
	input  logic                 i_clk     , //! Input clock
	input  logic                 i_rstn    , //! Reset, active low
	input  logic                 i_incr_en , //! Increment enable
	output logic [K_ADWIDTH-1:0] o_addr    , //! Output address
	input  logic                 i_set_addr, //! Override counter value
	input  logic                 i_jump    , //! Jump one address
	input  logic [K_ADWIDTH-1:0] i_addr      //! Address to set the counter
);

I came up with something along the lines of

void VisitorModuleBlackBox::handle(const ImplicitAnsiPortSyntax& port)
{
	// bb.ports hold the list of ports of the module I'm analyzing
	if(bb.ports.size() > 0)
	{
		for(const slang::parsing::Trivia t : port.header->getFirstToken().trivia())
		{
			// Assuming that I will only have one comment, could be refined.
			// in particular by checking the line number with the port declaration.
			if(t.getRawText().starts_with("//"))
			{
				bb.ports.back().comment = t.getRawText();
				break;
			}
		}
	}
	// Do quite a bit of other things...
}

I'm starting to get around mixing the visitor strategy (with handles) and manually descending in interesting nodes manually.
It is still tedious though.

[suzizecat]

So, after tackling several point on another project of mine, I came back to have a try at this whole formatter thing.

The issue with my previous approach is the risk of losing elements during the conversion.
In order to avoid this, I am looking into the syntax rewriter class.

My idea would have been to just edit the nodes/tokens/trivia required to perform the wanted changes (In example, add a whitespace trivia before a specified token to perform indentation).
The issue is that it looks like it is mandatory to rebuild a SyntaxNode from scratch in order to be able to perform those edits, which will cause the same risk of losing information if I do not handle a certain type of node.

Would there be a possibility to:

1. Perform a deep-copy of a node in a non-const way
2. Edit this node or its children in whatever way I see fit (mainly changing tokens/trivia)
3. Re-inject this new node through the SyntaxRewriter::replace utility.

This way, I could be sure that no information is lost without my knowledge.

[suzizecat]

After looking around, I am starting to get a visitor that extract and present enough data to start actually formatting.

The issue I have now is that I don't quite see how to create/update trivia.

The point would be to inject a trivia with whitespaces for indentation/alignments of several parts of the code. However, it looks like I can only create a Trivia from a string_view and it seems to me that this is not the best course of action as it will be impractical to store a buffer for the string_view to refers to.

Setting aside creating the trivia, could you confirm that the way to update a token in a cloned syntax node with some new trivia would be to use something along the lines of

Token new_token = previous_token.withTrivia(a_bump_allocator,{my_trivia_1, my_trivia_2});
the_syntax_node.anAttribute = new_token;

given that the new_token will only have my_trivia_1 and my_trivia_2.

Also, about the BumpAllocator, what should be the lifetime of this object ?

1. Should I keep it along until I re-print the (formatted) syntax tree ?
2. Can I safely declare it in a local function ?
3. Should I keep it until the end of times ?

As far as I understand, that would be more the first option, but can I safely use it while mixing any kind of things to allocate ? (Is it a kind of "fast malloc" ?)

---

PS:
As of today (manipulating strings through the fmtlib for ease of prototyping), my proof of concept performs the following transformation (I have not quite managed the alignment within the ranges):

// Before
logic simple;
logic [1:0] single_packed;
logic [1:0][3:0] multi_packed;
logic [1:0][K_DIIM-1:0] multi_packed_param;
logic single_unpacked [3:0];

logic  multi_unpacked [3:0][31:0];
logic multi_unpacked_single [3][31];
logic multi_unpacked_weird [3][K_DIMENSION];

logic [1:0][15:0] full_mix [3][31];

//After 
logic                     simple             ;
logic   [1:0]             single_packed      ;
logic   [1:0][3:0]        multi_packed       ;
logic   [1:0][K_DIIM-1:0] multi_packed_param ;
logic                     single_unpacked     [3:0];

logic    multi_unpacked         [3:0][31:0];
logic    multi_unpacked_single  [3][31];
logic    multi_unpacked_weird   [3][K_DIMENSION];

logic   [1:0][15:0] full_mix  [3][31];

[MikePopoloski]

Yes, that looks like the right way to update the token's trivia.

You need to keep the BumpAllocator alive until anything that could possibly be referring to its memory is gone. Typically this means you no longer have any references to any tokens, syntax nodes, etc. Yes, it's kind of like a fast malloc, and it's even faster to free because everything stays alive together until the allocator is destroyed, and then everything is freed in one go.

Trivia objects are lightweight; the memory for their strings needs to live elsewhere. You can put that memory into the BumpAllocator as well.

[suzizecat]

So ! Now the issue is how to declare properly elements using the bump allocator.

I managed to have a functional PoC but it looks very convoluted to me.
Given that node is a DataDeclarationSyntax that I am visiting, I came up with:

slang::syntax::DataDeclarationSyntax* work = deepClone(*node,_mem);
std::cout << "Modifier pre-update: " << work->modifiers.toString() << std::endl;

//Temp token list for modifiers;
std::vector<slang::parsing::Token> tok_list;

//work->modifier is a TokenList
for(const auto& tok : work->modifiers)
{
	std::string spacing{" !-"}; // Will be an actual spacing.

	// Store the string in "persistent" memory (BumpAllocator)
	slang::byte* spacing_base = _mem.allocate(spacing.length(), alignof(char));
	std::memcpy(spacing_base,spacing.c_str(),spacing.length());
	
	// Declare and store the trivia, then create the token to add.
	Trivia* t = _mem.emplace<Trivia>(TriviaKind::Whitespace,std::string_view((char*)spacing_base,spacing.length()));
	tok_list.push_back(tok.withTrivia(_mem,{t,1}));
}

// Update the modifiers token list
work->modifiers = TokenList(tok_list);

std::cout << "Modifier post-update: " << work->modifiers.toString() << std::endl;

I feel that this is quite convoluted for "not much" but didn't find an example of code that would do this (as slang code works on the buffers that are properly stored at once). Would you have some insight ?

Anyway, on the line

const logic [1:0] foo;

this produces

Modifier pre-update: 
const
Modifier post-update:  !-const

Therefore, I feel that I am on the right path !

Thanks a lot for all the help you're providing !

[MikePopoloski]

You have the right idea. It's going to be clunky because the memory management is important, but once you have it figured out you can wrap it all up in some nice helper methods and make it look pretty for your actual rewriter logic so I wouldn't worry about it too much.

Some thoughts: if the string you're adding is an actual string literal (in this case " !=") then you don't need to allocate memory for it; string literals live in a fixed location in memory for the lifetime of the program so you can just pass a pointer to it without issue. You only need the alloc and copy for dynamically constructed strings.

Also you need to be careful about this line:

work->modifiers = TokenList(tok_list);

That saves a pointer to a local vector on the stack, so if you leave this function it will become garbage. You need to make sure that memory lives dynamically, again by using the BumpAllocator. If you use slang's SmallVector for this there is a handy utility method copy that will do what you need (this is a common idiom throughout the library):

BumpAllocator alloc;
SmallVector<Token> buffer;
for (...) {
    buffer.push_back(...);
}
work->modifiers = buffer.copy(alloc);

[suzizecat]

Some thoughts: if the string you're adding is an actual string literal (in this case " !=") then you don't need to allocate memory for it; string literals live in a fixed location in memory for the lifetime of the program so you can just pass a pointer to it without issue. You only need the alloc and copy for dynamically constructed strings.

Thanks for the heads up. I am not very familiar with string_views and a fair bit of the modern C++ stuff. In this situation, the spacing will be dynamically generated anyway.

Also you need to be careful about this line:

work->modifiers = TokenList(tok_list);

That saves a pointer to a local vector on the stack, so if you leave this function it will become garbage. You need to make sure that memory lives dynamically, again by using the BumpAllocator.

Yes, I saw it after posting.

Thanks for the tip about the small vector ! I was wondering how to conveniently create a range and such.
So I'll wrap the clunky part into a nice function and it should be OK.

[suzizecat]

The final kind of result I have is functions such as this one:

Token replace_spacing(slang::BumpAllocator& alloc , const Token& tok, const unsigned int space_number)
{
	// Store the string in "persistent" memory (BumpAllocator)
	if(space_number == 0)
		return tok.withTrivia(alloc,{});
	
	slang::byte* spacing_base = alloc.allocate(space_number, alignof(char));
	std::memset(spacing_base,' ',space_number);

	// Declare and store the trivia, then create the token to add.
	Trivia* t = alloc.emplace<Trivia>(TriviaKind::Whitespace,std::string_view((char*)spacing_base,space_number));
	return tok.withTrivia(alloc,{t,1});
}

This function should be used with caution (as it may remove too much trivias) but will allow to set the spacing of a single token easily.

With that done, using the modifiable version of the AST, created through clone, I can simply replace the targeted Token while being sure to not remove any meaningful content.

This is made with something like:

ast_node->token = replace_spacing(alloc, ast_node->token, number_of_spaces);

With that said, and with some more code, I get to convert:

// Before:

logic single_unpacked [3:0];
logic [1:0][K_DIM-1:0] multi_packed_param_and_more;
logic [1:THE_FOO][3:0] multi_packed;

logic multi_unpacked_weird [3][K_DIMENSION];
logic [1:0][15:0] full_mix [3][31];

logic simple;
logic [THE_LONG_BAR:0] single_packed; //! A comment

// Another signal
logic [1:0][K_DIM-1:0] multi_packed_param; //! Commented !

// This one is not aligned
    // This is a silly comment
static const logic  multi_unpacked [3:0][31:0];

logic multi_unpacked_single [3][31]; 

To

//After
 logic                        single_unpacked             [3:0];
 logic [1:0      ][K_DIM-1:0] multi_packed_param_and_more      ;
 logic [1:THE_FOO][3      :0] multi_packed                     ;
 
 logic             multi_unpacked_weird [3][K_DIMENSION];
 logic [1:0][15:0] full_mix             [3][31         ];
 
 logic                  simple       ;
 logic [THE_LONG_BAR:0] single_packed; //! A comment
 
 // Another signal
 logic [1:0][K_DIM-1:0] multi_packed_param; //! Commented !
 
 // This one is not aligned
 // This is a silly comment
 static const logic multi_unpacked [3:0][31:0];

So I would call this a success !