awk_rs/parser/
mod.rs

1use crate::ast::*;
2use crate::error::{Error, Result, SourceLocation};
3use crate::lexer::{Token, TokenKind};
4
5/// AWK parser using recursive descent
6pub struct Parser {
7    tokens: Vec<Token>,
8    current: usize,
9}
10
11impl Parser {
12    pub fn new(tokens: Vec<Token>) -> Self {
13        Self { tokens, current: 0 }
14    }
15
16    /// Parse a complete AWK program
17    pub fn parse(&mut self) -> Result<Program> {
18        let mut program = Program::new();
19
20        self.skip_newlines();
21
22        while !self.is_at_end() {
23            // Check for function definition
24            if self.check(&TokenKind::Function) {
25                program.functions.push(self.parse_function()?);
26            } else {
27                program.rules.push(self.parse_rule()?);
28            }
29            self.skip_newlines();
30        }
31
32        Ok(program)
33    }
34
35    /// Parse a function definition
36    fn parse_function(&mut self) -> Result<FunctionDef> {
37        let location = self.current_location();
38        self.expect(&TokenKind::Function)?;
39
40        let name = self.expect_identifier()?;
41        self.expect(&TokenKind::LeftParen)?;
42
43        let mut params = Vec::new();
44        if !self.check(&TokenKind::RightParen) {
45            params.push(self.expect_identifier()?);
46            while self.match_token(&TokenKind::Comma) {
47                params.push(self.expect_identifier()?);
48            }
49        }
50        self.expect(&TokenKind::RightParen)?;
51        self.skip_newlines();
52
53        let body = self.parse_block()?;
54
55        Ok(FunctionDef {
56            name,
57            params,
58            body,
59            location,
60        })
61    }
62
63    /// Parse a pattern-action rule
64    fn parse_rule(&mut self) -> Result<Rule> {
65        let location = self.current_location();
66
67        // Check for BEGIN/END/BEGINFILE/ENDFILE
68        if self.check(&TokenKind::Begin) {
69            self.advance();
70            self.skip_newlines();
71            let action = Some(self.parse_block()?);
72            return Ok(Rule {
73                pattern: Some(Pattern::Begin),
74                action,
75                location,
76            });
77        }
78
79        if self.check(&TokenKind::End) {
80            self.advance();
81            self.skip_newlines();
82            let action = Some(self.parse_block()?);
83            return Ok(Rule {
84                pattern: Some(Pattern::End),
85                action,
86                location,
87            });
88        }
89
90        if self.check(&TokenKind::BeginFile) {
91            self.advance();
92            self.skip_newlines();
93            let action = Some(self.parse_block()?);
94            return Ok(Rule {
95                pattern: Some(Pattern::BeginFile),
96                action,
97                location,
98            });
99        }
100
101        if self.check(&TokenKind::EndFile) {
102            self.advance();
103            self.skip_newlines();
104            let action = Some(self.parse_block()?);
105            return Ok(Rule {
106                pattern: Some(Pattern::EndFile),
107                action,
108                location,
109            });
110        }
111
112        // Check for action-only rule (just a block)
113        if self.check(&TokenKind::LeftBrace) {
114            let action = Some(self.parse_block()?);
115            return Ok(Rule {
116                pattern: None,
117                action,
118                location,
119            });
120        }
121
122        // Parse pattern
123        let pattern = Some(self.parse_pattern()?);
124        self.skip_newlines();
125
126        // Optional action
127        let action = if self.check(&TokenKind::LeftBrace) {
128            Some(self.parse_block()?)
129        } else {
130            None
131        };
132
133        Ok(Rule {
134            pattern,
135            action,
136            location,
137        })
138    }
139
140    /// Parse a pattern (expression or regex)
141    fn parse_pattern(&mut self) -> Result<Pattern> {
142        // Check for regex pattern
143        if let Some(TokenKind::Regex(pattern)) = self.peek_kind() {
144            let pattern = pattern.clone();
145            self.advance();
146
147            // Check for range pattern
148            if self.match_token(&TokenKind::Comma) {
149                self.skip_newlines();
150                let end = self.parse_pattern()?;
151                return Ok(Pattern::Range {
152                    start: Box::new(Pattern::Regex(pattern)),
153                    end: Box::new(end),
154                });
155            }
156
157            return Ok(Pattern::Regex(pattern));
158        }
159
160        // Parse as expression pattern
161        let expr = self.parse_expression()?;
162
163        // Check for range pattern
164        if self.match_token(&TokenKind::Comma) {
165            self.skip_newlines();
166            let end = self.parse_pattern()?;
167            return Ok(Pattern::Range {
168                start: Box::new(Pattern::Expr(expr)),
169                end: Box::new(end),
170            });
171        }
172
173        Ok(Pattern::Expr(expr))
174    }
175
176    /// Parse a block { ... }
177    fn parse_block(&mut self) -> Result<Block> {
178        let location = self.current_location();
179        self.expect(&TokenKind::LeftBrace)?;
180        self.skip_newlines();
181
182        let mut statements = Vec::new();
183
184        while !self.check(&TokenKind::RightBrace) && !self.is_at_end() {
185            statements.push(self.parse_statement()?);
186            self.skip_terminators();
187        }
188
189        self.expect(&TokenKind::RightBrace)?;
190
191        Ok(Block::new(statements, location))
192    }
193
194    /// Parse a single statement
195    fn parse_statement(&mut self) -> Result<Stmt> {
196        self.skip_newlines();
197
198        let location = self.current_location();
199
200        // Empty statement
201        if self.check(&TokenKind::Semicolon) {
202            self.advance();
203            return Ok(Stmt::Empty);
204        }
205
206        // Block
207        if self.check(&TokenKind::LeftBrace) {
208            return Ok(Stmt::Block(self.parse_block()?));
209        }
210
211        // If statement
212        if self.match_token(&TokenKind::If) {
213            return self.parse_if_statement(location);
214        }
215
216        // While statement
217        if self.match_token(&TokenKind::While) {
218            return self.parse_while_statement(location);
219        }
220
221        // For statement
222        if self.match_token(&TokenKind::For) {
223            return self.parse_for_statement(location);
224        }
225
226        // Do-while statement
227        if self.match_token(&TokenKind::Do) {
228            return self.parse_do_while_statement(location);
229        }
230
231        // Break
232        if self.match_token(&TokenKind::Break) {
233            return Ok(Stmt::Break { location });
234        }
235
236        // Continue
237        if self.match_token(&TokenKind::Continue) {
238            return Ok(Stmt::Continue { location });
239        }
240
241        // Next
242        if self.match_token(&TokenKind::Next) {
243            return Ok(Stmt::Next { location });
244        }
245
246        // Nextfile
247        if self.match_token(&TokenKind::Nextfile) {
248            return Ok(Stmt::Nextfile { location });
249        }
250
251        // Exit
252        if self.match_token(&TokenKind::Exit) {
253            let code = if self.can_start_expression() {
254                Some(self.parse_expression()?)
255            } else {
256                None
257            };
258            return Ok(Stmt::Exit { code, location });
259        }
260
261        // Return
262        if self.match_token(&TokenKind::Return) {
263            let value = if self.can_start_expression() {
264                Some(self.parse_expression()?)
265            } else {
266                None
267            };
268            return Ok(Stmt::Return { value, location });
269        }
270
271        // Delete
272        if self.match_token(&TokenKind::Delete) {
273            let name = self.expect_identifier()?;
274
275            // Check if there's an index (delete array[i]) or not (delete array)
276            let indices = if self.match_token(&TokenKind::LeftBracket) {
277                let mut indices = vec![self.parse_expression()?];
278                while self.match_token(&TokenKind::Comma) {
279                    indices.push(self.parse_expression()?);
280                }
281                self.expect(&TokenKind::RightBracket)?;
282                indices
283            } else {
284                // delete array (entire array)
285                Vec::new()
286            };
287
288            return Ok(Stmt::Delete {
289                array: name,
290                index: indices,
291                location,
292            });
293        }
294
295        // Print statement
296        if self.match_token(&TokenKind::Print) {
297            return self.parse_print_statement(location);
298        }
299
300        // Printf statement
301        if self.match_token(&TokenKind::Printf) {
302            return self.parse_printf_statement(location);
303        }
304
305        // Expression statement
306        let expr = self.parse_expression()?;
307        Ok(Stmt::Expr(expr))
308    }
309
310    fn parse_if_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
311        self.expect(&TokenKind::LeftParen)?;
312        let condition = self.parse_expression()?;
313        self.expect(&TokenKind::RightParen)?;
314        self.skip_newlines();
315
316        let then_branch = Box::new(self.parse_statement()?);
317
318        // Skip terminators (semicolons and newlines) before checking for else
319        self.skip_terminators();
320        let else_branch = if self.match_token(&TokenKind::Else) {
321            self.skip_newlines();
322            Some(Box::new(self.parse_statement()?))
323        } else {
324            None
325        };
326
327        Ok(Stmt::If {
328            condition,
329            then_branch,
330            else_branch,
331            location,
332        })
333    }
334
335    fn parse_while_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
336        self.expect(&TokenKind::LeftParen)?;
337        let condition = self.parse_expression()?;
338        self.expect(&TokenKind::RightParen)?;
339        self.skip_newlines();
340
341        let body = Box::new(self.parse_statement()?);
342
343        Ok(Stmt::While {
344            condition,
345            body,
346            location,
347        })
348    }
349
350    fn parse_for_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
351        self.expect(&TokenKind::LeftParen)?;
352
353        // Check for for-in loop: for (var in array)
354        if let Some(TokenKind::Identifier(name)) = self.peek_kind() {
355            let name = name.clone();
356            let saved_pos = self.current;
357            self.advance();
358
359            if self.match_token(&TokenKind::In) {
360                let array = self.expect_identifier()?;
361                self.expect(&TokenKind::RightParen)?;
362                self.skip_newlines();
363                let body = Box::new(self.parse_statement()?);
364
365                return Ok(Stmt::ForIn {
366                    var: name,
367                    array,
368                    body,
369                    location,
370                });
371            }
372
373            // Not a for-in, backtrack
374            self.current = saved_pos;
375        }
376
377        // C-style for loop
378        let init = if !self.check(&TokenKind::Semicolon) {
379            Some(Box::new(self.parse_statement()?))
380        } else {
381            None
382        };
383        self.expect(&TokenKind::Semicolon)?;
384
385        let condition = if !self.check(&TokenKind::Semicolon) {
386            Some(self.parse_expression()?)
387        } else {
388            None
389        };
390        self.expect(&TokenKind::Semicolon)?;
391
392        let update = if !self.check(&TokenKind::RightParen) {
393            Some(self.parse_expression()?)
394        } else {
395            None
396        };
397        self.expect(&TokenKind::RightParen)?;
398        self.skip_newlines();
399
400        let body = Box::new(self.parse_statement()?);
401
402        Ok(Stmt::For {
403            init,
404            condition,
405            update,
406            body,
407            location,
408        })
409    }
410
411    fn parse_do_while_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
412        self.skip_newlines();
413        let body = Box::new(self.parse_statement()?);
414        self.skip_newlines();
415        self.expect(&TokenKind::While)?;
416        self.expect(&TokenKind::LeftParen)?;
417        let condition = self.parse_expression()?;
418        self.expect(&TokenKind::RightParen)?;
419
420        Ok(Stmt::DoWhile {
421            body,
422            condition,
423            location,
424        })
425    }
426
427    fn parse_print_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
428        let mut args = Vec::new();
429
430        // Check for arguments (print without args prints $0)
431        if self.can_start_expression()
432            && !self.check(&TokenKind::Greater)
433            && !self.check(&TokenKind::Append)
434            && !self.check(&TokenKind::Pipe)
435        {
436            args.push(self.parse_print_arg()?);
437            while self.match_token(&TokenKind::Comma) {
438                args.push(self.parse_print_arg()?);
439            }
440        }
441
442        // Check for output redirection
443        let output = self.parse_output_redirect()?;
444
445        Ok(Stmt::Print {
446            args,
447            output,
448            location,
449        })
450    }
451
452    fn parse_printf_statement(&mut self, location: SourceLocation) -> Result<Stmt> {
453        let format = self.parse_print_arg()?;
454        let mut args = Vec::new();
455
456        while self.match_token(&TokenKind::Comma) {
457            args.push(self.parse_print_arg()?);
458        }
459
460        let output = self.parse_output_redirect()?;
461
462        Ok(Stmt::Printf {
463            format,
464            args,
465            output,
466            location,
467        })
468    }
469
470    fn parse_print_arg(&mut self) -> Result<Expr> {
471        // Print arguments don't include comparison operators with > at the top level
472        // because > is used for output redirection. We parse up to concatenation level.
473        self.parse_print_ternary()
474    }
475
476    fn parse_print_ternary(&mut self) -> Result<Expr> {
477        let expr = self.parse_print_or()?;
478
479        if self.match_token(&TokenKind::Question) {
480            let location = self.current_location();
481            let then_expr = self.parse_print_ternary()?;
482            self.expect(&TokenKind::Colon)?;
483            let else_expr = self.parse_print_ternary()?;
484            return Ok(Expr::Ternary {
485                condition: Box::new(expr),
486                then_expr: Box::new(then_expr),
487                else_expr: Box::new(else_expr),
488                location,
489            });
490        }
491
492        Ok(expr)
493    }
494
495    fn parse_print_or(&mut self) -> Result<Expr> {
496        let mut expr = self.parse_print_and()?;
497
498        while self.match_token(&TokenKind::Or) {
499            let location = self.current_location();
500            let right = self.parse_print_and()?;
501            expr = Expr::Binary {
502                left: Box::new(expr),
503                op: BinaryOp::Or,
504                right: Box::new(right),
505                location,
506            };
507        }
508
509        Ok(expr)
510    }
511
512    fn parse_print_and(&mut self) -> Result<Expr> {
513        let mut expr = self.parse_print_in()?;
514
515        while self.match_token(&TokenKind::And) {
516            let location = self.current_location();
517            let right = self.parse_print_in()?;
518            expr = Expr::Binary {
519                left: Box::new(expr),
520                op: BinaryOp::And,
521                right: Box::new(right),
522                location,
523            };
524        }
525
526        Ok(expr)
527    }
528
529    fn parse_print_in(&mut self) -> Result<Expr> {
530        let expr = self.parse_print_match()?;
531
532        if self.match_token(&TokenKind::In) {
533            let location = self.current_location();
534            let array = self.expect_identifier()?;
535            return Ok(Expr::InArray {
536                key: vec![expr],
537                array,
538                location,
539            });
540        }
541
542        Ok(expr)
543    }
544
545    fn parse_print_match(&mut self) -> Result<Expr> {
546        let expr = self.parse_print_comparison()?;
547
548        let location = self.current_location();
549        if self.match_token(&TokenKind::Match) {
550            let pattern = self.parse_print_comparison()?;
551            return Ok(Expr::Match {
552                expr: Box::new(expr),
553                pattern: Box::new(pattern),
554                negated: false,
555                location,
556            });
557        }
558
559        if self.match_token(&TokenKind::NotMatch) {
560            let pattern = self.parse_print_comparison()?;
561            return Ok(Expr::Match {
562                expr: Box::new(expr),
563                pattern: Box::new(pattern),
564                negated: true,
565                location,
566            });
567        }
568
569        Ok(expr)
570    }
571
572    fn parse_print_comparison(&mut self) -> Result<Expr> {
573        let mut expr = self.parse_concat()?;
574
575        // For print args, we DON'T consume > or >> because they're used for output redirection
576        // But we DO handle >=, <, <=, ==, !=
577        loop {
578            let location = self.current_location();
579            let op = if self.match_token(&TokenKind::Less) {
580                BinaryOp::Lt
581            } else if self.match_token(&TokenKind::LessEqual) {
582                BinaryOp::Le
583            } else if self.match_token(&TokenKind::GreaterEqual) {
584                BinaryOp::Ge
585            } else if self.match_token(&TokenKind::Equal) {
586                BinaryOp::Eq
587            } else if self.match_token(&TokenKind::NotEqual) {
588                BinaryOp::Ne
589            } else {
590                // Don't consume > or >> for print arguments (used for output redirection)
591                break;
592            };
593
594            let right = self.parse_concat()?;
595            expr = Expr::Binary {
596                left: Box::new(expr),
597                op,
598                right: Box::new(right),
599                location,
600            };
601        }
602
603        Ok(expr)
604    }
605
606    fn parse_output_redirect(&mut self) -> Result<Option<OutputRedirect>> {
607        if self.match_token(&TokenKind::Greater) {
608            let target = self.parse_print_arg()?;
609            Ok(Some(OutputRedirect::Truncate(target)))
610        } else if self.match_token(&TokenKind::Append) {
611            let target = self.parse_print_arg()?;
612            Ok(Some(OutputRedirect::Append(target)))
613        } else if self.match_token(&TokenKind::Pipe) {
614            let target = self.parse_print_arg()?;
615            Ok(Some(OutputRedirect::Pipe(target)))
616        } else {
617            Ok(None)
618        }
619    }
620
621    /// Parse an expression
622    fn parse_expression(&mut self) -> Result<Expr> {
623        self.parse_assignment()
624    }
625
626    fn parse_assignment(&mut self) -> Result<Expr> {
627        let expr = self.parse_ternary()?;
628
629        // Check for assignment operators
630        let location = self.current_location();
631        let op = if self.match_token(&TokenKind::Assign) {
632            Some(AssignOp::Assign)
633        } else if self.match_token(&TokenKind::PlusAssign) {
634            Some(AssignOp::AddAssign)
635        } else if self.match_token(&TokenKind::MinusAssign) {
636            Some(AssignOp::SubAssign)
637        } else if self.match_token(&TokenKind::StarAssign) {
638            Some(AssignOp::MulAssign)
639        } else if self.match_token(&TokenKind::SlashAssign) {
640            Some(AssignOp::DivAssign)
641        } else if self.match_token(&TokenKind::PercentAssign) {
642            Some(AssignOp::ModAssign)
643        } else if self.match_token(&TokenKind::CaretAssign) {
644            Some(AssignOp::PowAssign)
645        } else {
646            None
647        };
648
649        if let Some(op) = op {
650            let value = self.parse_assignment()?;
651            return Ok(Expr::Assign {
652                target: Box::new(expr),
653                op,
654                value: Box::new(value),
655                location,
656            });
657        }
658
659        Ok(expr)
660    }
661
662    fn parse_ternary(&mut self) -> Result<Expr> {
663        let expr = self.parse_or()?;
664
665        if self.match_token(&TokenKind::Question) {
666            let location = self.current_location();
667            let then_expr = self.parse_expression()?;
668            self.expect(&TokenKind::Colon)?;
669            let else_expr = self.parse_ternary()?;
670            return Ok(Expr::Ternary {
671                condition: Box::new(expr),
672                then_expr: Box::new(then_expr),
673                else_expr: Box::new(else_expr),
674                location,
675            });
676        }
677
678        Ok(expr)
679    }
680
681    fn parse_or(&mut self) -> Result<Expr> {
682        let mut expr = self.parse_and()?;
683
684        while self.match_token(&TokenKind::Or) {
685            let location = self.current_location();
686            let right = self.parse_and()?;
687            expr = Expr::Binary {
688                left: Box::new(expr),
689                op: BinaryOp::Or,
690                right: Box::new(right),
691                location,
692            };
693        }
694
695        Ok(expr)
696    }
697
698    fn parse_and(&mut self) -> Result<Expr> {
699        let mut expr = self.parse_in()?;
700
701        while self.match_token(&TokenKind::And) {
702            let location = self.current_location();
703            let right = self.parse_in()?;
704            expr = Expr::Binary {
705                left: Box::new(expr),
706                op: BinaryOp::And,
707                right: Box::new(right),
708                location,
709            };
710        }
711
712        Ok(expr)
713    }
714
715    fn parse_in(&mut self) -> Result<Expr> {
716        let expr = self.parse_pipe_getline()?;
717
718        // Check for "in" (array membership)
719        // Format: (expr) in array or expr in array
720        if self.match_token(&TokenKind::In) {
721            let location = self.current_location();
722            let array = self.expect_identifier()?;
723            return Ok(Expr::InArray {
724                key: vec![expr],
725                array,
726                location,
727            });
728        }
729
730        Ok(expr)
731    }
732
733    /// Parses the optional target lvalue of a `getline`.
734    ///
735    /// POSIX allows the target to be any lvalue: a plain variable, an array
736    /// element (`getline a[i]`), or a field (`getline $1`). Returns `None`
737    /// when no target follows, in which case the record ($0) is set instead.
738    fn parse_getline_target(&mut self) -> Result<Option<Box<Expr>>> {
739        let location = self.current_location();
740
741        if self.check(&TokenKind::Dollar) {
742            return Ok(Some(Box::new(self.parse_field()?)));
743        }
744
745        let Some(TokenKind::Identifier(name)) = self.peek_kind() else {
746            return Ok(None);
747        };
748        let name = name.clone();
749        self.advance();
750
751        if self.match_token(&TokenKind::LeftBracket) {
752            let mut indices = vec![self.parse_expression()?];
753            while self.match_token(&TokenKind::Comma) {
754                indices.push(self.parse_expression()?);
755            }
756            self.expect(&TokenKind::RightBracket)?;
757            return Ok(Some(Box::new(Expr::ArrayAccess {
758                array: name,
759                indices,
760                location,
761            })));
762        }
763
764        Ok(Some(Box::new(Expr::Var(name, location))))
765    }
766
767    /// Handle `cmd | getline [var]` syntax
768    fn parse_pipe_getline(&mut self) -> Result<Expr> {
769        let expr = self.parse_match()?;
770
771        // Check for pipe to getline: expr | getline [var]
772        if self.check(&TokenKind::Pipe) {
773            // Look ahead to see if getline follows
774            let saved_pos = self.current;
775            self.advance(); // consume |
776
777            if self.check(&TokenKind::Getline) {
778                let location = self.current_location();
779                self.advance(); // consume getline
780
781                // Optional target lvalue
782                let var = self.parse_getline_target()?;
783
784                return Ok(Expr::Getline {
785                    var,
786                    input: Some(GetlineInput::Pipe(Box::new(expr))),
787                    location,
788                });
789            } else {
790                // Not getline, backtrack
791                self.current = saved_pos;
792            }
793        }
794
795        Ok(expr)
796    }
797
798    fn parse_match(&mut self) -> Result<Expr> {
799        let expr = self.parse_comparison()?;
800
801        let location = self.current_location();
802        if self.match_token(&TokenKind::Match) {
803            let pattern = self.parse_comparison()?;
804            return Ok(Expr::Match {
805                expr: Box::new(expr),
806                pattern: Box::new(pattern),
807                negated: false,
808                location,
809            });
810        }
811
812        if self.match_token(&TokenKind::NotMatch) {
813            let pattern = self.parse_comparison()?;
814            return Ok(Expr::Match {
815                expr: Box::new(expr),
816                pattern: Box::new(pattern),
817                negated: true,
818                location,
819            });
820        }
821
822        Ok(expr)
823    }
824
825    fn parse_comparison(&mut self) -> Result<Expr> {
826        let mut expr = self.parse_concat()?;
827
828        loop {
829            let location = self.current_location();
830            let op = if self.match_token(&TokenKind::Less) {
831                BinaryOp::Lt
832            } else if self.match_token(&TokenKind::LessEqual) {
833                BinaryOp::Le
834            } else if self.match_token(&TokenKind::Greater) {
835                BinaryOp::Gt
836            } else if self.match_token(&TokenKind::GreaterEqual) {
837                BinaryOp::Ge
838            } else if self.match_token(&TokenKind::Equal) {
839                BinaryOp::Eq
840            } else if self.match_token(&TokenKind::NotEqual) {
841                BinaryOp::Ne
842            } else {
843                break;
844            };
845
846            let right = self.parse_concat()?;
847            expr = Expr::Binary {
848                left: Box::new(expr),
849                op,
850                right: Box::new(right),
851                location,
852            };
853        }
854
855        Ok(expr)
856    }
857
858    fn parse_concat(&mut self) -> Result<Expr> {
859        let mut expr = self.parse_additive()?;
860
861        // Concatenation is implicit between adjacent expressions
862        // But we need to be careful about operators that could follow
863        while self.can_start_concat_operand() {
864            let right = self.parse_additive()?;
865            let location = expr.location();
866            expr = Expr::Binary {
867                left: Box::new(expr),
868                op: BinaryOp::Concat,
869                right: Box::new(right),
870                location,
871            };
872        }
873
874        Ok(expr)
875    }
876
877    fn can_start_concat_operand(&mut self) -> bool {
878        if let Some(kind) = self.peek_kind() {
879            matches!(
880                kind,
881                TokenKind::Number(_)
882                    | TokenKind::String(_)
883                    | TokenKind::Identifier(_)
884                    | TokenKind::Dollar
885                    | TokenKind::LeftParen
886                    | TokenKind::Not
887                    | TokenKind::Increment
888                    | TokenKind::Decrement
889            )
890        } else {
891            false
892        }
893    }
894
895    fn parse_additive(&mut self) -> Result<Expr> {
896        let mut expr = self.parse_multiplicative()?;
897
898        loop {
899            let location = self.current_location();
900            let op = if self.match_token(&TokenKind::Plus) {
901                BinaryOp::Add
902            } else if self.match_token(&TokenKind::Minus) {
903                BinaryOp::Sub
904            } else {
905                break;
906            };
907
908            let right = self.parse_multiplicative()?;
909            expr = Expr::Binary {
910                left: Box::new(expr),
911                op,
912                right: Box::new(right),
913                location,
914            };
915        }
916
917        Ok(expr)
918    }
919
920    fn parse_multiplicative(&mut self) -> Result<Expr> {
921        let mut expr = self.parse_power()?;
922
923        loop {
924            let location = self.current_location();
925            let op = if self.match_token(&TokenKind::Star) {
926                BinaryOp::Mul
927            } else if self.match_token(&TokenKind::Slash) {
928                BinaryOp::Div
929            } else if self.match_token(&TokenKind::Percent) {
930                BinaryOp::Mod
931            } else {
932                break;
933            };
934
935            let right = self.parse_power()?;
936            expr = Expr::Binary {
937                left: Box::new(expr),
938                op,
939                right: Box::new(right),
940                location,
941            };
942        }
943
944        Ok(expr)
945    }
946
947    fn parse_power(&mut self) -> Result<Expr> {
948        let expr = self.parse_unary()?;
949
950        // Exponentiation is right-associative
951        if self.match_token(&TokenKind::Caret) {
952            let location = self.current_location();
953            let right = self.parse_power()?;
954            return Ok(Expr::Binary {
955                left: Box::new(expr),
956                op: BinaryOp::Pow,
957                right: Box::new(right),
958                location,
959            });
960        }
961
962        Ok(expr)
963    }
964
965    fn parse_unary(&mut self) -> Result<Expr> {
966        let location = self.current_location();
967
968        if self.match_token(&TokenKind::Not) {
969            let operand = self.parse_unary()?;
970            return Ok(Expr::Unary {
971                op: UnaryOp::Not,
972                operand: Box::new(operand),
973                location,
974            });
975        }
976
977        if self.match_token(&TokenKind::Minus) {
978            let operand = self.parse_unary()?;
979            return Ok(Expr::Unary {
980                op: UnaryOp::Neg,
981                operand: Box::new(operand),
982                location,
983            });
984        }
985
986        if self.match_token(&TokenKind::Plus) {
987            let operand = self.parse_unary()?;
988            return Ok(Expr::Unary {
989                op: UnaryOp::Pos,
990                operand: Box::new(operand),
991                location,
992            });
993        }
994
995        if self.match_token(&TokenKind::Increment) {
996            let operand = self.parse_unary()?;
997            return Ok(Expr::PreIncrement(Box::new(operand), location));
998        }
999
1000        if self.match_token(&TokenKind::Decrement) {
1001            let operand = self.parse_unary()?;
1002            return Ok(Expr::PreDecrement(Box::new(operand), location));
1003        }
1004
1005        self.parse_postfix()
1006    }
1007
1008    fn parse_postfix(&mut self) -> Result<Expr> {
1009        let mut expr = self.parse_field()?;
1010
1011        loop {
1012            let location = self.current_location();
1013
1014            if self.match_token(&TokenKind::Increment) {
1015                expr = Expr::PostIncrement(Box::new(expr), location);
1016            } else if self.match_token(&TokenKind::Decrement) {
1017                expr = Expr::PostDecrement(Box::new(expr), location);
1018            } else if self.match_token(&TokenKind::LeftBracket) {
1019                // Array access
1020                if let Expr::Var(name, _) = expr {
1021                    let mut indices = vec![self.parse_expression()?];
1022                    while self.match_token(&TokenKind::Comma) {
1023                        indices.push(self.parse_expression()?);
1024                    }
1025                    self.expect(&TokenKind::RightBracket)?;
1026                    expr = Expr::ArrayAccess {
1027                        array: name,
1028                        indices,
1029                        location,
1030                    };
1031                } else {
1032                    return Err(Error::parser(
1033                        "array access requires variable name",
1034                        location.line,
1035                        location.column,
1036                    ));
1037                }
1038            } else {
1039                break;
1040            }
1041        }
1042
1043        Ok(expr)
1044    }
1045
1046    fn parse_field(&mut self) -> Result<Expr> {
1047        if self.match_token(&TokenKind::Dollar) {
1048            let location = self.current_location();
1049            let expr = self.parse_field_operand()?;
1050            return Ok(Expr::Field(Box::new(expr), location));
1051        }
1052
1053        self.parse_primary()
1054    }
1055
1056    /// Parses the operand of a `$` field reference.
1057    ///
1058    /// POSIX AWK grammar has `$` apply to a `unary_expr`, so field
1059    /// references like `$-1`, `$+x`, `$++i`, `$--i`, and `$!x` are valid.
1060    /// This mirrors `parse_unary`'s prefix operators but bottoms out in
1061    /// `parse_field` (rather than `parse_postfix`) so that a nested `$`
1062    /// (e.g. `$$1`) is still handled, and so that precedence for
1063    /// everything else (postfix `++`/`--`, binary operators, `^`) is
1064    /// unaffected: those are applied by the callers of `parse_field`.
1065    fn parse_field_operand(&mut self) -> Result<Expr> {
1066        let location = self.current_location();
1067
1068        if self.match_token(&TokenKind::Not) {
1069            let operand = self.parse_field_operand()?;
1070            return Ok(Expr::Unary {
1071                op: UnaryOp::Not,
1072                operand: Box::new(operand),
1073                location,
1074            });
1075        }
1076
1077        if self.match_token(&TokenKind::Minus) {
1078            let operand = self.parse_field_operand()?;
1079            return Ok(Expr::Unary {
1080                op: UnaryOp::Neg,
1081                operand: Box::new(operand),
1082                location,
1083            });
1084        }
1085
1086        if self.match_token(&TokenKind::Plus) {
1087            let operand = self.parse_field_operand()?;
1088            return Ok(Expr::Unary {
1089                op: UnaryOp::Pos,
1090                operand: Box::new(operand),
1091                location,
1092            });
1093        }
1094
1095        if self.match_token(&TokenKind::Increment) {
1096            let operand = self.parse_field_operand()?;
1097            return Ok(Expr::PreIncrement(Box::new(operand), location));
1098        }
1099
1100        if self.match_token(&TokenKind::Decrement) {
1101            let operand = self.parse_field_operand()?;
1102            return Ok(Expr::PreDecrement(Box::new(operand), location));
1103        }
1104
1105        self.parse_field()
1106    }
1107
1108    fn parse_primary(&mut self) -> Result<Expr> {
1109        let location = self.current_location();
1110
1111        // Number literal
1112        if let Some(TokenKind::Number(n)) = self.peek_kind() {
1113            let n = *n;
1114            self.advance();
1115            return Ok(Expr::Number(n, location));
1116        }
1117
1118        // String literal
1119        if let Some(TokenKind::String(s)) = self.peek_kind() {
1120            let s = s.clone();
1121            self.advance();
1122            return Ok(Expr::String(s, location));
1123        }
1124
1125        // Regex literal
1126        if let Some(TokenKind::Regex(r)) = self.peek_kind() {
1127            let r = r.clone();
1128            self.advance();
1129            return Ok(Expr::Regex(r, location));
1130        }
1131
1132        // Identifier (variable or function call)
1133        if let Some(TokenKind::Identifier(name)) = self.peek_kind() {
1134            let name = name.clone();
1135            self.advance();
1136
1137            // Check for function call
1138            if self.match_token(&TokenKind::LeftParen) {
1139                let mut args = Vec::new();
1140                if !self.check(&TokenKind::RightParen) {
1141                    args.push(self.parse_expression()?);
1142                    while self.match_token(&TokenKind::Comma) {
1143                        args.push(self.parse_expression()?);
1144                    }
1145                }
1146                self.expect(&TokenKind::RightParen)?;
1147                return Ok(Expr::Call {
1148                    name,
1149                    args,
1150                    location,
1151                });
1152            }
1153
1154            return Ok(Expr::Var(name, location));
1155        }
1156
1157        // Getline
1158        if self.match_token(&TokenKind::Getline) {
1159            let var = self.parse_getline_target()?;
1160
1161            let input = if self.match_token(&TokenKind::Less) {
1162                Some(GetlineInput::File(Box::new(self.parse_primary()?)))
1163            } else {
1164                None
1165            };
1166
1167            return Ok(Expr::Getline {
1168                var,
1169                input,
1170                location,
1171            });
1172        }
1173
1174        // Parenthesized expression
1175        if self.match_token(&TokenKind::LeftParen) {
1176            let expr = self.parse_expression()?;
1177            self.expect(&TokenKind::RightParen)?;
1178            return Ok(Expr::Group(Box::new(expr), location));
1179        }
1180
1181        Err(Error::parser(
1182            format!("unexpected token {:?}", self.peek_kind()),
1183            location.line,
1184            location.column,
1185        ))
1186    }
1187
1188    // ===== Helper methods =====
1189
1190    fn peek_kind(&self) -> Option<&TokenKind> {
1191        self.tokens.get(self.current).map(|t| &t.kind)
1192    }
1193
1194    fn current_location(&self) -> SourceLocation {
1195        self.tokens
1196            .get(self.current)
1197            .map(|t| t.location)
1198            .unwrap_or(SourceLocation::new(0, 0))
1199    }
1200
1201    fn is_at_end(&self) -> bool {
1202        matches!(self.peek_kind(), None | Some(TokenKind::Eof))
1203    }
1204
1205    fn check(&self, kind: &TokenKind) -> bool {
1206        self.peek_kind()
1207            .map(|k| std::mem::discriminant(k) == std::mem::discriminant(kind))
1208            .unwrap_or(false)
1209    }
1210
1211    fn advance(&mut self) -> Option<&Token> {
1212        if !self.is_at_end() {
1213            self.current += 1;
1214        }
1215        self.tokens.get(self.current - 1)
1216    }
1217
1218    fn match_token(&mut self, kind: &TokenKind) -> bool {
1219        if self.check(kind) {
1220            self.advance();
1221            true
1222        } else {
1223            false
1224        }
1225    }
1226
1227    fn expect(&mut self, kind: &TokenKind) -> Result<&Token> {
1228        if self.check(kind) {
1229            Ok(self.advance().unwrap())
1230        } else {
1231            let loc = self.current_location();
1232            Err(Error::parser(
1233                format!("expected {:?}, found {:?}", kind, self.peek_kind()),
1234                loc.line,
1235                loc.column,
1236            ))
1237        }
1238    }
1239
1240    fn expect_identifier(&mut self) -> Result<String> {
1241        if let Some(TokenKind::Identifier(name)) = self.peek_kind() {
1242            let name = name.clone();
1243            self.advance();
1244            Ok(name)
1245        } else {
1246            let loc = self.current_location();
1247            Err(Error::parser(
1248                format!("expected identifier, found {:?}", self.peek_kind()),
1249                loc.line,
1250                loc.column,
1251            ))
1252        }
1253    }
1254
1255    fn skip_newlines(&mut self) {
1256        while self.match_token(&TokenKind::Newline) {}
1257    }
1258
1259    fn skip_terminators(&mut self) {
1260        while self.match_token(&TokenKind::Newline) || self.match_token(&TokenKind::Semicolon) {}
1261    }
1262
1263    fn can_start_expression(&self) -> bool {
1264        self.peek_kind()
1265            .map(|k| k.can_start_expression())
1266            .unwrap_or(false)
1267    }
1268}
1269
1270#[cfg(test)]
1271mod tests {
1272    use super::*;
1273    use crate::lexer::Lexer;
1274
1275    fn parse(source: &str) -> Result<Program> {
1276        let mut lexer = Lexer::new(source);
1277        let tokens = lexer.tokenize()?;
1278        let mut parser = Parser::new(tokens);
1279        parser.parse()
1280    }
1281
1282    #[test]
1283    fn test_simple_print() {
1284        let program = parse(r#"{ print "hello" }"#).unwrap();
1285        assert_eq!(program.rules.len(), 1);
1286    }
1287
1288    #[test]
1289    fn test_begin_end() {
1290        let program = parse(r#"BEGIN { x = 1 } END { print x }"#).unwrap();
1291        assert_eq!(program.rules.len(), 2);
1292        assert!(matches!(program.rules[0].pattern, Some(Pattern::Begin)));
1293        assert!(matches!(program.rules[1].pattern, Some(Pattern::End)));
1294    }
1295
1296    #[test]
1297    fn test_regex_pattern() {
1298        let program = parse(r#"/foo/ { print }"#).unwrap();
1299        assert_eq!(program.rules.len(), 1);
1300        assert!(matches!(
1301            &program.rules[0].pattern,
1302            Some(Pattern::Regex(r)) if r == "foo"
1303        ));
1304    }
1305
1306    #[test]
1307    fn test_arithmetic() {
1308        let program = parse(r#"{ x = 1 + 2 * 3 }"#).unwrap();
1309        assert_eq!(program.rules.len(), 1);
1310    }
1311
1312    #[test]
1313    fn test_function_def() {
1314        let program = parse(r#"function add(a, b) { return a + b }"#).unwrap();
1315        assert_eq!(program.functions.len(), 1);
1316        assert_eq!(program.functions[0].name, "add");
1317        assert_eq!(program.functions[0].params, vec!["a", "b"]);
1318    }
1319
1320    #[test]
1321    fn test_if_else() {
1322        let program = parse(r#"{ if (x) print 1; else print 2 }"#).unwrap();
1323        assert_eq!(program.rules.len(), 1);
1324    }
1325
1326    #[test]
1327    fn test_while_loop() {
1328        let program = parse(r#"{ while (x < 10) x++ }"#).unwrap();
1329        assert_eq!(program.rules.len(), 1);
1330    }
1331
1332    #[test]
1333    fn test_for_loop() {
1334        let program = parse(r#"{ for (i=0; i<10; i++) print i }"#).unwrap();
1335        assert_eq!(program.rules.len(), 1);
1336    }
1337
1338    #[test]
1339    fn test_for_in_loop() {
1340        let program = parse(r#"{ for (k in a) print k }"#).unwrap();
1341        assert_eq!(program.rules.len(), 1);
1342    }
1343
1344    #[test]
1345    fn test_do_while() {
1346        let program = parse(r#"{ do { x++ } while (x < 10) }"#).unwrap();
1347        assert_eq!(program.rules.len(), 1);
1348    }
1349
1350    #[test]
1351    fn test_delete() {
1352        let program = parse(r#"{ delete a[1] }"#).unwrap();
1353        assert_eq!(program.rules.len(), 1);
1354    }
1355
1356    #[test]
1357    fn test_delete_array() {
1358        let program = parse(r#"{ delete a }"#).unwrap();
1359        assert_eq!(program.rules.len(), 1);
1360    }
1361
1362    #[test]
1363    fn test_break_continue() {
1364        let program = parse(r#"{ break; continue }"#).unwrap();
1365        assert_eq!(program.rules.len(), 1);
1366    }
1367
1368    #[test]
1369    fn test_next_nextfile() {
1370        let program = parse(r#"{ next } { nextfile }"#).unwrap();
1371        assert_eq!(program.rules.len(), 2);
1372    }
1373
1374    #[test]
1375    fn test_exit() {
1376        let program = parse(r#"{ exit 0 }"#).unwrap();
1377        assert_eq!(program.rules.len(), 1);
1378    }
1379
1380    #[test]
1381    fn test_return() {
1382        let program = parse(r#"function f() { return 42 }"#).unwrap();
1383        assert_eq!(program.functions.len(), 1);
1384    }
1385
1386    #[test]
1387    fn test_printf() {
1388        let program = parse(r#"{ printf "%d", x }"#).unwrap();
1389        assert_eq!(program.rules.len(), 1);
1390    }
1391
1392    #[test]
1393    fn test_getline() {
1394        let program = parse(r#"{ getline x < "file" }"#).unwrap();
1395        assert_eq!(program.rules.len(), 1);
1396    }
1397
1398    #[test]
1399    fn test_pipe_getline() {
1400        let program = parse(r#"{ "cmd" | getline x }"#).unwrap();
1401        assert_eq!(program.rules.len(), 1);
1402    }
1403
1404    #[test]
1405    fn test_output_redirect() {
1406        let program = parse(r#"{ print "x" > "file" }"#).unwrap();
1407        assert_eq!(program.rules.len(), 1);
1408    }
1409
1410    #[test]
1411    fn test_output_append() {
1412        let program = parse(r#"{ print "x" >> "file" }"#).unwrap();
1413        assert_eq!(program.rules.len(), 1);
1414    }
1415
1416    #[test]
1417    fn test_output_pipe() {
1418        let program = parse(r#"{ print "x" | "cmd" }"#).unwrap();
1419        assert_eq!(program.rules.len(), 1);
1420    }
1421
1422    #[test]
1423    fn test_ternary() {
1424        let program = parse(r#"{ x = a ? b : c }"#).unwrap();
1425        assert_eq!(program.rules.len(), 1);
1426    }
1427
1428    #[test]
1429    fn test_logical_and_or() {
1430        let program = parse(r#"{ x = a && b || c }"#).unwrap();
1431        assert_eq!(program.rules.len(), 1);
1432    }
1433
1434    #[test]
1435    fn test_array_in() {
1436        let program = parse(r#"{ x = (1 in a) }"#).unwrap();
1437        assert_eq!(program.rules.len(), 1);
1438    }
1439
1440    #[test]
1441    fn test_regex_match() {
1442        let program = parse(r#"{ x = ($0 ~ /foo/) }"#).unwrap();
1443        assert_eq!(program.rules.len(), 1);
1444    }
1445
1446    #[test]
1447    fn test_concatenation() {
1448        let program = parse(r#"{ x = a b c }"#).unwrap();
1449        assert_eq!(program.rules.len(), 1);
1450    }
1451
1452    #[test]
1453    fn test_field_access() {
1454        let program = parse(r#"{ print $1, $NF, $(2+1) }"#).unwrap();
1455        assert_eq!(program.rules.len(), 1);
1456    }
1457
1458    #[test]
1459    fn test_field_unary_operand() {
1460        // POSIX: `$` applies to a unary_expr, so `$-1`, `$+x`, `$!x` are
1461        // valid field references (equivalent to `$(-1)`, `$(+x)`, `$(!x)`).
1462        let program = parse(r#"{ print $-1 }"#).unwrap();
1463        assert_eq!(program.rules.len(), 1);
1464
1465        let program = parse(r#"{ print $+x }"#).unwrap();
1466        assert_eq!(program.rules.len(), 1);
1467
1468        let program = parse(r#"{ print $!x }"#).unwrap();
1469        assert_eq!(program.rules.len(), 1);
1470    }
1471
1472    #[test]
1473    fn test_field_pre_increment_operand() {
1474        // `$++i` and `$--i` are valid field references: `$(++i)`.
1475        let program = parse(r#"{ print $++i }"#).unwrap();
1476        assert_eq!(program.rules.len(), 1);
1477
1478        let program = parse(r#"{ print $--i }"#).unwrap();
1479        assert_eq!(program.rules.len(), 1);
1480    }
1481
1482    #[test]
1483    fn test_nested_field_dollar() {
1484        // `$$1` is `$($1)`, not affected by the unary-operand extension.
1485        let program = parse(r#"{ print $$1 }"#).unwrap();
1486        assert_eq!(program.rules.len(), 1);
1487    }
1488
1489    #[test]
1490    fn test_field_post_increment_precedence() {
1491        // `$1++` must remain `($1)++`, not `$(1++)`.
1492        let program = parse(r#"{ $1++ }"#).unwrap();
1493        let stmt = &program.rules[0].action.as_ref().unwrap().statements[0];
1494        match stmt {
1495            Stmt::Expr(Expr::PostIncrement(inner, _)) => {
1496                assert!(matches!(**inner, Expr::Field(_, _)));
1497            }
1498            other => panic!("expected PostIncrement(Field(..)), got {other:?}"),
1499        }
1500    }
1501
1502    #[test]
1503    fn test_field_binary_precedence() {
1504        // `$a+b` must remain `($a)+b`, not `$(a+b)`.
1505        let program = parse(r#"{ x = $a + b }"#).unwrap();
1506        assert_eq!(program.rules.len(), 1);
1507    }
1508
1509    #[test]
1510    fn test_array_multi_index() {
1511        let program = parse(r#"{ a[1,2,3] = x }"#).unwrap();
1512        assert_eq!(program.rules.len(), 1);
1513    }
1514
1515    #[test]
1516    fn test_function_call() {
1517        let program = parse(r#"{ x = substr(s, 1, 5) }"#).unwrap();
1518        assert_eq!(program.rules.len(), 1);
1519    }
1520
1521    #[test]
1522    fn test_pre_increment() {
1523        let program = parse(r#"{ ++x; --y }"#).unwrap();
1524        assert_eq!(program.rules.len(), 1);
1525    }
1526
1527    #[test]
1528    fn test_post_increment() {
1529        let program = parse(r#"{ x++; y-- }"#).unwrap();
1530        assert_eq!(program.rules.len(), 1);
1531    }
1532
1533    #[test]
1534    fn test_compound_assign() {
1535        let program = parse(r#"{ x += 1; y -= 1; z *= 2; w /= 2; v %= 3; p ^= 2 }"#).unwrap();
1536        assert_eq!(program.rules.len(), 1);
1537    }
1538
1539    #[test]
1540    fn test_range_pattern() {
1541        let program = parse(r#"/start/,/end/ { print }"#).unwrap();
1542        assert_eq!(program.rules.len(), 1);
1543        assert!(matches!(
1544            &program.rules[0].pattern,
1545            Some(Pattern::Range { .. })
1546        ));
1547    }
1548
1549    #[test]
1550    fn test_expression_pattern() {
1551        let program = parse(r#"NR > 5 { print }"#).unwrap();
1552        assert_eq!(program.rules.len(), 1);
1553    }
1554
1555    #[test]
1556    fn test_beginfile_endfile() {
1557        let program = parse(r#"BEGINFILE { x = 1 } ENDFILE { print }"#).unwrap();
1558        assert_eq!(program.rules.len(), 2);
1559        assert!(matches!(program.rules[0].pattern, Some(Pattern::BeginFile)));
1560        assert!(matches!(program.rules[1].pattern, Some(Pattern::EndFile)));
1561    }
1562
1563    #[test]
1564    fn test_empty_statement() {
1565        let program = parse(r#"{ ; ; ; }"#).unwrap();
1566        assert_eq!(program.rules.len(), 1);
1567    }
1568
1569    #[test]
1570    fn test_block_statement() {
1571        let program = parse(r#"{ { { x = 1 } } }"#).unwrap();
1572        assert_eq!(program.rules.len(), 1);
1573    }
1574
1575    #[test]
1576    fn test_multiple_rules() {
1577        let program = parse(r#"BEGIN { } { } END { }"#).unwrap();
1578        assert_eq!(program.rules.len(), 3);
1579    }
1580
1581    #[test]
1582    fn test_parenthesized_expression() {
1583        let program = parse(r#"{ x = (1 + 2) * 3 }"#).unwrap();
1584        assert_eq!(program.rules.len(), 1);
1585    }
1586
1587    #[test]
1588    fn test_unary_ops() {
1589        let program = parse(r#"{ x = -a + +b }"#).unwrap();
1590        assert_eq!(program.rules.len(), 1);
1591    }
1592
1593    #[test]
1594    fn test_not_operator() {
1595        let program = parse(r#"{ x = !a }"#).unwrap();
1596        assert_eq!(program.rules.len(), 1);
1597    }
1598
1599    #[test]
1600    fn test_comparison_ops() {
1601        let program =
1602            parse(r#"{ x = a < b && b <= c && c > d && d >= e && e == f && f != g }"#).unwrap();
1603        assert_eq!(program.rules.len(), 1);
1604    }
1605
1606    #[test]
1607    fn test_exponentiation() {
1608        let program = parse(r#"{ x = 2^3^4 }"#).unwrap(); // right associative
1609        assert_eq!(program.rules.len(), 1);
1610    }
1611}
awk_rs/parser/mod.rs

awk_rs/parser/
mod.rs
