glast/

parser.rs

//! Types and functionality related to the parser.
//!
//! This module contains the structs and enums used to represent the AST (in the [`ast`] submodule), and the
//! [`parse_from_str()`]/[`parse_from_token_stream()`] functions that return a [`TokenTree`], which can be used to
//! parse the token tree into an abstract syntax tree ([`ParseResult`]).
//!
//! # Parser
//! This parser is (aiming to be) 100% specification compliant; that is, all valid source strings are parsed to
//! produce correct results with no compile-time errors, and all invalid source strings are parsed on a "best
//! effort" basis to produce some results and the correct compile-time errors.
//!
//! ## Macro expansion
//! This parser correctly deals with all macro expansion, no matter how arbitrarily complex. Macros are expanded in
//! all of the places that they are allowed to be expanded in. Because of the fact that macros can contain
//! partially-valid grammar that only becomes fully valid at the call site with surrounding context, the parser
//! discards information that a macro call site exists and just looks at the result of the expansion. Hence, the
//! final AST has no information about macro call sites. However, the syntax highlighting spans does correctly
//! colour macro call sites.
//!
//! ## Conditional compilation
//! This parser fully supports conditional compilation. Because conditional compilation is a pre-pass (part of the
//! preprocessor) that runs before the main parser, conditional compilation must be applied beforehand. This crate
//! handles this process through the [`TokenTree`] struct, which allows you to choose how to apply conditional
//! compilation. The following options are available:
//! - Conditional compilation is disabled - no branches are included.
//! - Conditional compilation is evaluated - branches are included according to the evaluation rules.
//! - Conditional compilation is enabled using a key - branches are included if they are part of a key.
//!
//! By default, syntax highlighting spans are only produced for the chosen branches. If you wish to highlight the
//! entire source string, all parsing functions have a `syntax_highlight_entire_file` boolean parameter.
//!
//! # Differences in behaviour
//! Since this crate is part of a larger effort to provide an LSP implementation, it is designed to handle errors
//! in a UX friendly manner. Therefore, this parser tries its best to recover from syntax errors in a sensible
//! manner and provide a "best effort" AST. The AST retains 100% semantic meaning of the token stream only if no
//! syntax or semantic errors are produced. If any errors are produced, that means some information has been lost
//! in the token stream-to-ast conversion.
//!
//! The GLSL specification does not mention what the result should be if a syntax/semantic error is encountered,
//! apart from the fact that a compile-time error must be emitted. The [`ParseResult`] contains all detected
//! compile-time diagnostics.

pub mod ast;
pub mod conditional_eval;
mod conditional_expression;
mod expression;
mod printing;
#[cfg(test)]
mod walker_tests;

use crate::{
	diag::{
		ExprDiag, PreprocConditionalDiag, PreprocDefineDiag, PreprocExtDiag,
		PreprocLineDiag, PreprocVersionDiag, Semantic, StmtDiag, Syntax,
	},
	lexer::{
		self,
		preprocessor::{
			ConditionToken, ExtensionToken, LineToken,
			TokenStream as PreprocStream, VersionToken,
		},
		OpTy, Token, TokenStream,
	},
	parser::conditional_expression::cond_parser,
	syntax::*,
	Either, GlslVersion, Span, SpanEncoding, Spanned,
};
use ast::*;
use expression::{expr_parser, Mode};
use std::collections::{HashMap, HashSet};

/// The result of a parsed GLSL token tree.
#[derive(Debug)]
pub struct ParseResult {
	/// The abstract syntax tree. By nature of this tree being parsed after having applied conditional compilation,
	/// it will not contain any conditional compilation directives.
	pub ast: Vec<Node>,
	/// All syntax diagnostics.
	pub syntax_diags: Vec<Syntax>,
	/// All semantic diagnostics. Since the parser only creates an AST and doesn't perform any further analysis
	/// (such as name resolution), this vector will only contain semantic errors in relation to macros.
	pub semantic_diags: Vec<Semantic>,
	/// The syntax highlighting tokens. If this result is obtained by calling a parsing method without enabling
	/// entire-file syntax highlighting, the tokens in this vector will only be for the contents of the abstract
	/// syntax tree. If entire-file syntax highlighting was enabled, the tokens will be for the entire token tree,
	/// (and will be correctly ordered).
	pub syntax_tokens: Vec<SyntaxToken>,
	/// Spans which cover any regions of disabled code. These regions map to conditional branches that have not
	/// been included. This vector is populated only if entire-file syntax highlighting was enabled, otherwise it
	/// will be empty.
	pub disabled_code_regions: Vec<Span>,
}

/// Parses a GLSL source string into a tree of tokens that can be then parsed into an abstract syntax tree.
///
/// This parser returns a [`TokenTree`] rather than the AST itself; this is required to support conditional
/// compilation. Because conditional compilation is applied through the preprocessor, there are no rules as to
/// where the parser can branch - a conditional branch could be introduced in the middle of a variable declaration
/// for instance. This makes it effectively impossible to represent all branches of a source string within a single
/// AST without greatly overcomplicating the entire parser, so multiple ASTs are needed to represent all the
/// conditional branch permutations.
///
/// The [`TokenTree`] struct allows you to pick which conditional branches to include, and then parse the source
/// string with that permutation to produce a [`ParseResult`]. Each permutation of all possible ASTs can be
/// accessed with a key that describes which of the conditional branches to include. The example below illustrates
/// this:
/// ```c
///                         // Order by appearance
///                         //  0 (root)
/// foo                     //  │                   
///                         //  │                   
/// #ifdef ...              //  │  1                
///     AAA                 //  │  │                
///                         //  │  │                
///         #ifdef ...      //  │  │  2             
///             50          //  │  │  │             
///         #else           //  │  │  3             
///             60          //  │  │  │             
///         #endif          //  │  │  ┴             
///                         //  │  │                
///     BBB                 //  │  │                
/// #elif ...               //  │  4                
///     CCC                 //  │  │                
/// #else                   //  │  5                
///     DDD                 //  │  │                
/// #endif                  //  │  ┴                
///                         //  │                   
/// #ifdef ...              //  │  6                
///     EEE                 //  │  │                
///                         //  │  │                
///         #ifdef ...      //  │  │  7             
///             100         //  │  │  │             
///         #endif          //  │  │  ┴             
/// #endif                  //  │  ┴                
///                         //  │                   
/// bar                     //  │                   
///                         //  ┴                   
/// ```
///
/// ## Conditional compilation is disabled
/// There is always a root token stream which has no conditional branches included. This can be accessed through
/// the [`root()`](TokenTree::root) method.
///
/// ## Conditional compilation is evaluated
/// Conditional branches are included if they evaluate to true according to the evaluation rules. This can be
/// accessed through the [`evaluate()`](TokenTree::evaluate) method.
///
/// ## Conditional compilation is enabled using a key
/// Conditional branches are included only if they are part of a key. This can be accessed through the
/// [`with_key`()](TokenTree::with_key) method.
///
/// A key is a list of integers which describes a set of conditional branches. Each encountered controlling
/// conditional directive (`#ifdef`/`#ifndef`/`#if`/`#elif`/`#else`) in the token stream is given an incrementing
/// number starting at `1`. If a key contains a given number `n`, that is equivalent to including the conditional
/// branch under the `n`th directive.
///
/// Some examples to visualise:
/// - `[1, 3]` will produce: `foo AAA 60 BBB bar`.
/// - `[4]` will produce: `foo CCC bar`.
/// - `[6, 7]` will produce: `foo EEE 100 bar`.
/// - `[1, 2, 6, 7]` will produce: `foo AAA 50 BBB EEE 100 bar`.
///
/// If you pass a key which doesn't form a valid permutation, the method will return an error. If you pass a key
/// which includes more than one conditional branch from the same block, the method will return an error.
///
/// # Examples
/// Parse a simple GLSL expression:
/// ```rust
/// # use glast::parser::{parse_from_str, ParseResult};
/// let src = r#"
/// ##version 450 core
/// int i = 5.0 + 1;
/// "#;
/// let tree = parse_from_str(&src).unwrap();
/// let ParseResult { ast, .. } = tree.root(false); // We don't care about extra
///                                                 // syntax highlighting information
/// ```
///
/// # Further reading
/// See the documentation for the [`TokenTree`] struct for a more in-depth explanation about why this seemingly
/// roundabout way of doing things is necessary.
pub fn parse_from_str(source: &str) -> Result<TokenTree, lexer::ParseErr> {
	let (token_stream, metadata) = lexer::parse(source)?;
	parse_from_token_stream(token_stream, metadata)
}

/// Parses a token stream into a tree of tokens that can be then parsed into an abstract syntax tree.
///
/// # Examples
/// See the documentation for the [`parse_from_str()`] function.
pub fn parse_from_token_stream(
	mut token_stream: TokenStream,
	metadata: lexer::Metadata,
) -> Result<TokenTree, lexer::ParseErr> {
	// Check the GLSL version as detected by the lexer.
	if metadata.version == GlslVersion::Unsupported && !token_stream.is_empty()
	{
		return Err(lexer::ParseErr::UnsupportedVersion(metadata.version));
	}

	// Skip tree generation if there are no conditional compilation directives, or if the token stream is empty.
	if !metadata.contains_conditional_directives || token_stream.is_empty() {
		let span = if !token_stream.is_empty() {
			Span::new(
				token_stream.first().unwrap().1.start,
				token_stream.last().unwrap().1.end,
			)
		} else {
			Span::new(0, 0)
		};
		return Ok(TokenTree {
			arena: vec![token_stream],
			tree: vec![TreeNode {
				parent: None,
				children: vec![Either::Left(TokenTree::ROOT_NODE_ID)],
				span,
			}],
			order_by_appearance: vec![],
			end_position: span.end,
			syntax_diags: vec![],
			contains_conditional_directives: false,
			span_encoding: metadata.span_encoding,
		});
	}

	// Below is a simple arena-based tree structure. Here is an example of how the source would be represented in
	// the tree:
	//
	// foo
	// #ifdef T
	//   AAA
	//     #ifdef Z
	//       90
	//
	//     #endif
	//   BBB
	// #else
	//   EEE
	// #endif
	// bar
	// baz
	//
	// Tree representation:
	//
	// Node(                                   0
	//     Tokens[foo],                        |
	//     Conditional{                        |
	//         if: Node(                       |  1
	//             Tokens[AAA],                |  |
	//             Conditional{                |  |
	//                 if: Node(               |  |  2
	//                     Tokens[90],         |  |  |
	//                 ),                      |  |  |
	//             },                          |  |
	//             Tokens[BBB],                |  |
	//         ),                              |  |
	//         else: Node(                     |  3
	//             Tokens[EEE],                |  |
	//         )                               |  |
	//     },                                  |
	//     Tokens[bar, baz],                   |
	// )
	//
	// order-by-appearance: [(0, [0]), (1, [0]), (2, [1, 0]), (3, [0])]

	let token_stream_end = token_stream.last().unwrap().1.end;

	let mut arena = Vec::new();
	let mut tree = vec![TreeNode {
		parent: None,
		children: Vec::new(),
		span: Span::new(0, 0),
	}];
	// A vector which creates a mapping between `order-of-appearance` -> `(node ID, parent node IDs)`. The parent
	// node IDs are tracked so that in the `with_key()` method we can check whether the key is valid.
	let mut order_by_appearance = vec![(0, vec![0])];
	let mut syntax_diags = Vec::new();

	// The current grouping of tokens. This is pushed into the arena whenever we encounter a branch that creates a
	// new tree node.
	let mut current_tokens = Vec::with_capacity(100);
	// The stack representing the IDs of currently nested nodes. The first ID always refers to the root node.
	// Invariant: Any time this is `pop()`ed a length check is made to ensure that `[0]` is always valid.
	let mut stack: Vec<NodeId> = vec![0];

	fn top(stack: &[NodeId]) -> NodeId {
		*stack.last().unwrap()
	}

	// We consume all of the tokens from the beginning.
	loop {
		let (token, token_span) = if !token_stream.is_empty() {
			token_stream.remove(0)
		} else {
			break;
		};

		match token {
			Token::Directive(d) => match d {
				PreprocStream::IfDef {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					let conditional_content_span = if tokens.is_empty() {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::ExpectedNameAfterIfDef(
								kw_span.next_single_width(),
							),
						));
						kw_span.next_single_width()
					} else if tokens.len() == 1 {
						Span::new(tokens[0].1.start, tokens[0].1.end)
					} else {
						// We have trailing tokens.
						let start = tokens[1].1.start;
						let end = tokens.last().unwrap().1.end;
						syntax_diags.push(Syntax::PreprocTrailingTokens(
							Span::new(start, end),
						));
						Span::new(start, end)
					};

					// Finish the current token group.
					let idx = arena.len();
					arena.push(std::mem::take(&mut current_tokens));
					tree.get_mut(top(&stack))
						.unwrap()
						.children
						.push(Either::Left(idx));

					// Create a new condition block, and a new node for the `ifdef` condition.
					let idx = tree.len();
					tree.push(TreeNode {
						parent: Some(top(&stack)),
						children: Vec::new(),
						span: token_span,
					});
					tree.get_mut(top(&stack)).unwrap().children.push(
						Either::Right(ConditionalBlock {
							conditions: vec![(
								Conditional::IfDef,
								token_span,
								tokens,
								conditional_content_span,
								idx,
								hash_syntax,
								name_syntax,
							)],
							end: None,
						}),
					);
					order_by_appearance.push((idx, stack.clone()));
					stack.push(idx);
				}
				PreprocStream::IfNotDef {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					let conditional_content_span = if tokens.is_empty() {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::ExpectedNameAfterIfDef(
								kw_span.next_single_width(),
							),
						));
						kw_span.next_single_width()
					} else if tokens.len() == 1 {
						Span::new(tokens[0].1.start, tokens[0].1.end)
					} else {
						// We have trailing tokens.
						let start = tokens[1].1.start;
						let end = tokens.last().unwrap().1.end;
						syntax_diags.push(Syntax::PreprocTrailingTokens(
							Span::new(start, end),
						));
						Span::new(start, end)
					};

					// Finish the current token group.
					let idx = arena.len();
					arena.push(std::mem::take(&mut current_tokens));
					tree.get_mut(top(&stack))
						.unwrap()
						.children
						.push(Either::Left(idx));

					// Create a new condition block, and a new node for the `ifdef` condition.
					let idx = tree.len();
					tree.push(TreeNode {
						parent: Some(top(&stack)),
						children: Vec::new(),
						span: token_span,
					});
					tree.get_mut(top(&stack)).unwrap().children.push(
						Either::Right(ConditionalBlock {
							conditions: vec![(
								Conditional::IfNotDef,
								token_span,
								tokens,
								conditional_content_span,
								idx,
								hash_syntax,
								name_syntax,
							)],
							end: None,
						}),
					);
					order_by_appearance.push((idx, stack.clone()));
					stack.push(idx);
				}
				PreprocStream::If {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					let conditional_content_span = if tokens.is_empty() {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::ExpectedExprAfterIf(
								kw_span.next_single_width(),
							),
						));
						kw_span.next_single_width()
					} else {
						Span::new(
							tokens.first().unwrap().1.start,
							tokens.last().unwrap().1.end,
						)
					};

					// Finish the current token group.
					let idx = arena.len();
					arena.push(std::mem::take(&mut current_tokens));
					tree.get_mut(top(&stack))
						.unwrap()
						.children
						.push(Either::Left(idx));

					// Create a new condition block, and a new node for the `if` condition.
					let idx = tree.len();
					tree.push(TreeNode {
						parent: Some(top(&stack)),
						children: Vec::new(),
						span: token_span,
					});
					tree.get_mut(top(&stack)).unwrap().children.push(
						Either::Right(ConditionalBlock {
							conditions: vec![(
								Conditional::If,
								token_span,
								tokens,
								conditional_content_span,
								idx,
								hash_syntax,
								name_syntax,
							)],
							end: None,
						}),
					);
					order_by_appearance.push((idx, stack.clone()));
					stack.push(idx);
				}
				PreprocStream::ElseIf {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					let conditional_content_span = if tokens.is_empty() {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::ExpectedExprAfterElseIf(
								kw_span.next_single_width(),
							),
						));
						kw_span.next_single_width()
					} else {
						Span::new(
							tokens.first().unwrap().1.start,
							tokens.last().unwrap().1.end,
						)
					};

					if stack.len() > 1 {
						// Finish the current token group for the previous conditional node.
						let idx = arena.len();
						arena.push(std::mem::take(&mut current_tokens));
						tree.get_mut(top(&stack))
							.unwrap()
							.children
							.push(Either::Left(idx));
						stack.pop();

						// By popping the stack, we are now pointing to the parent node that is the conditional
						// block.

						// Create a new node for the `elif` condition.
						let idx = tree.len();
						tree.push(TreeNode {
							parent: Some(top(&stack)),
							children: Vec::new(),
							span: token_span,
						});
						let node = tree.get_mut(top(&stack)).unwrap();
						node.span.end = token_span.end;
						let Either::Right(cond_block) = node.children.last_mut().unwrap() else { unreachable!() };
						cond_block.conditions.push((
							Conditional::ElseIf,
							token_span,
							tokens,
							conditional_content_span,
							idx,
							hash_syntax,
							name_syntax,
						));
						order_by_appearance.push((idx, stack.clone()));
						stack.push(idx);
					} else {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::UnmatchedElseIf(token_span),
						));
					}
				}
				PreprocStream::Else {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					// We are not expecting anything after `#else`.
					let conditional_content_span = if tokens.is_empty() {
						kw_span.next_single_width()
					} else {
						let span = Span::new(
							tokens.first().unwrap().1.start,
							tokens.last().unwrap().1.end,
						);
						syntax_diags.push(Syntax::PreprocTrailingTokens(span));
						span
					};

					if stack.len() > 1 {
						// Finish the current token group for the previous conditional node.
						let idx = arena.len();
						arena.push(std::mem::take(&mut current_tokens));
						tree.get_mut(top(&stack))
							.unwrap()
							.children
							.push(Either::Left(idx));
						stack.pop();

						// By popping the stack, we are now pointing to the parent node that is the conditional
						// block.

						// Create a new node for the `else` condition.
						let idx = tree.len();
						tree.push(TreeNode {
							parent: Some(top(&stack)),
							children: Vec::new(),
							span: token_span,
						});
						let node = tree.get_mut(top(&stack)).unwrap();
						node.span.end = token_span.end;
						let Either::Right(cond_block) = node.children.last_mut().unwrap() else { unreachable!() };
						cond_block.conditions.push((
							Conditional::Else,
							token_span,
							tokens,
							conditional_content_span,
							idx,
							hash_syntax,
							name_syntax,
						));
						order_by_appearance.push((idx, stack.clone()));
						stack.push(idx);
					} else {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::UnmatchedElse(token_span),
						));
					}
				}
				PreprocStream::EndIf {
					kw: kw_span,
					tokens,
				} => {
					let hash_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveHash,
						modifiers: SyntaxModifiers::empty(),
						span: token_span.first_char(),
					};
					let name_syntax = SyntaxToken {
						ty: SyntaxType::DirectiveName,
						modifiers: SyntaxModifiers::empty(),
						span: kw_span,
					};

					// We are not expecting anything after `#endif`.
					let conditional_content_span = if tokens.is_empty() {
						kw_span.next_single_width()
					} else {
						let span = Span::new(
							tokens.first().unwrap().1.start,
							tokens.last().unwrap().1.end,
						);
						syntax_diags.push(Syntax::PreprocTrailingTokens(span));
						span
					};

					if stack.len() > 1 {
						let node = tree.get_mut(top(&stack)).unwrap();
						node.span.end = token_span.end;
						// Finish the current token group for the previous conditional node.
						let idx = arena.len();
						arena.push(std::mem::take(&mut current_tokens));
						tree.get_mut(top(&stack))
							.unwrap()
							.children
							.push(Either::Left(idx));
						stack.pop();

						// By popping the stack, we are now pointing to the parent node that is the conditional
						// block.

						// Close the condition block.
						let node = tree.get_mut(top(&stack)).unwrap();
						node.span.end = token_span.end;
						let Either::Right(cond_block) = node.children.last_mut().unwrap() else { unreachable!() };
						cond_block.end = Some((
							Conditional::End,
							token_span,
							tokens,
							conditional_content_span,
							hash_syntax,
							name_syntax,
						));
					} else {
						syntax_diags.push(Syntax::PreprocConditional(
							PreprocConditionalDiag::UnmatchedEndIf(token_span),
						));
					}
				}
				_ => {
					let node = tree.get_mut(top(&stack)).unwrap();
					node.span.end = token_span.end;
					current_tokens.push((Token::Directive(d), token_span));
				}
			},
			_ => {
				let node = tree.get_mut(top(&stack)).unwrap();
				node.span.end = token_span.end;
				current_tokens.push((token, token_span));
			}
		}
	}

	// Finish the current group of remaining tokens.
	if !current_tokens.is_empty() {
		let idx = arena.len();
		arena.push(std::mem::take(&mut current_tokens));
		tree.get_mut(top(&stack))
			.unwrap()
			.children
			.push(Either::Left(idx));
	}
	stack.pop();

	// If we still have nodes on the stack, that means we have one or more unclosed condition blocks.
	if stack.len() > 0 {
		let node = tree.get_mut(top(&stack)).unwrap();
		node.span.end = token_stream_end;
		let Either::Right(cond) = node.children.last_mut().unwrap() else { unreachable!(); };
		syntax_diags.push(Syntax::PreprocConditional(
			PreprocConditionalDiag::UnclosedBlock(
				cond.conditions[0].1,
				Span::new(token_stream_end, token_stream_end),
			),
		));
	}

	// In order to make our job easier later down the line, for each conditional branch node ordered-by-appearance,
	// we want to know its node ID and the () for the parent nodes. The () consists of:
	// - The parent's position within `order_by_appearance`. <- We don't have this information yet.
	// - The parent's node ID.
	let old_order = order_by_appearance;
	let mut order_by_appearance = Vec::with_capacity(old_order.len());
	for (node_id, parents) in old_order.iter() {
		order_by_appearance.push((
			*node_id,
			parents
				.iter()
				.map(|node_id| {
					(
						old_order.iter().find(|(n, _)| node_id == n).unwrap().0,
						*node_id,
					)
				})
				.collect::<Vec<_>>(),
		))
	}

	Ok(TokenTree {
		arena,
		tree,
		order_by_appearance,
		end_position: token_stream_end,
		syntax_diags,
		contains_conditional_directives: true,
		span_encoding: metadata.span_encoding,
	})
}

/// Pretty-prints the AST.
///
/// The output is not stable and can be changed at any time, so the specific formatting should not be relied upon.
///
/// # Examples
/// Print a simple GLSL expression:
/// ```rust
/// # use glast::parser::{parse_from_str, print_ast, ParseResult};
/// let src = r#"
/// ##version 450 core
/// int i = 5.0 + 1;
/// "#;
/// let tree = parse_from_str(&src).unwrap();
/// let ParseResult { ast, .. } = tree.root(false);
/// println!("{}", print_ast(&ast));
/// ```
/// Would result in:
/// ```text
/// #Version(
///     version: 450
///     profile: core
/// ),
/// VarDef(
///     type: int
///     ident: i
///     value: BinOp(
///         op: +
///         left: 5.0
///         right: 1
///     )
/// )
/// ```
pub fn print_ast(ast: &[Node]) -> String {
	printing::print_ast(ast)
}

/// The error type for parsing operations.
#[derive(Debug)]
pub enum ParseErr {
	/// This number doesn't map to a controlling conditional directive.
	InvalidNum(usize),
	/// This number has a dependent number that was not specified in the key.
	InvalidChain(usize),
	/// This tree contains no conditional compilation branches.
	NoConditionalBranches,
}

/// A tree of token streams generated from a GLSL source string.
///
/// The tree represents all conditional compilation branches. Call the [`root()`](Self::root),
/// [`evaluate()`](Self::evaluate) or [`with_key()`](Self::with_key) method to parse an abstract syntax tree with
/// the selected conditional branches into a [`ParseResult`].
///
/// # Examples
/// For a fully detailed example on how to use this struct to create an AST, see the documentation for the
/// [`parse_from_str()`] function.
///
/// # Why is this necessary?
/// Conditional compilation is implemented through the preprocessor, which sets no rules as to where conditional
/// branching can take place, (apart from the fact that a preprocessor directive must exist on its own line). This
/// means that a conditional branch could, for example, completely change the signature of a program:
/// ```c
///  1│ void foo() {
///  2│
///  3│     int i = 5;
///  4│
///  5│     #ifdef TOGGLE
///  6│     }
///  7│     void bar() {
///  8│     #endif
///  9│
/// 10│     int p = 0;
/// 11│ }
/// ```
/// In the example above, if `TOGGLE` is not defined, we have a function `foo` who's scope ends on line `11` and
/// includes two variable definitions `i` and `p`. However, if `TOGGLE` is defined, the function `foo` ends on line
/// `6` instead and only contains the variable `i`, and we have a completely new function `bar` which has the
/// variable `p`.
///
/// This technically can be representable in the AST, it's just that it would look something like this:
/// ```text
/// Root(
///     Either(
///         (
///             Function(
///                 name="foo"
///                 start=1
///                 end=11
///                 contents(
///                     Variable(name="i" value=5)
///                     Variable(name="p" value=0)
///                 )
///             )
///         ),
///         (
///             Function(
///                 name="foo"
///                 start=1
///                 end=6
///                 contents(
///                     Variable(name="i" value=5)
///                 )
///             ),
///             Function(
///                 name="bar"
///                 start=7
///                 end=11
///                 contents(
///                     Variable(name="p" value=0)
///                 )
///             ),
///         )
///     )
/// )
/// ```
/// Notice how this AST is effectively `Either(AST_with_condition_false, AST_with_condition_true)`. This is because
/// the function `foo` could potentially be split in the middle, but an AST node cannot have multiple end points,
/// which means that we can't include both permutations within the function node; we need separate function nodes
/// instead. And since we have two separate possibilities for `foo`, we need to branch in the node above `foo`,
/// which in this example is effectively the root node.
///
/// It is arguable whether such a representation would be better than the current solution. On one hand all
/// possibilities are within the single AST, but on the other hand such an AST would quickly become confusing to
/// work with, manipulate, and analyse in the scenario of complex conditional branching.
///
/// The main reason this option wasn't chosen is because it would immensely complicate the parsing logic, and in
/// turn the maintainability of this project. As with all recursive-descent parsers, the individual parsing
/// functions hold onto any temporary state. In this case, the function for parsing functions holds information
/// such as the name, the starting position, the parameters, etc. If we would encounter the conditional branching
/// within this parsing function, we would somehow need to know ahead-of-time whether this conditional branch will
/// affect the function node, and if so, be able to return up the call stack to split the parser whilst also
/// somehow not losing the temporary state. This would require abandoning the recursive-descent approach, which
/// would greatly complicate the parser and make writing & maintaining the parsing logic itself a convoluted mess,
/// and that is not a trade-off I'm willing to take.
///
/// This complication occurs because the preprocessor is a separate pass ran before the main compiler and does not
/// follow the GLSL grammar rules, which means that preprocessor directives and macros can be included literally
/// anywhere and the file *may* still be valid after expansion. In comparison, some newer languages include
/// conditional compilation as part of the language grammar itself. In Rust for example, conditional compilation is
/// applied via attributes to entire expressions/statements, which means that you can't run into this mess where a
/// conditional branch could split a function mid-way through parsing. GLSL unfortunately uses the C preprocessor,
/// which results in the approach taken by this crate being necessary to achieve 100% specification-compliant
/// behaviour.
///
/// Note that macros can actually be correctly expanded within the same pass as the main parser without introducing
/// too much complexity, it's just that conditional compilation can't.
pub struct TokenTree {
	/// The arena of token streams.
	///
	/// # Invariants
	/// If `contains_conditional_directives` is `false`, this vector is:
	/// ```ignore
	/// vec![enitire_token_stream]
	/// ```
	arena: Vec<TokenStream>,
	/// The tree.
	///
	/// # Invariants
	/// `self.[0]` always exists and is the root node.
	///
	/// If `contains_conditional_directives` is `false`, this vector is:
	/// ```ignore
	/// vec![TreeNode {
	///     parent: None,
	///     children: vec![Either::Left(Self::ROOT_NODE_ID)]
	/// }]
	/// ```
	tree: Vec<TreeNode>,
	/// IDs of the conditional branch nodes ordered by appearance.
	///
	/// - `0` - The ID of the `[n]`th conditional branch node.
	/// - `1` - The `(index into self, node ID)` of the parent nodes which this conditional branch node depends on.
	///
	/// # Invariants
	/// If `contains_conditional_directives` is `false`, this is empty.
	///
	/// If this contains entries, each `self[n].1[0]` is guaranteed to exist and be of value `(0,
	/// Self::ROOT_NODE_ID)`. Also, `self[0]` is guaranteed to exist, (and point to the root node).
	order_by_appearance: Vec<(NodeId, Vec<(usize, NodeId)>)>,
	/// The ending position of the last token in the tree.
	end_position: usize,

	/// Syntax diagnostics related to conditional compilation directives. Note that this vector won't contain any
	/// syntax diagnostics in relation to conditional expressions, since those are not evaluated here.
	///
	/// # Invariants
	/// If `contains_conditional_directives` is `false`, this is empty.
	syntax_diags: Vec<Syntax>,

	/// Whether there are any conditional directives.
	contains_conditional_directives: bool,
	/// The type of encoding of spans.
	span_encoding: SpanEncoding,
}

type NodeId = usize;
type ArenaId = usize;

/// A node within the token tree.
#[derive(Debug)]
struct TreeNode {
	/// The parent of this node.
	parent: Option<NodeId>,
	/// The children/contents of this node. Each entry either points to a token stream (in the arena), or is a
	/// conditional block which points to child nodes for each conditional branch.
	children: Vec<Either<ArenaId, ConditionalBlock>>,
	/// The span of the entire node.
	///
	/// If this is a conditional branch node, the span starts from the beginning of the controlling conditional
	/// directive to the beginning of the next `#elif`/`#else` directive, or to the end of the `#endif` directive.
	span: Span,
}

/// A conditional block, part of a `TreeNode`.
#[derive(Debug)]
struct ConditionalBlock {
	/// The individual conditional branches.
	///
	/// - `0` - The type of condition.
	/// - `1` - The span of the entire directive.
	/// - `2` - The tokens in the directive.
	/// - `3` - The span of the tokens **only**, this does not include the `#if` part.
	/// - `4` - The ID of the node that contains the contents of the branch.
	/// - `5` - The syntax highlighting token for the `#` symbol.
	/// - `6` - The syntax highlighting token for the name of the directive.
	///
	/// # Invariants
	/// There will always be an entry at `[0]` and it will be a `Conditional::IfDef/IfNotDef/If` variant.
	///
	/// This will never contain a `Conditional::End` variant.
	conditions: Vec<(
		Conditional,
		Span,
		Vec<Spanned<ConditionToken>>,
		Span,
		NodeId,
		SyntaxToken,
		SyntaxToken,
	)>,
	/// The `#endif` directive.
	///
	/// This is separate because the `#endif` doesn't contain any children, (since it ends the conditional block),
	/// hence a `NodeId` for this would be semantically nonsensical.
	///
	/// - `0` - The type of conditional directive.
	/// - `1` - The span of the entire directive.
	/// - `2` - The tokens in the directive.
	/// - `3` - The span of the tokens **only**, this does not include the `#endif` part.
	/// - `4` - The syntax highlighting token for the `#` symbol.
	/// - `5` - The syntax highlighting token for the `endif` directive name.
	///
	/// # Invariants
	/// This will be a `Conditional::End` variant.
	end: Option<(
		Conditional,
		Span,
		Vec<Spanned<ConditionToken>>,
		Span,
		SyntaxToken,
		SyntaxToken,
	)>,
}

/// Describes the type of a conditional directive.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Conditional {
	IfDef,
	IfNotDef,
	If,
	ElseIf,
	Else,
	End,
}

impl TokenTree {
	/// Node ID of the root node.
	const ROOT_NODE_ID: usize = 0;

	/// Parses the root token stream; no conditional branches are included.
	///
	/// Whilst this is guaranteed to succeed, if the entire source string is wrapped within a conditional block
	/// this will return an empty AST.
	///
	/// # Syntax highlighting
	/// The `syntax_highlight_entire_source` parameter controls whether to produce syntax tokens for the entire
	/// source string, rather than just for the root tokens. This involves parsing all conditional branches in
	/// order to produce all the syntax highlighting information. Whilst the implementation of this functionality
	/// uses the smallest possible number of permutations that cover the entire source string, if there are a lot
	/// of conditional branches that can result in the token tree being parsed many times which may have
	/// performance implications.
	///
	/// The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If
	/// you require more control, you must manually parse the relevant permutations and collect the tokens
	/// yourself.
	///
	/// If there are no conditional branches, this parameter does nothing.
	///
	/// # Examples
	/// For a fully detailed example on how to use this method to create an abstract syntax tree, see the
	/// documentation for the [`parse_from_str()`] function.
	pub fn root(&self, syntax_highlight_entire_source: bool) -> ParseResult {
		// Get the relevant streams for the root branch.
		let streams = if !self.contains_conditional_directives {
			self.arena.clone()
		} else {
			let mut streams = Vec::new();
			let node = &self.tree[Self::ROOT_NODE_ID];
			for child in &node.children {
				match child {
					Either::Left(idx) => streams.push(self.arena[*idx].clone()),
					// Ignore any conditional blocks under the root node.
					Either::Right(_) => {}
				}
			}
			streams
		};

		// Parse the root branch.
		let mut walker = Walker::new(
			RootTokenStreamProvider::new(streams, self.end_position),
			self.span_encoding,
		);
		let mut nodes = Vec::new();
		while !walker.is_done() {
			parse_stmt(&mut walker, &mut nodes);
		}
		walker.syntax_diags.append(&mut self.syntax_diags.clone());
		let (ast, syntax_diags, semantic_diags, mut root_tokens) = (
			nodes,
			walker.syntax_diags,
			walker.semantic_diags,
			walker.syntax_tokens,
		);

		if syntax_highlight_entire_source
			&& self.contains_conditional_directives
		{
			let mut merged_syntax_tokens =
				Vec::with_capacity(root_tokens.len());
			// This will store the regions of the conditional blocks.
			let mut conditional_block_regions = Vec::new();

			let keys = self
				.minimal_no_of_permutations_for_complete_syntax_highlighting();

			// Move over any root tokens before any conditional blocks.
			let first_node = &self.tree[keys[0][0]];
			let span = Span::new(0, first_node.span.start);
			loop {
				match root_tokens.get(0) {
					Some(token) => {
						if span.contains(token.span) {
							merged_syntax_tokens.push(root_tokens.remove(0));
						} else {
							break;
						}
					}
					None => break,
				}
			}

			// Deal with all tokens produced from conditional branches, as well as any root tokens in-between
			// the conditional blocks.
			for (i, key) in keys.iter().enumerate() {
				let node = &self.tree[key[0]];
				conditional_block_regions.push(node.span);

				let (
					ParseResult {
						syntax_tokens: mut new_tokens,
						..
					},
					_,
				) = self.parse_nodes(key);
				loop {
					let SyntaxToken { span: s, .. } = match new_tokens.get(0) {
						Some(t) => t,
						None => break,
					};

					if s.is_before_pos(node.span.start) {
						new_tokens.remove(0);
						continue;
					}

					if node.span.contains(*s) {
						merged_syntax_tokens.push(new_tokens.remove(0));
					} else {
						break;
					}
				}

				if let Some(next_key) = keys.get(i + 1) {
					let next_node = &self.tree[next_key[0]];
					let span = Span::new(node.span.end, next_node.span.start);
					if !span.is_zero_width() {
						// We have another conditional block after this one; there may be root tokens in-between
						// these two blocks which require moving over.
						loop {
							let SyntaxToken { span: s, .. } =
								match root_tokens.get(0) {
									Some(t) => t,
									None => break,
								};

							if span.contains(*s) {
								merged_syntax_tokens
									.push(root_tokens.remove(0));
							} else {
								break;
							}
						}
					}
				}
			}

			// Append any remaining root tokens.
			merged_syntax_tokens.append(&mut root_tokens);

			ParseResult {
				ast,
				syntax_diags,
				semantic_diags,
				syntax_tokens: merged_syntax_tokens,
				disabled_code_regions: conditional_block_regions,
			}
		} else {
			ParseResult {
				ast,
				syntax_diags,
				semantic_diags,
				syntax_tokens: root_tokens,
				disabled_code_regions: Vec::new(),
			}
		}
	}

	/// Parses the token tree by including conditional branches if they evaluate to true.
	///
	/// Whilst this is guaranteed to succeed, if the entire source string is wrapped within a conditional branch
	/// that fails evaluation this will return an empty AST. This method also returns the evaluated key.
	///
	/// # Syntax highlighting
	/// The `syntax_highlight_entire_source` parameter controls whether to produce syntax tokens for the entire
	/// source string, rather than just for the included conditional branches. This involves parsing **all**
	/// conditional branches in order to produce all the syntax highlighting information. Whilst the implementation
	/// of this functionality uses the smallest possible number of permutations that cover the entire source
	/// string, if there are a lot of conditional branches that can result in the token tree being parsed many
	/// times which may have performance implications.
	///
	/// The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If
	/// you require more control, you must manually parse the relevant permutations and collect the tokens
	/// yourself.
	///
	/// If there are no conditional branches, or the only conditional branches that exist are also evaluated as
	/// true and included in the running of the parser, this parameter does nothing.
	///
	/// # Examples
	/// For a fully detailed example on how to use this method to create an abstract syntax tree, see the
	/// documentation for the [`parse_from_str()`] function.
	pub fn evaluate(
		&self,
		syntax_highlight_entire_source: bool,
	) -> (ParseResult, Vec<usize>) {
		// Parse the token tree, evaluating conditional compilation.
		let mut walker = Walker::new(
			DynamicTokenStreamProvider::new(
				&self.arena,
				&self.tree,
				self.end_position,
			),
			self.span_encoding,
		);
		let mut nodes = Vec::new();
		while !walker.is_done() {
			parse_stmt(&mut walker, &mut nodes);
		}
		walker.syntax_diags.append(&mut self.syntax_diags.clone());

		let eval_key = walker.token_provider.chosen_key;
		let eval_regions = walker.token_provider.chosen_regions;
		let (ast, syntax_diags, semantic_diags, eval_tokens) = (
			nodes,
			walker.syntax_diags,
			walker.semantic_diags,
			walker.syntax_tokens,
		);

		let (syntax_tokens, disabled_code_regions) =
			if syntax_highlight_entire_source
				&& self.contains_conditional_directives
			{
				self.merge_syntax_tokens(
					eval_key.clone(),
					eval_regions,
					eval_tokens,
				)
			} else {
				(eval_tokens, Vec::new())
			};

		(
			ParseResult {
				ast,
				syntax_diags,
				semantic_diags,
				syntax_tokens,
				disabled_code_regions,
			},
			eval_key,
		)
	}

	/// Parses a token tree by including conditional branches if they are part of the provided key.
	///
	/// This method can return an `Err` in the following cases:
	/// - The `key` has a number which doesn't map to a controlling conditional directive.
	/// - The `key` has a number which depends on another number that is missing.
	///
	/// # Syntax highlighting
	/// The `syntax_highlight_entire_source` parameter controls whether to produce syntax tokens for the entire
	/// source string, rather than just for the selected conditional branches. This involves parsing all
	/// conditional branches in order to produce all the syntax highlighting information. Whilst the implementation
	/// of this functionality uses the smallest possible number of permutations that cover the entire source
	/// string, if there are a lot of conditional branches that can result in the token tree being parsed many
	/// times which may have performance implications.
	///
	/// The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If
	/// you require more control, you must manually parse the relevant permutations and collect the tokens
	/// yourself.
	///
	/// If there are no conditional branches, this parameter does nothing.
	///
	/// # Examples
	/// For a fully detailed example on how to use this method to create an abstract syntax tree, see the
	/// documentation for the [`parse_from_str()`] function.
	pub fn with_key(
		&self,
		key: impl AsRef<[usize]>,
		syntax_highlight_entire_source: bool,
	) -> Result<ParseResult, ParseErr> {
		let key = key.as_ref();

		if !self.contains_conditional_directives {
			return Err(ParseErr::NoConditionalBranches);
		}

		let mut nodes = Vec::with_capacity(key.len());
		// Check that the key is valid.
		let mut visited_node_ids = vec![0];
		for num in key {
			let (id, required_ids) = match self.order_by_appearance.get(*num) {
				Some(t) => t,
				None => return Err(ParseErr::InvalidNum(*num)),
			};

			// Panic: See `self.order_by_appearance` invariant.
			if !visited_node_ids.contains(&required_ids.last().unwrap().1) {
				return Err(ParseErr::InvalidChain(*num));
			}

			visited_node_ids.push(*id);
			nodes.push(*id);
		}

		let (
			ParseResult {
				ast,
				syntax_diags,
				semantic_diags,
				syntax_tokens,
				disabled_code_regions: _,
			},
			chosen_regions,
		) = self.parse_nodes(&nodes);

		let (syntax_tokens, disabled_code_regions) =
			if syntax_highlight_entire_source
				&& self.contains_conditional_directives
			{
				self.merge_syntax_tokens(nodes, chosen_regions, syntax_tokens)
			} else {
				(syntax_tokens, Vec::new())
			};

		Ok(ParseResult {
			ast,
			syntax_diags,
			semantic_diags,
			syntax_tokens,
			disabled_code_regions,
		})
	}

	/// Parses the specified nodes.
	///
	/// Returns a `ParseResult` along with a vector of chosen regions.
	///
	/// # Invariants
	/// At least one node ID needs to be specified.
	///
	/// The IDs of the nodes need to be in chronological order.
	///
	/// The IDs need to map to a valid permutation of conditional branches.
	fn parse_nodes(&self, nodes: &[NodeId]) -> (ParseResult, Vec<Span>) {
		if nodes.is_empty() {
			panic!("Expected at least one node to parse");
		}

		let mut streams = Vec::new();
		let mut chosen_regions = Vec::new();
		let mut conditional_syntax_tokens = Vec::new();
		let mut nodes_idx = 0;
		let mut call_stack = vec![(0, 0, 0, -1)];
		// Panic: We have at least one node, so at least one iteration of this loop can be performed without
		// any panics.
		'outer: loop {
			let (node_id, child_idx, cond_block_idx, evaluated_cond_block) =
				match call_stack.last_mut() {
					Some(t) => t,
					None => break,
				};
			let node = &self.tree[*node_id];
			let Some(child) = node.children.get(*child_idx) else { break; };

			match child {
				Either::Left(arena_id) => {
					let stream = self.arena[*arena_id].clone();

					if let Some((_, span)) = stream.last() {
						chosen_regions.push(Span::new(
							stream.first().unwrap().1.start,
							span.end,
						));
					}

					*child_idx += 1;
					if *child_idx == node.children.len() {
						// We have gone through all of the children of this node, so we want to pop it from the
						// stack.
						call_stack.pop();
					}

					streams.push(stream);
				}
				Either::Right(cond_block) => {
					let matched_condition_node_id;
					loop {
						if *cond_block_idx == cond_block.conditions.len() {
							// We've gone through all of the conditional blocks. We can now push the syntax tokens
							// for the `#endif` and move onto the next child of this node.
							if let Some((
								_,
								directive_span,
								syntax_tokens,
								_,
								hash_token,
								dir_token,
							)) = &cond_block.end
							{
								let mut tokens = vec![*hash_token, *dir_token];
								if !syntax_tokens.is_empty() {
									tokens.push(SyntaxToken {
										ty: SyntaxType::Invalid,
										modifiers: SyntaxModifiers::CONDITIONAL,
										span: Span::new(
											syntax_tokens
												.first()
												.unwrap()
												.1
												.start,
											syntax_tokens.last().unwrap().1.end,
										),
									});
								}
								conditional_syntax_tokens.push(tokens);

								if *evaluated_cond_block
									== cond_block.conditions.len() as isize - 1
								{
									// We have either chosen the final conditional branch, which means we are
									// responsible for syntax highlighting the `#endif` directive. (This is only
									// relevant if we are syntax highlighting the entire file). The reason we can't
									// do this unconditionally is because if the final block wasn't picked, then an
									// alternative permutation is responsible for syntax highlighting it, but the
									// span of the syntax highlight region stretches to cover the `#endif` part. If
									// we declared this as chosen, the other span region wouldn't fit and would
									// therefore be discarded, and hence syntax highlighting would be missing for
									// the final branch.
									chosen_regions.push(*directive_span);
								}
							}

							*cond_block_idx = 0;
							*child_idx += 1;
							*evaluated_cond_block = -1;
							if *child_idx == node.children.len() {
								// We have gone through all of the children of this node, so we want to pop it from
								// the stack.
								call_stack.pop();
							}

							continue 'outer;
						}

						let current_cond_block_idx = *cond_block_idx;

						let (
							_,
							directive_span,
							syntax_tokens,
							_,
							branch_node_id,
							hash_token,
							dir_token,
						) = &cond_block.conditions[current_cond_block_idx];

						*cond_block_idx += 1;

						match nodes.get(nodes_idx) {
							Some(n) => {
								if *branch_node_id == *n {
									// We have found a matching branch.
									let mut tokens =
										vec![*hash_token, *dir_token];
									for (token, span) in syntax_tokens.iter() {
										tokens.push(SyntaxToken {
											ty: token.non_semantic_colour(),
											modifiers:
												SyntaxModifiers::CONDITIONAL,
											span: *span,
										});
									}
									conditional_syntax_tokens.push(tokens);

									matched_condition_node_id = *branch_node_id;
									*evaluated_cond_block =
										current_cond_block_idx as isize;
									chosen_regions.push(*directive_span);
									break;
								}
							}
							None => {}
						}
					}

					call_stack.push((matched_condition_node_id, 0, 0, -1));
					nodes_idx += 1;
					continue;
				}
			}
		}

		// Parse the pre-selected branches.
		let mut walker = Walker::new(
			PreselectedTokenStreamProvider::new(
				streams,
				conditional_syntax_tokens,
				self.end_position,
			),
			self.span_encoding,
		);
		let mut nodes = Vec::new();
		while !walker.is_done() {
			parse_stmt(&mut walker, &mut nodes);
		}
		walker.syntax_diags.append(&mut self.syntax_diags.clone());

		(
			ParseResult {
				ast: nodes,
				syntax_diags: walker.syntax_diags,
				semantic_diags: walker.semantic_diags,
				syntax_tokens: walker.syntax_tokens,
				disabled_code_regions: Vec::new(),
			},
			chosen_regions,
		)
	}

	/// Merges syntax tokens from other keys to cover the entire file.
	///
	/// This method takes the chosen key, the chosen regions, and syntax tokens from said chosen key. If there are
	/// no other permutations, this will return the syntax tokens verbatim.
	fn merge_syntax_tokens(
		&self,
		chosen_key: Vec<usize>,
		chosen_regions: Vec<Span>,
		mut chosen_tokens: Vec<SyntaxToken>,
	) -> (Vec<SyntaxToken>, Vec<Span>) {
		let mut other_keys =
			self.minimal_no_of_permutations_for_complete_syntax_highlighting();
		// We want to exclude the key that we've already chosen. If that leaves no keys left, we know we've already
		// covered the entire tree, so we can return early.
		other_keys.retain(|k| k != &chosen_key);
		if other_keys.is_empty() {
			return (chosen_tokens, Vec::new());
		}

		// Parse all of the keys and store relevant information.
		// `(key, parse_result, chosen_spans)`.
		let mut other_keys = other_keys
			.into_iter()
			.map(|k| {
				let (a, b) = self.parse_nodes(&k);
				(k, a, b)
			})
			.collect::<Vec<_>>();

		// This will store the calculated regions of disabled code in the context of the chosen key.
		let mut disabled_regions_for_chosen_key = Vec::new();
		// This will store the regions of tokens (with the key they came from) in a chronological order that covers
		// the entire source string.
		let mut final_regions_with_key = Vec::new();

		let mut span_to_next_chosen_region =
			Span::new(0, chosen_regions.first().map(|s| s.start).unwrap_or(0));
		let mut chosen_regions_idx = 0;
		// We toggle between consuming regions from the chosen key and consuming regions from the other keys on
		// each iteration on the loop.
		let mut consuming_chosen = false;
		loop {
			if !consuming_chosen {
				// We create a vector of all regions from the other keys that can fit before the next region in the
				// chosen key.
				let mut regions_that_can_fit = Vec::new();
				for (key, _, regions) in other_keys.iter() {
					for region in regions {
						if span_to_next_chosen_region.contains(*region) {
							regions_that_can_fit.push((*region, key.clone()));
						}
					}
				}

				// We sort the vector chronologically and remove any duplicates. It doesn't matter which duplicate
				// we remove since they will be identical.
				regions_that_can_fit.sort_by(|a, b| {
					if a.0.is_before(&b.0) {
						std::cmp::Ordering::Less
					} else if a.0.is_after(&b.0) {
						std::cmp::Ordering::Greater
					} else {
						std::cmp::Ordering::Equal
					}
				});
				regions_that_can_fit.dedup_by(|a, b| a.0 == b.0);

				// This vector is also a list of disabled regions from the perspective of the chosen key, so we
				// want to append it.
				regions_that_can_fit.iter().for_each(|(span, _)| {
					disabled_regions_for_chosen_key.push(*span)
				});

				final_regions_with_key.append(&mut regions_that_can_fit);

				if chosen_regions_idx == chosen_regions.len() {
					break;
				}
				consuming_chosen = true;
			} else {
				// We push the next region from the chosen key.
				let current_region = chosen_regions[chosen_regions_idx];
				final_regions_with_key
					.push((current_region, chosen_key.clone()));
				match chosen_regions.get(chosen_regions_idx + 1) {
					Some(next) => {
						span_to_next_chosen_region =
							Span::new(current_region.end, next.start);
					}
					None => {
						span_to_next_chosen_region =
							Span::new(current_region.end, self.end_position);
					}
				}

				chosen_regions_idx += 1;
				consuming_chosen = false;
			}
		}

		// We now have a vector of chronologically ordered regions along with the key we should take tokens from.
		// We can now create a new vector that contains all of these tokens.
		let mut merged_syntax_tokens = Vec::with_capacity(chosen_tokens.len());
		for (range, key) in final_regions_with_key {
			let tokens = if key == chosen_key {
				&mut chosen_tokens
			} else {
				&mut other_keys
					.iter_mut()
					.find(|(k, _, _)| k == &key)
					.unwrap()
					.1
					.syntax_tokens
			};

			loop {
				let Some(token) = tokens.get(0) else { break; };

				if token.span.is_before(&range) {
					// This token is before the current range. We clearly have already gone past it, so it can
					// safely be discarded.
					tokens.remove(0);
				} else if range.contains(token.span) {
					merged_syntax_tokens.push(tokens.remove(0));
				} else {
					// This token is after the current range. We haven't gotten there yet, so that means we can
					// finish dealing with this token stream for now.
					break;
				}
			}
		}

		(merged_syntax_tokens, disabled_regions_for_chosen_key)
	}

	/// Returns all of the keys (**of node IDs, not order-of-appearance numbers**) required to fully syntax
	/// highlight the entire tree.
	///
	/// Each key points to the conditional branch nodes that contain the actual tokens of the conditional branch.
	/// To get information about the controlling conditional directive itself, you must look up the parent and find
	/// the node ID in one of the child's conditional blocks.
	fn minimal_no_of_permutations_for_complete_syntax_highlighting(
		&self,
	) -> Vec<Vec<NodeId>> {
		// TODO: Merge permutations that have no collisions, such as the first branch from the first conditional
		// block with the first branch from the second conditional block. It may make sense to replace the
		// `order_by_appearance` traversal with a manual stack traversal of the tree.

		let mut chains_of_nodes = Vec::new();
		for (id, required_ids) in self.order_by_appearance.iter().skip(1) {
			let mut new_chain = required_ids[1..]
				.iter()
				.map(|(_, id)| *id)
				.collect::<Vec<_>>();
			new_chain.push(*id);

			// We may have a chain of nodes which fully fits within this new chain. For example, we could have a
			// chain `[0, 4]`, and the new chain we have is `[0, 4, 5]`. In this case, the existing chain is wholly
			// unnecessary because all of the lines of code in that chain will be covered in this new chain, (plus
			// the lines of code in the new `5` branch). Since we are trying to find the minimal number of
			// permutations to cover the whole file, we can discard the existing chain.

			// See if any existing chains are contained within the new one.
			let idx = chains_of_nodes
				.iter()
				.position(|v: &Vec<usize>| new_chain.starts_with(v.as_ref()));

			if let Some(idx) = idx {
				// `idx` points to an existing chain of nodes that is part of the new chain of nodes being added
				// right now. That means the existing chain can be removed because this new chain will cover 100%
				// of the old chain.
				chains_of_nodes.remove(idx);
			}

			chains_of_nodes.push(new_chain);
		}
		chains_of_nodes
	}

	/// Returns a vector of all controlling conditional directives in the tree.
	///
	/// The return value consists of:
	/// - `0` - The conditional directive type. This cannot be `Conditional::End`.
	/// - `1` - Span of the directive.
	///
	/// Note that the first controlling conditional directive (index of `1`) is at the beginning of this vector
	/// (index `0`), so an offset must be performed.
	pub fn get_all_controlling_conditional_directives(
		&self,
	) -> Vec<(Conditional, Span)> {
		let mut directives = Vec::new();
		for (_i, (node_id, _)) in
			self.order_by_appearance.iter().enumerate().skip(1)
		{
			let parent_id = self.tree[*node_id].parent.unwrap();
			for child in self.tree[parent_id].children.iter() {
				match child {
					Either::Left(_) => {}
					Either::Right(block) => {
						let Some((ty,_, _, span, _, _, _)) = block.conditions.iter().find(|(_,_, _, _, id, _, _)| node_id == id) else { continue; };
						directives.push((*ty, *span));
					}
				}
			}
		}
		directives
	}

	/// Creates a new key to access the specified controlling conditional directive.
	///
	/// This method takes the index (of the chronological appearance) of the controlling conditional directive
	/// (`#if`/`#ifdef`/`#ifndef`/`#elif`/`#else`), and returns a key that reaches that conditional branch. The new
	/// key contains the minimal number of prerequisite branches necessary to reach the chosen directive.
	pub fn create_key(
		&self,
		chosen_conditional_directive: usize,
	) -> Vec<usize> {
		// There is no existing key, so we need to construct one from scratch. Each node within the vector has
		// a list of all prerequisite parents, so we can just use that, (removing the unneeded parent node IDs).
		let Some((_new_selection_node_id, parent_info)) = self.order_by_appearance.get(chosen_conditional_directive) else {
				return Vec::new();
			};

		let mut key = parent_info
			.iter()
			.skip(1)
			.map(|(idx, _)| *idx)
			.collect::<Vec<_>>();
		key.push(chosen_conditional_directive);
		key
	}

	/// Modifies an existing key to access the specified controlling conditional directive.
	///
	/// This method keeps all existing conditional branches as long as they don't conflict with the newly chosen
	/// branch.
	pub fn add_selection_to_key(
		&self,
		existing_key: &Vec<usize>,
		chosen_conditional_directive: usize,
	) -> Vec<usize> {
		let mut call_stack = vec![(0, 0, 0)];
		// This map will store a vector of sibling branches. This is a map so that the iteration can access the
		// correct vector to push into, but once the iteration is over we only care about the values not the keys.
		// Each vector has all of the order-of-appearance indexes of sibling conditional branches.
		let mut sibling_map: HashMap<(usize, usize), Vec<usize>> =
			HashMap::new();
		let mut cond_counter = 0;
		'outer: loop {
			let (node_id, child_idx, cond_block_idx) =
				match call_stack.last_mut() {
					Some(t) => t,
					None => break,
				};
			let node = &self.tree[*node_id];
			let Some(child) = node.children.get(*child_idx) else { break; };

			match child {
				Either::Left(_) => {
					*child_idx += 1;
					if *child_idx == node.children.len() {
						// We have gone through all of the children of this node, so we want to pop it from the
						// stack.
						call_stack.pop();
					}
				}
				Either::Right(cond_block) => {
					if *cond_block_idx == cond_block.conditions.len() {
						// We have gone through all of the conditional branches.
						*cond_block_idx = 0;
						*child_idx += 1;
						if *child_idx == node.children.len() {
							// We have gone through all of the children of this node, so we want to pop it from the
							// stack.
							call_stack.pop();
						}

						continue 'outer;
					}

					cond_counter += 1;
					let current_cond_block_idx = *cond_block_idx;
					let (_, _, _, _, cond_branch_node_id, _, _) =
						&cond_block.conditions[current_cond_block_idx];

					match sibling_map.get_mut(&(*node_id, *child_idx)) {
						Some(v) => v.push(cond_counter),
						None => {
							sibling_map.insert(
								(*node_id, *child_idx),
								vec![cond_counter],
							);
						}
					}

					*cond_block_idx += 1;
					call_stack.push((*cond_branch_node_id, 0, 0));
				}
			}
		}

		let chosen_parents =
			match self.order_by_appearance.get(chosen_conditional_directive) {
				Some((_, parent_info)) => {
					parent_info.iter().map(|(i, _)| *i).collect::<Vec<_>>()
				}
				None => {
					return existing_key.to_vec();
				}
			};

		// Vector of vectors of siblings of nodes that the newly chosen node depends on.
		let mut siblings = sibling_map
			.values()
			.filter(|siblings| {
				for parent in chosen_parents.iter() {
					if siblings.contains(parent) {
						return true;
					}
				}
				false
			})
			.collect::<Vec<_>>();

		match sibling_map
			.values()
			.find(|siblings| siblings.contains(&chosen_conditional_directive))
		{
			Some(v) => siblings.push(v),
			None => return existing_key.to_vec(),
		}

		let mut new_key = Vec::with_capacity(existing_key.len());
		'outer: for existing in existing_key {
			for siblings in siblings.iter() {
				if siblings.contains(existing) {
					// This node is a sibling of the newly chosen node or one of the parent nodes required by the
					// newly chosen node, so we disgard it.
					continue 'outer;
				}
			}

			let (_, parent_info) =
				self.order_by_appearance.get(*existing).unwrap();
			let parent_idx_s =
				parent_info.iter().map(|(i, _)| *i).collect::<Vec<_>>();
			for siblings in siblings.iter() {
				for i in parent_idx_s.iter() {
					if siblings.contains(i) {
						// This node depends on a parent node that is a sibling of the newly chosen node or one of
						// the parent nodes required by the newly chosen node, so we discard it.
						continue 'outer;
					}
				}
			}

			// This node does not clash, so we can keep it.
			new_key.push(*existing);
		}

		let mut insertion = chosen_parents;
		insertion.remove(0); // Remove the `0` root parent, since that's treated implicitly in the key.
		insertion.push(chosen_conditional_directive);

		if new_key.is_empty() {
			return insertion;
		} else if new_key.len() == 1 {
			if insertion.last().unwrap() < new_key.first().unwrap() {
				insertion.append(&mut new_key);
				return insertion;
			} else {
				new_key.append(&mut insertion);
				return new_key;
			}
		}

		// We need to insert the new selection. The correct place to insert it will be chronological.
		if insertion.last().unwrap() < new_key.first().unwrap() {
			insertion.append(&mut new_key);
			return insertion;
		}

		let mut insertion_idx = None;
		for (i, val) in new_key.windows(2).enumerate() {
			let first = val[0];
			let second = val[1];

			if first == *insertion.first().unwrap() {
				insertion.remove(0);
			}

			if first < *insertion.first().unwrap()
				&& *insertion.last().unwrap() < second
			{
				// The insertion fits between these two values.
				insertion_idx = Some(i + 1);
				break;
			}
		}

		if let Some(insertion_idx) = insertion_idx {
			for i in insertion.into_iter().rev() {
				new_key.insert(insertion_idx, i);
			}
		} else {
			new_key.append(&mut insertion);
		}

		new_key
	}

	/// Modifies an existing key to remove access to the specified controlling conditional directive.
	///
	/// This method keeps all existing conditional branches as long as they don't depend on the specified to-remove
	/// branch.
	pub fn remove_selection_from_key(
		&self,
		existing_key: &Vec<usize>,
		removed_conditional_directive: usize,
	) -> Vec<usize> {
		existing_key
			.iter()
			.filter_map(|node| {
				// This node is the to-remove node.
				if *node == removed_conditional_directive {
					return None;
				}

				// This node doesn't even exist
				let Some((_node_id, parent_info)) = self.order_by_appearance.get(*node) else {
				return None;
			};

				// This node depends on the to-remove node.
				if parent_info
					.iter()
					.find(|(i, _)| *i == removed_conditional_directive)
					.is_some()
				{
					return None;
				}

				return Some(*node);
			})
			.collect()
	}

	/// Returns whether the source string contains any conditional directives.
	pub fn contains_conditional_directives(&self) -> bool {
		self.contains_conditional_directives
	}
}

/// A token stream provider.
trait TokenStreamProvider<'a>: Clone {
	/// Returns the next token stream. If the end of the source string has been reached, `None` will be returned.
	fn get_next_stream(
		&mut self,
		macros: &HashMap<String, (Span, Macro)>,
		syntax_diags: &mut Vec<Syntax>,
		syntax_tokens: &mut Vec<SyntaxToken>,
		span_encoding: SpanEncoding,
	) -> Option<TokenStream>;

	/// Returns the zero-width span of the source string.
	fn get_end_span(&self) -> Span;
}

/// A root token stream provider.
#[derive(Debug, Clone)]
struct RootTokenStreamProvider<'a> {
	/// The source streams in the correct order.
	streams: Vec<TokenStream>,
	/// Cursor position.
	cursor: usize,
	/// The zero-width span at the end of the source string.
	end_span: Span,
	_phantom: std::marker::PhantomData<&'a ()>,
}

impl<'a> RootTokenStreamProvider<'a> {
	/// Constructs a new pre-selected token stream provider.
	fn new(streams: Vec<TokenStream>, end_position: usize) -> Self {
		Self {
			streams,
			cursor: 0,
			end_span: Span::new(end_position, end_position),
			_phantom: std::marker::PhantomData::default(),
		}
	}
}

impl<'a> TokenStreamProvider<'a> for RootTokenStreamProvider<'a> {
	fn get_next_stream(
		&mut self,
		_macros: &HashMap<String, (Span, Macro)>,
		_syntax_diags: &mut Vec<Syntax>,
		_syntax_tokens: &mut Vec<SyntaxToken>,
		_span_encoding: SpanEncoding,
	) -> Option<TokenStream> {
		let v = self.streams.get(self.cursor).map(|v| v.clone());
		self.cursor += 1;
		v
	}

	fn get_end_span(&self) -> Span {
		self.end_span
	}
}

/// A pre-selected token stream provider.
#[derive(Debug, Clone)]
struct PreselectedTokenStreamProvider<'a> {
	/// The source streams in the correct order.
	streams: Vec<TokenStream>,
	/// Cursor position.
	cursor: usize,
	/// The zero-width span at the end of the source string.
	end_span: Span,
	/// Syntax tokens for each conditional directive that is part of the pre-selected evaluation, in order of
	/// appearance.
	conditional_syntax_tokens: Vec<Vec<SyntaxToken>>,
	_phantom: std::marker::PhantomData<&'a ()>,
}

impl<'a> PreselectedTokenStreamProvider<'a> {
	/// Constructs a new pre-selected token stream provider.
	fn new(
		streams: Vec<TokenStream>,
		conditional_syntax_tokens: Vec<Vec<SyntaxToken>>,
		end_position: usize,
	) -> Self {
		Self {
			streams,
			cursor: 0,
			end_span: Span::new(end_position, end_position),
			conditional_syntax_tokens,
			_phantom: std::marker::PhantomData::default(),
		}
	}
}

impl<'a> TokenStreamProvider<'a> for PreselectedTokenStreamProvider<'a> {
	fn get_next_stream(
		&mut self,
		_macros: &HashMap<String, (Span, Macro)>,
		_syntax_diags: &mut Vec<Syntax>,
		syntax_tokens: &mut Vec<SyntaxToken>,
		_span_encoding: SpanEncoding,
	) -> Option<TokenStream> {
		match self.streams.get(self.cursor) {
			Some(v) => {
				if let Some((_, stream_span)) = v.first() {
					while let Some(f) = self.conditional_syntax_tokens.first() {
						if let Some(SyntaxToken {
							span: cond_span, ..
						}) = f.first()
						{
							if cond_span.is_before(stream_span) {
								syntax_tokens.append(
									&mut self
										.conditional_syntax_tokens
										.remove(0),
								);
							} else {
								break;
							}
						} else {
							// This vector conditional syntax tokens is empty, so there's no need to keep it
							// around. If we didn't remove this, we could theoretically have an infinite loop.
							self.conditional_syntax_tokens.remove(0);
						}
					}
				}

				self.cursor += 1;
				return Some(v.clone());
			}
			None => {
				while !self.conditional_syntax_tokens.is_empty() {
					syntax_tokens
						.append(&mut self.conditional_syntax_tokens.remove(0));
				}
				return None;
			}
		}
	}

	fn get_end_span(&self) -> Span {
		self.end_span
	}
}

/// A dynamic token stream provider. This evaluates conditional directives on-the-fly.
#[derive(Debug, Clone)]
struct DynamicTokenStreamProvider<'a> {
	/// The arena of token streams.
	arena: &'a [TokenStream],
	/// The tree.
	tree: &'a [TreeNode],
	/// The current call stack.
	///
	/// - `0` - The node ID.
	/// - `1` - The index into the node's `children`.
	/// - `2` - The index into the current child's conditional branches if the child is a conditional block.
	/// - `3` - The conditional branch that has been picked, if the child is a conditional block.
	ptrs: Vec<(usize, usize, usize, isize)>,
	/// The key of node IDs that was chosen in the evaluation.
	chosen_key: Vec<usize>,
	/// The spans of regions of relevant syntax tokens. This includes all tokens within conditional branches that
	/// have been chosen, as well as all tokens for the directives themselves that have been looked at, but not
	/// necessarily chosen; i.e. this would include a failed `#elif`/`#else` and the `#endif`.
	chosen_regions: Vec<Span>,
	/// The zero-width span at the end of the source string.
	end_span: Span,
}

impl<'a> DynamicTokenStreamProvider<'a> {
	/// Constructs a new dynamic token stream provider.
	fn new(
		arena: &'a [TokenStream],
		tree: &'a [TreeNode],
		end_position: usize,
	) -> Self {
		Self {
			arena,
			tree,
			ptrs: vec![(TokenTree::ROOT_NODE_ID, 0, 0, -1)],
			chosen_key: Vec::new(),
			chosen_regions: Vec::new(),
			end_span: Span::new(end_position, end_position),
		}
	}
}

impl<'a> TokenStreamProvider<'a> for DynamicTokenStreamProvider<'a> {
	fn get_next_stream(
		&mut self,
		macros: &HashMap<String, (Span, Macro)>,
		syntax_diags: &mut Vec<Syntax>,
		syntax_tokens: &mut Vec<SyntaxToken>,
		span_encoding: SpanEncoding,
	) -> Option<TokenStream> {
		'outer: loop {
			let (node_ptr, child_idx, cond_block_idx, evaluated_cond_block) =
				match self.ptrs.last_mut() {
					// `let-else` breaks `rustfmt`.
					Some((
						node_ptr,
						child_idx,
						cond_block_idx,
						evaluated_cond_block,
					)) => (
						node_ptr,
						child_idx,
						cond_block_idx,
						evaluated_cond_block,
					),
					_ => {
						// We have exhausted the token tree; there is nothing left.
						return None;
					}
				};
			let node = self.tree.get(*node_ptr).unwrap();
			let Some(child) = node.children.get(*child_idx) else { return None; };

			match child {
				Either::Left(arena_id) => {
					let stream = self.arena[*arena_id].clone();

					// Update the last span value. This value can't be calculated ahead-of-time since we don't know
					// what conditional compilation will evaluate to.
					if let Some((_, span)) = stream.last() {
						/* self.end_span = *span; */
						self.chosen_regions.push(Span::new(
							stream.first().unwrap().1.start,
							span.end,
						));
					}

					*child_idx += 1;
					if *child_idx == node.children.len() {
						// We have gone through all of the children of this node, so we want to pop it from the
						// stack.
						self.ptrs.pop();
					}

					return Some(stream);
				}
				Either::Right(cond_block) => {
					let matched_condition_node_id;
					loop {
						if *cond_block_idx == cond_block.conditions.len() {
							// We've gone through all of the conditional blocks. We can now push the syntax tokens
							// for the `#endif` and move onto the next child of this node.
							if let Some((
								_,
								directive_span,
								tokens,
								_,
								hash_token,
								dir_token,
							)) = &cond_block.end
							{
								syntax_tokens.push(*hash_token);
								syntax_tokens.push(*dir_token);
								if !tokens.is_empty() {
									syntax_tokens.push(SyntaxToken {
										ty: SyntaxType::Invalid,
										modifiers: SyntaxModifiers::CONDITIONAL,
										span: Span::new(
											tokens.first().unwrap().1.start,
											tokens.last().unwrap().1.end,
										),
									});
								}
								if *evaluated_cond_block
									== cond_block.conditions.len() as isize - 1
								{
									// We have chosen the final conditional block, which means we are responsible
									// for syntax highlighting the `#endif` directive. (This is only relevant if we
									// are syntax highlighting the entire file). The reason we can't do this
									// unconditionally is because if the final block wasn't picked, then an
									// alternative permutation is responsible for syntax highlighting it, but the
									// span of the syntax highlight region stretches to cover the `#endif` part. If
									// we declared this as chosen, the other span region wouldn't fit and would
									// therefore be discarded, and hence syntax highlighting would be missing for
									// the final branch.
									self.chosen_regions.push(*directive_span);
								}
							}

							*cond_block_idx = 0;
							*child_idx += 1;
							*evaluated_cond_block = -1;
							if *child_idx == node.children.len() {
								// We have gone through all of the children of this node, so we want to pop it from
								// the stack.
								self.ptrs.pop();
							}

							continue 'outer;
						}

						let current_cond_block_idx = *cond_block_idx;

						let (
							condition_ty,
							directive_span,
							tokens,
							_,
							node_id,
							hash_token,
							dir_token,
						) = &cond_block.conditions[current_cond_block_idx];

						*cond_block_idx += 1;

						match condition_ty {
							Conditional::IfDef | Conditional::IfNotDef => {
								syntax_tokens.push(*hash_token);
								syntax_tokens.push(*dir_token);

								if !tokens.is_empty() {
									let (token, token_span) = &tokens[0];
									match token {
										ConditionToken::Ident(str) => {
											syntax_tokens.push(SyntaxToken {
												ty: SyntaxType::Ident,
												modifiers:
													SyntaxModifiers::CONDITIONAL,
												span: *token_span,
											});
											if tokens.len() > 1 {
												syntax_tokens.push(SyntaxToken {
													ty: SyntaxType::Invalid,
													modifiers:SyntaxModifiers::CONDITIONAL,
													span: Span::new(
														tokens[1].1.start,
														tokens.last().unwrap().1.end
													)
												});
											}
											let result =
												conditional_eval::evaluate_def(
													Ident {
														name: str.clone(),
														span: *token_span,
													},
													macros,
												);
											if result
												&& *evaluated_cond_block == -1
											{
												matched_condition_node_id =
													*node_id;
												*evaluated_cond_block =
													current_cond_block_idx
														as isize;
												self.chosen_regions
													.push(*directive_span);
												break;
											}
										}
										_ => {
											syntax_tokens.push(SyntaxToken {
												ty: SyntaxType::Invalid,
												modifiers:
													SyntaxModifiers::CONDITIONAL,
												span: Span::new(
													token_span.start,
													tokens
														.last()
														.unwrap()
														.1
														.end,
												),
											});
										}
									}
								}
							}
							Conditional::If | Conditional::ElseIf => {
								syntax_tokens.push(*hash_token);
								syntax_tokens.push(*dir_token);

								let (expr, mut syntax, mut colours) =
									cond_parser(
										tokens.clone(),
										macros,
										span_encoding,
									);
								syntax_diags.append(&mut syntax);
								syntax_tokens.append(&mut colours);

								if let Some(expr) = expr {
									let result =
										conditional_eval::evaluate_expr(
											expr, macros,
										);
									if result && *evaluated_cond_block == -1 {
										matched_condition_node_id = *node_id;
										*evaluated_cond_block =
											current_cond_block_idx as isize;
										self.chosen_regions
											.push(*directive_span);
										break;
									}
								}
							}
							Conditional::Else => {
								syntax_tokens.push(*hash_token);
								syntax_tokens.push(*dir_token);
								if !tokens.is_empty() {
									syntax_tokens.push(SyntaxToken {
										ty: SyntaxType::Invalid,
										modifiers: SyntaxModifiers::CONDITIONAL,
										span: Span::new(
											tokens.first().unwrap().1.start,
											tokens.last().unwrap().1.end,
										),
									});
								}

								if *evaluated_cond_block == -1 {
									// An `else` branch is always unconditionally chosen.
									matched_condition_node_id = *node_id;
									*evaluated_cond_block =
										current_cond_block_idx as isize;
									self.chosen_regions.push(*directive_span);
									break;
								}
							}
							Conditional::End => unreachable!(),
						}
					}

					self.ptrs.push((matched_condition_node_id, 0, 0, -1));
					self.chosen_key.push(matched_condition_node_id);
					continue;
				}
			}
		}
	}

	fn get_end_span(&self) -> Span {
		self.end_span
	}
}

/// Allows for stepping through a token stream. Takes care of dealing with irrelevant details from the perspective
/// of the parser, such as comments and macro expansion.
struct Walker<'a, Provider: TokenStreamProvider<'a>> {
	/// The token stream provider.
	token_provider: Provider,
	_phantom: std::marker::PhantomData<&'a ()>,
	/// The active token streams.
	///
	/// - `0` - The macro identifier, (for the root source stream this is just `""`).
	/// - `1` - The token stream.
	/// - `2` - The cursor.
	streams: Vec<(String, TokenStream, usize)>,

	/// The currently defined macros.
	///
	/// Key: The macro identifier.
	///
	/// Value:
	/// - `0` - The span of the macro signature.
	/// - `1` - Macro information.
	macros: HashMap<String, (Span, Macro)>,
	/// The span of an initial macro call site. Only the first macro call site is registered here.
	macro_call_site: Option<Span>,
	/// The actively-called macro identifiers.
	active_macros: HashSet<String>,

	/// Any syntax diagnostics created from the tokens parsed so-far.
	syntax_diags: Vec<Syntax>,
	/// Any semantic diagnostics created from the tokens parsed so-far.
	semantic_diags: Vec<Semantic>,

	/// The syntax highlighting tokens created from the tokens parsed so-far.
	syntax_tokens: Vec<SyntaxToken>,
	/// The type of encoding of spans.
	span_encoding: SpanEncoding,
}

/// Data for a macro.
#[derive(Debug, Clone)]
enum Macro {
	Object(TokenStream),
	Function {
		params: Vec<Ident>,
		body: TokenStream,
	},
}

impl<'a, Provider: TokenStreamProvider<'a>> Walker<'a, Provider> {
	/// Constructs a new walker.
	fn new(mut token_provider: Provider, span_encoding: SpanEncoding) -> Self {
		let macros = HashMap::new();
		let mut syntax_diags = Vec::new();
		let mut syntax_tokens = Vec::new();

		// Get the first stream.
		let streams = match token_provider.get_next_stream(
			&macros,
			&mut syntax_diags,
			&mut syntax_tokens,
			span_encoding,
		) {
			Some(stream) => vec![("".into(), stream, 0)],
			None => vec![],
		};

		let mut active_macros = HashSet::new();
		// Invariant: A macro cannot have no name (an empty identifier), so this won't cause any hashing clashes
		// with valid macros. By using "" we can avoid having a special case for the root source stream.
		active_macros.insert("".into());

		Self {
			token_provider,
			_phantom: Default::default(),
			streams,
			macros,
			macro_call_site: None,
			active_macros,
			syntax_diags,
			semantic_diags: Vec::new(),
			syntax_tokens,
			span_encoding,
		}
	}

	/// Returns a reference to the current token under the cursor, without advancing the cursor.
	fn peek(&self) -> Option<Spanned<&Token>> {
		if self.streams.is_empty() {
			None
		} else if self.streams.len() == 1 {
			let (_, stream, cursor) = self.streams.last().unwrap();
			stream.get(*cursor).map(|(t, s)| (t, *s))
		} else {
			let (_, stream, cursor) = self.streams.last().unwrap();
			match stream.get(*cursor).map(|(t, _)| t) {
				Some(token) => Some((
					token,
					// Panic: This is guaranteed to be some if `self.streams.len() > 1`.
					self.macro_call_site.unwrap(),
				)),
				None => None,
			}
		}
	}

	/// Returns the current token under the cursor, without advancing the cursor. (The token gets cloned).
	fn get(&self) -> Option<Spanned<Token>> {
		if self.streams.is_empty() {
			None
		} else if self.streams.len() == 1 {
			let (_, stream, cursor) = self.streams.last().unwrap();
			stream.get(*cursor).cloned()
		} else {
			let (_, stream, cursor) = self.streams.last().unwrap();
			let token = stream.get(*cursor).map(|(t, _)| t).cloned();
			token.map(|t| {
				(
					t,
					// Panic: This is guaranteed to be some if `self.streams.len() > 1`.
					self.macro_call_site.unwrap(),
				)
			})
		}
	}

	/// Peeks the next token without advancing the cursor.
	///
	/// **This method is expensive** to call because it needs to correctly deal with macros. Avoid calling this
	/// often.
	///
	/// This method correctly steps into/out-of macros, jumps between conditional compilation branches, and
	/// consumes any comments.
	fn lookahead_1(&self) -> Option<Spanned<Token>> {
		let mut token_provider = self.token_provider.clone();
		let mut streams = self.streams.clone();
		let mut macros = self.macros.clone();
		let mut active_macros = self.active_macros.clone();
		let mut macro_call_site = self.macro_call_site.clone();
		let mut syntax_diags = Vec::new();
		let mut semantic_diags = Vec::new();
		let mut syntax_tokens = Vec::new();
		// PERF: Optimize for certain cases to prevent having to clone everything everytime.
		Self::_move_cursor(
			&mut token_provider,
			&mut streams,
			&mut macros,
			&mut active_macros,
			&mut macro_call_site,
			&mut syntax_diags,
			&mut semantic_diags,
			&mut syntax_tokens,
			self.span_encoding,
		);

		// Copy of `Self::get()`.
		if streams.is_empty() {
			None
		} else if streams.len() == 1 {
			let (_, stream, cursor) = streams.last().unwrap();
			stream.get(*cursor).cloned()
		} else {
			let (_, stream, cursor) = streams.last().unwrap();
			let token = stream.get(*cursor).map(|(t, _)| t).cloned();
			token.map(|t| {
				(
					t,
					// Panic: This is guaranteed to be some if `streams.len() > 1`.
					macro_call_site.unwrap(),
				)
			})
		}
	}

	/// Advances the cursor by one.
	///
	/// This method correctly steps into/out-of macros, jumps between conditional compilation branches, and
	/// consumes any comments.
	fn advance(&mut self) {
		Self::_move_cursor(
			&mut self.token_provider,
			&mut self.streams,
			&mut self.macros,
			&mut self.active_macros,
			&mut self.macro_call_site,
			&mut self.syntax_diags,
			&mut self.semantic_diags,
			&mut self.syntax_tokens,
			self.span_encoding,
		);
	}

	/// Advances the cursor by one.
	///
	/// This method is identical to `advance()` apart from that diagnostics and syntax highlighting tokens are
	/// returned. This is necessary because otherwise the spans could be produced in the wrong order, if, for
	/// example, the walker consumes a comment but the expresion syntax tokens are appended after the fact.
	fn advance_expr_parser(
		&mut self,
		syntax_diags: &mut Vec<Syntax>,
		semantic_diags: &mut Vec<Semantic>,
		syntax_tokens: &mut Vec<SyntaxToken>,
	) {
		Self::_move_cursor(
			&mut self.token_provider,
			&mut self.streams,
			&mut self.macros,
			&mut self.active_macros,
			&mut self.macro_call_site,
			syntax_diags,
			semantic_diags,
			syntax_tokens,
			self.span_encoding,
		);
	}

	/// Returns whether the walker has reached the end of the token streams.
	fn is_done(&self) -> bool {
		self.streams.is_empty()
	}

	/// Returns the span of the last token in the token stream.
	fn get_last_span(&self) -> Span {
		self.token_provider.get_end_span()
	}

	/// Moves the cursor to the next token. This function takes all the necessary data by parameter so that the
	/// functionality can be re-used between the `Self::advance()` and `Self::lookahead_1()` methods.
	fn _move_cursor(
		token_provider: &mut Provider,
		streams: &mut Vec<(String, TokenStream, usize)>,
		macros: &mut HashMap<String, (Span, Macro)>,
		active_macros: &mut HashSet<String>,
		macro_call_site: &mut Option<Span>,
		syntax_diags: &mut Vec<Syntax>,
		semantic_diags: &mut Vec<Semantic>,
		syntax_tokens: &mut Vec<SyntaxToken>,
		span_encoding: SpanEncoding,
	) {
		let mut dont_increment = false;
		'outer: while let Some((identifier, stream, cursor)) =
			streams.last_mut()
		{
			if !dont_increment {
				*cursor += 1;
			}
			dont_increment = false;

			if *cursor == stream.len() {
				// We have reached the end of this stream. We close it and re-run the loop on the next stream, (if
				// there is one).

				let ident = identifier.clone();
				if streams.len() == 1 {
					// If we aren't in a macro, that means we've finished the current source stream. There may
					// however be another stream, for which we need to query the provider for.
					match token_provider.get_next_stream(
						macros,
						syntax_diags,
						syntax_tokens,
						span_encoding,
					) {
						Some(mut next_stream) => {
							let (_, s, c) = &mut streams[0];
							std::mem::swap(s, &mut next_stream);
							*c = 0;
							dont_increment = true;
							continue;
						}
						None => {
							// The provider didn't return anything, so that means we have reached the final end.
							streams.remove(0);
							break;
						}
					}
				} else {
					// Panic: Anytime a stream is added the identifier is inserted into the set.
					active_macros.remove(&ident);
					streams.remove(streams.len() - 1);
					continue;
				}
			}

			let (token, token_span) = stream.get(*cursor).unwrap();

			match token {
				// We check if the new token is a macro call site.
				Token::Ident(s) => {
					if let Some((signature_span, macro_)) = macros.get(s) {
						if active_macros.contains(s) {
							// We have already visited a macro with this identifier. Recursion is not supported so
							// we don't continue.
							break;
						}

						let ident_span = *token_span;

						if let Macro::Function { params, body } = macro_ {
							// We have an identifier which matches a function-like macro, so we are expecting a
							// parameter list in the current token stream before we do any switching.

							// We don't need to worry about having to switch source streams because that would
							// imply that a conditional compilation directive is in the middle of a function-like
							// macro call site, which isn't valid. A function-like macro call cannot have
							// preprocessor directives within, which means that the source stream won't be split up
							// by a conditional, which means the entire invocation of the macro will be within this
							// stream.

							let mut tmp_cursor = *cursor + 1;
							let mut syntax_spans = vec![SyntaxToken {
								ty: SyntaxType::FunctionMacro,
								modifiers: SyntaxModifiers::empty(),
								span: ident_span,
							}];
							loop {
								match stream.get(tmp_cursor) {
									Some((token, token_span)) => match token {
										Token::LineComment(_)
										| Token::BlockComment { .. } => {
											syntax_spans.push(SyntaxToken {
												ty: SyntaxType::Comment,
												modifiers:
													SyntaxModifiers::empty(),
												span: *token_span,
											});
											tmp_cursor += 1;
										}
										_ => break,
									},
									None => break 'outer,
								}
							}

							// Consume the opening `(` parenthesis.
							let l_paren_span = match stream.get(tmp_cursor) {
								Some((token, token_span)) => match token {
									Token::LParen => {
										syntax_spans.push(SyntaxToken {
											ty: SyntaxType::Punctuation,
											modifiers: SyntaxModifiers::empty(),
											span: *token_span,
										});
										*cursor = tmp_cursor + 1;
										*token_span
									}
									_ => {
										// We did not immediately encounter a parenthesis, which means that this is
										// not a call to a function-like macro even if the names match.
										break;
									}
								},
								None => break,
							};

							// Look for any arguments until we hit a closing `)` parenthesis. The preprocessor
							// immediately switches to the next argument when a `,` is encountered, unless we are
							// within a parenthesis group.
							/* #[derive(PartialEq)]
							enum Prev {
								None,
								Param,
								Comma,
								Invalid,
							}
							let mut prev = Prev::None; */
							let mut prev_span = l_paren_span;
							let mut paren_groups = 0;
							let mut args = Vec::new();
							let mut arg = Vec::new();
							let r_paren_span = loop {
								let (token, token_span) =
									match stream.get(*cursor) {
										Some(t) => t,
										None => {
											syntax_diags.push(Syntax::PreprocDefine(PreprocDefineDiag::ParamsExpectedRParen(
											prev_span.next_single_width()
										)));
											break 'outer;
										}
									};

								match token {
									Token::Comma => {
										syntax_spans.push(SyntaxToken {
											ty: SyntaxType::Punctuation,
											modifiers: SyntaxModifiers::empty(),
											span: *token_span,
										});
										if paren_groups == 0 {
											let arg = std::mem::take(&mut arg);
											args.push(arg);
											/* prev = Prev::Comma; */
										}
										prev_span = *token_span;
										*cursor += 1;
										continue;
									}
									Token::LParen => {
										paren_groups += 1;
									}
									Token::RParen => {
										if paren_groups == 0 {
											// We have reached the end of this function-like macro call site.
											syntax_spans.push(SyntaxToken {
												ty: SyntaxType::Punctuation,
												modifiers:
													SyntaxModifiers::empty(),
												span: *token_span,
											});
											let arg = std::mem::take(&mut arg);
											args.push(arg);
											// It is important that we don't increment the cursor to the next token
											// after the macro call site. This is because once this macro is
											// finished, and we return to the previous stream, we will
											// automatically increment the cursor onto the next token which will be
											// the first token after the macro call site. The object-like macro
											// branch also doesn't perform this increment.
											// *cursor += 1;
											break *token_span;
										}
										paren_groups -= 1;
									}
									_ => {}
								}
								syntax_spans.push(SyntaxToken {
									ty: token.non_semantic_colour(),
									modifiers: SyntaxModifiers::empty(),
									span: *token_span,
								});
								arg.push((token.clone(), *token_span));
								/* prev = Prev::Param; */
								*cursor += 1;
							};
							let call_site_span =
								Span::new(ident_span.start, r_paren_span.end);

							// We have a set of arguments now.
							if params.len() != args.len() {
								// If there is a mismatch in the argument/parameter count, we ignore this macro
								// call and move onto the next token after the call site.
								semantic_diags.push(
									Semantic::FunctionMacroMismatchedArgCount(
										call_site_span,
										*signature_span,
									),
								);
								continue;
							}
							let mut param_map = HashMap::new();
							params.iter().zip(args.into_iter()).for_each(
								|(ident, tokens)| {
									param_map.insert(&ident.name, tokens);
								},
							);

							// We now go through the replacement token list and replace any identifiers which match
							// a parameter name with the relevant argument's tokens.
							let mut new_body = Vec::with_capacity(body.len());
							for (token, token_span) in body {
								match token {
									Token::Ident(str) => {
										if let Some(arg) = param_map.get(&str) {
											for token in arg {
												new_body.push(token.clone());
											}
											continue;
										}
									}
									_ => {}
								}
								new_body.push((token.clone(), *token_span));
							}
							// Then, we perform token concatenation.
							let (new_body, mut syntax, mut semantic) =
								lexer::preprocessor::concat_macro_body(
									new_body,
									span_encoding,
								);
							syntax_diags.append(&mut syntax);
							semantic_diags.append(&mut semantic);

							if body.is_empty() {
								// The macro is empty, so we want to move to the next token of the existing stream.
								semantic_diags.push(
									Semantic::EmptyMacroCallSite(
										call_site_span,
									),
								);
								if streams.len() == 1 {
									// We only syntax highlight when it is the first macro call.
									syntax_tokens.append(&mut syntax_spans);
								}
								continue;
							}

							let ident = s.to_owned();

							// We only syntax highlight and note the macro call site when it is the first macro
							// call.
							if streams.len() == 1 {
								*macro_call_site = Some(call_site_span);
								syntax_tokens.append(&mut syntax_spans);
							}

							active_macros.insert(ident.clone());
							streams.push((ident, new_body, 0));

							// The first token in the new stream could be another macro call, so we re-run the loop
							// on this new stream in case.
							dont_increment = true;
							continue;
						} else if let Macro::Object(stream) = macro_ {
							if stream.is_empty() {
								// The macro is empty, so we want to move to the next token of the existing stream.
								semantic_diags.push(
									Semantic::EmptyMacroCallSite(ident_span),
								);
								if streams.len() == 1 {
									// We only syntax highlight when it is the first macro call.
									syntax_tokens.push(SyntaxToken {
										ty: SyntaxType::ObjectMacro,
										modifiers: SyntaxModifiers::empty(),
										span: ident_span,
									});
								}
								continue;
							}

							let ident = s.to_owned();

							// We only syntax highlight and note the macro call site when it is the first macro
							// call.
							if streams.len() == 1 {
								*macro_call_site = Some(ident_span);
								syntax_tokens.push(SyntaxToken {
									ty: SyntaxType::ObjectMacro,
									modifiers: SyntaxModifiers::empty(),
									span: ident_span,
								});
							}

							active_macros.insert(ident.clone());
							streams.push((ident, stream.clone(), 0));

							// The first token in the new stream could be another macro call, so we re-run the loop
							// on this new stream in case.
							dont_increment = true;
							continue;
						}
					}
					break;
				}
				// We want to consume any comments since they are semantically ignored.
				Token::LineComment(_) => {
					let token_span = *token_span;
					if streams.len() == 1 {
						// We only syntax highlight when we are not in a macro call.
						syntax_tokens.push(SyntaxToken {
							ty: SyntaxType::Comment,
							modifiers: SyntaxModifiers::empty(),
							span: token_span,
						});
					}
				}
				Token::BlockComment { contains_eof, .. } => {
					if *contains_eof {
						syntax_diags.push(Syntax::BlockCommentMissingEnd(
							token_span.end_zero_width(),
						));
					}
					let token_span = *token_span;
					if streams.len() == 1 {
						// We only syntax highlight when we are not in a macro call.
						syntax_tokens.push(SyntaxToken {
							ty: SyntaxType::Comment,
							modifiers: SyntaxModifiers::empty(),
							span: token_span,
						});
					}
				}
				_ => break,
			}
		}

		if streams.len() <= 1 {
			*macro_call_site = None;
		}
	}

	/// Registers a define macro.
	fn register_macro(
		&mut self,
		ident: String,
		signature_span: Span,
		macro_: Macro,
	) {
		if let Some(_prev) = self.macros.insert(ident, (signature_span, macro_))
		{
			// TODO: Emit error if the macros aren't identical (will require scanning the tokenstream to compare).
		}
	}

	/// Un-registers a defined macro.
	fn unregister_macro(&mut self, ident: &str, span: Span) {
		match self.macros.remove(ident) {
			Some((_, macro_)) => match macro_ {
				Macro::Object(_) => self.push_colour_with_modifiers(
					span,
					SyntaxType::ObjectMacro,
					SyntaxModifiers::UNDEFINE,
				),
				Macro::Function { .. } => self.push_colour_with_modifiers(
					span,
					SyntaxType::FunctionMacro,
					SyntaxModifiers::UNDEFINE,
				),
			},
			None => {
				self.push_colour_with_modifiers(
					span,
					SyntaxType::UnresolvedIdent,
					SyntaxModifiers::UNDEFINE,
				);
				self.push_semantic_diag(Semantic::UndefMacroNameUnresolved(
					span,
				));
			}
		}
	}

	/// Pushes a syntax diagnostic.
	fn push_syntax_diag(&mut self, diag: Syntax) {
		self.syntax_diags.push(diag);
	}

	/// Appends a collection of syntax diagnostics.
	fn append_syntax_diags(&mut self, syntax: &mut Vec<Syntax>) {
		self.syntax_diags.append(syntax);
	}

	/// Pushes a semantic diagnostic.
	fn push_semantic_diag(&mut self, diag: Semantic) {
		self.semantic_diags.push(diag);
	}

	/// Appends a collection of semantic diagnostics.
	fn append_semantic_diags(&mut self, semantic: &mut Vec<Semantic>) {
		self.semantic_diags.append(semantic);
	}

	/// Pushes a syntax highlighting token over the given span.
	fn push_colour(&mut self, span: Span, token: SyntaxType) {
		self.push_colour_with_modifiers(span, token, SyntaxModifiers::empty())
	}

	/// Pushes a syntax highlighting token with one or more modifiers over the given span.
	fn push_colour_with_modifiers(
		&mut self,
		span: Span,
		ty: SyntaxType,
		modifiers: SyntaxModifiers,
	) {
		// When we are within a macro, we don't want to produce syntax tokens.
		// Note: This functionality is duplicated in the `ShuntingYard::colour()` method.
		if self.streams.len() == 1 {
			self.syntax_tokens.push(SyntaxToken {
				ty,
				modifiers,
				span,
			});
		}
	}

	/// Appends a collection of syntax highlighting tokens.
	fn append_colours(&mut self, colours: &mut Vec<SyntaxToken>) {
		self.syntax_tokens.append(colours);
	}
}

/* ACTUAL STATEMENT PARSING LOGIC BELOW */

/// Consumes tokens until a beginning of a new statement is reached.
///
/// This function consumes tokens until a keyword which can begin a statement is found, or until a semi-colon is
/// reached (which is consumed). This is used for some instances of error recovery, where no more specific
/// strategies can be employed.
fn seek_next_stmt<'a, P: TokenStreamProvider<'a>>(walker: &mut Walker<'a, P>) {
	loop {
		match walker.peek() {
			Some((token, span)) => {
				if token.can_start_statement() {
					return;
				} else if *token == Token::Semi {
					walker.push_colour(span, SyntaxType::Punctuation);
					walker.advance();
					return;
				} else {
					walker.push_colour(span, SyntaxType::Invalid);
					walker.advance();
					continue;
				}
			}
			None => return,
		}
	}
}

/// Invalidates a set of qualifiers.
///
/// This function is used to emit a diagnostic about the use of qualifiers before a statement which doesn't support
/// qualifiers.
fn invalidate_qualifiers<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	qualifiers: Vec<Qualifier>,
) {
	if let Some(q) = qualifiers.last() {
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::FoundQualifiersBeforeStmt(Span::new(
				qualifiers.first().unwrap().span.start,
				q.span.end,
			)),
		));
	}
}

/// Parses an individual statement at the current position.
fn parse_stmt<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<ast::Node>,
) {
	let qualifiers = try_parse_qualifiers(walker);

	let Some((token, token_span)) = walker.get() else {
		return;
	};

	match token {
		Token::LBrace => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Punctuation);
			walker.advance();
			let block = parse_scope(walker, brace_scope, token_span);
			nodes.push(Node {
				span: block.span,
				ty: NodeTy::Block(block),
			});
		}
		Token::Semi => {
			walker.push_colour(token_span, SyntaxType::Punctuation);
			walker.advance();
			if !qualifiers.is_empty() {
				nodes.push(Node {
					span: Span::new(
						qualifiers.first().unwrap().span.start,
						qualifiers.last().unwrap().span.end,
					),
					ty: NodeTy::Qualifiers(qualifiers),
				});
			} else {
				nodes.push(Node {
					span: token_span,
					ty: NodeTy::Empty,
				});
			}
		}
		Token::Struct => parse_struct(walker, nodes, qualifiers, token_span),
		Token::Directive(stream) => {
			invalidate_qualifiers(walker, qualifiers);
			parse_directive(walker, nodes, stream, token_span);
			walker.advance();
		}
		Token::If => parse_if(walker, nodes, token_span),
		Token::Switch => parse_switch(walker, nodes, token_span),
		Token::For => parse_for_loop(walker, nodes, token_span),
		Token::While => parse_while_loop(walker, nodes, token_span),
		Token::Do => parse_do_while_loop(walker, nodes, token_span),
		Token::Break => {
			invalidate_qualifiers(walker, qualifiers);
			parse_break_continue_discard(
				walker,
				nodes,
				token_span,
				|| NodeTy::Break,
				|span| Syntax::Stmt(StmtDiag::BreakExpectedSemiAfterKw(span)),
			)
		}
		Token::Continue => {
			invalidate_qualifiers(walker, qualifiers);
			parse_break_continue_discard(
				walker,
				nodes,
				token_span,
				|| NodeTy::Continue,
				|span| {
					Syntax::Stmt(StmtDiag::ContinueExpectedSemiAfterKw(span))
				},
			);
		}
		Token::Discard => {
			invalidate_qualifiers(walker, qualifiers);
			parse_break_continue_discard(
				walker,
				nodes,
				token_span,
				|| NodeTy::Discard,
				|span| Syntax::Stmt(StmtDiag::DiscardExpectedSemiAfterKw(span)),
			);
		}
		Token::Return => {
			invalidate_qualifiers(walker, qualifiers);
			parse_return(walker, nodes, token_span);
		}
		Token::RBrace => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Punctuation);
			walker.push_syntax_diag(Syntax::FoundUnmatchedRBrace(token_span));
			walker.advance();
		}
		Token::Else => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Keyword);
			walker.push_syntax_diag(Syntax::FoundLonelyElseKw(token_span));
			walker.advance();
		}
		Token::Case => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Keyword);
			walker.push_syntax_diag(Syntax::FoundLonelyCaseKw(token_span));
			walker.advance();
		}
		Token::Default => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Keyword);
			walker.push_syntax_diag(Syntax::FoundLonelyDefaultKw(token_span));
			walker.advance();
		}
		Token::Subroutine => {
			invalidate_qualifiers(walker, qualifiers);
			parse_subroutine(walker, nodes, token_span);
		}
		Token::Reserved(str) => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Invalid);
			walker.push_syntax_diag(Syntax::FoundReservedKw(token_span, str));
			walker.advance();
		}
		Token::Invalid(c) => {
			invalidate_qualifiers(walker, qualifiers);
			walker.push_colour(token_span, SyntaxType::Invalid);
			walker.push_syntax_diag(Syntax::FoundIllegalChar(token_span, c));
			walker.advance();
		}
		_ => try_parse_definition_declaration_expr(
			walker, nodes, qualifiers, false,
		),
	}
}

/// Parses a scope of statements.
///
/// This function assumes that the opening delimiter is already consumed.
fn parse_scope<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	exit_condition: ScopeEnd<'a, P>,
	opening_span: Span,
) -> Scope {
	let mut nodes = Vec::new();
	let ending_span = loop {
		// Check if we have reached the closing delimiter.
		if let Some(span) = exit_condition(walker, opening_span) {
			break span;
		}
		parse_stmt(walker, &mut nodes);
	};

	Scope {
		contents: nodes,
		span: Span::new(opening_span.start, ending_span.end),
	}
}

/// A function, which given the `walker`, determines whether to end parsing the current scope of statements and
/// return back to the caller. If this returns `Some`, we have reached the end of the scope. If the span returned
/// is zero-width, that means we have no closing delimiter.
///
/// This also takes a span of the opening delimiter which allows for the creation of a syntax error if the function
/// never encounters the desired ending delimiter.
type ScopeEnd<'a, P> = fn(&mut Walker<'a, P>, Span) -> Option<Span>;

fn brace_scope<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	l_brace_span: Span,
) -> Option<Span> {
	match walker.peek() {
		Some((token, span)) => {
			if *token == Token::RBrace {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ScopeMissingRBrace(
					l_brace_span,
					walker.get_last_span().next_single_width(),
				),
			));
			Some(walker.get_last_span().end_zero_width())
		}
	}
}
fn switch_case_scope<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	_start_span: Span,
) -> Option<Span> {
	match walker.peek() {
		Some((token, span)) => match token {
			Token::Case | Token::Default | Token::RBrace => Some(span),
			_ => None,
		},
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SwitchExpectedRBrace(
					walker.get_last_span().next_single_width(),
				),
			));
			Some(walker.get_last_span().end_zero_width())
		}
	}
}

/// Tries to parse one or more qualifiers.
///
/// This function makes no assumptions as to what the current token is.
fn try_parse_qualifiers<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
) -> Vec<Qualifier> {
	let mut qualifiers = Vec::new();
	'outer: loop {
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => break,
		};

		match token {
			Token::Const => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Const,
				});
			}
			Token::In => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::In,
				});
			}
			Token::Out => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Out,
				});
			}
			Token::InOut => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::InOut,
				});
			}
			Token::Attribute => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Attribute,
				});
			}
			Token::Uniform => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Uniform,
				});
			}
			Token::Varying => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Varying,
				});
			}
			Token::Buffer => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Buffer,
				});
			}
			Token::Shared => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Shared,
				});
			}
			Token::Centroid => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Centroid,
				});
			}
			Token::Sample => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Sample,
				});
			}
			Token::Patch => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Patch,
				});
			}
			Token::Flat => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Flat,
				});
			}
			Token::Smooth => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Smooth,
				});
			}
			Token::NoPerspective => {
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::NoPerspective,
				});
			}
			Token::HighP => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::HighP,
				});
			}
			Token::MediumP => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::MediumP,
				});
			}
			Token::LowP => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::LowP,
				});
			}
			Token::Invariant => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Invariant,
				});
			}
			Token::Precise => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Precise,
				});
			}
			Token::Coherent => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Coherent,
				});
			}
			Token::Volatile => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Volatile,
				});
			}
			Token::Restrict => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Restrict,
				});
			}
			Token::Readonly => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Readonly,
				});
			}
			Token::Writeonly => {
				walker.push_colour(token_span, SyntaxType::Keyword);
				qualifiers.push(Qualifier {
					span: token_span,
					ty: QualifierTy::Writeonly,
				});
			}
			Token::Layout => {
				let kw_span = token_span;
				walker.push_colour(kw_span, SyntaxType::Keyword);
				walker.advance();

				// Consume the `(`.
				let (token, token_span) = match walker.peek() {
					Some(t) => t,
					None => {
						// We don't have any layout contents yet.
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::LayoutExpectedLParenAfterKw(
								kw_span.next_single_width(),
							),
						));
						qualifiers.push(Qualifier {
							span: kw_span,
							ty: QualifierTy::Layout(vec![]),
						});
						break;
					}
				};
				let l_paren_span = if *token == Token::LParen {
					walker.push_colour(token_span, SyntaxType::Punctuation);
					walker.advance();
					token_span
				} else {
					// We don't have any layout contents yet.
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::LayoutExpectedLParenAfterKw(
							kw_span.next_single_width(),
						),
					));
					qualifiers.push(Qualifier {
						span: kw_span,
						ty: QualifierTy::Layout(vec![]),
					});
					break;
				};

				// Look for any layouts until we hit a closing `)` parenthesis.
				#[derive(PartialEq)]
				enum Prev {
					None,
					Layout,
					Comma,
					Invalid,
				}
				let mut prev = Prev::None;
				let mut prev_span = l_paren_span;
				let mut layouts = Vec::new();
				let r_paren_span = loop {
					let (token, token_span) = match walker.get() {
						Some(t) => t,
						None => {
							// We have not yet finished parsing the layout list, but we treat this as a valid
							// layout qualifier.
							let span = Span::new(
								kw_span.start,
								walker.get_last_span().end,
							);
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::LayoutMissingRParen(
									span.next_single_width(),
								),
							));
							qualifiers.push(Qualifier {
								span,
								ty: QualifierTy::Layout(layouts),
							});
							break 'outer;
						}
					};

					match token {
						Token::Comma => {
							walker.push_colour(
								token_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							if prev == Prev::Comma {
								walker.push_syntax_diag(Syntax::Stmt(
									StmtDiag::LayoutExpectedLayoutAfterComma(
										Span::new(
											prev_span.start,
											token_span.end,
										),
									),
								));
							} else if prev == Prev::None {
								walker.push_syntax_diag(Syntax::Stmt(StmtDiag::LayoutExpectedLayoutBetweenParenComma(
									Span::new(prev_span.start, token_span.end)
								)));
							}
							prev = Prev::Comma;
							prev_span = token_span;
							continue;
						}
						Token::RParen => {
							walker.push_colour(
								token_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							break token_span;
						}
						_ => {}
					}

					if prev == Prev::Layout {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::LayoutExpectedCommaAfterLayout(
								prev_span.next_single_width(),
							),
						));
					}
					let layout_span_start = token_span.start;

					// Consume the layout identifier. This creates a constructor either for a layout which only
					// consists of an identifier, or for a layout which expects an expression.
					let constructor: Either<
						LayoutTy,
						fn(Option<Expr>) -> LayoutTy,
					> = if let Token::Ident(str) = token {
						match str.as_ref() {
							"packed" => Either::Left(LayoutTy::Packed),
							"std140" => Either::Left(LayoutTy::Std140),
							"std430" => Either::Left(LayoutTy::Std430),
							"row_major" => Either::Left(LayoutTy::RowMajor),
							"column_major" => {
								Either::Left(LayoutTy::ColumnMajor)
							}
							"binding" => Either::Right(LayoutTy::Binding),
							"offset" => Either::Right(LayoutTy::Offset),
							"align" => Either::Right(LayoutTy::Align),
							"location" => Either::Right(LayoutTy::Location),
							"component" => Either::Right(LayoutTy::Component),
							"index" => Either::Right(LayoutTy::Index),
							"points" => Either::Left(LayoutTy::Points),
							"lines" => Either::Left(LayoutTy::Lines),
							"isolines" => Either::Left(LayoutTy::Isolines),
							"triangles" => Either::Left(LayoutTy::Triangles),
							"quads" => Either::Left(LayoutTy::Quads),
							"equal_spacing" => {
								Either::Left(LayoutTy::EqualSpacing)
							}
							"fractional_even_spacing" => {
								Either::Left(LayoutTy::FractionalEvenSpacing)
							}
							"fractional_odd_spacing" => {
								Either::Left(LayoutTy::FractionalOddSpacing)
							}
							"cw" => Either::Left(LayoutTy::Clockwise),
							"ccw" => Either::Left(LayoutTy::CounterClockwise),
							"point_mode" => Either::Left(LayoutTy::PointMode),
							"line_adjacency" => {
								Either::Left(LayoutTy::LineAdjacency)
							}
							"triangle_adjacency" => {
								Either::Left(LayoutTy::TriangleAdjacency)
							}
							"invocations" => {
								Either::Right(LayoutTy::Invocations)
							}
							"origin_upper_left" => {
								Either::Left(LayoutTy::OriginUpperLeft)
							}
							"pixel_center_integer" => {
								Either::Left(LayoutTy::PixelCenterInteger)
							}
							"early_fragment_tests" => {
								Either::Left(LayoutTy::EarlyFragmentTests)
							}
							"local_size_x" => {
								Either::Right(LayoutTy::LocalSizeX)
							}
							"local_size_y" => {
								Either::Right(LayoutTy::LocalSizeY)
							}
							"local_size_z" => {
								Either::Right(LayoutTy::LocalSizeZ)
							}
							"xfb_buffer" => Either::Right(LayoutTy::XfbBuffer),
							"xfb_stride" => Either::Right(LayoutTy::XfbStride),
							"xfb_offset" => Either::Right(LayoutTy::XfbOffset),
							"vertices" => Either::Right(LayoutTy::Vertices),
							"line_strip" => Either::Left(LayoutTy::LineStrip),
							"triangle_strip" => {
								Either::Left(LayoutTy::TriangleStrip)
							}
							"max_vertices" => {
								Either::Right(LayoutTy::MaxVertices)
							}
							"stream" => Either::Right(LayoutTy::Stream),
							"depth_any" => Either::Left(LayoutTy::DepthAny),
							"depth_greater" => {
								Either::Left(LayoutTy::DepthGreater)
							}
							"depth_less" => Either::Left(LayoutTy::DepthLess),
							"depth_unchanged" => {
								Either::Left(LayoutTy::DepthUnchanged)
							}
							_ => {
								// We have an identifier that is not a valid layout. We ignore it and continue
								// for the next layout.
								walker.push_colour(
									token_span,
									SyntaxType::UnresolvedIdent,
								);
								walker.push_syntax_diag(Syntax::Stmt(
									StmtDiag::LayoutInvalidIdent(token_span),
								));
								walker.advance();
								prev = Prev::Invalid;
								prev_span = token_span;
								continue;
							}
						}
					} else if let Token::Shared = token {
						Either::Left(LayoutTy::Shared)
					} else {
						// We have a token that is not a valid layout. We ignore it and continue for the next
						// layout.
						walker.push_colour(token_span, SyntaxType::Invalid);
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::LayoutInvalidIdent(token_span),
						));
						walker.advance();
						prev = Prev::Invalid;
						prev_span = token_span;
						continue;
					};

					let (constructor, ident_span) = match constructor {
						Either::Left(ty) => {
							walker.push_colour(
								token_span,
								SyntaxType::LayoutQualifier,
							);
							walker.advance();
							layouts.push(Layout {
								span: token_span,
								ty,
							});
							prev = Prev::Layout;
							prev_span = token_span;
							continue;
						}
						Either::Right(constructor) => {
							walker.push_colour(
								token_span,
								SyntaxType::LayoutQualifier,
							);
							walker.advance();
							(constructor, token_span)
						}
					};

					// We have a layout identifier which expects an expression.

					// Consume the `=`.
					let (token, token_span) = match walker.peek() {
						Some(t) => t,
						None => {
							// We are missing the equals sign and we don't know what comes after. We ignore this
							// layout.
							let span = Span::new(
								kw_span.start,
								walker.get_last_span().end,
							);
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::LayoutExpectedEqAfterIdent(
									span.next_single_width(),
								),
							));
							qualifiers.push(Qualifier {
								span,
								ty: QualifierTy::Layout(layouts),
							});
							break 'outer;
						}
					};
					let eq_span = if let Token::Op(OpTy::Eq) = token {
						walker.push_colour(token_span, SyntaxType::Operator);
						walker.advance();
						token_span
					} else {
						// We are missing the equals sign and we don't know what comes after. We ignore this
						// layout.
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::LayoutExpectedEqAfterIdent(
								ident_span.next_single_width(),
							),
						));
						prev = Prev::Layout;
						prev_span = ident_span;
						continue;
					};

					// Consume the expression.
					let value_expr = match expr_parser(
						walker,
						Mode::DisallowTopLevelList,
						[Token::RParen],
					) {
						(Some(e), mut syntax, mut semantic, mut colours) => {
							walker.append_colours(&mut colours);
							walker.append_syntax_diags(&mut syntax);
							walker.append_semantic_diags(&mut semantic);
							e
						}
						(None, _, _, _) => {
							// We are missing the expression.
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::LayoutExpectedExprAfterEq(
									eq_span.next_single_width(),
								),
							));
							layouts.push(Layout {
								span: Span::new(layout_span_start, eq_span.end),
								ty: constructor(None),
							});
							prev = Prev::Layout;
							prev_span = eq_span;
							continue;
						}
					};

					prev = Prev::Layout;
					prev_span = value_expr.span;
					layouts.push(Layout {
						span: Span::new(layout_span_start, value_expr.span.end),
						ty: constructor(Some(value_expr)),
					});
				};

				qualifiers.push(Qualifier {
					span: Span::new(kw_span.start, r_paren_span.end),
					ty: QualifierTy::Layout(layouts),
				});
				continue;
			}
			_ => break,
		}
		walker.advance();
	}

	qualifiers
}

/// Tries to parse a variable definition or a function declaration/definition, an expression statement, or an
/// interface block.
///
/// This function attempts to look for a statement at the current position. If this fails, error recovery till the
/// next clear statement delineation occurs.
///
/// - `parsing_last_for_stmt` - Set to `true` if this function is attempting to parse the increment statement in a
///   for loop header.
fn try_parse_definition_declaration_expr<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	qualifiers: Vec<Qualifier>,
	parsing_last_for_stmt: bool,
) {
	// We attempt to parse an expression at the current position.
	let (start, mut start_syntax, mut start_semantic, mut start_colours) =
		match expr_parser(walker, Mode::Default, [Token::Semi]) {
			(Some(expr), syntax, semantic, colours) => {
				(expr, syntax, semantic, colours)
			}
			(None, _, _, _) => {
				// The current token cannot begin any sort of expression. Since this function gets called if all
				// other statement branches have failed to match, it means that whatever we have cannot be a valid
				// statement at all.
				invalidate_qualifiers(walker, qualifiers);
				seek_next_stmt(walker);
				return;
			}
		};

	// We test if the expression can be converted into a type.
	if let Some(mut type_) = Type::parse(&start) {
		// Since we ran the expression parser in the Default mode, what we have so far must be something like
		// `foobar`, `int`, `vec2[3]`, `MyStruct` etc. This can be the type part of a declaration/definition, but
		// it could be just an expression statement depending on what comes next.

		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				// We lack any identifiers necessary for a declaration/definition, so this must be an expression
				// statement.
				invalidate_qualifiers(walker, qualifiers);
				walker.append_colours(&mut start_colours);
				walker.append_syntax_diags(&mut start_syntax);
				walker.append_semantic_diags(&mut start_semantic);
				if parsing_last_for_stmt {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ForExpectedRParenAfterStmts(
							start.span.next_single_width(),
						),
					))
				} else {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ExprStmtExpectedSemiAfterExpr(
							start.span.next_single_width(),
						),
					));
				}
				nodes.push(Node {
					span: start.span,
					ty: NodeTy::Expr(start),
				});
				return;
			}
		};

		// Check whether we have a function declaration/definition, whether this is an expression immediately
		// followed by a semi-colon, or whether this is an expression followed by an opening brace if we have an
		// appropriate qualifier to make this an interface block.
		match token {
			Token::Ident(i) => match walker.lookahead_1() {
				Some(next) => match next.0 {
					Token::LParen => {
						// We have a function declaration/definition.
						type_.qualifiers = qualifiers;
						let l_paren_span = next.1;
						let ident = Ident {
							name: i.clone(),
							span: token_span,
						};
						walker.append_colours(&mut start_colours);
						start_syntax.retain(|e| {
							if let Syntax::Expr(
								ExprDiag::FoundOperandAfterOperand(_, _),
							) = e
							{
								false
							} else {
								true
							}
						});
						walker.append_syntax_diags(&mut start_syntax);
						walker.append_semantic_diags(&mut start_semantic);
						walker.push_colour(
							token_span,
							SyntaxType::UncheckedIdent,
						);
						walker.advance();
						walker.push_colour(next.1, SyntaxType::Punctuation);
						walker.advance();
						parse_function(
							walker,
							nodes,
							type_,
							ident,
							l_paren_span,
						);
						return;
					}
					_ => {}
				},
				None => {}
			},
			Token::Semi => {
				// We have an expression statement.
				invalidate_qualifiers(walker, qualifiers);
				let semi_span = token_span;
				walker.append_colours(&mut start_colours);
				walker.append_syntax_diags(&mut start_syntax);
				walker.append_semantic_diags(&mut start_semantic);
				walker.push_colour(semi_span, SyntaxType::Punctuation);
				walker.advance();
				if parsing_last_for_stmt {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ForExpectedRParenAfterStmts(semi_span),
					));
				}
				nodes.push(Node {
					span: Span::new(start.span.start, semi_span.end),
					ty: NodeTy::Expr(start),
				});
				return;
			}
			Token::RParen if parsing_last_for_stmt => {
				// We have an expression statement.
				invalidate_qualifiers(walker, qualifiers);
				walker.append_colours(&mut start_colours);
				walker.append_syntax_diags(&mut start_syntax);
				walker.append_semantic_diags(&mut start_semantic);
				nodes.push(Node {
					span: start.span,
					ty: NodeTy::Expr(start),
				});
				return;
			}
			Token::LBrace => {
				// Interface blocks can begin with one of the following:
				// in
				// out
				// patch in
				// patch out
				// uniform
				// buffer
				// A layout() qualifier may precede any of these.
				if qualifiers.len() == 1 {
					match &qualifiers[0].ty {
						QualifierTy::In
						| QualifierTy::Out
						| QualifierTy::Uniform
						| QualifierTy::Buffer => {
							let l_brace_span = token_span;
							walker.append_colours(&mut start_colours);
							start_syntax.retain(|e| {
								if let Syntax::Expr(
									ExprDiag::FoundOperandAfterOperand(_, _),
								) = e
								{
									false
								} else {
									true
								}
							});
							walker.append_syntax_diags(&mut start_syntax);
							walker.append_semantic_diags(&mut start_semantic);
							walker.push_colour(
								l_brace_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							parse_interface_block(
								walker,
								nodes,
								qualifiers,
								start,
								l_brace_span,
							);
							return;
						}
						_ => {}
					}
				} else if qualifiers.len() == 2 {
					match (&qualifiers[0].ty, &qualifiers[1].ty) {
						(QualifierTy::Patch, QualifierTy::In)
						| (QualifierTy::Patch, QualifierTy::Out)
						| (QualifierTy::Layout(_), QualifierTy::In)
						| (QualifierTy::Layout(_), QualifierTy::Out)
						| (QualifierTy::Layout(_), QualifierTy::Uniform)
						| (QualifierTy::Layout(_), QualifierTy::Buffer) => {
							let l_brace_span = token_span;
							walker.append_colours(&mut start_colours);
							start_syntax.retain(|e| {
								if let Syntax::Expr(
									ExprDiag::FoundOperandAfterOperand(_, _),
								) = e
								{
									false
								} else {
									true
								}
							});
							walker.append_syntax_diags(&mut start_syntax);
							walker.append_semantic_diags(&mut start_semantic);
							walker.push_colour(
								l_brace_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							parse_interface_block(
								walker,
								nodes,
								qualifiers,
								start,
								l_brace_span,
							);
							return;
						}
						(_, _) => {}
					}
				} else if qualifiers.len() == 3 {
					match (
						&qualifiers[0].ty,
						&qualifiers[1].ty,
						&qualifiers[2].ty,
					) {
						(
							QualifierTy::Layout(_),
							QualifierTy::Patch,
							QualifierTy::In,
						)
						| (
							QualifierTy::Layout(_),
							QualifierTy::Patch,
							QualifierTy::Out,
						) => {
							let l_brace_span = token_span;
							walker.append_colours(&mut start_colours);
							start_syntax.retain(|e| {
								if let Syntax::Expr(
									ExprDiag::FoundOperandAfterOperand(_, _),
								) = e
								{
									false
								} else {
									true
								}
							});
							walker.append_syntax_diags(&mut start_syntax);
							walker.append_semantic_diags(&mut start_semantic);
							walker.push_colour(
								l_brace_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							parse_interface_block(
								walker,
								nodes,
								qualifiers,
								start,
								l_brace_span,
							);
							return;
						}
						(_, _, _) => {}
					}
				}
			}
			_ => {}
		}

		// We don't have a function declaration/definition, nor an interface block, so this must be a variable
		// definition (with possibly an initialization) or an expression statement.

		// We attempt to parse an expression for the identifier(s).
		let (
			ident_expr,
			mut ident_syntax,
			mut ident_semantic,
			mut ident_colours,
		) = match expr_parser(walker, Mode::BreakAtEq, [Token::Semi]) {
			(Some(e), syntax, semantic, colours) => {
				(e, syntax, semantic, colours)
			}
			(None, _, _, _) => {
				// We have an expression followed by neither another expression nor a semi-colon. We treat this
				// as an expression statement since that's the closest possible match.
				invalidate_qualifiers(walker, qualifiers);
				walker.append_colours(&mut start_colours);
				walker.append_syntax_diags(&mut start_syntax);
				walker.append_semantic_diags(&mut start_semantic);
				if parsing_last_for_stmt {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ForExpectedRParenAfterStmts(
							start.span.next_single_width(),
						),
					))
				} else {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ExprStmtExpectedSemiAfterExpr(
							start.span.next_single_width(),
						),
					));
				}
				nodes.push(Node {
					span: start.span,
					ty: NodeTy::Expr(start),
				});
				return;
			}
		};
		let ident_span = ident_expr.span;

		// We test if the identifier(s) expression can be converted into one or more variable identifiers.
		let ident_info = if let Some(i) = Type::parse_var_idents(&ident_expr) {
			i
		} else {
			// We have a second expression after the first expression, but the second expression can't be converted
			// to one or more identifiers for a variable definition. We treat the first expression as an expression
			// statement, and the second expression as invalid.
			invalidate_qualifiers(walker, qualifiers);
			walker.append_colours(&mut start_colours);
			walker.append_syntax_diags(&mut start_syntax);
			walker.append_semantic_diags(&mut start_semantic);
			if parsing_last_for_stmt {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ForExpectedRParenAfterStmts(
						start.span.next_single_width(),
					),
				))
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ExprStmtExpectedSemiAfterExpr(
						start.span.next_single_width(),
					),
				));
			}
			nodes.push(Node {
				span: start.span,
				ty: NodeTy::Expr(start),
			});
			for SyntaxToken { span, .. } in ident_colours {
				walker.push_colour(span, SyntaxType::Invalid);
			}
			seek_next_stmt(walker);
			return;
		};

		// We have one expression which can be converted to a type, and a second expression which can be converted
		// to one or more identifiers. That means the first expression will have a syntax error about a missing
		// operator between the two; we remove that error since in this case it's not applicable.
		start_syntax.retain(|e| {
			if let Syntax::Expr(ExprDiag::FoundOperandAfterOperand(_, _)) = e {
				false
			} else {
				true
			}
		});
		type_.qualifiers = qualifiers;
		walker.append_colours(&mut start_colours);
		walker.append_syntax_diags(&mut start_syntax);
		walker.append_semantic_diags(&mut start_semantic);
		walker.append_colours(&mut ident_colours);
		walker.append_syntax_diags(&mut ident_syntax);
		walker.append_semantic_diags(&mut ident_semantic);

		fn var_def(
			type_: Type,
			idents: Vec<(Ident, Vec<ArrSize>)>,
			end_pos: usize,
		) -> Node {
			let span = Span::new(type_.span.start, end_pos);
			let mut vars = combine_type_with_idents(type_, idents);
			match vars.len() {
				1 => {
					let (type_, ident) = vars.remove(0);
					Node {
						span,
						ty: NodeTy::VarDef { type_, ident },
					}
				}
				_ => Node {
					span,
					ty: NodeTy::VarDefs(vars),
				},
			}
		}

		fn var_def_init(
			type_: Type,
			idents: Vec<(Ident, Vec<ArrSize>)>,
			value: Option<Expr>,
			end_pos: usize,
		) -> Node {
			let span = Span::new(type_.span.start, end_pos);
			let mut vars = combine_type_with_idents(type_, idents);
			match vars.len() {
				1 => {
					let (type_, ident) = vars.remove(0);
					Node {
						span,
						ty: NodeTy::VarDefInit {
							type_,
							ident,
							value,
						},
					}
				}
				_ => Node {
					span,
					ty: NodeTy::VarDefInits(vars, value),
				},
			}
		}

		// Consume the `;` for a definition, or a `=` for a definition with initialization.
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				// We have something that matches the start of a variable definition. Since we have neither the `;`
				// or `=`, we assume that this is a definition without initialization that is missing the
				// semi-colon.
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::VarDefExpectedSemiOrEqAfterIdents(
						ident_span.next_single_width(),
					),
				));
				nodes.push(var_def(type_, ident_info, ident_span.end));
				return;
			}
		};
		if *token == Token::Semi {
			// We have a variable definition without initialization.
			let semi_span = token_span;
			walker.push_colour(semi_span, SyntaxType::Punctuation);
			walker.advance();
			nodes.push(var_def(type_, ident_info, semi_span.end));
			return;
		} else if *token == Token::Op(lexer::OpTy::Eq) {
			// We have a variable definition with initialization.
			let eq_span = token_span;
			walker.push_colour(eq_span, SyntaxType::Operator);
			walker.advance();

			// Consume the value expression.
			let value_expr =
				match expr_parser(walker, Mode::Default, [Token::Semi]) {
					(Some(e), mut syntax, mut semantic, mut colours) => {
						walker.append_colours(&mut colours);
						walker.append_syntax_diags(&mut syntax);
						walker.append_semantic_diags(&mut semantic);
						e
					}
					(None, _, _, _) => {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::VarDefInitExpectedValueAfterEq(
								eq_span.next_single_width(),
							),
						));
						nodes.push(var_def_init(
							type_,
							ident_info,
							None,
							eq_span.end,
						));
						seek_next_stmt(walker);
						return;
					}
				};

			// Consume the semi-colon.
			let (token, token_span) = match walker.peek() {
				Some(t) => t,
				None => {
					let value_span = value_expr.span;
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::VarDefInitExpectedSemiAfterValue(
							value_span.next_single_width(),
						),
					));
					nodes.push(var_def_init(
						type_,
						ident_info,
						Some(value_expr),
						value_span.end,
					));
					return;
				}
			};
			if *token == Token::Semi {
				let semi_span = token_span;
				walker.push_colour(semi_span, SyntaxType::Punctuation);
				walker.advance();
				nodes.push(var_def_init(
					type_,
					ident_info,
					Some(value_expr),
					semi_span.end,
				));
				return;
			} else {
				let end_span = token_span;
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::VarDefInitExpectedSemiAfterValue(
						end_span.next_single_width(),
					),
				));
				nodes.push(var_def_init(
					type_,
					ident_info,
					Some(value_expr),
					end_span.end,
				));
				seek_next_stmt(walker);
				return;
			}
		} else {
			// We have something that matches the start of a variable definition. Since we have neither the `;` or
			// `=`, we assume that this is a definition without initialization which is missing the semi-colon.
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::VarDefExpectedSemiOrEqAfterIdents(
					ident_span.next_single_width(),
				),
			));
			nodes.push(var_def(type_, ident_info, ident_span.end));
			seek_next_stmt(walker);
			return;
		}
	}

	// We have an expression which cannot be parsed as a type, so this cannot start a declaration/definition nor an
	// interface block; it must therefore be a standalone expression statement.
	invalidate_qualifiers(walker, qualifiers);
	let expr = start;
	walker.append_colours(&mut start_colours);
	walker.append_syntax_diags(&mut start_syntax);
	walker.append_semantic_diags(&mut start_semantic);

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => None,
	};
	if semi_span.is_none() {
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::ExprStmtExpectedSemiAfterExpr(
				expr.span.next_single_width(),
			),
		));
		seek_next_stmt(walker);
	}

	nodes.push(Node {
		span: if let Some(semi_span) = semi_span {
			Span::new(expr.span.start, semi_span.end)
		} else {
			expr.span
		},
		ty: NodeTy::Expr(expr),
	});
}

/// Parses a function declaration/definition.
///
/// This function assumes that the return type, ident, and opening parenthesis have been consumed.
fn parse_function<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	return_type: Type,
	ident: Ident,
	l_paren_span: Span,
) {
	// Look for any parameters until we hit a closing `)` parenthesis.
	#[derive(PartialEq)]
	enum Prev {
		None,
		Param,
		Comma,
		Invalid,
	}
	let mut prev = Prev::None;
	let mut prev_span = l_paren_span;
	let mut params = Vec::new();
	let param_end_span = loop {
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				// We have not yet finished parsing the parameter list, but we treat this as a valid declaration
				// since that's the closest match.
				let span = Span::new(return_type.span.start, prev_span.end);
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ParamsExpectedRParen(
						prev_span.next_single_width(),
					),
				));
				nodes.push(Node {
					span,
					ty: NodeTy::FnDecl {
						return_type,
						ident,
						params,
					},
				});
				return;
			}
		};

		match token {
			Token::Comma => {
				walker.push_colour(token_span, SyntaxType::Punctuation);
				walker.advance();
				if prev == Prev::Comma {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ParamsExpectedParamAfterComma(
							Span::new_between(prev_span, token_span),
						),
					));
				} else if prev == Prev::None {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ParamsExpectedParamBetweenParenComma(
							Span::new_between(l_paren_span, token_span),
						),
					));
				}
				prev = Prev::Comma;
				prev_span = token_span;
				continue;
			}
			Token::RParen => {
				walker.push_colour(token_span, SyntaxType::Punctuation);
				walker.advance();
				if prev == Prev::Comma {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ParamsExpectedParamAfterComma(
							Span::new_between(prev_span, token_span),
						),
					));
				}
				break token_span;
			}
			Token::Semi => {
				walker.push_colour(token_span, SyntaxType::Punctuation);
				walker.advance();
				// We have not yet finished parsing the parameter list but we've encountered a semi-colon. We treat
				// this as a valid declaration since that's the closest match.
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ParamsExpectedRParen(
						prev_span.next_single_width(),
					),
				));
				nodes.push(Node {
					span: Span::new(return_type.span.start, token_span.end),
					ty: NodeTy::FnDecl {
						return_type,
						ident,
						params,
					},
				});
				return;
			}
			Token::LBrace => {
				walker.push_colour(token_span, SyntaxType::Punctuation);
				// We don't advance because the next check after this loop checks for a l-brace.

				// We have not yet finished parsing the parameter list but we've encountered a l-brace. We treat
				// this as a potentially valid definition since that's the closest match.
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ParamsExpectedRParen(
						prev_span.next_single_width(),
					),
				));
				break token_span;
			}
			_ => {}
		}

		if prev == Prev::Param {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ParamsExpectedCommaAfterParam(
					prev_span.next_single_width(),
				),
			));
		}
		let param_span_start = token_span.start;

		let qualifiers = try_parse_qualifiers(walker);

		// Consume the type.
		let mut type_ = match expr_parser(
			walker,
			Mode::TakeOneUnit,
			[Token::Semi, Token::LBrace],
		) {
			(Some(e), _, mut semantic, mut colours) => {
				if let Some(type_) = Type::parse(&e) {
					walker.append_colours(&mut colours);
					walker.append_semantic_diags(&mut semantic);
					type_
				} else {
					// We have an expression which cannot be parsed into a type. We ignore this and continue
					// searching for the next parameter.
					for SyntaxToken { span, .. } in colours {
						walker.push_colour(span, SyntaxType::Invalid);
					}
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ParamsInvalidTypeExpr(e.span),
					));
					prev = Prev::Invalid;
					prev_span = Span::new(param_span_start, e.span.end);
					continue;
				}
			}
			(None, _, _, _) => {
				// We immediately have a token that is not an expression. We ignore this and loop until we hit
				// something recognizable.
				let end_span = loop {
					match walker.peek() {
						Some((token, span)) => {
							if *token == Token::Comma
								|| *token == Token::RParen || *token
								== Token::Semi || *token == Token::LBrace
							{
								break span;
							} else {
								walker.push_colour(span, SyntaxType::Invalid);
								walker.advance();
								continue;
							}
						}
						None => break walker.get_last_span(),
					}
				};
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ParamsInvalidTypeExpr(Span::new(
						param_span_start,
						end_span.end,
					)),
				));
				prev = Prev::Invalid;
				prev_span = token_span;
				continue;
			}
		};

		// Look for the optional ident.
		let (ident_expr, ident_colours) = match expr_parser(
			walker,
			Mode::TakeOneUnit,
			[Token::Semi, Token::LBrace],
		) {
			(Some(e), _, mut semantic, colours) => {
				walker.append_semantic_diags(&mut semantic);
				(e, colours)
			}
			(None, _, _, _) => {
				// We have a first expression and then something that is not an expression. We treat this as an
				// anonymous parameter, whatever the current token is will be dealt with in the next iteration.
				type_.qualifiers = qualifiers;
				let param_span = Span::new(param_span_start, type_.span.end);
				params.push(Param {
					span: param_span,
					type_,
					ident: Omittable::None,
				});
				prev = Prev::Param;
				prev_span = param_span;
				continue;
			}
		};
		let ident_span = ident_expr.span;

		// Invariant: This vector is guaranteed to have a length of 1 because the `ident_expr` was parsed with the
		// `TakeOneUnit` mode which prevents lists.
		let ident_info = if let Some(i) = Type::parse_var_idents(&ident_expr) {
			i
		} else {
			// We have a second expression after the first expression, but the second expression can't be converted
			// to an identifier for the parameter. We treat the first type expression as an anonymous parameter,
			// and the second expression as invalid.
			let param_span = Span::new(param_span_start, type_.span.end);
			type_.qualifiers = qualifiers;
			params.push(Param {
				span: Span::new(param_span_start, type_.span.end),
				type_,
				ident: Omittable::None,
			});
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ParamsInvalidIdentExpr(ident_expr.span),
			));
			for SyntaxToken { span, .. } in ident_colours {
				walker.push_colour(span, SyntaxType::Invalid);
			}
			prev = Prev::Param;
			prev_span = param_span;
			continue;
		};

		type_.qualifiers = qualifiers;
		let (type_, ident) =
			combine_type_with_idents(type_, ident_info).remove(0);
		let param_span = Span::new(param_span_start, ident_span.end);
		params.push(Param {
			span: param_span,
			type_,
			ident: Omittable::Some(ident),
		});
		prev = Prev::Param;
		prev_span = param_span;
	};

	// Consume the `;` for a declaration or a `{` for a definition.
	let (token, token_span) = match walker.peek() {
		Some(t) => t,
		None => {
			// This branch will only be triggered if we exited the param loop with a `)`, it will not trigger if we
			// exit with a `{` because that token is not consumed.

			// We are missing a `;` for a declaration. We treat this as a declaration since that's the closest
			// match.
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::FnExpectedSemiOrLBraceAfterParams(
					param_end_span.next_single_width(),
				),
			));
			nodes.push(Node {
				span: Span::new(return_type.span.start, param_end_span.end),
				ty: NodeTy::FnDecl {
					return_type,
					ident,
					params,
				},
			});
			return;
		}
	};
	if *token == Token::Semi {
		// We have a declaration.
		walker.push_colour(token_span, SyntaxType::Punctuation);
		walker.advance();
		nodes.push(Node {
			span: Span::new(return_type.span.start, param_end_span.end),
			ty: NodeTy::FnDecl {
				return_type,
				ident,
				params,
			},
		});
	} else if *token == Token::LBrace {
		// We have a definition.
		let l_brace_span = token_span;
		walker.push_colour(l_brace_span, SyntaxType::Punctuation);
		walker.advance();
		let body = parse_scope(walker, brace_scope, l_brace_span);
		nodes.push(Node {
			span: Span::new(return_type.span.start, body.span.end),
			ty: NodeTy::FnDef {
				return_type,
				ident,
				params,
				body,
			},
		});
	} else {
		// We are missing a `;` for a declaration. We treat this as a declaration since that's the closest match.
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::FnExpectedSemiOrLBraceAfterParams(
				param_end_span.next_single_width(),
			),
		));
		nodes.push(Node {
			span: Span::new(return_type.span.start, param_end_span.end),
			ty: NodeTy::FnDecl {
				return_type,
				ident,
				params,
			},
		});
		seek_next_stmt(walker);
	}
}

/// Parses a subroutine type, associated function, or a subroutine uniform.
///
/// This function assumes that the `subroutine` keyword is not yet consumed.
fn parse_subroutine<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	let (token, token_span) = match walker.peek() {
		Some(t) => t,
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SubroutineExpectedTypeFuncUniformAfterKw(
					kw_span.next_single_width(),
				),
			));
			return;
		}
	};

	if *token == Token::Uniform {
		// We have a subroutine uniform definition.
		let uniform_kw_span = token_span;
		walker.push_colour(uniform_kw_span, SyntaxType::Keyword);
		walker.advance();
		let mut inner = Vec::new();
		try_parse_definition_declaration_expr(
			walker,
			&mut inner,
			vec![],
			false,
		);

		if inner.is_empty() {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SubroutineExpectedVarDefAfterUniformKw(
					uniform_kw_span.next_single_width(),
				),
			));
		} else {
			let first = inner.remove(0);
			match first.ty {
				NodeTy::VarDef { type_, ident } => {
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineUniformDef { type_, ident },
					});
				}
				_ => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineExpectedVarDefAfterUniformKw(
							uniform_kw_span.next_single_width(),
						),
					));
					nodes.push(first);
				}
			}
			inner.into_iter().for_each(|n| nodes.push(n));
		}
	} else if *token == Token::LParen {
		// We have an associated function definition.
		let l_paren_span = token_span;
		walker.push_colour(l_paren_span, SyntaxType::Punctuation);
		walker.advance();

		// Look for any subroutine identifiers until we hit a closing `)` parenthesis.
		#[derive(PartialEq)]
		enum Prev {
			None,
			Ident,
			Comma,
			Invalid,
		}
		let mut prev = Prev::None;
		let mut prev_span = l_paren_span;
		let mut associations = Vec::new();
		let r_paren_span = loop {
			let (token, token_span) = match walker.peek() {
				Some(t) => t,
				None => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineAssociatedListExpectedRParen(
							prev_span.next_single_width(),
						),
					));
					return;
				}
			};

			match token {
				Token::Comma => {
					walker.push_colour(token_span, SyntaxType::Punctuation);
					walker.advance();
					if prev == Prev::Comma {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::SubroutineAssociatedListExpectedIdentAfterComma(
								Span::new_between(prev_span, token_span),
							),
						));
					} else if prev == Prev::None {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::SubroutineAssociatedListExpectedIdentBetweenParenComma(
								Span::new_between(l_paren_span, token_span),
							),
						));
					}
					prev = Prev::Comma;
					prev_span = token_span;
					continue;
				}
				Token::RParen => {
					walker.push_colour(token_span, SyntaxType::Punctuation);
					walker.advance();
					if prev == Prev::Comma {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::SubroutineAssociatedListExpectedIdentAfterComma(
								Span::new_between(prev_span, token_span),
							),
						));
					}
					break token_span;
				}
				Token::Ident(str) => {
					associations.push(Ident {
						name: str.to_owned(),
						span: token_span,
					});
					walker.push_colour(token_span, SyntaxType::UncheckedIdent);
					walker.advance();
					if prev == Prev::Ident {
						walker.push_syntax_diag(Syntax::Stmt(StmtDiag::SubroutineAssociatedListExpectedCommaAfterIdent(
							prev_span.next_single_width()
						)));
					}
					prev = Prev::Ident;
					prev_span = token_span;
					continue;
				}
				_ => {
					walker.push_colour(token_span, SyntaxType::Invalid);
					walker.advance();
					prev = Prev::Invalid;
					prev_span = token_span;
				}
			}
		};

		let mut inner = Vec::new();
		try_parse_definition_declaration_expr(
			walker,
			&mut inner,
			vec![],
			false,
		);

		if inner.is_empty() {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SubroutineExpectedFnDefAfterAssociatedList(
					r_paren_span.next_single_width(),
				),
			));
		} else {
			let first = inner.remove(0);
			match first.ty {
				NodeTy::FnDef {
					return_type,
					ident,
					params,
					body,
				} => {
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineFnDef {
							associations,
							return_type,
							ident,
							params,
							body: Some(body),
						},
					});
				}
				NodeTy::FnDecl {
					return_type,
					ident,
					params,
				} => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineExpectedFnDefAfterAssociatedListFoundDecl(
							first.span,
						),
					));
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineFnDef {
							associations,
							return_type,
							ident,
							params,
							body: None,
						},
					});
				}
				_ => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineExpectedFnDefAfterAssociatedList(
							r_paren_span.next_single_width(),
						),
					));
					nodes.push(first);
				}
			}
		}
		inner.into_iter().for_each(|n| nodes.push(n));
	} else {
		// We have a subroutine type declaration.
		let mut inner = Vec::new();
		try_parse_definition_declaration_expr(
			walker,
			&mut inner,
			vec![],
			false,
		);

		if inner.is_empty() {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SubroutineExpectedTypeFuncUniformAfterKw(
					kw_span.next_single_width(),
				),
			));
		} else {
			let first = inner.remove(0);
			match first.ty {
				NodeTy::FnDecl {
					return_type,
					ident,
					params,
				} => {
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineTypeDecl {
							return_type,
							ident,
							params,
						},
					});
				}
				NodeTy::FnDef {
					return_type,
					ident,
					params,
					body,
				} => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineMissingAssociationsForFnDef(
							Span::new_between(kw_span, return_type.span),
						),
					));
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineFnDef {
							associations: vec![],
							return_type,
							ident,
							params,
							body: Some(body),
						},
					});
				}
				NodeTy::VarDef { type_, ident } => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineMissingUniformKwForUniformDef(
							Span::new_between(kw_span, type_.span),
						),
					));
					nodes.push(Node {
						span: Span::new(kw_span.start, first.span.end),
						ty: NodeTy::SubroutineUniformDef { type_, ident },
					});
				}
				_ => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SubroutineExpectedTypeFuncUniformAfterKw(
							kw_span.next_single_width(),
						),
					));
					nodes.push(first);
				}
			}
			inner.into_iter().for_each(|n| nodes.push(n));
		}
	}
}

/// Parses an interface block.
///
/// This function assumes that the qualifiers, identifier, and opening brace have been consumed.
///
/// # Invariants
/// `qualifiers` is not empty.
fn parse_interface_block<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	qualifiers: Vec<Qualifier>,
	ident_expr: Expr,
	l_brace_span: Span,
) {
	let ident = match ident_expr.ty {
		ExprTy::Ident(i) => i,
		_ => {
			// We do not have an identifier before the opening brace. We consume tokens until we hit a closing
			// brace.
			loop {
				match walker.peek() {
					Some((token, span)) => {
						if *token == Token::RBrace {
							walker.push_colour(span, SyntaxType::Punctuation);
							walker.advance();
							break;
						} else {
							walker.push_colour(span, SyntaxType::Invalid);
							walker.advance();
						}
					}
					None => break,
				}
			}
			return;
		}
	};

	let interface_span_start = qualifiers.first().unwrap().span.start;

	// Parse the contents of the body.
	let body = parse_scope(walker, brace_scope, l_brace_span);
	if body.contents.is_empty() {
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::InterfaceExpectedAtLeastOneStmtInBody(body.span),
		))
	}
	for stmt in &body.contents {
		match &stmt.ty {
			NodeTy::VarDef { .. }
			| NodeTy::VarDefInit { .. }
			| NodeTy::VarDefs(_)
			| NodeTy::VarDefInits(_, _) => {}
			_ => {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::InterfaceInvalidStmtInBody(stmt.span),
				));
			}
		}
	}

	// Look for an optional instance definition.
	let instance = match expr_parser(walker, Mode::TakeOneUnit, [Token::Semi]) {
		(Some(e), mut syntax, mut semantic, mut colours) => {
			if let Some(_) = Type::parse(&e) {
				// This expression can be a valid instance definition.
				walker.append_colours(&mut colours);
				walker.append_syntax_diags(&mut syntax);
				walker.append_semantic_diags(&mut semantic);
				Omittable::Some(e)
			} else {
				walker.append_colours(&mut colours);
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::InterfaceExpectedInstanceOrSemiAfterBody(e.span),
				));
				nodes.push(Node {
					span: Span::new(interface_span_start, body.span.end),
					ty: NodeTy::InterfaceDef {
						qualifiers,
						ident,
						body,
						instance: Omittable::None,
					},
				});
				return;
			}
		}
		_ => Omittable::None,
	};

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => None,
	};
	if semi_span.is_none() {
		if let Omittable::Some(ref i) = instance {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::InterfaceExpectedSemiAfterInstance(
					i.span.next_single_width(),
				),
			));
		} else {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::InterfaceExpectedInstanceOrSemiAfterBody(
					body.span.next_single_width(),
				),
			));
		}
	}

	nodes.push(Node {
		span: Span::new(
			interface_span_start,
			if let Some(semi_span) = semi_span {
				semi_span.end
			} else {
				if let Omittable::Some(ref i) = instance {
					i.span.end
				} else {
					body.span.end
				}
			},
		),
		ty: NodeTy::InterfaceDef {
			qualifiers,
			ident,
			body,
			instance,
		},
	});
}

/// Parses a struct declaration/definition.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_struct<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	qualifiers: Vec<Qualifier>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the identifier.
	let ident = match expr_parser(
		walker,
		Mode::TakeOneUnit,
		[Token::LBrace, Token::Semi],
	) {
		(Some(e), _, mut semantic, mut colours) => match e.ty {
			ExprTy::Ident(i) => {
				walker.append_colours(&mut colours);
				walker.append_semantic_diags(&mut semantic);
				i
			}
			_ => {
				walker.append_colours(&mut colours);
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::StructExpectedIdentAfterKw(e.span),
				));
				return;
			}
		},
		(None, _, _, _) => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::StructExpectedIdentAfterKw(
					kw_span.next_single_width(),
				),
			));
			return;
		}
	};

	let struct_span_start = if let Some(q) = qualifiers.first() {
		q.span.start
	} else {
		kw_span.start
	};

	// Consume the `{`.
	let (token, token_span) = match walker.peek() {
		Some(t) => t,
		None => {
			// We don't create a struct declaration because it would result in two errors that would reduce
			// clarity.
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::StructExpectedLBraceAfterIdent(
					ident.span.next_single_width(),
				),
			));
			return;
		}
	};
	let l_brace_span = if *token == Token::LBrace {
		walker.push_colour(token_span, SyntaxType::Punctuation);
		walker.advance();
		token_span
	} else if *token == Token::Semi {
		// We have a declaration, (which is illegal).
		let span = Span::new(struct_span_start, token_span.end);
		walker.push_colour(token_span, SyntaxType::Punctuation);
		walker.push_syntax_diag(Syntax::Stmt(StmtDiag::StructDeclIsIllegal(
			span,
		)));
		walker.advance();
		nodes.push(Node {
			span,
			ty: NodeTy::StructDecl { qualifiers, ident },
		});
		return;
	} else {
		// We don't create a struct declaration because it would result in two errors that would reduce clarity.
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::StructExpectedLBraceAfterIdent(
				ident.span.next_single_width(),
			),
		));
		return;
	};

	// Parse the contents of the body.
	let body = parse_scope(walker, brace_scope, l_brace_span);
	if body.contents.is_empty() {
		walker.push_syntax_diag(Syntax::Stmt(
			StmtDiag::StructExpectedAtLeastOneStmtInBody(body.span),
		));
	}
	for stmt in &body.contents {
		match &stmt.ty {
			NodeTy::VarDef { .. }
			| NodeTy::VarDefInit { .. }
			| NodeTy::VarDefs(_)
			| NodeTy::VarDefInits(_, _) => {}
			_ => {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::StructInvalidStmtInBody(stmt.span),
				));
			}
		}
	}

	// Look for an optional instance identifier.
	let instance = match expr_parser(walker, Mode::TakeOneUnit, [Token::Semi]) {
		(Some(e), _, mut semantic, mut colours) => match e.ty {
			ExprTy::Ident(i) => {
				walker.append_colours(&mut colours);
				walker.append_semantic_diags(&mut semantic);
				Omittable::Some(i)
			}
			_ => {
				walker.append_colours(&mut colours);
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::StructExpectedInstanceOrSemiAfterBody(e.span),
				));
				nodes.push(Node {
					span: Span::new(struct_span_start, body.span.end),
					ty: NodeTy::StructDef {
						qualifiers,
						ident,
						body,
						instance: Omittable::None,
					},
				});
				return;
			}
		},
		_ => Omittable::None,
	};

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => None,
	};
	if semi_span.is_none() {
		if let Omittable::Some(ref i) = instance {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::StructExpectedSemiAfterInstance(
					i.span.next_single_width(),
				),
			));
		} else {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::StructExpectedInstanceOrSemiAfterBody(
					body.span.next_single_width(),
				),
			));
		}
	}

	nodes.push(Node {
		span: Span::new(
			struct_span_start,
			if let Some(semi_span) = semi_span {
				semi_span.end
			} else {
				if let Omittable::Some(ref i) = instance {
					i.span.end
				} else {
					body.span.end
				}
			},
		),
		ty: NodeTy::StructDef {
			qualifiers,
			ident,
			body,
			instance,
		},
	});
}

/// Parses an if statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_if<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	let mut branches = Vec::new();
	let mut first_iter = true;
	// On the first iteration of this loop, the current token is guaranteed to be `Token::If`.
	loop {
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				nodes.push(Node {
					span: Span::new(kw_span.start, walker.get_last_span().end),
					ty: NodeTy::If(branches),
				});
				return;
			}
		};

		let else_kw_span = if *token != Token::Else && !first_iter {
			// We've found a token that is not `else`, which means we've finished the current if statement.
			nodes.push(Node {
				span: Span::new(
					kw_span.start,
					if let Some(branch) = branches.last() {
						branch.span.end
					} else {
						kw_span.end
					},
				),
				ty: NodeTy::If(branches),
			});
			return;
		} else if *token == Token::If && first_iter {
			// In the first iteration this variable is ignored. This is just to prevent divergence of branches
			// which would require a different overall parsing algorithm.
			token_span
		} else {
			// Consume the `else` keyword.
			walker.push_colour(token_span, SyntaxType::Keyword);
			walker.advance();
			token_span
		};

		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				// We have an else keyword followed by nothing.
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::IfExpectedIfOrLBraceOrStmtAfterElseKw(
						walker.get_last_span().next_single_width(),
					),
				));
				nodes.push(Node {
					span: Span::new(kw_span.start, walker.get_last_span().end),
					ty: NodeTy::If(branches),
				});
				return;
			}
		};

		if *token == Token::If {
			let if_kw_span = token_span;
			walker.push_colour(if_kw_span, SyntaxType::Keyword);
			walker.advance();

			// Consume the `(`.
			let l_paren_span = match walker.peek() {
				Some((token, span)) => {
					if *token == Token::LParen {
						walker.push_colour(span, SyntaxType::Punctuation);
						walker.advance();
						Some(span)
					} else {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::IfExpectedLParenAfterKw(
								if_kw_span.next_single_width(),
							),
						));
						None
					}
				}
				None => {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::IfExpectedLParenAfterKw(
							if_kw_span.next_single_width(),
						),
					));
					branches.push(IfBranch {
						span: if first_iter {
							if_kw_span
						} else {
							Span::new(else_kw_span.start, if_kw_span.end)
						},
						condition: if first_iter {
							(IfCondition::If(None), if_kw_span)
						} else {
							(
								IfCondition::ElseIf(None),
								Span::new(else_kw_span.start, if_kw_span.end),
							)
						},
						body: None,
					});
					nodes.push(Node {
						span: Span::new(
							kw_span.start,
							walker.get_last_span().end,
						),
						ty: NodeTy::If(branches),
					});
					return;
				}
			};

			// Consume the condition expression.
			let cond_expr = match expr_parser(
				walker,
				Mode::Default,
				[Token::RParen, Token::LBrace],
			) {
				(Some(e), mut syntax, mut semantic, mut colours) => {
					walker.append_colours(&mut colours);
					walker.append_syntax_diags(&mut syntax);
					walker.append_semantic_diags(&mut semantic);
					Some(e)
				}
				(None, _, _, _) => {
					if let Some(l_paren_span) = l_paren_span {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::IfExpectedExprAfterLParen(
								l_paren_span.next_single_width(),
							),
						));
					}
					None
				}
			};

			// Consume the `)`.
			let r_paren_span = match walker.peek() {
				Some((token, span)) => {
					if *token == Token::RParen {
						walker.push_colour(span, SyntaxType::Punctuation);
						walker.advance();
						Some(span)
					} else {
						if let Some(ref cond_expr) = cond_expr {
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::IfExpectedRParenAfterExpr(
									cond_expr.span.next_single_width(),
								),
							));
						}
						None
					}
				}
				None => {
					if let Some(ref cond_expr) = cond_expr {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::IfExpectedRParenAfterExpr(
								cond_expr.span.next_single_width(),
							),
						));
					}
					let span = Span::new(
						if first_iter {
							if_kw_span.start
						} else {
							else_kw_span.start
						},
						if let Some(ref cond_expr) = cond_expr {
							cond_expr.span.end
						} else if let Some(l_paren_span) = l_paren_span {
							l_paren_span.end
						} else {
							if_kw_span.end
						},
					);
					branches.push(IfBranch {
						span,
						condition: (
							if first_iter {
								IfCondition::If(cond_expr)
							} else {
								IfCondition::ElseIf(None)
							},
							span,
						),
						body: None,
					});
					nodes.push(Node {
						span: Span::new(
							kw_span.start,
							walker.get_last_span().end,
						),
						ty: NodeTy::If(branches),
					});
					return;
				}
			};

			// Consume either the `{` for a multi-line if body or a statement for a single-statement if body.
			match walker.peek() {
				Some((token, token_span)) => {
					if *token == Token::LBrace {
						// We have a multi-line body.
						walker.push_colour(token_span, SyntaxType::Punctuation);
						walker.advance();
						let body = parse_scope(walker, brace_scope, token_span);
						let span = Span::new(
							if first_iter {
								if_kw_span.start
							} else {
								else_kw_span.start
							},
							if let Some(r_paren_span) = r_paren_span {
								r_paren_span.end
							} else if let Some(ref cond_expr) = cond_expr {
								cond_expr.span.end
							} else if let Some(l_paren_span) = l_paren_span {
								l_paren_span.end
							} else {
								if_kw_span.end
							},
						);
						branches.push(IfBranch {
							span: Span::new(if_kw_span.start, body.span.end),
							condition: (
								if first_iter {
									IfCondition::If(cond_expr)
								} else {
									IfCondition::ElseIf(cond_expr)
								},
								span,
							),
							body: Some(body),
						});
					} else {
						// We don't have a multi-line body, so we attempt to parse a single statement.
						let mut stmts = Vec::new();
						parse_stmt(walker, &mut stmts);

						let body = if stmts.is_empty() {
							if let Some(r_paren_span) = r_paren_span {
								walker.push_syntax_diag(Syntax::Stmt(
									StmtDiag::IfExpectedLBraceOrStmtAfterRParen(
										r_paren_span,
									),
								));
							}
							None
						} else {
							let stmt = stmts.remove(0);
							let body = Scope {
								span: stmt.span,
								contents: vec![stmt],
							};
							Some(body)
						};

						let span = Span::new(
							if first_iter {
								if_kw_span.start
							} else {
								else_kw_span.start
							},
							if let Some(r_paren_span) = r_paren_span {
								r_paren_span.end
							} else if let Some(ref cond_expr) = cond_expr {
								cond_expr.span.end
							} else if let Some(l_paren_span) = l_paren_span {
								l_paren_span.end
							} else {
								if_kw_span.end
							},
						);
						branches.push(IfBranch {
							span: Span::new(
								if_kw_span.start,
								if let Some(ref body) = body {
									body.span.end
								} else {
									span.end
								},
							),
							condition: (
								if first_iter {
									IfCondition::If(cond_expr)
								} else {
									IfCondition::ElseIf(cond_expr)
								},
								span,
							),
							body,
						});
					}
				}
				None => {
					// We have a if-header but no associated body but we've reached the EOF.
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::IfExpectedLBraceOrStmtAfterRParen(
							walker.get_last_span().next_single_width(),
						),
					));
					let span = Span::new(
						if first_iter {
							if_kw_span.start
						} else {
							else_kw_span.start
						},
						if let Some(r_paren_span) = r_paren_span {
							r_paren_span.end
						} else if let Some(ref cond_expr) = cond_expr {
							cond_expr.span.end
						} else if let Some(l_paren_span) = l_paren_span {
							l_paren_span.end
						} else {
							if_kw_span.end
						},
					);
					branches.push(IfBranch {
						span,
						condition: (
							if first_iter {
								IfCondition::If(cond_expr)
							} else {
								IfCondition::ElseIf(cond_expr)
							},
							span,
						),
						body: None,
					});
					nodes.push(Node {
						span: Span::new(
							kw_span.start,
							walker.get_last_span().end,
						),
						ty: NodeTy::If(branches),
					});
					return;
				}
			}
		} else {
			// Consume either the `{` for a multi-line if body or a statement for a single-statement if body.
			match walker.peek() {
				Some((token, token_span)) => {
					if *token == Token::LBrace {
						// We have a multi-line body.
						walker.push_colour(token_span, SyntaxType::Punctuation);
						walker.advance();
						let body = parse_scope(walker, brace_scope, token_span);
						branches.push(IfBranch {
							span: Span::new(else_kw_span.start, body.span.end),
							condition: (IfCondition::Else, else_kw_span),
							body: Some(body),
						});
					} else {
						// We don't have a multi-line body, so we attempt to parse a single statement.
					}
				}
				None => {
					// We have one else-header but no associated body.
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::IfExpectedLBraceOrStmtAfterRParen(
							walker.get_last_span().next_single_width(),
						),
					));
					branches.push(IfBranch {
						span: else_kw_span,
						condition: (IfCondition::Else, else_kw_span),
						body: None,
					});
					nodes.push(Node {
						span: Span::new(
							kw_span.start,
							walker.get_last_span().end,
						),
						ty: NodeTy::If(branches),
					});
					return;
				}
			}
		}

		first_iter = false;
	}
}

/// Parses a switch statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_switch<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the `(`.
	let l_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::SwitchExpectedLParenAfterKw(
						kw_span.next_single_width(),
					),
				));
				None
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::SwitchExpectedLParenAfterKw(
					kw_span.next_single_width(),
				),
			));
			return;
		}
	};

	// Consume the condition expression.
	let cond_expr = match expr_parser(
		walker,
		Mode::Default,
		[Token::RParen, Token::LBrace],
	) {
		(Some(e), mut syntax, mut semantic, mut colours) => {
			walker.append_colours(&mut colours);
			walker.append_syntax_diags(&mut syntax);
			walker.append_semantic_diags(&mut semantic);
			Some(e)
		}
		(None, _, _, _) => {
			if let Some(l_paren_span) = l_paren_span {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::SwitchExpectedExprAfterLParen(
						l_paren_span.next_single_width(),
					),
				));
			}
			None
		}
	};

	// Consume the `)`.
	let r_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::RParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				if let Some(ref cond_expr) = cond_expr {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SwitchExpectedRParenAfterExpr(
							cond_expr.span.next_single_width(),
						),
					));
				}
				None
			}
		}
		None => {
			if let Some(ref cond_expr) = cond_expr {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::SwitchExpectedRParenAfterExpr(
						cond_expr.span.next_single_width(),
					),
				));
			}
			return;
		}
	};

	// Consume the `{`.
	let l_brace_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LBrace {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				span
			} else {
				if let Some(r_paren_span) = r_paren_span {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::SwitchExpectedLBraceAfterCond(
							r_paren_span.next_single_width(),
						),
					));
				}
				nodes.push(Node {
					span: Span::new(
						kw_span.start,
						if let Some(r_paren_span) = r_paren_span {
							r_paren_span.end
						} else if let Some(ref cond_expr) = cond_expr {
							cond_expr.span.end
						} else if let Some(l_paren_span) = l_paren_span {
							l_paren_span.end
						} else {
							kw_span.end
						},
					),
					ty: NodeTy::Switch {
						cond: cond_expr,
						cases: vec![],
					},
				});
				return;
			}
		}
		None => {
			if let Some(r_paren_span) = r_paren_span {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::SwitchExpectedLBraceAfterCond(
						r_paren_span.next_single_width(),
					),
				));
			}
			nodes.push(Node {
				span: Span::new(kw_span.start, walker.get_last_span().end),
				ty: NodeTy::Switch {
					cond: cond_expr,
					cases: vec![],
				},
			});
			return;
		}
	};

	// Check if the body is empty.
	match walker.peek() {
		Some((token, token_span)) => {
			if *token == Token::RBrace {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::SwitchFoundEmptyBody(Span::new(
						l_brace_span.start,
						token_span.end,
					)),
				));
				nodes.push(Node {
					span: Span::new(kw_span.start, token_span.end),
					ty: NodeTy::Switch {
						cond: cond_expr,
						cases: vec![],
					},
				});
				return;
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ScopeMissingRBrace(
					l_brace_span,
					walker.get_last_span().next_single_width(),
				),
			));
			nodes.push(Node {
				span: Span::new(kw_span.start, walker.get_last_span().end),
				ty: NodeTy::Switch {
					cond: cond_expr,
					cases: vec![],
				},
			});
			return;
		}
	}

	// Consume cases until we reach the end of the body.
	let mut cases = Vec::new();
	loop {
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ScopeMissingRBrace(
						l_brace_span,
						walker.get_last_span().next_single_width(),
					),
				));
				nodes.push(Node {
					span: Span::new(kw_span.start, walker.get_last_span().end),
					ty: NodeTy::Switch {
						cond: cond_expr,
						cases,
					},
				});
				return;
			}
		};

		match token {
			Token::Case => {
				let case_kw_span = token_span;
				walker.push_colour(case_kw_span, SyntaxType::Keyword);
				walker.advance();

				// Consume the expression.
				let expr =
					match expr_parser(walker, Mode::Default, [Token::Colon]) {
						(Some(e), mut syntax, mut semantic, mut colours) => {
							walker.append_colours(&mut colours);
							walker.append_syntax_diags(&mut syntax);
							walker.append_semantic_diags(&mut semantic);
							Some(e)
						}
						(None, _, _, _) => {
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::SwitchExpectedExprAfterCaseKw(
									case_kw_span.next_single_width(),
								),
							));
							None
						}
					};

				// Consume the `:`.
				let colon_span = match walker.peek() {
					Some((token, token_span)) => {
						if *token == Token::Colon {
							walker.push_colour(
								token_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							Some(token_span)
						} else {
							if let Some(ref expr) = expr {
								walker.push_syntax_diag(Syntax::Stmt(
									StmtDiag::SwitchExpectedColonAfterCaseExpr(
										expr.span.next_single_width(),
									),
								));
							}
							None
						}
					}
					None => {
						// We don't have a complete case but we've reached the EOF.
						if let Some(ref expr) = expr {
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::SwitchExpectedColonAfterCaseExpr(
									expr.span.next_single_width(),
								),
							));
						}
						cases.push(SwitchCase {
							span: Span::new(
								case_kw_span.start,
								walker.get_last_span().end,
							),
							expr: Either::Left(expr),
							body: None,
						});
						nodes.push(Node {
							span: Span::new(
								kw_span.start,
								walker.get_last_span().end,
							),
							ty: NodeTy::Switch {
								cond: cond_expr,
								cases,
							},
						});
						return;
					}
				};

				// Consume the body of the case.
				let body = parse_scope(
					walker,
					switch_case_scope,
					colon_span.unwrap_or(if let Some(ref expr) = expr {
						expr.span
					} else {
						case_kw_span
					}),
				);
				cases.push(SwitchCase {
					span: Span::new(case_kw_span.start, body.span.end),
					expr: Either::Left(expr),
					body: Some(body),
				});
			}
			Token::Default => {
				let default_kw_span = token_span;
				walker.push_colour(default_kw_span, SyntaxType::Keyword);
				walker.advance();

				// Consume the `:`.
				let colon_span = match walker.peek() {
					Some((token, token_span)) => {
						if *token == Token::Colon {
							walker.push_colour(
								token_span,
								SyntaxType::Punctuation,
							);
							walker.advance();
							Some(token_span)
						} else {
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::SwitchExpectedColonAfterDefaultKw(
									default_kw_span.next_single_width(),
								),
							));
							None
						}
					}
					None => {
						// We don't have a complete case but we've reached the EOF.
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::SwitchExpectedColonAfterDefaultKw(
								default_kw_span.next_single_width(),
							),
						));
						cases.push(SwitchCase {
							span: default_kw_span,
							expr: Either::Right(()),
							body: None,
						});
						nodes.push(Node {
							span: Span::new(
								kw_span.start,
								walker.get_last_span().end,
							),
							ty: NodeTy::Switch {
								cond: cond_expr,
								cases,
							},
						});
						return;
					}
				};

				// Consume the body of the case.
				let body = parse_scope(
					walker,
					switch_case_scope,
					colon_span.unwrap_or(default_kw_span.end_zero_width()),
				);
				cases.push(SwitchCase {
					span: Span::new(default_kw_span.start, body.span.end),
					expr: Either::Right(()),
					body: Some(body),
				});
			}
			Token::RBrace => {
				// If this branch is triggered, this `}` is closing the entire body of the switch statement. In the
				// following example:
				//
				// switch (true) {
				//     default: {
				//         /*...*/
				//     }
				// }
				//
				// the first `}` will be consumed by the `parse_scope()` function of the default case body, whilst
				// the second will be consumed by this branch. In the following example:
				//
				// switch (true) {
				//     default:
				//         /*...*/
				// }
				//
				// The `}` will close the body of the default case but it won't be consumed, and hence it will be
				// consumed by this branch.
				walker.push_colour(token_span, SyntaxType::Punctuation);
				walker.advance();
				nodes.push(Node {
					span: Span::new(kw_span.start, token_span.end),
					ty: NodeTy::Switch {
						cond: cond_expr,
						cases,
					},
				});
				return;
			}
			_ => {
				// We have a token which cannot begin a case, nor can finish the switch body. We consume tokens
				// until we hit something recognizable.
				let invalid_span_start = token_span.start;
				let mut invalid_span_end = token_span.end;
				loop {
					match walker.peek() {
						Some((token, token_span)) => {
							if *token == Token::Case
								|| *token == Token::Default || *token
								== Token::RBrace
							{
								// We don't consume the token because the next iteration of the main loop will deal
								// with it appropriately.
								walker.push_syntax_diag(Syntax::Stmt(StmtDiag::SwitchExpectedCaseOrDefaultKwOrEnd(
									Span::new(invalid_span_start, invalid_span_end)
								)));
								break;
							} else {
								invalid_span_end = token_span.end;
								walker.push_colour(
									token_span,
									token.non_semantic_colour(),
								);
								walker.advance();
							}
						}
						None => {
							// We haven't yet hit anything recognizable but we've reached the EOF.
							walker.push_syntax_diag(Syntax::Stmt(
								StmtDiag::SwitchExpectedCaseOrDefaultKwOrEnd(
									Span::new(
										invalid_span_start,
										walker.get_last_span().end,
									),
								),
							));
							nodes.push(Node {
								span: Span::new(
									kw_span.start,
									walker.get_last_span().end,
								),
								ty: NodeTy::Switch {
									cond: cond_expr,
									cases,
								},
							});
							return;
						}
					}
				}
			}
		}
	}
}

/// Parses a for loop statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_for_loop<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the `(`.
	let l_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ForExpectedLParenAfterKw(
						kw_span.next_single_width(),
					),
				));
				None
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ForExpectedLParenAfterKw(kw_span.next_single_width()),
			));
			return;
		}
	};

	// Consume the "expressions" (actually expression/declaration statements).
	let mut init: Option<Node> = None;
	let mut cond: Option<Node> = None;
	let mut inc: Option<Node> = None;
	let mut counter = 0;
	let r_paren_span = 'outer: loop {
		let (token, token_span) = match walker.peek() {
			Some(t) => t,
			None => {
				// We have not encountered a `)` yet.
				let span = Span::new(
					kw_span.start,
					if let Some(ref inc) = inc {
						inc.span.end
					} else if let Some(ref cond) = cond {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::ForExpectedIncStmt(
								cond.span.next_single_width(),
							),
						));
						cond.span.end
					} else if let Some(ref init) = init {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::ForExpectedCondStmt(
								init.span.next_single_width(),
							),
						));
						init.span.end
					} else if let Some(l_paren_span) = l_paren_span {
						walker.push_syntax_diag(Syntax::Stmt(
							StmtDiag::ForExpectedInitStmt(
								l_paren_span.next_single_width(),
							),
						));
						l_paren_span.end
					} else {
						kw_span.end
					},
				);
				nodes.push(Node {
					span,
					ty: NodeTy::For {
						init: init.map(|n| Box::from(n)),
						cond: cond.map(|n| Box::from(n)),
						inc: inc.map(|n| Box::from(n)),
						body: None,
					},
				});
				return;
			}
		};

		match token {
			Token::RParen => {
				if counter < 3 {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ForExpected3Stmts(
							token_span.previous_single_width(),
						),
					));
				}
				walker.push_colour(token_span, SyntaxType::Punctuation);
				walker.advance();
				break token_span;
			}
			_ => {
				if counter == 3 {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::ForExpectedRParenAfterStmts(
							inc.as_ref().unwrap().span.next_single_width(),
						),
					));

					walker.push_colour(token_span, SyntaxType::Invalid);
					walker.advance();

					loop {
						match walker.peek() {
							Some((token, span)) => {
								if *token == Token::RParen {
									walker.push_colour(
										span,
										SyntaxType::Punctuation,
									);
									walker.advance();
									break 'outer span;
								} else {
									walker
										.push_colour(span, SyntaxType::Invalid);
									walker.advance();
								}
							}
							None => break,
						}
					}

					nodes.push(Node {
						span: Span::new(
							kw_span.start,
							inc.as_ref().unwrap().span.end,
						),
						ty: NodeTy::For {
							init: init.map(|n| Box::from(n)),
							cond: cond.map(|n| Box::from(n)),
							inc: inc.map(|n| Box::from(n)),
							body: None,
						},
					});
					return;
				}
			}
		}

		let qualifiers = try_parse_qualifiers(walker);
		let mut stmt = Vec::new();
		try_parse_definition_declaration_expr(
			walker,
			&mut stmt,
			qualifiers,
			counter == 2,
		);

		if !stmt.is_empty() {
			if counter == 0 {
				init = Some(stmt.remove(0));
			} else if counter == 1 {
				cond = Some(stmt.remove(0));
			} else if counter == 2 {
				inc = Some(stmt.remove(0));
			}
			counter += 1;
		}
	};

	// Consume the `{`.
	let l_brace_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LBrace {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				span
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::ForExpectedLBraceAfterHeader(
						r_paren_span.next_single_width(),
					),
				));
				nodes.push(Node {
					span: Span::new(kw_span.start, r_paren_span.end),
					ty: NodeTy::For {
						init: init.map(|n| Box::from(n)),
						cond: cond.map(|n| Box::from(n)),
						inc: inc.map(|n| Box::from(n)),
						body: None,
					},
				});
				return;
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ForExpectedLBraceAfterHeader(
					r_paren_span.next_single_width(),
				),
			));
			nodes.push(Node {
				span: Span::new(kw_span.start, r_paren_span.end),
				ty: NodeTy::For {
					init: init.map(|n| Box::from(n)),
					cond: cond.map(|n| Box::from(n)),
					inc: inc.map(|n| Box::from(n)),
					body: None,
				},
			});
			return;
		}
	};

	// Consume the body.
	let body = parse_scope(walker, brace_scope, l_brace_span);
	nodes.push(Node {
		span: Span::new(kw_span.start, body.span.end),
		ty: NodeTy::For {
			init: init.map(|n| Box::from(n)),
			cond: cond.map(|n| Box::from(n)),
			inc: inc.map(|n| Box::from(n)),
			body: Some(body),
		},
	});
}

/// Parses a while loop statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_while_loop<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the `(`.
	let l_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedLParenAfterKw(
						kw_span.next_single_width(),
					),
				));
				None
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::WhileExpectedLParenAfterKw(
					kw_span.next_single_width(),
				),
			));
			return;
		}
	};

	// Consume the condition expression.
	let cond_expr = match expr_parser(
		walker,
		Mode::Default,
		[Token::RParen, Token::Semi],
	) {
		(Some(e), mut syntax, mut semantic, mut colours) => {
			walker.append_colours(&mut colours);
			walker.append_syntax_diags(&mut syntax);
			walker.append_semantic_diags(&mut semantic);
			Some(e)
		}
		(None, _, _, _) => {
			if let Some(l_paren_span) = l_paren_span {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedExprAfterLParen(
						l_paren_span.next_single_width(),
					),
				));
			}
			None
		}
	};

	// Consume the `)`.
	let r_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::RParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				if let Some(ref cond_expr) = cond_expr {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::WhileExpectedRParenAfterExpr(
							cond_expr.span.next_single_width(),
						),
					));
				}
				None
			}
		}
		None => {
			if let Some(ref cond_expr) = cond_expr {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedRParenAfterExpr(
						cond_expr.span.next_single_width(),
					),
				));
			}
			return;
		}
	};

	// Consume the `{`.
	let l_brace_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LBrace {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				span
			} else {
				if let Some(r_paren_span) = r_paren_span {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::WhileExpectedLBraceAfterCond(
							r_paren_span.next_single_width(),
						),
					));
				}
				return;
			}
		}
		None => {
			if let Some(r_paren_span) = r_paren_span {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedLBraceAfterCond(
						r_paren_span.next_single_width(),
					),
				));
			}
			return;
		}
	};

	// Parse the body.
	let body = parse_scope(walker, brace_scope, l_brace_span);
	nodes.push(Node {
		span: Span::new(kw_span.start, body.span.end),
		ty: NodeTy::While {
			cond: cond_expr,
			body,
		},
	});
}

/// Parses a do-while loop statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_do_while_loop<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the `{`.
	let l_brace_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LBrace {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				span
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::DoWhileExpectedLBraceAfterKw(
						kw_span.next_single_width(),
					),
				));
				return;
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::DoWhileExpectedLBraceAfterKw(
					kw_span.next_single_width(),
				),
			));
			return;
		}
	};

	// Parse the body.
	let body = parse_scope(walker, brace_scope, l_brace_span);

	// Consume the `while` keyword.
	let while_kw_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::While {
				walker.push_colour(span, SyntaxType::Keyword);
				walker.advance();
				span
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::DoWhileExpectedWhileAfterBody(
						body.span.next_single_width(),
					),
				));
				nodes.push(Node {
					span: Span::new(kw_span.start, body.span.end),
					ty: NodeTy::DoWhile { body, cond: None },
				});
				return;
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::DoWhileExpectedWhileAfterBody(
					body.span.next_single_width(),
				),
			));
			nodes.push(Node {
				span: Span::new(kw_span.start, body.span.end),
				ty: NodeTy::DoWhile { body, cond: None },
			});
			return;
		}
	};

	// Consume the `(`.
	let l_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::LParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedLParenAfterKw(
						while_kw_span.next_single_width(),
					),
				));
				None
			}
		}
		None => {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::WhileExpectedLParenAfterKw(
					while_kw_span.next_single_width(),
				),
			));
			nodes.push(Node {
				span: Span::new(kw_span.start, while_kw_span.end),
				ty: NodeTy::DoWhile { body, cond: None },
			});
			return;
		}
	};

	// Consume the condition expression.
	let cond_expr = match expr_parser(
		walker,
		Mode::Default,
		[Token::RParen, Token::Semi],
	) {
		(Some(e), mut syntax, mut semantic, mut colours) => {
			walker.append_colours(&mut colours);
			walker.append_syntax_diags(&mut syntax);
			walker.append_semantic_diags(&mut semantic);
			Some(e)
		}
		(None, _, _, _) => {
			if let Some(l_paren_span) = l_paren_span {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedExprAfterLParen(
						l_paren_span.next_single_width(),
					),
				));
			}
			None
		}
	};

	// Consume the `)`.
	let r_paren_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::RParen {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				if let Some(ref cond_expr) = cond_expr {
					walker.push_syntax_diag(Syntax::Stmt(
						StmtDiag::WhileExpectedRParenAfterExpr(
							cond_expr.span.next_single_width(),
						),
					));
				}
				None
			}
		}
		None => {
			if let Some(ref cond_expr) = cond_expr {
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::WhileExpectedRParenAfterExpr(
						cond_expr.span.next_single_width(),
					),
				));
			}
			nodes.push(Node {
				span: Span::new(kw_span.start, while_kw_span.end),
				ty: NodeTy::DoWhile {
					body,
					cond: cond_expr,
				},
			});
			return;
		}
	};

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				span
			} else {
				let span = if let Some(r_paren_span) = r_paren_span {
					r_paren_span
				} else if let Some(ref expr) = cond_expr {
					expr.span
				} else if let Some(l_paren_span) = l_paren_span {
					l_paren_span
				} else {
					while_kw_span
				};
				walker.push_syntax_diag(Syntax::Stmt(
					StmtDiag::DoWhileExpectedSemiAfterRParen(
						span.next_single_width(),
					),
				));
				nodes.push(Node {
					span,
					ty: NodeTy::DoWhile {
						body,
						cond: cond_expr,
					},
				});
				return;
			}
		}
		None => {
			let span = if let Some(r_paren_span) = r_paren_span {
				r_paren_span
			} else if let Some(ref expr) = cond_expr {
				expr.span
			} else if let Some(l_paren_span) = l_paren_span {
				l_paren_span
			} else {
				while_kw_span
			};
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::DoWhileExpectedSemiAfterRParen(
					span.next_single_width(),
				),
			));
			nodes.push(Node {
				span,
				ty: NodeTy::DoWhile {
					body,
					cond: cond_expr,
				},
			});
			return;
		}
	};

	nodes.push(Node {
		span: Span::new(kw_span.start, semi_span.end),
		ty: NodeTy::DoWhile {
			cond: cond_expr,
			body,
		},
	});
}

/// Parses a break/continue/discard statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_break_continue_discard<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
	ty: impl FnOnce() -> NodeTy,
	error: impl FnOnce(Span) -> Syntax,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => None,
	};
	if semi_span.is_none() {
		walker.push_syntax_diag(error(kw_span.next_single_width()));
	}

	nodes.push(Node {
		span: Span::new(
			kw_span.start,
			if let Some(s) = semi_span {
				s.end
			} else {
				kw_span.end
			},
		),
		ty: ty(),
	});
}

/// Parses a return statement.
///
/// This function assumes that the keyword is not yet consumed.
fn parse_return<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	kw_span: Span,
) {
	walker.push_colour(kw_span, SyntaxType::Keyword);
	walker.advance();

	// Look for the optional return value expression.
	let return_expr = match expr_parser(walker, Mode::Default, [Token::Semi]) {
		(Some(expr), mut syntax, mut semantic, mut colours) => {
			walker.append_colours(&mut colours);
			walker.append_syntax_diags(&mut syntax);
			walker.append_semantic_diags(&mut semantic);
			Omittable::Some(expr)
		}
		(None, _, _, _) => Omittable::None,
	};

	// Consume the `;` to end the statement.
	let semi_span = match walker.peek() {
		Some((token, span)) => {
			if *token == Token::Semi {
				walker.push_colour(span, SyntaxType::Punctuation);
				walker.advance();
				Some(span)
			} else {
				None
			}
		}
		None => None,
	};
	if semi_span.is_none() {
		if let Omittable::Some(ref return_expr) = return_expr {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ReturnExpectedSemiAfterExpr(
					return_expr.span.next_single_width(),
				),
			));
		} else {
			walker.push_syntax_diag(Syntax::Stmt(
				StmtDiag::ReturnExpectedSemiOrExprAfterKw(
					kw_span.next_single_width(),
				),
			));
		}
	}

	nodes.push(Node {
		span: Span::new(
			kw_span.start,
			if let Some(s) = semi_span {
				s.end
			} else {
				kw_span.end
			},
		),
		ty: NodeTy::Return { value: return_expr },
	});
}

/// Parses a preprocessor directive.
///
/// This function assumes that the directive has not yet been consumed.
fn parse_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	stream: PreprocStream,
	dir_span: Span,
) {
	use crate::lexer::preprocessor::{self, DefineToken, UndefToken};

	match stream {
		PreprocStream::Empty => {
			walker.push_colour(dir_span, SyntaxType::DirectiveHash);
			walker.push_semantic_diag(Semantic::EmptyDirective(dir_span));
			nodes.push(Node {
				span: dir_span,
				ty: NodeTy::EmptyDirective,
			});
		}
		PreprocStream::Custom { kw, content } => {
			walker
				.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
			walker.push_colour(kw.1, SyntaxType::DirectiveName);
			if let Some(content) = content {
				walker.push_colour(content.1, SyntaxType::Directive);
			}
			walker.push_syntax_diag(Syntax::FoundIllegalPreproc(
				dir_span,
				Some(kw),
			));
		}
		PreprocStream::Invalid { content } => {
			walker
				.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
			walker.push_colour(content.1, SyntaxType::Directive);
			walker
				.push_syntax_diag(Syntax::FoundIllegalPreproc(dir_span, None));
		}
		PreprocStream::Version { kw, tokens } => {
			parse_version_directive(walker, nodes, dir_span, kw, tokens)
		}
		PreprocStream::Extension { kw, tokens } => {
			parse_extension_directive(walker, nodes, dir_span, kw, tokens)
		}
		PreprocStream::Line { kw, tokens } => {
			parse_line_directive(walker, nodes, dir_span, kw, tokens)
		}
		PreprocStream::Define {
			kw: kw_span,
			mut ident_tokens,
			body_tokens,
		} => {
			walker
				.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
			walker.push_colour(kw_span, SyntaxType::DirectiveName);

			if ident_tokens.is_empty() {
				// We have a macro that's missing a name.

				walker.push_syntax_diag(Syntax::PreprocDefine(
					PreprocDefineDiag::DefineExpectedMacroName(
						kw_span.next_single_width(),
					),
				));
				body_tokens.iter().for_each(|(t, s)| {
					walker.push_colour_with_modifiers(
						*s,
						t.non_semantic_colour(),
						SyntaxModifiers::MACRO_BODY,
					)
				});
			} else if ident_tokens.len() == 1 {
				// We have an object-like macro.

				let ident = match ident_tokens.remove(0) {
					(DefineToken::Ident(s), span) => {
						walker.push_colour_with_modifiers(
							span,
							SyntaxType::ObjectMacro,
							SyntaxModifiers::MACRO_SIGNATURE,
						);
						(s, span)
					}
					_ => unreachable!(),
				};

				// Since object-like macros don't have parameters, we can perform the concatenation right here
				// since we know the contents of the macro body will never change.
				let (body_tokens, mut syntax, mut semantic) =
					preprocessor::concat_macro_body(
						body_tokens,
						walker.span_encoding,
					);
				walker.append_syntax_diags(&mut syntax);
				walker.append_semantic_diags(&mut semantic);
				body_tokens.iter().for_each(|(t, s)| {
					walker.push_colour_with_modifiers(
						*s,
						t.non_semantic_colour(),
						SyntaxModifiers::MACRO_BODY,
					)
				});

				walker.register_macro(
					ident.0.clone(),
					ident.1,
					Macro::Object(body_tokens.clone()),
				);
				nodes.push(Node {
					span: dir_span,
					ty: NodeTy::DefineDirective {
						macro_: ast::Macro::Object {
							ident: Ident {
								span: ident.1,
								name: ident.0,
							},
						},
						replacement_tokens: body_tokens,
					},
				});
			} else {
				// We have a function-like macro.

				let ident = match ident_tokens.remove(0) {
					(DefineToken::Ident(s), span) => {
						walker.push_colour_with_modifiers(
							span,
							SyntaxType::FunctionMacro,
							SyntaxModifiers::MACRO_SIGNATURE,
						);
						(s, span)
					}
					_ => unreachable!(),
				};

				// Consume the `(`.
				let l_paren_span = match ident_tokens.remove(0) {
					(DefineToken::LParen, span) => {
						walker.push_colour_with_modifiers(
							span,
							SyntaxType::Punctuation,
							SyntaxModifiers::MACRO_SIGNATURE,
						);
						span
					}
					_ => unreachable!(),
				};

				// Look for any parameters until we hit a closing `)` parenthesis.
				#[derive(PartialEq)]
				enum Prev {
					None,
					Param,
					Comma,
					Invalid,
				}
				let mut prev = Prev::None;
				let mut prev_span = l_paren_span;
				let mut params = Vec::new();
				let r_paren_span = loop {
					let (token, token_span) = if !ident_tokens.is_empty() {
						ident_tokens.remove(0)
					} else {
						walker.push_syntax_diag(Syntax::PreprocDefine(
							PreprocDefineDiag::ParamsExpectedRParen(
								prev_span.next_single_width(),
							),
						));
						nodes.push(Node {
							span: dir_span,
							ty: NodeTy::DefineDirective {
								macro_: ast::Macro::Function {
									ident: Ident {
										span: ident.1,
										name: ident.0,
									},
									params,
								},
								replacement_tokens: body_tokens,
							},
						});
						return;
					};

					match token {
						DefineToken::Comma => {
							walker.push_colour_with_modifiers(
								token_span,
								SyntaxType::Punctuation,
								SyntaxModifiers::MACRO_SIGNATURE,
							);
							if prev == Prev::Comma {
								walker.push_syntax_diag(Syntax::PreprocDefine(
									PreprocDefineDiag::ParamsExpectedParamAfterComma(Span::new_between(
										prev_span, token_span
									))
								));
							} else if prev == Prev::None {
								walker.push_syntax_diag(Syntax::PreprocDefine(
									PreprocDefineDiag::ParamsExpectedParamBetweenParenComma(Span::new_between(
										l_paren_span, token_span
									))
								));
							}
							prev = Prev::Comma;
							prev_span = token_span;
						}
						DefineToken::Ident(str) => {
							walker.push_colour_with_modifiers(
								token_span,
								SyntaxType::Parameter,
								SyntaxModifiers::MACRO_SIGNATURE,
							);
							params.push(Ident {
								name: str,
								span: token_span,
							});
							if prev == Prev::Param {
								walker.push_syntax_diag(Syntax::PreprocDefine(
									PreprocDefineDiag::ParamsExpectedCommaAfterParam(prev_span.next_single_width())
								));
							}
							prev = Prev::Param;
							prev_span = token_span;
						}
						DefineToken::RParen => {
							walker.push_colour_with_modifiers(
								token_span,
								SyntaxType::Punctuation,
								SyntaxModifiers::MACRO_SIGNATURE,
							);
							if prev == Prev::Comma {
								walker.push_syntax_diag(Syntax::PreprocDefine(
									PreprocDefineDiag::ParamsExpectedParamAfterComma(Span::new_between(
										prev_span, token_span
									))
								));
							}
							break token_span;
						}
						DefineToken::Invalid(_) | _ => {
							walker.push_colour_with_modifiers(
								token_span,
								SyntaxType::Invalid,
								SyntaxModifiers::MACRO_SIGNATURE,
							);
							walker.push_syntax_diag(Syntax::PreprocDefine(
								PreprocDefineDiag::ParamsExpectedParam(
									token_span,
								),
							));
							prev = Prev::Invalid;
							prev_span = token_span;
						}
					}
				};

				// We can't perform the token concatenation right here since the contents of the macro body will
				// change depending on the parameters, but we can still concatenate in order to find any
				// syntax/semantic diagnostics.
				let (_, mut syntax, mut semantic) =
					preprocessor::concat_macro_body(
						body_tokens.clone(),
						walker.span_encoding,
					);
				walker.append_syntax_diags(&mut syntax);
				walker.append_semantic_diags(&mut semantic);

				// Syntax highlight the body. If any identifier matches a parameter, we correctly highlight that.
				body_tokens.iter().for_each(|(t, s)| match t {
					Token::Ident(str) => {
						if let Some(_) =
							params.iter().find(|ident| &ident.name == str)
						{
							walker.push_colour_with_modifiers(
								*s,
								SyntaxType::Parameter,
								SyntaxModifiers::MACRO_BODY,
							)
						} else {
							walker.push_colour_with_modifiers(
								*s,
								t.non_semantic_colour(),
								SyntaxModifiers::MACRO_BODY,
							)
						}
					}
					_ => walker.push_colour_with_modifiers(
						*s,
						t.non_semantic_colour(),
						SyntaxModifiers::MACRO_BODY,
					),
				});

				walker.register_macro(
					ident.0.clone(),
					Span::new(ident.1.start, r_paren_span.end),
					Macro::Function {
						params: params.clone(),
						body: body_tokens.clone(),
					},
				);
				nodes.push(Node {
					span: dir_span,
					ty: NodeTy::DefineDirective {
						macro_: ast::Macro::Function {
							ident: Ident {
								span: ident.1,
								name: ident.0,
							},
							params,
						},
						replacement_tokens: body_tokens,
					},
				});
			}
		}
		PreprocStream::Undef {
			kw: kw_span,
			mut tokens,
		} => {
			walker
				.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
			walker.push_colour(kw_span, SyntaxType::DirectiveName);

			let ident = if tokens.is_empty() {
				walker.push_syntax_diag(Syntax::PreprocDefine(
					PreprocDefineDiag::UndefExpectedMacroName(
						kw_span.next_single_width(),
					),
				));
				Omittable::None
			} else {
				let (token, token_span) = tokens.remove(0);
				let ident = match token {
					UndefToken::Ident(s) => {
						walker.unregister_macro(&s, token_span);
						Omittable::Some(Ident {
							name: s,
							span: token_span,
						})
					}
					UndefToken::Invalid(_) => {
						walker.push_syntax_diag(Syntax::PreprocDefine(
							PreprocDefineDiag::UndefExpectedMacroName(
								token_span,
							),
						));
						Omittable::None
					}
				};

				if !tokens.is_empty() {
					let (_, first) = tokens.first().unwrap();
					let (_, last) = tokens.last().unwrap();
					walker.push_colour_with_modifiers(
						Span::new(first.start, last.end),
						SyntaxType::Invalid,
						SyntaxModifiers::UNDEFINE,
					);
					walker.push_syntax_diag(Syntax::PreprocTrailingTokens(
						Span::new(first.start, last.end),
					));
				}

				ident
			};

			nodes.push(Node {
				span: Span::new(
					dir_span.start,
					if let Omittable::Some(ref ident) = ident {
						ident.span.end
					} else {
						kw_span.end
					},
				),
				ty: NodeTy::UndefDirective { name: ident },
			});
		}
		PreprocStream::Error { kw, message } => {
			parse_error_directive(walker, nodes, dir_span, kw, message)
		}
		PreprocStream::Pragma { kw, options } => {
			parse_pragma_directive(walker, nodes, dir_span, kw, options)
		}
		_ => {}
	}
}

/// Parses a `#version` directive.
fn parse_version_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	dir_span: Span,
	kw_span: Span,
	tokens: Vec<(VersionToken, Span)>,
) {
	walker.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
	walker.push_colour(kw_span, SyntaxType::DirectiveName);

	if tokens.is_empty() {
		walker.push_syntax_diag(Syntax::PreprocVersion(
			PreprocVersionDiag::ExpectedNumber(kw_span.next_single_width()),
		));
		return;
	}
	let mut tokens = tokens.into_iter();

	/// Consumes the rest of the tokens.
	fn seek_end<'a, P: TokenStreamProvider<'a>>(
		walker: &mut Walker<'a, P>,
		mut tokens: impl Iterator<Item = (VersionToken, Span)>,
		emit_diagnostic: bool,
	) {
		let span_start = match tokens.next() {
			Some((_, span)) => span.start,
			None => return,
		};
		let mut span_end = span_start;
		for (token, token_span) in tokens {
			walker.push_colour(
				token_span,
				match token {
					VersionToken::Invalid(_) => SyntaxType::Invalid,
					_ => SyntaxType::Directive,
				},
			);
			span_end = token_span.end;
		}
		if emit_diagnostic {
			walker.push_syntax_diag(Syntax::PreprocTrailingTokens(Span::new(
				span_start, span_end,
			)));
		}
	}

	/// Parses the version number.
	fn parse_version<'a, P: TokenStreamProvider<'a>>(
		walker: &mut Walker<'a, P>,
		number: usize,
		span: Span,
	) -> Option<usize> {
		match number {
			450 => Some(number),
			100 | 110 | 120 | 130 | 140 | 150 | 300 | 310 | 320 | 330 | 400
			| 410 | 420 | 430 | 460 => {
				walker.push_syntax_diag(Syntax::PreprocVersion(
					PreprocVersionDiag::UnsupportedVersion(span, number),
				));
				Some(number)
			}
			_ => {
				walker.push_syntax_diag(Syntax::PreprocVersion(
					PreprocVersionDiag::InvalidVersion(span, number),
				));
				None
			}
		}
	}

	/// Parses the profile.
	fn parse_profile<'a, P: TokenStreamProvider<'a>>(
		walker: &mut Walker<'a, P>,
		str: &str,
		span: Span,
	) -> Option<ProfileTy> {
		match str {
			"core" => {
				walker.push_colour(span, SyntaxType::DirectiveProfile);
				Some(ProfileTy::Core)
			}
			"compatability" => {
				walker.push_colour(span, SyntaxType::DirectiveProfile);
				Some(ProfileTy::Compatability)
			}
			"es" => {
				walker.push_colour(span, SyntaxType::DirectiveProfile);
				Some(ProfileTy::Es)
			}
			_ => {
				let str = str.to_lowercase();
				match str.as_ref() {
					"core" => {
						walker.push_colour(span, SyntaxType::DirectiveProfile);
						walker.push_syntax_diag(Syntax::PreprocVersion(
							PreprocVersionDiag::InvalidProfileCasing(
								span, "core",
							),
						));
						Some(ProfileTy::Core)
					}
					"compatability" => {
						walker.push_colour(span, SyntaxType::DirectiveProfile);
						walker.push_syntax_diag(Syntax::PreprocVersion(
							PreprocVersionDiag::InvalidProfileCasing(
								span,
								"compatability",
							),
						));
						Some(ProfileTy::Compatability)
					}
					"es" => {
						walker.push_colour(span, SyntaxType::DirectiveProfile);
						walker.push_syntax_diag(Syntax::PreprocVersion(
							PreprocVersionDiag::InvalidProfileCasing(
								span, "es",
							),
						));
						Some(ProfileTy::Es)
					}
					_ => None,
				}
			}
		}
	}

	// Consume the version number.
	let version = {
		let (token, token_span) = tokens.next().unwrap();
		match token {
			VersionToken::Num(n) => {
				match parse_version(walker, n, token_span) {
					Some(n) => {
						walker.push_colour(
							token_span,
							SyntaxType::DirectiveVersion,
						);
						(n, token_span)
					}
					None => {
						walker.push_colour(token_span, SyntaxType::Directive);
						seek_end(walker, tokens, false);
						return;
					}
				}
			}
			VersionToken::InvalidNum(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocVersion(
					PreprocVersionDiag::InvalidNumber(token_span),
				));
				seek_end(walker, tokens, false);
				return;
			}
			VersionToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocVersion(
					PreprocVersionDiag::ExpectedNumber(token_span),
				));
				seek_end(walker, tokens, false);
				return;
			}
			VersionToken::Word(str) => {
				match parse_profile(walker, &str, token_span) {
					Some(profile) => {
						// We have a profile immediately after the `version` keyword.
						walker.push_syntax_diag(Syntax::PreprocVersion(PreprocVersionDiag::MissingNumberBetweenKwAndProfile(
								Span::new_between(kw_span, token_span)
							)));
						seek_end(walker, tokens, true);
						nodes.push(Node {
							span: Span::new(dir_span.start, token_span.end),
							ty: NodeTy::VersionDirective {
								version: None,
								profile: Omittable::Some((profile, token_span)),
							},
						});
						return;
					}
					None => {
						walker.push_colour(token_span, SyntaxType::Directive);
						walker.push_syntax_diag(Syntax::PreprocVersion(
							PreprocVersionDiag::ExpectedNumber(token_span),
						));
						seek_end(walker, tokens, false);
						return;
					}
				}
			}
		}
	};

	// Look for an optional profile.
	let profile = match tokens.next() {
		Some((token, token_span)) => match token {
			VersionToken::Word(str) => {
				match parse_profile(walker, &str, token_span) {
					Some(p) => Omittable::Some((p, token_span)),
					None => {
						walker.push_syntax_diag(Syntax::PreprocVersion(
							PreprocVersionDiag::InvalidProfile(token_span),
						));
						seek_end(walker, tokens, false);
						nodes.push(Node {
							span: Span::new(dir_span.start, version.1.end),
							ty: NodeTy::VersionDirective {
								version: Some(version),
								profile: Omittable::None,
							},
						});
						return;
					}
				}
			}
			_ => {
				walker.push_syntax_diag(Syntax::PreprocVersion(
					PreprocVersionDiag::ExpectedProfile(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, version.1.end),
					ty: NodeTy::VersionDirective {
						version: Some(version),
						profile: Omittable::None,
					},
				});
				return;
			}
		},
		None => Omittable::None,
	};

	seek_end(walker, tokens, true);
	nodes.push(Node {
		span: Span::new(
			dir_span.start,
			if let Omittable::Some(ref profile) = profile {
				profile.1.end
			} else {
				version.1.end
			},
		),
		ty: NodeTy::VersionDirective {
			version: Some(version),
			profile,
		},
	});
}

/// Parses an `#extension` directive.
fn parse_extension_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	dir_span: Span,
	kw_span: Span,
	tokens: Vec<(ExtensionToken, Span)>,
) {
	walker.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
	walker.push_colour(kw_span, SyntaxType::DirectiveName);

	if tokens.is_empty() {
		walker.push_syntax_diag(Syntax::PreprocExt(
			PreprocExtDiag::ExpectedName(kw_span.next_single_width()),
		));
		return;
	}
	let mut tokens = tokens.into_iter();

	/// Consumes the rest of the tokens.
	fn seek_end<'a, P: TokenStreamProvider<'a>>(
		walker: &mut Walker<'a, P>,
		mut tokens: impl Iterator<Item = (ExtensionToken, Span)>,
		emit_diagnostic: bool,
	) {
		let span_start = match tokens.next() {
			Some((_, span)) => span.start,
			None => return,
		};
		let mut span_end = span_start;
		for (token, token_span) in tokens {
			walker.push_colour(
				token_span,
				match token {
					ExtensionToken::Invalid(_) => SyntaxType::Invalid,
					_ => SyntaxType::Directive,
				},
			);
			span_end = token_span.end;
		}
		if emit_diagnostic {
			walker.push_syntax_diag(Syntax::PreprocTrailingTokens(Span::new(
				span_start, span_end,
			)));
		}
	}

	/// Parses the behaviour.
	fn parse_behaviour(
		str: &str,
		span: Span,
	) -> Option<(BehaviourTy, Option<Syntax>)> {
		match str {
			"require" => Some((BehaviourTy::Require, None)),
			"enable" => Some((BehaviourTy::Enable, None)),
			"warn" => Some((BehaviourTy::Warn, None)),
			"disable" => Some((BehaviourTy::Disable, None)),
			_ => {
				let str = str.to_lowercase();
				match str.as_ref() {
					"require" => Some((
						BehaviourTy::Require,
						Some(Syntax::PreprocExt(
							PreprocExtDiag::InvalidBehaviourCasing(
								span, "require",
							),
						)),
					)),
					"enable" => Some((
						BehaviourTy::Enable,
						Some(Syntax::PreprocExt(
							PreprocExtDiag::InvalidBehaviourCasing(
								span, "enable",
							),
						)),
					)),
					"warn" => Some((
						BehaviourTy::Warn,
						Some(Syntax::PreprocExt(
							PreprocExtDiag::InvalidBehaviourCasing(
								span, "warn",
							),
						)),
					)),
					"disable" => Some((
						BehaviourTy::Disable,
						Some(Syntax::PreprocExt(
							PreprocExtDiag::InvalidBehaviourCasing(
								span, "disable",
							),
						)),
					)),
					_ => None,
				}
			}
		}
	}

	// Consume the extension name.
	let name = {
		let (token, token_span) = tokens.next().unwrap();
		match token {
			ExtensionToken::Word(str) => {
				match parse_behaviour(&str, token_span) {
					Some((behaviour, _)) => {
						walker.push_colour(
							token_span,
							SyntaxType::DirectiveExtBehaviour,
						);
						walker.push_syntax_diag(Syntax::PreprocExt(
							PreprocExtDiag::MissingNameBetweenKwAndBehaviour(
								Span::new_between(kw_span, token_span),
							),
						));
						seek_end(walker, tokens, false);
						nodes.push(Node {
							span: Span::new(dir_span.start, token_span.end),
							ty: NodeTy::ExtensionDirective {
								name: None,
								behaviour: Some((behaviour, token_span)),
							},
						});
						return;
					}
					None => {
						walker.push_colour(
							token_span,
							SyntaxType::DirectiveExtName,
						);
						(str, token_span)
					}
				}
			}
			ExtensionToken::Colon => {
				walker.push_colour(token_span, SyntaxType::Directive);
				walker.push_syntax_diag(Syntax::PreprocExt(
					PreprocExtDiag::MissingNameBetweenKwAndColon(
						Span::new_between(kw_span, token_span),
					),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, kw_span.end),
					ty: NodeTy::ExtensionDirective {
						name: None,
						behaviour: None,
					},
				});
				return;
			}
			ExtensionToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocExt(
					PreprocExtDiag::ExpectedName(token_span),
				));
				seek_end(walker, tokens, false);
				return;
			}
		}
	};

	// Consume the colon.
	let colon_span = match tokens.next() {
		Some((token, token_span)) => match token {
			ExtensionToken::Colon => {
				walker.push_colour(token_span, SyntaxType::Directive);
				token_span
			}
			ExtensionToken::Word(str) => {
				match parse_behaviour(&str, token_span) {
					Some((behaviour, _)) => {
						walker.push_colour(
							token_span,
							SyntaxType::DirectiveExtBehaviour,
						);
						walker.push_syntax_diag(Syntax::PreprocExt(
							PreprocExtDiag::MissingColonBetweenNameAndBehaviour(
								Span::new_between(name.1, token_span),
							),
						));
						seek_end(walker, tokens, false);
						nodes.push(Node {
							span: Span::new(dir_span.start, token_span.end),
							ty: NodeTy::ExtensionDirective {
								name: Some(name),
								behaviour: Some((behaviour, token_span)),
							},
						});
						return;
					}
					None => {
						walker.push_colour(token_span, SyntaxType::Directive);
						walker.push_syntax_diag(Syntax::PreprocExt(
							PreprocExtDiag::ExpectedColon(token_span),
						));
						seek_end(walker, tokens, false);
						nodes.push(Node {
							span: Span::new(dir_span.start, name.1.end),
							ty: NodeTy::ExtensionDirective {
								name: Some(name),
								behaviour: None,
							},
						});
						return;
					}
				}
			}
			ExtensionToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocExt(
					PreprocExtDiag::ExpectedColon(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, name.1.end),
					ty: NodeTy::ExtensionDirective {
						name: Some(name),
						behaviour: None,
					},
				});
				return;
			}
		},
		None => {
			walker.push_syntax_diag(Syntax::PreprocExt(
				PreprocExtDiag::ExpectedColon(name.1.next_single_width()),
			));
			nodes.push(Node {
				span: Span::new(dir_span.start, name.1.end),
				ty: NodeTy::ExtensionDirective {
					name: Some(name),
					behaviour: None,
				},
			});
			return;
		}
	};

	// Consume the behaviour.
	let behaviour = match tokens.next() {
		Some((token, token_span)) => match token {
			ExtensionToken::Word(str) => {
				match parse_behaviour(&str, token_span) {
					Some((behaviour, diag)) => {
						walker.push_colour(
							token_span,
							SyntaxType::DirectiveExtBehaviour,
						);
						if let Some(diag) = diag {
							walker.push_syntax_diag(diag);
						}
						(behaviour, token_span)
					}
					None => {
						walker.push_colour(token_span, SyntaxType::Directive);
						walker.push_syntax_diag(Syntax::PreprocExt(
							PreprocExtDiag::InvalidBehaviour(token_span),
						));
						seek_end(walker, tokens, false);
						nodes.push(Node {
							span: Span::new(dir_span.start, colon_span.end),
							ty: NodeTy::ExtensionDirective {
								name: Some(name),
								behaviour: None,
							},
						});
						return;
					}
				}
			}
			ExtensionToken::Colon => {
				walker.push_colour(token_span, SyntaxType::Directive);
				walker.push_syntax_diag(Syntax::PreprocExt(
					PreprocExtDiag::ExpectedBehaviour(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, colon_span.end),
					ty: NodeTy::ExtensionDirective {
						name: Some(name),
						behaviour: None,
					},
				});
				return;
			}
			ExtensionToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocExt(
					PreprocExtDiag::ExpectedBehaviour(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, colon_span.end),
					ty: NodeTy::ExtensionDirective {
						name: Some(name),
						behaviour: None,
					},
				});
				return;
			}
		},
		None => {
			walker.push_syntax_diag(Syntax::PreprocExt(
				PreprocExtDiag::ExpectedBehaviour(name.1.next_single_width()),
			));
			nodes.push(Node {
				span: Span::new(dir_span.start, colon_span.end),
				ty: NodeTy::ExtensionDirective {
					name: Some(name),
					behaviour: None,
				},
			});
			return;
		}
	};

	seek_end(walker, tokens, true);
	nodes.push(Node {
		span: Span::new(dir_span.start, behaviour.1.end),
		ty: NodeTy::ExtensionDirective {
			name: Some(name),
			behaviour: Some(behaviour),
		},
	});
}

/// Parses a `#line` directive.
fn parse_line_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	dir_span: Span,
	kw_span: Span,
	tokens: Vec<(LineToken, Span)>,
) {
	walker.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
	walker.push_colour(kw_span, SyntaxType::DirectiveName);

	if tokens.is_empty() {
		walker.push_syntax_diag(Syntax::PreprocLine(
			PreprocLineDiag::ExpectedNumber(kw_span.next_single_width()),
		));
		return;
	}
	let mut tokens = tokens.into_iter();

	/// Consumes the rest of the tokens.
	fn seek_end<'a, P: TokenStreamProvider<'a>>(
		walker: &mut Walker<'a, P>,
		mut tokens: impl Iterator<Item = (LineToken, Span)>,
		emit_diagnostic: bool,
	) {
		let span_start = match tokens.next() {
			Some((_, span)) => span.start,
			None => return,
		};
		let mut span_end = span_start;
		for (token, token_span) in tokens {
			walker.push_colour(
				token_span,
				match token {
					LineToken::Invalid(_) => SyntaxType::Invalid,
					_ => SyntaxType::Directive,
				},
			);
			span_end = token_span.end;
		}
		if emit_diagnostic {
			walker.push_syntax_diag(Syntax::PreprocTrailingTokens(Span::new(
				span_start, span_end,
			)));
		}
	}

	let line = {
		let (token, token_span) = tokens.next().unwrap();
		match token {
			LineToken::Num(n) => {
				walker.push_colour(token_span, SyntaxType::DirectiveLineNumber);
				Some((n, token_span))
			}
			LineToken::InvalidNum(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocLine(
					PreprocLineDiag::InvalidNumber(token_span),
				));
				None
			}
			LineToken::Ident(_str) => {
				let _ident_span = token_span;

				let line = None;
				let src_str_num = Omittable::None;
				if src_str_num.is_some() {
					seek_end(walker, tokens, true);
					nodes.push(Node {
						span: Span::new(dir_span.start, kw_span.end),
						ty: NodeTy::LineDirective { line, src_str_num },
					});
					return;
				} else {
					line
				}
			}
			LineToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocLine(
					PreprocLineDiag::ExpectedNumber(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(dir_span.start, kw_span.end),
					ty: NodeTy::LineDirective {
						line: None,
						src_str_num: Omittable::None,
					},
				});
				return;
			}
		}
	};

	let src_str_num = match tokens.next() {
		Some((token, token_span)) => match token {
			LineToken::Num(n) => {
				walker.push_colour(token_span, SyntaxType::DirectiveLineNumber);
				Omittable::Some((n, token_span))
			}
			LineToken::InvalidNum(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocLine(
					PreprocLineDiag::InvalidNumber(token_span),
				));
				Omittable::None
			}
			LineToken::Ident(_str) => Omittable::None,
			LineToken::Invalid(_) => {
				walker.push_colour(token_span, SyntaxType::Invalid);
				walker.push_syntax_diag(Syntax::PreprocLine(
					PreprocLineDiag::ExpectedNumber(token_span),
				));
				seek_end(walker, tokens, false);
				nodes.push(Node {
					span: Span::new(
						dir_span.start,
						if let Some(line) = line {
							line.1.end
						} else {
							kw_span.end
						},
					),
					ty: NodeTy::LineDirective {
						line,
						src_str_num: Omittable::None,
					},
				});
				return;
			}
		},
		None => Omittable::None,
	};

	seek_end(walker, tokens, true);
	nodes.push(Node {
		span: Span::new(
			dir_span.start,
			if let Omittable::Some(src_str_num) = src_str_num {
				src_str_num.1.end
			} else if let Some(line) = line {
				line.1.end
			} else {
				kw_span.end
			},
		),
		ty: NodeTy::LineDirective { line, src_str_num },
	});
}

/// Parses an `#error` directive.
fn parse_error_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	dir_span: Span,
	kw_span: Span,
	message: Option<Spanned<String>>,
) {
	walker.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
	walker.push_colour(kw_span, SyntaxType::DirectiveName);
	if let Some(ref message) = message {
		walker.push_colour(message.1, SyntaxType::DirectiveError);
	}
	nodes.push(Node {
		span: Span::new(
			dir_span.start,
			if let Some(ref message) = message {
				message.1.end
			} else {
				kw_span.end
			},
		),
		ty: NodeTy::ErrorDirective {
			message: message.into(),
		},
	});
}

/// Parses a `#pragma` directive.
fn parse_pragma_directive<'a, P: TokenStreamProvider<'a>>(
	walker: &mut Walker<'a, P>,
	nodes: &mut Vec<Node>,
	dir_span: Span,
	kw_span: Span,
	options: Option<Spanned<String>>,
) {
	walker.push_colour(dir_span.first_char(), SyntaxType::DirectiveHash);
	walker.push_colour(kw_span, SyntaxType::DirectiveName);
	if let Some(ref options) = options {
		walker.push_colour(options.1, SyntaxType::DirectivePragma);
	}
	nodes.push(Node {
		span: Span::new(
			dir_span.start,
			if let Some(ref options) = options {
				options.1.end
			} else {
				kw_span.end
			},
		),
		ty: NodeTy::PragmaDirective {
			options: options.into(),
		},
	});
}

/// Combines the ident information with the type to create one or more type-ident pairs. This step is necessary
/// because the idents themselves can contain type information, e.g. `int[3] i[9]`.
fn combine_type_with_idents(
	type_: Type,
	ident_info: Vec<(Ident, Vec<ArrSize>)>,
) -> Vec<(Type, Ident)> {
	let mut vars = Vec::new();
	for (ident, sizes) in ident_info {
		if sizes.is_empty() {
			vars.push((type_.clone(), ident));
		} else {
			let mut sizes = sizes.clone();
			let Type {
				ty,
				qualifiers,
				span,
			} = type_.clone();
			let primitive = match ty {
				TypeTy::Single(p) => p,
				TypeTy::Array(p, i) => {
					sizes.push(i);
					p
				}
				TypeTy::Array2D(p, i, j) => {
					sizes.push(i);
					sizes.push(j);
					p
				}
				TypeTy::ArrayND(p, mut v) => {
					sizes.append(&mut v);
					p
				}
			};

			let type_ = if sizes.len() == 0 {
				Type {
					span,
					ty: TypeTy::Single(primitive),
					qualifiers,
				}
			} else if sizes.len() == 1 {
				Type {
					span,
					ty: TypeTy::Array(primitive, sizes.remove(0)),
					qualifiers,
				}
			} else if sizes.len() == 2 {
				Type {
					span,
					ty: TypeTy::Array2D(
						primitive,
						sizes.remove(0),
						sizes.remove(0),
					),
					qualifiers,
				}
			} else {
				Type {
					span,
					ty: TypeTy::ArrayND(primitive, sizes),
					qualifiers,
				}
			};

			vars.push((type_, ident))
		}
	}
	vars
}