Repository: Marwes/combine (language: rust)

Issue:
API request for combining satisfy and map.
I need to parse any of a set of characters, then return different values depending on that character. To do this, I use `satisfy` and then `map`. Simplified example:

``` rust
satisfy(|c| c == 'x' || c == 'y' || c == 'z')
    .map(|c| match c { 'x' => 42, 'y' => 17, 'z' => 0 })
```

Is there an existing way to eliminate the redundancy in my code, while ensuring the parser only consumes known characters? If not, the API I'm looking for is something like:

``` rust
satisfy_mapped(|c| match c { 'x' => Some(42), 'y' => Some(17), 'z' => Some(0), _ => None })
```



Discussion / hints:

Fix patch:
diff --git a/.travis.yml b/.travis.yml
index 3e1abc2c..1d9f5e7e 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -17,12 +17,12 @@ before_script:
 script:
 - |
   cargo build &&
-  cargo test --features test &&
-  travis-cargo --only nightly bench -- --features test &&
+  travis_wait cargo test &&
+  travis-cargo --only nightly bench &&
   travis-cargo --only stable doc
 after_success:
 - travis-cargo --only stable doc-upload
-- travis-cargo coveralls --no-sudo -- --features test
+- travis-cargo coveralls --no-sudo
 env:
   global:
   - TRAVIS_CARGO_NIGHTLY_FEATURE=""
diff --git a/Cargo.toml b/Cargo.toml
index d32f582b..81b95c33 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 
 name = "combine"
-version = "1.3.0"
+version = "2.0.0-beta3"
 authors = ["Markus Westerlind <marwes91@gmail.com>"]
 
 description = "Parser combinators based on the Haskell library parsec."
@@ -20,9 +20,13 @@ license = "MIT"
 name = "combine"
 path = "src/lib.rs"
 
+[dependencies]
+ascii = "0.7.0"
+
+[dev-dependencies]
+byteorder = "0.5.3"
+
+
 [features]
-# Using a feature in combine is considered to be unstable (does not adhere to semver) if you use one or more features
-# then you have been warned that you may experience breaking changes between any release
-buffered_stream = []
-# Feature to be passed as `cargo test --features test` making sure that all tests are run
-test = ["buffered_stream"]
+# Run the mp4 benchmark, requires a mp4 file named `small.mp4` in the benches directory
+mp4 = []
diff --git a/README.md b/README.md
index d0977fbe..54a3f93f 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) [![Coverage Status](https://coveralls.io/repos/Marwes/parser-combinators/badge.svg?branch=master&service=github)](https://coveralls.io/github/Marwes/parser-combinators?branch=master) [![Docs v1](https://docs.rs/combine/badge.svg?version=^1)](https://docs.rs/crate/combine/^1) [![Docs](https://docs.rs/combine/badge.svg?version=2.0.0-beta2)](https://docs.rs/crate/combine/2.0.0-beta2) [![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) [![Coverage Status](https://coveralls.io/repos/Marwes/parser-combinators/badge.svg?branch=master&service=github)](https://coveralls.io/github/Marwes/parser-combinators?branch=master) [![Docs v1](https://docs.rs/combine/badge.svg?version=^1)](https://docs.rs/crate/combine/^1) [![Docs](https://docs.rs/combine/badge.svg?version=2.0.0-beta3)](https://docs.rs/crate/combine/2.0.0-beta3) [![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).
 
@@ -23,7 +23,7 @@ Larger examples can be found in the [tests][tests] and [benches][benches] folder
 
 [Documentation and examples](https://docs.rs/crate/combine)
 
-[Documentation and examples (beta)](https://docs.rs/crate/combine/2.0.0-beta2)
+[Documentation and examples (beta)](https://docs.rs/crate/combine/2.0.0-beta3)
 
 [crates.io](https://crates.io/crates/combine)
 
diff --git a/benches/http-requests.txt b/benches/http-requests.txt
new file mode 100644
index 00000000..40684603
--- /dev/null
+++ b/benches/http-requests.txt
@@ -0,0 +1,494 @@
+GET / HTTP/1.1
+Host: www.reddit.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+
+GET /reddit.v_EZwRzV-Ns.css HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/css,*/*;q=0.1
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /reddit-init.en-us.O1zuMqOOQvY.js HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /reddit.en-us.31yAfSoTsfo.js HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /kill.png HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /icon.png HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+
+GET /favicon.ico HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+
+GET /AMZM4CWd6zstSC8y.jpg HTTP/1.1
+Host: b.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /jz1d5Nm0w97-YyNm.jpg HTTP/1.1
+Host: b.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /aWGO99I6yOcNUKXB.jpg HTTP/1.1
+Host: a.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /rZ_rD5TjrJM0E9Aj.css HTTP/1.1
+Host: e.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/css,*/*;q=0.1
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /tmsPwagFzyTvrGRx.jpg HTTP/1.1
+Host: a.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /KYgUaLvXCK3TCEJx.jpg HTTP/1.1
+Host: a.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /81pzxT5x2ozuEaxX.jpg HTTP/1.1
+Host: e.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /MFqCUiUVPO5V8t6x.jpg HTTP/1.1
+Host: a.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /TFpYTiAO5aEowokv.jpg HTTP/1.1
+Host: e.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /eMWMpmm9APNeNqcF.jpg HTTP/1.1
+Host: e.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /S-IpsJrOKuaK9GZ8.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /3V6dj9PDsNnheDXn.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /wQ3-VmNXhv8sg4SJ.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /ixd1C1njpczEWC22.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /nGsQj15VyOHMwmq8.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /zT4yQmDxQLbIxK1b.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /L5e1HcZLv1iu4nrG.jpg HTTP/1.1
+Host: f.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /WJFFPxD8X4JO_lIG.jpg HTTP/1.1
+Host: f.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /hVMVTDdjuY3bQox5.jpg HTTP/1.1
+Host: f.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /rnWf8CjBcyPQs5y_.jpg HTTP/1.1
+Host: f.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /gZJL1jNylKbGV4d-.jpg HTTP/1.1
+Host: d.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /aNd2zNRLXiMnKUFh.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /droparrowgray.gif HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.redditstatic.com/reddit.v_EZwRzV-Ns.css
+
+GET /sprite-reddit.an0Lnf61Ap4.png HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.redditstatic.com/reddit.v_EZwRzV-Ns.css
+
+GET /ga.js HTTP/1.1
+Host: www.google-analytics.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+If-Modified-Since: Tue, 29 Oct 2013 19:33:51 GMT
+
+GET /reddit/ads.html?sr=-reddit.com&bust2 HTTP/1.1
+Host: static.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /pixel/of_destiny.png?v=hOlmDALJCWWdjzfBV4ZxJPmrdCLWB%2Ftq7Z%2Ffp4Q%2FxXbVPPREuMJMVGzKraTuhhNWxCCwi6yFEZg%3D&r=783333388 HTTP/1.1
+Host: pixel.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /UNcO-h_QcS9PD-Gn.jpg HTTP/1.1
+Host: c.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://e.thumbs.redditmedia.com/rZ_rD5TjrJM0E9Aj.css
+
+GET /welcome-lines.png HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.redditstatic.com/reddit.v_EZwRzV-Ns.css
+
+GET /welcome-upvote.png HTTP/1.1
+Host: www.redditstatic.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.redditstatic.com/reddit.v_EZwRzV-Ns.css
+
+GET /__utm.gif?utmwv=5.5.1&utms=1&utmn=720496082&utmhn=www.reddit.com&utme=8(site*srpath*usertype*uitype)9(%20reddit.com*%20reddit.com-GET_listing*guest*web)11(3!2)&utmcs=UTF-8&utmsr=2560x1600&utmvp=1288x792&utmsc=24-bit&utmul=en-us&utmje=1&utmfl=13.0%20r0&utmdt=reddit%3A%20the%20front%20page%20of%20the%20internet&utmhid=2129416330&utmr=-&utmp=%2F&utmht=1400862512705&utmac=UA-12131688-1&utmcc=__utma%3D55650728.585571751.1400862513.1400862513.1400862513.1%3B%2B__utmz%3D55650728.1400862513.1.1.utmcsr%3D(direct)%7Cutmccn%3D(direct)%7Cutmcmd%3D(none)%3B&utmu=qR~ HTTP/1.1
+Host: www.google-analytics.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /ImnpOQhbXUPkwceN.png HTTP/1.1
+Host: a.thumbs.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /ajax/libs/jquery/1.7.1/jquery.min.js HTTP/1.1
+Host: ajax.googleapis.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /__utm.gif?utmwv=5.5.1&utms=2&utmn=1493472678&utmhn=www.reddit.com&utmt=event&utme=5(AdBlock*enabled*false)(0)8(site*srpath*usertype*uitype)9(%20reddit.com*%20reddit.com-GET_listing*guest*web)11(3!2)&utmcs=UTF-8&utmsr=2560x1600&utmvp=1288x792&utmsc=24-bit&utmul=en-us&utmje=1&utmfl=13.0%20r0&utmdt=reddit%3A%20the%20front%20page%20of%20the%20internet&utmhid=2129416330&utmr=-&utmp=%2F&utmht=1400862512708&utmac=UA-12131688-1&utmni=1&utmcc=__utma%3D55650728.585571751.1400862513.1400862513.1400862513.1%3B%2B__utmz%3D55650728.1400862513.1.1.utmcsr%3D(direct)%7Cutmccn%3D(direct)%7Cutmcmd%3D(none)%3B&utmu=6R~ HTTP/1.1
+Host: www.google-analytics.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /ados.js?q=43 HTTP/1.1
+Host: secure.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /fetch-trackers?callback=jQuery111005268222517967478_1400862512407&ids%5B%5D=t3_25jzeq-t8_k2ii&_=1400862512408 HTTP/1.1
+Host: tracker.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /ados?t=1400862512892&request={%22Placements%22:[{%22A%22:5146,%22S%22:24950,%22D%22:%22main%22,%22AT%22:5},{%22A%22:5146,%22S%22:24950,%22D%22:%22sponsorship%22,%22AT%22:8}],%22Keywords%22:%22-reddit.com%22,%22Referrer%22:%22http%3A%2F%2Fwww.reddit.com%2F%22,%22IsAsync%22:true,%22WriteResults%22:true} HTTP/1.1
+Host: engine.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /pixel/of_doom.png?id=t3_25jzeq-t8_k2ii&hash=da31d967485cdbd459ce1e9a5dde279fef7fc381&r=1738649500 HTTP/1.1
+Host: pixel.redditmedia.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /Extensions/adFeedback.js HTTP/1.1
+Host: static.adzrk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: */*
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /Extensions/adFeedback.css HTTP/1.1
+Host: static.adzrk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/css,*/*;q=0.1
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /reddit/ads-load.html?bust2 HTTP/1.1
+Host: static.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://www.reddit.com/
+
+GET /Advertisers/a774d7d6148046efa89403a8db635a81.jpg HTTP/1.1
+Host: static.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /i.gif?e=eyJhdiI6NjIzNTcsImF0Ijo1LCJjbSI6MTE2MzUxLCJjaCI6Nzk4NCwiY3IiOjMzNzAxNSwiZGkiOiI4NmI2Y2UzYWM5NDM0MjhkOTk2ZTg4MjYwZDE5ZTE1YyIsImRtIjoxLCJmYyI6NDE2MTI4LCJmbCI6MjEwNDY0LCJrdyI6Ii1yZWRkaXQuY29tIiwibWsiOiItcmVkZGl0LmNvbSIsIm53Ijo1MTQ2LCJwYyI6MCwicHIiOjIwMzYyLCJydCI6MSwicmYiOiJodHRwOi8vd3d3LnJlZGRpdC5jb20vIiwic3QiOjI0OTUwLCJ1ayI6InVlMS01ZWIwOGFlZWQ5YTc0MDFjOTE5NWNiOTMzZWI3Yzk2NiIsInRzIjoxNDAwODYyNTkzNjQ1fQ&s=lwlbFf2Uywt7zVBFRj_qXXu7msY HTTP/1.1
+Host: engine.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+Cookie: azk=ue1-5eb08aeed9a7401c9195cb933eb7c966
+
+GET /BurstingPipe/adServer.bs?cn=tf&c=19&mc=imp&pli=9994987&PluID=0&ord=1400862593644&rtu=-1 HTTP/1.1
+Host: bs.serving-sys.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads.html?sr=-reddit.com&bust2
+
+GET /Advertisers/63cfd0044ffd49c0a71a6626f7a1d8f0.jpg HTTP/1.1
+Host: static.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads-load.html?bust2
+
+GET /BurstingPipe/adServer.bs?cn=tf&c=19&mc=imp&pli=9962555&PluID=0&ord=1400862593645&rtu=-1 HTTP/1.1
+Host: bs.serving-sys.com
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads-load.html?bust2
+Cookie: S_9994987=6754579095859875029; A4=01fmFvgRnI09SF00000; u2=d1263d39-874b-4a89-86cd-a2ab0860ed4e3Zl040
+
+GET /i.gif?e=eyJhdiI6NjIzNTcsImF0Ijo4LCJjbSI6MTE2MzUxLCJjaCI6Nzk4NCwiY3IiOjMzNzAxOCwiZGkiOiI3OTdlZjU3OWQ5NjE0ODdiODYyMGMyMGJkOTE4YzNiMSIsImRtIjoxLCJmYyI6NDE2MTMxLCJmbCI6MjEwNDY0LCJrdyI6Ii1yZWRkaXQuY29tIiwibWsiOiItcmVkZGl0LmNvbSIsIm53Ijo1MTQ2LCJwYyI6MCwicHIiOjIwMzYyLCJydCI6MSwicmYiOiJodHRwOi8vd3d3LnJlZGRpdC5jb20vIiwic3QiOjI0OTUwLCJ1ayI6InVlMS01ZWIwOGFlZWQ5YTc0MDFjOTE5NWNiOTMzZWI3Yzk2NiIsInRzIjoxNDAwODYyNTkzNjQ2fQ&s=OjzxzXAgQksbdQOHNm-bjZcnZPA HTTP/1.1
+Host: engine.adzerk.net
+User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:15.0) Gecko/20100101 Firefox/15.0.1
+Accept: image/png,image/*;q=0.8,*/*;q=0.5
+Accept-Language: en-us,en;q=0.5
+Accept-Encoding: gzip, deflate
+Connection: keep-alive
+Referer: http://static.adzerk.net/reddit/ads-load.html?bust2
+Cookie: azk=ue1-5eb08aeed9a7401c9195cb933eb7c966
+
+GET /subscribe?host_int=1042356184&ns_map=571794054_374233948806,464381511_13349283399&user_id=245722467&nid=1399334269710011966&ts=1400862514 HTTP/1.1
+Host: notify8.dropbox.com
+Accept-Encoding: identity
+Connection: keep-alive
+X-Dropbox-Locale: en_US
+User-Agent: DropboxDesktopClient/2.7.54 (Macintosh; 10.8; ('i32',); en_US)
+
diff --git a/benches/http.rs b/benches/http.rs
new file mode 100644
index 00000000..291633d5
--- /dev/null
+++ b/benches/http.rs
@@ -0,0 +1,139 @@
+#![feature(test)]
+extern crate test;
+extern crate combine;
+
+use combine::*;
+use combine::primitives::Error;
+use combine::range::{take_while1, range};
+
+#[derive(Debug)]
+struct Request<'a> {
+    method: &'a [u8],
+    uri: &'a [u8],
+    version: &'a [u8],
+}
+
+#[derive(Debug)]
+struct Header<'a> {
+    name: &'a [u8],
+    value: Vec<&'a [u8]>,
+}
+
+fn is_token(c: u8) -> bool {
+    match c {
+        128...255 => false,
+        0...31 => false,
+        b'(' => false,
+        b')' => false,
+        b'<' => false,
+        b'>' => false,
+        b'@' => false,
+        b',' => false,
+        b';' => false,
+        b':' => false,
+        b'\\' => false,
+        b'"' => false,
+        b'/' => false,
+        b'[' => false,
+        b']' => false,
+        b'?' => false,
+        b'=' => false,
+        b'{' => false,
+        b'}' => false,
+        b' ' => false,
+        _ => true,
+    }
+}
+
+fn is_horizontal_space(c: u8) -> bool {
+    c == b' ' || c == b'\t'
+}
+fn is_space(c: u8) -> bool {
+    c == b' '
+}
+fn is_not_space(c: u8) -> bool {
+    c != b' '
+}
+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]>> {
+    // 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'));
+
+    let http_version = range(&b"HTTP/"[..]).with(take_while1(is_http_version));
+
+    let request_line = (take_while1(is_token),
+                        take_while1(is_space),
+                        take_while1(is_not_space),
+                        take_while1(is_space),
+                        http_version)
+        .map(|(method, _, uri, _, version)| {
+            Request {
+                method: method,
+                uri: uri,
+                version: version,
+            }
+        });
+
+
+    let message_header_line = (take_while1(is_horizontal_space),
+                               take_while1(|c| c != b'\r' && c != b'\n'),
+                               end_of_line())
+        .map(|(_, line, _)| line);
+
+    let message_header = (take_while1(is_token), token(b':'), many1(message_header_line))
+        .map(|(name, _, value)| {
+            Header {
+                name: name,
+                value: value,
+            }
+        });
+
+    let mut request = (request_line, end_of_line(), many(message_header), end_of_line())
+        .map(|(request, _, headers, _)| (request, headers));
+
+    request.parse(input)
+}
+
+static REQUESTS: &'static [u8] = include_bytes!("http-requests.txt");
+
+#[bench]
+fn http_requests_small(b: &mut ::test::Bencher) {
+    http_requests_bench(b, REQUESTS)
+}
+
+#[bench]
+fn http_requests_large(b: &mut ::test::Bencher) {
+    use std::iter;
+
+    let mut buffer = Vec::with_capacity(REQUESTS.len() * 5);
+    for buf in iter::repeat(REQUESTS).take(5) {
+        buffer.extend_from_slice(buf);
+    }
+    http_requests_bench(b, &buffer)
+}
+
+fn http_requests_bench(b: &mut ::test::Bencher, buffer: &[u8]) {
+    b.iter(|| {
+        let mut i = 0;
+        let mut buf = test::black_box(buffer);
+
+        while !buf.is_empty() {
+            // Needed for inferrence for many(message_header)
+            match parse_http_request(buf) {
+                Ok(((_, _), b)) => {
+                    i += 1;
+
+                    buf = b
+                }
+                Err(ref err) if err.errors[0] == Error::end_of_input() => {
+                    test::black_box(i);
+                    return;
+                }
+                Err(err) => panic!("{:?}", err),
+            }
+        }
+    });
+}
diff --git a/benches/json.rs b/benches/json.rs
index 19e128f5..47098222 100644
--- a/benches/json.rs
+++ b/benches/json.rs
@@ -9,8 +9,9 @@ use std::path::Path;
 
 use pc::primitives::{Consumed, Parser, ParseError, ParseResult, State, Stream, BufferedStream};
 use pc::combinator::{any, between, choice, many, many1, optional, parser, satisfy, sep_by,
-                     Expected, FnParser, Skip, ParserExt};
+                     Expected, FnParser, Skip};
 use pc::char::{char, digit, spaces, Spaces, string};
+use pc::from_iter;
 
 #[derive(PartialEq, Debug)]
 enum Value {
@@ -30,21 +31,22 @@ fn lex<'a, P>(p: P) -> Skip<P, Spaces<P::Input>>
 }
 struct Json<I>(::std::marker::PhantomData<fn(I) -> I>);
 
-type JsonParser<O, I> = Expected<FnParser<I, fn(State<I>) -> ParseResult<O, I>>>;
+type JsonParser<O, I> = Expected<FnParser<I, fn(I) -> ParseResult<O, I>>>;
 
-fn fn_parser<O, I>(f: fn(State<I>) -> ParseResult<O, I>, err: &'static str) -> JsonParser<O, I>
+fn fn_parser<O, I>(f: fn(I) -> ParseResult<O, I>, err: &'static str) -> JsonParser<O, I>
     where I: Stream<Item = char>
 {
     parser(f).expected(err)
 }
 
-impl<I> Json<I> where I: Stream<Item = char>
+impl<I> Json<I>
+    where I: Stream<Item = char>
 {
     fn integer() -> JsonParser<i64, I> {
         fn_parser(Json::<I>::integer_, "integer")
     }
-    fn integer_(input: State<I>) -> ParseResult<i64, I> {
-        let (s, input) = try!(lex(many1::<String, _>(digit())).parse_lazy(input));
+    fn integer_(input: I) -> ParseResult<i64, I> {
+        let (s, input) = try!(lex(many1::<String, _>(digit())).parse_lazy(input).into());
         let mut n = 0;
         for c in s.chars() {
             n = n * 10 + (c as i64 - '0' as i64);
@@ -55,10 +57,10 @@ impl<I> Json<I> where I: Stream<Item = char>
     fn number() -> JsonParser<f64, I> {
         fn_parser(Json::<I>::number_, "number")
     }
-    fn number_(input: State<I>) -> ParseResult<f64, I> {
+    fn number_(input: I) -> ParseResult<f64, I> {
         let i = char('0')
-                    .map(|_| 0.0)
-                    .or(Json::<I>::integer().map(|x| x as f64));
+            .map(|_| 0.0)
+            .or(Json::<I>::integer().map(|x| x as f64));
         let fractional = many(digit()).map(|digits: String| {
             let mut magnitude = 1.0;
             digits.chars().fold(0.0, |acc, d| {
@@ -71,64 +73,49 @@ impl<I> Json<I> where I: Stream<Item = char>
         });
 
         let exp = satisfy(|c| c == 'e' || c == 'E')
-                      .with(optional(char('-')).and(Json::<I>::integer()));
+            .with(optional(char('-')).and(Json::<I>::integer()));
         lex(optional(char('-'))
                 .and(i)
-                .map(|(sign, n)| {
-                    if sign.is_some() {
-                        -n
-                    } else {
-                        n
-                    }
-                })
+                .map(|(sign, n)| { if sign.is_some() { -n } else { n } })
                 .and(optional(char('.')).with(fractional))
-                .map(|(x, y)| {
-                    if x > 0.0 {
-                        x + y
-                    } else {
-                        x - y
-                    }
-                })
+                .map(|(x, y)| { if x > 0.0 { x + y } else { x - y } })
                 .and(optional(exp))
                 .map(|(n, exp_option)| {
                     match exp_option {
                         Some((sign, e)) => {
-                            let e = if sign.is_some() {
-                                -e
-                            } else {
-                                e
-                            };
+                            let e = if sign.is_some() { -e } else { e };
                             n * 10.0f64.powi(e as i32)
                         }
                         None => n,
                     }
                 }))
             .parse_lazy(input)
+            .into()
     }
 
     fn char() -> JsonParser<char, I> {
         fn_parser(Json::<I>::char_, "char")
     }
-    fn char_(input: State<I>) -> ParseResult<char, I> {
-        let (c, input) = try!(any().parse_lazy(input));
+    fn char_(input: I) -> ParseResult<char, I> {
+        let (c, input) = try!(any().parse_lazy(input).into());
         let mut back_slash_char = satisfy(|c| "\"\\/bfnrt".chars().find(|x| *x == c).is_some())
-                                      .map(|c| {
-                                          match c {
-                                              '"' => '"',
-                                              '\\' => '\\',
-                                              '/' => '/',
-                                              'b' => '\u{0008}',
-                                              'f' => '\u{000c}',
-                                              'n' => '\n',
-                                              'r' => '\r',
-                                              't' => '\t',
-                                              c => c,//Should never happen
-                                          }
-                                      });
+            .map(|c| {
+                match c {
+                    '"' => '"',
+                    '\\' => '\\',
+                    '/' => '/',
+                    'b' => '\u{0008}',
+                    'f' => '\u{000c}',
+                    'n' => '\n',
+                    'r' => '\r',
+                    't' => '\t',
+                    c => c,//Should never happen
+                }
+            });
         match c {
-            '\\' => input.combine(|input| back_slash_char.parse_state(input)),
+            '\\' => input.combine(|input| back_slash_char.parse_stream(input)),
             '"' => {
-                Err(Consumed::Empty(ParseError::from_errors(input.into_inner().position,
+                Err(Consumed::Empty(ParseError::from_errors(input.into_inner().position(),
                                                             Vec::new())))
             }
             _ => Ok((c, input)),
@@ -137,43 +124,51 @@ impl<I> Json<I> where I: Stream<Item = char>
     fn string() -> JsonParser<String, I> {
         fn_parser(Json::<I>::string_, "string")
     }
-    fn string_(input: State<I>) -> ParseResult<String, I> {
-        between(char('"'), lex(char('"')), many(Json::<I>::char())).parse_lazy(input)
+    fn string_(input: I) -> ParseResult<String, I> {
+        between(char('"'), lex(char('"')), many(Json::<I>::char())).parse_lazy(input).into()
     }
 
     fn object() -> JsonParser<Value, I> {
         fn_parser(Json::<I>::object_, "object")
     }
-    fn object_(input: State<I>) -> ParseResult<Value, I> {
+    fn object_(input: I) -> ParseResult<Value, I> {
         let field = (Json::<I>::string(), lex(char(':')), Json::<I>::value()).map(|t| (t.0, t.2));
         let fields = sep_by(field, lex(char(',')));
         between(lex(char('{')), lex(char('}')), fields)
             .map(Value::Object)
             .parse_lazy(input)
+            .into()
     }
 
-    fn value() -> FnParser<I, fn(State<I>) -> ParseResult<Value, I>> {
+    fn value() -> FnParser<I, fn(I) -> ParseResult<Value, I>> {
         parser({
             let f: fn(_) -> _ = Json::<I>::value_;
             f
         })
     }
     #[allow(unconditional_recursion)]
-    fn value_(input: State<I>) -> ParseResult<Value, I> {
+    fn value_(input: I) -> ParseResult<Value, I> {
         let mut 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))])
+            .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)
+            .into()
     }
 }
 
@@ -202,9 +197,9 @@ fn json_test() {
                                ("true", Bool(true)),
                                ("false", Bool(false)),
                                ("null", Null)]
-                              .into_iter()
-                              .map(|(k, v)| (k.to_string(), v))
-                              .collect());
+        .into_iter()
+        .map(|(k, v)| (k.to_string(), v))
+        .collect());
     match result {
         Ok(result) => assert_eq!(result, (expected, "")),
         Err(e) => {
@@ -221,7 +216,7 @@ fn bench_json(bencher: &mut ::test::Bencher) {
         .and_then(|mut file| file.read_to_string(&mut data))
         .unwrap();
     let mut parser = Json::value();
-    match parser.parse(&data[..]) {
+    match parser.parse(State::new(&data[..])) {
         Ok((Value::Array(_), _)) => (),
         Ok(_) => assert!(false),
         Err(err) => {
@@ -230,7 +225,7 @@ fn bench_json(bencher: &mut ::test::Bencher) {
         }
     }
     bencher.iter(|| {
-        let result = parser.parse(&data[..]);
+        let result = parser.parse(State::new(&data[..]));
         ::test::black_box(result)
     });
 }
@@ -242,9 +237,9 @@ fn bench_buffered_json(bencher: &mut ::test::Bencher) {
         .and_then(|mut file| file.read_to_string(&mut data))
         .unwrap();
     bencher.iter(|| {
-        let buffer = BufferedStream::new(data.chars(), 1);
+        let buffer = BufferedStream::new(from_iter(data.chars()), 1);
         let mut parser = Json::value();
-        match parser.parse(buffer.as_stream()) {
+        match parser.parse(State::new(buffer.as_stream())) {
             Ok((Value::Array(v), _)) => {
                 ::test::black_box(v);
             }
diff --git a/benches/mp4.rs b/benches/mp4.rs
new file mode 100644
index 00000000..381d91aa
--- /dev/null
+++ b/benches/mp4.rs
@@ -0,0 +1,72 @@
+#![cfg(feature = "mp4")]
+#![feature(test)]
+extern crate test;
+
+extern crate combine;
+extern crate byteorder;
+
+use test::{Bencher, black_box};
+
+use std::str::from_utf8;
+
+use byteorder::{BigEndian, ByteOrder};
+
+use combine::*;
+use combine::range::{range, take};
+
+#[derive(Clone, PartialEq, Eq, Debug)]
+struct FileType<'a> {
+    major_brand: &'a str,
+    major_brand_version: &'a [u8],
+    compatible_brands: Vec<&'a str>,
+}
+
+#[derive(Clone, Debug)]
+enum MP4Box<'a> {
+    Ftyp(FileType<'a>),
+    Moov,
+    Mdat,
+    Free,
+    Skip,
+    Wide,
+    Unknown,
+}
+
+fn parse_mp4(data: &[u8]) -> Result<(Vec<MP4Box>, &[u8]), ParseError<&[u8]>> {
+    let brand_name = || take(4).and_then(from_utf8);
+    let filetype_box = (range(&b"ftyp"[..]), brand_name(), take(4), many(brand_name()))
+        .map(|(_, m, v, c)| {
+            MP4Box::Ftyp(FileType {
+                major_brand: m,
+                major_brand_version: v,
+                compatible_brands: c,
+            })
+        });
+
+    let mp4_box = take(4).map(BigEndian::read_u32).then(|offset| take(offset as usize - 4));
+    let mut box_parser = filetype_box.or(range(&b"moov"[..]).map(|_| MP4Box::Moov))
+        .or(range(&b"mdat"[..]).map(|_| MP4Box::Mdat))
+        .or(range(&b"free"[..]).map(|_| MP4Box::Free))
+        .or(range(&b"skip"[..]).map(|_| MP4Box::Skip))
+        .or(range(&b"wide"[..]).map(|_| MP4Box::Wide))
+        .or(value(MP4Box::Unknown));
+    let data_interpreter = mp4_box.flat_map(|box_data| box_parser.parse(box_data).map(|t| t.0));
+
+    many(data_interpreter).parse(data)
+}
+
+static MP4_SMALL: &'static [u8] = include_bytes!("small.mp4");
+
+fn run_test(b: &mut Bencher, data: &[u8]) {
+    b.iter(|| {
+        match parse_mp4(data) {
+            Ok(x) => black_box(x),
+            Err(err) => panic!("{:?}", err),
+        }
+    });
+}
+
+#[bench]
+fn mp4_small_test(b: &mut Bencher) {
+    run_test(b, MP4_SMALL)
+}
diff --git a/src/byte.rs b/src/byte.rs
new file mode 100644
index 00000000..0bc7fe75
--- /dev/null
+++ b/src/byte.rs
@@ -0,0 +1,220 @@
+extern crate ascii;
+
+use std::marker::PhantomData;
+
+use self::ascii::AsciiChar;
+
+use combinator::{Expected, satisfy, Satisfy, skip_many, SkipMany, token, Token, With};
+use primitives::{Consumed, ConsumedResult, Error, Info, Parser, ParseError, Stream};
+
+/// Parses a character and succeeds if the character is equal to `c`
+///
+/// ```
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::byte::byte;
+/// # fn main() {
+/// let result = byte(b'!')
+///     .parse(&b"!"[..])
+///     .map(|x| x.0);
+/// assert_eq!(result, Ok(b'!'));
+/// # }
+/// ```
+#[inline(always)]
+pub fn byte<I>(c: u8) -> Token<I>
+    where I: Stream<Item = u8>
+{
+    token(c)
+}
+
+impl_token_parser! { Digit(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+
+macro_rules! byte_parser {
+    ($name: ident, $ty : ident, $f : ident) => ({
+        let f = static_fn!((c, u8) -> bool {
+            AsciiChar::from(c).map(|c| c.$f()).unwrap_or(false)
+        });
+        $ty(satisfy(f).expected(stringify!($name)), PhantomData)
+    })
+}
+
+/// Parses a digit from a stream containing characters
+#[inline(always)]
+pub fn digit<I>() -> Digit<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(digit, Digit, is_digit)
+}
+
+impl_token_parser! { Space(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+
+/// Parses whitespace
+#[inline(always)]
+pub fn space<I>() -> Space<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(space, Space, is_whitespace)
+}
+
+impl_token_parser! { Spaces(), u8, Expected<SkipMany<Space<I>>> }
+/// Skips over zero or more spaces
+#[inline(always)]
+pub fn spaces<I>() -> Spaces<I>
+    where I: Stream<Item = u8>
+{
+    Spaces(skip_many(space()).expected("whitespaces"), PhantomData)
+}
+
+impl_token_parser! { Newline(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+
+/// Parses a newline character
+#[inline(always)]
+pub fn newline<I>() -> Newline<I>
+    where I: Stream<Item = u8>
+{
+    Newline(satisfy(static_fn!((ch, u8) -> bool { ch == b'\n' })).expected("lf newline"),
+            PhantomData)
+}
+
+impl_token_parser! { CrLf(), u8, Expected<With<Satisfy<I, fn (u8) -> bool>, Newline<I>>> }
+
+/// Parses carriage return and newline, returning the newline character.
+#[inline(always)]
+pub fn crlf<I>() -> CrLf<I>
+    where I: Stream<Item = u8>
+{
+    CrLf(satisfy(static_fn!((ch, u8) -> bool { ch == b'\r' }))
+             .with(newline())
+             .expected("crlf newline"),
+         PhantomData)
+}
+
+impl_token_parser! { Tab(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses a tab character
+#[inline(always)]
+pub fn tab<I>() -> Tab<I>
+    where I: Stream<Item = u8>
+{
+    Tab(satisfy(static_fn!((ch, u8) -> bool { ch == b'\t' })).expected("tab"),
+        PhantomData)
+}
+
+impl_token_parser! { Upper(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses an uppercase letter
+#[inline(always)]
+pub fn upper<I>() -> Upper<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(upper, Upper, is_uppercase)
+}
+
+impl_token_parser! { Lower(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses an lowercase letter
+#[inline(always)]
+pub fn lower<I>() -> Lower<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(lower, Lower, is_lowercase)
+}
+
+impl_token_parser! { AlphaNum(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses either an alphabet letter or digit
+#[inline(always)]
+pub fn alpha_num<I>() -> AlphaNum<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(alpha_num, AlphaNum, is_alphanumeric)
+}
+
+impl_token_parser! { Letter(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses an alphabet letter
+#[inline(always)]
+pub fn letter<I>() -> Letter<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(letter, Letter, is_alphabetic)
+}
+
+impl_token_parser! { HexDigit(), u8, Expected<Satisfy<I, fn (u8) -> bool>> }
+/// Parses a hexdecimal digit with uppercase and lowercase
+#[inline(always)]
+pub fn hex_digit<I>() -> HexDigit<I>
+    where I: Stream<Item = u8>
+{
+    byte_parser!(hex_digit, HexDigit, is_hex)
+}
+
+#[derive(Clone)]
+pub struct Bytes<I>(&'static [u8], PhantomData<I>);
+impl<'a, I> Parser for Bytes<I>
+    where I: Stream<Item = u8, Range = &'a [u8]>
+{
+    type Input = I;
+    type Output = &'static [u8];
+    #[inline]
+    fn parse_lazy(&mut self, mut input: I) -> ConsumedResult<&'static [u8], I> {
+        let start = input.position();
+        let mut consumed = false;
+        for &c in self.0 {
+            match ::primitives::uncons(input) {
+                Ok((other, rest)) => {
+                    if c != other {
+                        return Err(if consumed {
+                                let errors = vec![Error::Unexpected(Info::Token(other)),
+                                                  Error::Expected(Info::Range(self.0))];
+                                let error = ParseError::from_errors(start, errors);
+                                Consumed::Consumed(error)
+                            } else {
+                                Consumed::Empty(ParseError::empty(start))
+                            })
+                            .into();
+                    }
+                    consumed = true;
+                    input = rest.into_inner();
+                }
+                Err(error) => {
+                    return error.combine_consumed(|mut error| {
+                        error.position = start;
+                        Err(if consumed {
+                                Consumed::Consumed(error)
+                            } else {
+                                Consumed::Empty(error)
+                            })
+                            .into()
+                    })
+                }
+            }
+        }
+        Ok((self.0,
+            if consumed {
+                Consumed::Consumed(input)
+            } else {
+                Consumed::Empty(input)
+            }))
+            .into()
+    }
+    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+        errors.add_error(Error::Expected(Info::Range(self.0)));
+    }
+}
+
+/// Parses the bytes `s`. If you have a stream implementing `RangeStream` such as `&[u8]` you can
+/// also use the `range` parser which may be more efficient.
+///
+/// ```
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::byte::bytes;
+/// # fn main() {
+/// let result = bytes(b"rust")
+///     .parse(&b"rust"[..])
+///     .map(|x| x.0);
+/// assert_eq!(result, Ok(&b"rust"[..]));
+/// # }
+/// ```
+#[inline(always)]
+pub fn bytes<'a, I>(s: &'static [u8]) -> Bytes<I>
+    where I: Stream<Item = u8, Range = &'a [u8]>
+{
+    Bytes(s, PhantomData)
+}
diff --git a/src/char.rs b/src/char.rs
index b2678eee..037adf68 100644
--- a/src/char.rs
+++ b/src/char.rs
@@ -1,32 +1,13 @@
-use primitives::{Consumed, Parser, ParseError, ParseResult, Error, State, Stream};
-use combinator::{Expected, satisfy, Satisfy, skip_many, SkipMany, token, Token, ParserExt, With};
+use primitives::{Consumed, Parser, ParseError, ConsumedResult, Error, Stream};
+use combinator::{Expected, satisfy, Satisfy, skip_many, SkipMany, token, Token, With};
 use std::marker::PhantomData;
 
-macro_rules! impl_char_parser {
-    ($name: ident ($($ty_var: ident),*), $inner_type: ty) => {
-    #[derive(Clone)]
-    pub struct $name<I $(,$ty_var)*>($inner_type, PhantomData<fn (I) -> I>)
-        where I: Stream<Item=char> $(, $ty_var : Parser<Input=I>)*;
-    impl <I $(,$ty_var)*> Parser for $name<I $(,$ty_var)*>
-        where I: Stream<Item=char> $(, $ty_var : Parser<Input=I>)* {
-        type Input = I;
-        type Output = <$inner_type as Parser>::Output;
-        fn parse_lazy(&mut self,
-                      input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-            self.0.parse_lazy(input)
-        }
-        fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-            self.0.add_error(errors)
-        }
-    }
-}
-}
-
-///Parses a character and succeeds if the character is equal to `c`
+/// Parses a character and succeeds if the character is equal to `c`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::char;
 /// # fn main() {
 /// let result = char('!')
 ///     .parse("!")
@@ -34,14 +15,16 @@ macro_rules! impl_char_parser {
 /// assert_eq!(result, Ok('!'));
 /// # }
 /// ```
+#[inline(always)]
 pub fn char<I>(c: char) -> Token<I>
     where I: Stream<Item = char>
 {
     token(c)
 }
 
-impl_char_parser! { Digit(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses a digit from a stream containing characters
+impl_token_parser! { Digit(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses a digit from a stream containing characters
+#[inline(always)]
 pub fn digit<I>() -> Digit<I>
     where I: Stream<Item = char>
 {
@@ -49,33 +32,37 @@ pub fn digit<I>() -> Digit<I>
           PhantomData)
 }
 
-impl_char_parser! { Space(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses whitespace
+impl_token_parser! { Space(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses whitespace
+#[inline(always)]
 pub fn space<I>() -> Space<I>
     where I: Stream<Item = char>
 {
     let f: fn(char) -> bool = char::is_whitespace;
     Space(satisfy(f).expected("whitespace"), PhantomData)
 }
-impl_char_parser! { Spaces(), Expected<SkipMany<Space<I>>> }
-///Skips over zero or more spaces
+impl_token_parser! { Spaces(), char, Expected<SkipMany<Space<I>>> }
+/// Skips over zero or more spaces
+#[inline(always)]
 pub fn spaces<I>() -> Spaces<I>
     where I: Stream<Item = char>
 {
     Spaces(skip_many(space()).expected("whitespaces"), PhantomData)
 }
 
-impl_char_parser! { NewLine(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses a newline character
-pub fn newline<I>() -> NewLine<I>
+impl_token_parser! { Newline(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses a newline character
+#[inline(always)]
+pub fn newline<I>() -> Newline<I>
     where I: Stream<Item = char>
 {
-    NewLine(satisfy(static_fn!((ch, char) -> bool { ch == '\n' })).expected("lf newline"),
+    Newline(satisfy(static_fn!((ch, char) -> bool { ch == '\n' })).expected("lf newline"),
             PhantomData)
 }
 
-impl_char_parser! { CrLf(), Expected<With<Satisfy<I, fn (char) -> bool>, NewLine<I>>> }
-///Parses carriage return and newline, returning the newline character.
+impl_token_parser! { CrLf(), char, Expected<With<Satisfy<I, fn (char) -> bool>, Newline<I>>> }
+/// Parses carriage return and newline, returning the newline character.
+#[inline(always)]
 pub fn crlf<I>() -> CrLf<I>
     where I: Stream<Item = char>
 {
@@ -85,8 +72,9 @@ pub fn crlf<I>() -> CrLf<I>
          PhantomData)
 }
 
-impl_char_parser! { Tab(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses a tab character
+impl_token_parser! { Tab(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses a tab character
+#[inline(always)]
 pub fn tab<I>() -> Tab<I>
     where I: Stream<Item = char>
 {
@@ -94,8 +82,9 @@ pub fn tab<I>() -> Tab<I>
         PhantomData)
 }
 
-impl_char_parser! { Upper(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses an uppercase letter
+impl_token_parser! { Upper(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses an uppercase letter
+#[inline(always)]
 pub fn upper<I>() -> Upper<I>
     where I: Stream<Item = char>
 {
@@ -103,8 +92,9 @@ pub fn upper<I>() -> Upper<I>
           PhantomData)
 }
 
-impl_char_parser! { Lower(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses an lowercase letter
+impl_token_parser! { Lower(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses an lowercase letter
+#[inline(always)]
 pub fn lower<I>() -> Lower<I>
     where I: Stream<Item = char>
 {
@@ -113,8 +103,9 @@ pub fn lower<I>() -> Lower<I>
           PhantomData)
 }
 
-impl_char_parser! { AlphaNum(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses either an alphabet letter or digit
+impl_token_parser! { AlphaNum(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses either an alphabet letter or digit
+#[inline(always)]
 pub fn alpha_num<I>() -> AlphaNum<I>
     where I: Stream<Item = char>
 {
@@ -123,8 +114,9 @@ pub fn alpha_num<I>() -> AlphaNum<I>
              PhantomData)
 }
 
-impl_char_parser! { Letter(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses an alphabet letter
+impl_token_parser! { Letter(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses an alphabet letter
+#[inline(always)]
 pub fn letter<I>() -> Letter<I>
     where I: Stream<Item = char>
 {
@@ -132,8 +124,9 @@ pub fn letter<I>() -> Letter<I>
            PhantomData)
 }
 
-impl_char_parser! { OctDigit(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses an octal digit
+impl_token_parser! { OctDigit(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses an octal digit
+#[inline(always)]
 pub fn oct_digit<I>() -> OctDigit<I>
     where I: Stream<Item = char>
 {
@@ -141,8 +134,9 @@ pub fn oct_digit<I>() -> OctDigit<I>
              PhantomData)
 }
 
-impl_char_parser! { HexDigit(), Expected<Satisfy<I, fn (char) -> bool>> }
-///Parses a hexdecimal digit with uppercase and lowercase
+impl_token_parser! { HexDigit(), char, Expected<Satisfy<I, fn (char) -> bool>> }
+/// Parses a hexdecimal digit with uppercase and lowercase
+#[inline(always)]
 pub fn hex_digit<I>() -> HexDigit<I>
     where I: Stream<Item = char>
 {
@@ -153,60 +147,65 @@ pub fn hex_digit<I>() -> HexDigit<I>
 
 
 #[derive(Clone)]
-pub struct String<I>(&'static str, PhantomData<I>);
-impl<I> Parser for String<I>
+pub struct Str<I>(&'static str, PhantomData<I>);
+impl<I> Parser for Str<I>
     where I: Stream<Item = char>
 {
     type Input = I;
     type Output = &'static str;
-    fn parse_lazy(&mut self, mut input: State<I>) -> ParseResult<&'static str, I> {
-        let start = input.position;
+    #[inline]
+    fn parse_lazy(&mut self, mut input: I) -> ConsumedResult<&'static str, I> {
+        let start = input.position();
         let mut consumed = false;
         for c in self.0.chars() {
-            match input.uncons() {
+            match ::primitives::uncons(input) {
                 Ok((other, rest)) => {
                     if c != other {
                         return Err(if consumed {
-                            let errors = vec![Error::Unexpected(other.into()),
-                                              Error::Expected(self.0.into())];
-                            let error = ParseError::from_errors(start, errors);
-                            Consumed::Consumed(error)
-                        } else {
-                            Consumed::Empty(ParseError::empty(start))
-                        });
+                                let errors = vec![Error::Unexpected(other.into()),
+                                                  Error::Expected(self.0.into())];
+                                let error = ParseError::from_errors(start, errors);
+                                Consumed::Consumed(error)
+                            } else {
+                                Consumed::Empty(ParseError::empty(start))
+                            })
+                            .into();
                     }
                     consumed = true;
                     input = rest.into_inner();
                 }
                 Err(error) => {
-                    return error.combine(|mut error| {
+                    return error.combine_consumed(|mut error| {
                         error.position = start;
                         Err(if consumed {
-                            Consumed::Consumed(error)
-                        } else {
-                            Consumed::Empty(error)
-                        })
+                                Consumed::Consumed(error)
+                            } else {
+                                Consumed::Empty(error)
+                            })
+                            .into()
                     })
                 }
             }
         }
         Ok((self.0,
             if consumed {
-            Consumed::Consumed(input)
-        } else {
-            Consumed::Empty(input)
-        }))
+                Consumed::Consumed(input)
+            } else {
+                Consumed::Empty(input)
+            }))
+            .into()
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
         errors.add_error(Error::Expected(self.0.into()));
     }
 }
 
-///Parses the string `s`
+/// Parses the string `s`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::string;
 /// # fn main() {
 /// let result = string("rust")
 ///     .parse("rust")
@@ -214,17 +213,18 @@ impl<I> Parser for String<I>
 /// assert_eq!(result, Ok("rust"));
 /// # }
 /// ```
-pub fn string<I>(s: &'static str) -> String<I>
+#[inline(always)]
+pub fn string<I>(s: &'static str) -> Str<I>
     where I: Stream<Item = char>
 {
-    String(s, PhantomData)
+    Str(s, PhantomData)
 }
 
 
 #[cfg(test)]
 mod tests {
     use super::*;
-    use primitives::{Error, ParseError, Parser, SourcePosition};
+    use primitives::{Error, ParseError, Parser, SourcePosition, State};
 
     #[test]
     fn space_error() {
@@ -237,7 +237,7 @@ mod tests {
 
     #[test]
     fn string_consumed() {
-        let result = string("a").parse("b");
+        let result = string("a").parse(State::new("b"));
         assert!(result.is_err());
         assert_eq!(result.unwrap_err().position,
                    SourcePosition {
@@ -248,7 +248,7 @@ mod tests {
 
     #[test]
     fn string_error() {
-        let result = string("abc").parse("bc");
+        let result = string("abc").parse(State::new("bc"));
         assert_eq!(result,
                    Err(ParseError {
                        position: SourcePosition {
diff --git a/src/combinator.rs b/src/combinator.rs
index c9952b70..5c1f7cce 100644
--- a/src/combinator.rs
+++ b/src/combinator.rs
@@ -1,7 +1,8 @@
 use std::iter::FromIterator;
 use std::marker::PhantomData;
-use primitives::{Info, Parser, ParseResult, ParseError, Positioner, Stream, State, Error, Consumed};
-use primitives::RangeStream;
+use primitives::{Info, Parser, ParseResult, ConsumedResult, ParseError, Stream, StreamOnce, Error,
+                 Consumed};
+use primitives::FastResult::*;
 
 macro_rules! impl_parser {
     ($name: ident ($first: ident, $($ty_var: ident),*), $inner_type: ty) => {
@@ -12,12 +13,16 @@ macro_rules! impl_parser {
         where $first: Parser $(, $ty_var : Parser<Input=<$first as Parser>::Input>)* {
         type Input = <$first as Parser>::Input;
         type Output = <$inner_type as Parser>::Output;
-        fn parse_state(&mut self,
-                       input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-            self.0.parse_state(input)
+        fn parse_stream(&mut self,
+                       input: Self::Input) -> ParseResult<Self::Output, Self::Input> {
+            self.0.parse_stream(input)
+        }
+        fn parse_stream_consumed(&mut self,
+                      input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+            self.0.parse_stream_consumed(input)
         }
         fn parse_lazy(&mut self,
-                      input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
+                      input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
             self.0.parse_lazy(input)
         }
         fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
@@ -35,16 +40,21 @@ impl<I> Parser for Any<I>
 {
     type Input = I;
     type Output = I::Item;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<I::Item, I> {
-        input.uncons()
+    #[inline]
+    fn parse_lazy(&mut self, mut input: I) -> ConsumedResult<I::Item, I> {
+        let position = input.position();
+        match input.uncons() {
+            Ok(x) => ConsumedOk((x, input)),
+            Err(err) => ConsumedErr(ParseError::new(position, err)),
+        }
     }
 }
 
-///Parses any token
+/// Parses any token
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
 /// # fn main() {
 /// let mut char_parser = any();
 /// assert_eq!(char_parser.parse("!").map(|x| x.0), Ok('!'));
@@ -54,6 +64,7 @@ impl<I> Parser for Any<I>
 /// assert!(byte_parser.parse(&b""[..]).is_err());
 /// # }
 /// ```
+#[inline(always)]
 pub fn any<I>() -> Any<I>
     where I: Stream
 {
@@ -68,20 +79,19 @@ pub struct Satisfy<I, P> {
     _marker: PhantomData<I>,
 }
 
-fn satisfy_impl<I, P, F>(input: State<I>, predicate: &mut P, f: F) -> ParseResult<I::Item, I>
+fn satisfy_impl<I, P, R>(input: I, mut predicate: P) -> ConsumedResult<R, I>
     where I: Stream,
-          P: FnMut(I::Item) -> bool,
-          F: FnOnce(<I::Item as Positioner>::Position, I::Item) -> ParseError<I>
-{
-    match input.input.clone().uncons() {
-        Ok((c, s)) => {
-            if (predicate)(c.clone()) {
-                input.update(c, s)
-            } else {
-                Err(Consumed::Empty(f(input.position, c)))
+          P: FnMut(I::Item) -> Option<R>
+{
+    let mut next = input.clone();
+    match next.uncons() {
+        Ok(c) => {
+            match predicate(c.clone()) {
+                Some(c) => ConsumedOk((c, next)),
+                None => EmptyErr(ParseError::empty(input.position())),
             }
         }
-        Err(err) => Err(Consumed::Empty(ParseError::new(input.position, err))),
+        Err(err) => EmptyErr(ParseError::new(input.position(), err)),
     }
 }
 
@@ -91,22 +101,28 @@ impl<I, P> Parser for Satisfy<I, P>
 {
     type Input = I;
     type Output = I::Item;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<I::Item, I> {
-        satisfy_impl(input, &mut self.predicate, |pos, _| ParseError::empty(pos))
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<I::Item, I> {
+        satisfy_impl(input, |c| if (self.predicate)(c.clone()) {
+            Some(c)
+        } else {
+            None
+        })
     }
 }
 
-///Parses a token and succeeds depending on the result of `predicate`
+/// Parses a token and succeeds depending on the result of `predicate`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
 /// # fn main() {
 /// let mut parser = satisfy(|c| c == '!' || c == '?');
 /// assert_eq!(parser.parse("!").map(|x| x.0), Ok('!'));
 /// assert_eq!(parser.parse("?").map(|x| x.0), Ok('?'));
 /// # }
 /// ```
+#[inline(always)]
 pub fn satisfy<I, P>(predicate: P) -> Satisfy<I, P>
     where I: Stream,
           P: FnMut(I::Item) -> bool
@@ -117,6 +133,59 @@ pub fn satisfy<I, P>(predicate: P) -> Satisfy<I, P>
     }
 }
 
+#[derive(Clone)]
+pub struct SatisfyMap<I, P> {
+    predicate: P,
+    _marker: PhantomData<I>,
+}
+
+impl<I, P, R> Parser for SatisfyMap<I, P>
+    where I: Stream,
+          P: FnMut(I::Item) -> Option<R>
+{
+    type Input = I;
+    type Output = R;
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<R, I> {
+        satisfy_impl(input, &mut self.predicate)
+    }
+}
+
+/// Parses a token and passes it to `predicate`. If `predicate` returns `Some` the parser succeeds
+/// and returns the value inside the `Option`. If `predicate` returns `None` the parser fails
+/// without consuming any imput.
+///
+/// ```
+/// # extern crate combine;
+/// # use combine::*;
+/// # fn main() {
+/// #[derive(Debug, PartialEq)]
+/// enum YesNo {
+///     Yes,
+///     No,
+/// }
+/// let mut parser = satisfy_map(|c| {
+///     match c {
+///         'Y' => Some(YesNo::Yes),
+///         'N' => Some(YesNo::No),
+///         _ => None,
+///     }
+/// });
+/// assert_eq!(parser.parse("Y").map(|x| x.0), Ok(YesNo::Yes));
+/// assert!(parser.parse("A").map(|x| x.0).is_err());
+/// # }
+/// ```
+#[inline(always)]
+pub fn satisfy_map<I, P, R>(predicate: P) -> SatisfyMap<I, P>
+    where I: Stream,
+          P: FnMut(I::Item) -> Option<R>
+{
+    SatisfyMap {
+        predicate: predicate,
+        _marker: PhantomData,
+    }
+}
+
 #[derive(Clone)]
 pub struct Token<I>
     where I: Stream,
@@ -132,19 +201,20 @@ impl<I> Parser for Token<I>
 {
     type Input = I;
     type Output = I::Item;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<I::Item, I> {
-        satisfy_impl(input, &mut |c| c == self.c, |pos, _| ParseError::empty(pos))
+    #[inline]
+    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.errors.push(Error::Expected(Info::Token(self.c.clone())));
     }
 }
 
-///Parses a character and succeeds if the character is equal to `c`
+/// Parses a character and succeeds if the character is equal to `c`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
 /// # fn main() {
 /// let result = token('!')
 ///     .parse("!")
@@ -152,6 +222,7 @@ impl<I> Parser for Token<I>
 /// assert_eq!(result, Ok('!'));
 /// # }
 /// ```
+#[inline(always)]
 pub fn token<I>(c: I::Item) -> Token<I>
     where I: Stream,
           I::Item: PartialEq
@@ -172,27 +243,29 @@ impl<I, O, S, P> Parser for Choice<S, P>
 {
     type Input = I;
     type Output = O;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
+    #[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@Err(Consumed::Consumed(_)) => return consumed_err,
-                Err(Consumed::Empty(err)) => {
+                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@Ok(_) => return ok,
+                ok @ ConsumedOk(_) => return ok,
+                ok @ EmptyOk(_) => return ok,
             }
         }
-        Err(Consumed::Empty(match empty_err {
+        EmptyErr(match empty_err {
             None => {
-                ParseError::new(input.position.clone(),
+                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() {
@@ -205,9 +278,10 @@ impl<I, O, S, P> Parser for Choice<S, P>
 /// Fails if all parsers fails or if an applied parser consumes input before failing.
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
-/// # use pc::primitives::Error;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::string;
+/// # use combine::primitives::Error;
 /// # fn main() {
 /// let mut parser = choice([string("Apple"), string("Banana"), string("Orange")]);
 /// assert_eq!(parser.parse("Banana"), Ok(("Banana", "")));
@@ -224,6 +298,7 @@ impl<I, O, S, P> Parser for Choice<S, P>
 /// assert_eq!(parser3.parse("three"), Ok(("three", "")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn choice<S, P>(ps: S) -> Choice<S, P>
     where S: AsMut<[P]>,
           P: Parser
@@ -238,20 +313,21 @@ impl<I> Parser for Unexpected<I>
 {
     type Input = I;
     type Output = ();
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<(), I> {
-        Err(Consumed::Empty(ParseError::empty(input.position)))
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<(), I> {
+        EmptyErr(ParseError::empty(input.position()))
     }
     fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
         error.errors.push(Error::Unexpected(self.0.clone()));
     }
 }
-///Always fails with `message` as an unexpected error.
-///Never consumes any input.
+/// Always fails with `message` as an unexpected error.
+/// Never consumes any input.
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
-/// # use pc::primitives::Error;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::primitives::Error;
 /// # fn main() {
 /// let result = unexpected("token")
 ///     .parse("a");
@@ -259,6 +335,7 @@ impl<I> Parser for Unexpected<I>
 /// assert!(result.err().unwrap().errors.iter().any(|m| *m == Error::Unexpected("token".into())));
 /// # }
 /// ```
+#[inline(always)]
 pub fn unexpected<I, S>(message: S) -> Unexpected<I>
     where I: Stream,
           S: Into<Info<I::Item, I::Range>>
@@ -274,15 +351,16 @@ impl<I, T> Parser for Value<I, T>
 {
     type Input = I;
     type Output = T;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<T, I> {
-        Ok((self.0.clone(), Consumed::Empty(input)))
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<T, I> {
+        EmptyOk((self.0.clone(), input))
     }
 }
-///Always returns the value `v` without consuming any input.
+/// Always returns the value `v` without consuming any input.
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
 /// # fn main() {
 /// let result = value(42)
 ///     .parse("hello world")
@@ -290,6 +368,7 @@ impl<I, T> Parser for Value<I, T>
 /// assert_eq!(result, Ok(42));
 /// # }
 /// ```
+#[inline(always)]
 pub fn value<I, T>(v: T) -> Value<I, T>
     where I: Stream,
           T: Clone
@@ -301,12 +380,13 @@ impl_parser! { NotFollowedBy(P,),
                Or<Then<Try<P>, fn(P::Output) -> Unexpected<P::Input>>, Value<P::Input, ()>>
 }
 
-///Succeeds only if `parser` fails.
-///Never consumes any input.
+/// Succeeds only if `parser` fails.
+/// Never consumes any input.
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::{alpha_num, string};
 /// # fn main() {
 /// let result = string("let")
 ///     .skip(not_followed_by(alpha_num()))
@@ -315,6 +395,7 @@ impl_parser! { NotFollowedBy(P,),
 /// assert!(result.is_err());
 /// # }
 /// ```
+#[inline(always)]
 pub fn not_followed_by<P>(parser: P) -> NotFollowedBy<P>
     where P: Parser,
           P::Output: ::std::fmt::Display
@@ -324,8 +405,8 @@ pub fn not_followed_by<P>(parser: P) -> NotFollowedBy<P>
     }
     let f: fn(P::Output) -> Unexpected<P::Input> = f;
     NotFollowedBy(try(parser)
-                      .then(f)
-                      .or(value(())))
+        .then(f)
+        .or(value(())))
 }
 
 #[derive(Clone)]
@@ -336,10 +417,11 @@ impl<I> Parser for Eof<I>
     type Input = I;
     type Output = ();
 
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<(), I> {
-        match input.input.clone().uncons() {
-            Err(ref err) if *err == Error::end_of_input() => Ok(((), Consumed::Empty(input))),
-            _ => Err(Consumed::Empty(ParseError::empty(input.position))),
+    #[inline]
+    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())),
         }
     }
 
@@ -356,8 +438,8 @@ impl<I> Parser for Eof<I>
 /// # use combine::primitives::{Error, Positioner};
 /// # fn main() {
 /// let mut parser = eof();
-/// assert_eq!(parser.parse(""), Ok(((), "")));
-/// assert_eq!(parser.parse("x"), Err(ParseError {
+/// assert_eq!(parser.parse(State::new("")), Ok(((), State::new(""))));
+/// assert_eq!(parser.parse(State::new("x")), Err(ParseError {
 ///     position: <char as Positioner>::start(),
 ///     errors: vec![
 ///         Error::Unexpected('x'.into()),
@@ -366,6 +448,7 @@ impl<I> Parser for Eof<I>
 /// }));
 /// # }
 /// ```
+#[inline(always)]
 pub fn eof<I>() -> Eof<I>
     where I: Stream
 {
@@ -374,24 +457,42 @@ pub fn eof<I>() -> Eof<I>
 
 pub struct Iter<P: Parser> {
     parser: P,
-    input: Consumed<State<P::Input>>,
-    error: Option<Consumed<ParseError<P::Input>>>,
+    input: P::Input,
+    consumed: bool,
+    state: State<P::Input>,
+}
+
+enum State<I: StreamOnce> {
+    Ok,
+    EmptyErr,
+    ConsumedErr(ParseError<I>),
 }
 
 impl<P: Parser> Iter<P> {
-    fn new(parser: P, input: State<P::Input>) -> Iter<P> {
+    pub fn new(parser: P, input: P::Input) -> Iter<P> {
         Iter {
             parser: parser,
-            input: Consumed::Empty(input),
-            error: None,
+            input: input,
+            consumed: false,
+            state: State::Ok,
         }
     }
-    ///Converts the iterator to a `ParseResult`, returning `Ok` if the parsing so far has be done
-    ///without any errors which consumed data.
+    /// Converts the iterator to a `ParseResult`, returning `Ok` if the parsing so far has be done
+    /// without any errors which consumed data.
     pub fn into_result<O>(self, value: O) -> ParseResult<O, P::Input> {
-        match self.error {
-            Some(err@Consumed::Consumed(_)) => Err(err),
-            _ => Ok((value, self.input)),
+        self.into_result_fast(value).into()
+    }
+
+    fn into_result_fast<O>(self, value: O) -> ConsumedResult<O, P::Input> {
+        match self.state {
+            State::Ok | State::EmptyErr => {
+                if self.consumed {
+                    ConsumedOk((value, self.input))
+                } else {
+                    EmptyOk((value, self.input))
+                }
+            }
+            State::ConsumedErr(e) => ConsumedErr(e),
         }
     }
 }
@@ -399,18 +500,30 @@ impl<P: Parser> Iter<P> {
 impl<P: Parser> Iterator for Iter<P> {
     type Item = P::Output;
     fn next(&mut self) -> Option<P::Output> {
-        if self.error.is_some() {
-            return None;
-        }
-        match self.parser.parse_lazy(self.input.clone().into_inner()) {
-            Ok((value, rest)) => {
-                self.input = self.input.merge(rest);
-                Some(value)
-            }
-            Err(err) => {
-                self.error = Some(err);
-                None
+        match self.state {
+            State::Ok => {
+                match self.parser.parse_lazy(self.input.clone()) {
+                    EmptyOk((v, input)) => {
+                        self.input = input;
+                        Some(v)
+                    }
+                    ConsumedOk((v, input)) => {
+                        self.input = input;
+                        self.consumed = true;
+                        Some(v)
+                    }
+                    EmptyErr(_) => {
+                        self.state = State::EmptyErr;
+                        None
+                    }
+                    ConsumedErr(e) => {
+                        self.state = State::ConsumedErr(e);
+                        None
+                    }
+                }
             }
+            State::ConsumedErr(_) |
+            State::EmptyErr => None,
         }
     }
 }
@@ -423,21 +536,22 @@ impl<F, P> Parser for Many<F, P>
 {
     type Input = P::Input;
     type Output = F;
-    fn parse_state(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
+    fn parse_stream_consumed(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
         let mut iter = (&mut self.0).iter(input);
         let result = iter.by_ref().collect();
-        iter.into_result(result)
+        iter.into_result_fast(result)
     }
 }
 
-///Parses `p` zero or more times returning a collection with the values from `p`.
-///If the returned collection cannot be inferred type annotations must be supplied, either by
-///annotating the resulting type binding `let collection: Vec<_> = ...` or by specializing when
-///calling many, `many::<Vec<_>, _>(...)`
+/// Parses `p` zero or more times returning a collection with the values from `p`.
+/// If the returned collection cannot be inferred type annotations must be supplied, either by
+/// annotating the resulting type binding `let collection: Vec<_> = ...` or by specializing when
+/// calling many, `many::<Vec<_>, _>(...)`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let result = many(digit())
 ///     .parse("123A")
@@ -445,6 +559,7 @@ impl<F, P> Parser for Many<F, P>
 /// assert_eq!(result, Ok(vec!['1', '2', '3']));
 /// # }
 /// ```
+#[inline(always)]
 pub fn many<F, P>(p: P) -> Many<F, P>
     where P: Parser,
           F: FromIterator<P::Output>
@@ -461,16 +576,20 @@ impl<F, P> Parser for Many1<F, P>
 {
     type Input = P::Input;
     type Output = F;
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
-        let (first, input) = try!(self.0.parse_lazy(input));
-        input.combine(move |input| {
-            let mut iter = Iter::new(&mut self.0, input);
-            let result = Some(first)
-                             .into_iter()
-                             .chain(iter.by_ref())
-                             .collect();
-            iter.into_result(result)
-        })
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
+        let (first, input) = ctry!(self.0.parse_lazy(input));
+        let mut iter = Iter {
+            parser: &mut self.0,
+            consumed: !input.is_empty(),
+            input: input.into_inner(),
+            state: State::Ok,
+        };
+        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>) {
         self.0.add_error(errors)
@@ -478,17 +597,19 @@ impl<F, P> Parser for Many1<F, P>
 }
 
 impl_parser!{ SkipMany(P,), Map<Many<Vec<()>, Map<P, fn (P::Output)>>, fn (Vec<()>)> }
-///Parses `p` zero or more times ignoring the result
+/// Parses `p` zero or more times ignoring the result
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let result = skip_many(digit())
 ///     .parse("A");
 /// assert_eq!(result, Ok(((), "A")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn skip_many<P>(p: P) -> SkipMany<P>
     where P: Parser
 {
@@ -499,17 +620,19 @@ pub fn skip_many<P>(p: P) -> SkipMany<P>
 }
 
 impl_parser!{ SkipMany1(P,), Map<Many1<Vec<()>, Map<P, fn (P::Output)>>, fn (Vec<()>)> }
-///Parses `p` one or more times ignoring the result
+/// Parses `p` one or more times ignoring the result
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let result = skip_many1(digit())
 ///     .parse("123A");
 /// assert_eq!(result, Ok(((), "A")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn skip_many1<P>(p: P) -> SkipMany1<P>
     where P: Parser
 {
@@ -519,21 +642,23 @@ pub fn skip_many1<P>(p: P) -> SkipMany1<P>
     SkipMany1(many1(p.map(ignore1)).map(ignore2))
 }
 
-///Parses `p` one or more times returning a collection with the values from `p`.
-///If the returned collection cannot be inferred type annotations must be supplied, either by
-///annotating the resulting type binding `let collection: Vec<_> = ...` or by specializing when
-///calling many1 `many1::<Vec<_>, _>(...)`
+/// Parses `p` one or more times returning a collection with the values from `p`.
+/// If the returned collection cannot be inferred type annotations must be supplied, either by
+/// annotating the resulting type binding `let collection: Vec<_> = ...` or by specializing when
+/// calling many1 `many1::<Vec<_>, _>(...)`
 ///
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let result = many1::<Vec<_>, _>(digit())
 ///     .parse("A123");
 /// assert!(result.is_err());
 /// # }
 /// ```
+#[inline(always)]
 pub fn many1<F, P>(p: P) -> Many1<F, P>
     where F: FromIterator<P::Output>,
           P: Parser
@@ -555,7 +680,8 @@ impl<F, P, S> Parser for SepBy<F, P, S>
     type Input = P::Input;
     type Output = F;
 
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
         sep_by1(&mut self.parser, &mut self.separator)
             .or(parser(|input| Ok((None.into_iter().collect(), Consumed::Empty(input)))))
             .parse_lazy(input)
@@ -572,8 +698,9 @@ impl<F, P, S> Parser for SepBy<F, P, S>
 /// specializing when calling sep_by, `sep_by::<Vec<_>, _, _>(...)`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let mut parser = sep_by(digit(), token(','));
 /// let result_ok = parser.parse("1,2,3");
@@ -582,6 +709,7 @@ impl<F, P, S> Parser for SepBy<F, P, S>
 /// assert_eq!(result_ok2, Ok((vec![], "")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn sep_by<F, P, S>(parser: P, separator: S) -> SepBy<F, P, S>
     where F: FromIterator<P::Output>,
           P: Parser,
@@ -608,17 +736,18 @@ impl<F, P, S> Parser for SepBy1<F, P, S>
     type Input = P::Input;
     type Output = F;
 
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
-        let (first, rest) = try!(self.parser.parse_lazy(input.clone()));
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
+        let (first, rest) = ctry!(self.parser.parse_lazy(input.clone()));
 
-        rest.combine(move |input| {
+        rest.combine_consumed(move |input| {
             let rest = (&mut self.separator).with(&mut self.parser);
             let mut iter = Iter::new(rest, input);
             let result = Some(first)
-                             .into_iter()
-                             .chain(iter.by_ref())
-                             .collect();
-            iter.into_result(result)
+                .into_iter()
+                .chain(iter.by_ref())
+                .collect();
+            iter.into_result_fast(result)
         })
     }
 
@@ -633,14 +762,16 @@ impl<F, P, S> Parser for SepBy1<F, P, S>
 /// specializing when calling sep_by, `sep_by1::<Vec<_>, _, _>(...)`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
-/// # use pc::primitives::{Error, Positioner};
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
+/// # use combine::primitives::{Error, Positioner};
 /// # fn main() {
 /// let mut parser = sep_by1(digit(), token(','));
-/// let result_ok = parser.parse("1,2,3");
+/// let result_ok = parser.parse(State::new("1,2,3"))
+///                       .map(|(vec, state)| (vec, state.input));
 /// assert_eq!(result_ok, Ok((vec!['1', '2', '3'], "")));
-/// let result_err = parser.parse("");
+/// let result_err = parser.parse(State::new(""));
 /// assert_eq!(result_err, Err(ParseError {
 ///     position: <char as Positioner>::start(),
 ///     errors: vec![
@@ -650,6 +781,7 @@ impl<F, P, S> Parser for SepBy1<F, P, S>
 /// }));
 /// # }
 /// ```
+#[inline(always)]
 pub fn sep_by1<F, P, S>(parser: P, separator: S) -> SepBy1<F, P, S>
     where F: FromIterator<P::Output>,
           P: Parser,
@@ -677,7 +809,8 @@ impl<F, P, S> Parser for SepEndBy<F, P, S>
     type Input = P::Input;
     type Output = F;
 
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
         sep_end_by1(&mut self.parser, &mut self.separator)
             .or(parser(|input| Ok((None.into_iter().collect(), Consumed::Empty(input)))))
             .parse_lazy(input)
@@ -694,8 +827,9 @@ impl<F, P, S> Parser for SepEndBy<F, P, S>
 /// specializing when calling sep_by, `sep_by::<Vec<_>, _, _>(...)`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let mut parser = sep_end_by(digit(), token(';'));
 /// let result_ok = parser.parse("1;2;3;");
@@ -704,6 +838,7 @@ impl<F, P, S> Parser for SepEndBy<F, P, S>
 /// assert_eq!(result_ok2, Ok((vec!['1', '2', '3'], "")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn sep_end_by<F, P, S>(parser: P, separator: S) -> SepEndBy<F, P, S>
     where F: FromIterator<P::Output>,
           P: Parser,
@@ -731,20 +866,21 @@ impl<F, P, S> Parser for SepEndBy1<F, P, S>
     type Input = P::Input;
     type Output = F;
 
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<F, P::Input> {
-        let (first, input) = try!(self.parser.parse_lazy(input.clone()));
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<F, P::Input> {
+        let (first, input) = ctry!(self.parser.parse_lazy(input.clone()));
 
-        input.combine(|input| {
+        input.combine_consumed(|input| {
             let rest = (&mut self.separator).with(optional(&mut self.parser));
             let mut iter = Iter::new(rest, input);
             // `iter` yields Option<P::Output>, by using flat map we make sure that we stop
             // iterating once a None element is received, i.e `self.parser` did not parse
             // successfully
             let result = Some(first)
-                             .into_iter()
-                             .chain(iter.by_ref().flat_map(|x| x))
-                             .collect();
-            iter.into_result(result)
+                .into_iter()
+                .chain(iter.by_ref().flat_map(|x| x))
+                .collect();
+            iter.into_result_fast(result)
         })
     }
 
@@ -759,14 +895,16 @@ impl<F, P, S> Parser for SepEndBy1<F, P, S>
 /// specializing when calling sep_by, `sep_by1::<Vec<_>, _, _>(...)`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
-/// # use pc::primitives::{Error, Positioner};
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
+/// # use combine::primitives::{Error, Positioner};
 /// # fn main() {
 /// let mut parser = sep_end_by1(digit(), token(';'));
-/// let result_ok = parser.parse("1;2;3;");
+/// let result_ok = parser.parse(State::new("1;2;3;"))
+///                       .map(|(vec, state)| (vec, state.input));
 /// assert_eq!(result_ok, Ok((vec!['1', '2', '3'], "")));
-/// let result_err = parser.parse("");
+/// let result_err = parser.parse(State::new(""));
 /// assert_eq!(result_err, Err(ParseError {
 ///     position: <char as Positioner>::start(),
 ///     errors: vec![
@@ -776,6 +914,7 @@ impl<F, P, S> Parser for SepEndBy1<F, P, S>
 /// }));
 /// # }
 /// ```
+#[inline(always)]
 pub fn sep_end_by1<F, P, S>(parser: P, separator: S) -> SepEndBy1<F, P, S>
     where F: FromIterator<P::Output>,
           P: Parser,
@@ -788,28 +927,31 @@ pub fn sep_end_by1<F, P, S>(parser: P, separator: S) -> SepEndBy1<F, P, S>
     }
 }
 
-impl<'a, I: Stream, O> Parser for FnMut(State<I>) -> ParseResult<O, I> + 'a {
+impl<'a, I: Stream, O> Parser for FnMut(I) -> ParseResult<O, I> + 'a {
     type Input = I;
     type Output = O;
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<O, I> {
+    fn parse_stream(&mut self, input: I) -> ParseResult<O, I> {
         self(input)
     }
 }
 #[derive(Clone)]
 pub struct FnParser<I, F>(F, PhantomData<fn(I) -> I>);
 
-///Wraps a function, turning it into a parser
-///Mainly needed to turn closures into parsers as function types can be casted to function pointers
-///to make them usable as a parser
+/// Wraps a function, turning it into a parser
+/// Mainly needed to turn closures into parsers as function types can be casted to function pointers
+/// to make them usable as a parser
 ///
 /// ```
-/// extern crate combine as pc;
-/// use pc::*;
-/// use pc::primitives::{Consumed, Error};
+/// extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
+/// # use combine::primitives::{Consumed, Error};
 /// # fn main() {
 /// let mut even_digit = parser(|input| {
-///     let position = input.position;
-///     let (char_digit, input) = try!(digit().parse_state(input));
+///     // Help type inference out
+///     let _: &str = input;
+///     let position = input.position();
+///     let (char_digit, input) = try!(digit().parse_stream(input));
 ///     let d = (char_digit as i32) - ('0' as i32);
 ///     if d % 2 == 0 {
 ///         Ok((d, input))
@@ -826,30 +968,31 @@ pub struct FnParser<I, F>(F, PhantomData<fn(I) -> I>);
 /// assert_eq!(result, Ok(8));
 /// # }
 /// ```
+#[inline(always)]
 pub fn parser<I, O, F>(f: F) -> FnParser<I, F>
     where I: Stream,
-          F: FnMut(State<I>) -> ParseResult<O, I>
+          F: FnMut(I) -> ParseResult<O, I>
 {
     FnParser(f, PhantomData)
 }
 
 impl<I, O, F> Parser for FnParser<I, F>
     where I: Stream,
-          F: FnMut(State<I>) -> ParseResult<O, I>
+          F: FnMut(I) -> ParseResult<O, I>
 {
     type Input = I;
     type Output = O;
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<O, I> {
+    fn parse_stream(&mut self, input: I) -> ParseResult<O, I> {
         (self.0)(input)
     }
 }
 
-impl<I, O> Parser for fn(State<I>) -> ParseResult<O, I>
+impl<I, O> Parser for fn(I) -> ParseResult<O, I>
     where I: Stream
 {
     type Input = I;
     type Output = O;
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<O, I> {
+    fn parse_stream(&mut self, input: I) -> ParseResult<O, I> {
         self(input)
     }
 }
@@ -861,20 +1004,22 @@ impl<P> Parser for Optional<P>
 {
     type Input = P::Input;
     type Output = Option<P::Output>;
-    fn parse_lazy(&mut self, input: State<P::Input>) -> ParseResult<Option<P::Output>, P::Input> {
-        match self.0.parse_state(input.clone()) {
-            Ok((x, rest)) => Ok((Some(x), rest)),
-            Err(err@Consumed::Consumed(_)) => return Err(err),
-            Err(Consumed::Empty(_)) => Ok((None, Consumed::Empty(input))),
+    #[inline]
+    fn parse_lazy(&mut self, input: P::Input) -> ConsumedResult<Option<P::Output>, P::Input> {
+        match self.0.parse_stream(input.clone()) {
+            Ok((x, rest)) => Ok((Some(x), rest)).into(),
+            Err(Consumed::Consumed(err)) => ConsumedErr(err),
+            Err(Consumed::Empty(_)) => EmptyOk((None, input)),
         }
     }
 }
 
-///Returns `Some(value)` and `None` on parse failure (always succeeds)
+/// Returns `Some(value)` and `None` on parse failure (always succeeds)
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let mut parser = optional(digit());
 /// let result1 = parser.parse("a");
@@ -883,6 +1028,7 @@ impl<P> Parser for Optional<P>
 /// assert_eq!(result2, Ok((Some('1'), "")));
 /// # }
 /// ```
+#[inline(always)]
 pub fn optional<P>(parser: P) -> Optional<P>
     where P: Parser
 {
@@ -890,12 +1036,13 @@ pub fn optional<P>(parser: P) -> Optional<P>
 }
 
 impl_parser! { Between(L, R, P), Skip<With<L, P>, R> }
-///Parses `open` followed by `parser` followed by `close`
-///Returns the value of `parser`
+/// Parses `open` followed by `parser` followed by `close`
+/// Returns the value of `parser`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::string;
 /// # fn main() {
 /// let result = between(token('['), token(']'), string("rust"))
 ///     .parse("[rust]")
@@ -903,6 +1050,7 @@ impl_parser! { Between(L, R, P), Skip<With<L, P>, R> }
 /// assert_eq!(result, Ok("rust"));
 /// # }
 /// ```
+#[inline(always)]
 pub fn between<I, L, R, P>(open: L, close: R, parser: P) -> Between<L, R, P>
     where I: Stream,
           L: Parser<Input = I>,
@@ -923,19 +1071,20 @@ impl<I, P, Op> Parser for Chainl1<P, Op>
     type Input = I;
     type Output = P::Output;
 
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<P::Output, I> {
-        let (mut l, mut input) = try!(self.0.parse_lazy(input));
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<P::Output, I> {
+        let (mut l, mut input) = ctry!(self.0.parse_lazy(input));
         loop {
-            match (&mut self.1, &mut self.0).parse_lazy(input.clone().into_inner()) {
+            match (&mut self.1, &mut self.0).parse_lazy(input.clone().into_inner()).into() {
                 Ok(((op, r), rest)) => {
                     l = op(l, r);
                     input = input.merge(rest);
                 }
-                Err(err@Consumed::Consumed(_)) => return Err(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
                 Err(Consumed::Empty(_)) => break,
             }
         }
-        Ok((l, input))
+        Ok((l, input)).into()
     }
 
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
@@ -943,19 +1092,21 @@ impl<I, P, Op> Parser for Chainl1<P, Op>
     }
 }
 
-///Parses `p` 1 or more times separated by `op`
-///The value returned is the one produced by the left associative application of `op`
+/// Parses `p` 1 or more times separated by `op`
+/// The value returned is the one produced by the left associative application of `op`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let number = digit().map(|c: char| c.to_digit(10).unwrap());
 /// let sub = token('-').map(|_| |l: u32, r: u32| l - r);
 /// let mut parser = chainl1(number, sub);
-///     assert_eq!(parser.parse("9-3-5"), Ok((1, "")));
-/// }
+/// assert_eq!(parser.parse("9-3-5"), Ok((1, "")));
+/// # }
 /// ```
+#[inline(always)]
 pub fn chainl1<P, Op>(parser: P, op: Op) -> Chainl1<P, Op>
     where P: Parser,
           Op: Parser<Input = P::Input>,
@@ -974,39 +1125,42 @@ impl<I, P, Op> Parser for Chainr1<P, Op>
 {
     type Input = I;
     type Output = P::Output;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<P::Output, I> {
-        let (mut l, mut input) = try!(self.0.parse_lazy(input));
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<P::Output, I> {
+        // FIXME FastResult
+        let (mut l, mut input) = ctry!(self.0.parse_lazy(input));
         loop {
-            let op = match self.1.parse_lazy(input.clone().into_inner()) {
+            let op = match self.1.parse_lazy(input.clone().into_inner()).into() {
                 Ok((x, rest)) => {
                     input = input.merge(rest);
                     x
                 }
-                Err(err@Consumed::Consumed(_)) => return Err(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
                 Err(Consumed::Empty(_)) => break,
             };
-            match self.parse_lazy(input.clone().into_inner()) {
+            match self.parse_lazy(input.clone().into_inner()).into() {
                 Ok((r, rest)) => {
                     l = op(l, r);
                     input = input.merge(rest);
                 }
-                Err(err@Consumed::Consumed(_)) => return Err(err),
+                Err(Consumed::Consumed(err)) => return ConsumedErr(err),
                 Err(Consumed::Empty(_)) => break,
             }
         }
-        Ok((l, input))
+        Ok((l, input)).into()
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
         self.0.add_error(errors)
     }
 }
 
-///Parses `p` one or more times separated by `op`
-///The value returned is the one produced by the right associative application of `op`
+/// Parses `p` one or more times separated by `op`
+/// The value returned is the one produced by the right associative application of `op`
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::digit;
 /// # fn main() {
 /// let number = digit().map(|c: char| c.to_digit(10).unwrap());
 /// let pow = token('^').map(|_| |l: u32, r: u32| l.pow(r));
@@ -1014,6 +1168,7 @@ impl<I, P, Op> Parser for Chainr1<P, Op>
 ///     assert_eq!(parser.parse("2^3^2"), Ok((512, "")));
 /// }
 /// ```
+#[inline(always)]
 pub fn chainr1<P, Op>(parser: P, op: Op) -> Chainr1<P, Op>
     where P: Parser,
           Op: Parser<Input = P::Input>,
@@ -1030,22 +1185,25 @@ impl<I, O, P> Parser for Try<P>
 {
     type Input = I;
     type Output = O;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
         self.0
-            .parse_state(input)
+            .parse_stream(input)
             .map_err(Consumed::as_empty)
+            .into()
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
         self.0.add_error(errors)
     }
 }
 
-///Try acts as `p` except it acts as if the parser hadn't consumed any input
-///if `p` returns an error after consuming input
+/// Try acts as `p` except it acts as if the parser hadn't consumed any input
+/// if `p` returns an error after consuming input
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::string;
 /// # fn main() {
 /// let mut p = try(string("let"))
 ///     .or(string("lex"));
@@ -1055,6 +1213,7 @@ impl<I, O, P> Parser for Try<P>
 /// assert!(result.is_err());
 /// # }
 /// ```
+#[inline(always)]
 pub fn try<P>(p: P) -> Try<P>
     where P: Parser
 {
@@ -1071,8 +1230,10 @@ impl<I, O, P> Parser for LookAhead<P>
     type Input = I;
     type Output = O;
 
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
-        self.0.parse_lazy(input.clone()).map(|(o, _input)| (o, Consumed::Empty(input)))
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
+        let (o, _input) = ctry!(self.0.parse_lazy(input.clone()));
+        EmptyOk((o, input))
     }
 
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
@@ -1080,11 +1241,12 @@ impl<I, O, P> Parser for LookAhead<P>
     }
 }
 
-///look_ahead acts as p but doesn't consume input on success.
+/// look_ahead acts as p but doesn't consume input on success.
 ///
 /// ```
-/// # extern crate combine as pc;
-/// # use pc::*;
+/// # extern crate combine;
+/// # use combine::*;
+/// # use combine::char::string;
 /// # fn main() {
 //        let mut p = look_ahead(string("test"));
 //
@@ -1095,6 +1257,7 @@ impl<I, O, P> Parser for LookAhead<P>
 //        assert!(result.is_err());
 /// # }
 /// ```
+#[inline(always)]
 pub fn look_ahead<P>(p: P) -> LookAhead<P>
     where P: Parser
 {
@@ -1102,28 +1265,7 @@ pub fn look_ahead<P>(p: P) -> LookAhead<P>
 }
 
 #[derive(Clone)]
-pub struct And<P1, P2>(P1, P2);
-impl<I, P1, P2> Parser for And<P1, P2>
-    where I: Stream,
-          P1: Parser<Input = I>,
-          P2: Parser<Input = I>
-{
-    type Input = I;
-    type Output = (P1::Output, P2::Output);
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<(P1::Output, P2::Output), I> {
-        let (a, rest) = try!(self.0.parse_lazy(input));
-        rest.combine(move |rest| {
-            let (b, rest) = try!(self.1.parse_state(rest));
-            Ok(((a, b), rest))
-        })
-    }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        self.0.add_error(errors)
-    }
-}
-
-#[derive(Clone)]
-pub struct With<P1, P2>(P1, P2)
+pub struct With<P1, P2>((P1, P2))
     where P1: Parser,
           P2: Parser;
 impl<I, P1, P2> Parser for With<P1, P2>
@@ -1133,17 +1275,25 @@ impl<I, P1, P2> Parser for With<P1, P2>
 {
     type Input = I;
     type Output = P2::Output;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<Self::Output, I> {
-        let ((_, b), rest) = try!((&mut self.0).and(&mut self.1).parse_lazy(input));
-        Ok((b, rest))
+    #[inline]
+    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>) {
         self.0.add_error(errors)
     }
 }
 
+#[inline(always)]
+pub fn with<P1, P2>(p1: P1, p2: P2) -> With<P1, P2>
+    where P1: Parser,
+          P2: Parser<Input = P1::Input>
+{
+    With((p1, p2))
+}
+
 #[derive(Clone)]
-pub struct Skip<P1, P2>(P1, P2)
+pub struct Skip<P1, P2>((P1, P2))
     where P1: Parser,
           P2: Parser;
 impl<I, P1, P2> Parser for Skip<P1, P2>
@@ -1153,17 +1303,25 @@ impl<I, P1, P2> Parser for Skip<P1, P2>
 {
     type Input = I;
     type Output = P1::Output;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<Self::Output, I> {
-        let ((a, _), rest) = try!((&mut self.0).and(&mut self.1).parse_lazy(input));
-        Ok((a, rest))
+    #[inline]
+    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>) {
         self.0.add_error(errors)
     }
 }
 
+#[inline(always)]
+pub fn skip<P1, P2>(p1: P1, p2: P2) -> Skip<P1, P2>
+    where P1: Parser,
+          P2: Parser<Input = P1::Input>
+{
+    Skip((p1, p2))
+}
+
 #[derive(Clone)]
-pub struct Message<P>(P, Info<<P::Input as Stream>::Item, <P::Input as Stream>::Range>)
+pub struct Message<P>(P, Info<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>)
     where P: Parser;
 impl<I, P> Parser for Message<P>
     where I: Stream,
@@ -1172,10 +1330,10 @@ impl<I, P> Parser for Message<P>
     type Input = I;
     type Output = P::Output;
 
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<Self::Output, I> {
+    fn parse_stream(&mut self, input: I) -> ParseResult<Self::Output, I> {
         // The message should always be added even if some input was consumed before failing
         self.0
-            .parse_state(input.clone())
+            .parse_stream(input.clone())
             .map_err(|errors| {
                 errors.map(|mut errors| {
                     errors.add_message(self.1.clone());
@@ -1184,7 +1342,8 @@ impl<I, P> Parser for Message<P>
             })
     }
 
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<Self::Output, I> {
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<Self::Output, I> {
         self.0.parse_lazy(input.clone())
     }
 
@@ -1194,6 +1353,15 @@ impl<I, P> Parser for Message<P>
     }
 }
 
+#[inline(always)]
+pub fn message<P>(p: P,
+                  msg: Info<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>)
+                  -> Message<P>
+    where P: Parser
+{
+    Message(p, msg)
+}
+
 #[derive(Clone)]
 pub struct Or<P1, P2>(P1, P2)
     where P1: Parser,
@@ -1205,15 +1373,18 @@ impl<I, O, P1, P2> Parser for Or<P1, P2>
 {
     type Input = I;
     type Output = O;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
         match self.0.parse_lazy(input.clone()) {
-            Ok(x) => Ok(x),
-            Err(err@Consumed::Consumed(_)) => Err(err),
-            Err(Consumed::Empty(error1)) => {
+            ConsumedOk(x) => ConsumedOk(x),
+            EmptyOk(x) => EmptyOk(x),
+            ConsumedErr(err) => ConsumedErr(err),
+            EmptyErr(error1) => {
                 match self.1.parse_lazy(input) {
-                    Ok(x) => Ok(x),
-                    Err(err@Consumed::Consumed(_)) => Err(err),
-                    Err(Consumed::Empty(error2)) => Err(Consumed::Empty(error1.merge(error2))),
+                    ConsumedOk(x) => ConsumedOk(x),
+                    EmptyOk(x) => EmptyOk(x),
+                    ConsumedErr(err) => ConsumedErr(err),
+                    EmptyErr(error2) => EmptyErr(error1.merge(error2)),
                 }
             }
         }
@@ -1224,6 +1395,14 @@ impl<I, O, P1, P2> Parser for Or<P1, P2>
     }
 }
 
+#[inline(always)]
+pub fn or<P1, P2>(p1: P1, p2: P2) -> Or<P1, P2>
+    where P1: Parser,
+          P2: Parser<Input = P1::Input, Output = P1::Output>
+{
+    Or(p1, p2)
+}
+
 #[derive(Clone)]
 pub struct Map<P, F>(P, F);
 impl<I, A, B, P, F> Parser for Map<P, F>
@@ -1233,10 +1412,13 @@ impl<I, A, B, P, F> Parser for Map<P, F>
 {
     type Input = I;
     type Output = B;
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<B, I> {
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<B, I> {
         match self.0.parse_lazy(input) {
-            Ok((x, input)) => Ok(((self.1)(x), input)),
-            Err(err) => Err(err),
+            ConsumedOk((x, input)) => ConsumedOk(((self.1)(x), input)),
+            EmptyOk((x, input)) => EmptyOk(((self.1)(x), input)),
+            ConsumedErr(err) => ConsumedErr(err),
+            EmptyErr(err) => EmptyErr(err),
         }
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
@@ -1244,6 +1426,55 @@ impl<I, A, B, P, F> Parser for Map<P, F>
     }
 }
 
+#[inline(always)]
+pub fn map<P, F, B>(p: P, f: F) -> Map<P, F>
+    where P: Parser,
+          F: FnMut(P::Output) -> B
+{
+    Map(p, f)
+}
+
+#[derive(Clone)]
+pub struct FlatMap<P, F>(P, F);
+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>>
+{
+    type Input = I;
+    type Output = B;
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<B, I> {
+        match self.0.parse_lazy(input) {
+            EmptyOk((o, input)) => {
+                match (self.1)(o) {
+                    Ok(x) => EmptyOk((x, input)),
+                    Err(err) => EmptyErr(err),
+                }
+            }
+            ConsumedOk((o, input)) => {
+                match (self.1)(o) {
+                    Ok(x) => ConsumedOk((x, input)),
+                    Err(err) => ConsumedErr(err),
+                }
+            }
+            EmptyErr(err) => EmptyErr(err),
+            ConsumedErr(err) => ConsumedErr(err),
+        }
+    }
+    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+        self.0.add_error(errors);
+    }
+}
+
+#[inline(always)]
+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>>
+{
+    FlatMap(p, f)
+}
+
 #[derive(Clone)]
 pub struct Then<P, F>(P, F);
 impl<P, N, F> Parser for Then<P, F>
@@ -1253,20 +1484,40 @@ impl<P, N, F> Parser for Then<P, F>
 {
     type Input = N::Input;
     type Output = N::Output;
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        let (value, input) = try!(self.0.parse_lazy(input));
-        input.combine(move |input| {
-            let mut next = (self.1)(value);
-            next.parse_state(input)
-        })
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        match self.0.parse_lazy(input) {
+            EmptyOk((value, input)) => {
+                let mut next = (self.1)(value);
+                next.parse_stream_consumed(input)
+            }
+            ConsumedOk((value, input)) => {
+                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(err) => EmptyErr(err),
+            ConsumedErr(err) => ConsumedErr(err),
+        }
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
         self.0.add_error(errors);
     }
 }
 
+#[inline(always)]
+pub fn then<P, F, N>(p: P, f: F) -> Then<P, F>
+    where F: FnMut(P::Output) -> N,
+          P: Parser,
+          N: Parser<Input = P::Input>
+{
+    Then(p, f)
+}
+
 #[derive(Clone)]
-pub struct Expected<P>(P, Info<<P::Input as Stream>::Item, <P::Input as Stream>::Range>)
+pub struct Expected<P>(P, Info<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>)
     where P: Parser;
 impl<P> Parser for Expected<P>
     where P: Parser
@@ -1274,11 +1525,11 @@ impl<P> Parser for Expected<P>
     type Input = P::Input;
     type Output = P::Output;
 
-    fn parse_state(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
+    fn parse_stream(&mut self, input: Self::Input) -> ParseResult<Self::Output, Self::Input> {
         // add_error is only called on unconsumed inputs but we want this expected message to always
         // replace the ones always present in the ParseError
         self.0
-            .parse_state(input)
+            .parse_stream(input)
             .map_err(|errors| {
                 errors.map(|mut errors| {
                     errors.set_expected(self.1.clone());
@@ -1287,7 +1538,8 @@ impl<P> Parser for Expected<P>
             })
     }
 
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
         self.0.parse_lazy(input)
     }
 
@@ -1312,270 +1564,56 @@ impl<P> Parser for Expected<P>
     }
 }
 
+#[inline(always)]
+pub fn expected<P>(p: P,
+                   info: Info<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>)
+                   -> Expected<P>
+    where P: Parser
+{
+    Expected(p, info)
+}
+
 #[derive(Clone)]
 pub struct AndThen<P, F>(P, F);
 impl<P, F, O, E> Parser for AndThen<P, F>
     where P: Parser,
           F: FnMut(P::Output) -> Result<O, E>,
-          E: Into<Error<<P::Input as Stream>::Item, <P::Input as Stream>::Range>>
+          E: Into<Error<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>>
 {
     type Input = P::Input;
     type Output = O;
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<O, Self::Input> {
-        self.0
-            .parse_lazy(input)
-            .and_then(|(o, input)| {
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<O, Self::Input> {
+        match self.0.parse_lazy(input) {
+            EmptyOk((o, input)) => {
                 match (self.1)(o) {
-                    Ok(o) => Ok((o, input)),
-                    Err(err) => {
-                        Err(input.map(move |input| ParseError::new(input.position, err.into())))
-                    }
+                    Ok(o) => EmptyOk((o, input)),
+                    Err(err) => EmptyErr(ParseError::new(input.position(), err.into())),
                 }
-            })
+            }
+            ConsumedOk((o, input)) => {
+                match (self.1)(o) {
+                    Ok(o) => ConsumedOk((o, input)),
+                    Err(err) => ConsumedErr(ParseError::new(input.position(), err.into())),
+                }
+            }
+            EmptyErr(err) => EmptyErr(err),
+            ConsumedErr(err) => ConsumedErr(err),
+        }
     }
     fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
         self.0.add_error(errors);
     }
 }
 
-///Extension trait which provides functions that are more conveniently used through method calls
-pub trait ParserExt : Parser + Sized {
-
-    ///Discards the value of the `self` parser and returns the value of `p`
-    ///Fails if any of the parsers fails
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let result = digit()
-    ///     .with(token('i'))
-    ///     .parse("9i")
-    ///     .map(|x| x.0);
-    /// assert_eq!(result, Ok('i'));
-    /// # }
-    /// ```
-    fn with<P2>(self, p: P2) -> With<Self, P2>
-        where P2: Parser<Input = Self::Input>
-    {
-        With(self, p)
-    }
-
-    ///Discards the value of the `p` parser and returns the value of `self`
-    ///Fails if any of the parsers fails
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let result = digit()
-    ///     .skip(token('i'))
-    ///     .parse("9i")
-    ///     .map(|x| x.0);
-    /// assert_eq!(result, Ok('9'));
-    /// # }
-    /// ```
-    fn skip<P2>(self, p: P2) -> Skip<Self, P2>
-        where P2: Parser<Input = Self::Input>
-    {
-        Skip(self, p)
-    }
-
-    ///Parses with `self` followed by `p`
-    ///Succeeds if both parsers succeed, otherwise fails
-    ///Returns a tuple with both values on success
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let result = digit()
-    ///     .and(token('i'))
-    ///     .parse("9i")
-    ///     .map(|x| x.0);
-    /// assert_eq!(result, Ok(('9', 'i')));
-    /// # }
-    /// ```
-    fn and<P2>(self, p: P2) -> And<Self, P2>
-        where P2: Parser<Input = Self::Input>
-    {
-        And(self, p)
-    }
-
-    /// Returns a parser which attempts to parse using `self`. If `self` fails without consuming any
-    /// input it tries to consume the same input using `p`.
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let mut parser = string("let")
-    ///     .or(digit().map(|_| "digit"))
-    ///     .or(string("led"));
-    /// assert_eq!(parser.parse("let"), Ok(("let", "")));
-    /// assert_eq!(parser.parse("1"), Ok(("digit", "")));
-    /// assert!(parser.parse("led").is_err());
-    ///
-    /// let mut parser2 = string("two").or(string("three"));
-    /// // Fails as the parser for "two" consumes the first 't' before failing
-    /// assert!(parser2.parse("three").is_err());
-    ///
-    /// // Use 'try' to make failing parsers always act as if they have not consumed any input
-    /// let mut parser3 = try(string("two")).or(try(string("three")));
-    /// assert_eq!(parser3.parse("three"), Ok(("three", "")));
-    /// # }
-    /// ```
-    fn or<P2>(self, p: P2) -> Or<Self, P2>
-        where P2: Parser<Input = Self::Input>
-    {
-        Or(self, p)
-    }
-
-    ///Parses using `self` and then passes the value to `f` which returns a parser used to parse
-    ///the rest of the input
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # use pc::primitives::{Consumed, Error};
-    /// # fn main() {
-    /// let result = digit()
-    ///     .then(|d| parser(move |input| {
-    ///         if d == '9' {
-    ///             Ok((9, Consumed::Empty(input)))
-    ///         }
-    ///         else {
-    ///             let err = ParseError::new(input.position, Error::Message("Not a nine".into()));
-    ///             Err((Consumed::Empty(err)))
-    ///         }
-    ///     }))
-    ///     .parse("9");
-    /// assert_eq!(result, Ok((9, "")));
-    /// # }
-    /// ```
-    fn then<N, F>(self, f: F) -> Then<Self, F>
-        where F: FnMut(Self::Output) -> N,
-              N: Parser<Input = Self::Input>
-    {
-        Then(self, f)
-    }
-
-    ///Uses `f` to map over the parsed value
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let result = digit()
-    ///     .map(|c| c == '9')
-    ///     .parse("9")
-    ///     .map(|x| x.0);
-    /// assert_eq!(result, Ok(true));
-    /// # }
-    /// ```
-    fn map<F, B>(self, f: F) -> Map<Self, F>
-        where F: FnMut(Self::Output) -> B
-    {
-        Map(self, f)
-    }
-
-    ///Parses with `self` and if it fails, adds the message `msg` to the error
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # use pc::primitives::{Error, Positioner};
-    /// # fn main() {
-    /// let result = token('9')
-    ///     .message("Not a nine")
-    ///     .parse("8");
-    /// assert_eq!(result, Err(ParseError {
-    ///     position: <char as Positioner>::start(),
-    ///     errors: vec![
-    ///         Error::Unexpected('8'.into()),
-    ///         Error::Expected('9'.into()),
-    ///         Error::Message("Not a nine".into())
-    ///     ]
-    /// }));
-    /// # }
-    /// ```
-    fn message<S>(self, msg: S) -> Message<Self>
-        where S: Into<Info<<Self::Input as Stream>::Item, <Self::Input as Stream>::Range>>
-    {
-        Message(self, msg.into())
-    }
-
-    /// Parses with `self` and if it fails without consuming any input any expected errors are
-    /// replaced by `msg`. `msg` is then used in error messages as "Expected `msg`".
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # use pc::primitives::{Error, Positioner};
-    /// # fn main() {
-    /// let result = token('9')
-    ///     .expected("nine")
-    ///     .parse("8");
-    /// assert_eq!(result, Err(ParseError {
-    ///     position: <char as Positioner>::start(),
-    ///     errors: vec![Error::Unexpected('8'.into()), Error::Expected("nine".into())]
-    /// }));
-    /// # }
-    /// ```
-    fn expected<S>(self, msg: S) -> Expected<Self>
-        where S: Into<Info<<Self::Input as Stream>::Item, <Self::Input as Stream>::Range>>
-    {
-        Expected(self, msg.into())
-    }
-
-    ///Parses with `self` and applies `f` on the result if `self` parses successfully
-    ///`f` may optionally fail with an error which is automatically converted to a `ParseError`
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let mut parser = many1(digit())
-    ///     .and_then(|s: String| s.parse::<i32>());
-    /// let result = parser.parse("1234");
-    /// assert_eq!(result, Ok((1234, "")));
-    /// let err = parser.parse("abc");
-    /// assert!(err.is_err());
-    /// # }
-    /// ```
-    fn and_then<F, O, E>(self, f: F) -> AndThen<Self, F>
-        where F: FnMut(Self::Output) -> Result<O, E>,
-              E: Into<Error<<Self::Input as Stream>::Item, <Self::Input as Stream>::Range>>
-    {
-        AndThen(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
-    ///
-    /// ```
-    /// # extern crate combine as pc;
-    /// # use pc::*;
-    /// # fn main() {
-    /// let mut buffer = String::new();
-    /// let number = parser(|input| {
-    ///     buffer.clear();
-    ///     let mut iter = digit().iter(input);
-    ///     buffer.extend(&mut iter);
-    ///     let i = buffer.parse::<i32>().unwrap();
-    ///     iter.into_result(i)
-    /// });
-    /// let result = sep_by(number, char(','))
-    ///     .parse("123,45,6");
-    /// assert_eq!(result, Ok((vec![123, 45, 6], "")));
-    /// # }
-    /// ```
-    fn iter(self, input: State<Self::Input>) -> Iter<Self> {
-        Iter::new(self, input)
-    }
-}
-
-impl<P: Parser> ParserExt for P {}
+#[inline(always)]
+pub fn and_then<P, F, O, E>(p: P, f: F) -> AndThen<P, F>
+    where P: Parser,
+          F: FnMut(P::Output) -> Result<O, E>,
+          E: Into<Error<<P::Input as StreamOnce>::Item, <P::Input as StreamOnce>::Range>>
+{
+    AndThen(p, f)
+}
 
 macro_rules! tuple_parser {
     ($h: ident, $($id: ident),+) => {
@@ -1588,12 +1626,53 @@ macro_rules! tuple_parser {
             type Output = ($h::Output, $($id::Output),+);
             #[allow(non_snake_case)]
             fn parse_lazy(&mut self,
-                          input: State<Input>)
-                          -> ParseResult<($h::Output, $($id::Output),+), Input> {
+                          mut input: Input)
+                          -> ConsumedResult<($h::Output, $($id::Output),+), Input> {
                 let (ref mut $h, $(ref mut $id),+) = *self;
-                let ($h, input) = try!($h.parse_lazy(input));
-                $(let ($id, input) = try!(input.combine(|input| $id.parse_state(input)));)+
-                Ok((($h, $($id),+), input))
+                let mut consumed = false;
+                let $h = match $h.parse_lazy(input) {
+                    ConsumedOk((x, new_input)) => {
+                        consumed = true;
+                        input = new_input;
+                        x
+                    }
+                    EmptyErr(err) => return EmptyErr(err),
+                    ConsumedErr(err) => return ConsumedErr(err),
+                    EmptyOk((x, new_input)) => {
+                        input = new_input;
+                        x
+                    }
+                };
+                $(
+                    let $id = match $id.parse_lazy(input.clone()) {
+                        ConsumedOk((x, new_input)) => {
+                            consumed = true;
+                            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)
+                            } else {
+                                return EmptyErr(err)
+                            }
+                        }
+                        ConsumedErr(err) => return ConsumedErr(err),
+                        EmptyOk((x, new_input)) => {
+                            input = new_input;
+                            x
+                        }
+                    };
+                )+
+                if consumed {
+                    ConsumedOk((($h, $($id),+), input))
+                } else {
+                    EmptyOk((($h, $($id),+), input))
+                }
             }
             fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
                 self.0.add_error(errors);
@@ -1619,7 +1698,7 @@ pub struct EnvParser<E, I, T>
     where I: Stream
 {
     env: E,
-    parser: fn(E, State<I>) -> ParseResult<T, I>,
+    parser: fn(E, I) -> ParseResult<T, I>,
 }
 
 impl<E, I, O> Parser for EnvParser<E, I, O>
@@ -1629,8 +1708,9 @@ impl<E, I, O> Parser for EnvParser<E, I, O>
     type Input = I;
     type Output = O;
 
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
-        (self.parser)(self.env.clone(), input)
+    #[inline]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
+        (self.parser)(self.env.clone(), input).into()
     }
 }
 
@@ -1639,19 +1719,19 @@ impl<E, I, O> Parser for EnvParser<E, I, O>
 /// while still allowing the parsers to be written in separate functions.
 ///
 /// ```
-/// # extern crate combine as pc;
+/// # extern crate combine;
 /// # use std::collections::HashMap;
-/// # use pc::primitives::Stream;
-/// # use pc::*;
+/// # use combine::*;
+/// # use combine::char::letter;
 /// # fn main() {
 ///     struct Interner(HashMap<String, u32>);
 ///     impl Interner {
-///         fn string<I>(&self, input: State<I>) -> ParseResult<u32, I>
+///         fn string<I>(&self, input: I) -> ParseResult<u32, I>
 ///             where I: Stream<Item=char>
 ///         {
 ///             many(letter())
 ///                 .map(|s: String| self.0.get(&s).cloned().unwrap_or(0))
-///                 .parse_state(input)
+///                 .parse_stream(input)
 ///         }
 ///     }
 ///
@@ -1669,9 +1749,8 @@ impl<E, I, O> Parser for EnvParser<E, I, O>
 ///     assert_eq!(result, Ok((0, "")));
 /// # }
 /// ```
-pub fn env_parser<E, I, O>(env: E,
-                           parser: fn(E, State<I>) -> ParseResult<O, I>)
-                           -> EnvParser<E, I, O>
+#[inline(always)]
+pub fn env_parser<E, I, O>(env: E, parser: fn(E, I) -> ParseResult<O, I>) -> EnvParser<E, I, O>
     where E: Clone,
           I: Stream
 {
@@ -1681,179 +1760,10 @@ pub fn env_parser<E, I, O>(env: E,
     }
 }
 
-pub struct Range<I>(I::Range) where I: RangeStream;
-
-impl<I, E> Parser for Range<I>
-    where I: RangeStream<Item = E>,
-          I::Range: Positioner<Position = E::Position> + PartialEq + ::primitives::Range,
-          E: Positioner + Clone
-{
-    type Input = I;
-    type Output = I::Range;
-
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        use primitives::Range;
-        let State { mut position, input, .. } = input;
-        match input.uncons_range(self.0.len()) {
-            Ok((other, rest)) => {
-                if other == self.0 {
-                    self.0.update(&mut position);
-                    Ok((other,
-                        Consumed::Consumed(State {
-                        position: position,
-                        input: rest,
-                    })))
-                } else {
-                    Err(Consumed::Empty(ParseError::empty(position)))
-                }
-            }
-            Err(err) => Err(Consumed::Empty(ParseError::new(position, err))),
-        }
-    }
-    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
-        // TODO Add unexpected message?
-        errors.add_error(Error::Expected(Info::Range(self.0.clone())));
-    }
-}
-
-/// ```
-/// # extern crate combine as pc;
-/// # use pc::combinator::range;
-/// # use pc::*;
-/// # fn main() {
-/// let mut parser = range("hello");
-/// let result = parser.parse("hello world");
-/// assert_eq!(result, Ok(("hello", " world")));
-/// let result = parser.parse("hel world");
-/// assert!(result.is_err());
-/// # }
-/// ```
-pub fn range<I, E>(i: I::Range) -> Range<I>
-    where I: RangeStream<Item = E>,
-          I::Range: Positioner<Position = E::Position> + PartialEq + ::primitives::Range,
-          E: Positioner + Clone
-{
-    Range(i)
-}
-
-pub struct Take<I>(usize, PhantomData<fn(I) -> I>);
-impl<I, E> Parser for Take<I>
-    where I: RangeStream<Item = E>,
-          I::Range: ::primitives::Range + Positioner<Position = E::Position>,
-          E: Positioner + Clone
-{
-    type Input = I;
-    type Output = I::Range;
-
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        input.uncons_range(self.0)
-    }
-}
-
-/// ```
-/// # extern crate combine as pc;
-/// # use pc::combinator::take;
-/// # use pc::*;
-/// # fn main() {
-/// let mut parser = take(4);
-/// let result = parser.parse("123abc");
-/// assert_eq!(result, Ok(("123a", "bc")));
-/// let result = parser.parse("abc");
-/// assert!(result.is_err());
-/// # }
-/// ```
-pub fn take<I>(n: usize) -> Take<I>
-    where I: RangeStream,
-          I::Range: ::primitives::Range
-{
-    Take(n, PhantomData)
-}
-
-pub struct TakeWhile<I, F>(F, PhantomData<fn(I) -> I>);
-impl<I, E, F> Parser for TakeWhile<I, F>
-    where I: RangeStream<Item = E>,
-          I::Range: ::primitives::Range + Positioner<Position = E::Position>,
-          E: Positioner + Clone,
-          F: FnMut(I::Item) -> bool
-{
-    type Input = I;
-    type Output = I::Range;
-
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        input.uncons_while(&mut self.0)
-    }
-}
-
-/// ```
-/// # extern crate combine as pc;
-/// # use pc::combinator::take_while;
-/// # use pc::*;
-/// # fn main() {
-/// let mut parser = take_while(|c: char| c.is_digit(10));
-/// let result = parser.parse("123abc");
-/// assert_eq!(result, Ok(("123", "abc")));
-/// let result = parser.parse("abc");
-/// assert_eq!(result, Ok(("", "abc")));
-/// # }
-/// ```
-pub fn take_while<I, F>(f: F) -> TakeWhile<I, F>
-    where I: RangeStream,
-          F: FnMut(I::Item) -> bool
-{
-    TakeWhile(f, PhantomData)
-}
-
-pub struct TakeWhile1<I, F>(F, PhantomData<fn(I) -> I>);
-impl<I, F> Parser for TakeWhile1<I, F>
-    where I: RangeStream,
-          I::Range: ::primitives::Range,
-          F: FnMut(I::Item) -> bool
-{
-    type Input = I;
-    type Output = I::Range;
-
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        input.uncons_while(&mut self.0)
-             .and_then(|(v, input)| {
-                 match input {
-                     Consumed::Consumed(_) => Ok((v, input)),
-                     Consumed::Empty(input) => {
-                         let error = match input.input.uncons() {
-                             Ok((t, _)) => Error::Unexpected(Info::Token(t)),
-                             Err(err) => err,
-                         };
-                         Err(Consumed::Empty(ParseError::new(input.position, error)))
-                     }
-                 }
-             })
-    }
-}
-
-
-/// ```
-/// # extern crate combine as pc;
-/// # use pc::combinator::take_while1;
-/// # use pc::*;
-/// # fn main() {
-/// let mut parser = take_while1(|c: char| c.is_digit(10));
-/// let result = parser.parse("123abc");
-/// assert_eq!(result, Ok(("123", "abc")));
-/// let result = parser.parse("abc");
-/// assert!(result.is_err());
-/// # }
-/// ```
-pub fn take_while1<I, F>(f: F) -> TakeWhile1<I, F>
-    where I: RangeStream,
-          I::Range: ::primitives::Range,
-          F: FnMut(I::Item) -> bool
-{
-    TakeWhile1(f, PhantomData)
-}
-
 #[cfg(test)]
 mod tests {
     use super::*;
-    use primitives::{Error, ParseError, Positioner, Parser};
+    use primitives::{Error, ParseError, Positioner, Parser, State};
     use char::{digit, letter};
 
     #[test]
@@ -1875,14 +1785,14 @@ mod tests {
         assert_eq!(parser.parse("1,2,z"), Ok((('1', ',', '2', ',', 'z'), "")));
     }
 
-    ///The expected combinator should retain only errors that are not `Expected`
+    /// The expected combinator should retain only errors that are not `Expected`
     #[test]
     fn expected_retain_errors() {
         let mut parser = digit()
-                             .message("message")
-                             .expected("N/A")
-                             .expected("my expected digit");
-        assert_eq!(parser.parse("a"),
+            .message("message")
+            .expected("N/A")
+            .expected("my expected digit");
+        assert_eq!(parser.parse(State::new("a")),
                    Err(ParseError {
                        position: <char as Positioner>::start(),
                        errors: vec![Error::Unexpected('a'.into()),
@@ -1894,24 +1804,11 @@ mod tests {
     #[test]
     fn tuple_parse_error() {
         let mut parser = (digit(), digit());
-        let result = parser.parse("a");
+        let result = parser.parse(State::new("a"));
         assert_eq!(result,
                    Err(ParseError {
                        position: <char as Positioner>::start(),
                        errors: vec![Error::Unexpected('a'.into()), Error::Expected("digit".into())],
                    }));
     }
-
-    #[test]
-    fn take_while_test() {
-        let result = take_while(|c: char| c.is_digit(10)).parse("123abc");
-        assert_eq!(result, Ok(("123", "abc")));
-    }
-
-    #[test]
-    fn range_string_no_char_boundary_error() {
-        let mut parser = range("hello");
-        let result = parser.parse("hell\u{00EE} world");
-        assert!(result.is_err());
-    }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 0ef1eb93..2e18ec14 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -19,7 +19,8 @@
 //!
 //! ```rust
 //! extern crate combine;
-//! use combine::{digit, letter, Parser, ParserExt};
+//! use combine::Parser;
+//! use combine::char::{digit, letter};
 //!
 //! fn main() {
 //!     if let Err(err) = digit().or(letter()).parse("|") {
@@ -37,8 +38,8 @@
 //!
 //! * `combinator` contains the before mentioned parser combinators and thus contains the main
 //! building blocks for creating any sort of complex parsers. It consists of free functions `such`
-//! as `many` and `satisfy` as well as a the `ParserExt` 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.
 //!
 //! * `char` provides parsers specifically working with streams of characters.
 //! As a few examples it has parsers for accepting digits, letters or whitespace.
@@ -51,7 +52,8 @@
 //!
 //! ```
 //! extern crate combine;
-//! use combine::{spaces, many1, sep_by, digit, char, Parser, ParserExt, ParseError};
+//! use combine::char::{spaces, digit, char};
+//! use combine::{many1, sep_by, Parser, ParseError};
 //!
 //! fn main() {
 //!     //Parse spaces first and use the with method to only keep the result of the next parser
@@ -77,11 +79,12 @@
 //! 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: State<&str>) -> ParseResult<Expr, &str>`
+//! could define `expr` as `fn expr(input: &str) -> ParseResult<Expr, &str>`
 //!
 //! ```
 //! extern crate combine;
-//! use combine::{between, char, letter, spaces, many1, parser, sep_by, Parser, ParserExt};
+//! use combine::char::{char, letter, spaces};
+//! use combine::{between, many1, parser, sep_by, Parser};
 //! use combine::primitives::{State, Stream, ParseResult};
 //!
 //! #[derive(Debug, PartialEq)]
@@ -91,7 +94,7 @@
 //!     Pair(Box<Expr>, Box<Expr>)
 //! }
 //!
-//! fn expr<I>(input: State<I>) -> ParseResult<Expr, I>
+//! fn expr<I>(input: I) -> ParseResult<Expr, I>
 //!     where I: Stream<Item=char>
 //! {
 //!     let word = many1(letter());
@@ -115,7 +118,7 @@
 //!         .or(array.map(Expr::Array))
 //!         .or(pair)
 //!         .skip(spaces())
-//!         .parse_state(input)
+//!         .parse_stream(input)
 //! }
 //!
 //! fn main() {
@@ -132,15 +135,13 @@
 //! ```
 
 #[doc(inline)]
-pub use primitives::{Parser, ParseError, ParseResult, State, from_iter};
-#[doc(inline)]
-pub use char::{char, digit, space, spaces, newline, crlf, tab, upper, lower, letter, alpha_num,
-               hex_digit, oct_digit, string};
+pub use primitives::{Parser, ParseError, ConsumedResult, ParseResult, State, from_iter, Stream,
+                     StreamOnce};
 #[doc(inline)]
 pub use combinator::{any, between, chainl1, chainr1, choice, eof, env_parser, many, many1,
-                     optional, parser, satisfy, sep_by, sep_by1, sep_end_by, sep_end_by1,
-                     skip_many, skip_many1, token, try, look_ahead, value, unexpected,
-                     not_followed_by, ParserExt};
+                     optional, parser, satisfy, satisfy_map, sep_by, sep_by1, sep_end_by,
+                     sep_end_by1, skip_many, skip_many1, token, try, look_ahead, value,
+                     unexpected, not_followed_by};
 
 macro_rules! static_fn {
     (($($arg: pat, $arg_ty: ty),*) -> $ret: ty { $body: expr }) => { {
@@ -150,25 +151,54 @@ macro_rules! static_fn {
     } }
 }
 
+macro_rules! impl_token_parser {
+    ($name: ident($($ty_var: ident),*), $ty: ty, $inner_type: ty) => {
+    #[derive(Clone)]
+    pub struct $name<I $(,$ty_var)*>($inner_type, PhantomData<fn (I) -> I>)
+        where I: Stream<Item=$ty> $(, $ty_var : Parser<Input=I>)*;
+    impl <I $(,$ty_var)*> Parser for $name<I $(,$ty_var)*>
+        where I: Stream<Item=$ty> $(, $ty_var : Parser<Input=I>)* {
+        type Input = I;
+        type Output = <$inner_type as Parser>::Output;
+        #[inline]
+        fn parse_lazy(&mut self,
+                      input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+            self.0.parse_lazy(input)
+        }
+        fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+            self.0.add_error(errors)
+        }
+    }
+}
+}
+
 /// Module containing the primitive types which is used to create and compose more advanced parsers
+#[macro_use]
 pub mod primitives;
 /// Module containing all specific parsers
 pub mod combinator;
-/// Module containg parsers specialized on character streams
+/// Module containing zero-copy parsers
+pub mod range;
+/// Module containing parsers specialized on byte streams
+pub mod byte;
+/// Module containing parsers specialized on character streams
 pub mod char;
 
+
+
 #[cfg(test)]
 mod tests {
     use super::*;
-    use super::primitives::{SourcePosition, Stream, Error, Consumed};
+    use super::primitives::{SourcePosition, Error, Consumed};
+    use char::{alpha_num, char, digit, letter, spaces, string};
 
 
-    fn integer<'a, I>(input: State<I>) -> ParseResult<i64, I>
+    fn integer<'a, I>(input: I) -> ParseResult<i64, I>
         where I: Stream<Item = char>
     {
         let (s, input) = try!(many1::<String, _>(digit())
-                                  .expected("integer")
-                                  .parse_state(input));
+            .expected("integer")
+            .parse_stream(input));
         let mut n = 0;
         for c in s.chars() {
             n = n * 10 + (c as i64 - '0' as i64);
@@ -190,17 +220,17 @@ mod tests {
     #[test]
     fn iterator() {
         let result = parser(integer)
-                         .parse(from_iter("123".chars()))
-                         .map(|(i, input)| (i, input.uncons().err().map(|_| ())));
-        assert_eq!(result, Ok((123i64, Some(()))));
+            .parse(from_iter("123".chars()))
+            .map(|(i, mut input)| (i, input.uncons().is_err()));
+        assert_eq!(result, Ok((123i64, true)));
     }
     #[test]
     fn field() {
         let word = || many(alpha_num());
         let spaces = spaces();
         let c_decl = (word(), spaces.clone(), char(':'), spaces, word())
-                         .map(|t| (t.0, t.4))
-                         .parse("x: int");
+            .map(|t| (t.0, t.4))
+            .parse("x: int");
         assert_eq!(c_decl, Ok((("x".to_string(), "int".to_string()), "")));
     }
     #[test]
@@ -209,8 +239,8 @@ mod tests {
 123
 ";
         let result = (spaces(), parser(integer), spaces())
-                         .map(|t| t.1)
-                         .parse_state(State::new(source));
+            .map(|t| t.1)
+            .parse_stream(State::new(source));
         let state = Consumed::Consumed(State {
             position: SourcePosition {
                 line: 3,
@@ -231,19 +261,21 @@ mod tests {
     }
 
     #[allow(unconditional_recursion)]
-    fn expr(input: State<&str>) -> ParseResult<Expr, &str> {
+    fn expr<I>(input: I) -> ParseResult<Expr, I>
+        where I: Stream<Item = char>
+    {
         let word = many1(letter()).expected("identifier");
         let integer = parser(integer);
         let array = between(char('['), char(']'), sep_by(parser(expr), char(','))).expected("[");
         let paren_expr = between(char('('), char(')'), parser(term)).expected("(");
         let spaces = spaces();
         spaces.clone()
-              .with(word.map(Expr::Id)
-                        .or(integer.map(Expr::Int))
-                        .or(array.map(Expr::Array))
-                        .or(paren_expr))
-              .skip(spaces)
-              .parse_state(input)
+            .with(word.map(Expr::Id)
+                .or(integer.map(Expr::Int))
+                .or(array.map(Expr::Array))
+                .or(paren_expr))
+            .skip(spaces)
+            .parse_stream(input)
     }
 
     #[test]
@@ -260,7 +292,7 @@ mod tests {
         let input = r"
 ,123
 ";
-        let result = parser(expr).parse(input);
+        let result = parser(expr).parse(State::new(input));
         let err = ParseError {
             position: SourcePosition {
                 line: 2,
@@ -277,21 +309,9 @@ mod tests {
         assert_eq!(result, Err(err));
     }
 
-    #[test]
-    fn expression_error_message() {
-        let input = r"
-,123
-";
-        let result = parser(expr).parse(input);
-        let m = format!("{}", result.unwrap_err());
-        let expected = r"Parse error at line: 2, column: 1
-Unexpected ','
-Expected 'integer', 'identifier', '[' or '('
-";
-        assert_eq!(m, expected);
-    }
-
-    fn term(input: State<&str>) -> ParseResult<Expr, &str> {
+    fn term<I>(input: I) -> ParseResult<Expr, I>
+        where I: Stream<Item = char>
+    {
         fn times(l: Expr, r: Expr) -> Expr {
             Expr::Times(Box::new(l), Box::new(r))
         }
@@ -301,7 +321,7 @@ Expected 'integer', 'identifier', '[' or '('
         let mul = char('*').map(|_| times);
         let add = char('+').map(|_| plus);
         let factor = chainl1(parser(expr), mul);
-        chainl1(factor, add).parse_state(input)
+        chainl1(factor, add).parse_stream(input)
     }
 
     #[test]
@@ -310,8 +330,8 @@ Expected 'integer', 'identifier', '[' or '('
 1 * 2 + 3 * test
 ";
         let (result, _) = parser(term)
-                              .parse(input)
-                              .unwrap();
+            .parse(State::new(input))
+            .unwrap();
 
         let e1 = Expr::Times(Box::new(Expr::Int(1)), Box::new(Expr::Int(2)));
         let e2 = Expr::Times(Box::new(Expr::Int(3)),
@@ -320,12 +340,12 @@ Expected 'integer', 'identifier', '[' or '('
     }
 
 
-    fn follow(input: State<&str>) -> ParseResult<(), &str> {
+    fn follow(input: State<&str>) -> ParseResult<(), State<&str>> {
         match input.clone().uncons() {
-            Ok((c, _)) => {
+            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)))
                 } else {
                     Ok(((), Consumed::Empty(input)))
                 }
@@ -336,10 +356,10 @@ Expected 'integer', 'identifier', '[' or '('
     #[test]
     fn error_position() {
         let mut p = string("let")
-                        .skip(parser(follow))
-                        .map(|x| x.to_string())
-                        .or(many1(digit()));
-        match p.parse("le123") {
+            .skip(parser(follow))
+            .map(|x| x.to_string())
+            .or(many1(digit()));
+        match p.parse(State::new("le123")) {
             Ok(_) => assert!(false),
             Err(err) => {
                 assert_eq!(err.position,
@@ -349,7 +369,7 @@ Expected 'integer', 'identifier', '[' or '('
                            })
             }
         }
-        match p.parse("let1") {
+        match p.parse(State::new("let1")) {
             Ok(_) => assert!(false),
             Err(err) => {
                 assert_eq!(err.position,
@@ -364,9 +384,9 @@ Expected 'integer', 'identifier', '[' or '('
     #[test]
     fn sep_by_error_consume() {
         let mut p = sep_by::<Vec<_>, _, _>(string("abc"), char(','));
-        let err = p.parse("ab,abc")
-                   .map(|x| format!("{:?}", x))
-                   .unwrap_err();
+        let err = p.parse(State::new("ab,abc"))
+            .map(|x| format!("{:?}", x))
+            .unwrap_err();
         assert_eq!(err.position,
                    SourcePosition {
                        line: 1,
@@ -377,9 +397,9 @@ Expected 'integer', 'identifier', '[' or '('
     #[test]
     fn optional_error_consume() {
         let mut p = optional(string("abc"));
-        let err = p.parse("ab")
-                   .map(|x| format!("{:?}", x))
-                   .unwrap_err();
+        let err = p.parse(State::new("ab"))
+            .map(|x| format!("{:?}", x))
+            .unwrap_err();
         assert_eq!(err.position,
                    SourcePosition {
                        line: 1,
@@ -398,10 +418,10 @@ Expected 'integer', 'identifier', '[' or '('
     #[test]
     fn inner_error_consume() {
         let mut p = many::<Vec<_>, _>(between(char('['), char(']'), digit()));
-        let result = p.parse("[1][2][]");
+        let result = p.parse(State::new("[1][2][]"));
         assert!(result.is_err(), format!("{:?}", result));
         let error = result.map(|x| format!("{:?}", x))
-                          .unwrap_err();
+            .unwrap_err();
         assert_eq!(error.position,
                    SourcePosition {
                        line: 1,
@@ -455,8 +475,8 @@ Expected 'integer', 'identifier', '[' or '('
             }
         }
         let result: Result<((), _), ParseError<&str>> = string("abc")
-                                                            .and_then(|_| Err(Error))
-                                                            .parse("abc");
+            .and_then(|_| Err(Error))
+            .parse("abc");
         assert!(result.is_err());
         // Test that ParseError can be coerced to a StdError
         let _ = result.map_err(|err| {
diff --git a/src/primitives.rs b/src/primitives.rs
index 2d27e4db..77b1f2d4 100644
--- a/src/primitives.rs
+++ b/src/primitives.rs
@@ -1,24 +1,39 @@
 use std::fmt;
 use std::error::Error as StdError;
 use std::any::Any;
-#[cfg(feature = "buffered_stream")]
 use std::cell::UnsafeCell;
-#[cfg(feature = "buffered_stream")]
 use std::collections::VecDeque;
 
-///Struct which represents a position in a source file
+use self::FastResult::*;
+
+use combinator::{AndThen, and_then, Expected, expected, FlatMap, flat_map, Iter, Map, map,
+                 Message, message, Or, or, Skip, skip, Then, then, With, with};
+
+#[macro_export]
+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()),
+        }
+    }
+}
+
+/// 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
+    /// Current line of the input
     pub line: i32,
-    ///Current column of the input
+    /// Current column of the input
     pub column: i32,
 }
 
-///Struct which represents a position in a byte stream
+/// Struct which represents a position in a byte stream
 #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
 pub struct BytePosition {
-    ///Current position
+    /// Current position
     pub position: usize,
 }
 
@@ -28,10 +43,10 @@ impl fmt::Display for BytePosition {
     }
 }
 
-///Enum holding error information
-///As there is implementations of `From` for `T: Positioner`, `String` and `&'static str` the
-///constructor need not be used directly as calling `msg.into()` should turn a message into the
-///correct `Info` variant
+/// Enum holding error information
+/// As there is implementations of `From` for `T: Positioner`, `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)]
 pub enum Info<T, R> {
     Token(T),
@@ -81,17 +96,17 @@ impl<T, R> From<&'static str> for Info<T, R> {
     }
 }
 
-///Enum used to store information about an error that has occured
+/// Enum used to store information about an error that has occured
 #[derive(Debug)]
 pub enum Error<T, R> {
-    ///Error indicating an unexpected token has been encountered in the stream
+    /// Error indicating an unexpected token has been encountered in the stream
     Unexpected(Info<T, R>),
-    ///Error indicating that the parser expected something else
+    /// Error indicating that the parser expected something else
     Expected(Info<T, R>),
-    ///Generic message
+    /// Generic message
     Message(Info<T, R>),
-    ///Variant for containing other types of errors
-    Other(Box<StdError + Send>),
+    /// Variant for containing other types of errors
+    Other(Box<StdError + Send + Sync>),
 }
 
 impl<T: PartialEq, R: PartialEq> PartialEq for Error<T, R> {
@@ -106,7 +121,7 @@ impl<T: PartialEq, R: PartialEq> PartialEq for Error<T, R> {
 }
 
 impl<E, T, R> From<E> for Error<T, R>
-    where E: StdError + 'static + Send
+    where E: StdError + 'static + Send + Sync
 {
     fn from(e: E) -> Error<T, R> {
         Error::Other(Box::new(e))
@@ -114,22 +129,113 @@ impl<E, T, R> From<E> for Error<T, R>
 }
 
 impl<T, R> Error<T, R> {
+    /// Returns the `end_of_input` error
     pub fn end_of_input() -> Error<T, R> {
         Error::Unexpected("end of input".into())
     }
+
+    /// Formats a slice of errors in a human readable way
+    ///
+    /// ```rust
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::*;
+    ///
+    /// # fn main() {
+    /// let input = r"
+    ///   ,123
+    /// ";
+    /// let result = spaces().with(char('.').or(char('a')).or(digit()))
+    ///     .parse(State::new(input));
+    /// let m = format!("{}", result.unwrap_err());
+    /// let expected = r"Parse error at line: 2, column: 3
+    /// Unexpected `,`
+    /// Expected `.`, `a` or `digit`
+    /// ";
+    /// assert_eq!(m, expected);
+    /// # }
+    /// ```
+    pub fn fmt_errors(errors: &[Error<T, R>], f: &mut fmt::Formatter) -> fmt::Result
+        where T: fmt::Display,
+              R: fmt::Display
+    {
+        // First print the token that we did not expect
+        // There should really just be one unexpected message at this point though we print them
+        // all to be safe
+        let unexpected = errors.iter()
+            .filter(|e| {
+                match **e {
+                    Error::Unexpected(_) => true,
+                    _ => false,
+                }
+            });
+        for error in unexpected {
+            try!(writeln!(f, "{}", error));
+        }
+
+        // Then we print out all the things that were expected in a comma separated list
+        // 'Expected 'a', 'expression' or 'let'
+        let iter = || {
+            errors.iter()
+                .filter_map(|e| {
+                    match *e {
+                        Error::Expected(ref err) => Some(err),
+                        _ => None,
+                    }
+                })
+        };
+        let expected_count = iter().count();
+        for (i, message) in iter().enumerate() {
+            let s = match i {
+                0 => "Expected",
+                _ if i < expected_count - 1 => ",",
+                // Last expected message to be written
+                _ => " or",
+            };
+            try!(write!(f, "{} `{}`", s, message));
+        }
+        if expected_count != 0 {
+            try!(writeln!(f, ""));
+        }
+        // If there are any generic messages we print them out last
+        let messages = errors.iter()
+            .filter(|e| {
+                match **e {
+                    Error::Message(_) |
+                    Error::Other(_) => true,
+                    _ => false,
+                }
+            });
+        for error in messages {
+            try!(writeln!(f, "{}", error));
+        }
+        Ok(())
+    }
 }
 
-///Enum used to indicate if a parser consumed any items of the stream it was given as an input
+/// Enum used to indicate if a parser consumed any items of the stream it was given as an input
 #[derive(Clone, PartialEq, Debug, Copy)]
 pub enum Consumed<T> {
-    ///Constructor indicating that the parser has consumed elements
+    /// Constructor indicating that the parser has consumed elements
     Consumed(T),
-    ///Constructor indicating that the parser did not consume any elements
+    /// Constructor indicating that the parser did not consume any elements
     Empty(T),
 }
 
 impl<T> Consumed<T> {
-    ///Returns true if `self` is empty
+    pub fn as_mut(&mut self) -> &mut T {
+        match *self {
+            Consumed::Empty(ref mut t) => t,
+            Consumed::Consumed(ref mut t) => t,
+        }
+    }
+    pub fn as_ref(&self) -> &T {
+        match *self {
+            Consumed::Empty(ref t) => t,
+            Consumed::Consumed(ref t) => t,
+        }
+    }
+    /// Returns true if `self` is empty
     pub fn is_empty(&self) -> bool {
         match *self {
             Consumed::Empty(_) => true,
@@ -137,7 +243,7 @@ impl<T> Consumed<T> {
         }
     }
 
-    ///Extracts the contained value
+    /// Extracts the contained value
     pub fn into_inner(self) -> T {
         match self {
             Consumed::Empty(x) => x,
@@ -145,17 +251,17 @@ impl<T> Consumed<T> {
         }
     }
 
-    ///Converts `self` into the Consumed state
+    /// Converts `self` into the Consumed state
     pub fn as_consumed(self) -> Consumed<T> {
         Consumed::Consumed(self.into_inner())
     }
 
-    ///Converts `self` into theEmpty state
+    /// Converts `self` into theEmpty state
     pub fn as_empty(self) -> Consumed<T> {
         Consumed::Empty(self.into_inner())
     }
 
-    ///Maps over the contained value without changing the consumed state
+    /// Maps over the contained value without changing the consumed state
     pub fn map<F, U>(self, f: F) -> Consumed<U>
         where F: FnOnce(T) -> U
     {
@@ -172,16 +278,16 @@ impl<T> Consumed<T> {
         }
     }
 
-    ///Combines the Consumed flags from `self` and the result of `f`
+    /// Combines the Consumed flags from `self` and the result of `f`
     ///
-    ///```
+    /// ```
     /// # extern crate combine as pc;
     /// # use pc::*;
     /// # fn main() {
     /// //Parses a character of string literal and handles the escaped characters \\ and \" as \
     /// //and " respectively
-    /// fn char(input: State<&str>) -> ParseResult<char, &str> {
-    ///     let (c, input) = try!(satisfy(|c| c != '"').parse_state(input));
+    /// fn char(input: &str) -> ParseResult<char, &str> {
+    ///     let (c, input) = try!(satisfy(|c| c != '"').parse_stream(input));
     ///     match c {
     ///         //Since the `char` parser has already consumed some of the input `combine` is used
     ///         //propagate the consumed state to the next part of the parser
@@ -194,7 +300,7 @@ impl<T> Consumed<T> {
     ///                         c => c
     ///                     }
     ///                 })
-    ///                 .parse_state(input)
+    ///                 .parse_stream(input)
     ///             }),
     ///         _ => Ok((c, input))
     ///     }
@@ -203,10 +309,10 @@ impl<T> Consumed<T> {
     ///     .parse(r#"abc\"\\"#);
     /// assert_eq!(result, Ok((r#"abc"\"#.to_string(), "")));
     /// }
-    ///```
+    /// ```
     pub fn combine<F, U, I>(self, f: F) -> ParseResult<U, I>
         where F: FnOnce(T) -> ParseResult<U, I>,
-              I: Stream
+              I: StreamOnce
     {
         match self {
             Consumed::Consumed(x) => {
@@ -219,50 +325,68 @@ impl<T> Consumed<T> {
             Consumed::Empty(x) => f(x),
         }
     }
+    pub fn combine_consumed<F, U, I>(self, f: F) -> ConsumedResult<U, I>
+        where F: FnOnce(T) -> ConsumedResult<U, I>,
+              I: StreamOnce
+    {
+        use self::FastResult::*;
+        match self {
+            Consumed::Consumed(x) => {
+                match f(x) {
+                    EmptyOk((v, rest)) => ConsumedOk((v, rest)),
+                    EmptyErr(err) => ConsumedErr(err),
+                    y => y,
+                }
+            }
+            Consumed::Empty(x) => f(x),
+        }
+    }
 }
-///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.
-pub struct ParseError<P: Stream> {
-    ///The position where the error occured
-    pub position: <P::Item as Positioner>::Position,
-    ///A vector containing specific information on what errors occured at `position`
-    pub errors: Vec<Error<P::Item, P::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.
+pub struct ParseError<S: StreamOnce> {
+    /// The position where the error occured
+    pub position: S::Position,
+    /// A vector containing specific information on what errors occured at `position`
+    pub errors: Vec<Error<S::Item, S::Range>>,
 }
 
-impl<P: Positioner + Clone, S: Stream<Item = P>> ParseError<S> {
-    pub fn new(position: P::Position, error: Error<S::Item, S::Range>) -> ParseError<S> {
+impl<S: StreamOnce> ParseError<S> {
+    pub fn new(position: S::Position, error: Error<S::Item, S::Range>) -> ParseError<S> {
         ParseError::from_errors(position, vec![error])
     }
 
-    pub fn empty(position: P::Position) -> ParseError<S> {
+    pub fn empty(position: S::Position) -> ParseError<S> {
         ParseError::from_errors(position, vec![])
     }
 
-    pub fn from_errors(position: P::Position, errors: Vec<Error<P, S::Range>>) -> ParseError<S> {
+    pub fn from_errors(position: S::Position,
+                       errors: Vec<Error<S::Item, S::Range>>)
+                       -> ParseError<S> {
         ParseError {
             position: position,
             errors: errors,
         }
     }
 
-    pub fn end_of_input(position: P::Position) -> ParseError<S> {
+    pub fn end_of_input(position: S::Position) -> ParseError<S> {
         ParseError::new(position, Error::end_of_input())
     }
 
     pub fn add_message<M>(&mut self, message: M)
-        where M: Into<Info<P, S::Range>>
+        where M: Into<Info<S::Item, S::Range>>
     {
         self.add_error(Error::Message(message.into()));
     }
 
-    pub fn add_error(&mut self, message: Error<P, S::Range>) {
+    pub fn add_error(&mut self, message: Error<S::Item, S::Range>) {
         // Don't add duplicate errors
         if self.errors.iter().all(|msg| *msg != message) {
             self.errors.push(message);
         }
     }
 
-    pub fn set_expected(&mut self, message: Info<P, S::Range>) {
+    pub fn set_expected(&mut self, message: Info<S::Item, S::Range>) {
         // Remove all other expected messages
         self.errors.retain(|e| {
             match *e {
@@ -293,7 +417,7 @@ impl<S> StdError for ParseError<S>
     where S: Stream,
           S::Range: fmt::Display + fmt::Debug + Any,
           S::Item: fmt::Display + fmt::Debug + Any,
-          <S::Item as Positioner>::Position: fmt::Display + fmt::Debug + Any
+          S::Position: fmt::Display + fmt::Debug + Any
 {
     fn description(&self) -> &str {
         "parse error"
@@ -302,7 +426,7 @@ impl<S> StdError for ParseError<S>
 
 impl<S> PartialEq for ParseError<S>
     where S: Stream,
-          <S::Item as Positioner>::Position: PartialEq
+          S::Position: PartialEq
 {
     fn eq(&self, other: &ParseError<S>) -> bool {
         self.position == other.position && self.errors == other.errors
@@ -313,7 +437,7 @@ impl<S> fmt::Debug for ParseError<S>
     where S: Stream,
           S::Range: fmt::Debug,
           S::Item: fmt::Debug,
-          <S::Item as Positioner>::Position: fmt::Debug
+          S::Position: fmt::Debug
 {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f,
@@ -327,70 +451,14 @@ impl<S> fmt::Display for ParseError<S>
     where S: Stream,
           S::Item: fmt::Display,
           S::Range: fmt::Display,
-          <S::Item as Positioner>::Position: fmt::Display
+          S::Position: fmt::Display
 {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(writeln!(f, "Parse error at {}", self.position));
-
-        // First print the token that we did not expect
-        // There should really just be one unexpected message at this point though we print them
-        // all to be safe
-        let unexpected = self.errors
-                             .iter()
-                             .filter(|e| {
-                                 match **e {
-                                     Error::Unexpected(_) => true,
-                                     _ => false,
-                                 }
-                             });
-        for error in unexpected {
-            try!(writeln!(f, "{}", error));
-        }
-
-        // Then we print out all the things that were expected in a comma separated list
-        // 'Expected 'a', 'expression' or 'let'
-        let iter = || {
-            self.errors
-                .iter()
-                .filter_map(|e| {
-                    match *e {
-                        Error::Expected(ref err) => Some(err),
-                        _ => None,
-                    }
-                })
-        };
-        let expected_count = iter().count();
-        let mut i = 0;
-        for message in iter() {
-            i += 1;
-            if i == 1 {
-                try!(write!(f, "Expected"));
-            } else if i == expected_count {
-                // Last expected message to be written
-                try!(write!(f, " or"));
-            } else {
-                try!(write!(f, ","));
-            }
-            try!(write!(f, " '{}'", message));
-        }
-        if expected_count != 0 {
-            try!(writeln!(f, ""));
-        }
-        // If there are any generic messages we print them out last
-        let messages = self.errors
-                           .iter()
-                           .filter(|e| {
-                               match **e {
-                                   Error::Message(_) | Error::Other(_) => true,
-                                   _ => false,
-                               }
-                           });
-        for error in messages {
-            try!(writeln!(f, "{}", error));
-        }
-        Ok(())
+        Error::fmt_errors(&self.errors, f)
     }
 }
+
 impl fmt::Display for SourcePosition {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "line: {}, column: {}", self.line, self.column)
@@ -399,27 +467,30 @@ impl fmt::Display for SourcePosition {
 impl<T: fmt::Display, R: fmt::Display> fmt::Display for Error<T, R> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match *self {
-            Error::Unexpected(ref c) => write!(f, "Unexpected '{}'", c),
-            Error::Expected(ref s) => write!(f, "Expected {}", s),
+            Error::Unexpected(ref c) => write!(f, "Unexpected `{}`", c),
+            Error::Expected(ref s) => write!(f, "Expected `{}`", s),
             Error::Message(ref msg) => msg.fmt(f),
             Error::Other(ref err) => err.fmt(f),
         }
     }
 }
 
-///The `State<I>` struct keeps track of the current position in the stream `I`
+/// 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
+    where I: Stream,
+          I::Item: Positioner
 {
-    ///The current position
+    /// The current position
     pub position: <I::Item as Positioner>::Position,
-    ///The input stream used when items are requested
+    /// 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 {
@@ -430,163 +501,177 @@ impl<I> fmt::Debug for State<I>
     }
 }
 
-impl<I: Stream> State<I> {
-    ///Creates a new `State<I>` from an input stream. Initializes the position to
-    ///`Positioner::start()`
+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,
         }
     }
+}
 
-    ///`uncons` is the most general way of extracting and item from a stream
-    ///It takes a function `f` as argument which should update the position
-    ///according to the item that was extracted
-    ///Usually you want to use `uncons_char` instead which works directly on character streams
-    pub fn uncons(self) -> ParseResult<I::Item, I> {
-        let State { mut position, input, .. } = self;
-        match input.uncons() {
-            Ok((c, input)) => {
-                c.update(&mut position);
-                Ok((c,
-                    Consumed::Consumed(State {
-                    position: position,
-                    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(Consumed::Empty(ParseError::new(position, err))),
+            Err(err) => Err(err),
         }
     }
 
-    ///Updates the `position` and `input` to be as if `item` was removed and `rest` is
-    ///the remaining input
-    pub fn update(mut self, item: I::Item, rest: I) -> ParseResult<I::Item, I> {
-        item.update(&mut self.position);
-        self.input = rest;
-        Ok((item, Consumed::Consumed(self)))
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.position.clone()
     }
 }
 
-impl<I, E> State<I>
+impl<I, E> RangeStream for State<I>
     where I: RangeStream<Item = E>,
           I::Range: Range + Positioner<Position = E::Position>,
           E: Positioner + Clone
 {
-    ///Removes `size` items from the input returning them as a range.
-    ///Fails if there are fewer items than `size`
-    pub fn uncons_range(self, size: usize) -> ParseResult<I::Range, I> {
-        let State { mut position, input, .. } = self;
-        let result = input.uncons_range(size);
-        match result {
-            Ok((value, input)) => {
-                value.update(&mut position);
-                let state = State {
-                    position: position,
-                    input: input,
-                };
-                let state = if value.len() == 0 {
-                    Consumed::Empty(state)
-                } else {
-                    Consumed::Consumed(state)
-                };
-                Ok((value, state))
-            }
-            Err(err) => Err(Consumed::Empty(ParseError::new(position, err))),
-        }
-    }
-}
-
-impl<I> State<I>
-    where I: RangeStream,
-          I::Range: Range
-{
-    ///Removes items from the input while `predicate` returns `true`.
-    pub fn uncons_while<F>(self, mut predicate: F) -> ParseResult<I::Range, I>
+    #[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 State { mut position, input, .. } = self;
-        let result = input.uncons_while(|t| {
+        let position = &mut self.position;
+        self.input.uncons_while(|t| {
             if predicate(t.clone()) {
-                t.update(&mut position);
+                t.update(position);
                 true
             } else {
                 false
             }
-        });
-        match result {
-            Ok((value, input)) => {
-                let state = State {
-                    position: position,
-                    input: input,
-                };
-                let state = if value.len() == 0 {
-                    Consumed::Empty(state)
-                } else {
-                    Consumed::Consumed(state)
-                };
-                Ok((value, state))
-            }
-            Err(err) => Err(Consumed::Empty(ParseError::new(position, err))),
-        }
+        })
     }
 }
 
-///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<State<I>>), Consumed<ParseError<I>>>;
+/// 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>>>;
+
+/// `StreamOnce` represents a sequence of items that can be extracted one by one.
+pub trait StreamOnce {
+    /// The type of items which is yielded from this stream
+    type Item: Clone + PartialEq;
+
+    /// The type of a range of items yielded from this stream.
+    /// Types which do not a have a way of yielding ranges of items should just use the
+    /// 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>>;
 
-///A stream is a sequence of items that can be extracted one by one
-pub trait Stream : Clone {
-    ///The type of items which is yielded from this stream
-    type Item: Positioner + Clone;
-    ///The type of a range of items yielded from this stream.
-    ///Types which do not a have a way of yielding ranges of items should just use the
-    ///Self::Item for this type
-    type Range: Positioner + Clone;
-    ///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(self) -> Result<(Self::Item, Self), 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 {}
+
+impl<I> Stream for I where I: StreamOnce + Clone {}
+
+#[inline]
+pub fn uncons<I>(mut input: I) -> ParseResult<I::Item, I>
+    where I: Stream
+{
+    let position = input.position();
+    let x = try!(input.uncons().map_err(|err| Consumed::Empty(ParseError::new(position, err))));
+    Ok((x, Consumed::Consumed(input)))
 }
 
 /// A `RangeStream` is an extension of Stream which allows for zero copy parsing
-pub trait RangeStream: Stream + Positioner {
-    ///Takes `size` elements from the stream
-    ///Fails if the length of the stream is less than `size`.
-    fn uncons_range(self,
-                    size: usize)
-                    -> Result<(Self::Range, Self), Error<Self::Item, Self::Range>>;
-
-    ///Takes items from stream, testing each one with `predicate`
-    ///returns the range of items which passed `predicate`
-    fn uncons_while<F>(self, f: F) -> Result<(Self::Range, Self), Error<Self::Item, Self::Range>>
+pub trait RangeStream: Stream {
+    /// Takes `size` elements from the stream
+    /// Fails if the length of the stream is less than `size`.
+    fn uncons_range(&mut self, size: usize) -> Result<Self::Range, Error<Self::Item, Self::Range>>;
+
+    /// Takes items from stream, testing each one with `predicate`
+    /// returns the range of items which passed `predicate`
+    fn uncons_while<F>(&mut self, f: F) -> Result<Self::Range, Error<Self::Item, Self::Range>>
         where F: FnMut(Self::Item) -> bool;
 }
 
+/// Removes items from the input while `predicate` returns `true`.
+#[inline]
+pub fn uncons_while<I, F>(mut input: I, predicate: F) -> ConsumedResult<I::Range, I>
+    where F: FnMut(I::Item) -> bool,
+          I: RangeStream,
+          I::Range: Range
+{
+    match input.uncons_while(predicate) {
+        Err(err) => EmptyErr(ParseError::new(input.position(), err)),
+        Ok(x) => {
+            if x.len() == 0 {
+                EmptyOk((x, input))
+            } else {
+                ConsumedOk((x, input))
+            }
+        }
+    }
+}
+
 pub trait Range {
-    ///Returns the remaining length of `self`.
-    ///The returned length need not be the same as the number of items left in the stream
+    /// Returns the remaining length of `self`.
+    /// The returned length need not be the same as the number of items left in the stream
     fn len(&self) -> usize;
 }
 
 impl<'a> RangeStream for &'a str {
-    fn uncons_while<F>(self, mut f: F) -> Result<(&'a str, &'a str), Error<char, &'a str>>
+    #[inline]
+    fn uncons_while<F>(&mut self, mut f: F) -> Result<&'a str, Error<char, &'a str>>
         where F: FnMut(Self::Item) -> bool
     {
         let mut chars = self.chars();
-        let mut last_char_len = 0;
-        for c in chars.by_ref() {
+        while let Some(c) = chars.next() {
             if !f(c) {
-                last_char_len = c.len_utf8();
-                break;
+                let len = self.len() - chars.as_str().len() - c.len_utf8();
+                let (result, rest) = self.split_at(len);
+                *self = rest;
+                return Ok(result);
             }
         }
-        let len = self.len() - chars.as_str().len() - last_char_len;
-        Ok(self.split_at(len))
+        let result = *self;
+        *self = &self[self.len()..];
+        Ok(result)
     }
-    fn uncons_range(self, size: usize) -> Result<(&'a str, &'a str), Error<char, &'a str>> {
+
+    #[inline]
+    fn uncons_range(&mut self, size: usize) -> Result<&'a str, Error<char, &'a str>> {
         fn is_char_boundary(s: &str, index: usize) -> bool {
             if index == s.len() {
                 return true;
@@ -596,9 +681,11 @@ impl<'a> RangeStream for &'a str {
                 Some(&b) => b < 128 || b >= 192,
             }
         }
-        if size < self.len() {
+        if size <= self.len() {
             if is_char_boundary(self, size) {
-                Ok(self.split_at(size))
+                let (result, remaining) = self.split_at(size);
+                *self = remaining;
+                Ok(result)
             } else {
                 Err(Error::Message("uncons_range on non character boundary".into()))
             }
@@ -609,63 +696,93 @@ impl<'a> RangeStream for &'a str {
 }
 
 impl<'a> Range for &'a str {
+    #[inline]
     fn len(&self) -> usize {
         str::len(self)
     }
 }
 
 impl<'a, T> Range for &'a [T] {
+    #[inline]
     fn len(&self) -> usize {
         <[T]>::len(self)
     }
 }
 
 impl<'a, T> RangeStream for &'a [T]
-    where T: Positioner + Copy
+    where T: Copy + PartialEq
 {
-    fn uncons_range(self, size: usize) -> Result<(&'a [T], &'a [T]), Error<T, &'a [T]>> {
-        if size < self.len() {
-            Ok(self.split_at(size))
+    #[inline]
+    fn uncons_range(&mut self, size: usize) -> Result<&'a [T], Error<T, &'a [T]>> {
+        if size <= self.len() {
+            let (result, remaining) = self.split_at(size);
+            *self = remaining;
+            Ok(result)
         } else {
             Err(Error::end_of_input())
         }
     }
-    fn uncons_while<F>(self, mut f: F) -> Result<(&'a [T], &'a [T]), Error<T, &'a [T]>>
+    #[inline]
+    fn uncons_while<F>(&mut self, mut f: F) -> Result<&'a [T], Error<T, &'a [T]>>
         where F: FnMut(Self::Item) -> bool
     {
         let len = self.iter()
-                      .take_while(|c| f(**c))
-                      .count();
-        Ok(self.split_at(len))
+            .take_while(|c| f(**c))
+            .count();
+        let (result, remaining) = self.split_at(len);
+        *self = remaining;
+        Ok(result)
     }
 }
 
-impl<'a> Stream for &'a str {
+impl<'a> StreamOnce for &'a str {
     type Item = char;
     type Range = &'a str;
-    fn uncons(self) -> Result<(char, &'a str), Error<char, &'a str>> {
+    type Position = usize;
+
+    #[inline]
+    fn uncons(&mut self) -> Result<char, Error<char, &'a str>> {
         let mut chars = self.chars();
         match chars.next() {
-            Some(c) => Ok((c, chars.as_str())),
+            Some(c) => {
+                *self = chars.as_str();
+                Ok(c)
+            }
             None => Err(Error::end_of_input()),
         }
     }
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.as_bytes().as_ptr() as usize
+    }
 }
 
-impl<'a, T> Stream for &'a [T]
-    where T: Positioner + Copy
+impl<'a, T> StreamOnce for &'a [T]
+    where T: Copy + PartialEq
 {
     type Item = T;
     type Range = &'a [T];
-    fn uncons(self) -> Result<(T, &'a [T]), Error<T, &'a [T]>> {
+    type Position = usize;
+
+    #[inline]
+    fn uncons(&mut self) -> Result<T, Error<T, &'a [T]>> {
         match self.split_first() {
-            Some((first, rest)) => Ok((*first, rest)),
+            Some((first, rest)) => {
+                *self = rest;
+                Ok(*first)
+            }
             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
+/// Newtype for constructing a stream from a slice where the items in the slice are not copyable
 #[derive(Copy, Eq, PartialEq, Ord, PartialOrd, Debug)]
 pub struct SliceStream<'a, T: 'a>(pub &'a [T]);
 
@@ -675,82 +792,117 @@ impl<'a, T> Clone for SliceStream<'a, T> {
     }
 }
 
-impl<'a, T> Stream for SliceStream<'a, T>
-    where T: Positioner + 'a
+impl<'a, T> StreamOnce for SliceStream<'a, T>
+    where T: Clone + PartialEq + 'a
 {
     type Item = &'a T;
     type Range = &'a [T];
-    fn uncons(self) -> Result<(&'a T, SliceStream<'a, T>), Error<&'a T, &'a [T]>> {
+    type Position = usize;
+
+    #[inline]
+    fn uncons(&mut self) -> Result<&'a T, Error<&'a T, &'a [T]>> {
         match self.0.split_first() {
-            Some((first, rest)) => Ok((first, SliceStream(rest))),
+            Some((first, rest)) => {
+                self.0 = rest;
+                Ok(first)
+            }
             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>
-    where T: Positioner + 'a
+    where T: Clone + PartialEq + 'a
 {
-    fn uncons_range(self,
-                    size: usize)
-                    -> Result<(&'a [T], SliceStream<'a, T>), Error<&'a T, &'a [T]>> {
-        if size < self.0.len() {
+    #[inline]
+    fn uncons_range(&mut self, size: usize) -> Result<&'a [T], Error<&'a T, &'a [T]>> {
+        if size <= self.0.len() {
             let (range, rest) = self.0.split_at(size);
-            Ok((range, SliceStream(rest)))
+            self.0 = rest;
+            Ok(range)
         } else {
             Err(Error::end_of_input())
         }
     }
 
-    fn uncons_while<F>(self,
-                       mut f: F)
-                       -> Result<(&'a [T], SliceStream<'a, T>), Error<&'a T, &'a [T]>>
+    #[inline]
+    fn uncons_while<F>(&mut self, mut f: F) -> Result<&'a [T], Error<&'a T, &'a [T]>>
         where F: FnMut(Self::Item) -> bool
     {
         let len = self.0
-                      .iter()
-                      .take_while(|c| f(*c))
-                      .count();
+            .iter()
+            .take_while(|c| f(*c))
+            .count();
         let (range, rest) = self.0.split_at(len);
-        Ok((range, SliceStream(rest)))
+        self.0 = rest;
+        Ok(range)
     }
 }
 
-///Wrapper around iterators which allows them to be treated as a stream.
-///Returned by `from_iter`.
+/// Wrapper around iterators which allows them to be treated as a stream.
+/// Returned by `from_iter`.
 #[derive(Clone, Debug)]
-pub struct IteratorStream<I>(I) where I: Iterator + Clone;
+pub struct IteratorStream<I>(I, usize) where I: Iterator;
 
 
-///Converts an `Iterator` into a stream.
+/// Converts an `Iterator` into a stream.
 pub fn from_iter<I>(iter: I) -> IteratorStream<I>
-    where I: Iterator + Clone
+    where I: Iterator
 {
-    IteratorStream(iter)
+    IteratorStream(iter, 0)
 }
 
-impl<I: Iterator + Clone> Stream for IteratorStream<I>
-    where I::Item: Positioner + Clone
+impl<I> Iterator for IteratorStream<I>
+    where I: Iterator
 {
     type Item = I::Item;
-    type Range = I::Item;
-    fn uncons(mut self) -> Result<(I::Item, Self), Error<I::Item, I::Item>> {
+    fn next(&mut self) -> Option<I::Item> {
         match self.0.next() {
-            Some(x) => Ok((x, self)),
+            Some(x) => {
+                self.1 += 1;
+                Some(x)
+            }
+            None => None,
+        }
+    }
+}
+
+impl<I: Iterator> StreamOnce for IteratorStream<I>
+    where I::Item: Clone + PartialEq
+{
+    type Item = I::Item;
+    type Range = I::Item;
+    type Position = usize;
+
+    #[inline]
+    fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Item>> {
+        match self.next() {
+            Some(x) => Ok(x),
             None => Err(Error::end_of_input()),
         }
     }
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.1
+    }
 }
 
-///Trait for updating the position for types which can be yielded from a `Stream`.
+/// 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.
+    /// The type which keeps track of the position.
     type Position: Clone + Ord;
-    ///Creates a start position
+    /// Creates a start position
     fn start() -> Self::Position;
-    ///Updates the position given that `self` has been taken from the stream
+    /// 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
 {
@@ -762,6 +914,7 @@ impl<'a, T: ?Sized> Positioner for &'a T
         (*self).update(position)
     }
 }
+
 impl<T> Positioner for [T]
     where T: Positioner
 {
@@ -831,36 +984,141 @@ impl Positioner for u8 {
     }
 }
 
-///By implementing the `Parser` trait a type says that it can be used to parse an input stream into
-///the type `Output`.
+#[derive(Clone, PartialEq, Debug, Copy)]
+pub enum FastResult<T, E> {
+    ConsumedOk(T),
+    EmptyOk(T),
+    ConsumedErr(E),
+    EmptyErr(E),
+}
+
+impl<T, E> FastResult<T, E> {
+    pub fn as_ref(&self) -> FastResult<&T, &E> {
+        match *self {
+            ConsumedOk(ref t) => ConsumedOk(t),
+            EmptyOk(ref t) => EmptyOk(t),
+            ConsumedErr(ref e) => ConsumedErr(e),
+            EmptyErr(ref e) => EmptyErr(e),
+        }
+    }
+
+    pub fn and_then<F, T2>(self, f: F) -> F::Output
+        where F: FnOnce(T) -> FastResult<T2, E>
+    {
+        match self {
+            ConsumedOk(t) => {
+                match f(t) {
+                    ConsumedOk(t2) | EmptyOk(t2) => ConsumedOk(t2),
+                    EmptyErr(e) | ConsumedErr(e) => ConsumedErr(e),
+                }
+            }
+            EmptyOk(t) => f(t),
+            ConsumedErr(e) => ConsumedErr(e),
+            EmptyErr(e) => EmptyErr(e),
+        }
+    }
+}
+
+impl<T, E> ConsumedResult<T, E>
+    where E: StreamOnce
+{
+    pub fn map<F, T2>(self, f: F) -> ConsumedResult<F::Output, E>
+        where F: FnOnce(T) -> T2
+    {
+        match self {
+            ConsumedOk((t, i)) => ConsumedOk((f(t), i)),
+            EmptyOk((t, i)) => EmptyOk((f(t), i)),
+            ConsumedErr(e) => ConsumedErr(e),
+            EmptyErr(e) => EmptyErr(e),
+        }
+    }
+}
+
+
+/// 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>>;
+
+impl<T, E> Into<Result<Consumed<T>, Consumed<E>>> for FastResult<T, E> {
+    fn into(self) -> Result<Consumed<T>, Consumed<E>> {
+        match self {
+            ConsumedOk(t) => Ok(Consumed::Consumed(t)),
+            EmptyOk(t) => Ok(Consumed::Empty(t)), 
+            ConsumedErr(e) => Err(Consumed::Consumed(e)),
+            EmptyErr(e) => Err(Consumed::Empty(e)),
+        }
+    }
+}
+
+impl<O, I> Into<ParseResult<O, I>> for ConsumedResult<O, I>
+    where I: StreamOnce
+{
+    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)),
+            EmptyErr(e) => Err(Consumed::Empty(e)),
+        }
+    }
+}
+
+impl<O, I> From<ParseResult<O, I>> for ConsumedResult<O, I>
+    where I: StreamOnce
+{
+    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::Empty(e)) => EmptyErr(e),
+        }
+    }
+}
+
+/// By implementing the `Parser` trait a type says that it can be used to parse an input stream into
+/// the type `Output`.
 ///
-///All methods have a default implementation but there needs to be at least an implementation of
-///`parse_state` or`parse_lazy`. If `parse_lazy` is implemented an implementation of `add_error` is
-///also recommended to improve error reporting.
+/// All methods have a default implementation but there needs to be at least an implementation of
+/// `parse_stream` or`parse_lazy`. If `parse_lazy` is implemented an implementation of `add_error` is
+/// also recommended to improve error reporting.
 pub trait Parser {
-    ///The type which is take as input for the parser. The type must implement the `Stream` trait
-    ///which allows the parser to read item from the type.
+    /// The type which is take as input for the parser. The type must implement the `Stream` trait
+    /// which allows the parser to read item from the type.
     type Input: Stream;
-    ///The type which is returned if the parser is successful.
+    /// The type which is returned if the parser is successful.
     type Output;
 
-    ///Entrypoint of the parser
-    ///Takes some input and tries to parse it returning a `ParseResult`
+    /// Entrypoint of the parser
+    /// Takes some input and tries to parse it returning a `ParseResult`
     fn parse(&mut self,
              input: Self::Input)
              -> Result<(Self::Output, Self::Input), ParseError<Self::Input>> {
-        match self.parse_state(State::new(input)) {
-            Ok((v, state)) => Ok((v, state.into_inner().input)),
+        match self.parse_stream(input) {
+            Ok((v, state)) => Ok((v, state.into_inner())),
             Err(error) => Err(error.into_inner()),
         }
     }
 
-    ///Parses using the state `input` by calling Stream::uncons one or more times
-    ///On success returns `Ok((value, new_state))` on failure it returns `Err(error)`
-    fn parse_state(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
+    /// Parses using the stream `input` by calling Stream::uncons one or more times
+    /// On success returns `Ok((value, new_state))` on failure it returns `Err(error)`
+    #[inline(always)]
+    fn parse_stream(&mut self, input: Self::Input) -> ParseResult<Self::Output, Self::Input> {
+        self.parse_stream_consumed(input).into()
+    }
+
+    /// Parses using the stream `input` by calling Stream::uncons one or more times
+    /// On success returns `Ok((value, new_state))` on failure it returns `Err(error)`
+    #[inline]
+    fn parse_stream_consumed(&mut self,
+                             mut input: Self::Input)
+                             -> ConsumedResult<Self::Output, Self::Input> {
         let mut result = self.parse_lazy(input.clone());
-        if let Err(Consumed::Empty(ref mut error)) = result {
-            if let Ok((t, _)) = input.input.uncons() {
+        if let FastResult::EmptyErr(ref mut error) = result {
+            if let Ok(t) = input.uncons() {
                 error.add_error(Error::Unexpected(Info::Token(t)));
             }
             self.add_error(error);
@@ -868,15 +1126,292 @@ pub trait Parser {
         result
     }
 
-    ///Specialized version of parse_state where the parser does not need to add an error to the
-    ///`ParseError` when it does not consume any input before encountering the error.
-    ///Instead the error can be added later through the `add_error` method
-    fn parse_lazy(&mut self, input: State<Self::Input>) -> ParseResult<Self::Output, Self::Input> {
-        self.parse_state(input)
+    /// Specialized version of parse_stream where the parser does not need to add an error to the
+    /// `ParseError` when it does not consume any input before encountering the error.
+    /// Instead the error can be added later through the `add_error` method
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        self.parse_stream(input).into()
     }
 
-    ///Adds the first error that would normally be returned by this parser if it failed
+    /// Adds the first error that would normally be returned by this parser if it failed
     fn add_error(&mut self, _error: &mut ParseError<Self::Input>) {}
+
+    /// Discards the value of the `self` parser and returns the value of `p`
+    /// Fails if any of the parsers fails
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # fn main() {
+    /// let result = digit()
+    ///     .with(token('i'))
+    ///     .parse("9i")
+    ///     .map(|x| x.0);
+    /// assert_eq!(result, Ok('i'));
+    /// # }
+    /// ```
+    fn with<P2>(self, p: P2) -> With<Self, P2>
+        where Self: Sized,
+              P2: Parser<Input = Self::Input>
+    {
+        with(self, p)
+    }
+
+    /// Discards the value of the `p` parser and returns the value of `self`
+    /// Fails if any of the parsers fails
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # fn main() {
+    /// let result = digit()
+    ///     .skip(token('i'))
+    ///     .parse("9i")
+    ///     .map(|x| x.0);
+    /// assert_eq!(result, Ok('9'));
+    /// # }
+    /// ```
+    fn skip<P2>(self, p: P2) -> Skip<Self, P2>
+        where Self: Sized,
+              P2: Parser<Input = Self::Input>
+    {
+        skip(self, p)
+    }
+
+    /// Parses with `self` followed by `p`
+    /// Succeeds if both parsers succeed, otherwise fails
+    /// Returns a tuple with both values on success
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # fn main() {
+    /// let result = digit()
+    ///     .and(token('i'))
+    ///     .parse("9i")
+    ///     .map(|x| x.0);
+    /// assert_eq!(result, Ok(('9', 'i')));
+    /// # }
+    /// ```
+    fn and<P2>(self, p: P2) -> (Self, P2)
+        where Self: Sized,
+              P2: Parser<Input = Self::Input>
+    {
+        (self, p)
+    }
+
+    /// Returns a parser which attempts to parse using `self`. If `self` fails without consuming any
+    /// input it tries to consume the same input using `p`.
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::{digit, string};
+    /// # fn main() {
+    /// let mut parser = string("let")
+    ///     .or(digit().map(|_| "digit"))
+    ///     .or(string("led"));
+    /// assert_eq!(parser.parse("let"), Ok(("let", "")));
+    /// assert_eq!(parser.parse("1"), Ok(("digit", "")));
+    /// assert!(parser.parse("led").is_err());
+    ///
+    /// let mut parser2 = string("two").or(string("three"));
+    /// // Fails as the parser for "two" consumes the first 't' before failing
+    /// assert!(parser2.parse("three").is_err());
+    ///
+    /// // Use 'try' to make failing parsers always act as if they have not consumed any input
+    /// let mut parser3 = try(string("two")).or(try(string("three")));
+    /// assert_eq!(parser3.parse("three"), Ok(("three", "")));
+    /// # }
+    /// ```
+    fn or<P2>(self, p: P2) -> Or<Self, P2>
+        where Self: Sized,
+              P2: Parser<Input = Self::Input, Output = Self::Output>
+    {
+        or(self, p)
+    }
+
+    /// Parses using `self` and then passes the value to `f` which returns a parser used to parse
+    /// the rest of the input
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # use combine::primitives::{Consumed, Error};
+    /// # fn main() {
+    /// let result = digit()
+    ///     .then(|d| parser(move |input| {
+    ///             // Force input to be a &str
+    ///             let _: &str = input;
+    ///         if d == '9' {
+    ///             Ok((9, Consumed::Empty(input)))
+    ///         }
+    ///         else {
+    ///             let position = input.position();
+    ///             let err = ParseError::new(position, Error::Message("Not a nine".into()));
+    ///             Err((Consumed::Empty(err)))
+    ///         }
+    ///     }))
+    ///     .parse("9");
+    /// assert_eq!(result, Ok((9, "")));
+    /// # }
+    /// ```
+    fn then<N, F>(self, f: F) -> Then<Self, F>
+        where Self: Sized,
+              F: FnMut(Self::Output) -> N,
+              N: Parser<Input = Self::Input>
+    {
+        then(self, f)
+    }
+
+    /// Uses `f` to map over the parsed value
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # fn main() {
+    /// let result = digit()
+    ///     .map(|c| c == '9')
+    ///     .parse("9")
+    ///     .map(|x| x.0);
+    /// assert_eq!(result, Ok(true));
+    /// # }
+    /// ```
+    fn map<F, B>(self, f: F) -> Map<Self, F>
+        where Self: Sized,
+              F: FnMut(Self::Output) -> B
+    {
+        map(self, f)
+    }
+
+    /// Uses `f` to map over the output of `self`. If `f` returns an error the parser fails.
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # use combine::range::take;
+    /// # fn main() {
+    /// let result = take(4)
+    ///     .flat_map(|bs| many(digit()).parse(bs).map(|t| t.0))
+    ///     .parse("12abcd");
+    /// assert_eq!(result, Ok((String::from("12"), "cd")));
+    /// # }
+    /// ```
+    fn flat_map<F, B>(self, f: F) -> FlatMap<Self, F>
+        where Self: Sized,
+              F: FnMut(Self::Output) -> Result<B, ParseError<Self::Input>>
+    {
+        flat_map(self, f)
+    }
+
+    /// Parses with `self` and if it fails, adds the message `msg` to the error
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::primitives::{Error, Positioner};
+    /// # fn main() {
+    /// let result = token('9')
+    ///     .message("Not a nine")
+    ///     .parse(State::new("8"));
+    /// assert_eq!(result, Err(ParseError {
+    ///     position: <char as Positioner>::start(),
+    ///     errors: vec![
+    ///         Error::Unexpected('8'.into()),
+    ///         Error::Expected('9'.into()),
+    ///         Error::Message("Not a nine".into())
+    ///     ]
+    /// }));
+    /// # }
+    /// ```
+    fn message<S>(self, msg: S) -> Message<Self>
+        where Self: Sized,
+              S: Into<Info<<Self::Input as StreamOnce>::Item, <Self::Input as StreamOnce>::Range>>
+    {
+        message(self, msg.into())
+    }
+
+    /// Parses with `self` and if it fails without consuming any input any expected errors are
+    /// replaced by `msg`. `msg` is then used in error messages as "Expected `msg`".
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::primitives::{Error, Positioner};
+    /// # fn main() {
+    /// let result = token('9')
+    ///     .expected("nine")
+    ///     .parse(State::new("8"));
+    /// assert_eq!(result, Err(ParseError {
+    ///     position: <char as Positioner>::start(),
+    ///     errors: vec![Error::Unexpected('8'.into()), Error::Expected("nine".into())]
+    /// }));
+    /// # }
+    /// ```
+    fn expected<S>(self, msg: S) -> Expected<Self>
+        where Self: Sized,
+              S: Into<Info<<Self::Input as StreamOnce>::Item, <Self::Input as StreamOnce>::Range>>
+    {
+        expected(self, msg.into())
+    }
+
+    /// Parses with `self` and applies `f` on the result if `self` parses successfully
+    /// `f` may optionally fail with an error which is automatically converted to a `ParseError`
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::digit;
+    /// # fn main() {
+    /// let mut parser = many1(digit())
+    ///     .and_then(|s: String| s.parse::<i32>());
+    /// let result = parser.parse("1234");
+    /// assert_eq!(result, Ok((1234, "")));
+    /// let err = parser.parse("abc");
+    /// assert!(err.is_err());
+    /// # }
+    /// ```
+    fn and_then<F, O, E>(self, f: F) -> AndThen<Self, F>
+        where Self: Sized,
+              F: FnMut(Self::Output) -> Result<O, E>,
+              E: Into<Error<<Self::Input as StreamOnce>::Item, <Self::Input as StreamOnce>::Range>>
+    {
+        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
+    ///
+    /// ```
+    /// # extern crate combine;
+    /// # use combine::*;
+    /// # use combine::char::{char, digit};
+    /// # fn main() {
+    /// let mut buffer = String::new();
+    /// let number = parser(|input| {
+    ///     buffer.clear();
+    ///     let mut iter = digit().iter(input);
+    ///     buffer.extend(&mut iter);
+    ///     let i = buffer.parse::<i32>().unwrap();
+    ///     iter.into_result(i)
+    /// });
+    /// let result = sep_by(number, char(','))
+    ///     .parse("123,45,6");
+    /// assert_eq!(result, Ok((vec![123, 45, 6], "")));
+    /// # }
+    /// ```
+    fn iter(self, input: Self::Input) -> Iter<Self>
+        where Self: Sized
+    {
+        Iter::new(self, input)
+    }
 }
 impl<'a, I, O, P: ?Sized> Parser for &'a mut P
     where I: Stream,
@@ -884,12 +1419,23 @@ impl<'a, I, O, P: ?Sized> Parser for &'a mut P
 {
     type Input = I;
     type Output = O;
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<O, I> {
-        (**self).parse_state(input)
+
+    #[inline(always)]
+    fn parse_stream(&mut self, input: I) -> ParseResult<O, I> {
+        (**self).parse_stream(input)
+    }
+
+    #[inline(always)]
+    fn parse_stream_consumed(&mut self, input: I) -> ConsumedResult<O, I> {
+        (**self).parse_stream_consumed(input)
     }
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
+
+    #[inline(always)]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
         (**self).parse_lazy(input)
     }
+
+    #[inline(always)]
     fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
         (**self).add_error(error)
     }
@@ -900,29 +1446,53 @@ impl<I, O, P: ?Sized> Parser for Box<P>
 {
     type Input = I;
     type Output = O;
-    fn parse_state(&mut self, input: State<I>) -> ParseResult<O, I> {
-        (**self).parse_state(input)
+
+    #[inline(always)]
+    fn parse_stream(&mut self, input: I) -> ParseResult<O, I> {
+        (**self).parse_stream(input)
+    }
+
+    #[inline(always)]
+    fn parse_stream_consumed(&mut self, input: I) -> ConsumedResult<O, I> {
+        (**self).parse_stream_consumed(input)
     }
-    fn parse_lazy(&mut self, input: State<I>) -> ParseResult<O, I> {
+
+    #[inline(always)]
+    fn parse_lazy(&mut self, input: I) -> ConsumedResult<O, I> {
         (**self).parse_lazy(input)
     }
+
+    #[inline(always)]
     fn add_error(&mut self, error: &mut ParseError<Self::Input>) {
         (**self).add_error(error)
     }
 }
 
-#[cfg(feature = "buffered_stream")]
+/// A `BufferedStream` wraps an instance `StreamOnce`, allowing it to b used as a `Stream`
 pub struct BufferedStream<'a, I>
-    where I: Iterator + 'a,
+    where I: StreamOnce + 'a,
           I::Item: 'a
 {
     offset: usize,
     buffer: &'a SharedBufferedStream<I>,
 }
 
-#[cfg(feature = "buffered_stream")]
+impl<'a, I> fmt::Debug for BufferedStream<'a, I>
+    where I: StreamOnce + '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: {:?} }}",
+               self.offset,
+               buffer_offset)
+    }
+}
+
 impl<'a, I> Clone for BufferedStream<'a, I>
-    where I: Iterator + 'a,
+    where I: StreamOnce + 'a,
+          I::Position: Clone,
           I::Item: 'a
 {
     fn clone(&self) -> BufferedStream<'a, I> {
@@ -933,53 +1503,61 @@ impl<'a, I> Clone for BufferedStream<'a, I>
     }
 }
 
-#[cfg(feature = "buffered_stream")]
 pub struct SharedBufferedStream<I>
-    where I: Iterator
+    where I: StreamOnce
 {
     buffer: UnsafeCell<BufferedStreamInner<I>>,
 }
 
-#[cfg(feature = "buffered_stream")]
 struct BufferedStreamInner<I>
-    where I: Iterator
+    where I: StreamOnce
 {
     offset: usize,
     iter: I,
-    buffer: VecDeque<I::Item>,
+    buffer: VecDeque<(I::Item, I::Position)>,
 }
 
-#[cfg(feature = "buffered_stream")]
 impl<I> BufferedStreamInner<I>
-    where I: Iterator,
+    where I: StreamOnce,
+          I::Position: Clone,
           I::Item: Clone
 {
-    fn uncons(&mut self, offset: usize) -> Result<I::Item, Error<I::Item, I::Item>> {
+    #[inline]
+    fn uncons(&mut self, offset: usize) -> Result<I::Item, Error<I::Item, I::Range>> {
         if offset >= self.offset {
-            let item = match self.iter.next() {
-                Some(item) => item,
-                None => return Err(Error::end_of_input()),
-            };
+            let position = self.iter.position();
+            let item = try!(self.iter.uncons());
             self.offset += 1;
             // We want the VecDeque to only keep the last .capacity() elements so we need to remove
             // an element if it gets to large
             if self.buffer.len() == self.buffer.capacity() {
                 self.buffer.pop_front();
             }
-            self.buffer.push_back(item.clone());
+            self.buffer.push_back((item.clone(), position.clone()));
             Ok(item)
         } else if offset < self.offset - self.buffer.len() {
             // We have backtracked to far
             Err(Error::Message("Backtracked to far".into()))
         } else {
-            Ok(self.buffer[self.buffer.len() - (self.offset - offset)].clone())
+            Ok(self.buffer[self.buffer.len() - (self.offset - offset)].0.clone())
+        }
+    }
+
+    #[inline]
+    fn position(&self, offset: usize) -> I::Position {
+        if offset >= self.offset {
+            self.iter.position()
+        } else if offset < self.offset - self.buffer.len() {
+            self.buffer.front().expect("Atleast 1 element in the buffer").1.clone()
+        } else {
+            self.buffer[self.buffer.len() - (self.offset - offset)].1.clone()
         }
     }
 }
 
-#[cfg(feature = "buffered_stream")]
 impl<I> SharedBufferedStream<I>
-    where I: Iterator,
+    where I: StreamOnce,
+          I::Position: Clone,
           I::Item: Clone
 {
     pub fn as_stream(&self) -> BufferedStream<I> {
@@ -988,15 +1566,24 @@ impl<I> SharedBufferedStream<I>
             buffer: self,
         }
     }
-    fn uncons(&self, offset: usize) -> Result<I::Item, Error<I::Item, I::Item>> {
+    #[inline]
+    fn uncons(&self, offset: usize) -> Result<I::Item, Error<I::Item, I::Range>> {
         unsafe { (*self.buffer.get()).uncons(offset) }
     }
+    #[inline(always)]
+    fn position(&self, offset: usize) -> I::Position {
+        unsafe { (*self.buffer.get()).position(offset) }
+    }
 }
 
-#[cfg(feature = "buffered_stream")]
 impl<'a, I> BufferedStream<'a, I>
-    where I: Iterator
+    where I: StreamOnce
 {
+    /// 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 could
+    /// be used multiple times.
     pub fn new(iter: I, lookahead: usize) -> SharedBufferedStream<I> {
         SharedBufferedStream {
             buffer: UnsafeCell::new(BufferedStreamInner {
@@ -1008,17 +1595,38 @@ impl<'a, I> BufferedStream<'a, I>
     }
 }
 
-#[cfg(feature = "buffered_stream")]
-impl<'a, I> Stream for BufferedStream<'a, I>
-    where I: Iterator + 'a,
-          I::Item: Positioner + Clone + 'a
+impl<'a, I> StreamOnce for BufferedStream<'a, I>
+    where I: StreamOnce + 'a,
+          I::Position: Clone,
+          I::Item: Clone + PartialEq + 'a
 {
     type Item = I::Item;
-    type Range = I::Item;
+    type Range = I::Range;
+    type Position = I::Position;
 
-    fn uncons(mut self) -> Result<(I::Item, BufferedStream<'a, I>), Error<I::Item, I::Item>> {
+    #[inline]
+    fn uncons(&mut self) -> Result<I::Item, Error<I::Item, I::Range>> {
         let value = try!(self.buffer.uncons(self.offset));
         self.offset += 1;
-        Ok((value, self))
+        Ok(value)
+    }
+
+    #[inline(always)]
+    fn position(&self) -> Self::Position {
+        self.buffer.position(self.offset)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    #[test]
+    #[inline]
+    fn uncons_range_at_end() {
+        assert_eq!("".uncons_range(0), Ok(""));
+        assert_eq!("123".uncons_range(3), Ok("123"));
+        assert_eq!((&[1][..]).uncons_range(1), Ok(&[1][..]));
+        let s: &[u8] = &[];
+        assert_eq!(SliceStream(s).uncons_range(0), Ok(&[][..]));
     }
 }
diff --git a/src/range.rs b/src/range.rs
new file mode 100644
index 00000000..fdb3d311
--- /dev/null
+++ b/src/range.rs
@@ -0,0 +1,194 @@
+use std::marker::PhantomData;
+
+use primitives::{ConsumedResult, Error, Info, ParseError, Parser, RangeStream};
+use primitives::FastResult::*;
+
+pub struct Range<I>(I::Range) where I: RangeStream;
+
+impl<I> Parser for Range<I>
+    where I: RangeStream,
+          I::Range: PartialEq + ::primitives::Range
+{
+    type Input = I;
+    type Output = I::Range;
+
+    #[inline]
+    fn parse_lazy(&mut self, mut input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        use primitives::Range;
+        let position = input.position();
+        match input.uncons_range(self.0.len()) {
+            Ok(other) => {
+                if other == self.0 {
+                    ConsumedOk((other, input))
+                } else {
+                    EmptyErr(ParseError::empty(position))
+                }
+            }
+            Err(err) => EmptyErr(ParseError::new(position, err)),
+        }
+    }
+    fn add_error(&mut self, errors: &mut ParseError<Self::Input>) {
+        // TODO Add unexpected message?
+        errors.add_error(Error::Expected(Info::Range(self.0.clone())));
+    }
+}
+
+/// ```
+/// # extern crate combine;
+/// # use combine::range::range;
+/// # use combine::*;
+/// # fn main() {
+/// let mut parser = range("hello");
+/// let result = parser.parse("hello world");
+/// assert_eq!(result, Ok(("hello", " world")));
+/// let result = parser.parse("hel world");
+/// assert!(result.is_err());
+/// # }
+/// ```
+#[inline(always)]
+pub fn range<I>(i: I::Range) -> Range<I>
+    where I: RangeStream,
+          I::Range: PartialEq + ::primitives::Range
+{
+    Range(i)
+}
+
+pub struct Take<I>(usize, PhantomData<fn(I) -> I>);
+impl<I> Parser for Take<I>
+    where I: RangeStream,
+          I::Range: ::primitives::Range
+{
+    type Input = I;
+    type Output = I::Range;
+
+    #[inline]
+    fn parse_lazy(&mut self, mut input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        let position = input.position();
+        match input.uncons_range(self.0) {
+            Ok(x) => ConsumedOk((x, input)),
+            Err(err) => EmptyErr(ParseError::new(position, err)),
+        }
+    }
+}
+
+/// ```
+/// # extern crate combine;
+/// # use combine::range::take;
+/// # use combine::*;
+/// # fn main() {
+/// let mut parser = take(1);
+/// let result = parser.parse("1");
+/// assert_eq!(result, Ok(("1", "")));
+/// let mut parser = take(4);
+/// let result = parser.parse("123abc");
+/// assert_eq!(result, Ok(("123a", "bc")));
+/// let result = parser.parse("abc");
+/// assert!(result.is_err());
+/// # }
+/// ```
+#[inline(always)]
+pub fn take<I>(n: usize) -> Take<I>
+    where I: RangeStream,
+          I::Range: ::primitives::Range
+{
+    Take(n, PhantomData)
+}
+
+pub struct TakeWhile<I, F>(F, PhantomData<fn(I) -> I>);
+impl<I, F> Parser for TakeWhile<I, F>
+    where I: RangeStream,
+          I::Range: ::primitives::Range,
+          F: FnMut(I::Item) -> bool
+{
+    type Input = I;
+    type Output = I::Range;
+
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        ::primitives::uncons_while(input, &mut self.0)
+    }
+}
+
+/// ```
+/// # extern crate combine;
+/// # use combine::range::take_while;
+/// # use combine::*;
+/// # fn main() {
+/// let mut parser = take_while(|c: char| c.is_digit(10));
+/// let result = parser.parse("123abc");
+/// assert_eq!(result, Ok(("123", "abc")));
+/// let result = parser.parse("abc");
+/// assert_eq!(result, Ok(("", "abc")));
+/// # }
+/// ```
+#[inline(always)]
+pub fn take_while<I, F>(f: F) -> TakeWhile<I, F>
+    where I: RangeStream,
+          F: FnMut(I::Item) -> bool
+{
+    TakeWhile(f, PhantomData)
+}
+
+pub struct TakeWhile1<I, F>(F, PhantomData<fn(I) -> I>);
+impl<I, F> Parser for TakeWhile1<I, F>
+    where I: RangeStream,
+          I::Range: ::primitives::Range,
+          F: FnMut(I::Item) -> bool
+{
+    type Input = I;
+    type Output = I::Range;
+
+    #[inline]
+    fn parse_lazy(&mut self, input: Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
+        match ::primitives::uncons_while(input, &mut self.0) {
+            ConsumedOk((v, input)) => ConsumedOk((v, input)),
+            EmptyOk((_, input)) => {
+                let position = input.position();
+                EmptyErr(ParseError::empty(position))
+            }
+            EmptyErr(err) => EmptyErr(err),
+            ConsumedErr(err) => ConsumedErr(err),
+        }
+    }
+}
+
+
+/// ```
+/// # extern crate combine;
+/// # use combine::range::take_while1;
+/// # use combine::*;
+/// # fn main() {
+/// let mut parser = take_while1(|c: char| c.is_digit(10));
+/// let result = parser.parse("123abc");
+/// assert_eq!(result, Ok(("123", "abc")));
+/// let result = parser.parse("abc");
+/// assert!(result.is_err());
+/// # }
+/// ```
+#[inline(always)]
+pub fn take_while1<I, F>(f: F) -> TakeWhile1<I, F>
+    where I: RangeStream,
+          I::Range: ::primitives::Range,
+          F: FnMut(I::Item) -> bool
+{
+    TakeWhile1(f, PhantomData)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use primitives::Parser;
+
+    #[test]
+    fn take_while_test() {
+        let result = take_while(|c: char| c.is_digit(10)).parse("123abc");
+        assert_eq!(result, Ok(("123", "abc")));
+    }
+
+    #[test]
+    fn range_string_no_char_boundary_error() {
+        let mut parser = range("hello");
+        let result = parser.parse("hell\u{00EE} world");
+        assert!(result.is_err());
+    }
+}


Test patch:
diff --git a/tests/buffered_stream.rs b/tests/buffered_stream.rs
index 4abe4498..3cccb3a2 100644
--- a/tests/buffered_stream.rs
+++ b/tests/buffered_stream.rs
@@ -1,7 +1,8 @@
 // The feature `buffered_stream` must be enabled to run these tests
 extern crate combine;
-use combine::*;
 use combine::primitives::{BufferedStream, Error};
+use combine::char::{char, digit, spaces, string};
+use combine::{StreamOnce, Parser, choice, from_iter, many, many1, sep_by, try};
 
 #[test]
 fn shared_stream_buffer() {
@@ -13,11 +14,12 @@ fn shared_stream_buffer() {
             c
         }
     });
-    let buffer = BufferedStream::new(text, 1);
-    let int = many(digit()).map(|s: String| s.parse::<i64>().unwrap());
+    let buffer = BufferedStream::new(from_iter(text), 1);
+    let int: &mut Parser<Input = _, Output = _> = &mut many(digit())
+        .map(|s: String| s.parse::<i64>().unwrap());
     let result = sep_by(int, char(','))
-                     .parse(buffer.as_stream())
-                     .map(|t| t.0);
+        .parse(buffer.as_stream())
+        .map(|t| t.0);
     assert_eq!(result, Ok(vec![21, 333, 4, 55]));
 }
 
@@ -26,13 +28,14 @@ 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(&mut iter, 2);
+    let buffer = BufferedStream::new(from_iter(&mut iter), 2);
     let stream = buffer.as_stream();
 
-    let value = choice([try(string("apple")), try(string("orange")), try(string("ananas"))]);
+    let value: &mut Parser<Input = _, Output = _> =
+        &mut choice([try(string("apple")), try(string("orange")), try(string("ananas"))]);
     let mut parser = sep_by(value, char(','));
     let result = parser.parse(stream)
-                       .map(|t| t.0);
+        .map(|t| t.0);
     assert_eq!(result, Ok(vec!["apple", "apple", "ananas", "orange"]));
 }
 
@@ -41,18 +44,19 @@ 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(&mut iter, 1);
+    let buffer = BufferedStream::new(from_iter(&mut iter), 1);
     let stream = buffer.as_stream();
 
-    let value = choice([try(string("apple")), try(string("orange")), try(string("ananas"))]);
+    let value: &mut Parser<Input = _, Output = _> =
+        &mut choice([try(string("apple")), try(string("orange")), try(string("ananas"))]);
     let mut parser = sep_by(value, char(','));
     let result: Result<Vec<&str>, _> = parser.parse(stream)
-                                             .map(|t| t.0);
+        .map(|t| t.0);
     assert!(result.is_err());
     assert!(result.unwrap_err()
-                  .errors
-                  .iter()
-                  .any(|err| *err == Error::Message("Backtracked to far".into())));
+        .errors
+        .iter()
+        .any(|err| *err == Error::Message("Backtracked to far".into())));
 }
 
 /// Test which checks that a stream which has ended does not repeat the last token in some cases in
@@ -60,10 +64,24 @@ fn shared_stream_insufficent_backtrack() {
 #[test]
 fn always_output_end_of_input_after_end_of_input() {
     let text = "10".chars();
-    let buffer = BufferedStream::new(text, 1);
+    let buffer = BufferedStream::new(from_iter(text), 1);
     let int = many1(digit()).map(|s: String| s.parse::<i64>().unwrap());
     let result = many(spaces().with(int))
-                     .parse(buffer.as_stream())
-                     .map(|t| t.0);
+        .parse(buffer.as_stream())
+        .map(|t| t.0);
     assert_eq!(result, Ok(vec![10]));
 }
+
+#[test]
+fn position() {
+    let text = "10abc".chars();
+    let buffer = BufferedStream::new(from_iter(text), 3);
+    let stream = buffer.as_stream();
+    println!("{:?}", stream);
+    assert_eq!(stream.position(), 0);
+    let result = many1::<Vec<_>, _>(digit()).parse(stream.clone());
+    println!("{:?}", stream);
+    assert_eq!(stream.position(), 0);
+    assert!(result.is_ok());
+    assert_eq!(result.unwrap().1.position(), 2);
+}
diff --git a/tests/date.rs b/tests/date.rs
index 5b90a98c..77f0533f 100644
--- a/tests/date.rs
+++ b/tests/date.rs
@@ -3,9 +3,10 @@
 
 extern crate combine;
 
-use combine::*;
 use combine::combinator::FnParser;
-use combine::primitives::Stream;
+use combine::char::{char, digit};
+use combine::{Stream, Parser, ParseResult, choice, many, optional, parser};
+
 
 #[derive(PartialEq, Debug)]
 pub struct Date {
@@ -37,15 +38,15 @@ fn two_digits_to_int((x, y): (char, char)) -> i32 {
 
 // Parsers which are used frequntly can be wrapped like this to avoid writing parser(fn_name) in
 // several places.
-fn two_digits<I>() -> FnParser<I, fn(State<I>) -> ParseResult<i32, I>>
+fn two_digits<I>() -> FnParser<I, fn(I) -> ParseResult<i32, I>>
     where I: Stream<Item = char>
 {
-    fn two_digits_<I>(input: State<I>) -> ParseResult<i32, I>
+    fn two_digits_<I>(input: I) -> ParseResult<i32, I>
         where I: Stream<Item = char>
     {
         (digit(), digit())
             .map(two_digits_to_int)
-            .parse_state(input)
+            .parse_stream(input)
     }
     parser(two_digits_)
 }
@@ -55,36 +56,28 @@ fn two_digits<I>() -> FnParser<I, fn(State<I>) -> ParseResult<i32, I>>
 /// -06:30
 /// -01
 /// Z
-fn time_zone<I>(input: State<I>) -> ParseResult<i32, I>
+fn time_zone<I>(input: I) -> ParseResult<i32, I>
     where I: Stream<Item = char>
 {
     let utc = char('Z').map(|_| 0);
     let offset = (choice([char('-'), char('+')]),
                   two_digits(),
                   optional(optional(char(':')).with(two_digits())))
-                     .map(|(sign, hour, minute)| {
-                         let offset = hour * 60 + minute.unwrap_or(0);
-                         if sign == '-' {
-                             -offset
-                         } else {
-                             offset
-                         }
-                     });
+        .map(|(sign, hour, minute)| {
+            let offset = hour * 60 + minute.unwrap_or(0);
+            if sign == '-' { -offset } else { offset }
+        });
 
     utc.or(offset)
-       .parse_state(input)
+        .parse_stream(input)
 }
 
 /// Parses a date
 /// 2010-01-30
-fn date<I>(input: State<I>) -> ParseResult<Date, I>
+fn date<I>(input: I) -> ParseResult<Date, I>
     where I: Stream<Item = char>
 {
-    (many::<String, _>(digit()),
-     char('-'),
-     two_digits(),
-     char('-'),
-     two_digits())
+    (many::<String, _>(digit()), char('-'), two_digits(), char('-'), two_digits())
         .map(|(year, _, month, _, day)| {
             // Its ok to just unwrap since we only parsed digits
             Date {
@@ -93,20 +86,15 @@ fn date<I>(input: State<I>) -> ParseResult<Date, I>
                 day: day,
             }
         })
-        .parse_state(input)
+        .parse_stream(input)
 }
 
 /// Parses a time
 /// 12:30:02
-fn time<I>(input: State<I>) -> ParseResult<Time, I>
+fn time<I>(input: I) -> ParseResult<Time, I>
     where I: Stream<Item = char>
 {
-    (two_digits(),
-     char(':'),
-     two_digits(),
-     char(':'),
-     two_digits(),
-     parser(time_zone))
+    (two_digits(), char(':'), two_digits(), char(':'), two_digits(), parser(time_zone))
         .map(|(hour, _, minute, _, second, time_zone)| {
             // Its ok to just unwrap since we only parsed digits
             Time {
@@ -116,12 +104,12 @@ fn time<I>(input: State<I>) -> ParseResult<Time, I>
                 time_zone: time_zone,
             }
         })
-        .parse_state(input)
+        .parse_stream(input)
 }
 
 /// Parses a date time according to ISO8601
 /// 2015-08-02T18:54:42+02
-fn date_time<I>(input: State<I>) -> ParseResult<DateTime, I>
+fn date_time<I>(input: I) -> ParseResult<DateTime, I>
     where I: Stream<Item = char>
 {
     (parser(date), char('T'), parser(time))
@@ -131,7 +119,7 @@ fn date_time<I>(input: State<I>) -> ParseResult<DateTime, I>
                 time: time,
             }
         })
-        .parse_state(input)
+        .parse_stream(input)
 }
 
 #[test]
diff --git a/tests/ini.rs b/tests/ini.rs
index 36bfcbf3..6231b65e 100644
--- a/tests/ini.rs
+++ b/tests/ini.rs
@@ -4,7 +4,8 @@ extern crate combine;
 use std::collections::HashMap;
 
 use combine::*;
-use combine::primitives::{Error, SourcePosition, Stream};
+use combine::char::space;
+use combine::primitives::{Error, SourcePosition};
 
 #[derive(PartialEq, Debug)]
 pub struct Ini {
@@ -12,7 +13,7 @@ pub struct Ini {
     pub sections: HashMap<String, HashMap<String, String>>,
 }
 
-fn property<I>(input: State<I>) -> ParseResult<(String, String), I>
+fn property<I>(input: I) -> ParseResult<(String, String), I>
     where I: Stream<Item = char>
 {
     (many1(satisfy(|c| c != '=' && c != '[' && c != ';')),
@@ -20,26 +21,26 @@ fn property<I>(input: State<I>) -> ParseResult<(String, String), I>
      many1(satisfy(|c| c != '\n' && c != ';')))
         .map(|(key, _, value)| (key, value))
         .expected("property")
-        .parse_state(input)
+        .parse_stream(input)
 }
 
-fn whitespace<I>(input: State<I>) -> ParseResult<(), I>
+fn whitespace<I>(input: I) -> ParseResult<(), I>
     where I: Stream<Item = char>
 {
     let comment = (token(';'), skip_many(satisfy(|c| c != '\n'))).map(|_| ());
     // Wrap the `spaces().or(comment)` in `skip_many` so that it skips alternating whitespace and
     // comments
-    skip_many(skip_many1(space()).or(comment)).parse_state(input)
+    skip_many(skip_many1(space()).or(comment)).parse_stream(input)
 }
 
-fn properties<I>(input: State<I>) -> ParseResult<HashMap<String, String>, I>
+fn properties<I>(input: I) -> ParseResult<HashMap<String, String>, I>
     where I: Stream<Item = char>
 {
     // After each property we skip any whitespace that followed it
-    many(parser(property).skip(parser(whitespace))).parse_state(input)
+    many(parser(property).skip(parser(whitespace))).parse_stream(input)
 }
 
-fn section<I>(input: State<I>) -> ParseResult<(String, HashMap<String, String>), I>
+fn section<I>(input: I) -> ParseResult<(String, HashMap<String, String>), I>
     where I: Stream<Item = char>
 {
     (between(token('['), token(']'), many(satisfy(|c| c != ']'))),
@@ -47,22 +48,20 @@ fn section<I>(input: State<I>) -> ParseResult<(String, HashMap<String, String>),
      parser(properties))
         .map(|(name, _, properties)| (name, properties))
         .expected("section")
-        .parse_state(input)
+        .parse_stream(input)
 }
 
-fn ini<I>(input: State<I>) -> ParseResult<Ini, I>
+fn ini<I>(input: I) -> ParseResult<Ini, I>
     where I: Stream<Item = char>
 {
-    (parser(whitespace),
-     parser(properties),
-     many(parser(section)))
+    (parser(whitespace), parser(properties), many(parser(section)))
         .map(|(_, global, sections)| {
             Ini {
                 global: global,
                 sections: sections,
             }
         })
-        .parse_state(input)
+        .parse_stream(input)
 }
 
 #[test]
@@ -87,8 +86,8 @@ type=LL(1)
     expected.sections.insert(String::from("section"), section);
 
     let result = parser(ini)
-                     .parse(text)
-                     .map(|t| t.0);
+        .parse(text)
+        .map(|t| t.0);
     assert_eq!(result, Ok(expected));
 }
 
@@ -96,8 +95,8 @@ type=LL(1)
 fn ini_error() {
     let text = "[error";
     let result = parser(ini)
-                     .parse(text)
-                     .map(|t| t.0);
+        .parse(State::new(text))
+        .map(|t| t.0);
     assert_eq!(result,
                Err(ParseError {
                    position: SourcePosition {