Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/fmt/parse.rs

23.0 KiB, 1 run

created by r1870400018:11632, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Structural parser for Rust.
2//!
3//! Converts a flat token stream into a concrete syntax tree by
4//! recognising brackets, keywords, and their nesting structure.
5//! This is a lightweight "structural" parser — it tracks bracket
6//! depth and keyword patterns rather than implementing a full
7//! grammar. This is enough for formatting decisions.
8//!
9
10use crate::fmt::cst::{
11 CstChild,
12 CstNode,
13 ChildRole,
14 NodeKind,
15 Span,
16 Token,
17 TokenKind,
18};
19
20use oxedyne_fe2o3_core::prelude::*;
21
22
23/// Parse a Rust token stream into a CST.
24pub fn parse_rust(tokens: Vec<Token>) -> Outcome<CstNode> {
25 let span = file_span(&tokens);
26 let mut parser = Parser::new(tokens);
27 let children = parser.parse_items();
28 Ok(CstNode {
29 kind: NodeKind::SourceFile,
30 children,
31 span,
32 })
33}
34
35/// Parser state.
36struct Parser {
37 tokens: Vec<Token>,
38 pos: usize,
39}
40
41impl Parser {
42 fn new(tokens: Vec<Token>) -> Self {
43 Self { tokens, pos: 0 }
44 }
45
46 /// Peek at the current token without consuming.
47 fn peek(&self) -> &Token {
48 &self.tokens[self.pos.min(self.tokens.len() - 1)]
49 }
50
51 /// Whether we have reached EOF.
52 fn at_eof(&self) -> bool {
53 self.pos >= self.tokens.len()
54 || matches!(self.peek().kind, TokenKind::Eof)
55 }
56
57 /// Consume the current token and return it.
58 fn bump(&mut self) -> Token {
59 let tok = self.tokens[self.pos].clone();
60 self.pos += 1;
61 tok
62 }
63
64 /// Check if the current token is a specific keyword.
65 fn at_keyword(&self, kw: &str) -> bool {
66 matches!(&self.peek().kind, TokenKind::Keyword(k) if k == kw)
67 }
68
69 /// Check if the current token is a specific punctuation character.
70 fn at_punct(&self, ch: char) -> bool {
71 matches!(&self.peek().kind, TokenKind::Punct(c) if *c == ch)
72 }
73
74 /// Peek ahead by n tokens.
75 fn peek_ahead(&self, n: usize) -> &Token {
76 let idx = (self.pos + n).min(self.tokens.len() - 1);
77 &self.tokens[idx]
78 }
79
80 // ── Top-level parsing ────────────────────────────────────
81
82 /// Parse a sequence of top-level items.
83 fn parse_items(&mut self) -> Vec<CstChild> {
84 let mut children = Vec::new();
85 while !self.at_eof() {
86 children.extend(self.parse_item());
87 }
88 children
89 }
90
91 /// Parse a single item. Returns one or more CstChild entries
92 /// (an item may be preceded by attributes/doc comments).
93 fn parse_item(&mut self) -> Vec<CstChild> {
94 // Collect doc comments and attributes.
95 let mut parts: Vec<CstChild> = Vec::new();
96
97 // Leading doc comments.
98 while matches!(self.peek().kind, TokenKind::DocComment(_)) {
99 parts.push(CstChild::Token(self.bump()));
100 }
101
102 // Attributes.
103 while matches!(self.peek().kind, TokenKind::Attribute) {
104 parts.push(CstChild::Token(self.bump()));
105 }
106
107 // Detect item kind by keyword.
108 let kind = match &self.peek().kind {
109 TokenKind::Keyword(k) => match k.as_str() {
110 "fn" => Some(NodeKind::FnDef),
111 "pub" => return self.parse_pub_item(parts),
112 "struct" => Some(NodeKind::StructDef),
113 "enum" => Some(NodeKind::EnumDef),
114 "trait" => Some(NodeKind::TraitDef),
115 "impl" => Some(NodeKind::ImplBlock),
116 "use" => Some(NodeKind::UseDecl),
117 "mod" => Some(NodeKind::ModDecl),
118 "type" => Some(NodeKind::TypeAlias),
119 "const" | "static" => Some(NodeKind::ConstItem),
120 "let" => Some(NodeKind::LetBinding),
121 _ => None,
122 },
123 _ => None,
124 };
125
126 match kind {
127 Some(NodeKind::FnDef) => {
128 let node = self.parse_fn_def(&mut parts);
129 parts.push(CstChild::Node { role: ChildRole::Misc, node });
130 parts
131 }
132 Some(NodeKind::StructDef) => {
133 let node = self.parse_struct_def(&mut parts);
134 parts.push(CstChild::Node { role: ChildRole::Misc, node });
135 parts
136 }
137 Some(NodeKind::EnumDef) => {
138 let node = self.parse_enum_def(&mut parts);
139 parts.push(CstChild::Node { role: ChildRole::Misc, node });
140 parts
141 }
142 Some(NodeKind::ImplBlock) => {
143 let node = self.parse_impl_block(&mut parts);
144 parts.push(CstChild::Node { role: ChildRole::Misc, node });
145 parts
146 }
147 Some(NodeKind::UseDecl) => {
148 let node = self.parse_use_decl();
149 parts.push(CstChild::Node { role: ChildRole::Misc, node });
150 parts
151 }
152 Some(nk) => {
153 // Generic: consume to next semicolon or braced block.
154 let node = self.parse_generic_item(nk);
155 parts.push(CstChild::Node { role: ChildRole::Misc, node });
156 parts
157 }
158 None => {
159 // Unknown token — emit verbatim.
160 parts.push(CstChild::Token(self.bump()));
161 parts
162 }
163 }
164 }
165
166 /// Handle `pub` visibility qualifier then delegate.
167 fn parse_pub_item(&mut self, mut parts: Vec<CstChild>) -> Vec<CstChild> {
168 // Consume `pub`.
169 parts.push(CstChild::Token(self.bump()));
170 // Consume optional `(crate)` / `(super)` / `(in path)`.
171 if self.at_punct('(') {
172 parts.push(CstChild::Token(self.bump())); // (
173 while !self.at_eof() && !self.at_punct(')') {
174 parts.push(CstChild::Token(self.bump()));
175 }
176 if self.at_punct(')') {
177 parts.push(CstChild::Token(self.bump())); // )
178 }
179 }
180 // Now delegate to parse_item for the actual item.
181 parts.extend(self.parse_item());
182 parts
183 }
184
185 // ── Function definition ──────────────────────────────────
186
187 fn parse_fn_def(&mut self, _attrs: &mut Vec<CstChild>) -> CstNode {
188 let start = self.peek().span.start;
189 let mut children = Vec::new();
190
191 // `fn` keyword.
192 children.push(CstChild::Token(self.bump()));
193
194 // Name.
195 if !self.at_eof() && matches!(self.peek().kind, TokenKind::Ident) {
196 children.push(CstChild::Token(self.bump()));
197 }
198
199 // Optional generic params <...>.
200 if self.at_punct('<') {
201 let generics = self.parse_angle_bracketed();
202 children.push(CstChild::Node {
203 role: ChildRole::Generics,
204 node: generics,
205 });
206 }
207
208 // Parameter list (...).
209 if self.at_punct('(') {
210 let params = self.parse_paren_list(NodeKind::ParamList);
211 children.push(CstChild::Node {
212 role: ChildRole::Params,
213 node: params,
214 });
215 }
216
217 // Return type: -> Type.
218 if matches!(self.peek().kind, TokenKind::Operator(ref op) if op == "->") {
219 let mut ret_children = Vec::new();
220 ret_children.push(CstChild::Token(self.bump())); // ->
221 // Consume type tokens until `{`, `where`, or `;`.
222 while !self.at_eof() {
223 if self.at_punct('{') || self.at_punct(';')
224 || self.at_keyword("where")
225 {
226 break;
227 }
228 ret_children.push(CstChild::Token(self.bump()));
229 }
230 children.push(CstChild::Node {
231 role: ChildRole::ReturnType,
232 node: CstNode {
233 kind: NodeKind::TypeExpr,
234 children: ret_children,
235 span: Span::default(),
236 },
237 });
238 }
239
240 // Where clause.
241 if self.at_keyword("where") {
242 let wh = self.parse_where_clause();
243 children.push(CstChild::Node {
244 role: ChildRole::Where,
245 node: wh,
246 });
247 }
248
249 // Body { ... } or semicolon.
250 if self.at_punct('{') {
251 let body = self.parse_braced_block();
252 children.push(CstChild::Node {
253 role: ChildRole::Body,
254 node: body,
255 });
256 } else if self.at_punct(';') {
257 children.push(CstChild::Token(self.bump()));
258 }
259
260 let end = self.prev_end();
261 CstNode {
262 kind: NodeKind::FnDef,
263 children,
264 span: Span { start, end },
265 }
266 }
267
268 // ── Struct definition ────────────────────────────────────
269
270 fn parse_struct_def(&mut self, _attrs: &mut Vec<CstChild>) -> CstNode {
271 let start = self.peek().span.start;
272 let mut children = Vec::new();
273
274 // `struct` keyword.
275 children.push(CstChild::Token(self.bump()));
276
277 // Name.
278 if !self.at_eof() && matches!(self.peek().kind, TokenKind::Ident) {
279 children.push(CstChild::Token(self.bump()));
280 }
281
282 // Optional generics.
283 if self.at_punct('<') {
284 let generics = self.parse_angle_bracketed();
285 children.push(CstChild::Node {
286 role: ChildRole::Generics,
287 node: generics,
288 });
289 }
290
291 // Where clause.
292 if self.at_keyword("where") {
293 let wh = self.parse_where_clause();
294 children.push(CstChild::Node {
295 role: ChildRole::Where,
296 node: wh,
297 });
298 }
299
300 // Body { ... } or tuple struct (...) or unit struct ;.
301 if self.at_punct('{') {
302 let body = self.parse_braced_block();
303 children.push(CstChild::Node {
304 role: ChildRole::Body,
305 node: body,
306 });
307 } else if self.at_punct('(') {
308 let body = self.parse_paren_list(NodeKind::ParamList);
309 children.push(CstChild::Node {
310 role: ChildRole::Body,
311 node: body,
312 });
313 if self.at_punct(';') {
314 children.push(CstChild::Token(self.bump()));
315 }
316 } else if self.at_punct(';') {
317 children.push(CstChild::Token(self.bump()));
318 }
319
320 let end = self.prev_end();
321 CstNode {
322 kind: NodeKind::StructDef,
323 children,
324 span: Span { start, end },
325 }
326 }
327
328 // ── Enum definition ──────────────────────────────────────
329
330 fn parse_enum_def(&mut self, _attrs: &mut Vec<CstChild>) -> CstNode {
331 let start = self.peek().span.start;
332 let mut children = Vec::new();
333
334 children.push(CstChild::Token(self.bump())); // enum
335
336 if !self.at_eof() && matches!(self.peek().kind, TokenKind::Ident) {
337 children.push(CstChild::Token(self.bump())); // name
338 }
339
340 if self.at_punct('<') {
341 let generics = self.parse_angle_bracketed();
342 children.push(CstChild::Node {
343 role: ChildRole::Generics,
344 node: generics,
345 });
346 }
347
348 if self.at_keyword("where") {
349 let wh = self.parse_where_clause();
350 children.push(CstChild::Node {
351 role: ChildRole::Where,
352 node: wh,
353 });
354 }
355
356 if self.at_punct('{') {
357 let body = self.parse_braced_block();
358 children.push(CstChild::Node {
359 role: ChildRole::Body,
360 node: body,
361 });
362 }
363
364 let end = self.prev_end();
365 CstNode {
366 kind: NodeKind::EnumDef,
367 children,
368 span: Span { start, end },
369 }
370 }
371
372 // ── Impl block ───────────────────────────────────────────
373
374 fn parse_impl_block(&mut self, _attrs: &mut Vec<CstChild>) -> CstNode {
375 let start = self.peek().span.start;
376 let mut children = Vec::new();
377
378 children.push(CstChild::Token(self.bump())); // impl
379
380 // Consume tokens until `{`.
381 while !self.at_eof() && !self.at_punct('{') {
382 if self.at_keyword("where") {
383 let wh = self.parse_where_clause();
384 children.push(CstChild::Node {
385 role: ChildRole::Where,
386 node: wh,
387 });
388 } else {
389 children.push(CstChild::Token(self.bump()));
390 }
391 }
392
393 if self.at_punct('{') {
394 let body = self.parse_item_block();
395 children.push(CstChild::Node {
396 role: ChildRole::Body,
397 node: body,
398 });
399 }
400
401 let end = self.prev_end();
402 CstNode {
403 kind: NodeKind::ImplBlock,
404 children,
405 span: Span { start, end },
406 }
407 }
408
409 // ── Use declaration ──────────────────────────────────────
410
411 fn parse_use_decl(&mut self) -> CstNode {
412 let start = self.peek().span.start;
413 let mut children = Vec::new();
414
415 children.push(CstChild::Token(self.bump())); // use
416
417 // Consume until semicolon, handling nested braces.
418 let mut depth = 0usize;
419 while !self.at_eof() {
420 if self.at_punct('{') { depth += 1; }
421 if self.at_punct('}') {
422 if depth > 0 { depth -= 1; }
423 }
424 let is_semi = self.at_punct(';') && depth == 0;
425 children.push(CstChild::Token(self.bump()));
426 if is_semi { break; }
427 }
428
429 let end = self.prev_end();
430 CstNode {
431 kind: NodeKind::UseDecl,
432 children,
433 span: Span { start, end },
434 }
435 }
436
437 // ── Generic item (consumes to `;` or `{}`) ───────────────
438
439 fn parse_generic_item(&mut self, kind: NodeKind) -> CstNode {
440 let start = self.peek().span.start;
441 let mut children = Vec::new();
442
443 while !self.at_eof() {
444 if self.at_punct('{') {
445 let body = self.parse_braced_block();
446 children.push(CstChild::Node {
447 role: ChildRole::Body,
448 node: body,
449 });
450 break;
451 }
452 if self.at_punct(';') {
453 children.push(CstChild::Token(self.bump()));
454 break;
455 }
456 children.push(CstChild::Token(self.bump()));
457 }
458
459 let end = self.prev_end();
460 CstNode { kind, children, span: Span { start, end } }
461 }
462
463 // ── Bracketed helpers ────────────────────────────────────
464
465 /// Parse a braced block that contains items (fn, type, const,
466 /// etc.). Used for impl and trait blocks. Recursively parses
467 /// each item so they get structured CST nodes.
468 fn parse_item_block(&mut self) -> CstNode {
469 let start = self.peek().span.start;
470 let mut children = Vec::new();
471
472 children.push(CstChild::Token(self.bump())); // {
473
474 // Parse items until `}`.
475 while !self.at_eof() && !self.at_punct('}') {
476 let item_children = self.parse_item();
477 children.extend(item_children);
478 }
479
480 if self.at_punct('}') {
481 children.push(CstChild::Token(self.bump())); // }
482 }
483
484 let end = self.prev_end();
485 CstNode {
486 kind: NodeKind::Block,
487 children,
488 span: Span { start, end },
489 }
490 }
491
492 /// Parse a braced block `{ ... }`, preserving all contents.
493 fn parse_braced_block(&mut self) -> CstNode {
494 let start = self.peek().span.start;
495 let mut children = Vec::new();
496
497 // Opening brace.
498 children.push(CstChild::Token(self.bump())); // {
499
500 let mut depth = 1usize;
501 while !self.at_eof() && depth > 0 {
502 if self.at_punct('{') { depth += 1; }
503 if self.at_punct('}') { depth -= 1; }
504 if depth == 0 {
505 children.push(CstChild::Token(self.bump())); // closing }
506 break;
507 }
508 children.push(CstChild::Token(self.bump()));
509 }
510
511 let end = self.prev_end();
512 CstNode {
513 kind: NodeKind::Block,
514 children,
515 span: Span { start, end },
516 }
517 }
518
519 /// Parse a parenthesised list `( ... )`.
520 fn parse_paren_list(&mut self, kind: NodeKind) -> CstNode {
521 let start = self.peek().span.start;
522 let mut children = Vec::new();
523
524 children.push(CstChild::Token(self.bump())); // (
525
526 let mut depth = 1usize;
527 while !self.at_eof() && depth > 0 {
528 if self.at_punct('(') { depth += 1; }
529 if self.at_punct(')') { depth -= 1; }
530 if depth == 0 {
531 children.push(CstChild::Token(self.bump())); // closing )
532 break;
533 }
534 children.push(CstChild::Token(self.bump()));
535 }
536
537 let end = self.prev_end();
538 CstNode { kind, children, span: Span { start, end } }
539 }
540
541 /// Parse angle-bracketed generics `< ... >`.
542 fn parse_angle_bracketed(&mut self) -> CstNode {
543 let start = self.peek().span.start;
544 let mut children = Vec::new();
545
546 children.push(CstChild::Token(self.bump())); // <
547
548 let mut depth = 1usize;
549 while !self.at_eof() && depth > 0 {
550 if self.at_punct('<') { depth += 1; }
551 if self.at_punct('>') { depth -= 1; }
552 if depth == 0 {
553 children.push(CstChild::Token(self.bump())); // closing >
554 break;
555 }
556 children.push(CstChild::Token(self.bump()));
557 }
558
559 let end = self.prev_end();
560 CstNode {
561 kind: NodeKind::GenericParams,
562 children,
563 span: Span { start, end },
564 }
565 }
566
567 /// Parse a where clause: `where P1, P2, ... `.
568 /// Consumed until `{` or `;` is encountered.
569 fn parse_where_clause(&mut self) -> CstNode {
570 let start = self.peek().span.start;
571 let mut children = Vec::new();
572
573 children.push(CstChild::Token(self.bump())); // where
574
575 while !self.at_eof() {
576 if self.at_punct('{') || self.at_punct(';') {
577 break;
578 }
579 children.push(CstChild::Token(self.bump()));
580 }
581
582 let end = self.prev_end();
583 CstNode {
584 kind: NodeKind::WhereClause,
585 children,
586 span: Span { start, end },
587 }
588 }
589
590 /// End position of the previously consumed token.
591 fn prev_end(&self) -> usize {
592 if self.pos > 0 {
593 self.tokens[self.pos - 1].span.end
594 } else {
595 0
596 }
597 }
598}
599
600/// Compute the span covering all tokens.
601fn file_span(tokens: &[Token]) -> Span {
602 if tokens.is_empty() {
603 return Span::default();
604 }
605 let start = tokens.first().map(|t| t.span.start).unwrap_or(0);
606 let end = tokens.last().map(|t| t.span.end).unwrap_or(0);
607 Span { start, end }
608}
609
610
611#[cfg(test)]
612mod tests {
613 use super::*;
614 use crate::fmt::lex;
615
616 fn parse(src: &str) -> CstNode {
617 let lang = lex::rust_tokens();
618 let tokens = lex::lex(src, &lang).expect("lex failed");
619 parse_rust(tokens).expect("parse failed")
620 }
621
622 fn count_nodes(node: &CstNode) -> usize {
623 let mut n = 1;
624 for child in &node.children {
625 if let CstChild::Node { node: ref inner, .. } = child {
626 n += count_nodes(inner);
627 }
628 }
629 n
630 }
631
632 #[test]
633 fn test_parse_fn_def() {
634 let cst = parse("fn foo(x: u32) -> bool { true }");
635 assert_eq!(cst.kind, NodeKind::SourceFile);
636 // Should have a FnDef child node.
637 let fn_node = cst.children.iter().find_map(|c| {
638 if let CstChild::Node { node, .. } = c {
639 if node.kind == NodeKind::FnDef { return Some(node); }
640 }
641 None
642 });
643 assert!(fn_node.is_some(), "expected FnDef node");
644 let fn_node = fn_node.expect("checked");
645 // Should have Params and ReturnType and Body children.
646 let has_params = fn_node.children.iter().any(|c| matches!(c,
647 CstChild::Node { role: ChildRole::Params, .. }));
648 let has_ret = fn_node.children.iter().any(|c| matches!(c,
649 CstChild::Node { role: ChildRole::ReturnType, .. }));
650 let has_body = fn_node.children.iter().any(|c| matches!(c,
651 CstChild::Node { role: ChildRole::Body, .. }));
652 assert!(has_params, "expected Params");
653 assert!(has_ret, "expected ReturnType");
654 assert!(has_body, "expected Body");
655 }
656
657 #[test]
658 fn test_parse_struct() {
659 let cst = parse("pub struct Foo { x: u32, y: u64, }");
660 let struct_node = cst.children.iter().find_map(|c| {
661 if let CstChild::Node { node, .. } = c {
662 if node.kind == NodeKind::StructDef { return Some(node); }
663 }
664 None
665 });
666 assert!(struct_node.is_some(), "expected StructDef node");
667 }
668
669 #[test]
670 fn test_parse_impl() {
671 let cst = parse("impl Foo { fn bar(&self) {} }");
672 let impl_node = cst.children.iter().find_map(|c| {
673 if let CstChild::Node { node, .. } = c {
674 if node.kind == NodeKind::ImplBlock { return Some(node); }
675 }
676 None
677 });
678 assert!(impl_node.is_some(), "expected ImplBlock node");
679 }
680
681 #[test]
682 fn test_parse_use() {
683 let cst = parse("use std::collections::HashMap;");
684 let use_node = cst.children.iter().find_map(|c| {
685 if let CstChild::Node { node, .. } = c {
686 if node.kind == NodeKind::UseDecl { return Some(node); }
687 }
688 None
689 });
690 assert!(use_node.is_some(), "expected UseDecl node");
691 }
692
693 #[test]
694 fn test_parse_fn_with_where() {
695 let cst = parse("fn foo<T>(x: T) -> T where T: Clone { x.clone() }");
696 let fn_node = cst.children.iter().find_map(|c| {
697 if let CstChild::Node { node, .. } = c {
698 if node.kind == NodeKind::FnDef { return Some(node); }
699 }
700 None
701 });
702 assert!(fn_node.is_some());
703 let fn_node = fn_node.expect("checked");
704 let has_where = fn_node.children.iter().any(|c| matches!(c,
705 CstChild::Node { role: ChildRole::Where, .. }));
706 assert!(has_where, "expected Where clause");
707 }
708
709 #[test]
710 fn test_parse_multiple_items() {
711 let cst = parse("use std::fmt;\n\nfn main() {}\n\nstruct Foo;");
712 let node_count = count_nodes(&cst);
713 assert!(node_count >= 4, "expected at least 4 nodes, got {}", node_count);
714 }
715}