Repository: Marwes/combine (language: rust)

Issue:
`parse_lazy` has imprecise semantics
So on attempting to fix a couple of other parser combinators' behaviours on error, I've come to realise that `parse_lazy` doesn't have the right semantics to correctly support what we want.

Let's look at a motivating example.

```rust
let mut emptyok_then_emptyerr = (value(()).message("not expected"), char('x'));

assert_eq!(emptyok_then_emptyerr.parse(State::new("hi")),
    Err(ParseError {
       position: SourcePosition { line: 1, column: 1 },
       errors: vec![Error::Unexpected('h'.into()),
                    Error::Expected('x'.into())],
    }));

// assert fails: actual error contains the message "not expected"
```

Here we sequentially chain two parsers, the first of which returns `EmptyOk`, and the second returns `EmptyErr`. Now this combined tuple parser will return `EmptyErr`, meaning "no input was consumed, and one of my child parsers failed". However due to the semantics of `parse_lazy`, this will also imply "*the first* of my child parsers failed". Hence, when `add_error` is called the message "not expected" will be added, which is clearly wrong.

What's the fix? `parse_lazy` should not conflate "no input was consumed" with "first parser failed." So it seems like we have two options:

* Make `parse_lazy` semantics tighter. This will probably entail returning a separate flag "was actually lazy", which becomes the thing that specifies whether `add_error` should be called or not. (One thing which I'm not sure about in this scenario is whether the Consumed flag is still useful or not? Is it currently important anywhere other than for determining laziness?)

* Keep the semantics of `parse_lazy` but rewrite some current parsers so they are not lazy. This loses us some amount of speed. Notably the `tuple` and `then` combinators will have to become non-lazy.
Add a combinator which returns the elements of a stream between two points
```rust
stream_parser((skip_many(digit()), token('.'), skip_many(digit()))).parse("123.456+-")
// The output of the parser is a string. "123.456"
```

https://gitter.im/Marwes/combine?at=58a0813cf045df0a223a0f0c

There should probably two variants of this parser, one which accumulates the tokens of these parsers using `FromIterator` (similiar to `many`) and one which is zero copy (similiar to `take_while`)


Discussion / hints:

Fix patch:
diff --git a/.travis.yml b/.travis.yml
index 769545a9..cc8710f1 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -13,7 +13,6 @@ rust:
 - nightly
 - beta
 - stable
-- 1.17.0
 before_script:
 - |
   pip install 'travis-cargo<0.2' --user &&
diff --git a/CHANGELOG.md b/CHANGELOG.md
index eea66e89..b4f77beb 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,36 @@
+<a name="v3.0.0-alpha.1"></a>
+## v3.0.0-alpha.1 (2017-08-07)
+
+
+#### Features
+
+*   Remove the old State type and Positioner trait ([ae43f8ae](https://github.com/Marwes/combine/commit/ae43f8ae2b303aca3b5ae9fbb1a87475349f2745), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Teach the choice parser to take tuples ([96da7ee0](https://github.com/Marwes/combine/commit/96da7ee0cf8a112e60747a0be8a4dbd90efbecba), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Add the range_of parser ([7e692086](https://github.com/Marwes/combine/commit/7e69208650f7fdc75279370b193030b09ccdbc7a), closes [#83](https://github.com/Marwes/combine/issues/83), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Add map_token and map_range methods to ParseError ([2f92b296](https://github.com/Marwes/combine/commit/2f92b29669b618535bcd7533b7dd39b7daa8579b), closes [#86](https://github.com/Marwes/combine/issues/86))
+*   Allow ParseError to be used without the StreamOnce constraint ([520da8e8](https://github.com/Marwes/combine/commit/520da8e89f7162b4d6ba3a3bca05a05f3bd37999), breaks [#](https://github.com/Marwes/combine/issues/))
+
+#### Bug Fixes
+
+*   Remove depreceated items ([9107342a](https://github.com/Marwes/combine/commit/9107342a89a5efc664bac9c2919a93a992ca6809), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Don't forward tuple parsers to frunk to prevent a performance loss ([7e27c523](https://github.com/Marwes/combine/commit/7e27c523da46828b254ee4fc7c1f9750623e5aff))
+*   Add the correct errors after sequencing has returned EmptyOk ([54fecc62](https://github.com/Marwes/combine/commit/54fecc62938445aae15373a6b1ec7c4419582025), closes [#95](https://github.com/Marwes/combine/issues/95))
+*   Renamed SharedBufferedStream and BufferedStream to be less confusing ([3add407e](https://github.com/Marwes/combine/commit/3add407eecf886cc72ce05414d58a2b3b19a0bb9), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Add From<u8> for Info ([4cf8cff6](https://github.com/Marwes/combine/commit/4cf8cff64466519bf2d4a4dc1dcbe8deb449e004))
+*   Make the positions of slice streams harder to misuse ([f50ab9e2](https://github.com/Marwes/combine/commit/f50ab9e2f42ec2465368bfb11a60b2339b699fc4), closes [#104](https://github.com/Marwes/combine/issues/104), breaks [#](https://github.com/Marwes/combine/issues/))
+
+#### Breaking Changes
+
+*   Remove depreceated items ([9107342a](https://github.com/Marwes/combine/commit/9107342a89a5efc664bac9c2919a93a992ca6809), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Renamed SharedBufferedStream and BufferedStream to be less confusing ([3add407e](https://github.com/Marwes/combine/commit/3add407eecf886cc72ce05414d58a2b3b19a0bb9), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Remove the old State type and Positioner trait ([ae43f8ae](https://github.com/Marwes/combine/commit/ae43f8ae2b303aca3b5ae9fbb1a87475349f2745), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Teach the choice parser to take tuples ([96da7ee0](https://github.com/Marwes/combine/commit/96da7ee0cf8a112e60747a0be8a4dbd90efbecba), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Add the range_of parser ([7e692086](https://github.com/Marwes/combine/commit/7e69208650f7fdc75279370b193030b09ccdbc7a), closes [#83](https://github.com/Marwes/combine/issues/83), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Make the positions of slice streams harder to misuse ([f50ab9e2](https://github.com/Marwes/combine/commit/f50ab9e2f42ec2465368bfb11a60b2339b699fc4), closes [#104](https://github.com/Marwes/combine/issues/104), breaks [#](https://github.com/Marwes/combine/issues/))
+*   Allow ParseError to be used without the StreamOnce constraint ([520da8e8](https://github.com/Marwes/combine/commit/520da8e89f7162b4d6ba3a3bca05a05f3bd37999), breaks [#](https://github.com/Marwes/combine/issues/))
+
+
+
 <a name="v2.5.0"></a>
 ## v2.5.0 (2017-08-07)
 
diff --git a/Cargo.toml b/Cargo.toml
index ae352297..b5ab0b86 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 
 name = "combine"
-version = "2.5.0"
+version = "3.0.0-alpha.1"
 authors = ["Markus Westerlind <marwes91@gmail.com>"]
 
 description = "Fast parser combinators on arbitrary streams with zero-copy support."
@@ -49,4 +49,4 @@ harness = false
 required-features = ["mp4"]
 
 [package.metadata.docs.rs]
-features = ["doc"]
\ No newline at end of file
+features = ["doc"]
diff --git a/README.md b/README.md
index b7621b2c..129a04c0 100644
--- a/README.md
+++ b/README.md
@@ -1,5 +1,5 @@
 # combine
-[![Build Status](https://travis-ci.org/Marwes/combine.svg?branch=master)](https://travis-ci.org/Marwes/combine) [![Docs v1](https://docs.rs/combine/badge.svg?version=^1)](https://docs.rs/combine/^1) [![Docs](https://docs.rs/combine/badge.svg)](https://docs.rs/combine) [![Gitter](https://badges.gitter.im/Join%20Chat.svg)](https://gitter.im/Marwes/combine?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge)
+[![Build Status](https://travis-ci.org/Marwes/combine.svg?branch=master)](https://travis-ci.org/Marwes/combine) [![Docs v2](https://docs.rs/combine/badge.svg?version=^1)](https://docs.rs/combine/^2) [![Docs](https://docs.rs/combine/badge.svg)](https://docs.rs/combine) [![Gitter](https://badges.gitter.im/Join%20Chat.svg)](https://gitter.im/Marwes/combine?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge)
 
 An implementation of parser combinators for Rust, inspired by the Haskell library [Parsec](https://hackage.haskell.org/package/parsec). As in Parsec the parsers are [LL(1)](https://en.wikipedia.org/wiki/LL_parser) by default but they can opt-in to arbitrary lookahead using the [try  combinator](https://marwes.github.io/combine/combine/fn.try.html).
 
@@ -7,11 +7,15 @@ An implementation of parser combinators for Rust, inspired by the Haskell librar
 
 ```rust
 extern crate combine;
-use combine::{many, Parser};
-use combine::char::letter;
+use combine::{many1, Parser, sep_by};
+use combine::char::{letter, space};
 
-let result = many(letter()).parse("hello world");
-assert_eq!(result, Ok(("hello".to_string(), " world")));
+let word = many1(letter());
+
+let mut parser = sep_by(word, space())
+    .map(|mut words: Vec<String>| words.pop());
+let result = parser.parse("Pick up that word!");
+assert_eq!(result, Ok((Some("word".to_string()), "!")));
 ```
 
 Larger examples can be found in the [tests][tests] and [benches][benches] folders.
@@ -37,7 +41,7 @@ If you end up trying it I welcome any feedback from your experience with it. I a
 
 ### Why does my errors contain inscrutable positions?
 
-Since `combine` aims to crate parsers with little to no overhead streams over `&str` and `&[T]` do not carry any extra position information but instead only rely on comparing the pointer of the buffer to check which `Stream` is further ahead than another `Stream`. To retrieve a better position, either call `translate_position` on the `ParseError` or wrap your stream with `State`.
+Since `combine` aims to crate parsers with little to no overhead streams over `&str` and `&[T]` do not carry any extra position information but instead only rely on comparing the pointer of the buffer to check which `Stream` is further ahead than another `Stream`. To retrieve a better position, either call `translate_position` on the `PointerOffset` which represents the position or wrap your stream with `State`.
 
 ## Extra
 
@@ -47,6 +51,9 @@ You can find older versions of combine (parser-combinators) [here](https://crate
 
 ## Contributing
 
+Current master is the 3.0.0 branch. If you want to submit a fix or feature to the 2.x version of combine then
+do so to the 2.x branch or submit the PR to master and request that it be backported.
+
 The easiest way to contribute is to just open an issue about any problems you encounter using combine but if you are interested in adding something to the library here is a list of some of the easier things to work on to get started.
 
 * __Add additional parsers__ There is a list of parsers which aren't implemented [here][add parsers] but if you have a suggestion for another parser just leave a suggestion on the issue itself.
@@ -59,6 +66,18 @@ The easiest way to contribute is to just open an issue about any problems you en
 
 Here is a list containing most of the breaking changes in older versions of combine (parser-combinators).
 
+### 3.0.0-alpha.1
+
+* Deprecated items have been changed or removed. Upgrade to the latest version of 2.x first and fix all
+    deprecations before upgrading to 3.x.
+* If you have written the `ParseError<I>` explicitly it needs to be changed to `StreamError<I>` as
+    `ParseError`s type signature have changed slightly. Function calls should not be affected however.
+* Parsers now return `Tracked<StreamError<I>>` instead of plain `ParseError<I>`. `Tracked` is an internal
+    wrapper which should just be constructed via `From::from` or `Into::into`. If you return errors explicitly
+    somewhere you will need to add `.into()` on the errors to wrap them.
+* A few other changes should be detected and fixed easily by simply compiling and fixing the compile errors.
+    See [CHANGELOG.md](https://github.com/Marwes/combine/blob/master/CHANGELOG.md) for a complete list of breaking changes.
+
 ### 2.0.0-beta3
 
 * `parse_state` renamed to `parse_stream`.
diff --git a/benches/http.rs b/benches/http.rs
index 4c835c96..510b32e6 100644
--- a/benches/http.rs
+++ b/benches/http.rs
@@ -60,7 +60,7 @@ fn is_http_version(c: u8) -> bool {
     c >= b'0' && c <= b'9' || c == b'.'
 }
 
-fn parse_http_request(input: &[u8]) -> Result<((Request, Vec<Header>), &[u8]), ParseError<&[u8]>> {
+fn parse_http_request(input: &[u8]) -> Result<((Request, Vec<Header>), &[u8]), StreamError<&[u8]>> {
     // Making a closure, because parser instances cannot be reused
     let end_of_line = || (token(b'\r'), token(b'\n')).map(|_| b'\r').or(token(b'\n'));
 
diff --git a/benches/json.rs b/benches/json.rs
index befa777e..8c41a9f6 100644
--- a/benches/json.rs
+++ b/benches/json.rs
@@ -11,10 +11,11 @@ use std::path::Path;
 use bencher::{black_box, Bencher};
 
 use pc::primitives::{BufferedStream, Consumed, IteratorStream, ParseError, ParseResult, Parser,
-                     State, Stream};
+                     Stream};
+use pc::char::{char, digit, spaces, string, Spaces};
 use pc::combinator::{any, between, choice, many, optional, parser, satisfy, sep_by, Expected,
                      FnParser, Skip, many1};
-use pc::char::{char, digit, spaces, string, Spaces};
+use pc::state::{SourcePosition, State};
 
 #[derive(PartialEq, Debug)]
 enum Value {
@@ -119,10 +120,9 @@ where
         });
         match c {
             '\\' => input.combine(|input| back_slash_char.parse_stream(input)),
-            '"' => Err(Consumed::Empty(ParseError::from_errors(
-                input.into_inner().position(),
-                Vec::new(),
-            ))),
+            '"' => Err(Consumed::Empty(
+                ParseError::from_errors(input.into_inner().position(), Vec::new()).into(),
+            )),
             _ => Ok((c, input)),
         }
     }
@@ -152,21 +152,21 @@ where
     }
     #[allow(unconditional_recursion)]
     fn value_(input: I) -> ParseResult<Value, I> {
-        let mut array = between(
+        let array = between(
             lex(char('[')),
             lex(char(']')),
             sep_by(Json::<I>::value(), lex(char(','))),
         ).map(Value::Array);
 
-        choice::<[&mut Parser<Input = I, Output = Value>; 7], _>([
-            &mut Json::<I>::string().map(Value::String),
-            &mut Json::<I>::object(),
-            &mut array,
-            &mut Json::<I>::number().map(Value::Number),
-            &mut lex(string("false").map(|_| Value::Bool(false))),
-            &mut lex(string("true").map(|_| Value::Bool(true))),
-            &mut lex(string("null").map(|_| Value::Null)),
-        ]).parse_lazy(input)
+        choice((
+            Json::<I>::string().map(Value::String),
+            Json::<I>::object(),
+            array,
+            Json::<I>::number().map(Value::Number),
+            lex(string("false").map(|_| Value::Bool(false))),
+            lex(string("true").map(|_| Value::Bool(true))),
+            lex(string("null").map(|_| Value::Null)),
+        )).parse_lazy(input)
             .into()
     }
 }
@@ -238,9 +238,12 @@ fn bench_buffered_json(bencher: &mut Bencher) {
         .and_then(|mut file| file.read_to_string(&mut data))
         .unwrap();
     bencher.iter(|| {
-        let buffer = BufferedStream::new(IteratorStream::new(data.chars()), 1);
+        let buffer = BufferedStream::new(State::new(IteratorStream::new(data.chars())), 1);
         let mut parser = Json::value();
-        match parser.parse(State::new(buffer.as_stream())) {
+        match parser.parse(State::with_positioner(
+            buffer.as_stream(),
+            SourcePosition::default(),
+        )) {
             Ok((Value::Array(v), _)) => {
                 black_box(v);
             }
diff --git a/benches/mp4.rs b/benches/mp4.rs
index 69c89219..40649c04 100644
--- a/benches/mp4.rs
+++ b/benches/mp4.rs
@@ -34,7 +34,7 @@ enum MP4Box<'a> {
     Unknown,
 }
 
-fn parse_mp4(data: &[u8]) -> Result<(Vec<MP4Box>, &[u8]), ParseError<&[u8]>> {
+fn parse_mp4(data: &[u8]) -> Result<(Vec<MP4Box>, &[u8]), StreamError<&[u8]>> {
     let brand_name = || take(4).and_then(from_utf8);
     let filetype_box = (
         range(&b"ftyp"[..]),
@@ -67,7 +67,7 @@ fn parse_mp4(data: &[u8]) -> Result<(Vec<MP4Box>, &[u8]), ParseError<&[u8]>> {
 fn run_test(b: &mut Bencher, data: &[u8]) {
     b.iter(|| match parse_mp4(data) {
         Ok(x) => black_box(x),
-        Err(err) => panic!("{:?}", err),
+        Err(err) => panic!("{}", err.map_range(|bytes| format!("{:?}", bytes))),
     });
 }
 
diff --git a/src/byte.rs b/src/byte.rs
index 23998bb7..f88881e3 100644
--- a/src/byte.rs
+++ b/src/byte.rs
@@ -5,8 +5,7 @@ use std::marker::PhantomData;
 use self::ascii::AsciiChar;
 
 use combinator::{satisfy, skip_many, token, tokens, Expected, Satisfy, SkipMany, Token, With};
-use primitives::{ConsumedResult, Info, ParseError, Parser, RangeStream, Stream};
-use range::take;
+use primitives::{ConsumedResult, Info, Parser, Stream, StreamError, Tracked};
 
 /// Parses a byteacter and succeeds if the byteacter is equal to `c`.
 ///
@@ -281,8 +280,8 @@ where
             .parse_lazy(input)
             .map(|bytes| bytes.as_slice())
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        tokens(|&l, r| l == r, Info::Range(self.0), self.0.iter()).add_error(errors)
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        tokens::<_, _, I>(|&l, r| l == r, Info::Range(self.0), self.0.iter()).add_error(errors)
     }
 }
 
@@ -330,9 +329,9 @@ where
         let cmp = &mut self.1;
         tokens(|&l, r| cmp(l, r), Info::Range(self.0), self.0).parse_lazy(input)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         let cmp = &mut self.1;
-        tokens(|&l, r| cmp(l, r), Info::Range(self.0), self.0.iter()).add_error(errors)
+        tokens::<_, _, I>(|&l, r| cmp(l, r), Info::Range(self.0), self.0.iter()).add_error(errors)
     }
 }
 
@@ -368,6 +367,8 @@ where
 /// Parsers for decoding numbers in big-endian or little-endian order.
 pub mod num {
     use super::*;
+    use primitives::RangeStream;
+    use range::take;
 
     use byteorder::{ByteOrder, BE, LE};
 
@@ -392,8 +393,8 @@ pub mod num {
                 fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
                     take(::std::mem::size_of::<Self::Output>()).map(B::$read_name).parse_lazy(input)
                 }
-                fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-                    take(::std::mem::size_of::<Self::Output>()).add_error(errors)
+                fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+                    take::<I>(::std::mem::size_of::<Self::Output>()).add_error(errors)
                 }
             }
 
diff --git a/src/char.rs b/src/char.rs
index 46790b19..084e520c 100644
--- a/src/char.rs
+++ b/src/char.rs
@@ -1,4 +1,4 @@
-use primitives::{ConsumedResult, ParseError, Parser, Stream};
+use primitives::{ConsumedResult, Parser, Stream, StreamError, Tracked};
 use combinator::{satisfy, skip_many, token, tokens, Expected, Satisfy, SkipMany, Token, With};
 use std::marker::PhantomData;
 
@@ -308,8 +308,8 @@ where
             .parse_lazy(input)
             .map(|_| self.0)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        tokens(eq, self.0.into(), self.0.chars()).add_error(errors)
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        tokens::<_, _, I>(eq, self.0.into(), self.0.chars()).add_error(errors)
     }
 }
 
@@ -351,8 +351,8 @@ where
             .parse_lazy(input)
             .map(|_| self.0)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        tokens(&mut self.1, self.0.into(), self.0.chars()).add_error(errors)
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        tokens::<_, _, I>(&mut self.1, self.0.into(), self.0.chars()).add_error(errors)
     }
 }
 
@@ -382,7 +382,8 @@ where
 #[cfg(test)]
 mod tests {
     use super::*;
-    use primitives::{Error, ParseError, Parser, SourcePosition, State};
+    use primitives::{Error, ParseError, Parser};
+    use state::{SourcePosition, State};
 
     #[test]
     fn space_error() {
diff --git a/src/combinator.rs b/src/combinator.rs
index 0fd65836..3dc7d6c8 100644
--- a/src/combinator.rs
+++ b/src/combinator.rs
@@ -1,9 +1,12 @@
 use std::iter::FromIterator;
 use std::marker::PhantomData;
-use primitives::{Consumed, ConsumedResult, Error, Info, ParseError, ParseResult, Parser, Stream,
-                 StreamOnce};
+
+use primitives::{Consumed, ConsumedResult, Error, Info, ParseError, ParseResult, Parser,
+                 Positioned, Stream, StreamError, StreamOnce, Tracked};
 use primitives::FastResult::*;
 
+use ErrorOffset;
+
 macro_rules! impl_parser {
     ($name: ident ($first: ident, $($ty_var: ident),*), $inner_type: ty) => {
     #[derive(Clone)]
@@ -25,7 +28,7 @@ macro_rules! impl_parser {
                       input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
             self.0.parse_lazy(input)
         }
-        fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
+        fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
             self.0.add_error(error)
         }
     }
@@ -46,7 +49,7 @@ where
         let position = input.position();
         match input.uncons() {
             Ok(x) => ConsumedOk((x, input)),
-            Err(err) => EmptyErr(ParseError::new(position, err)),
+            Err(err) => EmptyErr(ParseError::new(position, err).into()),
         }
     }
 }
@@ -90,9 +93,9 @@ where
     match input.uncons() {
         Ok(c) => match predicate(c.clone()) {
             Some(c) => ConsumedOk((c, input)),
-            None => EmptyErr(ParseError::empty(position)),
+            None => EmptyErr(ParseError::empty(position).into()),
         },
-        Err(err) => EmptyErr(ParseError::new(position, err)),
+        Err(err) => EmptyErr(ParseError::new(position, err).into()),
     }
 }
 
@@ -212,8 +215,9 @@ where
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<I::Item, I> {
         satisfy_impl(input, |c| if c == self.c { Some(c) } else { None })
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        errors
+            .error
             .errors
             .push(Error::Expected(Info::Token(self.c.clone())));
     }
@@ -278,7 +282,7 @@ where
                             let error = ParseError::from_errors(start, errors);
                             ConsumedErr(error)
                         } else {
-                            EmptyErr(ParseError::empty(start))
+                            EmptyErr(ParseError::empty(start).into())
                         };
                     }
                     consumed = true;
@@ -286,11 +290,11 @@ where
                 }
                 Err(error) => {
                     return error.combine_consumed(|mut error| {
-                        error.position = start;
+                        error.error.position = start;
                         if consumed {
-                            ConsumedErr(error)
+                            ConsumedErr(error.error)
                         } else {
-                            EmptyErr(error)
+                            EmptyErr(error.into())
                         }
                     })
                 }
@@ -302,8 +306,10 @@ where
             EmptyOk((self.tokens.clone(), input))
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        errors.add_error(Error::Expected(self.expected.clone()));
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        errors
+            .error
+            .add_error(Error::Expected(self.expected.clone()));
     }
 }
 
@@ -323,7 +329,11 @@ where
 ///     .parse("AbC")
 ///     .map(|x| x.0.as_str());
 /// assert_eq!(result, Ok("abc"));
-/// let result = tokens(|&l, r| (if l < r { r - l } else { l - r }) <= 2, Info::Range(&b"025"[..]), &b"025"[..])
+/// let result = tokens(
+///     |&l, r| (if l < r { r - l } else { l - r }) <= 2,
+///     Info::Range(&b"025"[..]),
+///     &b"025"[..]
+/// )
 ///     .parse(&b"123"[..])
 ///     .map(|x| x.0);
 /// assert_eq!(result, Ok(&b"025"[..]));
@@ -371,7 +381,7 @@ where
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::primitives::SourcePosition;
+/// # use combine::state::SourcePosition;
 /// # fn main() {
 /// let result = (position(), token('!'), position())
 ///     .parse(State::new("!"))
@@ -391,47 +401,6 @@ where
     }
 }
 
-#[derive(Clone)]
-pub struct Choice<S, P>(S, PhantomData<P>);
-
-impl<I, O, S, P> Parser for Choice<S, P>
-where
-    I: Stream,
-    S: AsMut<[P]>,
-    P: Parser<Input = I, Output = O>,
-{
-    type Input = I;
-    type Output = O;
-    #[inline]
-    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
-        let mut empty_err = None;
-        for p in AsMut::as_mut(&mut self.0) {
-            match p.parse_lazy(input.clone()) {
-                consumed_err @ ConsumedErr(_) => return consumed_err,
-                EmptyErr(err) => {
-                    empty_err = match empty_err {
-                        None => Some(err),
-                        Some(prev_err) => Some(prev_err.merge(err)),
-                    };
-                }
-                ok @ ConsumedOk(_) | ok @ EmptyOk(_) => return ok,
-            }
-        }
-        EmptyErr(match empty_err {
-            None => ParseError::new(
-                input.position(),
-                Error::Message("parser choice is empty".into()),
-            ),
-            Some(err) => err,
-        })
-    }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        for p in self.0.as_mut() {
-            p.add_error(error);
-        }
-    }
-}
-
 #[derive(Clone)]
 pub struct OneOf<T, I>
 where
@@ -455,9 +424,11 @@ where
         satisfy(|c| self.tokens.clone().into_iter().any(|t| t == c)).parse_lazy(input)
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         for expected in self.tokens.clone() {
-            errors.add_error(Error::Expected(Info::Token(expected)));
+            errors
+                .error
+                .add_error(Error::Expected(Info::Token(expected)));
         }
     }
 }
@@ -516,7 +487,8 @@ where
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::primitives::{BytePosition, Error, Info};
+/// # use combine::primitives::{Error, Info};
+/// # use combine::state::State;
 /// # fn main() {
 /// let mut parser = many1(none_of(b"abc".iter().cloned()));
 /// let result = parser.parse(State::new(&b"xyb"[..]))
@@ -525,7 +497,7 @@ where
 ///
 /// let result = parser.parse(State::new(&b"ab"[..]));
 /// assert_eq!(result, Err(ParseError {
-///     position: BytePosition { position: 0 },
+///     position: 0,
 ///     errors: vec![
 ///         Error::Unexpected(Info::Token(b'a')),
 ///     ]
@@ -567,7 +539,7 @@ where
         iter.into_result_fast(value)
     }
 
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(error)
     }
 }
@@ -577,7 +549,7 @@ where
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::primitives::{BytePosition, Error, Info};
+/// # use combine::primitives::{Error, Info};
 /// # fn main() {
 /// let mut parser = count(2, token(b'a'));
 ///
@@ -598,6 +570,263 @@ where
     }
 }
 
+
+/// Takes a number of parsers and tries to apply them each in order.
+/// Fails if all the parsers fails or if an applied parser consumes input before failing.
+///
+/// ```
+/// # #[macro_use]
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::{digit, letter, string};
+/// # use combine::primitives::Error;
+/// # fn main() {
+/// let mut parser = choice!(
+///     many1(digit()),
+///     string("let").map(|s| s.to_string()),
+///     many1(letter()));
+/// assert_eq!(parser.parse("let"), Ok(("let".to_string(), "")));
+/// assert_eq!(parser.parse("123abc"), Ok(("123".to_string(), "abc")));
+/// assert!(parser.parse(":123").is_err());
+/// # }
+/// ```
+#[macro_export]
+macro_rules! choice {
+    ($first : expr) => {
+        $first
+    };
+    ($first : expr, $($rest : expr),+) => {
+        $first.or(choice!($($rest),+))
+    }
+}
+
+/// `ChoiceParser` represents a parser which may parse one of several different choices depending
+/// on the input.
+///
+/// This is an internal trait used to overload the `choice` function.
+pub trait ChoiceParser {
+    type Input: Stream;
+    type Output;
+    fn parse_choice(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input>;
+    fn add_error_choice(&mut self, error: &mut Tracked<StreamError<Self::Input>>);
+}
+
+impl<'a, P> ChoiceParser for &'a mut P
+where
+    P: ?Sized + ChoiceParser,
+{
+    type Input = P::Input;
+    type Output = P::Output;
+
+    #[inline(always)]
+    fn parse_choice(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        (**self).parse_choice(input)
+    }
+    fn add_error_choice(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        (**self).add_error_choice(error)
+    }
+}
+
+macro_rules! merge {
+    ($head: ident) => {
+        $head.error
+    };
+    ($head: ident $($tail: ident)+) => {
+        $head.error.merge(merge!($($tail)+))
+    };
+}
+
+macro_rules! do_choice {
+    ($input: ident ( ) $($parser: ident $error: ident)+) => { {
+        let mut error = Tracked::from(merge!($($error)+));
+        // If offset != 1 then the nested parser is a sequence of parsers where 1 or
+        // more parsers returned `EmptyOk` before the parser finally failed with
+        // `EmptyErr`. Since we lose the offsets of the nested parsers when we merge
+        // the errors we must first extract the errors before we do the merge.
+        // If the offset == 0 on the other hand (which should be the common case) then
+        // we can delay the addition of the error since we know for certain that only
+        // the first parser in the sequence were tried
+        $(
+            if $error.offset != ErrorOffset(1) {
+                error.offset = $error.offset;
+                $parser.add_error(&mut error);
+                error.offset = ErrorOffset(0);
+            }
+        )+
+        EmptyErr(error)
+    } };
+    ($input: ident ( $head: ident $($tail: ident)* ) $($all: ident)*) => { {
+        let parser = $head;
+        match parser.parse_lazy($input.clone()) {
+            ConsumedOk(x) => ConsumedOk(x),
+            EmptyOk(x) => EmptyOk(x),
+            ConsumedErr(err) => ConsumedErr(err),
+            EmptyErr($head) => do_choice!($input ( $($tail)* ) $($all)* parser $head),
+        } }
+    }
+}
+
+macro_rules! tuple_choice_parser {
+    ($head: ident) => {
+    };
+    ($head: ident $($id: ident)+) => {
+        tuple_choice_parser_inner!($head $($id)+);
+        tuple_choice_parser!($($id)+);
+    };
+}
+
+macro_rules! tuple_choice_parser_inner {
+    ($($id: ident)+) => {
+        #[allow(non_snake_case)]
+        impl<Input, Output $(,$id)+> ChoiceParser for ($($id),+)
+        where
+            Input: Stream,
+            $($id: Parser<Input = Input, Output = Output>),+
+        {
+            type Input = Input;
+            type Output = Output;
+            #[inline]
+            fn parse_choice(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+                let ($(ref mut $id),+) = *self;
+                do_choice!(input ( $($id)+ ) )
+            }
+            fn add_error_choice(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+                if error.offset != ErrorOffset(0) {
+                    let ($(ref mut $id),+) = *self;
+                    $(
+                        $id.add_error(error);
+                    )+
+                }
+            }
+        }
+    }
+}
+
+tuple_choice_parser!(A B C D E F G H I J K L M N O P Q R S T U V X Y Z);
+
+macro_rules! array_choice_parser {
+    ($($t: tt)+) => {
+        $(
+        impl<P> ChoiceParser for [P; $t]
+        where
+            P: Parser,
+        {
+            type Input = P::Input;
+            type Output = P::Output;
+
+            #[inline(always)]
+            fn parse_choice(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+                self[..].parse_choice(input)
+            }
+            fn add_error_choice(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+                self[..].add_error_choice(error)
+            }
+        }
+        )+
+    };
+}
+
+array_choice_parser!(
+    0 1 2 3 4 5 6 7 8 9
+    10 11 12 13 14 15 16 17 18 19
+    20 21 22 23 24 25 26 27 28 29
+    30 31 32
+    );
+
+#[derive(Clone)]
+pub struct Choice<P>(P);
+
+impl<P> Parser for Choice<P>
+where
+    P: ChoiceParser,
+{
+    type Input = P::Input;
+    type Output = P::Output;
+
+    #[inline(always)]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        self.0.parse_choice(input)
+    }
+
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        self.0.add_error_choice(error)
+    }
+}
+
+impl<I, O, P> ChoiceParser for [P]
+where
+    I: Stream,
+    P: Parser<Input = I, Output = O>,
+{
+    type Input = I;
+    type Output = O;
+    #[inline]
+    fn parse_choice(&mut self, input: I) -> ConsumedResult<O, I> {
+        let mut prev_err = None;
+        let mut last_parser_having_non_1_offset = 0;
+        for i in 0..self.len() {
+            match self[i].parse_lazy(input.clone()) {
+                consumed_err @ ConsumedErr(_) => return consumed_err,
+                EmptyErr(err) => {
+                    prev_err = match prev_err {
+                        None => Some(err),
+                        Some(mut prev_err) => {
+                            if prev_err.offset != ErrorOffset(1) {
+                                // First add the errors of all the preceding parsers which did not
+                                // have a sequence of parsers returning `EmptyOk` before failing
+                                // with `EmptyErr`.
+                                let offset = prev_err.offset;
+                                for p in &mut self[last_parser_having_non_1_offset..(i - 1)] {
+                                    prev_err.offset = ErrorOffset(1);
+                                    p.add_error(&mut prev_err);
+                                }
+                                // Then add the errors if the current parser
+                                prev_err.offset = offset;
+                                self[i - 1].add_error(&mut prev_err);
+                                last_parser_having_non_1_offset = i;
+                            }
+                            Some(
+                                Tracked {
+                                    error: prev_err.error.merge(err.error),
+                                    offset: err.offset,
+                                }
+                            )
+                        }
+                    };
+                }
+                ok @ ConsumedOk(_) | ok @ EmptyOk(_) => return ok,
+            }
+        }
+        EmptyErr(match prev_err {
+            None => ParseError::new(
+                input.position(),
+                Error::Message("parser choice is empty".into()),
+            ).into(),
+            Some(mut prev_err) => {
+                if prev_err.offset != ErrorOffset(1) {
+                    let offset = prev_err.offset;
+                    let len = self.len();
+                    for p in &mut self[last_parser_having_non_1_offset..(len - 1)] {
+                        prev_err.offset = ErrorOffset(1);
+                        p.add_error(&mut prev_err);
+                    }
+                    prev_err.offset = offset;
+                    self.last_mut().unwrap().add_error(&mut prev_err);
+                    prev_err.offset = ErrorOffset(0);
+                }
+                prev_err
+            }
+        })
+    }
+    fn add_error_choice(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        if error.offset != ErrorOffset(0) {
+            for p in self {
+                p.add_error(error);
+            }
+        }
+    }
+}
+
 pub type SkipCount<P> = skip_count::SkipCount<P>;
 parser!{
     #[derive(Clone)]
@@ -607,7 +836,7 @@ parser!{
     /// ```
     /// # extern crate combine;
     /// # use combine::*;
-    /// # use combine::primitives::{BytePosition, Error, Info};
+    /// # use combine::primitives::{Error, Info};
     /// # fn main() {
     /// let mut parser = skip_count(2, token(b'a'));
     ///
@@ -644,16 +873,17 @@ where
     fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
         let mut iter = self.parser.by_ref().iter(input);
         let mut len = 0usize;
-        let value = iter.by_ref().take(self.max).inspect(|_| { len += 1 }).collect();
+        let value = iter.by_ref().take(self.max).inspect(|_| len += 1).collect();
         if len < self.min {
-            let message = Error::Message(format!("expected {} more elements", self.min - len).into());
+            let message =
+                Error::Message(format!("expected {} more elements", self.min - len).into());
             ConsumedErr(ParseError::new(iter.input.position(), message))
         } else {
             iter.into_result_fast(value)
         }
     }
 
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(error)
     }
 }
@@ -663,7 +893,7 @@ where
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::primitives::{BytePosition, Error, Info};
+/// # use combine::primitives::{Error, Info};
 /// # fn main() {
 /// let mut parser = count_min_max(2, 2, token(b'a'));
 ///
@@ -725,21 +955,28 @@ parser!{
     }
 }
 
-/// Takes an array of parsers and tries to apply them each in order.
+/// Takes a tuple, a slice or an array of parsers and tries to apply them each in order.
 /// Fails if all the parsers fails or if an applied parser consumes input before failing.
 ///
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::char::string;
-/// # use combine::primitives::Error;
+/// # use combine::char::{digit, string};
 /// # fn main() {
-/// let mut parser = choice([string("Apple"), string("Banana"), string("Orange")]);
-/// assert_eq!(parser.parse("Banana"), Ok(("Banana", "")));
-/// assert_eq!(parser.parse("Orangexx"), Ok(("Orange", "xx")));
+/// // `choice` is overloaded on tuples so that different types of parsers can be used
+/// // (each parser must still have the same input and output types)
+/// let mut parser = choice((
+///     string("Apple").map(|s| s.to_string()),
+///     many1(digit()),
+///     string("Orange").map(|s| s.to_string()),
+/// ));
+/// assert_eq!(parser.parse("1234"), Ok(("1234".to_string(), "")));
+/// assert_eq!(parser.parse("Orangexx"), Ok(("Orange".to_string(), "xx")));
 /// assert!(parser.parse("Appl").is_err());
 /// assert!(parser.parse("Pear").is_err());
 ///
+/// // If arrays or slices are used then all parsers must have the same type
+/// // (`string` in this case)
 /// let mut parser2 = choice([string("one"), string("two"), string("three")]);
 /// // Fails as the parser for "two" consumes the first 't' before failing
 /// assert!(parser2.parse("three").is_err());
@@ -750,41 +987,11 @@ parser!{
 /// # }
 /// ```
 #[inline(always)]
-pub fn choice<S, P>(ps: S) -> Choice<S, P>
+pub fn choice<P>(ps: P) -> Choice<P>
 where
-    S: AsMut<[P]>,
-    P: Parser,
+    P: ChoiceParser,
 {
-    Choice(ps, PhantomData)
-}
-
-/// Takes a number of parsers and tries to apply them each in order.
-/// Fails if all the parsers fails or if an applied parser consumes input before failing.
-///
-/// ```
-/// # #[macro_use]
-/// # extern crate combine;
-/// # use combine::*;
-/// # use combine::char::{digit, letter, string};
-/// # use combine::primitives::Error;
-/// # fn main() {
-/// let mut parser = choice!(
-///     many1(digit()),
-///     string("let").map(|s| s.to_string()),
-///     many1(letter()));
-/// assert_eq!(parser.parse("let"), Ok(("let".to_string(), "")));
-/// assert_eq!(parser.parse("123abc"), Ok(("123".to_string(), "abc")));
-/// assert!(parser.parse(":123").is_err());
-/// # }
-/// ```
-#[macro_export]
-macro_rules! choice {
-    ($first : expr) => {
-        $first
-    };
-    ($first : expr, $($rest : expr),+) => {
-        $first.or(choice!($($rest),+))
-    }
+    Choice(ps)
 }
 
 #[derive(Clone)]
@@ -799,10 +1006,10 @@ where
     type Output = ();
     #[inline]
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<(), I> {
-        EmptyErr(ParseError::empty(input.position()))
+        EmptyErr(ParseError::empty(input.position()).into())
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.errors.push(Error::Unexpected(self.0.clone()));
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        errors.error.errors.push(Error::Unexpected(self.0.clone()));
     }
 }
 /// Always fails with `message` as an unexpected error.
@@ -909,12 +1116,14 @@ where
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<(), I> {
         match input.clone().uncons() {
             Err(ref err) if *err == Error::end_of_input() => EmptyOk(((), input)),
-            _ => EmptyErr(ParseError::empty(input.position())),
+            _ => EmptyErr(ParseError::empty(input.position()).into()),
         }
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        errors.add_error(Error::Expected("end of input".into()))
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        errors
+            .error
+            .add_error(Error::Expected("end of input".into()))
     }
 }
 
@@ -923,12 +1132,13 @@ where
 /// ```
 /// # extern crate combine;
 /// # use combine::*;
-/// # use combine::primitives::{Error, Positioner};
+/// # use combine::primitives::Error;
+/// # use combine::state::SourcePosition;
 /// # fn main() {
 /// let mut parser = eof();
 /// assert_eq!(parser.parse(State::new("")), Ok(((), State::new(""))));
 /// assert_eq!(parser.parse(State::new("x")), Err(ParseError {
-///     position: <char as Positioner>::start(),
+///     position: SourcePosition::default(),
 ///     errors: vec![
 ///         Error::Unexpected('x'.into()),
 ///         Error::Expected("end of input".into())
@@ -951,10 +1161,10 @@ pub struct Iter<P: Parser> {
     state: State<P::Input>,
 }
 
-enum State<I: StreamOnce> {
+enum State<I: Stream> {
     Ok,
     EmptyErr,
-    ConsumedErr(ParseError<I>),
+    ConsumedErr(StreamError<I>),
 }
 
 impl<P: Parser> Iter<P> {
@@ -1028,6 +1238,10 @@ where
         let result = iter.by_ref().collect();
         iter.into_result_fast(result)
     }
+
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        self.0.add_error(errors)
+    }
 }
 
 /// Parses `p` zero or more times returning a collection with the values from `p`.
@@ -1078,7 +1292,7 @@ where
         let result = Some(first).into_iter().chain(iter.by_ref()).collect();
         iter.into_result_fast(result)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -1183,7 +1397,7 @@ where
             .parse_lazy(input)
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(errors)
     }
 }
@@ -1248,7 +1462,7 @@ where
         })
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(errors)
     }
 }
@@ -1264,7 +1478,8 @@ where
 /// # extern crate combine;
 /// # use combine::*;
 /// # use combine::char::digit;
-/// # use combine::primitives::{Error, Positioner};
+/// # use combine::primitives::Error;
+/// # use combine::state::SourcePosition;
 /// # fn main() {
 /// let mut parser = sep_by1(digit(), token(','));
 /// let result_ok = parser.parse(State::new("1,2,3"))
@@ -1272,7 +1487,7 @@ where
 /// assert_eq!(result_ok, Ok((vec!['1', '2', '3'], "")));
 /// let result_err = parser.parse(State::new(""));
 /// assert_eq!(result_err, Err(ParseError {
-///     position: <char as Positioner>::start(),
+///     position: SourcePosition::default(),
 ///     errors: vec![
 ///         Error::end_of_input(),
 ///         Error::Expected("digit".into())
@@ -1319,7 +1534,7 @@ where
             .parse_lazy(input)
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(errors)
     }
 }
@@ -1391,7 +1606,7 @@ where
         })
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.parser.add_error(errors)
     }
 }
@@ -1407,7 +1622,8 @@ where
 /// # extern crate combine;
 /// # use combine::*;
 /// # use combine::char::digit;
-/// # use combine::primitives::{Error, Positioner};
+/// # use combine::primitives::Error;
+/// # use combine::state::SourcePosition;
 /// # fn main() {
 /// let mut parser = sep_end_by1(digit(), token(';'));
 /// let result_ok = parser.parse(State::new("1;2;3;"))
@@ -1415,7 +1631,7 @@ where
 /// assert_eq!(result_ok, Ok((vec!['1', '2', '3'], "")));
 /// let result_err = parser.parse(State::new(""));
 /// assert_eq!(result_err, Err(ParseError {
-///     position: <char as Positioner>::start(),
+///     position: SourcePosition::default(),
 ///     errors: vec![
 ///         Error::end_of_input(),
 ///         Error::Expected("digit".into())
@@ -1471,7 +1687,7 @@ pub struct FnParser<I, F>(F, PhantomData<fn(I) -> I>);
 ///     else {
 ///         //Return an empty error since we only tested the first token of the stream
 ///         let errors = ParseError::new(position, Error::Expected(From::from("even number")));
-///         Err(Consumed::Empty(errors))
+///         Err(Consumed::Empty(errors.into()))
 ///     }
 /// });
 /// let result = even_digit
@@ -1529,6 +1745,10 @@ where
             EmptyErr(_) => EmptyOk((None, input)),
         }
     }
+
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        self.0.add_error(errors)
+    }
 }
 
 /// Parses `parser` and outputs `Some(value)` if it succeeds, `None` if it fails without
@@ -1603,14 +1823,14 @@ where
                     l = op(l, r);
                     input = input.merge(rest);
                 }
-                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err.error),
                 Err(Consumed::Empty(_)) => break,
             }
         }
         Ok((l, input)).into()
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -1660,7 +1880,7 @@ where
                     input = input.merge(rest);
                     x
                 }
-                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err.error),
                 Err(Consumed::Empty(_)) => break,
             };
             match self.parse_lazy(input.clone().into_inner()).into() {
@@ -1668,13 +1888,13 @@ where
                     l = op(l, r);
                     input = input.merge(rest);
                 }
-                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err.error),
                 Err(Consumed::Empty(_)) => break,
             }
         }
         Ok((l, input)).into()
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -1718,8 +1938,8 @@ where
     }
 }
 
-/// `try(p)` behaves as `p` except it acts as if the parser hadn't consumed any input if `p` fails after
-/// consuming input.
+/// `try(p)` behaves as `p` except it acts as if the parser hadn't consumed any input if `p` fails
+/// after consuming input.
 ///
 /// ```
 /// # extern crate combine;
@@ -1759,7 +1979,7 @@ where
         EmptyOk((o, input))
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
     }
 }
@@ -1805,7 +2025,7 @@ where
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<Self::Output, I> {
         self.0.parse_lazy(input).map(|(_, b)| b)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -1839,7 +2059,7 @@ where
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<Self::Output, I> {
         self.0.parse_lazy(input).map(|(a, _)| a)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -1885,9 +2105,9 @@ where
         }
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
-        errors.add_error(Error::Message(self.1.clone()));
+        errors.error.add_error(Error::Message(self.1.clone()));
     }
 }
 
@@ -1906,7 +2126,7 @@ where
 }
 
 #[derive(Clone)]
-pub struct Or<P1, P2>(P1, P2)
+pub struct Or<P1, P2>(Choice<(P1, P2)>)
 where
     P1: Parser,
     P2: Parser;
@@ -1918,23 +2138,13 @@ where
 {
     type Input = I;
     type Output = O;
-    #[inline]
+    #[inline(always)]
     fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
-        match self.0.parse_lazy(input.clone()) {
-            ConsumedOk(x) => ConsumedOk(x),
-            EmptyOk(x) => EmptyOk(x),
-            ConsumedErr(err) => ConsumedErr(err),
-            EmptyErr(error1) => match self.1.parse_lazy(input) {
-                ConsumedOk(x) => ConsumedOk(x),
-                EmptyOk(x) => EmptyOk(x),
-                ConsumedErr(err) => ConsumedErr(err),
-                EmptyErr(error2) => EmptyErr(error1.merge(error2)),
-            },
-        }
+        self.0.parse_lazy(input)
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    #[inline]
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
-        self.1.add_error(errors);
     }
 }
 
@@ -1950,7 +2160,7 @@ where
     P1: Parser,
     P2: Parser<Input = P1::Input, Output = P1::Output>,
 {
-    Or(p1, p2)
+    Or(choice((p1, p2)))
 }
 
 #[derive(Clone)]
@@ -1972,7 +2182,7 @@ where
             EmptyErr(err) => EmptyErr(err),
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
     }
 }
@@ -1995,7 +2205,7 @@ impl<I, A, B, P, F> Parser for FlatMap<P, F>
 where
     I: Stream,
     P: Parser<Input = I, Output = A>,
-    F: FnMut(A) -> Result<B, ParseError<I>>,
+    F: FnMut(A) -> Result<B, StreamError<I>>,
 {
     type Input = I;
     type Output = B;
@@ -2004,7 +2214,7 @@ where
         match self.0.parse_lazy(input) {
             EmptyOk((o, input)) => match (self.1)(o) {
                 Ok(x) => EmptyOk((x, input)),
-                Err(err) => EmptyErr(err),
+                Err(err) => EmptyErr(err.into()),
             },
             ConsumedOk((o, input)) => match (self.1)(o) {
                 Ok(x) => ConsumedOk((x, input)),
@@ -2014,7 +2224,7 @@ where
             ConsumedErr(err) => ConsumedErr(err),
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
     }
 }
@@ -2026,7 +2236,7 @@ where
 pub fn flat_map<P, F, B>(p: P, f: F) -> FlatMap<P, F>
 where
     P: Parser,
-    F: FnMut(P::Output) -> Result<B, ParseError<P::Input>>,
+    F: FnMut(P::Output) -> Result<B, StreamError<P::Input>>,
 {
     FlatMap(p, f)
 }
@@ -2052,14 +2262,15 @@ where
                 let mut next = (self.1)(value);
                 match next.parse_stream_consumed(input) {
                     EmptyOk(x) | ConsumedOk(x) => ConsumedOk(x),
-                    EmptyErr(x) | ConsumedErr(x) => ConsumedErr(x),
+                    EmptyErr(x) => ConsumedErr(x.error),
+                    ConsumedErr(x) => ConsumedErr(x),
                 }
             }
             EmptyErr(err) => EmptyErr(err),
             ConsumedErr(err) => ConsumedErr(err),
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
     }
 }
@@ -2096,13 +2307,13 @@ where
         self.0.parse_lazy(input)
     }
 
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        let start = errors.errors.len();
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        let start = errors.error.errors.len();
         self.0.add_error(errors);
         // Replace all expected errors that were added from the previous add_error
         // with this expected error
         let mut i = 0;
-        errors.errors.retain(|e| if i < start {
+        errors.error.errors.retain(|e| if i < start {
             i += 1;
             true
         } else {
@@ -2111,7 +2322,7 @@ where
                 _ => true,
             }
         });
-        errors.add_error(Error::Expected(self.1.clone()));
+        errors.error.add_error(Error::Expected(self.1.clone()));
     }
 }
 
@@ -2145,7 +2356,7 @@ where
         match self.0.parse_lazy(input) {
             EmptyOk((o, input)) => match (self.1)(o) {
                 Ok(o) => EmptyOk((o, input)),
-                Err(err) => EmptyErr(ParseError::new(position, err.into())),
+                Err(err) => EmptyErr(ParseError::new(position, err.into()).into()),
             },
             ConsumedOk((o, input)) => match (self.1)(o) {
                 Ok(o) => ConsumedOk((o, input)),
@@ -2155,7 +2366,7 @@ where
             ConsumedErr(err) => ConsumedErr(err),
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors);
     }
 }
@@ -2173,8 +2384,18 @@ where
     AndThen(p, f)
 }
 
+macro_rules! dispatch_on {
+    ($i: expr, $f: expr;) => {
+    };
+    ($i: expr, $f: expr; $first: ident $(, $id: ident)*) => { {
+        $f($i, $first);
+        dispatch_on!($i + 1, $f; $($id),*);
+    } }
+}
+
 macro_rules! tuple_parser {
     ($h: ident, $($id: ident),+) => {
+        #[allow(non_snake_case)]
         impl <Input: Stream, $h:, $($id:),+> Parser for ($h, $($id),+)
             where Input: Stream,
                   $h: Parser<Input=Input>,
@@ -2182,15 +2403,29 @@ macro_rules! tuple_parser {
         {
             type Input = Input;
             type Output = ($h::Output, $($id::Output),+);
-            #[allow(non_snake_case)]
+
+            #[inline]
+            #[allow(unused_assignments)]
             fn parse_lazy(&mut self,
                           mut input: Input)
                           -> ConsumedResult<($h::Output, $($id::Output),+), Input> {
                 let (ref mut $h, $(ref mut $id),+) = *self;
-                let mut consumed = false;
-                let $h = match $h.parse_lazy(input) {
+                let mut first_empty_parser = 0;
+                let mut current_parser = 0;
+
+                macro_rules! add_error {
+                    ($err: expr) => {
+                        dispatch_on!(0, |i, p| {
+                            if i >= first_empty_parser {
+                                Parser::add_error(p, &mut $err);
+                            }
+                        }; $h, $($id),*);
+                    }
+                }
+
+                let temp = match $h.parse_lazy(input) {
                     ConsumedOk((x, new_input)) => {
-                        consumed = true;
+                        first_empty_parser = current_parser + 1;
                         input = new_input;
                         x
                     }
@@ -2201,21 +2436,25 @@ macro_rules! tuple_parser {
                         x
                     }
                 };
+                let mut offset = $h.parser_count().0.saturating_add(1);
+                let $h = temp;
                 $(
-                    let $id = match $id.parse_lazy(input.clone()) {
+                    current_parser += 1;
+                    let temp = match $id.parse_lazy(input.clone()) {
                         ConsumedOk((x, new_input)) => {
-                            consumed = true;
+                            first_empty_parser = current_parser + 1;
                             input = new_input;
                             x
                         }
                         EmptyErr(mut err) => {
-                            if let Ok(t) = input.uncons() {
-                                err.add_error(Error::Unexpected(Info::Token(t)));
-                            }
-                            $id.add_error(&mut err);
-                            if consumed {
-                                return ConsumedErr(err)
+                            if first_empty_parser != 0 {
+                                if let Ok(t) = input.uncons() {
+                                    err.error.add_error(Error::Unexpected(Info::Token(t)));
+                                }
+                                add_error!(err);
+                                return ConsumedErr(err.error)
                             } else {
+                                err.offset = ErrorOffset(offset);
                                 return EmptyErr(err)
                             }
                         }
@@ -2225,15 +2464,39 @@ macro_rules! tuple_parser {
                             x
                         }
                     };
+                    offset = offset.saturating_add($id.parser_count().0);
+                    let $id = temp;
                 )+
-                if consumed {
+                if first_empty_parser != 0 {
                     ConsumedOk((($h, $($id),+), input))
                 } else {
                     EmptyOk((($h, $($id),+), input))
                 }
             }
-            fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-                self.0.add_error(errors);
+
+            #[inline(always)]
+            fn parser_count(&self) -> ErrorOffset {
+                let (ref $h, $(ref $id),+) = *self;
+                ErrorOffset($h.parser_count().0 $( + $id.parser_count().0)+)
+            }
+
+            #[inline(always)]
+            fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+                let (ref mut $h, $(ref mut $id),+) = *self;
+                $h.add_error(errors);
+                if errors.offset <= ErrorOffset(1) {
+                    return;
+                }
+                errors.offset = ErrorOffset(errors.offset.0.saturating_sub($h.parser_count().0));
+                $(
+                    $id.add_error(errors);
+                    if errors.offset <= ErrorOffset(1) {
+                        return;
+                    }
+                    errors.offset = ErrorOffset(
+                        errors.offset.0.saturating_sub($id.parser_count().0)
+                    );
+                )*
             }
         }
     }
@@ -2464,7 +2727,7 @@ where
                     .collect::<Result<_, _>>();
                 match result {
                     Ok(x) => EmptyOk((x, rest)),
-                    Err(err) => EmptyErr(ParseError::new(input.position(), err)),
+                    Err(err) => EmptyErr(ParseError::new(input.position(), err).into()),
                 }
             }
             ConsumedOk((_, rest)) => {
@@ -2486,7 +2749,7 @@ where
     }
 
     #[inline]
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         self.0.add_error(errors)
     }
 }
@@ -2515,19 +2778,21 @@ where
 #[cfg(test)]
 mod tests {
     use super::*;
-    use primitives::{Error, ParseError, Parser, Positioner, SourcePosition, State};
+    use primitives::{Error, Parser, StreamError};
     use char::{char, digit, letter};
+    use state::{SourcePosition, State};
 
     #[test]
     fn choice_empty() {
-        let mut parser = choice::<&mut [Token<&str>], Token<&str>>(&mut []);
+        let mut parser = choice::<&mut [Token<&str>]>(&mut []);
         let result_err = parser.parse("a");
         assert!(result_err.is_err());
     }
     #[test]
     fn sep_by_consumed_error() {
         let mut parser2 = sep_by((letter(), letter()), token(','));
-        let result_err: Result<(Vec<(char, char)>, &str), ParseError<&str>> = parser2.parse("a,bc");
+        let result_err: Result<(Vec<(char, char)>, &str), StreamError<&str>> =
+            parser2.parse("a,bc");
         assert!(result_err.is_err());
     }
 
@@ -2547,7 +2812,7 @@ mod tests {
         assert_eq!(
             parser.parse(State::new("a")),
             Err(ParseError {
-                position: <char as Positioner>::start(),
+                position: SourcePosition::default(),
                 errors: vec![
                     Error::Unexpected('a'.into()),
                     Error::Message("message".into()),
@@ -2564,7 +2829,7 @@ mod tests {
         assert_eq!(
             result,
             Err(ParseError {
-                position: <char as Positioner>::start(),
+                position: SourcePosition::default(),
                 errors: vec![
                     Error::Unexpected('a'.into()),
                     Error::Expected("digit".into()),
@@ -2718,4 +2983,122 @@ mod tests {
             })
         );
     }
+
+    #[test]
+    fn optional_empty_ok_then_error() {
+        let mut parser = (optional(char('a')), char('b'));
+
+        assert_eq!(
+            parser.parse(State::new("c")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 1 },
+                errors: vec![
+                    Error::Unexpected('c'.into()),
+                    Error::Expected('a'.into()),
+                    Error::Expected('b'.into()),
+                ],
+            })
+        );
+    }
+
+    #[test]
+    fn nested_optional_empty_ok_then_error() {
+        let mut parser = ((optional(char('a')), char('b')), char('c'));
+
+        assert_eq!(
+            parser.parse(State::new("c")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 1 },
+                errors: vec![
+                    Error::Unexpected('c'.into()),
+                    Error::Expected('a'.into()),
+                    Error::Expected('b'.into()),
+                ],
+            })
+        );
+    }
+
+    #[test]
+    fn consumed_then_optional_empty_ok_then_error() {
+        let mut parser = (char('b'), optional(char('a')), char('b'));
+
+        assert_eq!(
+            parser.parse(State::new("bc")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 2 },
+                errors: vec![
+                    Error::Unexpected('c'.into()),
+                    Error::Expected('a'.into()),
+                    Error::Expected('b'.into()),
+                ],
+            })
+        );
+    }
+
+    #[test]
+    fn sequence_in_choice_parser_empty_err() {
+        let mut parser = choice((
+            (optional(char('a')), char('1')),
+            (optional(char('b')), char('2')).skip(char('d')),
+        ));
+
+        assert_eq!(
+            parser.parse(State::new("c")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 1 },
+                errors: vec![
+                    Error::Expected('a'.into()),
+                    Error::Expected('1'.into()),
+                    Error::Expected('b'.into()),
+                    Error::Expected('2'.into()),
+                    Error::Unexpected('c'.into()),
+                ],
+            })
+        );
+    }
+
+    #[test]
+    fn sequence_in_choice_array_parser_empty_err() {
+        let mut parser = choice([
+            (optional(char('a')), char('1')),
+            (optional(char('b')), char('2')),
+        ]);
+
+        assert_eq!(
+            parser.parse(State::new("c")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 1 },
+                errors: vec![
+                    Error::Expected('a'.into()),
+                    Error::Expected('1'.into()),
+                    Error::Expected('b'.into()),
+                    Error::Expected('2'.into()),
+                    Error::Unexpected('c'.into()),
+                ],
+            })
+        );
+    }
+
+    #[test]
+    fn sequence_in_choice_array_parser_empty_err_where_first_parser_delay_errors() {
+        let mut p1 = char('1');
+        let mut p2 = (optional(char('b')), char('2')).map(|t| t. 1);
+        let mut parser = choice::<[&mut Parser<Input = _, Output = _>; 2]>([
+            &mut p1,
+            &mut p2,
+        ]);
+
+        assert_eq!(
+            parser.parse(State::new("c")),
+            Err(ParseError {
+                position: SourcePosition { line: 1, column: 1 },
+                errors: vec![
+                    Error::Expected('1'.into()),
+                    Error::Expected('b'.into()),
+                    Error::Expected('2'.into()),
+                    Error::Unexpected('c'.into()),
+                ],
+            })
+        );
+    }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 438cba80..f5e244fd 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -39,12 +39,12 @@
 //!
 //! * [`combinator`] contains the before mentioned parser combinators and thus contains the main
 //! building exprs for creating any sort of complex parsers. It consists of free functions such
-//! as [`many`] and [`satisfy`] as well as a few methods on the [`Parser`] trait which provides a few
-//! functions such as [`or`] which are more natural to use method calls.
+//! as [`many`] and [`satisfy`] as well as a few methods on the [`Parser`] trait which provides a
+//! few functions such as [`or`] which are more natural to use method calls.
 //!
-//! * [`primitives`] contains the [`Parser`] and [`Stream`] traits which are the core abstractions in
-//! combine as well as various structs dealing with input streams and errors. You usually only need
-//! to use this module if you want more control over parsing and input streams.
+//! * [`primitives`] contains the [`Parser`] and [`Stream`] traits which are the core abstractions
+//! in combine as well as various structs dealing with input streams and errors. You usually only
+//! need to use this module if you want more control over parsing and input streams.
 //!
 //! * [`char`] and [`byte`] provides parsers specifically working with streams of characters
 //! (`char`) and bytes (`u8`) respectively. As a few examples it has parsers for accepting digits,
@@ -57,7 +57,7 @@
 //! ```
 //! extern crate combine;
 //! use combine::char::{spaces, digit, char};
-//! use combine::{many1, sep_by, Parser, ParseError};
+//! use combine::{many1, sep_by, Parser, StreamError};
 //!
 //! fn main() {
 //!     //Parse spaces first and use the with method to only keep the result of the next parser
@@ -70,7 +70,7 @@
 //!
 //!     //Call parse with the input to execute the parser
 //!     let input = "1234, 45,78";
-//!     let result: Result<(Vec<i32>, &str), ParseError<&str>> = integer_list.parse(input);
+//!     let result: Result<(Vec<i32>, &str), StreamError<&str>> = integer_list.parse(input);
 //!     match result {
 //!         Ok((value, _remaining_input)) => println!("{:?}", value),
 //!         Err(err) => println!("{}", err)
@@ -79,18 +79,19 @@
 //! ```
 //!
 //! If we need a parser that is mutually recursive we can define a free function which internally
-//! can in turn be used as a parser by using the [`parser`][fn parser] function which turns a function with the
-//! correct signature into a parser. In this case we define `expr` to work on any type of [`Stream`]
-//! which is combine's way of abstracting over different data sources such as array slices, string
-//! slices, iterators etc. If instead you would only need to parse string already in memory you
-//! could define `expr` as `fn expr(input: &str) -> ParseResult<Expr, &str>`
+//! can in turn be used as a parser by using the [`parser`][fn parser] function which turns a
+//! function with the correct signature into a parser. In this case we define `expr` to work on any
+//! type of [`Stream`] which is combine's way of abstracting over different data sources such as
+//! array slices, string slices, iterators etc. If instead you would only need to parse string
+//! already in memory you could define `expr` as `fn expr(input: &str) -> ParseResult<Expr, &str>`
 //!
 //! ```
 //! #[macro_use]
 //! extern crate combine;
 //! use combine::char::{char, letter, spaces};
 //! use combine::{between, many1, parser, sep_by, Parser};
-//! use combine::primitives::{State, Stream, ParseResult};
+//! use combine::primitives::{Stream, Positioned, ParseResult};
+//! use combine::state::State;
 //!
 //! #[derive(Debug, PartialEq)]
 //! pub enum Expr {
@@ -159,20 +160,18 @@
 #![cfg_attr(feature = "cargo-clippy", allow(inline_always))]
 
 #[doc(inline)]
-pub use primitives::{ConsumedResult, ParseError, ParseResult, Parser, State, Stream, StreamOnce};
+pub use primitives::{ConsumedResult, ParseError, ParseResult, Parser, Positioned, Stream,
+                     StreamError, StreamOnce};
 
-// import this one separately, so we can set the allow(deprecated) for just this item
-// TODO: remove this when a new major version is released
 #[doc(inline)]
-#[allow(deprecated)]
-pub use primitives::from_iter;
+pub use state::State;
 
 #[doc(inline)]
 pub use combinator::{any, between, choice, count, count_min_max, env_parser, eof, look_ahead,
-                     many, none_of, not_followed_by, one_of, optional, parser, position,
-                     satisfy, satisfy_map, sep_by, sep_end_by, skip_count, skip_count_min_max,
-                     skip_many, token, tokens, try, unexpected, value, chainl1, chainr1, many1,
-                     sep_by1, sep_end_by1, skip_many1};
+                     many, none_of, not_followed_by, one_of, optional, parser, position, satisfy,
+                     satisfy_map, sep_by, sep_end_by, skip_count, skip_count_min_max, skip_many,
+                     token, tokens, try, unexpected, value, chainl1, chainr1, many1, sep_by1,
+                     sep_end_by1, skip_many1};
 
 macro_rules! static_fn {
     (($($arg: pat, $arg_ty: ty),*) -> $ret: ty { $body: expr }) => { {
@@ -195,7 +194,7 @@ macro_rules! impl_token_parser {
                       input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
             self.0.parse_lazy(input)
         }
-        fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+        fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
             self.0.add_error(errors)
         }
     }
@@ -442,7 +441,10 @@ macro_rules! combine_parser_impl {
                 }
 
                 #[inline]
-                fn add_error(&mut self, errors: &mut $crate::ParseError<$input_type>) {
+                fn add_error(
+                    &mut self,
+                    errors: &mut $crate::primitives::Tracked<$crate::StreamError<$input_type>>)
+                {
                     let $type_name { $( $arg : ref mut $arg,)*  __marker: _ } = *self;
                     combine_add_error!(errors ($input_type, $output_type) $($parser)*)
                 }
@@ -489,18 +491,25 @@ pub mod range;
 pub mod byte;
 /// Module containing parsers specialized on character streams.
 pub mod char;
+/// Module containing stateful stream wrappers
+pub mod state;
 
 #[cfg(feature = "regex")]
 pub mod regex;
 
+#[doc(hidden)]
+#[derive(Clone, PartialOrd, PartialEq, Debug, Copy)]
+pub struct ErrorOffset(u8);
 
 
 #[cfg(test)]
 mod tests {
     use super::*;
-    use super::primitives::{Consumed, Error, SourcePosition};
+    use super::primitives::{Consumed, Error, IteratorStream};
     use char::{alpha_num, char, digit, letter, spaces, string};
 
+    use state::SourcePosition;
+
 
     fn integer<'a, I>(input: I) -> ParseResult<i64, I>
     where
@@ -530,10 +539,9 @@ mod tests {
         assert_eq!(result, Ok((vec![123i64, 4, 56], "")));
     }
     #[test]
-    #[allow(deprecated)]
     fn iterator() {
         let result = parser(integer)
-            .parse(from_iter("123".chars()))
+            .parse(State::new(IteratorStream::new("123".chars())))
             .map(|(i, mut input)| (i, input.uncons().is_err()));
         assert_eq!(result, Ok((123i64, true)));
     }
@@ -553,9 +561,9 @@ mod tests {
 ";
         let result = (spaces(), parser(integer), spaces())
             .map(|t| t.1)
-            .parse_stream(State::new(source));
+            .parse_stream(State::with_positioner(source, SourcePosition::new()));
         let state = Consumed::Consumed(State {
-            position: SourcePosition { line: 3, column: 1 },
+            positioner: SourcePosition { line: 3, column: 1 },
             input: "",
         });
         assert_eq!(result, Ok((123i64, state)));
@@ -654,11 +662,11 @@ mod tests {
     }
 
 
-    fn follow(input: State<&str>) -> ParseResult<(), State<&str>> {
+    fn follow(input: State<&str, SourcePosition>) -> ParseResult<(), State<&str, SourcePosition>> {
         match input.clone().uncons() {
             Ok(c) => if c.is_alphanumeric() {
                 let e = Error::Unexpected(c.into());
-                Err(Consumed::Empty(ParseError::new(input.position(), e)))
+                Err(Consumed::Empty(ParseError::new(input.position(), e).into()))
             } else {
                 Ok(((), Consumed::Empty(input)))
             },
@@ -759,7 +767,7 @@ mod tests {
                 "error"
             }
         }
-        let result: Result<((), _), ParseError<&str>> =
+        let result: Result<((), _), ParseError<_, char, &str>> =
             string("abc").and_then(|_| Err(Error)).parse("abc");
         assert!(result.is_err());
         // Test that ParseError can be coerced to a StdError
@@ -817,7 +825,7 @@ mod tests {
         let input = &[CloneOnly("x".to_string()), CloneOnly("y".to_string())][..];
         let result = token(CloneOnly("z".to_string()))
             .parse(input)
-            .map_err(|e| e.translate_position(input))
+            .map_err(|e| e.map_position(|p| p.translate_position(input)))
             .map_err(|e| {
                 ExtractedError(
                     e.position,
diff --git a/src/primitives.rs b/src/primitives.rs
index c708bdf8..e25f46c0 100644
--- a/src/primitives.rs
+++ b/src/primitives.rs
@@ -7,6 +7,7 @@ use std::io::{Bytes, Read};
 
 use self::FastResult::*;
 
+use ErrorOffset;
 use combinator::{and_then, expected, flat_map, map, message, or, skip, then, with, AndThen,
                  Expected, FlatMap, Iter, Map, Message, Or, Skip, Then, With};
 
@@ -14,40 +15,54 @@ use combinator::{and_then, expected, flat_map, map, message, or, skip, then, wit
 macro_rules! ctry {
     ($result: expr) => {
         match $result {
-            $crate::primitives::FastResult::ConsumedOk((x, i)) => (x, $crate::primitives::Consumed::Consumed(i)),
-            $crate::primitives::FastResult::EmptyOk((x, i)) => (x, $crate::primitives::Consumed::Empty(i)),
-            $crate::primitives::FastResult::ConsumedErr(err) => return $crate::primitives::FastResult::ConsumedErr(err.into()),
-            $crate::primitives::FastResult::EmptyErr(err) => return $crate::primitives::FastResult::EmptyErr(err.into()),
+            $crate::primitives::FastResult::ConsumedOk((x, i)) =>
+                (x, $crate::primitives::Consumed::Consumed(i)),
+            $crate::primitives::FastResult::EmptyOk((x, i)) =>
+                (x, $crate::primitives::Consumed::Empty(i)),
+            $crate::primitives::FastResult::ConsumedErr(err) =>
+                return $crate::primitives::FastResult::ConsumedErr(err.into()),
+            $crate::primitives::FastResult::EmptyErr(err) =>
+                return $crate::primitives::FastResult::EmptyErr(err.into()),
         }
     }
 }
 
-/// Struct which represents a position in a source file.
+/// Newtype around a pointer offset into a slice stream (`&[T]`/`&str`).
 #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
-pub struct SourcePosition {
-    /// Current line of the input
-    pub line: i32,
-    /// Current column of the input
-    pub column: i32,
-}
+pub struct PointerOffset(pub usize);
 
-/// Struct which represents a position in a byte stream.
-#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
-pub struct BytePosition {
-    /// Current position
-    pub position: usize,
+impl fmt::Display for PointerOffset {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.0 as *const ())
+    }
 }
 
-impl fmt::Display for BytePosition {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "position: {}", self.position)
+impl PointerOffset {
+    /// Converts the pointer-based position into an indexed position.
+    ///
+    /// ```rust
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # fn main() {
+    /// let text = "b";
+    /// let err = token('a').parse(text).unwrap_err();
+    /// assert_eq!(err.position.0, text.as_ptr() as usize);
+    /// assert_eq!(err.map_position(|p| p.translate_position(text)).position, 0);
+    /// # }
+    /// ```
+    pub fn translate_position<T>(mut self, initial_string: &T) -> usize
+    where
+        T: ?Sized,
+    {
+        self.0 -= initial_string as *const T as *const () as usize;
+        self.0
     }
 }
 
 /// Enum holding error information. Variants are defined for `Stream::Item` and `Stream::Range` as
 /// well as string variants holding simple descriptions.
 ///
-/// As there is implementations of `From` for `T: Positioner`, `String` and `&'static str` the
+/// As there is implementations of `From` for `String` and `&'static str` the
 /// constructor need not be used directly as calling `msg.into()` should turn a message into the
 /// correct `Info` variant.
 #[derive(Clone, Debug)]
@@ -127,6 +142,12 @@ impl<T, R> From<&'static str> for Info<T, R> {
     }
 }
 
+impl<R> From<u8> for Info<u8, R> {
+    fn from(s: u8) -> Info<u8, R> {
+        Info::Token(s)
+    }
+}
+
 /// Enum used to store information about an error that has occurred during parsing.
 #[derive(Debug)]
 pub enum Error<T, R> {
@@ -309,23 +330,11 @@ impl<T> Consumed<T> {
         }
     }
 
-    /// Converts `self` into the `Consumed` state.
-    #[deprecated(since = "2.3.1", note = "Renamed to into_consumed")]
-    pub fn as_consumed(self) -> Consumed<T> {
-        self.into_consumed()
-    }
-
     /// Converts `self` into the `Consumed` state.
     pub fn into_consumed(self) -> Consumed<T> {
         Consumed::Consumed(self.into_inner())
     }
 
-    /// Converts `self` into the `Empty` state.
-    #[deprecated(since = "2.3.1", note = "Renamed to into_empty")]
-    pub fn as_empty(self) -> Consumed<T> {
-        self.into_empty()
-    }
-
     /// Converts `self` into the `Empty` state.
     pub fn into_empty(self) -> Consumed<T> {
         Consumed::Empty(self.into_inner())
@@ -391,7 +400,7 @@ impl<T> Consumed<T> {
     pub fn combine<F, U, I>(self, f: F) -> ParseResult<U, I>
     where
         F: FnOnce(T) -> ParseResult<U, I>,
-        I: StreamOnce,
+        I: StreamOnce + Positioned,
     {
         match self {
             Consumed::Consumed(x) => match f(x) {
@@ -405,47 +414,53 @@ impl<T> Consumed<T> {
     pub fn combine_consumed<F, U, I>(self, f: F) -> ConsumedResult<U, I>
     where
         F: FnOnce(T) -> ConsumedResult<U, I>,
-        I: StreamOnce,
+        I: StreamOnce + Positioned,
     {
         use self::FastResult::*;
         match self {
             Consumed::Consumed(x) => match f(x) {
                 EmptyOk((v, rest)) => ConsumedOk((v, rest)),
-                EmptyErr(err) => ConsumedErr(err),
+                EmptyErr(err) => ConsumedErr(err.error),
                 y => y,
             },
             Consumed::Empty(x) => f(x),
         }
     }
 }
-/// Struct which hold information about an error that occurred at a specific position.
-/// Can hold multiple instances of `Error` if more that one error occurred in the same position.
-pub struct ParseError<S: StreamOnce> {
+
+/// Alias over `ParseError` for `StreamOnce` types
+pub type StreamError<S> = ParseError<
+    <S as Positioned>::Position,
+    <S as StreamOnce>::Item,
+    <S as StreamOnce>::Range,
+>;
+
+/// Struct which hold information about an error that occured at a specific position.
+/// Can hold multiple instances of `Error` if more that one error occured in the same position.
+#[derive(Debug, PartialEq)]
+pub struct ParseError<P, I, R> {
     /// The position where the error occurred
-    pub position: S::Position,
+    pub position: P,
     /// A vector containing specific information on what errors occurred at `position`. Usually
     /// a fully formed message contains one `Unexpected` error and one or more `Expected` errors.
     /// `Message` and `Other` may also appear (`combine` never generates these errors on its own)
     /// and may warrant custom handling.
-    pub errors: Vec<Error<S::Item, S::Range>>,
+    pub errors: Vec<Error<I, R>>,
 }
 
-impl<S: StreamOnce> ParseError<S> {
+impl<P, I, R> ParseError<P, I, R> {
     /// Constructs a new `ParseError` which occurred at `position`.
-    pub fn new(position: S::Position, error: Error<S::Item, S::Range>) -> ParseError<S> {
+    pub fn new(position: P, error: Error<I, R>) -> ParseError<P, I, R> {
         ParseError::from_errors(position, vec![error])
     }
 
     /// Constructs an error with no other information than the position it occurred at.
-    pub fn empty(position: S::Position) -> ParseError<S> {
+    pub fn empty(position: P) -> ParseError<P, I, R> {
         ParseError::from_errors(position, vec![])
     }
 
     /// Constructs a `ParseError` with multiple causes.
-    pub fn from_errors(
-        position: S::Position,
-        errors: Vec<Error<S::Item, S::Range>>,
-    ) -> ParseError<S> {
+    pub fn from_errors(position: P, errors: Vec<Error<I, R>>) -> ParseError<P, I, R> {
         ParseError {
             position: position,
             errors: errors,
@@ -454,22 +469,17 @@ impl<S: StreamOnce> ParseError<S> {
 
     /// Constructs an end of input error. Should be returned by parsers which encounter end of
     /// input unexpectedly.
-    pub fn end_of_input(position: S::Position) -> ParseError<S> {
+    pub fn end_of_input(position: P) -> ParseError<P, I, R> {
         ParseError::new(position, Error::end_of_input())
     }
 
-    /// Adds a `Message` error, taking care not to add duplicated errors.
-    #[deprecated(since = "2.3.0", note = "Use `add_error(Error::Message())` instead")]
-    pub fn add_message<M>(&mut self, message: M)
-    where
-        M: Into<Info<S::Item, S::Range>>,
-    {
-        self.add_error(Error::Message(message.into()));
-    }
-
     /// Adds an error if `error` does not exist in this `ParseError` already (as determined byte
     /// `PartialEq`).
-    pub fn add_error(&mut self, error: Error<S::Item, S::Range>) {
+    pub fn add_error(&mut self, error: Error<I, R>)
+    where
+        I: PartialEq,
+        R: PartialEq,
+    {
         // Don't add duplicate errors
         if self.errors.iter().all(|err| *err != error) {
             self.errors.push(error);
@@ -477,7 +487,7 @@ impl<S: StreamOnce> ParseError<S> {
     }
 
     /// Remvoes all `Expected` errors in `self` and adds `info` instead.
-    pub fn set_expected(&mut self, info: Info<S::Item, S::Range>) {
+    pub fn set_expected(&mut self, info: Info<I, R>) {
         // Remove all other expected messages
         self.errors.retain(|e| match *e {
             Error::Expected(_) => false,
@@ -489,7 +499,12 @@ impl<S: StreamOnce> ParseError<S> {
     /// Merges two `ParseError`s. If they exist at the same position the errors of `other` are
     /// added to `self` (using `add_error` to skip duplicates). If they are not at the same
     /// position the error furthest ahead are returned, ignoring the other `ParseError`.
-    pub fn merge(mut self, other: ParseError<S>) -> ParseError<S> {
+    pub fn merge(mut self, other: ParseError<P, I, R>) -> ParseError<P, I, R>
+    where
+        P: Ord,
+        I: PartialEq,
+        R: PartialEq,
+    {
         use std::cmp::Ordering;
         // Only keep the errors which occurred after consuming the most amount of data
         match self.position.cmp(&other.position) {
@@ -503,94 +518,72 @@ impl<S: StreamOnce> ParseError<S> {
             }
         }
     }
-}
 
-impl<'s> ParseError<&'s str> {
-    /// Converts the pointer-based position into an indexed position.
-    ///
-    /// ```rust
-    /// # extern crate combine;
-    /// # use combine::*;
-    /// # fn main() {
-    /// let text = "b";
-    /// let err = token('a').parse(text).unwrap_err();
-    /// assert_eq!(err.position, text.as_ptr() as usize);
-    /// assert_eq!(err.translate_position(text).position, 0);
-    /// # }
-    /// ```
-    pub fn translate_position(mut self, initial_string: &'s str) -> ParseError<&'s str> {
-        self.position -= initial_string.as_ptr() as usize;
-        self
+    /// Maps the position to a new value
+    pub fn map_position<F, Q>(self, f: F) -> ParseError<Q, I, R>
+    where
+        F: FnOnce(P) -> Q,
+    {
+        ParseError::from_errors(f(self.position), self.errors)
     }
-}
 
-impl<'s, T: 's> ParseError<&'s [T]>
-where
-    T: Clone + PartialEq,
-{
-    /// Converts the pointer-based position into an indexed position.
+    /// Maps all token variants to a new value
+    pub fn map_token<F, U>(self, mut f: F) -> ParseError<P, U, R>
+    where
+        F: FnMut(I) -> U,
+    {
+        ParseError::from_errors(
+            self.position,
+            self.errors
+                .into_iter()
+                .map(|error| error.map_token(&mut f))
+                .collect(),
+        )
+    }
+
+    /// Maps all range variants to a new value.
     ///
-    /// ```rust
-    /// # extern crate combine;
-    /// # use combine::*;
-    /// # fn main() {
-    /// let text = b"b";
-    /// let err = token(b'a').parse(&text[..]).unwrap_err();
-    /// assert_eq!(err.position, text.as_ptr() as usize);
-    /// assert_eq!(err.translate_position(text).position, 0);
-    /// # }
     /// ```
-    pub fn translate_position(mut self, initial_string: &'s [T]) -> ParseError<&'s [T]> {
-        self.position -= initial_string.as_ptr() as usize;
-        self
+    /// use combine::Parser;
+    /// use combine::range::range;
+    /// println!(
+    ///     "{}",
+    ///     range(&"HTTP"[..])
+    ///         .parse("HTT")
+    ///         .unwrap_err()
+    ///         .map_range(|bytes| format!("{:?}", bytes))
+    /// );
+    /// ```
+    pub fn map_range<F, S>(self, mut f: F) -> ParseError<P, I, S>
+    where
+        F: FnMut(R) -> S,
+    {
+        ParseError::from_errors(
+            self.position,
+            self.errors
+                .into_iter()
+                .map(|error| error.map_range(&mut f))
+                .collect(),
+        )
     }
 }
 
-impl<S> StdError for ParseError<S>
+impl<P, I, R> StdError for ParseError<P, I, R>
 where
-    S: Stream,
-    S::Range: fmt::Display + fmt::Debug + Any,
-    S::Item: fmt::Display + fmt::Debug + Any,
-    S::Position: fmt::Display + fmt::Debug + Any,
+    P: fmt::Display + fmt::Debug + Any,
+    I: fmt::Display + fmt::Debug + Any,
+    R: fmt::Display + fmt::Debug + Any,
 {
     fn description(&self) -> &str {
         "parse error"
     }
 }
 
-impl<S> PartialEq for ParseError<S>
+impl<P, I, R> fmt::Display for ParseError<P, I, R>
 where
-    S: Stream,
-    S::Position: PartialEq,
-{
-    fn eq(&self, other: &ParseError<S>) -> bool {
-        self.position == other.position && self.errors == other.errors
-    }
-}
-
-impl<S> fmt::Debug for ParseError<S>
-where
-    S: Stream,
-    S::Range: fmt::Debug,
-    S::Item: fmt::Debug,
-    S::Position: fmt::Debug,
-{
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(
-            f,
-            "ParseError {{ position: {:?}, errors: {:?} }}",
-            self.position,
-            self.errors
-        )
-    }
-}
-
-impl<S> fmt::Display for ParseError<S>
-where
-    S: Stream,
-    S::Item: fmt::Display,
-    S::Range: fmt::Display,
-    S::Position: fmt::Display,
+    P: fmt::Display,
+    I: fmt::Display,
+    R: fmt::Display,
 {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(writeln!(f, "Parse error at {}", self.position));
@@ -598,11 +591,6 @@ where
     }
 }
 
-impl fmt::Display for SourcePosition {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "line: {}, column: {}", self.line, self.column)
-    }
-}
 impl<T: fmt::Display, R: fmt::Display> fmt::Display for Error<T, R> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match *self {
@@ -614,124 +602,20 @@ impl<T: fmt::Display, R: fmt::Display> fmt::Display for Error<T, R> {
     }
 }
 
-/// The `State<I>` struct keeps track of the current position in the stream `I` using the
-/// `Positioner` trait to update the position.
-#[derive(Clone, PartialEq)]
-pub struct State<I>
-where
-    I: Stream,
-    I::Item: Positioner,
-{
-    /// The current position
-    pub position: <I::Item as Positioner>::Position,
-    /// The input stream used when items are requested
-    pub input: I,
-}
-
-impl<I> fmt::Debug for State<I>
-where
-    I: Stream + fmt::Debug,
-    I::Item: Positioner,
-    <I::Item as Positioner>::Position: fmt::Debug,
-{
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(
-            f,
-            "State {{ position: {:?}, input: {:?} }}",
-            self.position,
-            self.input
-        )
-    }
-}
-
-impl<I> State<I>
-where
-    I: Stream,
-    I::Item: Positioner,
-{
-    /// Creates a new `State<I>` from an input stream. Initializes the position to
-    /// `Positioner::start()`.
-    pub fn new(input: I) -> State<I> {
-        State {
-            position: <I::Item as Positioner>::start(),
-            input: input,
-        }
-    }
-}
-
-impl<I> StreamOnce for State<I>
-where
-    I: Stream,
-    I::Item: Positioner,
-{
-    type Item = I::Item;
-    type Range = I::Range;
-    type Position = <I::Item as Positioner>::Position;
-
-    #[inline]
-    fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Range>> {
-        match self.input.uncons() {
-            Ok(c) => {
-                c.update(&mut self.position);
-                Ok(c)
-            }
-            Err(err) => Err(err),
-        }
-    }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.position.clone()
-    }
-}
-
-impl<I, E> RangeStream for State<I>
-where
-    I: RangeStream<Item = E>,
-    I::Range: Range + Positioner<Position = E::Position>,
-    E: Positioner + Clone,
-{
-    #[inline]
-    fn uncons_range(&mut self, size: usize) -> Result<I::Range, Error<I::Item, I::Range>> {
-        let position = &mut self.position;
-        self.input.uncons_range(size).map(|value| {
-            value.update(position);
-            value
-        })
-    }
-
-    #[inline]
-    fn uncons_while<F>(&mut self, mut predicate: F) -> Result<I::Range, Error<I::Item, I::Range>>
-    where
-        F: FnMut(I::Item) -> bool,
-    {
-        let position = &mut self.position;
-        self.input.uncons_while(|t| if predicate(t.clone()) {
-            t.update(position);
-            true
-        } else {
-            false
-        })
-    }
-}
-
-impl<I, E> FullRangeStream for State<I>
-where
-    I: RangeStream<Item = E>,
-    I::Range: Range + Positioner<Position = E::Position>,
-    E: Positioner + Clone,
-    I: FullRangeStream,
-{
-    fn range(&self) -> Self::Range {
-        self.input.range()
-    }
-}
-
 /// A type alias over the specific `Result` type used by parsers to indicate wether they were
 /// successful or not.
 /// `O` is the type that is output on success.
 /// `I` is the specific stream type used in the parser.
-pub type ParseResult<O, I> = Result<(O, Consumed<I>), Consumed<ParseError<I>>>;
+pub type ParseResult<O, I> = Result<(O, Consumed<I>), Consumed<Tracked<StreamError<I>>>>;
+
+pub trait Positioned {
+    /// Type which represents the position in a stream.
+    /// `Ord` is required to allow parsers to determine which of two positions are further ahead.
+    type Position: Clone + Ord;
+
+    /// Returns the current position of the stream.
+    fn position(&self) -> Self::Position;
+}
 
 /// `StreamOnce` represents a sequence of items that can be extracted one by one.
 pub trait StreamOnce {
@@ -743,24 +627,17 @@ pub trait StreamOnce {
     /// `Self::Item` for this type.
     type Range: Clone + PartialEq;
 
-    /// Type which represents the position in a stream.
-    /// `Ord` is required to allow parsers to determine which of two positions are further ahead.
-    type Position: Ord;
-
     /// Takes a stream and removes its first item, yielding the item and the rest of the elements.
     /// Returns `Err` if no element could be retrieved.
     fn uncons(&mut self) -> Result<Self::Item, Error<Self::Item, Self::Range>>;
-
-    /// Returns the current position of the stream.
-    fn position(&self) -> Self::Position;
 }
 
 /// A stream of tokens which can be duplicated
-pub trait Stream: StreamOnce + Clone {}
+pub trait Stream: StreamOnce + Positioned + Clone {}
 
 impl<I> Stream for I
 where
-    I: StreamOnce + Clone,
+    I: StreamOnce + Positioned + Clone,
 {
 }
 
@@ -773,7 +650,7 @@ where
     let x = try!(
         input
             .uncons()
-            .map_err(|err| Consumed::Empty(ParseError::new(position, err)))
+            .map_err(|err| Consumed::Empty(ParseError::new(position, err).into()))
     );
     Ok((x, Consumed::Consumed(input)))
 }
@@ -789,6 +666,15 @@ pub trait RangeStream: Stream {
     fn uncons_while<F>(&mut self, f: F) -> Result<Self::Range, Error<Self::Item, Self::Range>>
     where
         F: FnMut(Self::Item) -> bool;
+
+    /// Returns the distance between `self` and `end`. The returned `usize` must be so that
+    ///
+    /// ```ignore
+    /// let start = stream.clone();
+    /// stream.uncons_range(distance);
+    /// start.distance() == distance
+    /// ```
+    fn distance(&self, end: &Self) -> usize;
 }
 
 /// A `RangeStream` which is capable of providing it's entire range.
@@ -806,7 +692,7 @@ where
     I::Range: Range,
 {
     match input.uncons_while(predicate) {
-        Err(err) => EmptyErr(ParseError::new(input.position(), err)),
+        Err(err) => EmptyErr(ParseError::new(input.position(), err).into()),
         Ok(x) => if x.len() == 0 {
             EmptyOk((x, input))
         } else {
@@ -871,6 +757,11 @@ impl<'a> RangeStream for &'a str {
             Err(Error::end_of_input())
         }
     }
+
+    #[inline]
+    fn distance(&self, end: &Self) -> usize {
+        end.position().0 - self.position().0
+    }
 }
 
 impl<'a> FullRangeStream for &'a str {
@@ -907,6 +798,7 @@ where
             Err(Error::end_of_input())
         }
     }
+
     #[inline]
     fn uncons_while<F>(&mut self, mut f: F) -> Result<&'a [T], Error<T, &'a [T]>>
     where
@@ -917,6 +809,11 @@ where
         *self = remaining;
         Ok(result)
     }
+
+    #[inline]
+    fn distance(&self, end: &Self) -> usize {
+        end.position().0 - self.position().0
+    }
 }
 
 impl<'a, T> FullRangeStream for &'a [T]
@@ -928,10 +825,18 @@ where
     }
 }
 
+impl<'a> Positioned for &'a str {
+    type Position = PointerOffset;
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.as_bytes().position()
+    }
+}
+
 impl<'a> StreamOnce for &'a str {
     type Item = char;
     type Range = &'a str;
-    type Position = usize;
 
     #[inline]
     fn uncons(&mut self) -> Result<char, Error<char, &'a str>> {
@@ -944,10 +849,14 @@ impl<'a> StreamOnce for &'a str {
             None => Err(Error::end_of_input()),
         }
     }
+}
+
+impl<'a, T> Positioned for &'a [T] {
+    type Position = PointerOffset;
 
     #[inline(always)]
     fn position(&self) -> Self::Position {
-        self.as_bytes().as_ptr() as usize
+        PointerOffset(self.as_ptr() as usize)
     }
 }
 
@@ -957,7 +866,6 @@ where
 {
     type Item = T;
     type Range = &'a [T];
-    type Position = usize;
 
     #[inline]
     fn uncons(&mut self) -> Result<T, Error<T, &'a [T]>> {
@@ -969,11 +877,6 @@ where
             None => Err(Error::end_of_input()),
         }
     }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.as_ptr() as usize
-    }
 }
 
 /// Newtype for constructing a stream from a slice where the items in the slice are not copyable.
@@ -986,13 +889,21 @@ impl<'a, T> Clone for SliceStream<'a, T> {
     }
 }
 
+impl<'a, T> Positioned for SliceStream<'a, T> {
+    type Position = PointerOffset;
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.0.position()
+    }
+}
+
 impl<'a, T> StreamOnce for SliceStream<'a, T>
 where
     T: Clone + PartialEq + 'a,
 {
     type Item = &'a T;
     type Range = &'a [T];
-    type Position = usize;
 
     #[inline]
     fn uncons(&mut self) -> Result<&'a T, Error<&'a T, &'a [T]>> {
@@ -1004,11 +915,6 @@ where
             None => Err(Error::end_of_input()),
         }
     }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.0.as_ptr() as usize
-    }
 }
 
 impl<'a, T> RangeStream for SliceStream<'a, T>
@@ -1036,6 +942,11 @@ where
         self.0 = rest;
         Ok(range)
     }
+
+    #[inline]
+    fn distance(&self, end: &Self) -> usize {
+        self.0.distance(&end.0)
+    }
 }
 
 impl<'a, T> FullRangeStream for SliceStream<'a, T>
@@ -1052,9 +963,7 @@ where
 ///
 /// [`from_iter`]: fn.from_iter.html
 #[derive(Clone, Debug)]
-pub struct IteratorStream<I>(I, usize)
-where
-    I: Iterator;
+pub struct IteratorStream<I>(I);
 
 
 impl<I> IteratorStream<I>
@@ -1062,32 +971,21 @@ where
     I: Iterator,
 {
     /// Converts an `Iterator` into a stream.
+    ///
+    /// NOTE: This type do not implement `Positioned` and `Clone` and must be wrapped with types
+    ///     such as `BufferedStreamRef` and `State` to become a `Stream` which can be parsed
     pub fn new(iter: I) -> IteratorStream<I> {
-        IteratorStream(iter, 0)
+        IteratorStream(iter)
     }
 }
 
-#[deprecated(since = "2.4.0", note = "please use `IteratorStream::new` instead")]
-pub fn from_iter<I>(iter: I) -> IteratorStream<I>
-where
-    I: Iterator,
-{
-    IteratorStream::new(iter)
-}
-
 impl<I> Iterator for IteratorStream<I>
 where
     I: Iterator,
 {
     type Item = I::Item;
     fn next(&mut self) -> Option<I::Item> {
-        match self.0.next() {
-            Some(x) => {
-                self.1 += 1;
-                Some(x)
-            }
-            None => None,
-        }
+        self.0.next()
     }
 }
 
@@ -1097,7 +995,6 @@ where
 {
     type Item = I::Item;
     type Range = I::Item;
-    type Position = usize;
 
     #[inline]
     fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Item>> {
@@ -1106,39 +1003,24 @@ where
             None => Err(Error::end_of_input()),
         }
     }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.1
-    }
 }
 
 pub struct ReadStream<R> {
     bytes: Bytes<R>,
-    offset: usize,
 }
 
 impl<R: Read> StreamOnce for ReadStream<R> {
     type Item = u8;
     type Range = u8;
-    type Position = usize;
 
     #[inline]
     fn uncons(&mut self) -> Result<u8, Error<u8, u8>> {
         match self.bytes.next() {
-            Some(Ok(b)) => {
-                self.offset += 1;
-                Ok(b)
-            }
+            Some(Ok(b)) => Ok(b),
             Some(Err(err)) => Err(err.into()),
             None => Err(Error::end_of_input()),
         }
     }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.offset
-    }
 }
 
 impl<R> ReadStream<R>
@@ -1147,16 +1029,20 @@ where
 {
     /// Creates a `StreamOnce` instance from a value implementing `std::io::Read`.
     ///
+    /// NOTE: This type do not implement `Positioned` and `Clone` and must be wrapped with types
+    ///     such as `BufferedStreamRef` and `State` to become a `Stream` which can be parsed
+    ///
     /// ```rust
     /// # extern crate combine;
     /// use combine::*;
     /// use combine::byte::*;
     /// use combine::primitives::{BufferedStream, ReadStream};
+    /// use combine::state::State;
     /// use std::io::Read;
     ///
     /// # fn main() {
     /// let mut input: &[u8] = b"123,";
-    /// let stream = BufferedStream::new(ReadStream::new(&mut input), 1);
+    /// let stream = BufferedStream::new(State::new(ReadStream::new(&mut input)), 1);
     /// let result = (many(digit()), byte(b','))
     ///     .parse(stream.as_stream())
     ///     .map(|t| t.0);
@@ -1166,116 +1052,36 @@ where
     pub fn new(read: R) -> ReadStream<R> {
         ReadStream {
             bytes: read.bytes(),
-            offset: 0,
         }
     }
 }
 
-#[deprecated(since = "2.4.0", note = "please use `ReadStream::new` instead")]
-pub fn from_read<R>(read: R) -> ReadStream<R>
-where
-    R: Read,
-{
-    ReadStream::new(read)
-}
-
-/// Trait for updating the position for types which can be yielded from a `Stream`.
-pub trait Positioner: PartialEq {
-    /// The type which keeps track of the position.
-    type Position: Clone + Ord;
-    /// Creates a start position
-    fn start() -> Self::Position;
-    /// Updates the position given that `self` has been taken from the stream
-    fn update(&self, position: &mut Self::Position);
-}
-
-impl<'a, T: ?Sized> Positioner for &'a T
-where
-    T: Positioner,
-{
-    type Position = T::Position;
-    fn start() -> T::Position {
-        T::start()
-    }
-    fn update(&self, position: &mut T::Position) {
-        (*self).update(position)
-    }
-}
-
-impl<T> Positioner for [T]
-where
-    T: Positioner,
-{
-    type Position = T::Position;
-    fn start() -> T::Position {
-        T::start()
-    }
-    fn update(&self, position: &mut T::Position) {
-        for t in self {
-            t.update(position);
-        }
-    }
-}
-
-impl<'a, T> Positioner for SliceStream<'a, T>
-where
-    T: Positioner + 'a,
-{
-    type Position = T::Position;
-    fn start() -> T::Position {
-        T::start()
-    }
-    fn update(&self, position: &mut T::Position) {
-        for t in self.0 {
-            t.update(position);
-        }
-    }
-}
-
-impl Positioner for str {
-    type Position = SourcePosition;
-    fn start() -> SourcePosition {
-        char::start()
-    }
-    fn update(&self, position: &mut SourcePosition) {
-        for t in self.chars() {
-            t.update(position);
-        }
-    }
-}
-
-impl Positioner for char {
-    type Position = SourcePosition;
-    fn start() -> SourcePosition {
-        SourcePosition { line: 1, column: 1 }
-    }
-    fn update(&self, position: &mut SourcePosition) {
-        position.column += 1;
-        if *self == '\n' {
-            position.column = 1;
-            position.line += 1;
+/// Error wrapper which lets parsers track which parser in a sequence of sub-parsers has emitted
+/// the error. `Tracked::from` can be used to construct this and it should otherwise be
+/// ignored outside of combine.
+#[derive(Clone, PartialEq, Debug, Copy)]
+pub struct Tracked<E> {
+    /// The error returned
+    pub error: E,
+    #[doc(hidden)]
+    pub offset: ErrorOffset,
+}
+
+impl<E> From<E> for Tracked<E> {
+    fn from(error: E) -> Self {
+        Tracked {
+            error: error,
+            offset: ErrorOffset(1),
         }
     }
 }
 
-impl Positioner for u8 {
-    type Position = BytePosition;
-
-    fn start() -> BytePosition {
-        BytePosition { position: 0 }
-    }
-
-    fn update(&self, b: &mut BytePosition) {
-        b.position += 1;
-    }
-}
-
 #[derive(Clone, PartialEq, Debug, Copy)]
 pub enum FastResult<T, E> {
     ConsumedOk(T),
     EmptyOk(T),
     ConsumedErr(E),
-    EmptyErr(E),
+    EmptyErr(Tracked<E>),
 }
 
 impl<T, E> FastResult<T, E> {
@@ -1284,7 +1090,10 @@ impl<T, E> FastResult<T, E> {
             ConsumedOk(ref t) => ConsumedOk(t),
             EmptyOk(ref t) => EmptyOk(t),
             ConsumedErr(ref e) => ConsumedErr(e),
-            EmptyErr(ref e) => EmptyErr(e),
+            EmptyErr(ref e) => EmptyErr(Tracked {
+                error: &e.error,
+                offset: e.offset,
+            }),
         }
     }
 
@@ -1295,7 +1104,8 @@ impl<T, E> FastResult<T, E> {
         match self {
             ConsumedOk(t) => match f(t) {
                 ConsumedOk(t2) | EmptyOk(t2) => ConsumedOk(t2),
-                EmptyErr(e) | ConsumedErr(e) => ConsumedErr(e),
+                EmptyErr(e) => ConsumedErr(e.error),
+                ConsumedErr(e) => ConsumedErr(e),
             },
             EmptyOk(t) => f(t),
             ConsumedErr(e) => ConsumedErr(e),
@@ -1306,7 +1116,7 @@ impl<T, E> FastResult<T, E> {
 
 impl<T, E> ConsumedResult<T, E>
 where
-    E: StreamOnce,
+    E: StreamOnce + Positioned,
 {
     pub fn map<F, T2>(self, f: F) -> ConsumedResult<F::Output, E>
     where
@@ -1325,14 +1135,14 @@ where
 /// A `Result` type which has the consumed status flattened into the result.
 /// Conversions to and from `std::result::Result` can be done using `result.into()` or
 /// `From::from(result)`
-pub type ConsumedResult<O, I> = FastResult<(O, I), ParseError<I>>;
+pub type ConsumedResult<O, I> = FastResult<(O, I), StreamError<I>>;
 
-impl<T, E> Into<Result<Consumed<T>, Consumed<E>>> for FastResult<T, E> {
-    fn into(self) -> Result<Consumed<T>, Consumed<E>> {
+impl<T, E> Into<Result<Consumed<T>, Consumed<Tracked<E>>>> for FastResult<T, E> {
+    fn into(self) -> Result<Consumed<T>, Consumed<Tracked<E>>> {
         match self {
             ConsumedOk(t) => Ok(Consumed::Consumed(t)),
-            EmptyOk(t) => Ok(Consumed::Empty(t)), 
-            ConsumedErr(e) => Err(Consumed::Consumed(e)),
+            EmptyOk(t) => Ok(Consumed::Empty(t)),
+            ConsumedErr(e) => Err(Consumed::Consumed(e.into())),
             EmptyErr(e) => Err(Consumed::Empty(e)),
         }
     }
@@ -1340,14 +1150,14 @@ impl<T, E> Into<Result<Consumed<T>, Consumed<E>>> for FastResult<T, E> {
 
 impl<O, I> Into<ParseResult<O, I>> for ConsumedResult<O, I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
 {
     fn into(self) -> ParseResult<O, I> {
         use self::FastResult::*;
         match self {
             ConsumedOk((t, i)) => Ok((t, Consumed::Consumed(i))),
-            EmptyOk((t, i)) => Ok((t, Consumed::Empty(i))), 
-            ConsumedErr(e) => Err(Consumed::Consumed(e)),
+            EmptyOk((t, i)) => Ok((t, Consumed::Empty(i))),
+            ConsumedErr(e) => Err(Consumed::Consumed(e.into())),
             EmptyErr(e) => Err(Consumed::Empty(e)),
         }
     }
@@ -1355,14 +1165,14 @@ where
 
 impl<O, I> From<ParseResult<O, I>> for ConsumedResult<O, I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
 {
     fn from(result: ParseResult<O, I>) -> ConsumedResult<O, I> {
         use self::FastResult::*;
         match result {
             Ok((t, Consumed::Consumed(i))) => ConsumedOk((t, i)),
             Ok((t, Consumed::Empty(i))) => EmptyOk((t, i)),
-            Err(Consumed::Consumed(e)) => ConsumedErr(e),
+            Err(Consumed::Consumed(e)) => ConsumedErr(e.error),
             Err(Consumed::Empty(e)) => EmptyErr(e),
         }
     }
@@ -1396,10 +1206,10 @@ pub trait Parser {
     fn parse(
         &mut self,
         input: Self::Input,
-    ) -> Result<(Self::Output, Self::Input), ParseError<Self::Input>> {
+    ) -> Result<(Self::Output, Self::Input), StreamError<Self::Input>> {
         match self.parse_stream(input) {
             Ok((v, state)) => Ok((v, state.into_inner())),
-            Err(error) => Err(error.into_inner()),
+            Err(error) => Err(error.into_inner().error),
         }
     }
 
@@ -1433,7 +1243,7 @@ pub trait Parser {
         let mut result = self.parse_lazy(input.clone());
         if let FastResult::EmptyErr(ref mut error) = result {
             if let Ok(t) = input.uncons() {
-                error.add_error(Error::Unexpected(Info::Token(t)));
+                error.error.add_error(Error::Unexpected(Info::Token(t)));
             }
             self.add_error(error);
         }
@@ -1471,7 +1281,15 @@ pub trait Parser {
     /// See [`parse_lazy`] for details.
     ///
     /// [`parse_lazy`]: trait.Parser.html#method.parse_lazy
-    fn add_error(&mut self, _error: &mut ParseError<Self::Input>) {}
+    fn add_error(&mut self, _error: &mut Tracked<StreamError<Self::Input>>) {}
+
+    /// Returns how many parsers this parser contains
+    ///
+    /// This should not be implemented explicitly outside of combine.
+    #[doc(hidden)]
+    fn parser_count(&self) -> ErrorOffset {
+        ErrorOffset(1)
+    }
 
     /// Borrows a parser instead of consuming it.
     ///
@@ -1625,7 +1443,7 @@ pub trait Parser {
     ///         }
     ///         else {
     ///             let position = input.position();
-    ///             let err = ParseError::new(position, Error::Message("Not a nine".into()));
+    ///             let err = ParseError::new(position, Error::Message("Not a nine".into())).into();
     ///             Err((Consumed::Empty(err)))
     ///         }
     ///     }))
@@ -1681,7 +1499,8 @@ pub trait Parser {
     fn flat_map<F, B>(self, f: F) -> FlatMap<Self, F>
     where
         Self: Sized,
-        F: FnMut(Self::Output) -> Result<B, ParseError<Self::Input>>,
+        F: FnMut(Self::Output)
+            -> Result<B, StreamError<Self::Input>>,
     {
         flat_map(self, f)
     }
@@ -1691,13 +1510,14 @@ pub trait Parser {
     /// ```
     /// # extern crate combine;
     /// # use combine::*;
-    /// # use combine::primitives::{Error, Positioner};
+    /// # use combine::primitives::Error;
+    /// # use combine::state::SourcePosition;
     /// # fn main() {
     /// let result = token('9')
     ///     .message("Not a nine")
     ///     .parse(State::new("8"));
     /// assert_eq!(result, Err(ParseError {
-    ///     position: <char as Positioner>::start(),
+    ///     position: SourcePosition::default(),
     ///     errors: vec![
     ///         Error::Unexpected('8'.into()),
     ///         Error::Expected('9'.into()),
@@ -1720,13 +1540,14 @@ pub trait Parser {
     /// ```
     /// # extern crate combine;
     /// # use combine::*;
-    /// # use combine::primitives::{Error, Positioner};
+    /// # use combine::primitives::Error;
+    /// # use combine::state::SourcePosition;
     /// # fn main() {
     /// let result = token('9')
     ///     .expected("nine")
     ///     .parse(State::new("8"));
     /// assert_eq!(result, Err(ParseError {
-    ///     position: <char as Positioner>::start(),
+    ///     position: SourcePosition::default(),
     ///     errors: vec![Error::Unexpected('8'.into()), Error::Expected("nine".into())]
     /// }));
     /// # }
@@ -1745,7 +1566,7 @@ pub trait Parser {
     /// ```
     /// # extern crate combine;
     /// # use combine::*;
-    /// # use combine::primitives::SourcePosition;
+    /// # use combine::state::SourcePosition;
     /// # use combine::char::digit;
     /// # fn main() {
     /// let mut parser = many1(digit())
@@ -1767,8 +1588,8 @@ pub trait Parser {
         and_then(self, f)
     }
 
-    /// Creates an iterator from a parser and a state. Can be used as an alternative to [`many`] when
-    /// collecting directly into a `FromIterator` type is not desirable.
+    /// Creates an iterator from a parser and a state. Can be used as an alternative to [`many`]
+    /// when collecting directly into a `FromIterator` type is not desirable.
     ///
     /// ```
     /// # extern crate combine;
@@ -1804,7 +1625,10 @@ pub trait Parser {
     /// # extern crate combine;
     /// # use combine::*;
     /// # fn main() {
-    /// fn test<'input, F>(c: char, f: F) ->  Box<Parser<Input = &'input str, Output = (char, char)>>
+    /// fn test<'input, F>(
+    ///     c: char,
+    ///     f: F)
+    ///     -> Box<Parser<Input = &'input str, Output = (char, char)>>
     ///     where F: FnMut(char) -> bool + 'static
     /// {
     ///     (token(c), satisfy(f)).boxed()
@@ -1845,7 +1669,7 @@ where
     }
 
     #[inline(always)]
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
         (**self).add_error(error)
     }
 }
@@ -1873,61 +1697,61 @@ where
     }
 
     #[inline(always)]
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
         (**self).add_error(error)
     }
 }
 
-/// A `BufferedStream` wraps an instance `StreamOnce`, allowing it to be used as a `Stream`.
-pub struct BufferedStream<'a, I>
+/// A `BufferedStreamRef` wraps an instance `StreamOnce`, allowing it to be used as a `Stream`.
+pub struct BufferedStreamRef<'a, I>
 where
-    I: StreamOnce + 'a,
+    I: StreamOnce + Positioned + 'a,
     I::Item: 'a,
 {
     offset: usize,
-    buffer: &'a SharedBufferedStream<I>,
+    buffer: &'a BufferedStream<I>,
 }
 
-impl<'a, I> fmt::Debug for BufferedStream<'a, I>
+impl<'a, I> fmt::Debug for BufferedStreamRef<'a, I>
 where
-    I: StreamOnce + 'a,
+    I: StreamOnce + Positioned + 'a,
     I::Item: 'a,
 {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         let buffer_offset = unsafe { (*self.buffer.buffer.get()).offset };
         write!(
             f,
-            "BufferedStream {{ offset: {:?} buffer_offset: {:?} }}",
+            "BufferedStreamRef {{ offset: {:?} buffer_offset: {:?} }}",
             self.offset,
             buffer_offset
         )
     }
 }
 
-impl<'a, I> Clone for BufferedStream<'a, I>
+impl<'a, I> Clone for BufferedStreamRef<'a, I>
 where
-    I: StreamOnce + 'a,
+    I: StreamOnce + Positioned + 'a,
     I::Position: Clone,
     I::Item: 'a,
 {
-    fn clone(&self) -> BufferedStream<'a, I> {
-        BufferedStream {
+    fn clone(&self) -> BufferedStreamRef<'a, I> {
+        BufferedStreamRef {
             offset: self.offset,
             buffer: self.buffer,
         }
     }
 }
 
-pub struct SharedBufferedStream<I>
+pub struct BufferedStream<I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
 {
     buffer: UnsafeCell<BufferedStreamInner<I>>,
 }
 
 struct BufferedStreamInner<I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
 {
     offset: usize,
     iter: I,
@@ -1936,7 +1760,7 @@ where
 
 impl<I> BufferedStreamInner<I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
     I::Position: Clone,
     I::Item: Clone,
 {
@@ -1983,14 +1807,33 @@ where
     }
 }
 
-impl<I> SharedBufferedStream<I>
+impl<I> BufferedStream<I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
     I::Position: Clone,
     I::Item: Clone,
 {
-    pub fn as_stream(&self) -> BufferedStream<I> {
+    /// Constructs a new `BufferedStream` froma a `StreamOnce` instance with a `lookahead`
+    /// number of elements that can be stored in the buffer.
+    ///
+    /// `BufferedStream` do not implement `Stream` itself. To retrieve a value which implement
+    /// `Stream`, `as_stream` must be called.
+    pub fn new(iter: I, lookahead: usize) -> BufferedStream<I> {
         BufferedStream {
+            buffer: UnsafeCell::new(BufferedStreamInner {
+                offset: 0,
+                iter: iter,
+                buffer: VecDeque::with_capacity(lookahead),
+            }),
+        }
+    }
+
+    /// Creates a `BufferedStreamRef` which implements `Stream`.
+    ///
+    /// `BufferedStreamRef` always implement `Stream` allowing one-shot streams to used as if it
+    /// could be used multiple times.
+    pub fn as_stream(&self) -> BufferedStreamRef<I> {
+        BufferedStreamRef {
             offset: 0,
             buffer: self,
         }
@@ -2005,35 +1848,31 @@ where
     }
 }
 
-impl<'a, I> BufferedStream<'a, I>
+impl<'a, I> BufferedStreamRef<'a, I>
 where
-    I: StreamOnce,
+    I: StreamOnce + Positioned,
 {
-    /// Constructs a new `BufferedStream` froma a `StreamOnce` instance with a `lookahead` number
-    /// of elements stored in the buffer.
-    ///
-    /// `BufferedStream` always implement `Stream` allowing one-shot streams to used as if it could
-    /// be used multiple times.
-    pub fn new(iter: I, lookahead: usize) -> SharedBufferedStream<I> {
-        SharedBufferedStream {
-            buffer: UnsafeCell::new(BufferedStreamInner {
-                offset: 0,
-                iter: iter,
-                buffer: VecDeque::with_capacity(lookahead),
-            }),
-        }
+}
+
+impl<'a, I> Positioned for BufferedStreamRef<'a, I>
+where
+    I: StreamOnce + Positioned,
+{
+    type Position = I::Position;
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.buffer.position(self.offset)
     }
 }
 
-impl<'a, I> StreamOnce for BufferedStream<'a, I>
+impl<'a, I> StreamOnce for BufferedStreamRef<'a, I>
 where
-    I: StreamOnce + 'a,
-    I::Position: Clone,
+    I: StreamOnce + Positioned + 'a,
     I::Item: Clone + PartialEq + 'a,
 {
     type Item = I::Item;
     type Range = I::Range;
-    type Position = I::Position;
 
     #[inline]
     fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Range>> {
@@ -2041,11 +1880,6 @@ where
         self.offset += 1;
         Ok(value)
     }
-
-    #[inline(always)]
-    fn position(&self) -> Self::Position {
-        self.buffer.position(self.offset)
-    }
 }
 
 #[cfg(test)]
diff --git a/src/range.rs b/src/range.rs
index 28be9764..33e206f9 100644
--- a/src/range.rs
+++ b/src/range.rs
@@ -1,6 +1,7 @@
 use std::marker::PhantomData;
 
-use primitives::{ConsumedResult, Error, Info, ParseError, Parser, RangeStream};
+use primitives::{ConsumedResult, Error, Info, ParseError, Parser, RangeStream, StreamError,
+                 StreamOnce, Tracked};
 use primitives::FastResult::*;
 
 pub struct Range<I>(I::Range)
@@ -23,17 +24,63 @@ where
             Ok(other) => if other == self.0 {
                 ConsumedOk((other, input))
             } else {
-                EmptyErr(ParseError::empty(position))
+                EmptyErr(ParseError::empty(position).into())
             },
-            Err(err) => EmptyErr(ParseError::new(position, err)),
+            Err(err) => EmptyErr(ParseError::new(position, err).into()),
         }
     }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
         // TODO Add unexpected message?
-        errors.add_error(Error::Expected(Info::Range(self.0.clone())));
+        errors
+            .error
+            .add_error(Error::Expected(Info::Range(self.0.clone())));
     }
 }
 
+pub struct Recognize<P>(P);
+
+impl<P> Parser for Recognize<P>
+where
+    P: Parser,
+    P::Input: RangeStream,
+    <P::Input as StreamOnce>::Range: ::primitives::Range,
+{
+    type Input = P::Input;
+    type Output = <P::Input as StreamOnce>::Range;
+
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        let (_, new_input) = ctry!(self.0.parse_lazy(input.clone()));
+        let distance = input.distance(&new_input.into_inner());
+        take(distance).parse_lazy(input)
+    }
+    fn add_error(&mut self, errors: &mut Tracked<StreamError<Self::Input>>) {
+        self.0.add_error(errors)
+    }
+}
+
+/// Zero-copy parser which reads a range of length `i.len()` and succeds if `i` is equal to that
+/// range.
+///
+/// ```
+/// # extern crate combine;
+/// # use combine::range::recognize;
+/// # use combine::char::letter;
+/// # use combine::*;
+/// # fn main() {
+/// let mut parser = recognize(skip_many1(letter()));
+/// assert_eq!(parser.parse("hello world"), Ok(("hello", " world")));
+/// assert!(parser.parse("!").is_err());
+/// # }
+/// ```
+#[inline(always)]
+pub fn recognize<P>(parser: P) -> Recognize<P>
+where
+    P: Parser,
+{
+    Recognize(parser)
+}
+
 /// Zero-copy parser which reads a range of length `i.len()` and succeds if `i` is equal to that
 /// range.
 ///
@@ -72,7 +119,7 @@ where
         let position = input.position();
         match input.uncons_range(self.0) {
             Ok(x) => ConsumedOk((x, input)),
-            Err(err) => EmptyErr(ParseError::new(position, err)),
+            Err(err) => EmptyErr(ParseError::new(position, err).into()),
         }
     }
 }
@@ -158,7 +205,7 @@ where
             ConsumedOk((v, input)) => ConsumedOk((v, input)),
             EmptyOk((_, input)) => {
                 let position = input.position();
-                EmptyErr(ParseError::empty(position))
+                EmptyErr(ParseError::empty(position).into())
             }
             EmptyErr(err) => EmptyErr(err),
             ConsumedErr(err) => ConsumedErr(err),
@@ -231,7 +278,7 @@ where
                         }
                     }
                 }
-                Err(e) => return EmptyErr(ParseError::new(look_ahead_input.position(), e)),
+                Err(e) => return EmptyErr(ParseError::new(look_ahead_input.position(), e).into()),
             };
         }
     }
diff --git a/src/regex.rs b/src/regex.rs
index 14c92d0f..c0ea0e88 100644
--- a/src/regex.rs
+++ b/src/regex.rs
@@ -37,17 +37,16 @@ extern crate regex;
 use std::iter::FromIterator;
 use std::marker::PhantomData;
 
-use primitives::{ConsumedResult, Error, FullRangeStream, ParseError, Parser};
+use primitives::{ConsumedResult, Error, FullRangeStream, ParseError, Parser, StreamError, Tracked};
 use primitives::FastResult::*;
 use range::take;
 
 struct First<T>(Option<T>);
 
-impl<A> FromIterator<A> for First<A>
-{
+impl<A> FromIterator<A> for First<A> {
     fn from_iter<T>(iter: T) -> Self
     where
-        T: IntoIterator<Item = A>
+        T: IntoIterator<Item = A>,
     {
         First(iter.into_iter().next())
     }
@@ -218,11 +217,11 @@ where
         if self.0.is_match(input.range()) {
             EmptyOk((input.range(), input))
         } else {
-            EmptyErr(ParseError::empty(input.position()))
+            EmptyErr(ParseError::empty(input.position()).into())
         }
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        error.error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
     }
 }
 
@@ -269,11 +268,11 @@ where
         let (end, First(value)) = self.0.find_iter(input.range());
         match value {
             Some(value) => take(end).parse_lazy(input).map(|_| value),
-            None => EmptyErr(ParseError::empty(input.position())),
+            None => EmptyErr(ParseError::empty(input.position()).into()),
         }
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        error.error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
     }
 }
 
@@ -325,8 +324,8 @@ where
         let (end, value) = self.0.find_iter(input.range());
         take(end).parse_lazy(input).map(|_| value)
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        error.error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
     }
 }
 
@@ -377,11 +376,11 @@ where
         let (end, First(value)) = self.0.captures(input.range());
         match value {
             Some(value) => take(end).parse_lazy(input).map(|_| value),
-            None => EmptyErr(ParseError::empty(input.position())),
+            None => EmptyErr(ParseError::empty(input.position()).into()),
         }
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        error.error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
     }
 }
 
@@ -440,8 +439,8 @@ where
         let (end, value) = self.0.captures(input.range());
         take(end).parse_lazy(input).map(|_| value)
     }
-    fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
-        error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
+    fn add_error(&mut self, error: &mut Tracked<StreamError<Self::Input>>) {
+        error.error.add_error(Error::Expected(format!("/{}/", self.0.as_str()).into()))
     }
 }
 
diff --git a/src/state.rs b/src/state.rs
new file mode 100644
index 00000000..ce32a40b
--- /dev/null
+++ b/src/state.rs
@@ -0,0 +1,313 @@
+use std::fmt;
+
+use primitives::{Error, FullRangeStream, IteratorStream, Positioned, RangeStream, ReadStream,
+                 SliceStream, StreamOnce};
+
+/// Trait for tracking the current position of a `Stream`.
+pub trait Positioner<Item> {
+    /// The type which keeps track of the position
+    type Position: Clone + Ord;
+    /// Returns the current position
+    fn position(&self) -> Self::Position;
+    /// Updates the position given that `item` has been taken from the stream
+    fn update(&mut self, item: &Item);
+}
+
+/// Trait for tracking the current position of a `RangeStream`.
+pub trait RangePositioner<Item, Range>: Positioner<Item> {
+    /// Updates the position given that `range` has been taken from the stream
+    fn update_range(&mut self, range: &Range);
+}
+
+/// Defines a default `Positioner` type for a particular `Stream` type.
+pub trait DefaultPositioned {
+    type Positioner: Default;
+}
+
+impl<'a> DefaultPositioned for &'a str {
+    type Positioner = SourcePosition;
+}
+
+impl<'a, T> DefaultPositioned for &'a [T] {
+    type Positioner = IndexPositioner;
+}
+
+impl<'a, T> DefaultPositioned for SliceStream<'a, T> {
+    type Positioner = IndexPositioner;
+}
+
+impl<T> DefaultPositioned for IteratorStream<T> {
+    type Positioner = IndexPositioner;
+}
+
+impl<R> DefaultPositioned for ReadStream<R> {
+    type Positioner = IndexPositioner;
+}
+
+/// The `State<I>` struct maintains the current position in the stream `I` using
+/// the `Positioner` trait to track the position.
+///
+/// ```
+/// # extern crate combine;
+/// # use combine::{token, Parser, ParseError};
+/// # use combine::primitives::{Error};
+/// # use combine::state::{State, IndexPositioner};
+/// # fn main() {
+///     let result = token(b'9')
+///         .message("Not a nine")
+///         .parse(State::new(&b"8"[..]));
+///     assert_eq!(result, Err(ParseError {
+///         position: 0,
+///         errors: vec![
+///             Error::Unexpected(b'8'.into()),
+///             Error::Expected(b'9'.into()),
+///             Error::Message("Not a nine".into())
+///         ]
+///     }));
+/// # }
+/// ```
+#[derive(Clone, Debug, PartialEq)]
+pub struct State<I, X> {
+    /// The input stream used when items are requested
+    pub input: I,
+    /// The positioner used to update the current position
+    pub positioner: X,
+}
+
+impl<I, X> State<I, X>
+where
+    I: StreamOnce,
+    X: Positioner<I::Item>,
+{
+    /// Creates a new `State<I, X>` from an input stream and a positioner.
+    pub fn with_positioner(input: I, positioner: X) -> State<I, X> {
+        State {
+            input: input,
+            positioner: positioner,
+        }
+    }
+}
+
+impl<I> State<I, I::Positioner>
+where
+    I: StreamOnce + DefaultPositioned,
+    I::Positioner: Positioner<I::Item>,
+{
+    /// Creates a new `State<I, X>` from an input stream and its default positioner.
+    pub fn new(input: I) -> State<I, I::Positioner> {
+        State::with_positioner(input, I::Positioner::default())
+    }
+}
+
+impl<I, X> Positioned for State<I, X>
+where
+    I: StreamOnce,
+    X: Positioner<I::Item>,
+{
+    type Position = X::Position;
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.positioner.position()
+    }
+}
+
+impl<I, X> StreamOnce for State<I, X>
+where
+    I: StreamOnce,
+    X: Positioner<I::Item>,
+{
+    type Item = I::Item;
+    type Range = I::Range;
+
+    #[inline]
+    fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Range>> {
+        self.input.uncons().map(|c| {
+            self.positioner.update(&c);
+            c
+        })
+    }
+}
+
+/// The `IndexPositioner<Item, Range>` struct maintains the current index into the stream `I`.  The
+/// initial index is index 0.  Each `Item` consumed increments the index by 1; each `range` consumed
+/// increments the position by `range.len()`.
+#[derive(Clone, Debug, Default, PartialEq)]
+pub struct IndexPositioner(usize);
+
+impl<Item> Positioner<Item> for IndexPositioner
+where
+    Item: PartialEq + Clone,
+{
+    type Position = usize;
+
+    #[inline(always)]
+    fn position(&self) -> usize {
+        self.0
+    }
+
+    #[inline]
+    fn update(&mut self, _item: &Item) {
+        self.0 += 1
+    }
+}
+
+impl IndexPositioner {
+    pub fn new() -> IndexPositioner {
+        IndexPositioner::new_with_position(0)
+    }
+
+    pub fn new_with_position(position: usize) -> IndexPositioner {
+        IndexPositioner(position)
+    }
+}
+
+impl<Item, Range> RangePositioner<Item, Range> for IndexPositioner
+where
+    Item: PartialEq + Clone,
+    Range: PartialEq + Clone + ::primitives::Range,
+{
+    fn update_range(&mut self, range: &Range) {
+        self.0 += range.len()
+    }
+}
+
+/// Struct which represents a position in a source file.
+#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
+pub struct SourcePosition {
+    /// Current line of the input
+    pub line: i32,
+    /// Current column of the input
+    pub column: i32,
+}
+
+impl Default for SourcePosition {
+    fn default() -> Self {
+        SourcePosition { line: 1, column: 1 }
+    }
+}
+
+impl fmt::Display for SourcePosition {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "line: {}, column: {}", self.line, self.column)
+    }
+}
+
+impl SourcePosition {
+    pub fn new() -> Self {
+        SourcePosition::default()
+    }
+}
+
+impl Positioner<char> for SourcePosition {
+    type Position = SourcePosition;
+
+    #[inline(always)]
+    fn position(&self) -> SourcePosition {
+        self.clone()
+    }
+
+    #[inline]
+    fn update(&mut self, item: &char) {
+        self.column += 1;
+        if *item == '\n' {
+            self.column = 1;
+            self.line += 1;
+        }
+    }
+}
+
+impl<'a> RangePositioner<char, &'a str> for SourcePosition {
+    fn update_range(&mut self, range: &&'a str) {
+        for c in range.chars() {
+            self.update(&c);
+        }
+    }
+}
+
+
+impl<I, X> RangeStream for State<I, X>
+where
+    I: RangeStream,
+    X: Clone + RangePositioner<I::Item, I::Range>,
+    I::Position: Clone + Ord,
+{
+    #[inline]
+    fn uncons_range(&mut self, size: usize) -> Result<I::Range, Error<I::Item, I::Range>> {
+        self.input.uncons_range(size).map(|range| {
+            self.positioner.update_range(&range);
+            range
+        })
+    }
+
+    #[inline]
+    fn uncons_while<F>(&mut self, mut predicate: F) -> Result<I::Range, Error<I::Item, I::Range>>
+    where
+        F: FnMut(I::Item) -> bool,
+    {
+        let positioner = &mut self.positioner;
+        self.input.uncons_while(|t| if predicate(t.clone()) {
+            positioner.update(&t);
+            true
+        } else {
+            false
+        })
+    }
+
+    #[inline]
+    fn distance(&self, end: &Self) -> usize {
+        self.input.distance(&end.input)
+    }
+}
+
+impl<I, X> FullRangeStream for State<I, X>
+where
+    I: FullRangeStream,
+    I::Position: Clone + Ord,
+    X: Clone + RangePositioner<I::Item, I::Range>,
+{
+    fn range(&self) -> Self::Range {
+        self.input.range()
+    }
+}
+
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use primitives::Parser;
+
+    #[test]
+    fn test_positioner() {
+        let input = ["a".to_string(), "b".to_string()];
+        let mut parser = ::any();
+        let result = parser.parse(State::new(&input[..]));
+        assert_eq!(
+            result,
+            Ok((
+                "a".to_string(),
+                State::with_positioner(
+                    &["b".to_string()][..],
+                    IndexPositioner::new_with_position(1)
+                )
+            ))
+        );
+    }
+
+    #[test]
+    fn test_range_positioner() {
+        let input = ["a".to_string(), "b".to_string(), "c".to_string()];
+        let mut parser = ::range::take(2);
+        let result = parser.parse(State::new(&input[..]));
+        assert_eq!(
+            result,
+            Ok((
+                &["a".to_string(), "b".to_string()][..],
+                State::with_positioner(
+                    &["c".to_string()][..],
+                    IndexPositioner::new_with_position(2)
+                )
+            ))
+        );
+    }
+}


Test patch:
diff --git a/test.rs b/test.rs
new file mode 100644
index 00000000..be4de527
--- /dev/null
+++ b/test.rs
@@ -0,0 +1,36 @@
+#[macro_export]
+#[doc(hidden)]
+macro_rules! seq_parser_impl {
+    (; $name: ident $($tt: tt)*) => {
+        $name { $($tt)* }
+    };
+    (_ : $first_parser: expr; $name: ident $($tt: tt)*) => {
+        $name { $($tt)* }
+    };
+    ($first_field: ident : $first_parser: expr; $name: ident $($tt: tt)*) => {
+        seq_parser_impl!(; $name $($tt)* $first_field : $first_field,)
+    };
+    (_ : $first_parser: expr, $($field: ident : $parser: expr),+; $name: ident $($tt: tt)*) => {
+        seq_parser_impl!( $($field : $parser),+; $name $($tt)* )
+    };
+    ($first_field: ident : $first_parser: expr, $($field: ident : $parser: expr),+; $name: ident $($tt: tt)*) => {
+        seq_parser_impl!( $($field : $parser),+; $name $($tt)* $first_field: $first_field, )
+    };
+}
+
+#[macro_export]
+macro_rules! seq_parser { 
+    ($name: ident { $($field: ident : $parser: expr),* }) => {
+        ( $($parser),* )
+            .map(|( $($field),* )|
+                seq_parser_impl!($($field : $parser),*; $name )
+            )
+    }
+}
+struct Test {
+    a: i32,
+    b: i32,
+}
+fn main() {
+    seq_parser!(Test { a: 1, b: 2 });
+}
\ No newline at end of file
diff --git a/tests/buffered_stream.rs b/tests/buffered_stream.rs
index 0d648dab..8dd78b63 100644
--- a/tests/buffered_stream.rs
+++ b/tests/buffered_stream.rs
@@ -1,14 +1,11 @@
 // The feature `buffered_stream` must be enabled to run these tests
 extern crate combine;
-use combine::primitives::{BufferedStream, Error};
+use combine::primitives::{BufferedStream, Error, IteratorStream};
 use combine::char::{char, digit, spaces, string};
-use combine::{choice, many, sep_by, try, Parser, StreamOnce, many1};
-
-#[allow(deprecated)]
-use combine::from_iter;
+use combine::{choice, many, sep_by, try, Parser, Positioned, many1};
+use combine::state::State;
 
 #[test]
-#[allow(deprecated)]
 fn shared_stream_buffer() {
     // Iterator that can't be cloned
     let text = "10,222,3,44".chars().map(|c| if c.is_digit(10) {
@@ -16,7 +13,7 @@ fn shared_stream_buffer() {
     } else {
         c
     });
-    let buffer = BufferedStream::new(from_iter(text), 1);
+    let buffer = BufferedStream::new(State::new(IteratorStream::new(text)), 1);
     let int: &mut Parser<Input = _, Output = _> =
         &mut many(digit()).map(|s: String| s.parse::<i64>().unwrap());
     let result = sep_by(int, char(','))
@@ -26,12 +23,11 @@ fn shared_stream_buffer() {
 }
 
 #[test]
-#[allow(deprecated)]
 fn shared_stream_backtrack() {
     let text = "apple,apple,ananas,orangeblah";
     let mut iter = text.chars();
     // Iterator that can't be cloned
-    let buffer = BufferedStream::new(from_iter(&mut iter), 2);
+    let buffer = BufferedStream::new(State::new(IteratorStream::new(&mut iter)), 2);
     let stream = buffer.as_stream();
 
     let value: &mut Parser<Input = _, Output = _> = &mut choice([
@@ -45,12 +41,11 @@ fn shared_stream_backtrack() {
 }
 
 #[test]
-#[allow(deprecated)]
 fn shared_stream_insufficent_backtrack() {
     let text = "apple,apple,ananas,orangeblah";
     let mut iter = text.chars();
     // Iterator that can't be cloned
-    let buffer = BufferedStream::new(from_iter(&mut iter), 1);
+    let buffer = BufferedStream::new(State::new(IteratorStream::new(&mut iter)), 1);
     let stream = buffer.as_stream();
 
     let value: &mut Parser<Input = _, Output = _> = &mut choice([
@@ -73,10 +68,9 @@ fn shared_stream_insufficent_backtrack() {
 /// Test which checks that a stream which has ended does not repeat the last token in some cases in
 /// which case this test would loop forever
 #[test]
-#[allow(deprecated)]
 fn always_output_end_of_input_after_end_of_input() {
     let text = "10".chars();
-    let buffer = BufferedStream::new(from_iter(text), 1);
+    let buffer = BufferedStream::new(State::new(IteratorStream::new(text)), 1);
     let int = many1(digit()).map(|s: String| s.parse::<i64>().unwrap());
     let result = many(spaces().with(int))
         .parse(buffer.as_stream())
@@ -85,10 +79,9 @@ fn always_output_end_of_input_after_end_of_input() {
 }
 
 #[test]
-#[allow(deprecated)]
 fn position() {
     let text = "10abc".chars();
-    let buffer = BufferedStream::new(from_iter(text), 3);
+    let buffer = BufferedStream::new(State::new(IteratorStream::new(text)), 3);
     let stream = buffer.as_stream();
     println!("{:?}", stream);
     assert_eq!(stream.position(), 0);
diff --git a/tests/ini.rs b/tests/ini.rs
index c9057cb6..adbcba06 100644
--- a/tests/ini.rs
+++ b/tests/ini.rs
@@ -6,7 +6,8 @@ use std::collections::HashMap;
 
 use combine::*;
 use combine::char::space;
-use combine::primitives::{Error, SourcePosition};
+use combine::primitives::Error;
+use combine::state::SourcePosition;
 
 #[derive(PartialEq, Debug)]
 pub struct Ini {
diff --git a/tests/readme.rs b/tests/readme.rs
index 213b766b..7932ba0e 100644
--- a/tests/readme.rs
+++ b/tests/readme.rs
@@ -1,10 +1,13 @@
-
 extern crate combine;
-use combine::{many, Parser};
-use combine::char::letter;
+use combine::{many1, Parser, sep_by};
+use combine::char::{letter, space};
 
 #[test]
 fn readme() {
-    let result = many(letter()).parse("hello world");
-    assert_eq!(result, Ok(("hello".to_string(), " world")));
-}
+    let word = many1(letter());
+
+    let mut parser = sep_by(word, space())
+        .map(|mut words: Vec<String>| words.pop());
+    let result = parser.parse("Pick up that word!");
+    assert_eq!(result, Ok((Some("word".to_string()), "!")));
+}
\ No newline at end of file