Repository: rust-bakery/nom (language: rust)

Issue:
`take_while_m_n` is invalid for multi-byte UTF-8 characters
`take_m_n` does:
```rust
    match input.position(|c| !cond(c)) {
      Some(idx) => {
        if idx >= m {
          if idx <= n {
            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(idx) {
              Ok(input.take_split(index))
            } else {
              Err(Err::Error(Error::from_error_kind(
                input,
                ErrorKind::TakeWhileMN,
              )))
            };
```

while `Input::position` is defined as
```rust
  /// Returns the byte position of the first element satisfying the predicate
  fn position<P>(&self, predicate: P) -> Option<usize>
  where
    P: Fn(Self::Item) -> bool;
```
So it is looking up the byte position of the first non-matching character but then treats it as the `Item` count, comparing it with `m` and `n` and then using `slice_index` to convert it to a byte position.  This should cause it to hit `m` and `n` sooner than it should and split at the wrong position.

I see that #913 was previously reported but the 7483885 and #1097 just added the "`Item` count to byte position" conversion but didn't address that it was using a byte position.

The reason the test from #913 is working is the else-clause for when there are more valid elements than `n` (4 is greater than 1), it caps it by `n` (1), making the  `Item` count valid that it passes to `slice_index`.

To show this failing, we need to change `m`, `n`, and the input slightly
```rust
  #[test]
  fn take_while_m_n_utf8() {
    named!(parser<&str, &str>, take_while_m_n!(1, 2, |c| c == 'A' || c == '😃'));
    assert_eq!(parser("A!"), Ok(("!", "A")));
    assert_eq!(parser("😃!"), Ok(("!", "😃")));
  }
```
This fails, with the left-hand side reporting `Ok(("", "😃!")`.  The only reason it doesn't crash is that `slice_index`, when exhausted, returns `self.len()`.

I believe this problem predates #1612
`take_while_m_n` is invalid for multi-byte UTF-8 characters
`take_m_n` does:
```rust
    match input.position(|c| !cond(c)) {
      Some(idx) => {
        if idx >= m {
          if idx <= n {
            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(idx) {
              Ok(input.take_split(index))
            } else {
              Err(Err::Error(Error::from_error_kind(
                input,
                ErrorKind::TakeWhileMN,
              )))
            };
```

while `Input::position` is defined as
```rust
  /// Returns the byte position of the first element satisfying the predicate
  fn position<P>(&self, predicate: P) -> Option<usize>
  where
    P: Fn(Self::Item) -> bool;
```
So it is looking up the byte position of the first non-matching character but then treats it as the `Item` count, comparing it with `m` and `n` and then using `slice_index` to convert it to a byte position.  This should cause it to hit `m` and `n` sooner than it should and split at the wrong position.

I see that #913 was previously reported but the 7483885 and #1097 just added the "`Item` count to byte position" conversion but didn't address that it was using a byte position.

The reason the test from #913 is working is the else-clause for when there are more valid elements than `n` (4 is greater than 1), it caps it by `n` (1), making the  `Item` count valid that it passes to `slice_index`.

To show this failing, we need to change `m`, `n`, and the input slightly
```rust
  #[test]
  fn take_while_m_n_utf8() {
    named!(parser<&str, &str>, take_while_m_n!(1, 2, |c| c == 'A' || c == '😃'));
    assert_eq!(parser("A!"), Ok(("!", "A")));
    assert_eq!(parser("😃!"), Ok(("!", "😃")));
  }
```
This fails, with the left-hand side reporting `Ok(("", "😃!")`.  The only reason it doesn't crash is that `slice_index`, when exhausted, returns `self.len()`.

I believe this problem predates #1612


Discussion / hints:

Fix patch:
diff --git a/src/bytes/complete.rs b/src/bytes/complete.rs
index d70cddb06..0649efb2e 100644
--- a/src/bytes/complete.rs
+++ b/src/bytes/complete.rs
@@ -208,7 +208,7 @@ where
   }
 }
 
-/// Returns the longest (m <= len <= n) input slice  that matches the predicate.
+/// Returns the longest (m <= len <= n) input slice that matches the predicate.
 ///
 /// The parser will return the longest slice that matches the given predicate *(a function that
 /// takes the input and returns a bool)*.
@@ -242,54 +242,33 @@ where
 {
   move |i: I| {
     let input = i;
-
-    match input.position(|c| !cond(c)) {
-      Some(idx) => {
-        if idx >= m {
-          if idx <= n {
-            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(idx) {
-              Ok(input.take_split(index))
-            } else {
-              Err(Err::Error(Error::from_error_kind(
-                input,
-                ErrorKind::TakeWhileMN,
-              )))
-            };
-            res
-          } else {
-            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(n) {
-              Ok(input.take_split(index))
-            } else {
-              Err(Err::Error(Error::from_error_kind(
-                input,
-                ErrorKind::TakeWhileMN,
-              )))
-            };
-            res
-          }
-        } else {
-          let e = ErrorKind::TakeWhileMN;
-          Err(Err::Error(Error::from_error_kind(input, e)))
-        }
+    let mut count = 0;
+    for (i, (index, item)) in input.iter_indices().enumerate() {
+      if i == n {
+        return Ok(input.take_split(index));
       }
-      None => {
-        let len = input.input_len();
-        if len >= n {
-          match input.slice_index(n) {
-            Ok(index) => Ok(input.take_split(index)),
-            Err(_needed) => Err(Err::Error(Error::from_error_kind(
-              input,
-              ErrorKind::TakeWhileMN,
-            ))),
-          }
-        } else if len >= m && len <= n {
-          let res: IResult<_, _, Error> = Ok((input.take_from(len), input));
-          res
+
+      if !cond(item) {
+        if i >= m {
+          return Ok(input.take_split(index));
         } else {
-          let e = ErrorKind::TakeWhileMN;
-          Err(Err::Error(Error::from_error_kind(input, e)))
+          return Err(Err::Error(Error::from_error_kind(
+            input,
+            ErrorKind::TakeWhileMN,
+          )));
         }
       }
+
+      count += 1;
+    }
+
+    if count >= m {
+      Ok(input.take_split(input.input_len()))
+    } else {
+      Err(Err::Error(Error::from_error_kind(
+        input,
+        ErrorKind::TakeWhileMN,
+      )))
     }
   }
 }
@@ -672,6 +651,7 @@ where
 #[cfg(test)]
 mod tests {
   use super::*;
+  use crate::AsChar;
 
   #[test]
   fn complete_take_while_m_n_utf8_all_matching() {
@@ -718,4 +698,41 @@ mod tests {
   fn escaped_hang_1118() {
     assert_eq!(unquote(r#""""#), Ok(("", "")));
   }
+
+  // issue #1630 take_while_m_n is invalid for multi-byte UTF-8 characters
+  #[test]
+  fn complete_take_while_m_n_multibyte() {
+    use crate::error::Error;
+
+    fn multi_byte_chars(s: &str, m: usize, n: usize) -> IResult<&str, &str> {
+      take_while_m_n(m, n, |c: char| c.len() > 1)(s)
+    }
+
+    assert_eq!(
+      multi_byte_chars("€ latin", 0, 64),
+      Ok((&" latin"[..], &"€"[..]))
+    );
+    assert_eq!(
+      multi_byte_chars("𝄠 latin", 0, 1),
+      Ok((&" latin"[..], &"𝄠"[..]))
+    );
+    assert_eq!(
+      multi_byte_chars("باب latin", 0, 64),
+      Ok((&" latin"[..], &"باب"[..]))
+    );
+    assert_eq!(
+      multi_byte_chars("💣💢ᾠ latin", 3, 3),
+      Ok((&" latin"[..], &"💣💢ᾠ"[..]))
+    );
+    assert_eq!(
+      multi_byte_chars("latin", 0, 64),
+      Ok((&"latin"[..], &""[..]))
+    );
+    assert_eq!(multi_byte_chars("باب", 1, 3), Ok((&""[..], &"باب"[..])));
+    assert_eq!(multi_byte_chars("باب", 1, 2), Ok((&"ب"[..], &"با"[..])));
+    assert_eq!(
+      multi_byte_chars("latin", 1, 64),
+      Err(Err::Error(Error::new(&"latin"[..], ErrorKind::TakeWhileMN)))
+    );
+  }
 }
diff --git a/src/bytes/streaming.rs b/src/bytes/streaming.rs
index 00bf3f228..db064e2be 100644
--- a/src/bytes/streaming.rs
+++ b/src/bytes/streaming.rs
@@ -254,51 +254,26 @@ where
   move |i: I| {
     let input = i;
 
-    match input.position(|c| !cond(c)) {
-      Some(idx) => {
-        if idx >= m {
-          if idx <= n {
-            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(idx) {
-              Ok(input.take_split(index))
-            } else {
-              Err(Err::Error(Error::from_error_kind(
-                input,
-                ErrorKind::TakeWhileMN,
-              )))
-            };
-            res
-          } else {
-            let res: IResult<_, _, Error> = if let Ok(index) = input.slice_index(n) {
-              Ok(input.take_split(index))
-            } else {
-              Err(Err::Error(Error::from_error_kind(
-                input,
-                ErrorKind::TakeWhileMN,
-              )))
-            };
-            res
-          }
-        } else {
-          let e = ErrorKind::TakeWhileMN;
-          Err(Err::Error(Error::from_error_kind(input, e)))
-        }
+    for (i, (index, item)) in input.iter_indices().enumerate() {
+      if i == n {
+        return Ok(input.take_split(index));
       }
-      None => {
-        let len = input.input_len();
-        if len >= n {
-          match input.slice_index(n) {
-            Ok(index) => Ok(input.take_split(index)),
-            Err(_needed) => Err(Err::Error(Error::from_error_kind(
-              input,
-              ErrorKind::TakeWhileMN,
-            ))),
-          }
+
+      if !cond(item) {
+        if i >= m {
+          return Ok(input.take_split(index));
         } else {
-          let needed = if m > len { m - len } else { 1 };
-          Err(Err::Incomplete(Needed::new(needed)))
+          return Err(Err::Error(Error::from_error_kind(
+            input,
+            ErrorKind::TakeWhileMN,
+          )));
         }
       }
     }
+
+    let input_len = input.input_len();
+    let needed = if m > input_len { m - input_len } else { 1 };
+    Err(Err::Incomplete(Needed::new(needed)))
   }
 }
 
diff --git a/src/traits.rs b/src/traits.rs
index 37dff53fb..c71dc77a6 100644
--- a/src/traits.rs
+++ b/src/traits.rs
@@ -1,4 +1,7 @@
 //! Traits input types have to implement to work with nom combinators
+use core::iter::Enumerate;
+use core::str::CharIndices;
+
 use crate::error::{ErrorKind, ParseError};
 use crate::internal::{Err, IResult, Needed};
 use crate::lib::std::iter::Copied;
@@ -25,6 +28,11 @@ pub trait Input: Clone + Sized {
   /// An iterator over the input type, producing the item
   type Iter: Iterator<Item = Self::Item>;
 
+  /// An iterator over the input type, producing the item and its byte position
+  /// If we're iterating over `&str`, the position
+  /// corresponds to the byte index of the character
+  type IterIndices: Iterator<Item = (usize, Self::Item)>;
+
   /// Calculates the input length, as indicated by its name,
   /// and the name of the trait itself
   fn input_len(&self) -> usize;
@@ -43,6 +51,9 @@ pub trait Input: Clone + Sized {
 
   /// Returns an iterator over the elements
   fn iter_elements(&self) -> Self::Iter;
+  /// Returns an iterator over the elements and their byte offsets
+  fn iter_indices(&self) -> Self::IterIndices;
+
   /// Get the byte offset from the element's position in the stream
   fn slice_index(&self, count: usize) -> Result<usize, Needed>;
 
@@ -128,6 +139,7 @@ pub trait Input: Clone + Sized {
 impl<'a> Input for &'a [u8] {
   type Item = u8;
   type Iter = Copied<Iter<'a, u8>>;
+  type IterIndices = Enumerate<Self::Iter>;
 
   fn input_len(&self) -> usize {
     self.len()
@@ -160,6 +172,11 @@ impl<'a> Input for &'a [u8] {
     self.iter().copied()
   }
 
+  #[inline]
+  fn iter_indices(&self) -> Self::IterIndices {
+    self.iter_elements().enumerate()
+  }
+
   #[inline]
   fn slice_index(&self, count: usize) -> Result<usize, Needed> {
     if self.len() >= count {
@@ -232,6 +249,7 @@ impl<'a> Input for &'a [u8] {
 impl<'a> Input for &'a str {
   type Item = char;
   type Iter = Chars<'a>;
+  type IterIndices = CharIndices<'a>;
 
   fn input_len(&self) -> usize {
     self.len()
@@ -266,6 +284,11 @@ impl<'a> Input for &'a str {
     self.chars()
   }
 
+  #[inline]
+  fn iter_indices(&self) -> Self::IterIndices {
+    self.char_indices()
+  }
+
   #[inline]
   fn slice_index(&self, count: usize) -> Result<usize, Needed> {
     let mut cnt = 0;
@@ -1455,4 +1478,31 @@ mod tests {
     assert_eq!(a.offset(c), 0);
     assert_eq!(a.offset(d), 5);
   }
+
+  #[test]
+  fn test_slice_index() {
+    let a = "abcřèÂßÇd123";
+    assert_eq!(a.slice_index(0), Ok(0));
+    assert_eq!(a.slice_index(2), Ok(2));
+  }
+
+  #[test]
+  fn test_slice_index_utf8() {
+    let a = "a¡€💢€¡a";
+
+    for (c, len) in a.chars().zip([1, 2, 3, 4, 3, 2, 1]) {
+      assert_eq!(c.len(), len);
+    }
+
+    assert_eq!(a.slice_index(0), Ok(0));
+    assert_eq!(a.slice_index(1), Ok(1));
+    assert_eq!(a.slice_index(2), Ok(3));
+    assert_eq!(a.slice_index(3), Ok(6));
+    assert_eq!(a.slice_index(4), Ok(10));
+    assert_eq!(a.slice_index(5), Ok(13));
+    assert_eq!(a.slice_index(6), Ok(15));
+    assert_eq!(a.slice_index(7), Ok(16));
+
+    assert!(a.slice_index(8).is_err());
+  }
 }


Test patch:
diff --git a/src/bytes/tests.rs b/src/bytes/tests.rs
index 4af4eeff0..1d6ef4702 100644
--- a/src/bytes/tests.rs
+++ b/src/bytes/tests.rs
@@ -406,7 +406,7 @@ fn take_while_m_n() {
   assert_eq!(x(&a[..]), Err(Err::Incomplete(Needed::new(2))));
   assert_eq!(x(&b[..]), Err(Err::Incomplete(Needed::new(1))));
   assert_eq!(x(&c[..]), Err(Err::Incomplete(Needed::new(1))));
-  assert_eq!(x(&d[..]), Ok((&b"123"[..], &c[..])));
+  assert_eq!(x(&d[..]), Ok((&b"123"[..], &b"abc"[..])));
   assert_eq!(x(&e[..]), Ok((&b"e"[..], &b"abcd"[..])));
   assert_eq!(
     x(&f[..]),