Repository: kevinmehall/rust-peg (language: rust)

Issue:
Add bounded repetitions
It would be nice if this syntax was supported:

```
x{n,m}    at least n times x and at most m times x
x{,m}     at most m times x (including zero times)
x{n,}     at least n times x
x{n}      exactly n times x
```

It can be emulated with something like `x x (x (x x?)?)?` but that quickly gets cumbersome.



Discussion / hints:

Fix patch:
diff --git a/src/grammar.rs b/src/grammar.rs
index ddbf981..dc0dad5 100644
--- a/src/grammar.rs
+++ b/src/grammar.rs
@@ -1576,6 +1576,7 @@ fn parse_suffixed(input: &str, pos: uint) -> Result<(uint, Expr), uint> {
                                                                 Ok((pos,
                                                                     Repeat(box() expression,
                                                                            0,
+                                                                           None,
                                                                            Some(box() sep))))
                                                             }
                                                         }
@@ -1623,6 +1624,7 @@ fn parse_suffixed(input: &str, pos: uint) -> Result<(uint, Expr), uint> {
                                                                         Ok((pos,
                                                                             Repeat(box() expression,
                                                                                    1,
+                                                                                   None,
                                                                                    Some(box() sep))))
                                                                     }
                                                                 }
@@ -1663,6 +1665,7 @@ fn parse_suffixed(input: &str, pos: uint) -> Result<(uint, Expr), uint> {
                                                                     Ok((pos,
                                                                         Repeat(box() expression,
                                                                                0,
+                                                                               None,
                                                                                None)))
                                                                 }
                                                             }
@@ -1708,6 +1711,7 @@ fn parse_suffixed(input: &str, pos: uint) -> Result<(uint, Expr), uint> {
                                                                             Ok((pos,
                                                                                 Repeat(box() expression,
                                                                                        1,
+                                                                                       None,
                                                                                        None)))
                                                                         }
                                                                     }
@@ -1720,8 +1724,370 @@ fn parse_suffixed(input: &str, pos: uint) -> Result<(uint, Expr), uint> {
                                         match choice_res {
                                             Ok((pos, value)) =>
                                             Ok((pos, value)),
-                                            Err(..) =>
-                                            parse_primary(input, pos),
+                                            Err(..) => {
+                                                let choice_res =
+                                                    {
+                                                        let start_pos = pos;
+                                                        {
+                                                            let seq_res =
+                                                                parse_primary(input,
+                                                                              pos);
+                                                            match seq_res {
+                                                                Err(pos) => {
+                                                                    Err(pos)
+                                                                }
+                                                                Ok((pos,
+                                                                    expression))
+                                                                => {
+                                                                    {
+                                                                        let seq_res =
+                                                                            parse_lbrace(input,
+                                                                                         pos);
+                                                                        match seq_res
+                                                                            {
+                                                                            Err(pos)
+                                                                            =>
+                                                                            {
+                                                                                Err(pos)
+                                                                            }
+                                                                            Ok((pos,
+                                                                                _))
+                                                                            =>
+                                                                            {
+                                                                                {
+                                                                                    let seq_res =
+                                                                                        parse_integer(input,
+                                                                                                      pos);
+                                                                                    match seq_res
+                                                                                        {
+                                                                                        Err(pos)
+                                                                                        =>
+                                                                                        {
+                                                                                            Err(pos)
+                                                                                        }
+                                                                                        Ok((pos,
+                                                                                            n))
+                                                                                        =>
+                                                                                        {
+                                                                                            {
+                                                                                                let seq_res =
+                                                                                                    parse_rbrace(input,
+                                                                                                                 pos);
+                                                                                                match seq_res
+                                                                                                    {
+                                                                                                    Err(pos)
+                                                                                                    =>
+                                                                                                    {
+                                                                                                        Err(pos)
+                                                                                                    }
+                                                                                                    Ok((pos,
+                                                                                                        _))
+                                                                                                    =>
+                                                                                                    {
+                                                                                                        {
+                                                                                                            let match_str =
+                                                                                                                input.slice(start_pos,
+                                                                                                                            pos);
+                                                                                                            Ok((pos,
+                                                                                                                Repeat(box() expression,
+                                                                                                                       n,
+                                                                                                                       Some(n),
+                                                                                                                       None)))
+                                                                                                        }
+                                                                                                    }
+                                                                                                }
+                                                                                            }
+                                                                                        }
+                                                                                    }
+                                                                                }
+                                                                            }
+                                                                        }
+                                                                    }
+                                                                }
+                                                            }
+                                                        }
+                                                    };
+                                                match choice_res {
+                                                    Ok((pos, value)) =>
+                                                    Ok((pos, value)),
+                                                    Err(..) => {
+                                                        let choice_res =
+                                                            {
+                                                                let start_pos =
+                                                                    pos;
+                                                                {
+                                                                    let seq_res =
+                                                                        parse_primary(input,
+                                                                                      pos);
+                                                                    match seq_res
+                                                                        {
+                                                                        Err(pos)
+                                                                        => {
+                                                                            Err(pos)
+                                                                        }
+                                                                        Ok((pos,
+                                                                            expression))
+                                                                        => {
+                                                                            {
+                                                                                let seq_res =
+                                                                                    parse_lbrace(input,
+                                                                                                 pos);
+                                                                                match seq_res
+                                                                                    {
+                                                                                    Err(pos)
+                                                                                    =>
+                                                                                    {
+                                                                                        Err(pos)
+                                                                                    }
+                                                                                    Ok((pos,
+                                                                                        _))
+                                                                                    =>
+                                                                                    {
+                                                                                        {
+                                                                                            let seq_res =
+                                                                                                parse_integer(input,
+                                                                                                              pos);
+                                                                                            match seq_res
+                                                                                                {
+                                                                                                Err(pos)
+                                                                                                =>
+                                                                                                {
+                                                                                                    Err(pos)
+                                                                                                }
+                                                                                                Ok((pos,
+                                                                                                    min))
+                                                                                                =>
+                                                                                                {
+                                                                                                    {
+                                                                                                        let seq_res =
+                                                                                                            parse_comma(input,
+                                                                                                                        pos);
+                                                                                                        match seq_res
+                                                                                                            {
+                                                                                                            Err(pos)
+                                                                                                            =>
+                                                                                                            {
+                                                                                                                Err(pos)
+                                                                                                            }
+                                                                                                            Ok((pos,
+                                                                                                                _))
+                                                                                                            =>
+                                                                                                            {
+                                                                                                                {
+                                                                                                                    let seq_res =
+                                                                                                                        match parse_integer(input,
+                                                                                                                                            pos)
+                                                                                                                            {
+                                                                                                                            Ok((newpos,
+                                                                                                                                value))
+                                                                                                                            =>
+                                                                                                                            {
+                                                                                                                                Ok((newpos,
+                                                                                                                                    Some(value)))
+                                                                                                                            }
+                                                                                                                            Err(..)
+                                                                                                                            =>
+                                                                                                                            {
+                                                                                                                                Ok((pos,
+                                                                                                                                    None))
+                                                                                                                            }
+                                                                                                                        };
+                                                                                                                    match seq_res
+                                                                                                                        {
+                                                                                                                        Err(pos)
+                                                                                                                        =>
+                                                                                                                        {
+                                                                                                                            Err(pos)
+                                                                                                                        }
+                                                                                                                        Ok((pos,
+                                                                                                                            max))
+                                                                                                                        =>
+                                                                                                                        {
+                                                                                                                            {
+                                                                                                                                let seq_res =
+                                                                                                                                    parse_rbrace(input,
+                                                                                                                                                 pos);
+                                                                                                                                match seq_res
+                                                                                                                                    {
+                                                                                                                                    Err(pos)
+                                                                                                                                    =>
+                                                                                                                                    {
+                                                                                                                                        Err(pos)
+                                                                                                                                    }
+                                                                                                                                    Ok((pos,
+                                                                                                                                        _))
+                                                                                                                                    =>
+                                                                                                                                    {
+                                                                                                                                        {
+                                                                                                                                            let match_str =
+                                                                                                                                                input.slice(start_pos,
+                                                                                                                                                            pos);
+                                                                                                                                            Ok((pos,
+                                                                                                                                                Repeat(box() expression,
+                                                                                                                                                       min,
+                                                                                                                                                       max,
+                                                                                                                                                       None)))
+                                                                                                                                        }
+                                                                                                                                    }
+                                                                                                                                }
+                                                                                                                            }
+                                                                                                                        }
+                                                                                                                    }
+                                                                                                                }
+                                                                                                            }
+                                                                                                        }
+                                                                                                    }
+                                                                                                }
+                                                                                            }
+                                                                                        }
+                                                                                    }
+                                                                                }
+                                                                            }
+                                                                        }
+                                                                    }
+                                                                }
+                                                            };
+                                                        match choice_res {
+                                                            Ok((pos, value))
+                                                            =>
+                                                            Ok((pos, value)),
+                                                            Err(..) => {
+                                                                let choice_res =
+                                                                    {
+                                                                        let start_pos =
+                                                                            pos;
+                                                                        {
+                                                                            let seq_res =
+                                                                                parse_primary(input,
+                                                                                              pos);
+                                                                            match seq_res
+                                                                                {
+                                                                                Err(pos)
+                                                                                =>
+                                                                                {
+                                                                                    Err(pos)
+                                                                                }
+                                                                                Ok((pos,
+                                                                                    expression))
+                                                                                =>
+                                                                                {
+                                                                                    {
+                                                                                        let seq_res =
+                                                                                            parse_lbrace(input,
+                                                                                                         pos);
+                                                                                        match seq_res
+                                                                                            {
+                                                                                            Err(pos)
+                                                                                            =>
+                                                                                            {
+                                                                                                Err(pos)
+                                                                                            }
+                                                                                            Ok((pos,
+                                                                                                _))
+                                                                                            =>
+                                                                                            {
+                                                                                                {
+                                                                                                    let seq_res =
+                                                                                                        parse_comma(input,
+                                                                                                                    pos);
+                                                                                                    match seq_res
+                                                                                                        {
+                                                                                                        Err(pos)
+                                                                                                        =>
+                                                                                                        {
+                                                                                                            Err(pos)
+                                                                                                        }
+                                                                                                        Ok((pos,
+                                                                                                            _))
+                                                                                                        =>
+                                                                                                        {
+                                                                                                            {
+                                                                                                                let seq_res =
+                                                                                                                    match parse_integer(input,
+                                                                                                                                        pos)
+                                                                                                                        {
+                                                                                                                        Ok((newpos,
+                                                                                                                            value))
+                                                                                                                        =>
+                                                                                                                        {
+                                                                                                                            Ok((newpos,
+                                                                                                                                Some(value)))
+                                                                                                                        }
+                                                                                                                        Err(..)
+                                                                                                                        =>
+                                                                                                                        {
+                                                                                                                            Ok((pos,
+                                                                                                                                None))
+                                                                                                                        }
+                                                                                                                    };
+                                                                                                                match seq_res
+                                                                                                                    {
+                                                                                                                    Err(pos)
+                                                                                                                    =>
+                                                                                                                    {
+                                                                                                                        Err(pos)
+                                                                                                                    }
+                                                                                                                    Ok((pos,
+                                                                                                                        max))
+                                                                                                                    =>
+                                                                                                                    {
+                                                                                                                        {
+                                                                                                                            let seq_res =
+                                                                                                                                parse_rbrace(input,
+                                                                                                                                             pos);
+                                                                                                                            match seq_res
+                                                                                                                                {
+                                                                                                                                Err(pos)
+                                                                                                                                =>
+                                                                                                                                {
+                                                                                                                                    Err(pos)
+                                                                                                                                }
+                                                                                                                                Ok((pos,
+                                                                                                                                    _))
+                                                                                                                                =>
+                                                                                                                                {
+                                                                                                                                    {
+                                                                                                                                        let match_str =
+                                                                                                                                            input.slice(start_pos,
+                                                                                                                                                        pos);
+                                                                                                                                        Ok((pos,
+                                                                                                                                            Repeat(box() expression,
+                                                                                                                                                   0,
+                                                                                                                                                   max,
+                                                                                                                                                   None)))
+                                                                                                                                    }
+                                                                                                                                }
+                                                                                                                            }
+                                                                                                                        }
+                                                                                                                    }
+                                                                                                                }
+                                                                                                            }
+                                                                                                        }
+                                                                                                    }
+                                                                                                }
+                                                                                            }
+                                                                                        }
+                                                                                    }
+                                                                                }
+                                                                            }
+                                                                        }
+                                                                    };
+                                                                match choice_res
+                                                                    {
+                                                                    Ok((pos,
+                                                                        value))
+                                                                    =>
+                                                                    Ok((pos,
+                                                                        value)),
+                                                                    Err(..) =>
+                                                                    parse_primary(input,
+                                                                                  pos),
+                                                                }
+                                                            }
+                                                        }
+                                                    }
+                                                }
+                                            }
                                         }
                                     }
                                 }
@@ -2187,6 +2553,103 @@ fn parse_returns(input: &str, pos: uint) -> Result<(uint, ()), uint> {
         }
     }
 }
+fn parse_lbrace(input: &str, pos: uint) -> Result<(uint, ()), uint> {
+    {
+        let seq_res = slice_eq(input, pos, "{");
+        match seq_res {
+            Err(pos) => { Err(pos) }
+            Ok((pos, _)) => { parse___(input, pos) }
+        }
+    }
+}
+fn parse_rbrace(input: &str, pos: uint) -> Result<(uint, ()), uint> {
+    {
+        let seq_res = slice_eq(input, pos, "}");
+        match seq_res {
+            Err(pos) => { Err(pos) }
+            Ok((pos, _)) => { parse___(input, pos) }
+        }
+    }
+}
+fn parse_comma(input: &str, pos: uint) -> Result<(uint, ()), uint> {
+    {
+        let seq_res = slice_eq(input, pos, ",");
+        match seq_res {
+            Err(pos) => { Err(pos) }
+            Ok((pos, _)) => { parse___(input, pos) }
+        }
+    }
+}
+fn parse_integer(input: &str, pos: uint) -> Result<(uint, uint), uint> {
+    {
+        let start_pos = pos;
+        {
+            let seq_res =
+                {
+                    let start_pos = pos;
+                    {
+                        let seq_res =
+                            {
+                                let mut repeat_pos = pos;
+                                let mut repeat_value = vec!();
+                                loop  {
+                                    let pos = repeat_pos;
+                                    let step_res =
+                                        if input.len() > pos {
+                                            let ::std::str::CharRange {
+                                                    ch: ch, next: next } =
+                                                input.char_range_at(pos);
+                                            match ch {
+                                                '0' ...'9' => Ok((next, ())),
+                                                _ => Err(pos),
+                                            }
+                                        } else { Err(pos) };
+                                    match step_res {
+                                        Ok((newpos, value)) => {
+                                            repeat_pos = newpos;
+                                            repeat_value.push(value);
+                                        }
+                                        Err(..) => { break ; }
+                                    }
+                                }
+                                if repeat_value.len() >= 1u {
+                                    Ok((repeat_pos, ()))
+                                } else { Err(repeat_pos) }
+                            };
+                        match seq_res {
+                            Err(pos) => { Err(pos) }
+                            Ok((pos, _)) => {
+                                {
+                                    let match_str =
+                                        input.slice(start_pos, pos);
+                                    Ok((pos,
+                                        from_str::<uint>(match_str).unwrap()))
+                                }
+                            }
+                        }
+                    }
+                };
+            match seq_res {
+                Err(pos) => { Err(pos) }
+                Ok((pos, i)) => {
+                    {
+                        let seq_res = parse___(input, pos);
+                        match seq_res {
+                            Err(pos) => { Err(pos) }
+                            Ok((pos, _)) => {
+                                {
+                                    let match_str =
+                                        input.slice(start_pos, pos);
+                                    Ok((pos, i))
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+}
 fn parse_identifier(input: &str, pos: uint) -> Result<(uint, String), uint> {
     {
         let start_pos = pos;
diff --git a/src/grammar.rustpeg b/src/grammar.rustpeg
index 0a69755..9cc6994 100644
--- a/src/grammar.rustpeg
+++ b/src/grammar.rustpeg
@@ -103,16 +103,25 @@ suffixed -> Expr
        OptionalExpr(box expression)
     }
   / expression:primary starstar sep:primary {
-      Repeat(box expression, 0, Some(box sep))
+      Repeat(box expression, 0, None, Some(box sep))
     }
   / expression:primary plusplus sep:primary {
-      Repeat(box expression, 1, Some(box sep))
+      Repeat(box expression, 1, None, Some(box sep))
     }
   / expression:primary star {
-      Repeat(box expression, 0, None)
+      Repeat(box expression, 0, None, None)
     }
   / expression:primary plus {
-      Repeat(box expression, 1, None)
+      Repeat(box expression, 1, None, None)
+    }
+  / expression:primary lbrace n:integer rbrace {
+      Repeat(box expression, n, Some(n), None)
+    }
+  / expression:primary lbrace min:integer comma max:integer? rbrace {
+      Repeat(box expression, min, max, None)
+    }
+  / expression:primary lbrace comma max:integer? rbrace {
+      Repeat(box expression, 0, max, None)
     }
   / primary
 
@@ -155,6 +164,12 @@ lparen    = "("  __
 rparen    = ")"  __ 
 dot       = "."  __ 
 returns   = "->" __
+lbrace    = "{"  __
+rbrace    = "}"  __
+comma     = ","  __
+
+integer -> uint
+  = i:([0-9]+ { from_str::<uint>(match_str).unwrap() }) __ { i }
 
 /*
  * Modeled after ECMA-262, 5th ed., 7.6, but much simplified:
diff --git a/src/translate.rs b/src/translate.rs
index 22c90a8..ff3781f 100644
--- a/src/translate.rs
+++ b/src/translate.rs
@@ -39,7 +39,7 @@ pub enum Expr {
 	SequenceExpr(Vec<Expr>),
 	ChoiceExpr(Vec<Expr>),
 	OptionalExpr(Box<Expr>),
-	Repeat(Box<Expr>, /*min*/ uint, /*sep*/ Option<Box<Expr>>),
+	Repeat(Box<Expr>, /*min*/ uint, /*max*/ Option<uint>, /*sep*/ Option<Box<Expr>>),
 	PosAssertExpr(Box<Expr>),
 	NegAssertExpr(Box<Expr>),
 	ActionExpr(Vec<TaggedExpr>, String),
@@ -272,7 +272,7 @@ fn compile_expr(ctxt: &rustast::ExtCtxt, e: &Expr, result_used: bool) -> rustast
 			})
 		}
 
-		Repeat(box ref e, min, ref sep) => {
+		Repeat(box ref e, min, max, ref sep) => {
 			let inner = compile_expr(ctxt, e, result_used);
 
 			let match_sep = match *sep {
@@ -297,13 +297,21 @@ fn compile_expr(ctxt: &rustast::ExtCtxt, e: &Expr, result_used: bool) -> rustast
 				quote_expr!(ctxt, ())
 			};
 
-			let (repeat_vec, repeat_step) = if result_used || min > 0 || sep.is_some() {
+			let (repeat_vec, repeat_step) =
+			if result_used || min > 0 || max.is_some() || sep.is_some() {
 				(quote_tokens!(ctxt, let mut repeat_value = vec!();),
 				 quote_tokens!(ctxt, repeat_value.push(value);))
 			} else {
 				(vec!(), vec!())
 			};
 
+			let max_check = match max {
+				None => vec!(),
+				Some(max) => quote_tokens!(ctxt,
+					if repeat_value.len() >= $max { break }
+				)
+			};
+
 			let result_check = if min > 0 {
 				quote_expr!(ctxt,
 					if repeat_value.len() >= $min {
@@ -324,6 +332,7 @@ fn compile_expr(ctxt: &rustast::ExtCtxt, e: &Expr, result_used: bool) -> rustast
 					let pos = repeat_pos;
 
 					$match_sep
+					$max_check
 
 					let step_res = $inner;
 					match step_res {


Test patch:
diff --git a/examples/tests.rs b/examples/tests.rs
index 6e25d5e..5f2f6e7 100644
--- a/examples/tests.rs
+++ b/examples/tests.rs
@@ -1,4 +1,6 @@
-use test_grammar::{consonants, options, list, boundaries, borrowed};
+#![feature(globs)]
+
+use test_grammar::*;
 mod test_grammar;
 
 #[test]
@@ -20,6 +22,29 @@ fn test_list() {
 	assert_eq!(list("1,2,3,4"), Ok(vec![1,2,3,4]));
 }
 
+#[test]
+fn test_repeat() {
+	assert!(repeat_n("123").is_err());
+	assert_eq!(repeat_n("1234"), Ok(vec![1,2,3,4]));
+	assert!(repeat_n("12345").is_err());
+
+	assert!(repeat_min("").is_err());
+	assert!(repeat_min("1").is_err());
+	assert_eq!(repeat_min("12"), Ok(vec![1,2]));
+	assert_eq!(repeat_min("123"), Ok(vec![1,2,3]));
+
+	assert_eq!(repeat_max(""), Ok(vec![]));
+	assert_eq!(repeat_max("1"), Ok(vec![1]));
+	assert_eq!(repeat_max("12"), Ok(vec![1,2]));
+	assert!(repeat_max("123").is_err());
+
+	assert!(repeat_min_max("").is_err());
+	assert!(repeat_min_max("1").is_err());
+	assert_eq!(repeat_min_max("12"), Ok(vec![1,2]));
+	assert_eq!(repeat_min_max("123"), Ok(vec![1,2,3]));
+	assert!(repeat_min_max("1234").is_err());
+}
+
 #[test]
 // before we were testing string matches using .slice(), which
 // threw an ugly fail!() when we compared unequal character
diff --git a/examples/tests.rustpeg b/examples/tests.rustpeg
index 543447e..8e86cff 100644
--- a/examples/tests.rustpeg
+++ b/examples/tests.rustpeg
@@ -13,6 +13,25 @@ number -> int
 list -> Vec<int>
 	= number ** ","
 
+digit -> int
+	= [0-9] { from_str::<int>(match_str).unwrap() }
+
+#[export]
+repeat_n -> Vec<int>
+	= digit{4}
+
+#[export]
+repeat_min -> Vec<int>
+	= digit{2,}
+
+#[export]
+repeat_max -> Vec<int>
+	= digit{,2}
+
+#[export]
+repeat_min_max -> Vec<int>
+	= digit{2,3}
+
 #[export]
 boundaries -> String
 	= "foo" { match_str.to_string() }