Repository: m4rw3r/chomp (language: rust)

Issue:
`string` can cause parsing to be slow with `verbose_error`
# Problem

`string` allocates a copy of the string it was trying to match on error in `verbose_error` mode. This can cause really bad performance when eg. trying to match multiple different tags using nested `or`-combinators (used in the mp4-benchmark from nom_benchmarks).



Discussion / hints:
The `string` parser could be made to just return the `Error::Expected` on the differing character. This might even allow for removal of the `verbose_error` feature completely since `Error` will not contain any heap-allocated data.

This will result in slightly less useful error messages from the `string` parser, since it will not display the full string. In addition to this the error position returned from the `string` parser would be set to the unexpected character instead of the start of the match (the current behaviour). This could break some buffer-usage where it is expected to restart the parsing from the start of the attempted `string` match instead of restarting from the offending character.

Another possibility is to only allow `'static` lifetime on the string to match against, but this will probably be too limiting.

Combining #23 with just reporting the offending character (ie. you get a full back-trace pointing to the `string` parser) will most likely solve the issue where you actually need to see which string it is trying to match.


Fix patch:
diff --git a/.travis.yml b/.travis.yml
index ca1b8b25..2c932076 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -36,7 +36,10 @@ after_success:
 
 env:
   matrix:
+    - FEATURES="--features noop_error"
+    - FEATURES="--features backtrace"
+    # Travis seems to have issues with quotation in env-vars, use a merged feature
+    - FEATURES="--features noop_error_and_backtrace"
     - FEATURES=""
-    - FEATURES="--no-default-features"
   global:
     - secure: gsvH3282enp+tO7Hjd0BEUnv9+jX0uQ/E9+B07ZPcbjYvoSA68Hk2UfZb1IYMWWXO1mWR8zF1Q/AnZR26fYEtlGaF8vTRqoYQHCc5pYUxNaSJPf1C2fvGpiRW63h9lC9sAwia7r2oS+aBeXHdrxvPtScMescf+fzjdeTYy4sHAg9ahrMIDlXB2cFXBixyqbjKwPB3wT0VqjOc8avzhAKehxXU8/h51P2FjRXLv/aEs/cMV7vpGGAZG4uA9cgrql7zayWMdiUNFGzR0Di7r3tDK3TPsla1c1W5+YYrbWkXT/cX5AvpDa9IH+jookPITzNlN7v6ZAQiwBzE7U2qzbZu34QAk34lfEwlcF/wVfuiKfUwR/U+B8Lb5tFPBF1lWn/NOw+uec4d/0XO2K6sfVxXn0nMrfeA/L8Q3pJ+3Fmts+gP4oumrjZ9L+zoYE+Lpn22T2W81BOPuW2c1JvbB5ZDds4ztHc2BL4aiYSO9DzMYTCz4sT/UbDbgVWkhwwfeKarCAvTmfTfpgIsNdnMdkiMX4gLIzm1W0xwtTc8Tl7GgCQjO8zxcgZT67bi507Huf9zQ4AwaBN4P9jCGSsa+bleIcUeR5NkX2KJlT5WNqUIyCHqHwG18Ddm8jmSMut4AVsyXkdAONq4Xfa07cZUBoKtAahrgl8UqXclCjtw31acGk=
diff --git a/Cargo.toml b/Cargo.toml
index 4d7dea58..4f45de2e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -22,15 +22,20 @@ include = [
 ]
 
 [dependencies]
-bitflags = "0.5.0"
-conv     = { version = "0.3", default-features = false }
+bitflags   = "0.5.0"
+conv       = { version = "0.3", default-features = false }
+debugtrace = { version = "0.1.0" }
 
 # Technically a dev-dependency, but dev-dependencies are not allowed to be optional,
 # compiletest_rs fails to compile on stable and beta
 compiletest_rs = { version = "0.1.1", optional = true }
 
 [features]
-default       = ["verbose_error"]
-verbose_error = []
 # Feature for running extra (compiletime fail) tests on nightly
 unstable      = ["compiletest_rs"]
+noop_error    = []
+backtrace     = ["debugtrace/backtrace"]
+
+# Feature for travis, so that both noop_error and backtrace can be enabled simultaneously
+# without causing parse-errors in the argument parser in travis-cargo.
+noop_error_and_backtrace = ["noop_error", "backtrace"]
diff --git a/src/combinators/mod.rs b/src/combinators/mod.rs
index 04950e70..c716c9e5 100644
--- a/src/combinators/mod.rs
+++ b/src/combinators/mod.rs
@@ -14,22 +14,20 @@ use primitives::{IntoInner, InputBuffer, InputClone};
 
 /// Applies the parser ``p`` exactly ``num`` times collecting all items into `T: FromIterator`.
 ///
-#[cfg_attr(feature = "verbose_error", doc = "
-```
- use chomp::{U8Result, ParseError, Error, Input, parse_only, count, token, take_remainder};
-
- fn parse(i: Input<u8>) -> U8Result<Vec<u8>> {
-     count(i, 2, |i| token(i, b'a'))
- }
-
- assert_eq!(parse_only(parse, b\"a  \"), Err(ParseError::Error(b\"  \", Error::Expected(b'a'))));
- assert_eq!(parse_only(parse, b\"aa \"), Ok(vec![b'a', b'a']));
-
- let with_remainder = |i| parse(i).bind(|i, d| take_remainder(i).map(|r| (r, d)));
-
- assert_eq!(parse_only(with_remainder, b\"aaa\"), Ok((&b\"a\"[..], vec![b'a', b'a'])));
-```
-")]
+/// ```
+/// use chomp::{U8Result, ParseError, Error, Input, parse_only, count, token, take_remainder};
+///
+/// fn parse(i: Input<u8>) -> U8Result<Vec<u8>> {
+///     count(i, 2, |i| token(i, b'a'))
+/// }
+///
+/// assert_eq!(parse_only(parse, b"a  "), Err(ParseError::Error(b"  ", Error::expected(b'a'))));
+/// assert_eq!(parse_only(parse, b"aa "), Ok(vec![b'a', b'a']));
+///
+/// let with_remainder = |i| parse(i).bind(|i, d| take_remainder(i).map(|r| (r, d)));
+///
+/// assert_eq!(parse_only(with_remainder, b"aaa"), Ok((&b"a"[..], vec![b'a', b'a'])));
+/// ```
 #[inline]
 pub fn count<'a, I, T, E, F, U>(i: Input<'a, I>, num: usize, p: F) -> ParseResult<'a, I, T, E>
   where I: Copy,
@@ -77,19 +75,17 @@ pub fn option<'a, I, T, E, F>(i: Input<'a, I>, f: F, default: T) -> ParseResult<
 /// If multiple `or` combinators are used in the same expression, consider using the `parse!` macro
 /// and its alternation operator (`<|>`).
 ///
-#[cfg_attr(feature = "verbose_error", doc = "
-```
- use chomp::{ParseError, Error, parse_only, or, token};
-
- let p = |i| or(i,
-             |i| token(i, b'a'),
-             |i| token(i, b'b'));
-
- assert_eq!(parse_only(&p, b\"abc\"), Ok(b'a'));
- assert_eq!(parse_only(&p, b\"bbc\"), Ok(b'b'));
- assert_eq!(parse_only(&p, b\"cbc\"), Err(ParseError::Error(b\"cbc\", Error::Expected(b'b'))));
-```
-")]
+/// ```
+/// use chomp::{ParseError, Error, parse_only, or, token};
+///
+/// let p = |i| or(i,
+///             |i| token(i, b'a'),
+///             |i| token(i, b'b'));
+///
+/// assert_eq!(parse_only(&p, b"abc"), Ok(b'a'));
+/// assert_eq!(parse_only(&p, b"bbc"), Ok(b'b'));
+/// assert_eq!(parse_only(&p, b"cbc"), Err(ParseError::Error(b"cbc", Error::expected(b'b'))));
+/// ```
 #[inline]
 pub fn or<'a, I, T, E, F, G>(i: Input<'a, I>, f: F, g: G) -> ParseResult<'a, I, T, E>
   where F: FnOnce(Input<'a, I>) -> ParseResult<'a, I, T, E>,
@@ -141,18 +137,16 @@ pub fn many<'a, I, T, E, F, U>(i: Input<'a, I>, f: F) -> ParseResult<'a, I, T, E
 ///
 /// Note: Allocates data.
 ///
-#[cfg_attr(feature = "verbose_error", doc = "
-```
- use chomp::{ParseError, Error, parse_only, token, many1, take_while1};
-
- let p = |i| many1(i, |i| take_while1(i, |c| c != b',' && c != b' ')
-             .bind(|i, c| token(i, b',')
-                          .map(|_| c)));
-
- assert_eq!(parse_only(&p, b\"a \"), Err(ParseError::Error(b\" \", Error::Expected(b','))));
- assert_eq!(parse_only(&p, b\"a, \"), Ok(vec![&b\"a\"[..]]));
-```
-")]
+/// ```
+/// use chomp::{ParseError, Error, parse_only, token, many1, take_while1};
+///
+/// let p = |i| many1(i, |i| take_while1(i, |c| c != b',' && c != b' ')
+///             .bind(|i, c| token(i, b',')
+///                          .map(|_| c)));
+///
+/// assert_eq!(parse_only(&p, b"a "), Err(ParseError::Error(b" ", Error::expected(b','))));
+/// assert_eq!(parse_only(&p, b"a, "), Ok(vec![&b"a"[..]]));
+/// ```
 #[inline]
 pub fn many1<'a, I, T, E, F, U>(i: Input<'a, I>, f: F) -> ParseResult<'a, I, T, E>
   where I: Copy,
@@ -276,18 +270,16 @@ pub fn skip_many<'a, I, T, E, F>(i: Input<'a, I>, f: F) -> ParseResult<'a, I, ()
 /// This is more efficient compared to using ``many1`` and then just discarding the result as
 /// ``many1`` allocates a separate data structure to contain the data before proceeding.
 ///
-#[cfg_attr(feature = "verbose_error", doc = "
-```
- use chomp::{ParseError, Error, parse_only, skip_many1, token};
-
- let p = |i| skip_many1(i, |i| token(i, b'a')).bind(|i, _| token(i, b'b'));
-
- assert_eq!(parse_only(&p, b\"aaaabc\"), Ok(b'b'));
- assert_eq!(parse_only(&p, b\"abc\"), Ok(b'b'));
-
- assert_eq!(parse_only(&p, b\"bc\"), Err(ParseError::Error(b\"bc\", Error::Expected(b'a'))));
-```
-")]
+/// ```
+/// use chomp::{ParseError, Error, parse_only, skip_many1, token};
+///
+/// let p = |i| skip_many1(i, |i| token(i, b'a')).bind(|i, _| token(i, b'b'));
+///
+/// assert_eq!(parse_only(&p, b"aaaabc"), Ok(b'b'));
+/// assert_eq!(parse_only(&p, b"abc"), Ok(b'b'));
+///
+/// assert_eq!(parse_only(&p, b"bc"), Err(ParseError::Error(b"bc", Error::expected(b'a'))));
+/// ```
 #[inline]
 pub fn skip_many1<'a, I, T, E, F>(i: Input<'a, I>, f: F) -> ParseResult<'a, I, (), E>
   where T: 'a, F: FnMut(Input<'a, I>) -> ParseResult<'a, I, T, E> {
diff --git a/src/lib.rs b/src/lib.rs
index bfc1bed8..4d90259e 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -93,7 +93,7 @@
 //! ```
 //! # #[macro_use] extern crate chomp;
 //! # fn main() {
-//! # use chomp::{Input, satisfy, parse_only};
+//! # use chomp::{satisfy, parse_only};
 //! # let r = parse_only(parser!{
 //! satisfy(|c| {
 //!     match c {
@@ -144,7 +144,7 @@
 //!
 //! ```
 //! # #[macro_use] extern crate chomp;
-//! # use chomp::{Input, parse_only, satisfy, string, token, U8Result};
+//! # use chomp::{Input, parse_only, satisfy, string, U8Result};
 //! fn f(i: Input<u8>) -> U8Result<(u8, u8, u8)> {
 //!     parse!{i;
 //!         let a = digit();
@@ -178,10 +178,33 @@
 //!   type of the entire parser, should it succeed.
 //!
 //! The entire grammar for the macro is listed elsewhere in this documentation.
+//!
+//! # Features
+//!
+//! * `backtrace`:
+#![cfg_attr(feature="backtrace", doc = " enabled.")]
+#![cfg_attr(not(feature="backtrace"), doc = " disabled (default).")]
+//!
+//!    This feature enables backtraces for parse-errors, either by calling `Error::trace` or by
+//!    printing it using `fmt::Debug`.
+//!
+//!    This incurs a performance-hit every time a `chomp::parsers` parser fails since a backtrace
+//!    must be collected.
+//!
+//!    In the `dev` and `test` profiles backtraces will always be enabled. This does not incur any
+//!    cost when built using the `release` profile unless the `backtrace` feature is enabled.
+//!
+//! * `noop_error`:
+#![cfg_attr(not(feature="noop_error"), doc = " disabled (default).")]
+#![cfg_attr(feature="noop_error", doc = " enabled.")]
+//!
+//!    The built-in `chomp::parsers::Error` type is zero-sized and carry no error-information. This
+//!    increases performance somewhat.
 
 #[macro_use]
 extern crate bitflags;
 extern crate conv;
+extern crate debugtrace;
 
 #[macro_use]
 mod macros;
diff --git a/src/macros.rs b/src/macros.rs
index 4d507e3d..89290271 100644
--- a/src/macros.rs
+++ b/src/macros.rs
@@ -186,8 +186,7 @@
 /// ```
 /// # #[macro_use] extern crate chomp;
 /// # fn main() {
-/// # use chomp::ascii::decimal;
-/// # use chomp::{parse_only, Input, token, U8Result};
+/// # use chomp::{parse_only, Input, U8Result};
 /// # fn my_parser(i: Input<u8>) -> U8Result<&'static str> {
 /// fn do_it<'i, 'a>(i: Input<'i, u8>, s: &'a str) -> U8Result<'i, &'a str> { i.ret(s) }
 ///
@@ -326,7 +325,7 @@
 /// ```
 /// # #[macro_use] extern crate chomp;
 /// # fn main() {
-/// # use chomp::{parse_only, token};
+/// # use chomp::{parse_only};
 /// let p = parser!{ (i -> i.err("foo")) <|> (i -> i.ret("bar")) };
 ///
 /// assert_eq!(parse_only(p, b"a;"), Ok("bar"));
diff --git a/src/parse_result.rs b/src/parse_result.rs
index 643309c5..4148f499 100644
--- a/src/parse_result.rs
+++ b/src/parse_result.rs
@@ -347,27 +347,24 @@ impl<'a, I, T: fmt::Debug, E> ParseResult<'a, I, T, E> {
     /// Panics if the parse result is in a success-state or if the parsing is incomplete. Will
     /// provide a panic message based on the value of the success or incomplete state.
     ///
-    #[cfg_attr(feature = "verbose_error", doc = "
-
- # Examples
-
- ```
- use chomp::{Error, Input, token};
-
- let r = token(Input::new(b\"a\"), b'b');
-
- assert_eq!(r.unwrap_err(), Error::Expected(98));
- ```
-
- ```{.should_panic}
- use chomp::{Error, Input, token};
-
- let r = token(Input::new(b\"a\"), b'a');
-
- // Panics with \"called `ParseResult::unwrap_err` on a success state: 97\"
- assert_eq!(r.unwrap_err(), Error::Expected(98));
- ```
-    ")]
+    /// # Examples
+    ///
+    /// ```
+    /// use chomp::{Error, Input, token};
+    ///
+    /// let r = token(Input::new(b"a"), b'b');
+    ///
+    /// assert_eq!(r.unwrap_err(), Error::expected(98));
+    /// ```
+    ///
+    /// ```{.should_panic}
+    /// use chomp::{Error, Input, token};
+    ///
+    /// let r = token(Input::new(b"a"), b'a');
+    ///
+    /// // Panics with "called `ParseResult::unwrap_err` on a success state: 97"
+    /// assert_eq!(r.unwrap_err(), Error::expected(98));
+    /// ```
     #[inline]
     pub fn unwrap_err(self) -> E {
         match self.0 {
diff --git a/src/parsers.rs b/src/parsers.rs
index 4b9a2135..84cc1393 100644
--- a/src/parsers.rs
+++ b/src/parsers.rs
@@ -1,17 +1,18 @@
 //! Basic parsers.
 
 use std::mem;
-use std::any;
-use std::error;
-use std::fmt;
-
-#[cfg(not(feature = "verbose_error"))]
-use std::marker::PhantomData;
 
 use input::Input;
 use parse_result::SimpleResult;
 use primitives::InputBuffer;
 
+pub use self::error::Error;
+
+// Only export if we have backtraces enabled, in debug/test profiles the StackFrame is only used
+// to debug-print.
+#[cfg(feature="backtrace")]
+pub use debugtrace::StackFrame;
+
 /// Matches any item, returning it if present.
 ///
 /// If the buffer length is 0 this parser is considered incomplete.
@@ -49,7 +50,7 @@ pub fn satisfy<I: Copy, F>(i: Input<I>, f: F) -> SimpleResult<I, I>
     match b.first() {
         None             => i.incomplete(1),
         Some(&c) if f(c) => i.replace(&b[1..]).ret(c),
-        Some(_)          => i.err(err::unexpected()),
+        Some(_)          => i.err(Error::unexpected()),
     }
 }
 
@@ -80,7 +81,7 @@ pub fn satisfy_with<I: Copy, T: Clone, F, P>(i: Input<I>, f: F, p: P) -> SimpleR
             if p(t.clone()) {
                 i.replace(&b[1..]).ret(t)
             } else {
-                i.err(err::unexpected())
+                i.err(Error::unexpected())
             }
         },
         None    => i.incomplete(1),
@@ -103,7 +104,7 @@ pub fn token<I: Copy + PartialEq>(i: Input<I>, t: I) -> SimpleResult<I, I> {
     match b.first() {
         None               => i.incomplete(1),
         Some(&c) if t == c => i.replace(&b[1..]).ret(c),
-        Some(_)            => i.err(err::expected(t)),
+        Some(_)            => i.err(Error::expected(t)),
     }
 }
 
@@ -123,7 +124,7 @@ pub fn not_token<I: Copy + PartialEq>(i: Input<I>, t: I) -> SimpleResult<I, I> {
     match b.first() {
         None               => i.incomplete(1),
         Some(&c) if t != c => i.replace(&b[1..]).ret(c),
-        Some(_)            => i.err(err::unexpected()),
+        Some(_)            => i.err(Error::unexpected()),
     }
 }
 
@@ -244,7 +245,7 @@ pub fn take_while1<I: Copy, F>(i: Input<I>, f: F) -> SimpleResult<I, &[I]>
     let b = i.buffer();
 
     match b.iter().position(|c| f(*c) == false) {
-        Some(0) => i.err(err::unexpected()),
+        Some(0) => i.err(Error::unexpected()),
         Some(n) => i.replace(&b[n..]).ret(&b[..n]),
         // TODO: Should this following 1 be something else, seeing as take_while1 is potentially
         // infinite?
@@ -380,7 +381,7 @@ pub fn string<'a, 'b, I: Copy + PartialEq>(i: Input<'a, I>, s: &'b [I])
 
     for j in 0..s.len() {
         if s[j] != d[j] {
-            return err::string(i, j, s);
+            return i.replace(&b[j..]).err(Error::expected(d[j]))
         }
     }
 
@@ -401,157 +402,162 @@ pub fn eof<I>(i: Input<I>) -> SimpleResult<I, ()> {
     if i.buffer().len() == 0 && i.is_last_slice() {
         i.ret(())
     } else {
-        i.err(err::unexpected())
+        i.err(Error::unexpected())
     }
 }
 
-/// Common error for the basic Chomp parsers, verbose version.
-///
-/// This is a verbose version of the common error for the basic Chomp parsers. It will contain
-/// information about what a parser expected or if it encountered something unexpected (in the
-/// case of user supplied predicates, eg. `satisfy`).
-///
-/// This is coupled with the state found in the error state of the `ParseResult` type.
-#[cfg(feature = "verbose_error")]
-#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
-pub enum Error<I> {
-    /// Expected a specific token
-    Expected(I),
-    /// Did not expect the token present in the input stream
-    Unexpected,
-    /// Expected a specific string of tokens
-    String(Vec<I>),
-}
+mod error {
+    use std::any;
+    use std::error;
+    use std::fmt;
 
-#[cfg(feature = "verbose_error")]
-impl<I> Error<I> {
-    /// Creates a new Unexpected error.
-    ///
-    /// Should be used when the error value is not important.
-    pub fn new() -> Self {
-        Error::Unexpected
-    }
-}
+    use debugtrace::Trace;
 
-#[cfg(feature = "verbose_error")]
-impl<I> fmt::Display for Error<I>
-  where I: fmt::Debug {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        match *self {
-            Error::Expected(ref c) => write!(f, "expected {:?}", *c),
-            Error::Unexpected      => write!(f, "unexpected"),
-            Error::String(ref s)   => write!(f, "expected {:?}", *s),
-        }
-    }
-}
-
-#[cfg(feature = "verbose_error")]
-impl<I: any::Any + fmt::Debug> error::Error for Error<I> {
-    fn description(&self) -> &str {
-        match *self {
-            Error::Expected(_) => "expected a certain token, received another",
-            Error::Unexpected  => "received an unexpected token",
-            Error::String(_)   =>
-                "expected a certain string of tokens, encountered an unexpected token",
+    #[cfg(feature="noop_error")]
+    use std::marker::PhantomData;
+    #[cfg(not(feature="noop_error"))]
+    use std::ops::Deref;
+
+    /// Empty type to eat the generic without printing
+    #[cfg(feature="noop_error")]
+    #[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+    struct Expected<I>(PhantomData<I>);
+
+    #[cfg(feature="noop_error")]
+    impl<I: fmt::Debug> fmt::Debug for Expected<I> {
+        fn fmt(&self, _f: &mut fmt::Formatter) -> fmt::Result {
+            // Intentionally empty
+            Ok(())
         }
     }
-}
-
-#[cfg(feature = "verbose_error")]
-mod err {
-    //! This is a private module to contain the constructors for the verbose error type.
-    //!
-    //! All constructors are #[inline(always)] and will construct the appropriate error type.
 
-    use input::Input;
-    use parse_result::ParseResult;
-    use super::Error;
+    /// `Some(T)` if it expected a specific token, `None` if it encountered something unexpected.
+    #[cfg(not(feature="noop_error"))]
+    #[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+    struct Expected<I>(Option<I>);
 
-    #[inline(always)]
-    pub fn unexpected<I>() -> Error<I> {
-        Error::Unexpected
-    }
+    #[cfg(not(feature="noop_error"))]
+    impl<I> Deref for Expected<I> {
+        type Target = Option<I>;
 
-    #[inline(always)]
-    pub fn expected<I>(i: I) -> Error<I> {
-        Error::Expected(i)
+        fn deref(&self) -> &Option<I> {
+            &self.0
+        }
     }
 
-
-    #[inline(always)]
-    pub fn string<'a, 'b, I, T>(i: Input<'a, I>, _offset: usize, expected: &'b [I])
-        -> ParseResult<'a, I, T, Error<I>>
-      where I: Copy {
-        i.err(Error::String(expected.to_vec()))
+    #[cfg(not(feature="noop_error"))]
+    impl<I: fmt::Debug> fmt::Debug for Expected<I> {
+        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+            match self.0 {
+                Some(ref c) => write!(f, "Expected({:?})", c),
+                None        => write!(f, "Unexpected"),
+            }
+        }
     }
-}
-
-/// Common error for the basic Chomp parsers, noop version.
-///
-/// An empty error type, it only indicates that an error occurred. The error state in the
-/// `ParseResult` type provides the position of the error.
-///
-/// This is coupled with the state found in the error state of the `ParseResult` type.
-#[cfg(not(feature = "verbose_error"))]
-#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
-pub struct Error<I>(PhantomData<I>);
 
-#[cfg(not(feature = "verbose_error"))]
-impl<I> Error<I> {
-    /// Creates a new Unexpected error.
+    /// Common error for the basic Chomp parsers.
     ///
-    /// Should be used when the error value is not important.
-    pub fn new() -> Self {
-        Error(PhantomData)
+    /// This is the common error for the basic Chomp parsers. It will contain information about what a
+    /// parser expected or if it encountered something unexpected (in the case of user supplied
+    /// predicates, eg. `satisfy`).
+    ///
+    /// This is coupled with the state found in the error state of the `ParseResult` type.
+    #[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
+    pub struct Error<I>(Trace<Expected<I>>);
+
+    #[cfg(feature="noop_error")]
+    impl<I> fmt::Display for Error<I>
+      where I: fmt::Debug {
+        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+            write!(f, "parse error")
+        }
     }
-}
 
-#[cfg(not(feature = "verbose_error"))]
-impl<I: fmt::Debug> fmt::Display for Error<I> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        write!(f, "generic parse error (chomp was compiled without --feature verbose_error)")
+    #[cfg(not(feature="noop_error"))]
+    impl<I> fmt::Display for Error<I>
+      where I: fmt::Debug {
+        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+            match self.0.as_ref() {
+                Some(ref c) => write!(f, "expected {:?}", *c),
+                None        => write!(f, "unexpected"),
+            }
+        }
     }
-}
 
-#[cfg(not(feature = "verbose_error"))]
-impl<I: any::Any + fmt::Debug> error::Error for Error<I> {
-    fn description(&self) -> &str {
-        "generic parse error (chomp was compiled without --feature verbose_error)"
+    #[cfg(feature="noop_error")]
+    impl<I: any::Any + fmt::Debug> error::Error for Error<I> {
+        fn description(&self) -> &str {
+            &"parse error"
+        }
     }
-}
 
-#[cfg(not(feature = "verbose_error"))]
-mod err {
-    //! This is a private module to contain the constructors for the smaller error type.
-    //!
-    //! All constructors are #[inline(always)], and will just noop the data.
+    #[cfg(not(feature="noop_error"))]
+    impl<I: any::Any + fmt::Debug> error::Error for Error<I> {
+        fn description(&self) -> &str {
+            match self.0.as_ref() {
+                Some(_) => "expected a certain token, received another",
+                None    => "received an unexpected token",
+            }
+        }
+    }
 
-    use std::marker::PhantomData;
+    #[cfg(feature="noop_error")]
+    macro_rules! create_error {
+        ($_e:expr) => { Error(Trace::new(Expected(PhantomData))) }
+    }
 
-    use input::Input;
-    use parse_result::ParseResult;
-    use super::Error;
+    #[cfg(not(feature="noop_error"))]
+    macro_rules! create_error {
+        ($e:expr) => { Error(Trace::new(Expected($e))) }
+    }
 
+    impl<I> Error<I> {
+        /// Creates a new Unexpected error.
+        ///
+        /// Should be used when the error value is not important.
+        #[inline(always)]
+        pub fn new() -> Self {
+            create_error!(None)
+        }
 
-    #[inline(always)]
-    pub fn unexpected<I>() -> Error<I> {
-        Error(PhantomData)
-    }
+        /// Creates a new Unexpected error.
+        ///
+        /// Should be used when the token was unexpected, as in the case of `satisfy` where a user
+        /// provided predicate is provided.
+        #[inline(always)]
+        pub fn unexpected() -> Self {
+            create_error!(None)
+        }
 
-    #[inline(always)]
-    pub fn expected<'a, I>(_: I) -> Error<I> {
-        Error(PhantomData)
-    }
+        /// Creates a new Expected error.
+        ///
+        /// Should be used when a specific token was expected.
+        #[inline(always)]
+        pub fn expected(_i: I) -> Self {
+            create_error!(Some(_i))
+        }
 
-    #[inline(always)]
-    pub fn string<'a, 'b, I, T>(i: Input<'a, I>, offset: usize, _expected: &'b [I])
-        -> ParseResult<'a, I, T, Error<I>>
-      where I: Copy {
-        use primitives::InputBuffer;
+        /// Returns `Some(&I)` if a specific token was expected, `None` otherwise.
+        ///
+        /// Will always yield `None` since `noop_error` is enabled.
+        #[inline]
+        #[cfg(feature="noop_error")]
+        pub fn expected_token(&self) -> Option<&I> {
+            None
+        }
 
-        let b = i.buffer();
+        /// Returns `Some(&I)` if a specific token was expected, `None` otherwise.
+        #[inline]
+        #[cfg(not(feature="noop_error"))]
+        pub fn expected_token(&self) -> Option<&I> {
+            self.0.as_ref()
+        }
 
-        i.replace(&b[offset..]).err(Error(PhantomData))
+        /// Returns a stack-trace to where the error was created.
+        #[cfg(feature="backtrace")]
+        pub fn trace(&self) -> Vec<::debugtrace::StackFrame> {
+            self.0.resolve()
+        }
     }
 }
 
@@ -561,7 +567,6 @@ mod test {
     use primitives::IntoInner;
     use primitives::State;
     use super::*;
-    use super::err;
     use {Input, SimpleResult};
 
     #[test]
@@ -610,7 +615,7 @@ mod test {
     fn token_test() {
         assert_eq!(token(new(DEFAULT, b""), b'a').into_inner(), State::Incomplete(1));
         assert_eq!(token(new(DEFAULT, b"ab"), b'a').into_inner(), State::Data(new(DEFAULT, b"b"), b'a'));
-        assert_eq!(token(new(DEFAULT, b"bb"), b'a').into_inner(), State::Error(b"bb", err::expected(b'a')));
+        assert_eq!(token(new(DEFAULT, b"bb"), b'a').into_inner(), State::Error(b"bb", Error::expected(b'a')));
     }
 
     #[test]
@@ -636,8 +641,8 @@ mod test {
     #[test]
     fn take_while1_test() {
         assert_eq!(take_while1(new(DEFAULT, b"abc"), |c| c != b'b').into_inner(), State::Data(new(DEFAULT, b"bc"), &b"a"[..]));
-        assert_eq!(take_while1(new(DEFAULT, b"bbc"), |c| c != b'b').into_inner(), State::Error(&b"bbc"[..], err::unexpected()));
-        assert_eq!(take_while1(new(END_OF_INPUT, b"bbc"), |c| c != b'b').into_inner(), State::Error(&b"bbc"[..], err::unexpected()));
+        assert_eq!(take_while1(new(DEFAULT, b"bbc"), |c| c != b'b').into_inner(), State::Error(&b"bbc"[..], Error::unexpected()));
+        assert_eq!(take_while1(new(END_OF_INPUT, b"bbc"), |c| c != b'b').into_inner(), State::Error(&b"bbc"[..], Error::unexpected()));
         assert_eq!(take_while1(new(END_OF_INPUT, b"abc"), |c| c != b'b').into_inner(), State::Data(new(END_OF_INPUT, b"bc"), &b"a"[..]));
         // TODO: Update when the incomplete type has been updated
         assert_eq!(take_while1(new(DEFAULT, b"acc"), |c| c != b'b').into_inner(), State::Incomplete(1));
@@ -666,4 +671,54 @@ mod test {
         assert_eq!(m2, 0);
         assert_eq!(n2, 0);
     }
+
+    #[test]
+    fn string_test() {
+        assert_eq!(string(new(DEFAULT, b"abc"), b"a").into_inner(), State::Data(new(DEFAULT, b"bc"), &b"a"[..]));
+        assert_eq!(string(new(DEFAULT, b"abc"), b"ab").into_inner(), State::Data(new(DEFAULT, b"c"), &b"ab"[..]));
+        assert_eq!(string(new(DEFAULT, b"abc"), b"abc").into_inner(), State::Data(new(DEFAULT, b""), &b"abc"[..]));
+        assert_eq!(string(new(DEFAULT, b"abc"), b"abcd").into_inner(), State::Incomplete(1));
+        assert_eq!(string(new(DEFAULT, b"abc"), b"abcde").into_inner(), State::Incomplete(2));
+        assert_eq!(string(new(DEFAULT, b"abc"), b"ac").into_inner(), State::Error(b"bc", Error::expected(b'b')));
+
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"a").into_inner(), State::Data(new(END_OF_INPUT, b"bc"), &b"a"[..]));
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"ab").into_inner(), State::Data(new(END_OF_INPUT, b"c"), &b"ab"[..]));
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"abc").into_inner(), State::Data(new(END_OF_INPUT, b""), &b"abc"[..]));
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"abcd").into_inner(), State::Incomplete(1));
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"abcde").into_inner(), State::Incomplete(2));
+        assert_eq!(string(new(END_OF_INPUT, b"abc"), b"ac").into_inner(), State::Error(b"bc", Error::expected(b'b')));
+    }
+
+    #[test]
+    #[cfg(not(feature = "noop_error"))]
+    fn error_test() {
+        let e = Error::<()>::new();
+        assert_eq!(e.expected_token(), None);
+        let e = Error::<()>::unexpected();
+        assert_eq!(e.expected_token(), None);
+        let e = Error::expected(b'a');
+        assert_eq!(e.expected_token(), Some(&b'a'));
+    }
+
+    #[test]
+    #[cfg(feature = "noop_error")]
+    fn noop_error_test() {
+        let e = Error::<()>::new();
+        assert_eq!(e.expected_token(), None);
+        let e = Error::<()>::unexpected();
+        assert_eq!(e.expected_token(), None);
+        let e = Error::expected(b'a');
+        assert_eq!(e.expected_token(), None);
+    }
+
+    #[test]
+    #[cfg(feature="backtrace")]
+    fn backtrace_test() {
+        let e = Error::<()>::new();
+
+        let trace = e.trace();
+        let this  = &trace[0];
+
+        assert!(this.name.as_ref().map(|n| n.contains("parsers::test::backtrace_test")).unwrap_or(false), "Expected trace to contain \"parsers::test::backtrace_test\", got: {:?}", this.name.as_ref());
+    }
 }


Test patch: