css_parse/
cursor_ordered_sink.rs

1use crate::{Arena, Cursor, CursorSink, Kind, SourceOffset, Vec};
2
3/// This is a [CursorSink] that buffers cursors and emits them in source order. It uses contiguous coverage tracking to
4/// eagerly emit cursors as soon as gaps are filled.
5///
6/// Many CSS grammars allow constructing a tree in arbitrarily authored order, but have a canonical ordering, so for e.g
7/// a function like `foo(bar, baz)` could be represented as `foo(baz, bar)` and still be valid. AST nodes output their
8/// cursors in grammar order, which is most often desirable, but this sink will enforce source ordering.
9pub struct CursorOrderedSink<'a, S> {
10	sink: &'a mut S,
11	/// Sorted buffer of cursors by start position
12	buffer: Vec<'a, Cursor>,
13	/// How far we've committed (emitted contiguously from position 0)
14	committed_position: SourceOffset,
15	#[cfg(debug_assertions)]
16	seen_eof: bool,
17}
18
19impl<'a, S: CursorSink> CursorOrderedSink<'a, S> {
20	pub fn new(alloc: &'a Arena, sink: &'a mut S) -> Self {
21		Self {
22			sink,
23			buffer: Vec::new_in(alloc),
24			committed_position: SourceOffset(0),
25			#[cfg(debug_assertions)]
26			seen_eof: false,
27		}
28	}
29
30	/// Flush all remaining buffered cursors to the delegate sink in source order.
31	/// This is typically called when no more cursors will be added.
32	pub fn flush(&mut self) {
33		self.buffer.sort_by_key(|cursor| cursor.span().start());
34		for cursor in self.buffer.iter() {
35			self.sink.append(*cursor);
36		}
37		if let Some(last_cursor) = self.buffer.last() {
38			self.committed_position = last_cursor.end_offset();
39		}
40		self.buffer.clear();
41	}
42}
43
44impl<'a, S: CursorSink> CursorSink for CursorOrderedSink<'a, S> {
45	// Insert cursor into the buffer, maintaining sorted order efficiently
46	//
47	// The algorithm models cursor coverage as an "array with holes" that get filled over time:
48	//
49	// ```text
50	// Positions: [0][1][2][3][4][5][6]
51	// Initial:   [ ][ ][ ][ ][ ][ ][ ]    committed_position = 0
52	//
53	// Add cursor_4: [ ][ ][ ][ ][4][ ][ ]    buffer: [4], nothing emitted
54	// Add cursor_0: [0][ ][ ][ ][4][ ][ ]    emit [0], committed_position = 1
55	// Add cursor_2: [0][ ][2][ ][4][ ][ ]    buffer: [2,4], gap at 1
56	// Add cursor_1: [0][1][2][ ][4][ ][ ]    emit [1,2], committed_position = 3
57	// Add cursor_3: [0][1][2][3][4][ ][ ]    emit [3,4], committed_position = 5
58	// Add cursor_5: [0][1][2][3][4][5][ ]    emit [5], committed_position = 6
59	// ```
60	//
61	// Once a contiguous section from `committed_position` is complete, it's emitted immediately.
62	fn append(&mut self, cursor: Cursor) {
63		#[cfg(debug_assertions)]
64		{
65			debug_assert!(!self.seen_eof, "Received cursor after EOF: {:?}", cursor);
66			if cursor == Kind::Eof {
67				self.seen_eof = true;
68			}
69		}
70		let cursor_start = cursor.span().start();
71		if self.buffer.is_empty() || cursor_start.0 >= self.buffer.last().unwrap().span().start().0 {
72			self.buffer.push(cursor);
73		} else if cursor_start == self.committed_position {
74			// This cursor is the next in order
75			self.sink.append(cursor);
76			self.committed_position = cursor.end_offset();
77		} else {
78			// The cursor needs to be buffered.
79			// TODO: binary_search_by_key is giving BTreeMap which would be O(log n) instead of O(n), but
80			// for small enough numbers that's fine? Investigate more.
81			let insert_pos =
82				self.buffer.binary_search_by_key(&cursor_start, |c| c.span().start()).unwrap_or_else(|pos| pos);
83			self.buffer.insert(insert_pos, cursor);
84		}
85
86		// Check if a contiguous section from committed_position exists, and emit it if so
87		while !self.buffer.is_empty() {
88			// Remove any overlapping cursors first (those that start before committed_position)
89			let mut overlapping_count = 0;
90			for cursor in self.buffer.iter() {
91				if cursor.span().start().0 < self.committed_position.0 {
92					overlapping_count += 1;
93				} else {
94					break;
95				}
96			}
97			if overlapping_count > 0 {
98				self.buffer.drain(0..overlapping_count);
99			}
100
101			if self.buffer.is_empty() {
102				break;
103			}
104
105			// Find how many contiguous cursors can be emitted from the front
106			let mut current_pos = self.committed_position;
107			let mut emit_count = 0;
108
109			for cursor in self.buffer.iter() {
110				let cursor_start = cursor.span().start();
111
112				if cursor_start == current_pos {
113					current_pos = cursor.end_offset();
114					emit_count += 1;
115				} else {
116					// If this cursor starts after current_pos, stop, as there is a gap
117					break;
118				}
119			}
120
121			if emit_count > 0 {
122				for cursor in self.buffer.drain(0..emit_count) {
123					self.sink.append(cursor);
124				}
125				self.committed_position = current_pos;
126			} else {
127				// No contiguous section found, stop
128				break;
129			}
130		}
131
132		// If we just processed EOF, flush any remaining buffered cursors
133		if cursor == Kind::Eof {
134			self.flush();
135		}
136	}
137}
138
139#[cfg(test)]
140mod tests {
141	use super::*;
142	use crate::Arena;
143	use crate::Vec as ArenaVec;
144	use crate::{ComponentValues, EmptyAtomSet, Parser, SourceCursor, ToCursors};
145	use css_lexer::Lexer;
146	use std::fmt::Write;
147
148	#[test]
149	fn test_basic() {
150		let source_text = "foo bar";
151		let alloc = Arena::default();
152		let mut output = ArenaVec::new_in(&alloc);
153		{
154			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
155			let lexer = Lexer::new(&EmptyAtomSet::ATOMS, source_text);
156			let mut parser = Parser::new(&alloc, source_text, lexer);
157			parser.parse_entirely::<ComponentValues>().output.unwrap().to_cursors(&mut ordered_sink);
158			ordered_sink.flush();
159		}
160		let mut result = String::new();
161		for c in output.iter() {
162			write!(&mut result, "{}", SourceCursor::from(*c, c.str_slice(source_text))).unwrap();
163		}
164		assert_eq!(result, "foo bar");
165	}
166
167	#[test]
168	fn test_manual_flush() {
169		use crate::{SourceOffset, Token};
170
171		let alloc = Arena::default();
172		let mut output = ArenaVec::new_in(&alloc);
173		{
174			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
175			let cursor1 = Cursor::new(SourceOffset(0), Token::SPACE); // position 0, length 1
176			let cursor2 = Cursor::new(SourceOffset(10), Token::SPACE); // position 10, length 1
177			let cursor3 = Cursor::new(SourceOffset(4), Token::SPACE); // position 4, length 1
178
179			// Append cursors in non-source-order
180			ordered_sink.append(cursor2);
181			ordered_sink.append(cursor1);
182			ordered_sink.append(cursor3);
183			ordered_sink.flush();
184		}
185		assert_eq!(output.len(), 3);
186		assert_eq!(output[0].span().start(), SourceOffset(0));
187		assert_eq!(output[1].span().start(), SourceOffset(4));
188		assert_eq!(output[2].span().start(), SourceOffset(10));
189	}
190
191	#[test]
192	fn test_contiguous_eager_emission() {
193		use crate::{SourceOffset, Token};
194		let alloc = Arena::default();
195		let mut output = ArenaVec::new_in(&alloc);
196		{
197			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
198			// Create cursors that form a contiguous sequence
199			let cursor_at_0 = Cursor::new(SourceOffset(0), Token::SPACE);
200			let cursor_at_1 = Cursor::new(SourceOffset(1), Token::SPACE);
201			ordered_sink.append(cursor_at_0);
202			ordered_sink.append(cursor_at_1);
203			// Avoid flushing as they should be emitted immediately
204		}
205		assert_eq!(output.len(), 2);
206		assert_eq!(output[0].span().start(), SourceOffset(0));
207		assert_eq!(output[1].span().start(), SourceOffset(1));
208	}
209
210	#[test]
211	fn test_gap_filling() {
212		use crate::{SourceOffset, Token};
213		let alloc = Arena::default();
214		let mut output = ArenaVec::new_in(&alloc);
215
216		{
217			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
218			// Create cursors with a gap, then fill the gap
219			let cursor_at_0 = Cursor::new(SourceOffset(0), Token::SPACE); // ends at 1
220			let cursor_at_2 = Cursor::new(SourceOffset(2), Token::SPACE); // ends at 3
221			let cursor_at_1 = Cursor::new(SourceOffset(1), Token::SPACE); // ends at 2, fills the gap
222			ordered_sink.append(cursor_at_0);
223			ordered_sink.append(cursor_at_2);
224			ordered_sink.append(cursor_at_1);
225			// Avoid flushing as they should be emitted immediately
226		}
227		assert_eq!(output.len(), 3);
228		assert_eq!(output[0].span().start(), SourceOffset(0));
229		assert_eq!(output[1].span().start(), SourceOffset(1));
230		assert_eq!(output[2].span().start(), SourceOffset(2));
231	}
232
233	#[test]
234	fn test_sequential() {
235		use crate::{SourceOffset, Token};
236		let alloc = Arena::default();
237		let mut output = ArenaVec::new_in(&alloc);
238		{
239			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
240			let cursor1 = Cursor::new(SourceOffset(0), Token::SPACE);
241			let cursor2 = Cursor::new(SourceOffset(1), Token::SPACE);
242			let cursor3 = Cursor::new(SourceOffset(2), Token::SPACE);
243			ordered_sink.append(cursor1);
244			ordered_sink.append(cursor2);
245			ordered_sink.append(cursor3);
246			// Avoid flushing as they should be emitted immediately
247		}
248		assert_eq!(output.len(), 3);
249		assert_eq!(output[0].span().start(), SourceOffset(0));
250		assert_eq!(output[1].span().start(), SourceOffset(1));
251		assert_eq!(output[2].span().start(), SourceOffset(2));
252	}
253
254	#[test]
255	fn test_varied_order() {
256		use crate::{SourceOffset, Token};
257		let alloc = Arena::default();
258		let mut output = ArenaVec::new_in(&alloc);
259		{
260			let mut ordered_sink = CursorOrderedSink::new(&alloc, &mut output);
261			let cursor_at_4 = Cursor::new(SourceOffset(4), Token::SPACE); // ends at 5
262			let cursor_at_0 = Cursor::new(SourceOffset(0), Token::SPACE); // ends at 1
263			let cursor_at_6 = Cursor::new(SourceOffset(6), Token::SPACE); // ends at 7
264			let cursor_at_2 = Cursor::new(SourceOffset(2), Token::SPACE); // ends at 3
265			let cursor_at_1 = Cursor::new(SourceOffset(1), Token::SPACE); // ends at 2
266			let cursor_at_3 = Cursor::new(SourceOffset(3), Token::SPACE); // ends at 4
267			let cursor_at_5 = Cursor::new(SourceOffset(5), Token::SPACE); // ends at 6
268			ordered_sink.append(cursor_at_4);
269			ordered_sink.append(cursor_at_0);
270			ordered_sink.append(cursor_at_6);
271			ordered_sink.append(cursor_at_2);
272			ordered_sink.append(cursor_at_1);
273			ordered_sink.append(cursor_at_3);
274			ordered_sink.append(cursor_at_5);
275			// Avoid flushing as they should be emitted immediately
276		}
277		assert_eq!(output.len(), 7);
278		for i in 0..7 {
279			assert_eq!(output[i].span().start(), SourceOffset(i as u32));
280		}
281	}
282}
css_parse/cursor_ordered_sink.rs

css_parse/
cursor_ordered_sink.rs
