rustidy_parse/

lib.rs

//! Parsing

// Features
#![feature(
	never_type,
	try_trait_v2,
	try_trait_v2_residual,
	pattern,
	coverage_attribute,
	decl_macro,
	macro_metavar_expr_concat,
	unwrap_infallible,
	substr_range
)]

// Lints
#![cfg_attr(
	not(feature = "flamegraph-traces"),
	expect(unused_crate_dependencies, reason = "It's only used with that feature flag")
)]

// Modules
mod error;
mod recursive;
mod tag;
mod whitespace;

// Exports
pub use {
	self::{
		error::{ParseError, ParserError},
		recursive::{
			FromRecursiveRoot,
			IntoRecursiveRoot,
			ParsableRecursive,
			ParseRecursive,
			RecursiveWrapper,
			TryFromRecursiveRoot,
		},
		tag::ParserTag,
	},
	rustidy_macros::Parse,
};

// Imports
use {
	app_error::AppError,
	arcstr::ArcStr,
	core::{marker::PhantomData, ops::{Residual, Try}},
	rustidy_util::{ArenaData, ArenaIdx, AstPos, AstRange, AstStr},
	std::fmt,
};
#[cfg(feature = "flamegraph-traces")]
use {
	app_error::Context,
	flate2::write::GzEncoder,
	std::{env, fs, io::BufWriter, io::Write},
};

/// Parsable types
pub trait Parse: Sized {
	/// Error type
	type Error: ParseError;

	/// A name for this type.
	///
	/// This is mostly used in error reporting and should be a lower case name,
	/// with `a` / `an` prefixed. Used for example in the following way:
	/// `expected {name}, found {other_name}`.
	///
	/// If this returns `None`, no extra error is displayed when parsing the type.
	/// This is useful for containers that usually don't want to expose themselves
	#[must_use]
	#[coverage(off)]
	fn name() -> Option<impl fmt::Display> {
		None::<!>
	}

	/// Parses this type from `input`, mutating it in-place.
	fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error>;
}

#[derive(Debug)]
pub struct NeverError;

impl ParseError for NeverError {
	fn is_fatal(&self) -> bool {
		false
	}

	fn pos(&self) -> Option<AstPos> {
		None
	}

	fn to_app_error(&self, _parser: &Parser) -> AppError {
		AppError::from_multiple([])
	}
}

impl Parse for ! {
	type Error = NeverError;

	fn parse_from(_parser: &mut Parser) -> Result<Self, Self::Error> {
		Err(NeverError)
	}
}

impl<T> Parse for PhantomData<T> {
	type Error = !;

	fn parse_from(_parser: &mut Parser) -> Result<Self, Self::Error> {
		Ok(Self)
	}
}

impl<T> Parse for Box<T>
where
	T: Parse, {
	type Error = T::Error;

	fn name() -> Option<impl fmt::Display> {
		T::name()
	}

	fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error> {
		T::parse_from(parser).map(Self::new)
	}
}

impl<T> Parse for Option<T>
where
	T: Parse, {
	type Error = T::Error;

	fn name() -> Option<impl fmt::Display> {
		T::name()
	}

	fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error> {
		parser
			.try_parse_with(T::parse_from)
			.map(Result::ok)
	}
}

impl<T> Parse for Vec<T>
where
	T: Parse, {
	type Error = T::Error;

	fn name() -> Option<impl fmt::Display> {
		T::name()
	}

	fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error> {
		let mut values = vec![];
		loop {
			let start_pos = parser.cur_pos;
			match parser.try_parse_with(T::parse_from)? {
				Ok(value) if parser.cur_pos != start_pos => values.push(value),
				_ => break,
			}
		}

		Ok(values)
	}
}

impl Parse for () {
	type Error = !;

	fn parse_from(_parser: &mut Parser) -> Result<Self, Self::Error> {
		Ok(())
	}
}

macro tuple_impl(
	$N:literal, $($T:ident),* $(,)?
) {
	#[automatically_derived]
	impl< $($T: Parse,)* > Parse for ( $($T,)* ) {
		type Error = ${concat( Tuple, $N, Error )}< $($T,)* >;

		#[expect(non_snake_case)]
		fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error> {
			$(
				let $T = parser.parse().map_err(Self::Error::$T)?;
			)*
			Ok(( $( $T, )* ))
		}
	}

	#[derive(derive_more::Debug)]
	pub enum ${concat( Tuple, $N, Error )}< $($T: Parse,)* > {
		$(
			$T(ParserError<$T>),
		)*
	}

	#[automatically_derived]
	impl< $($T: Parse,)* > ParseError for ${concat( Tuple, $N, Error )}< $($T,)* > {
		fn is_fatal(&self) -> bool {
			match *self {
				$(
					Self::$T(ref err, ..) => err.is_fatal(),
				)*
			}
		}

		fn pos(&self) -> Option<AstPos> {
			match *self {
				$(
					Self::$T(ref err, ..) => err.pos(),
				)*
			}
		}

		fn to_app_error(&self, parser: &Parser) -> AppError {
			match *self {
				$(
					Self::$T(ref err, ..) => err.to_app_error(parser),
				)*
			}
		}
	}
}

tuple_impl! { 1, T0 }
tuple_impl! { 2, T0, T1 }
tuple_impl! { 3, T0, T1, T2 }
tuple_impl! { 4, T0, T1, T2, T3 }

impl<T: ArenaData + Parse> Parse for ArenaIdx<T> {
	type Error = T::Error;

	fn name() -> Option<impl fmt::Display> {
		T::name()
	}

	fn parse_from(parser: &mut Parser) -> Result<Self, Self::Error> {
		let value = T::parse_from(parser)?;
		let idx = Self::new(value);
		Ok(idx)
	}
}

/// Parser
#[derive(Debug)]
pub struct Parser {
	/// Input
	input:           ArcStr,

	/// Current position
	cur_pos:         AstPos,

	/// Tags
	// Note: Always sorted by ast position.
	tags:            Vec<(AstPos, ParserTag)>,

	/// Tags offset
	tags_offset:     usize,

	#[cfg(feature = "flamegraph-traces")]
	stack:           Vec<&'static str>,

	#[cfg(feature = "flamegraph-traces")]
	trace_max_depth: usize,

	#[cfg(feature = "flamegraph-traces")]
	trace_file:      BufWriter<GzEncoder<fs::File>>,
}

impl Parser {
	/// Creates a new parser
	#[must_use]
	pub fn new(input: impl Into<ArcStr>) -> Self {
		Self {
			input: input.into(),
			cur_pos: AstPos::from_usize(0),
			tags: vec![],
			tags_offset: 0,
			#[cfg(feature = "flamegraph-traces")]
			stack: {
				let mut stack = Vec::with_capacity(128);
				stack.push("parse");
				stack
			},
			#[cfg(feature = "flamegraph-traces")]
			trace_max_depth: {
				let var = "RUSTIDY_FLAMEGRAPH_TRACE_MAX_DEPTH";
				let default = 50;

				match self::get_flamegraph_trace_max_depth(var, default) {
					Ok(max_depth) => max_depth,
					Err(err) => {
						tracing::warn!("Unable to parse {var:?}: {err:?}");
						default
					},
				}
			},
			#[cfg(feature = "flamegraph-traces")]
			trace_file: {
				let var = "RUSTIDY_FLAMEGRAPH_TRACE_FILE";
				let default = "output.gz";

				self::open_flamegraph_trace_file(var, default).unwrap_or_else(
					|err| panic!("Unable to create {var:?}: {err:?}")
				)
			},
		}
	}

	/// Returns the whole input of the parser
	#[must_use]
	pub const fn input(&self) -> &ArcStr {
		&self.input
	}

	/// Returns the remaining string for the parser
	#[must_use]
	pub fn remaining(&self) -> &str {
		&self.input[self.cur_pos.0..]
	}

	/// Returns the current position of the parser
	pub const fn cur_pos(&mut self) -> AstPos {
		self.cur_pos
	}

	/// Sets the position of this parser
	pub const fn set_pos(&mut self, pos: AstPos) {
		self.cur_pos = pos;
	}

	/// Reverses all whitespace (except the last) in the current position
	pub fn reverse_whitespace(&mut self) {
		self.cur_pos.0 = self
			.input[..self
			.cur_pos.0]
			.rfind(|ch: char| !ch.is_whitespace())
			.map_or(0, |idx| idx + 1);
	}

	/// Reverses to the start of the current line
	pub fn reverse_line(&mut self) {
		self.cur_pos.0 = self
			.input[..self
			.cur_pos.0]
			.rfind('\n')
			.map_or(0, |idx| idx + 1);
	}

	/// Returns the current line of the parser, not including the end
	#[must_use]
	pub fn cur_line(&self) -> &str {
		let start = self
			.input[..self
			.cur_pos.0]
			.rfind('\n')
			.map_or(0, |idx| idx + 1);
		let end = self.cur_pos.0 + self
			.input[self
			.cur_pos.0..]
			.find('\n')
			.unwrap_or(self.input.len() - self.cur_pos.0);

		&self.input[start..end]
	}

	/// Gets the position (0-indexed) of the parser at a position
	#[must_use]
	pub fn loc(&self, pos: AstPos) -> ParserLoc {
		let line = self
			.input[..pos.0]
			.chars()
			.filter(|&ch| ch == '\n').count();
		let column = match self.input[..pos.0].rfind('\n') {
			Some(newline_pos) => pos.0 - newline_pos - 1,
			None => pos.0,
		};

		ParserLoc { line, column }
	}

	/// Gets the current position (0-indexed) of the parser
	#[must_use]
	pub fn cur_loc(&self) -> ParserLoc {
		self.loc(self.cur_pos)
	}

	/// Returns if the parser is finished
	#[must_use]
	pub fn is_finished(&self) -> bool {
		self.remaining().is_empty()
	}

	/// Updates this parser from a string.
	///
	/// See [`Self::try_update_with`] for more details.
	pub fn update_with<F, O>(&mut self, f: F) -> (AstStr, O)
	where
		F: FnOnce(&mut &str) -> O,
	{
		self
			.try_update_with(|remaining| Ok::<_, !>(f(remaining)))
			.into_ok()
	}

	/// Updates this parser from a string.
	///
	/// The function `f` receives a string to update.
	/// The value it is updated with *must* be a substring of the
	/// received function.
	///
	/// # Success
	/// When `f` returns successfully, the parser is updated from
	/// the state of the string.
	///
	/// # Failure
	/// If `f` returns unsuccessfully, an error will be returned
	/// with the latest change to the string as it's position.
	pub fn try_update_with<F, T>(&mut self, f: F) -> <T::Residual as Residual<(AstStr, T::Output)>>::TryType
	where
		F: FnOnce(&mut &str) -> T,
		T: Try<Residual: Residual<(AstStr, T::Output)>>,
	{
		let mut remaining = self.remaining();
		let res = f(&mut remaining);

		let remaining_range = self
			.remaining()
			.substr_range(remaining)
			.expect("Result was not a substring of the input");
		assert_eq!(self.cur_pos.0 + remaining_range.end, self.input.len(), "Updated string truncated input");

		let output_range = self.cur_pos.0..self.cur_pos.0 + remaining_range.start;
		self.cur_pos.0 += remaining_range.start;

		// After updating the remaining, quit if an error occurred
		let value = res?;

		<_>::from_output(
			(AstStr::from_input(self.input.substr(output_range)), value)
		)
	}

	/// Parses `T` from this parser
	pub fn parse<T: Parse>(&mut self) -> Result<T, ParserError<T>> {
		#[cfg(feature = "flamegraph-traces")]
		let emit_traces = self.stack.len() < self.trace_max_depth;

		#[cfg(feature = "flamegraph-traces")]
		if emit_traces {
			self.stack.push(std::any::type_name::<T>());
		}

		#[cfg(feature = "flamegraph-traces")]
		let start = self::flamegraph_trace_get_timestamp();

		let start_pos = self.cur_pos;
		let res = T::parse_from(self).map_err(
			|source| ParserError::new(source, AstRange::new(start_pos, self.cur_pos))
		);

		#[cfg(feature = "flamegraph-traces")]
		let end = self::flamegraph_trace_get_timestamp();

		// TODO: Do this in another thread?
		#[cfg(feature = "flamegraph-traces")]
		if emit_traces {
			self.stack.pop();
			for &ty in &self.stack {
				write!(self.trace_file, "{ty};")
					.expect("Unable to write to trace file");
			}
			writeln!(self.trace_file, "{} {}", std::any::type_name::<T>(), end - start)
				.expect("Unable to write to trace file");
		}

		res
	}

	/// Parses `T` from this parser with a peeked value
	pub fn parse_with_peeked<T: ParsePeeked<U>, U>(&mut self, parsed: U) -> Result<T, ParserError<T>> {
		let start_pos = self.cur_pos;
		T::parse_from_with_peeked(self, parsed).map_err(
			|source| ParserError::new(source, AstRange::new(start_pos, self.cur_pos))
		)
	}

	/// Tries to parses `T` from this parser using `parser` for parsing.
	///
	/// On error, nothing is modified.
	pub fn try_parse_with<T, E: ParseError>(&mut self, parser: impl FnOnce(&mut Self) -> Result<T, E>,) -> Result<Result<T, E>, E> {
		let prev_pos = self.cur_pos;
		match parser(self) {
			Ok(value) => Ok(Ok(value)),
			Err(err) if err.is_fatal() => Err(err),
			Err(err) => {
				self.cur_pos = prev_pos;
				Ok(Err(err))
			},
		}
	}

	/// Tries to parses `T` from this parser.
	///
	/// On error, nothing is modified.
	pub fn try_parse<T: Parse>(&mut self) -> Result<Result<T, ParserError<T>>, ParserError<T>> {
		self.try_parse_with(Self::parse::<T>)
	}

	/// Peeks a `T` from this parser using `parser` for parsing.
	///
	/// Parser is only advanced is a fatal error occurs
	pub fn peek_with<T, E: ParseError>(&mut self, parse: impl FnOnce(&mut Self) -> Result<T, E>,) -> Result<Result<(T, PeekState), E>, E> {
		let start_pos = self.cur_pos;
		let output = match parse(self) {
			Ok(value) => Ok(value),
			Err(err) if err.is_fatal() => return Err(err),
			Err(err) => Err(err),
		};

		let peek_state = PeekState { cur_pos: self.cur_pos };
		self.cur_pos = start_pos;

		let output = output.map(|value| (value, peek_state));
		Ok(output)
	}

	/// Peeks a `T` from this parser.
	///
	/// Parser is only advanced is a fatal error occurs
	#[expect(clippy::type_complexity, reason = "TODO")]
	pub fn peek<T: Parse>(&mut self) -> Result<Result<(T, PeekState), ParserError<T>>, ParserError<T>> {
		self.peek_with(Self::parse::<T>)
	}

	/// Accepts a peeked state.
	#[expect(
		clippy::needless_pass_by_value,
		reason = "It's to ensure the user doesn't use the same peek state multiple times"
	)]
	pub const fn set_peeked(&mut self, peek_state: PeekState) {
		self.cur_pos = peek_state.cur_pos;
	}

	/// Returns all current tags
	pub fn tags(&self) -> impl Iterator<Item = ParserTag> {
		self
			.tags[self
			.tags_offset..]
			.iter()
			.rev()
			.take_while(|&&(pos, _)| pos == self.cur_pos)
			.map(|&(_, tag)| tag)
	}

	/// Returns if this parser has a tag
	#[must_use]
	pub fn has_tag(&self, tag: impl Into<ParserTag>) -> bool {
		let tag = tag.into();
		self.tags().any(|cur_tag| cur_tag == tag)
	}

	/// Calls `f` with tags `tags` added to this parser
	pub fn with_tags<O>(
		&mut self,
		tags: impl IntoIterator<Item = ParserTag>,
		f: impl FnOnce(&mut Self) -> O
	) -> O {
		let tags_len = self.tags.len();

		for tag in tags {
			self.tags.push((self.cur_pos, tag));
		}
		let output = f(self);
		self.tags.truncate(tags_len);

		output
	}

	/// Calls `f` with tag `tag` added to this parser
	pub fn with_tag<O>(
		&mut self,
		tag: impl Into<ParserTag>,
		f: impl FnOnce(&mut Self) -> O
	) -> O {
		self.with_tags([tag.into()], f)
	}

	/// Calls `f` with all tags removed.
	pub fn without_tags<O>(&mut self, f: impl FnOnce(&mut Self) -> O) -> O {
		let prev_offset = self.tags_offset;
		self.tags_offset = self.tags.len();
		let output = f(self);
		self.tags_offset = prev_offset;

		output
	}
}

/// Peek state
#[derive(Debug)]
pub struct PeekState {
	cur_pos: AstPos,
}

impl PeekState {
	/// Returns if this peek state is further ahead than another
	#[must_use]
	pub fn ahead_of(&self, other: &Self) -> bool {
		self.cur_pos > other.cur_pos
	}

	/// Returns if this peek state is further ahead or equal to another
	#[must_use]
	pub fn ahead_of_or_equal(&self, other: &Self) -> bool {
		self.cur_pos >= other.cur_pos
	}
}

/// Parser location (0-indexed).
///
/// # Display
/// The display impl transforms this into a 1-indexed format of `{line}:{column}`
#[derive(Debug)]
#[derive(derive_more::Display)]
#[display("{}:{}", line + 1, column + 1)]
pub struct ParserLoc {
	pub line:   usize,
	pub column: usize,
}

/// Types that may be parsed using a peek into itself
pub trait ParsePeeked<T>: Parse {
	fn parse_from_with_peeked(parser: &mut Parser, parsed: T) -> Result<Self, Self::Error>;
}

impl<T, U> ParsePeeked<U> for T
where
	T: Parse + From<U>, {
	fn parse_from_with_peeked(_parser: &mut Parser, parsed: U) -> Result<Self, Self::Error> {
		Ok(parsed.into())
	}
}

/// Types that may be parsed from another
pub trait ParsableFrom<T> {
	fn from_parsable(value: T) -> Self;
}

/// `[Parser::parse]` for strings
pub fn parse_from_str<'a, F, E>(s: &mut &'a str, parse: F) -> Result<&'a str, E>
where
	F: FnOnce(&mut &'a str) -> Result<(), E>,
	E: ParseError,
{
	let start = *s;
	parse(s)?;
	let range = start
		.substr_range(s)
		.expect("Output was not a substring of the input");
	let parsed = &start[..range.start];
	Ok(parsed)
}

/// `[Parser::try_parse]` for strings
pub fn try_parse_from_str<'a, F, E>(s: &mut &'a str, parse: F) -> Result<Result<&'a str, E>, E>
where
	F: FnOnce(&mut &'a str) -> Result<(), E>,
	E: ParseError,
{
	match self::parse_from_str(s, parse) {
		Ok(value) => Ok(Ok(value)),
		Err(err) if err.is_fatal() => Err(err),
		Err(err) => Ok(Err(err)),
	}
}

#[cfg(feature = "flamegraph-traces")]
fn get_flamegraph_trace_max_depth(var: &str, default: usize) -> Result<usize, AppError> {
	let Ok(max_depth) = env::var(var) else {
		return Ok(default);
	};

	max_depth
		.parse::<usize>()
		.context("Unable to parse value")
}

#[cfg(feature = "flamegraph-traces")]
fn open_flamegraph_trace_file(var: &str, default: &str) -> Result<BufWriter<GzEncoder<fs::File>>, AppError> {
	let res = env::var(var);
	let path = match &res {
		Ok(path) => path,
		Err(_) => default,
	};

	let file = fs::File::create(path)
		.context("Unable to create file")?;
	let file = GzEncoder::new(file, flate2::Compression::fast());
	Ok(BufWriter::new(file))
}

#[cfg(feature = "flamegraph-traces")]
fn flamegraph_trace_get_timestamp() -> u64 {
	// Safety: `rdtsc` is always safe to call
	unsafe {
		std::arch::x86_64::_rdtsc()
	}
}