Eliminating whitespace from the parser logic

[LucaCappelletti94]

Hi,

At this time, whitespace tokens are stored in the parser, and are then filtered out in several distinct points in the parser logic, such as:

• datafusion-sqlparser-rs/src/parser/mod.rs

  Lines 4032 to 4049 in 67684c8

  	pub fn peek_tokens_with_location<const N: usize>(&self) -> [TokenWithSpan; N] {
  	let mut index = self.index;
  	core::array::from_fn(|_| loop {
  	let token = self.tokens.get(index);
  	index += 1;
  	if let Some(TokenWithSpan {
  	token: Token::Whitespace(_),
  	span: _,
  	}) = token
  	{
  	continue;
  	}
  	break token.cloned().unwrap_or(TokenWithSpan {
  	token: Token::EOF,
  	span: Span::empty(),
  	});
  	})
  	}

• datafusion-sqlparser-rs/src/parser/mod.rs

  Lines 4055 to 4069 in 67684c8

  	pub fn peek_tokens_ref<const N: usize>(&self) -> [&TokenWithSpan; N] {
  	let mut index = self.index;
  	core::array::from_fn(|_| loop {
  	let token = self.tokens.get(index);
  	index += 1;
  	if let Some(TokenWithSpan {
  	token: Token::Whitespace(_),
  	span: _,
  	}) = token
  	{
  	continue;
  	}
  	break token.unwrap_or(&EOF_TOKEN);
  	})
  	}

• datafusion-sqlparser-rs/src/parser/mod.rs

  Lines 4077 to 4094 in 67684c8

  	pub fn peek_nth_token_ref(&self, mut n: usize) -> &TokenWithSpan {
  	let mut index = self.index;
  	loop {
  	index += 1;
  	match self.tokens.get(index - 1) {
  	Some(TokenWithSpan {
  	token: Token::Whitespace(_),
  	span: _,
  	}) => continue,
  	non_whitespace => {
  	if n == 0 {
  	return non_whitespace.unwrap_or(&EOF_TOKEN);
  	}
  	n -= 1;
  	}
  	}
  	}
  	}

• datafusion-sqlparser-rs/src/parser/mod.rs

  Lines 4149 to 4160 in 67684c8

  	pub fn advance_token(&mut self) {
  	loop {
  	self.index += 1;
  	match self.tokens.get(self.index - 1) {
  	Some(TokenWithSpan {
  	token: Token::Whitespace(_),
  	span: _,
  	}) => continue,
  	_ => break,
  	}
  	}
  	}

• datafusion-sqlparser-rs/src/parser/mod.rs

  Lines 4183 to 4202 in 67684c8

  	/// Seek back the last one non-whitespace token.
  	///
  	/// Must be called after `next_token()`, otherwise might panic. OK to call
  	/// after `next_token()` indicates an EOF.
  	///
  	// TODO rename to backup_token and deprecate prev_token?
  	pub fn prev_token(&mut self) {
  	loop {
  	assert!(self.index > 0);
  	self.index -= 1;
  	if let Some(TokenWithSpan {
  	token: Token::Whitespace(_),
  	span: _,
  	}) = self.tokens.get(self.index)
  	{
  	continue;
  	}
  	return;
  	}
  	}

and many more.

SQL, as far as I know, is not a language that cares about spaces like Python - it should be safe to remove all concepts of whitespaces after the tokenization process is complete, and this should:

• Reduce memory requirements, as whitespace tokens would not be stored anymore
• Significantly simplify parser logic by removing all of the whitespace-related logic from the parser
• Move the parser closer to a streaming logic, but that will require many more PRs

Since such a PR would require quite a bit of effort on my part, I would appreciate some feedback on it before moving forward with it.

@iffyio do you happen to have any opinion regarding such a refactoring?

Ciao,
Luca

[LucaCappelletti94]

I have encountered the following case which I had honestly never heard of before. I suggest to move such data preprocessing in the tokenizer, as I would argue the benefits of totally removing the whitespace from the parser logic are massive. I shall attempt a PR to do so.

datafusion-sqlparser-rs/tests/sqlparser_postgres.rs

Lines 1016 to 1038 in 67684c8

	fn parse_copy_from_stdin() {
	let sql = r#"COPY public.actor (actor_id, first_name, last_name, last_update, value) FROM stdin;
	1 PENELOPE GUINESS 2006-02-15 09:34:33 0.11111
	2 NICK WAHLBERG 2006-02-15 09:34:33 0.22222
	3 ED CHASE 2006-02-15 09:34:33 0.312323
	4 JENNIFER DAVIS 2006-02-15 09:34:33 0.3232
	5 JOHNNY LOLLOBRIGIDA 2006-02-15 09:34:33 1.343
	6 BETTE NICHOLSON 2006-02-15 09:34:33 5.0
	7 GRACE MOSTEL 2006-02-15 09:34:33 6.0
	8 MATTHEW JOHANSSON 2006-02-15 09:34:33 7.0
	9 JOE SWANK 2006-02-15 09:34:33 8.0
	10 CHRISTIAN GABLE 2006-02-15 09:34:33 9.1
	11 ZERO CAGE 2006-02-15 09:34:33 10.001
	12 KARL BERRY 2017-11-02 19:15:42.308637+08 11.001
	A Fateful Reflection of a Waitress And a Boat who must Discover a Sumo Wrestler in Ancient China
	Kwara & Kogi
	{"Deleted Scenes","Behind the Scenes"}
	'awe':5 'awe-inspir':4 'barbarella':1 'cat':13 'conquer':16 'dog':18 'feminist':10 'inspir':6 'monasteri':21 'must':15 'stori':7 'streetcar':2
	PHP ₱ USD $
	\N Some other value
	\\."#;
	pg_and_generic().one_statement_parses_to(sql, "");
	}

[LucaCappelletti94]

I managed to get a reasonably refactored version to handle the COPY... STDIN thing, but I am now struggling to find a solution for big query identifiers, which unfortunately require or ignore spaces depending on context. See:

datafusion-sqlparser-rs/tests/sqlparser_bigquery.rs

Lines 1696 to 1725 in 67684c8

	assert_eq!(
	bigquery()
	.verified_only_select_with_canonical(
	"select * from foo-123.bar",
	"SELECT * FROM foo-123.bar"
	)
	.from[0]
	.relation,
	table_from_name(ObjectName::from(vec![
	Ident::new("foo-123"),
	Ident::new("bar")
	])),
	);
	assert_eq!(
	bigquery()
	.verified_only_select_with_canonical(
	"SELECT foo-bar.x FROM t",
	"SELECT foo - bar.x FROM t"
	)
	.projection[0],
	SelectItem::UnnamedExpr(Expr::BinaryOp {
	left: Box::new(Expr::Identifier(Ident::new("foo"))),
	op: BinaryOperator::Minus,
	right: Box::new(Expr::CompoundIdentifier(vec![
	Ident::new("bar"),
	Ident::new("x")
	]))
	})
	);

At this time, I have no idea how to handle such thing in the context of the Tokenizer, as the Tokenizer should really not be aware of such things.

[iffyio]

@LucaCappelletti94 would the intent be to remove whitespace characters specifically or all of the parser's representations of whitespace? For the former I'm not super sure in general if the parser (or downstream users of the tokenizer) can always disambiguate some of rarer cases going forward without relying on detecting whitespace - I think the current usages of the *no_skip methods could give us an idea.
For the latter, it seems that are some cases like this PR that will require keeping around any comments (which the parser also represents as whitespace).

[LucaCappelletti94]

The #2077 PR basically moves all of the whitespace related processing in the tokenizer, so that the parser can then entirely be freed of dealing with them.

There are some corner cases (the ones listed above) but I feel I ended up dealing with them in a reasonably clean manner. Having removed whitespaces entirely in PR #2077, I can say that the resulting code seems to be much cleaner, and the *_no_skip methods have been entirely removed.

I don't see how the #2034 PR would be blocked by this merge - it is simply another type of comment.

PR #2069 (from a PhD student in my team) in its current version will be comparatively more affected, but after this change it should be exceedingly easier to add support for such leading comments.

[iffyio]

I don't see how the #2034 PR would be blocked by this merge - it is simply another type of comment.

Yeah I think you're right, any required changes for that PR can be handled internally in the tokenizer

[iffyio]

The overall goal sounds reasonable to me, but I'm not sure that I can fully judge the impact of the changes

@alamb @yoavcloud do you have any thoughts on whether discarding whitespace and essentially removing Token::Whitespace would be desirable?

[alamb]

The overall goal sounds reasonable to me, but I'm not sure that I can fully judge the impact of the changes

@alamb @yoavcloud do you have any thoughts on whether discarding whitespace and essentially removing Token::Whitespace would be desirable?

It seems reasonable to me -- one way to judge the impact of such a change would be to try it out with some other downstream project (e.g. DataFusion). I did a quick search and didn't see any such issues

https://github.com/search?q=repo%3Aapache%2Fdatafusion+Token%3A%3AWhitespace&type=code

[LucaCappelletti94]

It seems reasonable to me -- one way to judge the impact of such a change would be to try it out with some other downstream project (e.g. DataFusion). I did a quick search and didn't see any such issues

There’s already a branch with PR #2077 if you’d like to test whether it breaks anything downstream.

In that branch, I removed several (previously pub) methods related to advancing the parser while skipping or not skipping spaces, and removed the Whitespace token entirely, which I believe is the right approach, as retaining it seems to encourage anti-patterns in SQL parsing (given how often whitespace-specific checks appeared).

While it’s technically possible that someone has extended the tokenizer or parser to rely on whitespace, I’d argue that doing so would already be an anti-pattern and not something we should encourage.