# WGSL Parser

A hand-rolled, zero-copy recursive-descent parser for WebGPU shading language,
written with [Gramatika](https://github.com/dannymcgee/gramatika).

## API

### Parsing a source file

```rs
use parser::{Parse, ParseStream, SyntaxTree};

const SOURCE_TEXT: &str = include_str!("path/to/some/shader.wgsl");

fn main() -> anyhow::Result<()> {
	let mut parser = ParseStream::from(SOURCE_TEXT);
	// The `SyntaxTree`
	let tree = parser.parse::<SyntaxTree>()?;
	// A tuple of `(ArcStr, Vec<Token>)`
	let (source, tokens) = parser.into_inner();

	Ok(())
}
```

### Tokenizing a source file without doing a full parse

```rs
use gramatika::Lexer as _;
use parser::Lexer;

const SOURCE_TEXT: &str = include_str!("path/to/some/shader.wgsl");

fn main() {
	let mut lexer = Lexer::new(SOURCE_TEXT.into());
	// `Vec<Token>`
	let tokens = lexer.scan();
}
```

## Syntax tree representation

A `SyntaxTree` contains a vector of `Decl`s representing the top-level syntax
types defined by the [WGSL grammar](https://www.w3.org/TR/WGSL/), e.g.:

* `Decl::Var(VarDecl { .. })`
	```wgsl
	@group(1) @binding(2)
	var<uniform> uniforms: Uniforms;
	```

* `Decl::Const(VarDecl { .. })`
	```wgsl
	const FOO: u32 = 1u;
	```

* `Decl::Struct(StructDecl { .. })`
	```wgsl
	struct Foo {
		foo: mat3x4<f32>,
		bar: vec2<u32>,
		baz: array<mat4x4<f32>, 256u>,
	}
	```

* `Decl::Function(FunctionDecl { .. })`
	```wgsl
	fn sum(a: f32, b: f32) -> f32 {
		return a + b;
	}
	```

The structures wrapped by those declarations can contain sub-declarations, e.g.:
* `Decl::Field(FieldDecl { .. })` inside of a `StructDecl`
* `Decl::Param(ParamDecl { .. })` inside of a `FunctionDecl`

The `body` of a `FunctionDecl` contains a vector of `Stmt`s.

`Stmt` is an enum in a form similar to `Decl`, with variants indicating the kind
of statement it represents, each wrapping an inner structure that describes the
syntax in further detail, often recursively, e.g.:

```
// NOTE: This is not valid Rust code, just a pseudo-code example of what some
//       `Stmt` might look like on the inside

Stmt::If(IfStmt {
	..
	else_branch: Some(ElseStmt {
		..
		body: Arc(Stmt::Block(BlockStmt {
			..
			stmts: Arc<[Stmt]>,
		})),
	}),
})
```

Finally, `Expr` is the "lowest" form of syntax in the tree, taking the same
general form as `Decl` and `Stmt` above.

### Inspecting a syntax tree

Each node of the syntax tree derives a bespoke `Debug` implementation, which
prints the tree in a format that's a sort of cross between Lisp (a format
commonly used for representing syntax trees) and Rust syntax.

That format looks like this:

```wgsl
max(4, 2) // The expression represented by the tree below
```
```
(Expr::Primary (PrimaryExpr
	expr: (Expr::FnCall (FnCallExpr
		ident: (IdentExpr::Leaf `max` (Function (1:1...1:4))),
		arguments: (ArgumentList
			brace_open: `(` (Brace (1:4...1:5)),
			arguments: [
				(Expr::Primary (PrimaryExpr
					expr: (Expr::Literal `4` (IntLiteral (1:5...1:6))),
				)),
				(Expr::Primary (PrimaryExpr
					expr: (Expr::Literal `2` (IntLiteral (1:8...1:9))),
				)),
			],
			brace_close: `)` (Brace (1:9...1:10)),
		),
	)),
))
```

### Traversing a syntax tree

The package exports a `Visitor` trait which can be implemented to efficiently
traverse the tree. `Visitor` defines a `visit_` method for each type of syntax
represented by the tree. `visit_` methods for nodes that contain child nodes
must return either `FlowControl::Continue` to traverse their children, or
`FlowControl::Break` to stop traversing the current branch.

The default `Visitor` implementation returns `FlowControl::Continue` for every
node, so you only need to actually implement the `visit_` methods that your
particular use case calls for:

```rs
use std::collections::HashMap;

use gramatika::{Substr, Token as _};
use parser::{
	decl::VarDecl,
	expr::{IdentExpr, NamespacedIdent},
	traversal::{FlowControl, Visitor, Walk},
	ParseStream, SyntaxTree,
};

#[derive(Default)]
struct ReferenceCounter {
	counts: HashMap<Substr, usize>,
}

impl Visitor for ReferenceCounter {
	fn visit_var_decl(&mut self, decl: &VarDecl) -> FlowControl {
		self.counts.insert(decl.name.lexeme(), 0);

		if let Some(ref expr) = decl.assignment {
			expr.walk(self);
		}

		FlowControl::Break
	}

	fn visit_ident_expr(&mut self, mut expr: &IdentExpr) {
		if let IdentExpr::Leaf(name) = expr {
			if let Some(count) = self.counts.get_mut(&name.lexeme()) {
				*count += 1;
			}
		}
	}
}

// Note: Not actually a robust implementation of a reference-counter,
//       but good enough for this toy example
pub fn count_references(tree: &SyntaxTree) -> HashMap<Substr, usize> {
	let mut visitor = ReferenceCounter::default();
	tree.walk(&mut visitor);

	visitor.counts
}
```