Merge ~athos-ribeiro/ubuntu/+source/mdevctl:merge-mdevctl-rust-kinetic into ubuntu/+source/mdevctl:debian/sid

[Athos Ribeiro]

This is the current proposal for using vendorized code in the new, rust based, mdevctl package.

Do note that this could be ported to Debian and be used as a sync IF having vendorized code in the debian source package does not infringe any Debian policies. I could not find a reference for the matter in the Debian policy. While this is not clear, this should be a delta here.

PPA: https://launchpad.net/~athos-ribeiro/+archive/ubuntu/mdevctl-mre/+packages

To build the package with the delta, one would need to use uscan to fetch the vendorized code as described in the d/watch file since it will not be available in Debian.

It is worth mentioning that dh-cargo generates a X-Cargo-Built-Using field, describing some package build dependencies. For instance, the current Debian unstable package has

$ dpkg-deb --info ../mdevctl_1.1.0-1+b1_amd64.deb
 ...
 Depends: udev, libc6 (>= 2.33), libgcc-s1 (>= 4.2)
 Built-Using: rustc (= 1.58.1+dfsg1-1)
 ...
 X-Cargo-Built-Using: rust-aho-corasick (= 0.7.10-1), rust-ansi-term (= 0.12.1-1), rust-anyhow (= 1.0.44-2), rust-atty (= 0.2.14-2), rust-bitflags (= 1.3.2-2), rust-cfg-if-0.1 (= 0.1.10-2), rust-cfg-if (= 1.0.0-1), rust-clap-2 (= 2.34.0-1), rust-env-logger (= 0.9.0-1), rust-getrandom (= 0.2.4-2), rust-hashbrown (= 0.11.2-2), rust-humantime (= 2.1.0-1), rust-indexmap (= 1.7.0-1), rust-itoa (= 0.4.8-1), rust-lazy-static (= 1.4.0-1), rust-libc (= 0.2.103-1), rust-log (= 0.4.11-2), rust-memchr (= 2.4.1-1), rust-ppv-lite86 (= 0.2.16-1), rust-rand-chacha (= 0.3.1-2), rust-rand-core (= 0.6.3-2), rust-rand (= 0.8.4-2), rust-regex (= 1.5.5-1), rust-regex-syntax (= 0.6.25-1), rust-remove-dir-all (= 0.5.2-1), rust-ryu (= 1.0.2-1), rust-serde (= 1.0.130-2), rust-serde-json (= 1.0.45-1), rust-smawk (= 0.3.1-2), rust-strsim (= 0.9.3-1), rust-structopt (= 0.3.26-2), rust-tempfile (= 3.2.0-2), rust-termcolor (= 1.1.2-1), rust-textwrap (= 0.15.0-2), rust-unicode-linebreak (= 0.1.2-1), rust-unicode-width (= 0.1.9-3), rust-uuid (= 0.8.1-4), rust-vec-map (= 0.8.1-2), rustc (= 1.58.1+dfsg1-1)

This field will no longer be meaningful once we are building from vendorized dependencies:

$ dpkg-deb --info ../mdevctl_1.1.0-1ubuntu1_amd64.deb
 ...
 Depends: udev, libc6 (>= 2.34), libgcc-s1 (>= 4.2)
 Built-Using: rustc (= 1.59.0+dfsg1-1~ubuntu2)
 ...
 X-Cargo-Built-Using: rustc (= 1.59.0+dfsg1-1~ubuntu2)

In the future, if vendoring becomes a standard for rust packages in main, we may want to add a delta to dh-cargo to possibly include the vendored data in that field. Alternatively, the sec team would need to monitor the vendored code in the source package. For either of these cases, we would need to fetch the data from the `vendor` directory, for instance:

find vendor -name Cargo.toml -exec grep -m2 -E '^name|^version' '{}' \;

[Athos Ribeiro (athos-ribeiro)]

Do note that this MP was filed to present and discuss the proposed approach on how to deal with mdevctl. This would only be merged and uploaded after the rust-based mdevctl MIR process is complete.

[Athos Ribeiro (athos-ribeiro)]

Also, the hack in execute_after_dh_auto_configure could be a complete override in dh_auto_configure, which would look like

override_dh_auto_configure:
 cp debian/cargo-checksum.json
 rm -rf Cargo.lock
 /usr/share/cargo/bin/cargo prepare-debian $(CURDIR)/vendor

But then we would risk missing any further changes in dh-cargo regarding dh_auto_configure.

[Christian Ehrhardt  (paelzer)]

Hi,
thanks for your work here, going through one by one:

56c301e * New changes: - d/control: depend on librust-uuid+rand-dev for v4 feature.
  The change to the new librust-uuid+rand-dev (>= 0.8.1) is fine for Debian
  But since we want to become all-vendored do we want/need it here?
  Would it make sense to split this into a salsa PR instead?

1170c60 - d/watch: introduce vendor component with bundled dependencies.
  haven't seen opts=component=vendor before but it LGTM
  Tried it and it worked including the subdir repack
  ack for this as ubuntu delta

39c8e95 - vendor: unpack vendorized sources.
50d5f29 - d/copyright: include vendorized projects copyright data.
  ack for these as ubuntu delta

73d40a9 - d/rules: use vendorized dependencies for Ubuntu builds.
  Nice use of /usr/share/dpkg/vendor.mk
  ack for this as ubuntu delta
  This part is a Debian no-op and could even be added there I guess.

3df8c59 - d/patches: drop dependency version tweaks in favor of vendorized dependencies.
  Maybe just disable it in d/p/series but do not remove the patch
  That way you have less noise and will
  a) easier rebase future versions
  b) allow people to "go back for deb style build" more easily
  This is up to you though, not enough to mark this won't fix

80b5454 Update changelog for 1.1.0-1ubuntu1 release
1d1eb5e Update maintainer
  Just mechanical, yes that LGTM as well

Back in the "debate rust MIR rules" we had discussed about ways for security to track those inclcuded things. See https://github.com/cpaelzer/ubuntu-mir/pull/3/files
Do you have a new build/buildlog so we can check to modify getting any of that?

#1 We either want a .lock file (which dh-cargo deleted the one you get from upstream and does IIRC not create a new one). The discussion there wasn't 100% final so if that isn't working it might be ok but then it needs proper mentioning in some Built-Using that works.

#2 Other than those dependencies we also had the need to document "how to refresh vendored code" in debian/README.source - you could drop an example how uscan works with component=vendor in this case.

review: Needs Information

[Athos Ribeiro (athos-ribeiro)]

Thanks for the review, Christian!

> 56c301e * New changes: - d/control: depend on librust-uuid+rand-dev for
> v4 feature.
> The change to the new librust-uuid+rand-dev (>= 0.8.1) is fine for Debian
> But since we want to become all-vendored do we want/need it here?
> Would it make sense to split this into a salsa PR instead?

This was already submitted and merged into Debian (it was not released yet though).

> 73d40a9 - d/rules: use vendorized dependencies for Ubuntu builds.
> Nice use of /usr/share/dpkg/vendor.mk
> ack for this as ubuntu delta
> This part is a Debian no-op and could even be added there I guess.

I submitted https://salsa.debian.org/debian/mdevctl/-/merge_requests/4 for this one.

> 3df8c59 - d/patches: drop dependency version tweaks in favor of vendorized
> dependencies.
> Maybe just disable it in d/p/series but do not remove the patch
> That way you have less noise and will
> a) easier rebase future versions
> b) allow people to "go back for deb style build" more easily
> This is up to you though, not enough to mark this won't fix

+1 Done.

> Back in the "debate rust MIR rules" we had discussed about ways for security
> to track those inclcuded things. See https://github.com/cpaelzer/ubuntu-
> mir/pull/3/files
> Do you have a new build/buildlog so we can check to modify getting any of
> that?
>

The current proposal is in a PPA at https://launchpad.net/~athos-ribeiro/+archive/ubuntu/mdevctl-mre/+packages

> #1 We either want a .lock file (which dh-cargo deleted the one you get from
> upstream and does IIRC not create a new one). The discussion there wasn't 100%
> final so if that isn't working it might be ok but then it needs proper
> mentioning in some Built-Using that works.
>
> #2 Other than those dependencies we also had the need to document "how to
> refresh vendored code" in debian/README.source - you could drop an example how
> uscan works with component=vendor in this case.

I added a small comment in d/README.source to address #2.

I am working on a solution for #1 and will update this MP as soon as it is up.

[Athos Ribeiro (athos-ribeiro)]

MP updated to ship the cargo lockfile, as proposed in https://github.com/cpaelzer/ubuntu-mir/pull/3.

PPA available at https://launchpad.net/~athos-ribeiro/+archive/ubuntu/mdevctl-vendored-plus-lockfile/+packages

[Christian Ehrhardt  (paelzer)]

On Tue, Jun 28, 2022 at 2:57 PM Athos Ribeiro
<email address hidden> wrote:
>
> Thanks for the review, Christian!
>
> > 56c301e * New changes: - d/control: depend on librust-uuid+rand-dev for
> > v4 feature.
> > The change to the new librust-uuid+rand-dev (>= 0.8.1) is fine for Debian
> > But since we want to become all-vendored do we want/need it here?
> > Would it make sense to split this into a salsa PR instead?
>
> This was already submitted and merged into Debian (it was not released yet though).

oO - I should know since I merged it :-)

> > 73d40a9 - d/rules: use vendorized dependencies for Ubuntu builds.
> > Nice use of /usr/share/dpkg/vendor.mk
> > ack for this as ubuntu delta
> > This part is a Debian no-op and could even be added there I guess.
>
> I submitted https://salsa.debian.org/debian/mdevctl/-/merge_requests/4 for this one.

merged

> > 3df8c59 - d/patches: drop dependency version tweaks in favor of vendorized
> > dependencies.
> > Maybe just disable it in d/p/series but do not remove the patch
> > That way you have less noise and will
> > a) easier rebase future versions
> > b) allow people to "go back for deb style build" more easily
> > This is up to you though, not enough to mark this won't fix
>
> +1 Done.
>
> > Back in the "debate rust MIR rules" we had discussed about ways for security
> > to track those inclcuded things. See https://github.com/cpaelzer/ubuntu-
> > mir/pull/3/files
> > Do you have a new build/buildlog so we can check to modify getting any of
> > that?
> >
>
> The current proposal is in a PPA at https://launchpad.net/~athos-ribeiro/+archive/ubuntu/mdevctl-mre/+packages
>
> > #1 We either want a .lock file (which dh-cargo deleted the one you get from
> > upstream and does IIRC not create a new one). The discussion there wasn't 100%
> > final so if that isn't working it might be ok but then it needs proper
> > mentioning in some Built-Using that works.
> >
> > #2 Other than those dependencies we also had the need to document "how to
> > refresh vendored code" in debian/README.source - you could drop an example how
> > uscan works with component=vendor in this case.
>
> I added a small comment in d/README.source to address #2.

Thanks, that part LGTM!

> I am working on a solution for #1 and will update this MP as soon as it is up.

[Christian Ehrhardt  (paelzer)]

On Tue, Jun 28, 2022 at 6:24 PM Athos Ribeiro
<email address hidden> wrote:
>
> MP updated to ship the cargo lockfile, as proposed in https://github.com/cpaelzer/ubuntu-mir/pull/3.

Nice, that looks cleaner than I thought, so you generate it right out
of the real vendor source that we added.
Awesome!

> PPA available at https://launchpad.net/~athos-ribeiro/+archive/ubuntu/mdevctl-vendored-plus-lockfile/+packages

Downloaded and checked, LGTM!
It is auto-compressed though since it is in the doc path - that is
fine but whatever checkers security had in mind need to be able to
deal with it.

Thanks, overall I think with that PPA we can go to security and MIR
team and ask if this can be approved as sufficient until the dh_cargo
tooling exists.

[Athos Ribeiro (athos-ribeiro)]

Merge Proposal updated to include a build-time test suite run with the vendorized dependencies.

[Christian Ehrhardt  (paelzer)]

Thanks, with the Rust rules landed I think this is now ready for review.
You could set it form WIP to "review"

[Christian Ehrhardt  (paelzer)]

FYI - if anyone crosses this MP, here an update.

We got the MIR approved by the MIR team

We have got a few smaller improvements to land (they are all generic, so we preferably land them in Debian) and will re-base this onto the latest Debian version then. Athos is working on those.

All of this is worked on while the security review is going on.

[Christian Ehrhardt  (paelzer)]

Please rebase for 1.2.0 - until then please mark it WIP to not clutter our to-be-reviewed list.

[Athos Ribeiro (athos-ribeiro)]

I rebased this one on top of 1.2.0. The PPA has been updated as well.

15f87ca... by Athos Ribeiro on 2022-08-29

    - d/control: remove librust-uuid B-D. This is now vendorized in this
      package and the new librust-uuid version in kinetic is currently
      incompatible.

1bcabcb... by Athos Ribeiro on 2022-08-29

update-maintainer

diff --git a/debian/README.source b/debian/README.source
index 9835852..e9161d2 100644
--- a/debian/README.source
+++ b/debian/README.source
@@ -1,3 +1,12 @@
+The debian/watch file was crafted with Multiple Upstream Tarball (MUT) support
+in mind. This was performed to account for the vendorized dependencies bundle,
+which is shipped by the upstream project as a separate tarball. To obtain the
+sources with the vendorized code and update the package when new upstream
+versions are available, a regular uscan/uupdate workflow will suffice. The
+"component" option in the debian/watch file will ensure the vendorized code is
+expanded in the expected "vendor" directory. Please, refer to the uscan docs
+and manpage for more information on MUT support.
+
 `wrap-and-sort -at` is the convention for d/control and other affected
 files to ensure auto-ordering, but with the benefit of having just one
 package per line giving the benefit of more readable diffs.
diff --git a/debian/changelog b/debian/changelog
index fec5934..2561c06 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,22 @@
+mdevctl (1.2.0-1ubuntu1) kinetic; urgency=medium
+
+  * d/watch: introduce vendor component with bundled dependencies.
+  * vendor: unpack vendorized sources.
+  * d/p/series: drop dependency version tweaks in favor of vendorized
+    dependencies.
+  * d/README.source: include information on uscan's Multiple Upstream
+    Tarball (MUT) support for the vendorized code.
+  * Ship Cargo lockfile to provide data on the vendorized code:
+    - d/config.toml: provide a custom Cargo configuration to generate
+      a lockfile from the vendorized dependencies.
+    - d/install: ship the build-time generated lockfile.
+  * d/copyright: include vendorized projects copyright data.
+  * d/control: remove librust-uuid B-D. This is now vendorized in this
+    package and the new librust-uuid version in kinetic is currently
+    incompatible.
+
+ -- Athos Ribeiro <[e-mail]>  Thu, 11 Aug 2022 11:54:53 -0300
+
 mdevctl (1.2.0-1) unstable; urgency=medium
 
   [ Athos Ribeiro ]
diff --git a/debian/config.toml b/debian/config.toml
new file mode 100644
index 0000000..ecda502
--- /dev/null
+++ b/debian/config.toml
@@ -0,0 +1,7 @@
+# Use the vendorized sources to produce the Cargo.lock file. This can be
+# performed by pointing $CARGO_HOME to the path containing this file.
+[source]
+[source.my-vendor-source]
+directory = "vendor"
+[source.crates-io]
+replace-with = "my-vendor-source"
diff --git a/debian/control b/debian/control
index 44c3b25..5810f31 100644
--- a/debian/control
+++ b/debian/control
@@ -1,7 +1,8 @@
 Source: mdevctl
 Section: admin
 Priority: optional
-Maintainer: Christian Ehrhardt <[e-mail]>
+Maintainer: Ubuntu Developers <[e-mail]>
+XSBC-Original-Maintainer: Christian Ehrhardt <[e-mail]>
 Rules-Requires-Root: no
 Build-Depends: cargo,
                debhelper-compat (= 13),
@@ -14,7 +15,6 @@ Build-Depends: cargo,
                librust-clap-complete-dev (>= 3.0.6),
                librust-clap+strsim-dev,
                librust-tempfile-dev (>= 3.1.0) <!nocheck>,
-               librust-uuid+rand-dev (>= 0.8.1),
                pkg-config,
                python3-docutils,
                systemd,
diff --git a/debian/copyright b/debian/copyright
index d71245b..92abbc2 100644
--- a/debian/copyright
+++ b/debian/copyright
@@ -10,6 +10,260 @@ Files: debian/*
 Copyright: 2019-2022 Christian Ehrhardt <[e-mail]>
 License: GPL-2
 
+Files: vendor/winapi-x86_64-pc-windows-gnu/*
+Copyright: 2015-2019 Peter Atashian <[e-mail]>
+           2015-2019 The winapi-rs Developers
+License: MIT or Apache-2.0
+
+Files: vendor/winapi/*
+Copyright: 2015-2019 Peter Atashian <[e-mail]>
+           2015-2019 The winapi-rs Developers
+License: MIT or Apache-2.0
+
+Files: vendor/anyhow/*
+Copyright: 2019 David Tolnay <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/serde/*
+Copyright: 2017-2018 Erick Tryzelaar <[e-mail]>
+           2017-2019 David Tolnay <[e-mail]>
+           2017-2022 Serde Developers
+License: MIT or Apache-2.0
+
+Files: vendor/strsim/*
+Copyright: Danny Guo <[e-mail]>
+ 2016 Titus Wormer <[e-mail]>
+ 2006-2009 Graydon Hoare
+ 2009-2013 Mozilla Foundation
+License: MIT
+
+Files: vendor/regex-syntax/*
+Copyright: 2014-2019 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/regex-syntax/src/unicode_tables/*
+Copyright: 1991-2018 Unicode, Inc. All rights reserved.
+License: Unicode
+
+Files: vendor/termcolor/*
+Copyright: 2015 Andrew Gallant <[e-mail]>
+License: Unlicense or MIT
+
+Files: vendor/proc-macro-error-attr/*
+Copyright: 2019-2020 CreepySkeleton <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/log/*
+Copyright: 2014-2015 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/env_logger/*
+Copyright: 2014-2019 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/syn/*
+Copyright:
+ 2016-2019 David Tolnay <[e-mail]>
+ 2016-2019 Syn Developers
+License: MIT or Apache-2.0
+
+Files: vendor/ryu/*
+Copyright:
+ 2018-2020 David Tolnay <[e-mail]>
+ 2018 Ulf Adams
+License: Apache-2.0 or BSL-1.0
+
+Files: vendor/autocfg/*
+Copyright: 2018 Josh Stone <[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/regex/*
+Copyright: 2014-2018 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/itoa/*
+Copyright: 2016-2021 David Tolnay <[e-mail]>
+           2016-2021 Itoa Developers
+License: MIT or Apache-2.0
+
+Files: vendor/bitflags/*
+Copyright: 2014-2018 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/quote/*
+Copyright:
+ 2016-2019 David Tolnay <[e-mail]>
+ 2016 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/cfg-if/*
+Copyright: 2014-2019 Alex Crichton <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/winapi-util/*
+Copyright: 2017 Andrew Gallant <[e-mail]>
+License: Unlicense or MIT
+
+Files: vendor/libc/*
+Copyright: 2012-2020 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/atty/*
+Copyright: 2015-2019 Doug Tangren
+License: MIT
+
+Files: vendor/wasi/*
+Copyright: 2018 The Cranelift Project Developers
+License: MIT or Apache-2.0 or APACHE-2-LLVM-EXCEPTIONS
+
+Files: vendor/uuid/*
+Copyright:
+ 2013-2014 The Rust Project Developers
+ 2018 The Uuid Project Developers
+ 2013-2018 Ashley Mannix<[e-mail]>
+ 2013-2018 Christopher Armstrong
+ 2013-2018 Dylan DPC<[e-mail]>
+ 2013-2018 Hunar Roop Kahlon<[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/textwrap/*
+Copyright: 2016 Martin Geisler <[e-mail]>
+License: MIT
+
+Files: vendor/version_check/*
+Copyright: Sergio Benitez <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/aho-corasick/*
+Copyright: 2015-2020 Andrew Gallant <[e-mail]>
+License: Unlicense or MIT
+
+Files: vendor/clap/*
+Copyright: 2015-2020 Kevin B. Knapp <[e-mail]>
+License: MIT
+
+Files: vendor/clap/src/parser/matches/arg_matches.rs
+Copyright: 2015 The Rust Project Developers
+License: MIT
+
+Files: vendor/clap/src/macros.rs
+Copyright:
+ 2015 grabbag contributors
+ 2015-2020 Kevin B. Knapp <[e-mail]>
+License: MIT
+
+Files: vendor/humantime/*
+Copyright:
+ 2016-2018 Paul Colomiets <[e-mail]>
+ 2016 The humantime Developers
+ 2016 Pyfisch
+ 2005-2013 Rich Felker
+License: MIT or Apache-2.0
+
+Files: vendor/getrandom/*
+Copyright:
+ 2018-2021 Developers of the Rand project
+ 2014 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/remove_dir_all/*
+Copyright: 2017 Aaron Power <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/memchr/*
+Copyright: 2015 Andrew Gallant <[e-mail]>
+ bluss
+License: Unlicense or MIT
+
+Files: vendor/serde_json/*
+Copyright: 2014-2019 Serde Developers
+License: MIT or Apache-2.0
+
+Files: vendor/redox_syscall/*
+Copyright:
+ 2017-2019 Jeremy Soller <[e-mail]>
+ 2017-2019 Redox OS Developers
+License: MIT
+
+Files: vendor/hermit-abi/*
+Copyright: 2019 Stefan Lankes
+License: MIT or Apache-2.0
+
+Files: vendor/proc-macro2/*
+Copyright:
+ 2014-2020 Alex Crichton <[e-mail]>
+ 2017-2020 David Tolnay <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/winapi-i686-pc-windows-gnu/*
+Copyright: 2015-2019 Peter Atashian <[e-mail]>
+           2015-2019 The winapi-rs Developers
+License: MIT or Apache-2.0
+
+Files: vendor/tempfile/*
+Copyright:
+ 2015-2020 Steven Allen <[e-mail]>
+ 2015-2018 Ashley Mannix <[e-mail]>
+ 2015-2019 Jason White <[e-mail]>
+ 2013-2020 The Rust Project Developers
+License: MIT or Apache-2.0
+
+Files: vendor/proc-macro-error/*
+Copyright:
+ 2019-2020 CreepySkeleton <[e-mail]>
+ 2019-2020 Debian Rust Maintainers <[e-mail]>
+ 2019-2020 kpcyrd <[e-mail]>
+ 2020 Daniel Kahn Gillmor <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/hashbrown/*
+Copyright: 2018-2019 Amanieu d'Antras <[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/heck/*
+Copyright: 2015-2021 Without Boats <[e-mail]>
+License: MIT or Apache-2.0
+
+Files: vendor/indexmap/*
+Copyright:
+ 2016-2020 bluss
+ 2017-2020 Josh Stone <[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/clap_complete/*
+Copyright: 2015-2022 Kevin B. Knapp and Clap Contributors
+License: Apache-2.0 or MIT
+
+Files: vendor/clap_derive/*
+Copyright: 2015-2022 Kevin B. Knapp and Clap Contributors
+License: Apache-2.0 or MIT
+
+Files: vendor/clap_lex/*
+Copyright: 2015-2022 Kevin B. Knapp and Clap Contributors
+License: Apache-2.0 or MIT
+
+Files: vendor/fastrand/*
+Copyright: 2018 Stjepan Glavina <[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/instant/*
+Copyright: 2018 Sébastien Crozet <[e-mail]>
+License: BSD-3-clause
+
+Files: vendor/once_cell/*
+Copyright: 2018 Aleksey Kladov <[e-mail]>
+License: Apache-2.0 or MIT
+
+Files: vendor/os_str_bytes/*
+Copyright: 2019 dylni
+License: Apache-2.0 or MIT
+
+Files: vendor/unicode-ident/*
+Copyright:
+ 2018 David Tolnay <[e-mail]>
+ 1991-2022 Unicode, Inc. All rights reserved.
+License: Apache-2.0 or MIT, and Unicode
+
 License:   LGPL-2.1
  Licensed under the GNU Lesser General Public License aka LGPL v2.1.
  See [COPYING](COPYING) for details.
@@ -21,3 +275,179 @@ License: GPL-2
  This software is released under the terms of the GNU General Public
  License version 2, which on Debian systems can be found in the file
  '/usr/share/common-licenses/GPL-2'.
+
+License: MIT
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+ .
+ The above copyright notice and this permission notice shall be included in all
+ copies or substantial portions of the Software.
+ .
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+
+License: Unlicense
+ This is free and unencumbered software released into the public domain.
+ .
+ Anyone is free to copy, modify, publish, use, compile, sell, or
+ distribute this software, either in source code form or as a compiled
+ binary, for any purpose, commercial or non-commercial, and by any
+ means.
+ .
+ In jurisdictions that recognize copyright laws, the author or authors
+ of this software dedicate any and all copyright interest in the
+ software to the public domain. We make this dedication for the benefit
+ of the public at large and to the detriment of our heirs and
+ successors. We intend this dedication to be an overt act of
+ relinquishment in perpetuity of all present and future rights to this
+ software under copyright law.
+ .
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ OTHER DEALINGS IN THE SOFTWARE.
+
+License: Apache-2.0
+ Debian systems provide the Apache 2.0 license in
+ /usr/share/common-licenses/Apache-2.0
+
+License: Unicode
+ UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE
+ .
+ Unicode Data Files include all data files under the directories
+ http://www.unicode.org/Public/, http://www.unicode.org/reports/,
+ http://www.unicode.org/cldr/data/, http://source.icu-project.org/repos/icu/, and
+ http://www.unicode.org/utility/trac/browser/.
+ .
+ Unicode Data Files do not include PDF online code charts under the
+ directory http://www.unicode.org/Public/.
+ .
+ Software includes any source code published in the Unicode Standard
+ or under the directories
+ http://www.unicode.org/Public/, http://www.unicode.org/reports/,
+ http://www.unicode.org/cldr/data/, http://source.icu-project.org/repos/icu/, and
+ http://www.unicode.org/utility/trac/browser/.
+ .
+ NOTICE TO USER: Carefully read the following legal agreement.
+ BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S
+ DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),
+ YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
+ TERMS AND CONDITIONS OF THIS AGREEMENT.
+ IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE
+ THE DATA FILES OR SOFTWARE.
+ .
+ COPYRIGHT AND PERMISSION NOTICE
+ .
+ Copyright © 1991-2018 Unicode, Inc. All rights reserved.
+ Distributed under the Terms of Use in http://www.unicode.org/copyright.html.
+ .
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of the Unicode data files and any associated documentation
+ (the "Data Files") or Unicode software and any associated documentation
+ (the "Software") to deal in the Data Files or Software
+ without restriction, including without limitation the rights to use,
+ copy, modify, merge, publish, distribute, and/or sell copies of
+ the Data Files or Software, and to permit persons to whom the Data Files
+ or Software are furnished to do so, provided that either
+ (a) this copyright and permission notice appear with all copies
+ of the Data Files or Software, or
+ (b) this copyright and permission notice appear in associated
+ Documentation.
+ .
+ THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF
+ ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+ WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT OF THIRD PARTY RIGHTS.
+ IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS
+ NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL
+ DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ PERFORMANCE OF THE DATA FILES OR SOFTWARE.
+ .
+ Except as contained in this notice, the name of a copyright holder
+ shall not be used in advertising or otherwise to promote the sale,
+ use or other dealings in these Data Files or Software without prior
+ written authorization of the copyright holder.
+
+License: BSL-1.0
+ Boost Software License - Version 1.0 - August 17th, 2003
+ .
+ Permission is hereby granted, free of charge, to any person or organization
+ obtaining a copy of the software and accompanying documentation covered by
+ this license (the "Software") to use, reproduce, display, distribute,
+ execute, and transmit the Software, and to prepare derivative works of the
+ Software, and to permit third-parties to whom the Software is furnished to
+ do so, all subject to the following:
+ .
+ The copyright notices in the Software and this entire statement, including
+ the above license grant, this restriction and the following disclaimer,
+ must be included in all copies of the Software, in whole or in part, and
+ all derivative works of the Software, unless such copies or derivative
+ works are solely in the form of machine-executable object code generated by
+ a source language processor.
+ .
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
+ SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
+ FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
+ ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ DEALINGS IN THE SOFTWARE.
+
+License: APACHE-2-LLVM-EXCEPTIONS
+ On Debian systems the full text of the Apache Software License 2.0 can be
+ found in the `/usr/share/common-licenses/Apache-2.0' file.
+ .
+ ---- LLVM Exceptions to the Apache 2.0 License ----
+ .
+ As an exception, if, as a result of your compiling your source code, portions
+ of this Software are embedded into an Object form of such source code, you
+ may redistribute such embedded portions in such Object form without complying
+ with the conditions of Sections 4(a), 4(b) and 4(d) of the License.
+ .
+ In addition, if you combine or link compiled forms of this Software with
+ software that is licensed under the GPLv2 ("Combined Software") and if a
+ court of competent jurisdiction determines that the patent provision (Section
+ 3), the indemnity provision (Section 9) or other Section of the License
+ conflicts with the conditions of the GPLv2, you may retroactively and
+ prospectively choose to deem waived or otherwise exclude such Section(s) of
+ the License, but only in their entirety and only with respect to the Combined
+ Software.
+
+License: BSD-3-clause
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+ 1. Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+ 2. Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+ 3. Neither the name of the University nor the names of its contributors
+    may be used to endorse or promote products derived from this software
+    without specific prior written permission.
+ .
+ THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ SUCH DAMAGE.
diff --git a/debian/install b/debian/install
new file mode 100644
index 0000000..7f858c7
--- /dev/null
+++ b/debian/install
@@ -0,0 +1 @@
+Cargo.lock /usr/share/doc/mdevctl
diff --git a/debian/patches/series b/debian/patches/series
index f658191..7f0629b 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -1,2 +1,2 @@
-lower-versions-for-unstable.patch
+# lower-versions-for-unstable.patch
 main-binary-already-installed.patch
diff --git a/debian/watch b/debian/watch
index b30bd79..b6c4aee 100644
--- a/debian/watch
+++ b/debian/watch
@@ -1,3 +1,5 @@
 version=4
 opts=filenamemangle=s/.+\/v?(\d\S+)\.tar\.gz/mdevctl-$1\.tar\.gz/ \
-  https://github.com/mdevctl/mdevctl/tags .*/v?(\d\S+)\.tar\.gz
+  https://github.com/mdevctl/mdevctl/releases/latest .*/v@ANY_VERSION@\.tar\.gz debian
+opts=component=vendor \
+  https://github.com/mdevctl/mdevctl/releases/latest .*/@PACKAGE@@ANY_VERSION@-vendor\.tar\.gz ignore
diff --git a/vendor/aho-corasick/.cargo-checksum.json b/vendor/aho-corasick/.cargo-checksum.json
new file mode 100644
index 0000000..ec143d7
--- /dev/null
+++ b/vendor/aho-corasick/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.toml":"f61283fd900435313b9ba8c1b87a4b5b31d442f9b554222136ec8d1d3d1e39d8","DESIGN.md":"9065f33d818d1562244d36dc4781e2a351108030cee17f11c2ba512ca7b4c27e","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","README.md":"741e7249c8d1d6a7ba9341d68253dbf4952477c5620ff37c5325f2e894b148b6","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","rustfmt.toml":"1ca600239a27401c4a43f363cf3f38183a212affc1f31bff3ae93234bbaec228","src/ahocorasick.rs":"6fcbe812eec7af44b104c6b8a27b0a2ea8d67c3d9aec73cb69d802b30be5f005","src/automaton.rs":"610b3e2c104c51bf4f51a6d07626c3972e9d1274ca276e987385a231b284cc8b","src/buffer.rs":"dae7ee7c1f846ca9cf115ba4949484000e1837b4fb7311f8d8c9a35011c9c26f","src/byte_frequencies.rs":"2fb85b381c038c1e44ce94294531cdcd339dca48b1e61f41455666e802cbbc9e","src/classes.rs":"99a53a2ed8eea8c13699def90e31dfdff9d0b90572b1db3cb534e3396e7a0ed0","src/dfa.rs":"25e4455b3e179a7e192108d05f3683993456b36e3ebed99f827558c52525b7e6","src/error.rs":"d34c2c9c815df5d9dedc46b4b3ce109cd2cee07825de643f0c574ec960367beb","src/lib.rs":"f0c48b0ee093dd8b3034d025d052c3667860c5d4a196cb178588012b719acea4","src/nfa.rs":"2f443951c78196126bfd237ed5770a69077e6190daeecd47131339c25e51a3d0","src/packed/api.rs":"ec58ff1b4375dd4ff88fb5859c7ede994fe08d31b7d3677720a086592aa0fe53","src/packed/mod.rs":"d7ee11d487a7f129f16dc8f1473442a7127905933f378504bae83df0f23c5e2a","src/packed/pattern.rs":"3abf3835d4c4f8a43753c52936a894d819f713f233fc046e19de5ef95200dcce","src/packed/rabinkarp.rs":"caf9563b7442c9b75c9cb520fa236c7a6da8173705889b8d79b69ede14a20767","src/packed/teddy/README.md":"5819f40d221af93288e705eadef5393a41d7a0900881b4d676e01fd65d5adf15","src/packed/teddy/compile.rs":"aad40b3f93d2c388b409b31fb2795d414a365237789d5b1a7510d97ceb8ce260","src/packed/teddy/mod.rs":"83b52bd80272970ad17234d0db293d17c1710ec582302bf516b203c8edec037e","src/packed/teddy/runtime.rs":"836146e90b320b14fa2c65fe4af7915a41f6fb04408aac5fac731c22ff46adae","src/packed/tests.rs":"b8dc4d3281ecd6d0fa2bf7ef16cf292a467dfdce64e470c7921e983bfa60fee2","src/packed/vector.rs":"ab3c0535fca5f09198d58cbfae44c292aeb3ce44bc92bca36d30dc72963639fc","src/prefilter.rs":"82a3eb6d5c0c3f10bc8d5f57d55d6d14cf4cf21c475bb5253e1921084063b8d7","src/state_id.rs":"519ec8c7bf3fa72103d4c561c193759759f535dca924c9853efe630f406d2029","src/tests.rs":"6522ed1b244513c01de5bbcf0fe35571454fdea2c2a9d8dfe13a04bf57b70eca"},"package":"1e37cfd5e7657ada45f742d6e99ca5788580b5c529dc78faf11ece6dc702656f"}
\ No newline at end of file
diff --git a/vendor/aho-corasick/COPYING b/vendor/aho-corasick/COPYING
new file mode 100644
index 0000000..bb9c20a
--- /dev/null
+++ b/vendor/aho-corasick/COPYING
@@ -0,0 +1,3 @@
+This project is dual-licensed under the Unlicense and MIT licenses.
+
+You may use this code under the terms of either license.
diff --git a/vendor/aho-corasick/Cargo.toml b/vendor/aho-corasick/Cargo.toml
new file mode 100644
index 0000000..62b5f7e
--- /dev/null
+++ b/vendor/aho-corasick/Cargo.toml
@@ -0,0 +1,43 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+edition = "2018"
+name = "aho-corasick"
+version = "0.7.18"
+authors = ["Andrew Gallant <[e-mail]>"]
+exclude = ["/aho-corasick-debug", "/ci/*", "/.travis.yml", "/appveyor.yml"]
+autotests = false
+description = "Fast multiple substring searching."
+homepage = "https://github.com/BurntSushi/aho-corasick"
+readme = "README.md"
+keywords = ["string", "search", "text", "aho", "multi"]
+categories = ["text-processing"]
+license = "Unlicense/MIT"
+repository = "https://github.com/BurntSushi/aho-corasick"
+[profile.bench]
+debug = true
+
+[profile.release]
+debug = true
+
+[lib]
+name = "aho_corasick"
+[dependencies.memchr]
+version = "2.4.0"
+default-features = false
+
+[dev-dependencies]
+
+[features]
+default = ["std"]
+std = ["memchr/std"]
diff --git a/vendor/aho-corasick/DESIGN.md b/vendor/aho-corasick/DESIGN.md
new file mode 100644
index 0000000..367e203
--- /dev/null
+++ b/vendor/aho-corasick/DESIGN.md
@@ -0,0 +1,483 @@
+This document describes the internal design of this crate, which is an object
+lesson in what happens when you take a fairly simple old algorithm like
+Aho-Corasick and make it fast and production ready.
+
+The target audience of this document is Rust programmers that have some
+familiarity with string searching, however, one does not need to know the
+Aho-Corasick algorithm in order to read this (it is explained below). One
+should, however, know what a trie is. (If you don't, go read its Wikipedia
+article.)
+
+The center-piece of this crate is an implementation of Aho-Corasick. On its
+own, Aho-Corasick isn't that complicated. The complex pieces come from the
+different variants of Aho-Corasick implemented in this crate. Specifically,
+they are:
+
+* Aho-Corasick as an NFA, using dense transitions near the root with sparse
+  transitions elsewhere.
+* Aho-Corasick as a DFA. (An NFA is slower to search, but cheaper to construct
+  and uses less memory.)
+  * A DFA with pre-multiplied state identifiers. This saves a multiplication
+    instruction in the core search loop.
+  * A DFA with equivalence classes of bytes as the alphabet, instead of the
+    traditional 256-byte alphabet. This shrinks the size of the DFA in memory,
+    but adds an extra lookup in the core search loop to map the input byte to
+    an equivalent class.
+* The option to choose how state identifiers are represented, via one of
+  u8, u16, u32, u64 or usize. This permits creating compact automatons when
+  matching a small number of patterns.
+* Supporting "standard" match semantics, along with its overlapping variant,
+  in addition to leftmost-first and leftmost-longest semantics. The "standard"
+  semantics are typically what you see in a textbook description of
+  Aho-Corasick. However, Aho-Corasick is also useful as an optimization in
+  regex engines, which often use leftmost-first or leftmost-longest semantics.
+  Thus, it is useful to implement those semantics here. The "standard" and
+  "leftmost" search algorithms are subtly different, and also require slightly
+  different construction algorithms.
+* Support for ASCII case insensitive matching.
+* Support for accelerating searches when the patterns all start with a small
+  number of fixed bytes. Or alternatively, when the  patterns all contain a
+  small number of rare bytes. (Searching for these bytes uses SIMD vectorized
+  code courtesy of `memchr`.)
+* Transparent support for alternative SIMD vectorized search routines for
+  smaller number of literals, such as the Teddy algorithm. We called these
+  "packed" search routines because they use SIMD. They can often be an order of
+  magnitude faster than just Aho-Corasick, but don't scale as well.
+* Support for searching streams. This can reuse most of the underlying code,
+  but does require careful buffering support.
+* Support for anchored searches, which permit efficient `is_prefix` checks for
+  a large number of patterns.
+
+When you combine all of this together along with trying to make everything as
+fast as possible, what you end up with is enitrely too much code with too much
+`unsafe`. Alas, I was not smart enough to figure out how to reduce it. Instead,
+we will explain it.
+
+
+# Basics
+
+The fundamental problem this crate is trying to solve is to determine the
+occurrences of possibly many patterns in a haystack. The naive way to solve
+this is to look for a match for each pattern at each position in the haystack:
+
+    for i in 0..haystack.len():
+      for p in patterns.iter():
+        if haystack[i..].starts_with(p.bytes()):
+          return Match(p.id(), i, i + p.bytes().len())
+
+Those four lines are effectively all this crate does. The problem with those
+four lines is that they are very slow, especially when you're searching for a
+large number of patterns.
+
+While there are many different algorithms available to solve this, a popular
+one is Aho-Corasick. It's a common solution because it's not too hard to
+implement, scales quite well even when searching for thousands of patterns and
+is generally pretty fast. Aho-Corasick does well here because, regardless of
+the number of patterns you're searching for, it always visits each byte in the
+haystack exactly once. This means, generally speaking, adding more patterns to
+an Aho-Corasick automaton does not make it slower. (Strictly speaking, however,
+this is not true, since a larger automaton will make less effective use of the
+CPU's cache.)
+
+Aho-Corasick can be succinctly described as a trie with state transitions
+between some of the nodes that efficiently instruct the search algorithm to
+try matching alternative keys in the automaton. The trick is that these state
+transitions are arranged such that each byte of input needs to be inspected
+only once. These state transitions are typically called "failure transitions,"
+because they instruct the searcher (the thing traversing the automaton while
+reading from the haystack) what to do when a byte in the haystack does not
+correspond to a valid transition in the current state of the trie.
+
+More formally, a failure transition points to a state in the automaton that may
+lead to a match whose prefix is a proper suffix of the path traversed through
+the trie so far. (If no such proper suffix exists, then the failure transition
+points back to the start state of the trie, effectively restarting the search.)
+This is perhaps simpler to explain pictorally. For example, let's say we built
+an Aho-Corasick automaton with the following patterns: 'abcd' and 'cef'. The
+trie looks like this:
+
+         a - S1 - b - S2 - c - S3 - d - S4*
+        /
+    S0 - c - S5 - e - S6 - f - S7*
+
+where states marked with a `*` are match states (meaning, the search algorithm
+should stop and report a match to the caller).
+
+So given this trie, it should be somewhat straight-forward to see how it can
+be used to determine whether any particular haystack *starts* with either
+`abcd` or `cef`. It's easy to express this in code:
+
+    fn has_prefix(trie: &Trie, haystack: &[u8]) -> bool {
+      let mut state_id = trie.start();
+      // If the empty pattern is in trie, then state_id is a match state.
+      if trie.is_match(state_id) {
+        return true;
+      }
+      for (i, &b) in haystack.iter().enumerate() {
+        state_id = match trie.next_state(state_id, b) {
+          Some(id) => id,
+          // If there was no transition for this state and byte, then we know
+          // the haystack does not start with one of the patterns in our trie.
+          None => return false,
+        };
+        if trie.is_match(state_id) {
+          return true;
+        }
+      }
+      false
+    }
+
+And that's pretty much it. All we do is move through the trie starting with the
+bytes at the beginning of the haystack. If we find ourselves in a position
+where we can't move, or if we've looked through the entire haystack without
+seeing a match state, then we know the haystack does not start with any of the
+patterns in the trie.
+
+The meat of the Aho-Corasick algorithm is in how we add failure transitions to
+our trie to keep searching efficient. Specifically, it permits us to not only
+check whether a haystack *starts* with any one of a number of patterns, but
+rather, whether the haystack contains any of a number of patterns *anywhere* in
+the haystack.
+
+As mentioned before, failure transitions connect a proper suffix of the path
+traversed through the trie before, with a path that leads to a match that has a
+prefix corresponding to that proper suffix. So in our case, for patterns `abcd`
+and `cef`, with a haystack `abcef`, we want to transition to state `S5` (from
+the diagram above) from `S3` upon seeing that the byte following `c` is not
+`d`. Namely, the proper suffix in this example is `c`, which is a prefix of
+`cef`. So the modified diagram looks like this:
+
+
+         a - S1 - b - S2 - c - S3 - d - S4*
+        /                      /
+       /       ----------------
+      /       /
+    S0 - c - S5 - e - S6 - f - S7*
+
+One thing that isn't shown in this diagram is that *all* states have a failure
+transition, but only `S3` has a *non-trivial* failure transition. That is, all
+other states have a failure transition back to the start state. So if our
+haystack was `abzabcd`, then the searcher would transition back to `S0` after
+seeing `z`, which effectively restarts the search. (Because there is no pattern
+in our trie that has a prefix of `bz` or `z`.)
+
+The code for traversing this *automaton* or *finite state machine* (it is no
+longer just a trie) is not that much different from the `has_prefix` code
+above:
+
+    fn contains(fsm: &FiniteStateMachine, haystack: &[u8]) -> bool {
+      let mut state_id = fsm.start();
+      // If the empty pattern is in fsm, then state_id is a match state.
+      if fsm.is_match(state_id) {
+        return true;
+      }
+      for (i, &b) in haystack.iter().enumerate() {
+        // While the diagram above doesn't show this, we may wind up needing
+        // to follow multiple failure transitions before we land on a state
+        // in which we can advance. Therefore, when searching for the next
+        // state, we need to loop until we don't see a failure transition.
+        //
+        // This loop terminates because the start state has no empty
+        // transitions. Every transition from the start state either points to
+        // another state, or loops back to the start state.
+        loop {
+          match fsm.next_state(state_id, b) {
+            Some(id) => {
+              state_id = id;
+              break;
+            }
+            // Unlike our code above, if there was no transition for this
+            // state, then we don't quit. Instead, we look for this state's
+            // failure transition and follow that instead.
+            None => {
+              state_id = fsm.next_fail_state(state_id);
+            }
+          };
+        }
+        if fsm.is_match(state_id) {
+          return true;
+        }
+      }
+      false
+    }
+
+Other than the complication around traversing failure transitions, this code
+is still roughly "traverse the automaton with bytes from the haystack, and quit
+when a match is seen."
+
+And that concludes our section on the basics. While we didn't go deep into
+how the automaton is built (see `src/nfa.rs`, which has detailed comments about
+that), the basic structure of Aho-Corasick should be reasonably clear.
+
+
+# NFAs and DFAs
+
+There are generally two types of finite automata: non-deterministic finite
+automata (NFA) and deterministic finite automata (DFA). The difference between
+them is, principally, that an NFA can be in multiple states at once. This is
+typically accomplished by things called _epsilon_ transitions, where one could
+move to a new state without consuming any bytes from the input. (The other
+mechanism by which NFAs can be in more than one state is where the same byte in
+a particular state transitions to multiple distinct states.) In contrast, a DFA
+can only ever be in one state at a time. A DFA has no epsilon transitions, and
+for any given state, a byte transitions to at most one other state.
+
+By this formulation, the Aho-Corasick automaton described in the previous
+section is an NFA. This is because failure transitions are, effectively,
+epsilon transitions. That is, whenever the automaton is in state `S`, it is
+actually in the set of states that are reachable by recursively following
+failure transitions from `S`. (This means that, for example, the start state
+is always active since the start state is reachable via failure transitions
+from any state in the automaton.)
+
+NFAs have a lot of nice properties. They tend to be easier to construct, and
+also tend to use less memory. However, their primary downside is that they are
+typically slower to execute. For example, the code above showing how to search
+with an Aho-Corasick automaton needs to potentially iterate through many
+failure transitions for every byte of input. While this is a fairly small
+amount of overhead, this can add up, especially if the automaton has a lot of
+overlapping patterns with a lot of failure transitions.
+
+A DFA's search code, by contrast, looks like this:
+
+    fn contains(dfa: &DFA, haystack: &[u8]) -> bool {
+      let mut state_id = dfa.start();
+      // If the empty pattern is in dfa, then state_id is a match state.
+      if dfa.is_match(state_id) {
+        return true;
+      }
+      for (i, &b) in haystack.iter().enumerate() {
+        // An Aho-Corasick DFA *never* has a missing state that requires
+        // failure transitions to be followed. One byte of input advances the
+        // automaton by one state. Always.
+        state_id = trie.next_state(state_id, b);
+        if fsm.is_match(state_id) {
+          return true;
+        }
+      }
+      false
+    }
+
+The search logic here is much simpler than for the NFA, and this tends to
+translate into significant performance benefits as well, since there's a lot
+less work being done for each byte in the haystack. How is this accomplished?
+It's done by pre-following all failure transitions for all states for all bytes
+in the alphabet, and then building a single state transition table. Building
+this DFA can be much more costly than building the NFA, and use much more
+memory, but the better performance can be worth it.
+
+Users of this crate can actually choose between using an NFA or a DFA. By
+default, an NFA is used, because it typically strikes the best balance between
+space usage and search performance. But the DFA option is available for cases
+where a little extra memory and upfront time building the automaton is okay.
+For example, the `AhoCorasick::auto_configure` and
+`AhoCorasickBuilder::auto_configure` methods will enable the DFA setting if
+there are a small number of patterns.
+
+
+# More DFA tricks
+
+As described in the previous section, one of the downsides of using a DFA
+is that is uses more memory and can take longer to build. One small way of
+mitigating these concerns is to map the alphabet used by the automaton into
+a smaller space. Typically, the alphabet of a DFA has 256 elements in it:
+one element for each possible value that fits into a byte. However, in many
+cases, one does not need the full alphabet. For example, if all patterns in an
+Aho-Corasick automaton are ASCII letters, then this only uses up 52 distinct
+bytes. As far as the automaton is concerned, the rest of the 204 bytes are
+indistinguishable from one another: they will never disrciminate between a
+match or a non-match. Therefore, in cases like that, the alphabet can be shrunk
+to just 53 elements. One for each ASCII letter, and then another to serve as a
+placeholder for every other unused byte.
+
+In practice, this library doesn't quite compute the optimal set of equivalence
+classes, but it's close enough in most cases. The key idea is that this then
+allows the transition table for the DFA to be potentially much smaller. The
+downside of doing this, however, is that since the transition table is defined
+in terms of this smaller alphabet space, every byte in the haystack must be
+re-mapped to this smaller space. This requires an additional 256-byte table.
+In practice, this can lead to a small search time hit, but it can be difficult
+to measure. Moreover, it can sometimes lead to faster search times for bigger
+automata, since it could be difference between more parts of the automaton
+staying in the CPU cache or not.
+
+One other trick for DFAs employed by this crate is the notion of premultiplying
+state identifiers. Specifically, the normal way to compute the next transition
+in a DFA is via the following (assuming that the transition table is laid out
+sequentially in memory, in row-major order, where the rows are states):
+
+    next_state_id = dfa.transitions[current_state_id * 256 + current_byte]
+
+However, since the value `256` is a fixed constant, we can actually premultiply
+the state identifiers in the table when we build the table initially. Then, the
+next transition computation simply becomes:
+
+    next_state_id = dfa.transitions[current_state_id + current_byte]
+
+This doesn't seem like much, but when this is being executed for every byte of
+input that you're searching, saving that extra multiplication instruction can
+add up.
+
+The same optimization works even when equivalence classes are enabled, as
+described above. The only difference is that the premultiplication is by the
+total number of equivalence classes instead of 256.
+
+There isn't much downside to premultiplying state identifiers, other than the
+fact that you may need to choose a bigger integer representation than you would
+otherwise. For example, if you don't premultiply state identifiers, then an
+automaton that uses `u8` as a state identifier can hold up to 256 states.
+However, if they are premultiplied, then it can only hold up to
+`floor(256 / len(alphabet))` states. Thus premultiplication impacts how compact
+your DFA can be. In practice, it's pretty rare to use `u8` as a state
+identifier, so premultiplication is usually a good thing to do.
+
+Both equivalence classes and premultiplication are tuneable parameters via the
+`AhoCorasickBuilder` type, and both are enabled by default.
+
+
+# Match semantics
+
+One of the more interesting things about this implementation of Aho-Corasick
+that (as far as this author knows) separates it from other implementations, is
+that it natively supports leftmost-first and leftmost-longest match semantics.
+Briefly, match semantics refer to the decision procedure by which searching
+will disambiguate matches when there are multiple to choose from:
+
+* **standard** match semantics emits matches as soon as they are detected by
+  the automaton. This is typically equivalent to the textbook non-overlapping
+  formulation of Aho-Corasick.
+* **leftmost-first** match semantics means that 1) the next match is the match
+  starting at the leftmost position and 2) among multiple matches starting at
+  the same leftmost position, the match corresponding to the pattern provided
+  first by the caller is reported.
+* **leftmost-longest** is like leftmost-first, except when there are multiple
+  matches starting at the same leftmost position, the pattern corresponding to
+  the longest match is returned.
+
+(The crate API documentation discusses these differences, with examples, in
+more depth on the `MatchKind` type.)
+
+The reason why supporting these match semantics is important is because it
+gives the user more control over the match procedure. For example,
+leftmost-first permits users to implement match priority by simply putting the
+higher priority patterns first. Leftmost-longest, on the other hand, permits
+finding the longest possible match, which might be useful when trying to find
+words matching a dictionary. Additionally, regex engines often want to use
+Aho-Corasick as an optimization when searching for an alternation of literals.
+In order to preserve correct match semantics, regex engines typically can't use
+the standard textbook definition directly, since regex engines will implement
+either leftmost-first (Perl-like) or leftmost-longest (POSIX) match semantics.
+
+Supporting leftmost semantics requires a couple key changes:
+
+* Constructing the Aho-Corasick automaton changes a bit in both how the trie is
+  constructed and how failure transitions are found. Namely, only a subset of
+  the failure transitions are added. Specifically, only the failure transitions
+  that either do not occur after a match or do occur after a match but preserve
+  that match are kept. (More details on this can be found in `src/nfa.rs`.)
+* The search algorithm changes slightly. Since we are looking for the leftmost
+  match, we cannot quit as soon as a match is detected. Instead, after a match
+  is detected, we must keep searching until either the end of the input or
+  until a dead state is seen. (Dead states are not used for standard match
+  semantics. Dead states mean that searching should stop after a match has been
+  found.)
+
+Other implementations of Aho-Corasick do support leftmost match semantics, but
+they do it with more overhead at search time, or even worse, with a queue of
+matches and sophisticated hijinks to disambiguate the matches. While our
+construction algorithm becomes a bit more complicated, the correct match
+semantics fall out from the structure of the automaton itself.
+
+
+# Overlapping matches
+
+One of the nice properties of an Aho-Corasick automaton is that it can report
+all possible matches, even when they overlap with one another. In this mode,
+the match semantics don't matter, since all possible matches are reported.
+Overlapping searches work just like regular searches, except the state
+identifier at which the previous search left off is carried over to the next
+search, so that it can pick up where it left off. If there are additional
+matches at that state, then they are reported before resuming the search.
+
+Enabling leftmost-first or leftmost-longest match semantics causes the
+automaton to use a subset of all failure transitions, which means that
+overlapping searches cannot be used. Therefore, if leftmost match semantics are
+used, attempting to do an overlapping search will panic. Thus, to get
+overlapping searches, the caller must use the default standard match semantics.
+This behavior was chosen because there are only two alternatives, which were
+deemed worse:
+
+* Compile two automatons internally, one for standard semantics and one for
+  the semantics requested by the caller (if not standard).
+* Create a new type, distinct from the `AhoCorasick` type, which has different
+  capabilities based on the configuration options.
+
+The first is untenable because of the amount of memory used by the automaton.
+The second increases the complexity of the API too much by adding too many
+types that do similar things. It is conceptually much simpler to keep all
+searching isolated to a single type. Callers may query whether the automaton
+supports overlapping searches via the `AhoCorasick::supports_overlapping`
+method.
+
+
+# Stream searching
+
+Since Aho-Corasick is an automaton, it is possible to do partial searches on
+partial parts of the haystack, and then resume that search on subsequent pieces
+of the haystack. This is useful when the haystack you're trying to search is
+not stored contiguous in memory, or if one does not want to read the entire
+haystack into memory at once.
+
+Currently, only standard semantics are supported for stream searching. This is
+some of the more complicated code in this crate, and is something I would very
+much like to improve. In particular, it currently has the restriction that it
+must buffer at least enough of the haystack in memory in order to fit the
+longest possible match. The difficulty in getting stream searching right is
+that the implementation choices (such as the buffer size) often impact what the
+API looks like and what it's allowed to do.
+
+
+# Prefilters
+
+In some cases, Aho-Corasick is not the fastest way to find matches containing
+multiple patterns. Sometimes, the search can be accelerated using highly
+optimized SIMD routines. For example, consider searching the following
+patterns:
+
+    Sherlock
+    Moriarty
+    Watson
+
+It is plausible that it would be much faster to quickly look for occurrences of
+the leading bytes, `S`, `M` or `W`, before trying to start searching via the
+automaton. Indeed, this is exactly what this crate will do.
+
+When there are more than three distinct starting bytes, then this crate will
+look for three distinct bytes occurring at any position in the patterns, while
+preferring bytes that are heuristically determined to be rare over others. For
+example:
+
+    Abuzz
+    Sanchez
+    Vasquez
+    Topaz
+    Waltz
+
+Here, we have more than 3 distinct starting bytes, but all of the patterns
+contain `z`, which is typically a rare byte. In this case, the prefilter will
+scan for `z`, back up a bit, and then execute the Aho-Corasick automaton.
+
+If all of that fails, then a packed multiple substring algorithm will be
+attempted. Currently, the only algorithm available for this is Teddy, but more
+may be added in the future. Teddy is unlike the above prefilters in that it
+confirms its own matches, so when Teddy is active, it might not be necessary
+for Aho-Corasick to run at all. (See `Automaton::leftmost_find_at_no_state_imp`
+in `src/automaton.rs`.) However, the current Teddy implementation only works
+in `x86_64` and when SSSE3 or AVX2 are available, and moreover, only works
+_well_ when there are a small number of patterns (say, less than 100). Teddy
+also requires the haystack to be of a certain length (more than 16-34 bytes).
+When the haystack is shorter than that, Rabin-Karp is used instead. (See
+`src/packed/rabinkarp.rs`.)
+
+There is a more thorough description of Teddy at
+[`src/packed/teddy/README.md`](src/packed/teddy/README.md).
diff --git a/vendor/aho-corasick/LICENSE-MIT b/vendor/aho-corasick/LICENSE-MIT
new file mode 100644
index 0000000..3b0a5dc
--- /dev/null
+++ b/vendor/aho-corasick/LICENSE-MIT
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Andrew Gallant
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/vendor/aho-corasick/README.md b/vendor/aho-corasick/README.md
new file mode 100644
index 0000000..cd43051
--- /dev/null
+++ b/vendor/aho-corasick/README.md
@@ -0,0 +1,181 @@
+aho-corasick
+============
+A library for finding occurrences of many patterns at once with SIMD
+acceleration in some cases. This library provides multiple pattern
+search principally through an implementation of the
+[Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
+which builds a finite state machine for executing searches in linear time.
+Features include case insensitive matching, overlapping matches, fast searching
+via SIMD and optional full DFA construction and search & replace in streams.
+
+[![Build status](https://github.com/BurntSushi/aho-corasick/workflows/ci/badge.svg)](https://github.com/BurntSushi/aho-corasick/actions)
+[![](http://meritbadge.herokuapp.com/aho-corasick)](https://crates.io/crates/aho-corasick)
+
+Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
+
+
+### Documentation
+
+https://docs.rs/aho-corasick
+
+
+### Usage
+
+Add this to your `Cargo.toml`:
+
+```toml
+[dependencies]
+aho-corasick = "0.7"
+```
+
+
+### Example: basic searching
+
+This example shows how to search for occurrences of multiple patterns
+simultaneously. Each match includes the pattern that matched along with the
+byte offsets of the match.
+
+```rust
+use aho_corasick::AhoCorasick;
+
+let patterns = &["apple", "maple", "Snapple"];
+let haystack = "Nobody likes maple in their apple flavored Snapple.";
+
+let ac = AhoCorasick::new(patterns);
+let mut matches = vec![];
+for mat in ac.find_iter(haystack) {
+    matches.push((mat.pattern(), mat.start(), mat.end()));
+}
+assert_eq!(matches, vec![
+    (1, 13, 18),
+    (0, 28, 33),
+    (2, 43, 50),
+]);
+```
+
+
+### Example: case insensitivity
+
+This is like the previous example, but matches `Snapple` case insensitively
+using `AhoCorasickBuilder`:
+
+```rust
+use aho_corasick::AhoCorasickBuilder;
+
+let patterns = &["apple", "maple", "snapple"];
+let haystack = "Nobody likes maple in their apple flavored Snapple.";
+
+let ac = AhoCorasickBuilder::new()
+    .ascii_case_insensitive(true)
+    .build(patterns);
+let mut matches = vec![];
+for mat in ac.find_iter(haystack) {
+    matches.push((mat.pattern(), mat.start(), mat.end()));
+}
+assert_eq!(matches, vec![
+    (1, 13, 18),
+    (0, 28, 33),
+    (2, 43, 50),
+]);
+```
+
+
+### Example: replacing matches in a stream
+
+This example shows how to execute a search and replace on a stream without
+loading the entire stream into memory first.
+
+```rust
+use aho_corasick::AhoCorasick;
+
+let patterns = &["fox", "brown", "quick"];
+let replace_with = &["sloth", "grey", "slow"];
+
+// In a real example, these might be `std::fs::File`s instead. All you need to
+// do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
+let rdr = "The quick brown fox.";
+let mut wtr = vec![];
+
+let ac = AhoCorasick::new(patterns);
+ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
+    .expect("stream_replace_all failed");
+assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
+```
+
+
+### Example: finding the leftmost first match
+
+In the textbook description of Aho-Corasick, its formulation is typically
+structured such that it reports all possible matches, even when they overlap
+with another. In many cases, overlapping matches may not be desired, such as
+the case of finding all successive non-overlapping matches like you might with
+a standard regular expression.
+
+Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
+this doesn't always work in the expected way, since it will report matches as
+soon as they are seen. For example, consider matching the regex `Samwise|Sam`
+against the text `Samwise`. Most regex engines (that are Perl-like, or
+non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
+algorithm modified for reporting non-overlapping matches will report `Sam`.
+
+A novel contribution of this library is the ability to change the match
+semantics of Aho-Corasick (without additional search time overhead) such that
+`Samwise` is reported instead. For example, here's the standard approach:
+
+```rust
+use aho_corasick::AhoCorasick;
+
+let patterns = &["Samwise", "Sam"];
+let haystack = "Samwise";
+
+let ac = AhoCorasick::new(patterns);
+let mat = ac.find(haystack).expect("should have a match");
+assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
+```
+
+And now here's the leftmost-first version, which matches how a Perl-like
+regex will work:
+
+```rust
+use aho_corasick::{AhoCorasickBuilder, MatchKind};
+
+let patterns = &["Samwise", "Sam"];
+let haystack = "Samwise";
+
+let ac = AhoCorasickBuilder::new()
+    .match_kind(MatchKind::LeftmostFirst)
+    .build(patterns);
+let mat = ac.find(haystack).expect("should have a match");
+assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
+```
+
+In addition to leftmost-first semantics, this library also supports
+leftmost-longest semantics, which match the POSIX behavior of a regular
+expression alternation. See `MatchKind` in the docs for more details.
+
+
+### Minimum Rust version policy
+
+This crate's minimum supported `rustc` version is `1.41.1`.
+
+The current policy is that the minimum Rust version required to use this crate
+can be increased in minor version updates. For example, if `crate 1.0` requires
+Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust
+1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum
+version of Rust.
+
+In general, this crate will be conservative with respect to the minimum
+supported version of Rust.
+
+
+### Future work
+
+Here are some plans for the future:
+
+* Assuming the current API is sufficient, I'd like to commit to it and release
+  a `1.0` version of this crate some time in the next 6-12 months.
+* Support stream searching with leftmost match semantics. Currently, only
+  standard match semantics are supported. Getting this right seems possible,
+  but is tricky since the match state needs to be propagated through multiple
+  searches. (With standard semantics, as soon as a match is seen the search
+  ends.)
diff --git a/vendor/aho-corasick/UNLICENSE b/vendor/aho-corasick/UNLICENSE
new file mode 100644
index 0000000..68a49da
--- /dev/null
+++ b/vendor/aho-corasick/UNLICENSE
@@ -0,0 +1,24 @@
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.
+
+For more information, please refer to <http://unlicense.org/>
diff --git a/vendor/aho-corasick/rustfmt.toml b/vendor/aho-corasick/rustfmt.toml
new file mode 100644
index 0000000..aa37a21
--- /dev/null
+++ b/vendor/aho-corasick/rustfmt.toml
@@ -0,0 +1,2 @@
+max_width = 79
+use_small_heuristics = "max"
diff --git a/vendor/aho-corasick/src/ahocorasick.rs b/vendor/aho-corasick/src/ahocorasick.rs
new file mode 100644
index 0000000..2b1aa5c
--- /dev/null
+++ b/vendor/aho-corasick/src/ahocorasick.rs
@@ -0,0 +1,2143 @@
+use std::io;
+
+use crate::automaton::Automaton;
+use crate::buffer::Buffer;
+use crate::dfa::{self, DFA};
+use crate::error::Result;
+use crate::nfa::{self, NFA};
+use crate::packed;
+use crate::prefilter::{Prefilter, PrefilterState};
+use crate::state_id::StateID;
+use crate::Match;
+
+/// An automaton for searching multiple strings in linear time.
+///
+/// The `AhoCorasick` type supports a few basic ways of constructing an
+/// automaton, including
+/// [`AhoCorasick::new`](struct.AhoCorasick.html#method.new)
+/// and
+/// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured).
+/// However, there are a fair number of configurable options that can be set
+/// by using
+/// [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html)
+/// instead. Such options include, but are not limited to, how matches are
+/// determined, simple case insensitivity, whether to use a DFA or not and
+/// various knobs for controlling the space-vs-time trade offs taken when
+/// building the automaton.
+///
+/// If you aren't sure where to start, try beginning with
+/// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured).
+///
+/// # Resource usage
+///
+/// Aho-Corasick automatons are always constructed in `O(p)` time, where `p`
+/// is the combined length of all patterns being searched. With that said,
+/// building an automaton can be fairly costly because of high constant
+/// factors, particularly when enabling the
+/// [DFA](struct.AhoCorasickBuilder.html#method.dfa)
+/// option (which is disabled by default). For this reason, it's generally a
+/// good idea to build an automaton once and reuse it as much as possible.
+///
+/// Aho-Corasick automatons can also use a fair bit of memory. To get a
+/// concrete idea of how much memory is being used, try using the
+/// [`AhoCorasick::heap_bytes`](struct.AhoCorasick.html#method.heap_bytes)
+/// method.
+///
+/// # Examples
+///
+/// This example shows how to search for occurrences of multiple patterns
+/// simultaneously in a case insensitive fashion. Each match includes the
+/// pattern that matched along with the byte offsets of the match.
+///
+/// ```
+/// use aho_corasick::AhoCorasickBuilder;
+///
+/// let patterns = &["apple", "maple", "snapple"];
+/// let haystack = "Nobody likes maple in their apple flavored Snapple.";
+///
+/// let ac = AhoCorasickBuilder::new()
+///     .ascii_case_insensitive(true)
+///     .build(patterns);
+/// let mut matches = vec![];
+/// for mat in ac.find_iter(haystack) {
+///     matches.push((mat.pattern(), mat.start(), mat.end()));
+/// }
+/// assert_eq!(matches, vec![
+///     (1, 13, 18),
+///     (0, 28, 33),
+///     (2, 43, 50),
+/// ]);
+/// ```
+///
+/// This example shows how to replace matches with some other string:
+///
+/// ```
+/// use aho_corasick::AhoCorasick;
+///
+/// let patterns = &["fox", "brown", "quick"];
+/// let haystack = "The quick brown fox.";
+/// let replace_with = &["sloth", "grey", "slow"];
+///
+/// let ac = AhoCorasick::new(patterns);
+/// let result = ac.replace_all(haystack, replace_with);
+/// assert_eq!(result, "The slow grey sloth.");
+/// ```
+#[derive(Clone, Debug)]
+pub struct AhoCorasick<S: StateID = usize> {
+    imp: Imp<S>,
+    match_kind: MatchKind,
+}
+
+impl AhoCorasick {
+    /// Create a new Aho-Corasick automaton using the default configuration.
+    ///
+    /// The default configuration optimizes for less space usage, but at the
+    /// expense of longer search times. To change the configuration, use
+    /// [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html)
+    /// for fine-grained control, or
+    /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured)
+    /// for automatic configuration if you aren't sure which settings to pick.
+    ///
+    /// This uses the default
+    /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
+    /// match semantics, which reports a match as soon as it is found. This
+    /// corresponds to the standard match semantics supported by textbook
+    /// descriptions of the Aho-Corasick algorithm.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "foo", "bar", "baz",
+    /// ]);
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// ```
+    pub fn new<I, P>(patterns: I) -> AhoCorasick
+    where
+        I: IntoIterator<Item = P>,
+        P: AsRef<[u8]>,
+    {
+        AhoCorasickBuilder::new().build(patterns)
+    }
+
+    /// Build an Aho-Corasick automaton with an automatically determined
+    /// configuration.
+    ///
+    /// Specifically, this requires a slice of patterns instead of an iterator
+    /// since the configuration is determined by looking at the patterns before
+    /// constructing the automaton. The idea here is to balance space and time
+    /// automatically. That is, when searching a small number of patterns, this
+    /// will attempt to use the fastest possible configuration since the total
+    /// space required will be small anyway. As the number of patterns grows,
+    /// this will fall back to slower configurations that use less space.
+    ///
+    /// If you want auto configuration but with match semantics different from
+    /// the default `MatchKind::Standard`, then use
+    /// [`AhoCorasickBuilder::auto_configure`](struct.AhoCorasickBuilder.html#method.auto_configure).
+    ///
+    /// # Examples
+    ///
+    /// Basic usage is just like `new`, except you must provide a slice:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new_auto_configured(&[
+    ///     "foo", "bar", "baz",
+    /// ]);
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// ```
+    pub fn new_auto_configured<B>(patterns: &[B]) -> AhoCorasick
+    where
+        B: AsRef<[u8]>,
+    {
+        AhoCorasickBuilder::new().auto_configure(patterns).build(patterns)
+    }
+}
+
+impl<S: StateID> AhoCorasick<S> {
+    /// Returns true if and only if this automaton matches the haystack at any
+    /// position.
+    ///
+    /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
+    /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
+    /// `&[u8]` itself.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "foo", "bar", "quux", "baz",
+    /// ]);
+    /// assert!(ac.is_match("xxx bar xxx"));
+    /// assert!(!ac.is_match("xxx qux xxx"));
+    /// ```
+    pub fn is_match<B: AsRef<[u8]>>(&self, haystack: B) -> bool {
+        self.earliest_find(haystack).is_some()
+    }
+
+    /// Returns the location of the first detected match in `haystack`.
+    ///
+    /// This method has the same behavior regardless of the
+    /// [`MatchKind`](enum.MatchKind.html)
+    /// of this automaton.
+    ///
+    /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
+    /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
+    /// `&[u8]` itself.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "abc", "b",
+    /// ]);
+    /// let mat = ac.earliest_find("abcd").expect("should have match");
+    /// assert_eq!(1, mat.pattern());
+    /// assert_eq!((1, 2), (mat.start(), mat.end()));
+    /// ```
+    pub fn earliest_find<B: AsRef<[u8]>>(&self, haystack: B) -> Option<Match> {
+        let mut prestate = PrefilterState::new(self.max_pattern_len());
+        let mut start = self.imp.start_state();
+        self.imp.earliest_find_at(
+            &mut prestate,
+            haystack.as_ref(),
+            0,
+            &mut start,
+        )
+    }
+
+    /// Returns the location of the first match according to the match
+    /// semantics that this automaton was constructed with.
+    ///
+    /// When using `MatchKind::Standard`, this corresponds precisely to the
+    /// same behavior as
+    /// [`earliest_find`](struct.AhoCorasick.html#method.earliest_find).
+    /// Otherwise, match semantics correspond to either
+    /// [leftmost-first](enum.MatchKind.html#variant.LeftmostFirst)
+    /// or
+    /// [leftmost-longest](enum.MatchKind.html#variant.LeftmostLongest).
+    ///
+    /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
+    /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
+    /// `&[u8]` itself.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage, with standard semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::Standard) // default, not necessary
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("b", &haystack[mat.start()..mat.end()]);
+    /// ```
+    ///
+    /// Now with leftmost-first semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("abc", &haystack[mat.start()..mat.end()]);
+    /// ```
+    ///
+    /// And finally, leftmost-longest semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostLongest)
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("abcd", &haystack[mat.start()..mat.end()]);
+    /// ```
+    pub fn find<B: AsRef<[u8]>>(&self, haystack: B) -> Option<Match> {
+        let mut prestate = PrefilterState::new(self.max_pattern_len());
+        self.imp.find_at_no_state(&mut prestate, haystack.as_ref(), 0)
+    }
+
+    /// Returns an iterator of non-overlapping matches, using the match
+    /// semantics that this automaton was constructed with.
+    ///
+    /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
+    /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
+    /// `&[u8]` itself.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage, with standard semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::Standard) // default, not necessary
+    ///     .build(patterns);
+    /// let matches: Vec<usize> = ac
+    ///     .find_iter(haystack)
+    ///     .map(|mat| mat.pattern())
+    ///     .collect();
+    /// assert_eq!(vec![2, 2, 2], matches);
+    /// ```
+    ///
+    /// Now with leftmost-first semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let matches: Vec<usize> = ac
+    ///     .find_iter(haystack)
+    ///     .map(|mat| mat.pattern())
+    ///     .collect();
+    /// assert_eq!(vec![0, 2, 0], matches);
+    /// ```
+    ///
+    /// And finally, leftmost-longest semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostLongest)
+    ///     .build(patterns);
+    /// let matches: Vec<usize> = ac
+    ///     .find_iter(haystack)
+    ///     .map(|mat| mat.pattern())
+    ///     .collect();
+    /// assert_eq!(vec![0, 2, 1], matches);
+    /// ```
+    pub fn find_iter<'a, 'b, B: ?Sized + AsRef<[u8]>>(
+        &'a self,
+        haystack: &'b B,
+    ) -> FindIter<'a, 'b, S> {
+        FindIter::new(self, haystack.as_ref())
+    }
+
+    /// Returns an iterator of overlapping matches in the given `haystack`.
+    ///
+    /// Overlapping matches can _only_ be detected using
+    /// `MatchKind::Standard` semantics. If this automaton was constructed with
+    /// leftmost semantics, then this method will panic. To determine whether
+    /// this will panic at runtime, use the
+    /// [`AhoCorasick::supports_overlapping`](struct.AhoCorasick.html#method.supports_overlapping)
+    /// method.
+    ///
+    /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
+    /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
+    /// `&[u8]` itself.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `AhoCorasick::supports_overlapping` returns `false`.
+    /// That is, this panics when this automaton's match semantics are not
+    /// `MatchKind::Standard`.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage, with standard semantics:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasick::new(patterns);
+    /// let matches: Vec<usize> = ac
+    ///     .find_overlapping_iter(haystack)
+    ///     .map(|mat| mat.pattern())
+    ///     .collect();
+    /// assert_eq!(vec![2, 0, 2, 2, 0, 1], matches);
+    /// ```
+    pub fn find_overlapping_iter<'a, 'b, B: ?Sized + AsRef<[u8]>>(
+        &'a self,
+        haystack: &'b B,
+    ) -> FindOverlappingIter<'a, 'b, S> {
+        FindOverlappingIter::new(self, haystack.as_ref())
+    }
+
+    /// Replace all matches with a corresponding value in the `replace_with`
+    /// slice given. Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// Replacements are determined by the index of the matching pattern.
+    /// For example, if the pattern with index `2` is found, then it is
+    /// replaced by `replace_with[2]`.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `replace_with.len()` does not equal the total number
+    /// of patterns that are matched by this automaton.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let result = ac.replace_all(haystack, &["x", "y", "z"]);
+    /// assert_eq!("x the z to the xage", result);
+    /// ```
+    pub fn replace_all<B>(&self, haystack: &str, replace_with: &[B]) -> String
+    where
+        B: AsRef<str>,
+    {
+        assert_eq!(
+            replace_with.len(),
+            self.pattern_count(),
+            "replace_all requires a replacement for every pattern \
+             in the automaton"
+        );
+        let mut dst = String::with_capacity(haystack.len());
+        self.replace_all_with(haystack, &mut dst, |mat, _, dst| {
+            dst.push_str(replace_with[mat.pattern()].as_ref());
+            true
+        });
+        dst
+    }
+
+    /// Replace all matches using raw bytes with a corresponding value in the
+    /// `replace_with` slice given. Matches correspond to the same matches as
+    /// reported by [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// Replacements are determined by the index of the matching pattern.
+    /// For example, if the pattern with index `2` is found, then it is
+    /// replaced by `replace_with[2]`.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `replace_with.len()` does not equal the total number
+    /// of patterns that are matched by this automaton.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = b"append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let result = ac.replace_all_bytes(haystack, &["x", "y", "z"]);
+    /// assert_eq!(b"x the z to the xage".to_vec(), result);
+    /// ```
+    pub fn replace_all_bytes<B>(
+        &self,
+        haystack: &[u8],
+        replace_with: &[B],
+    ) -> Vec<u8>
+    where
+        B: AsRef<[u8]>,
+    {
+        assert_eq!(
+            replace_with.len(),
+            self.pattern_count(),
+            "replace_all_bytes requires a replacement for every pattern \
+             in the automaton"
+        );
+        let mut dst = Vec::with_capacity(haystack.len());
+        self.replace_all_with_bytes(haystack, &mut dst, |mat, _, dst| {
+            dst.extend(replace_with[mat.pattern()].as_ref());
+            true
+        });
+        dst
+    }
+
+    /// Replace all matches using a closure called on each match.
+    /// Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// The closure accepts three parameters: the match found, the text of
+    /// the match and a string buffer with which to write the replaced text
+    /// (if any). If the closure returns `true`, then it continues to the next
+    /// match. If the closure returns `false`, then searching is stopped.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let mut result = String::new();
+    /// ac.replace_all_with(haystack, &mut result, |mat, _, dst| {
+    ///     dst.push_str(&mat.pattern().to_string());
+    ///     true
+    /// });
+    /// assert_eq!("0 the 2 to the 0age", result);
+    /// ```
+    ///
+    /// Stopping the replacement by returning `false` (continued from the
+    /// example above):
+    ///
+    /// ```
+    /// # use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    /// # let patterns = &["append", "appendage", "app"];
+    /// # let haystack = "append the app to the appendage";
+    /// # let ac = AhoCorasickBuilder::new()
+    /// #    .match_kind(MatchKind::LeftmostFirst)
+    /// #    .build(patterns);
+    /// let mut result = String::new();
+    /// ac.replace_all_with(haystack, &mut result, |mat, _, dst| {
+    ///     dst.push_str(&mat.pattern().to_string());
+    ///     mat.pattern() != 2
+    /// });
+    /// assert_eq!("0 the 2 to the appendage", result);
+    /// ```
+    pub fn replace_all_with<F>(
+        &self,
+        haystack: &str,
+        dst: &mut String,
+        mut replace_with: F,
+    ) where
+        F: FnMut(&Match, &str, &mut String) -> bool,
+    {
+        let mut last_match = 0;
+        for mat in self.find_iter(haystack) {
+            dst.push_str(&haystack[last_match..mat.start()]);
+            last_match = mat.end();
+            if !replace_with(&mat, &haystack[mat.start()..mat.end()], dst) {
+                break;
+            };
+        }
+        dst.push_str(&haystack[last_match..]);
+    }
+
+    /// Replace all matches using raw bytes with a closure called on each
+    /// match. Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// The closure accepts three parameters: the match found, the text of
+    /// the match and a byte buffer with which to write the replaced text
+    /// (if any). If the closure returns `true`, then it continues to the next
+    /// match. If the closure returns `false`, then searching is stopped.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = b"append the app to the appendage";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let mut result = vec![];
+    /// ac.replace_all_with_bytes(haystack, &mut result, |mat, _, dst| {
+    ///     dst.extend(mat.pattern().to_string().bytes());
+    ///     true
+    /// });
+    /// assert_eq!(b"0 the 2 to the 0age".to_vec(), result);
+    /// ```
+    ///
+    /// Stopping the replacement by returning `false` (continued from the
+    /// example above):
+    ///
+    /// ```
+    /// # use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    /// # let patterns = &["append", "appendage", "app"];
+    /// # let haystack = b"append the app to the appendage";
+    /// # let ac = AhoCorasickBuilder::new()
+    /// #    .match_kind(MatchKind::LeftmostFirst)
+    /// #    .build(patterns);
+    /// let mut result = vec![];
+    /// ac.replace_all_with_bytes(haystack, &mut result, |mat, _, dst| {
+    ///     dst.extend(mat.pattern().to_string().bytes());
+    ///     mat.pattern() != 2
+    /// });
+    /// assert_eq!(b"0 the 2 to the appendage".to_vec(), result);
+    /// ```
+    pub fn replace_all_with_bytes<F>(
+        &self,
+        haystack: &[u8],
+        dst: &mut Vec<u8>,
+        mut replace_with: F,
+    ) where
+        F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,
+    {
+        let mut last_match = 0;
+        for mat in self.find_iter(haystack) {
+            dst.extend(&haystack[last_match..mat.start()]);
+            last_match = mat.end();
+            if !replace_with(&mat, &haystack[mat.start()..mat.end()], dst) {
+                break;
+            };
+        }
+        dst.extend(&haystack[last_match..]);
+    }
+
+    /// Returns an iterator of non-overlapping matches in the given
+    /// stream. Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// The matches yielded by this iterator use absolute position offsets in
+    /// the stream given, where the first byte has index `0`. Matches are
+    /// yieled until the stream is exhausted.
+    ///
+    /// Each item yielded by the iterator is an `io::Result<Match>`, where an
+    /// error is yielded if there was a problem reading from the reader given.
+    ///
+    /// When searching a stream, an internal buffer is used. Therefore, callers
+    /// should avoiding providing a buffered reader, if possible.
+    ///
+    /// Searching a stream requires that the automaton was built with
+    /// `MatchKind::Standard` semantics. If this automaton was constructed
+    /// with leftmost semantics, then this method will panic. To determine
+    /// whether this will panic at runtime, use the
+    /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
+    /// method.
+    ///
+    /// # Memory usage
+    ///
+    /// In general, searching streams will use a constant amount of memory for
+    /// its internal buffer. The one requirement is that the internal buffer
+    /// must be at least the size of the longest possible match. In most use
+    /// cases, the default buffer size will be much larger than any individual
+    /// match.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `AhoCorasick::supports_stream` returns `false`.
+    /// That is, this panics when this automaton's match semantics are not
+    /// `MatchKind::Standard`. This restriction may be lifted in the future.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// # fn example() -> Result<(), ::std::io::Error> {
+    /// let patterns = &["append", "appendage", "app"];
+    /// let haystack = "append the app to the appendage";
+    ///
+    /// let ac = AhoCorasick::new(patterns);
+    /// let mut matches = vec![];
+    /// for result in ac.stream_find_iter(haystack.as_bytes()) {
+    ///     let mat = result?;
+    ///     matches.push(mat.pattern());
+    /// }
+    /// assert_eq!(vec![2, 2, 2], matches);
+    /// # Ok(()) }; example().unwrap()
+    /// ```
+    pub fn stream_find_iter<'a, R: io::Read>(
+        &'a self,
+        rdr: R,
+    ) -> StreamFindIter<'a, R, S> {
+        StreamFindIter::new(self, rdr)
+    }
+
+    /// Search for and replace all matches of this automaton in
+    /// the given reader, and write the replacements to the given
+    /// writer. Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// Replacements are determined by the index of the matching pattern.
+    /// For example, if the pattern with index `2` is found, then it is
+    /// replaced by `replace_with[2]`.
+    ///
+    /// After all matches are replaced, the writer is _not_ flushed.
+    ///
+    /// If there was a problem reading from the given reader or writing to the
+    /// given writer, then the corresponding `io::Error` is returned and all
+    /// replacement is stopped.
+    ///
+    /// When searching a stream, an internal buffer is used. Therefore, callers
+    /// should avoiding providing a buffered reader, if possible. However,
+    /// callers may want to provide a buffered writer.
+    ///
+    /// Searching a stream requires that the automaton was built with
+    /// `MatchKind::Standard` semantics. If this automaton was constructed
+    /// with leftmost semantics, then this method will panic. To determine
+    /// whether this will panic at runtime, use the
+    /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
+    /// method.
+    ///
+    /// # Memory usage
+    ///
+    /// In general, searching streams will use a constant amount of memory for
+    /// its internal buffer. The one requirement is that the internal buffer
+    /// must be at least the size of the longest possible match. In most use
+    /// cases, the default buffer size will be much larger than any individual
+    /// match.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `AhoCorasick::supports_stream` returns `false`.
+    /// That is, this panics when this automaton's match semantics are not
+    /// `MatchKind::Standard`. This restriction may be lifted in the future.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// # fn example() -> Result<(), ::std::io::Error> {
+    /// let patterns = &["fox", "brown", "quick"];
+    /// let haystack = "The quick brown fox.";
+    /// let replace_with = &["sloth", "grey", "slow"];
+    ///
+    /// let ac = AhoCorasick::new(patterns);
+    /// let mut result = vec![];
+    /// ac.stream_replace_all(haystack.as_bytes(), &mut result, replace_with)?;
+    /// assert_eq!(b"The slow grey sloth.".to_vec(), result);
+    /// # Ok(()) }; example().unwrap()
+    /// ```
+    pub fn stream_replace_all<R, W, B>(
+        &self,
+        rdr: R,
+        wtr: W,
+        replace_with: &[B],
+    ) -> io::Result<()>
+    where
+        R: io::Read,
+        W: io::Write,
+        B: AsRef<[u8]>,
+    {
+        assert_eq!(
+            replace_with.len(),
+            self.pattern_count(),
+            "stream_replace_all requires a replacement for every pattern \
+             in the automaton"
+        );
+        self.stream_replace_all_with(rdr, wtr, |mat, _, wtr| {
+            wtr.write_all(replace_with[mat.pattern()].as_ref())
+        })
+    }
+
+    /// Search the given reader and replace all matches of this automaton
+    /// using the given closure. The result is written to the given
+    /// writer. Matches correspond to the same matches as reported by
+    /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
+    ///
+    /// The closure accepts three parameters: the match found, the text of
+    /// the match and the writer with which to write the replaced text (if any).
+    ///
+    /// After all matches are replaced, the writer is _not_ flushed.
+    ///
+    /// If there was a problem reading from the given reader or writing to the
+    /// given writer, then the corresponding `io::Error` is returned and all
+    /// replacement is stopped.
+    ///
+    /// When searching a stream, an internal buffer is used. Therefore, callers
+    /// should avoiding providing a buffered reader, if possible. However,
+    /// callers may want to provide a buffered writer.
+    ///
+    /// Searching a stream requires that the automaton was built with
+    /// `MatchKind::Standard` semantics. If this automaton was constructed
+    /// with leftmost semantics, then this method will panic. To determine
+    /// whether this will panic at runtime, use the
+    /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
+    /// method.
+    ///
+    /// # Memory usage
+    ///
+    /// In general, searching streams will use a constant amount of memory for
+    /// its internal buffer. The one requirement is that the internal buffer
+    /// must be at least the size of the longest possible match. In most use
+    /// cases, the default buffer size will be much larger than any individual
+    /// match.
+    ///
+    /// # Panics
+    ///
+    /// This panics when `AhoCorasick::supports_stream` returns `false`.
+    /// That is, this panics when this automaton's match semantics are not
+    /// `MatchKind::Standard`. This restriction may be lifted in the future.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::io::Write;
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// # fn example() -> Result<(), ::std::io::Error> {
+    /// let patterns = &["fox", "brown", "quick"];
+    /// let haystack = "The quick brown fox.";
+    ///
+    /// let ac = AhoCorasick::new(patterns);
+    /// let mut result = vec![];
+    /// ac.stream_replace_all_with(
+    ///     haystack.as_bytes(),
+    ///     &mut result,
+    ///     |mat, _, wtr| {
+    ///         wtr.write_all(mat.pattern().to_string().as_bytes())
+    ///     },
+    /// )?;
+    /// assert_eq!(b"The 2 1 0.".to_vec(), result);
+    /// # Ok(()) }; example().unwrap()
+    /// ```
+    pub fn stream_replace_all_with<R, W, F>(
+        &self,
+        rdr: R,
+        mut wtr: W,
+        mut replace_with: F,
+    ) -> io::Result<()>
+    where
+        R: io::Read,
+        W: io::Write,
+        F: FnMut(&Match, &[u8], &mut W) -> io::Result<()>,
+    {
+        let mut it = StreamChunkIter::new(self, rdr);
+        while let Some(result) = it.next() {
+            let chunk = result?;
+            match chunk {
+                StreamChunk::NonMatch { bytes, .. } => {
+                    wtr.write_all(bytes)?;
+                }
+                StreamChunk::Match { bytes, mat } => {
+                    replace_with(&mat, bytes, &mut wtr)?;
+                }
+            }
+        }
+        Ok(())
+    }
+
+    /// Returns the match kind used by this automaton.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasick, MatchKind};
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "foo", "bar", "quux", "baz",
+    /// ]);
+    /// assert_eq!(&MatchKind::Standard, ac.match_kind());
+    /// ```
+    pub fn match_kind(&self) -> &MatchKind {
+        self.imp.match_kind()
+    }
+
+    /// Returns the length of the longest pattern matched by this automaton.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "foo", "bar", "quux", "baz",
+    /// ]);
+    /// assert_eq!(4, ac.max_pattern_len());
+    /// ```
+    pub fn max_pattern_len(&self) -> usize {
+        self.imp.max_pattern_len()
+    }
+
+    /// Return the total number of patterns matched by this automaton.
+    ///
+    /// This includes patterns that may never participate in a match. For
+    /// example, if
+    /// [`MatchKind::LeftmostFirst`](enum.MatchKind.html#variant.LeftmostFirst)
+    /// match semantics are used, and the patterns `Sam` and `Samwise` were
+    /// used to build the automaton, then `Samwise` can never participate in a
+    /// match because `Sam` will always take priority.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasick;
+    ///
+    /// let ac = AhoCorasick::new(&[
+    ///     "foo", "bar", "baz",
+    /// ]);
+    /// assert_eq!(3, ac.pattern_count());
+    /// ```
+    pub fn pattern_count(&self) -> usize {
+        self.imp.pattern_count()
+    }
+
+    /// Returns true if and only if this automaton supports reporting
+    /// overlapping matches.
+    ///
+    /// If this returns false and overlapping matches are requested, then it
+    /// will result in a panic.
+    ///
+    /// Since leftmost matching is inherently incompatible with overlapping
+    /// matches, only
+    /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
+    /// supports overlapping matches. This is unlikely to change in the future.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::Standard)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert!(ac.supports_overlapping());
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert!(!ac.supports_overlapping());
+    /// ```
+    pub fn supports_overlapping(&self) -> bool {
+        self.match_kind.supports_overlapping()
+    }
+
+    /// Returns true if and only if this automaton supports stream searching.
+    ///
+    /// If this returns false and stream searching (or replacing) is attempted,
+    /// then it will result in a panic.
+    ///
+    /// Currently, only
+    /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
+    /// supports streaming. This may be expanded in the future.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::Standard)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert!(ac.supports_stream());
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert!(!ac.supports_stream());
+    /// ```
+    pub fn supports_stream(&self) -> bool {
+        self.match_kind.supports_stream()
+    }
+
+    /// Returns the approximate total amount of heap used by this automaton, in
+    /// units of bytes.
+    ///
+    /// # Examples
+    ///
+    /// This example shows the difference in heap usage between a few
+    /// configurations:
+    ///
+    /// ```ignore
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .dfa(false) // default
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert_eq!(10_336, ac.heap_bytes());
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .dfa(false) // default
+    ///     .ascii_case_insensitive(true)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert_eq!(10_384, ac.heap_bytes());
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .dfa(true)
+    ///     .ascii_case_insensitive(true)
+    ///     .build(&["foo", "bar", "baz"]);
+    /// assert_eq!(1_248, ac.heap_bytes());
+    /// ```
+    pub fn heap_bytes(&self) -> usize {
+        match self.imp {
+            Imp::NFA(ref nfa) => nfa.heap_bytes(),
+            Imp::DFA(ref dfa) => dfa.heap_bytes(),
+        }
+    }
+}
+
+/// The internal implementation of Aho-Corasick, which is either an NFA or
+/// a DFA. The NFA is slower but uses less memory. The DFA is faster but uses
+/// more memory.
+#[derive(Clone, Debug)]
+enum Imp<S: StateID> {
+    NFA(NFA<S>),
+    DFA(DFA<S>),
+}
+
+impl<S: StateID> Imp<S> {
+    /// Returns the type of match semantics implemented by this automaton.
+    fn match_kind(&self) -> &MatchKind {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.match_kind(),
+            Imp::DFA(ref dfa) => dfa.match_kind(),
+        }
+    }
+
+    /// Returns the identifier of the start state.
+    fn start_state(&self) -> S {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.start_state(),
+            Imp::DFA(ref dfa) => dfa.start_state(),
+        }
+    }
+
+    /// The length, in bytes, of the longest pattern in this automaton. This
+    /// information is useful for maintaining correct buffer sizes when
+    /// searching on streams.
+    fn max_pattern_len(&self) -> usize {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.max_pattern_len(),
+            Imp::DFA(ref dfa) => dfa.max_pattern_len(),
+        }
+    }
+
+    /// The total number of patterns added to this automaton. This includes
+    /// patterns that may never match. The maximum matching pattern that can be
+    /// reported is exactly one less than this number.
+    fn pattern_count(&self) -> usize {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.pattern_count(),
+            Imp::DFA(ref dfa) => dfa.pattern_count(),
+        }
+    }
+
+    /// Returns the prefilter object, if one exists, for the underlying
+    /// automaton.
+    fn prefilter(&self) -> Option<&dyn Prefilter> {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.prefilter(),
+            Imp::DFA(ref dfa) => dfa.prefilter(),
+        }
+    }
+
+    /// Returns true if and only if we should attempt to use a prefilter.
+    fn use_prefilter(&self) -> bool {
+        let p = match self.prefilter() {
+            None => return false,
+            Some(p) => p,
+        };
+        !p.looks_for_non_start_of_match()
+    }
+
+    #[inline(always)]
+    fn overlapping_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut S,
+        match_index: &mut usize,
+    ) -> Option<Match> {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+            Imp::DFA(ref dfa) => dfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+        }
+    }
+
+    #[inline(always)]
+    fn earliest_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut S,
+    ) -> Option<Match> {
+        match *self {
+            Imp::NFA(ref nfa) => {
+                nfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+            Imp::DFA(ref dfa) => {
+                dfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+        }
+    }
+
+    #[inline(always)]
+    fn find_at_no_state(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+    ) -> Option<Match> {
+        match *self {
+            Imp::NFA(ref nfa) => nfa.find_at_no_state(prestate, haystack, at),
+            Imp::DFA(ref dfa) => dfa.find_at_no_state(prestate, haystack, at),
+        }
+    }
+}
+
+/// An iterator of non-overlapping matches in a particular haystack.
+///
+/// This iterator yields matches according to the
+/// [`MatchKind`](enum.MatchKind.html)
+/// used by this automaton.
+///
+/// This iterator is constructed via the
+/// [`AhoCorasick::find_iter`](struct.AhoCorasick.html#method.find_iter)
+/// method.
+///
+/// The type variable `S` refers to the representation used for state
+/// identifiers. (By default, this is `usize`.)
+///
+/// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
+///
+/// The lifetime `'b` refers to the lifetime of the haystack being searched.
+#[derive(Debug)]
+pub struct FindIter<'a, 'b, S: StateID> {
+    fsm: &'a Imp<S>,
+    prestate: PrefilterState,
+    haystack: &'b [u8],
+    pos: usize,
+}
+
+impl<'a, 'b, S: StateID> FindIter<'a, 'b, S> {
+    fn new(ac: &'a AhoCorasick<S>, haystack: &'b [u8]) -> FindIter<'a, 'b, S> {
+        let prestate = PrefilterState::new(ac.max_pattern_len());
+        FindIter { fsm: &ac.imp, prestate, haystack, pos: 0 }
+    }
+}
+
+impl<'a, 'b, S: StateID> Iterator for FindIter<'a, 'b, S> {
+    type Item = Match;
+
+    fn next(&mut self) -> Option<Match> {
+        if self.pos > self.haystack.len() {
+            return None;
+        }
+        let result = self.fsm.find_at_no_state(
+            &mut self.prestate,
+            self.haystack,
+            self.pos,
+        );
+        let mat = match result {
+            None => return None,
+            Some(mat) => mat,
+        };
+        if mat.end() == self.pos {
+            // If the automaton can match the empty string and if we found an
+            // empty match, then we need to forcefully move the position.
+            self.pos += 1;
+        } else {
+            self.pos = mat.end();
+        }
+        Some(mat)
+    }
+}
+
+/// An iterator of overlapping matches in a particular haystack.
+///
+/// This iterator will report all possible matches in a particular haystack,
+/// even when the matches overlap.
+///
+/// This iterator is constructed via the
+/// [`AhoCorasick::find_overlapping_iter`](struct.AhoCorasick.html#method.find_overlapping_iter)
+/// method.
+///
+/// The type variable `S` refers to the representation used for state
+/// identifiers. (By default, this is `usize`.)
+///
+/// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
+///
+/// The lifetime `'b` refers to the lifetime of the haystack being searched.
+#[derive(Debug)]
+pub struct FindOverlappingIter<'a, 'b, S: StateID> {
+    fsm: &'a Imp<S>,
+    prestate: PrefilterState,
+    haystack: &'b [u8],
+    pos: usize,
+    last_match_end: usize,
+    state_id: S,
+    match_index: usize,
+}
+
+impl<'a, 'b, S: StateID> FindOverlappingIter<'a, 'b, S> {
+    fn new(
+        ac: &'a AhoCorasick<S>,
+        haystack: &'b [u8],
+    ) -> FindOverlappingIter<'a, 'b, S> {
+        assert!(
+            ac.supports_overlapping(),
+            "automaton does not support overlapping searches"
+        );
+        let prestate = PrefilterState::new(ac.max_pattern_len());
+        FindOverlappingIter {
+            fsm: &ac.imp,
+            prestate,
+            haystack,
+            pos: 0,
+            last_match_end: 0,
+            state_id: ac.imp.start_state(),
+            match_index: 0,
+        }
+    }
+}
+
+impl<'a, 'b, S: StateID> Iterator for FindOverlappingIter<'a, 'b, S> {
+    type Item = Match;
+
+    fn next(&mut self) -> Option<Match> {
+        let result = self.fsm.overlapping_find_at(
+            &mut self.prestate,
+            self.haystack,
+            self.pos,
+            &mut self.state_id,
+            &mut self.match_index,
+        );
+        match result {
+            None => return None,
+            Some(m) => {
+                self.pos = m.end();
+                Some(m)
+            }
+        }
+    }
+}
+
+/// An iterator that reports Aho-Corasick matches in a stream.
+///
+/// This iterator yields elements of type `io::Result<Match>`, where an error
+/// is reported if there was a problem reading from the underlying stream.
+/// The iterator terminates only when the underlying stream reaches `EOF`.
+///
+/// This iterator is constructed via the
+/// [`AhoCorasick::stream_find_iter`](struct.AhoCorasick.html#method.stream_find_iter)
+/// method.
+///
+/// The type variable `R` refers to the `io::Read` stream that is being read
+/// from.
+///
+/// The type variable `S` refers to the representation used for state
+/// identifiers. (By default, this is `usize`.)
+///
+/// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
+#[derive(Debug)]
+pub struct StreamFindIter<'a, R, S: StateID> {
+    it: StreamChunkIter<'a, R, S>,
+}
+
+impl<'a, R: io::Read, S: StateID> StreamFindIter<'a, R, S> {
+    fn new(ac: &'a AhoCorasick<S>, rdr: R) -> StreamFindIter<'a, R, S> {
+        StreamFindIter { it: StreamChunkIter::new(ac, rdr) }
+    }
+}
+
+impl<'a, R: io::Read, S: StateID> Iterator for StreamFindIter<'a, R, S> {
+    type Item = io::Result<Match>;
+
+    fn next(&mut self) -> Option<io::Result<Match>> {
+        loop {
+            match self.it.next() {
+                None => return None,
+                Some(Err(err)) => return Some(Err(err)),
+                Some(Ok(StreamChunk::NonMatch { .. })) => {}
+                Some(Ok(StreamChunk::Match { mat, .. })) => {
+                    return Some(Ok(mat));
+                }
+            }
+        }
+    }
+}
+
+/// An iterator over chunks in an underlying reader. Each chunk either
+/// corresponds to non-matching bytes or matching bytes, but all bytes from
+/// the underlying reader are reported in sequence. There may be an arbitrary
+/// number of non-matching chunks before seeing a matching chunk.
+///
+/// N.B. This does not actually implement Iterator because we need to borrow
+/// from the underlying reader. But conceptually, it's still an iterator.
+#[derive(Debug)]
+struct StreamChunkIter<'a, R, S: StateID> {
+    /// The AC automaton.
+    fsm: &'a Imp<S>,
+    /// State associated with this automaton's prefilter. It is a heuristic
+    /// for stopping the prefilter if it's deemed ineffective.
+    prestate: PrefilterState,
+    /// The source of bytes we read from.
+    rdr: R,
+    /// A fixed size buffer. This is what we actually search. There are some
+    /// invariants around the buffer's size, namely, it must be big enough to
+    /// contain the longest possible match.
+    buf: Buffer,
+    /// The ID of the FSM state we're currently in.
+    state_id: S,
+    /// The current position at which to start the next search in `buf`.
+    search_pos: usize,
+    /// The absolute position of `search_pos`, where `0` corresponds to the
+    /// position of the first byte read from `rdr`.
+    absolute_pos: usize,
+    /// The ending position of the last StreamChunk that was returned to the
+    /// caller. This position is used to determine whether we need to emit
+    /// non-matching bytes before emitting a match.
+    report_pos: usize,
+    /// A match that should be reported on the next call.
+    pending_match: Option<Match>,
+    /// Enabled only when the automaton can match the empty string. When
+    /// enabled, we need to execute one final search after consuming the
+    /// reader to find the trailing empty match.
+    has_empty_match_at_end: bool,
+}
+
+/// A single chunk yielded by the stream chunk iterator.
+///
+/// The `'r` lifetime refers to the lifetime of the stream chunk iterator.
+#[derive(Debug)]
+enum StreamChunk<'r> {
+    /// A chunk that does not contain any matches.
+    NonMatch { bytes: &'r [u8], start: usize },
+    /// A chunk that precisely contains a match.
+    Match { bytes: &'r [u8], mat: Match },
+}
+
+impl<'a, R: io::Read, S: StateID> StreamChunkIter<'a, R, S> {
+    fn new(ac: &'a AhoCorasick<S>, rdr: R) -> StreamChunkIter<'a, R, S> {
+        assert!(
+            ac.supports_stream(),
+            "stream searching is only supported for Standard match semantics"
+        );
+
+        let prestate = if ac.imp.use_prefilter() {
+            PrefilterState::new(ac.max_pattern_len())
+        } else {
+            PrefilterState::disabled()
+        };
+        let buf = Buffer::new(ac.imp.max_pattern_len());
+        let state_id = ac.imp.start_state();
+        StreamChunkIter {
+            fsm: &ac.imp,
+            prestate,
+            rdr,
+            buf,
+            state_id,
+            absolute_pos: 0,
+            report_pos: 0,
+            search_pos: 0,
+            pending_match: None,
+            has_empty_match_at_end: ac.is_match(""),
+        }
+    }
+
+    fn next<'r>(&'r mut self) -> Option<io::Result<StreamChunk<'r>>> {
+        loop {
+            if let Some(mut mat) = self.pending_match.take() {
+                let bytes = &self.buf.buffer()[mat.start()..mat.end()];
+                self.report_pos = mat.end();
+                mat = mat.increment(self.absolute_pos);
+                return Some(Ok(StreamChunk::Match { bytes, mat }));
+            }
+            if self.search_pos >= self.buf.len() {
+                if let Some(end) = self.unreported() {
+                    let bytes = &self.buf.buffer()[self.report_pos..end];
+                    let start = self.absolute_pos + self.report_pos;
+                    self.report_pos = end;
+                    return Some(Ok(StreamChunk::NonMatch { bytes, start }));
+                }
+                if self.buf.len() >= self.buf.min_buffer_len() {
+                    // This is the point at which we roll our buffer, which we
+                    // only do if our buffer has at least the minimum amount of
+                    // bytes in it. Before rolling, we update our various
+                    // positions to be consistent with the buffer after it has
+                    // been rolled.
+
+                    self.report_pos -=
+                        self.buf.len() - self.buf.min_buffer_len();
+                    self.absolute_pos +=
+                        self.search_pos - self.buf.min_buffer_len();
+                    self.search_pos = self.buf.min_buffer_len();
+                    self.buf.roll();
+                }
+                match self.buf.fill(&mut self.rdr) {
+                    Err(err) => return Some(Err(err)),
+                    Ok(false) => {
+                        // We've hit EOF, but if there are still some
+                        // unreported bytes remaining, return them now.
+                        if self.report_pos < self.buf.len() {
+                            let bytes = &self.buf.buffer()[self.report_pos..];
+                            let start = self.absolute_pos + self.report_pos;
+                            self.report_pos = self.buf.len();
+
+                            let chunk = StreamChunk::NonMatch { bytes, start };
+                            return Some(Ok(chunk));
+                        } else {
+                            // We've reported everything, but there might still
+                            // be a match at the very last position.
+                            if !self.has_empty_match_at_end {
+                                return None;
+                            }
+                            // fallthrough for another search to get trailing
+                            // empty matches
+                            self.has_empty_match_at_end = false;
+                        }
+                    }
+                    Ok(true) => {}
+                }
+            }
+            let result = self.fsm.earliest_find_at(
+                &mut self.prestate,
+                self.buf.buffer(),
+                self.search_pos,
+                &mut self.state_id,
+            );
+            match result {
+                None => {
+                    self.search_pos = self.buf.len();
+                }
+                Some(mat) => {
+                    self.state_id = self.fsm.start_state();
+                    if mat.end() == self.search_pos {
+                        // If the automaton can match the empty string and if
+                        // we found an empty match, then we need to forcefully
+                        // move the position.
+                        self.search_pos += 1;
+                    } else {
+                        self.search_pos = mat.end();
+                    }
+                    self.pending_match = Some(mat.clone());
+                    if self.report_pos < mat.start() {
+                        let bytes =
+                            &self.buf.buffer()[self.report_pos..mat.start()];
+                        let start = self.absolute_pos + self.report_pos;
+                        self.report_pos = mat.start();
+
+                        let chunk = StreamChunk::NonMatch { bytes, start };
+                        return Some(Ok(chunk));
+                    }
+                }
+            }
+        }
+    }
+
+    fn unreported(&self) -> Option<usize> {
+        let end = self.search_pos.saturating_sub(self.buf.min_buffer_len());
+        if self.report_pos < end {
+            Some(end)
+        } else {
+            None
+        }
+    }
+}
+
+/// A builder for configuring an Aho-Corasick automaton.
+#[derive(Clone, Debug)]
+pub struct AhoCorasickBuilder {
+    nfa_builder: nfa::Builder,
+    dfa_builder: dfa::Builder,
+    dfa: bool,
+}
+
+impl Default for AhoCorasickBuilder {
+    fn default() -> AhoCorasickBuilder {
+        AhoCorasickBuilder::new()
+    }
+}
+
+impl AhoCorasickBuilder {
+    /// Create a new builder for configuring an Aho-Corasick automaton.
+    ///
+    /// If you don't need fine grained configuration or aren't sure which knobs
+    /// to set, try using
+    /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured)
+    /// instead.
+    pub fn new() -> AhoCorasickBuilder {
+        AhoCorasickBuilder {
+            nfa_builder: nfa::Builder::new(),
+            dfa_builder: dfa::Builder::new(),
+            dfa: false,
+        }
+    }
+
+    /// Build an Aho-Corasick automaton using the configuration set on this
+    /// builder.
+    ///
+    /// A builder may be reused to create more automatons.
+    ///
+    /// This method will use the default for representing internal state
+    /// identifiers, which is `usize`. This guarantees that building the
+    /// automaton will succeed and is generally a good default, but can make
+    /// the size of the automaton 2-8 times bigger than it needs to be,
+    /// depending on your target platform.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// let patterns = &["foo", "bar", "baz"];
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .build(patterns);
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// ```
+    pub fn build<I, P>(&self, patterns: I) -> AhoCorasick
+    where
+        I: IntoIterator<Item = P>,
+        P: AsRef<[u8]>,
+    {
+        // The builder only returns an error if the chosen state ID
+        // representation is too small to fit all of the given patterns. In
+        // this case, since we fix the representation to usize, it will always
+        // work because it's impossible to overflow usize since the underlying
+        // storage would OOM long before that happens.
+        self.build_with_size::<usize, I, P>(patterns)
+            .expect("usize state ID type should always work")
+    }
+
+    /// Build an Aho-Corasick automaton using the configuration set on this
+    /// builder with a specific state identifier representation. This only has
+    /// an effect when the `dfa` option is enabled.
+    ///
+    /// Generally, the choices for a state identifier representation are
+    /// `u8`, `u16`, `u32`, `u64` or `usize`, with `usize` being the default.
+    /// The advantage of choosing a smaller state identifier representation
+    /// is that the automaton produced will be smaller. This might be
+    /// beneficial for just generally using less space, or might even allow it
+    /// to fit more of the automaton in your CPU's cache, leading to overall
+    /// better search performance.
+    ///
+    /// Unlike the standard `build` method, this can report an error if the
+    /// state identifier representation cannot support the size of the
+    /// automaton.
+    ///
+    /// Note that the state identifier representation is determined by the
+    /// `S` type variable. This requires a type hint of some sort, either
+    /// by specifying the return type or using the turbofish, e.g.,
+    /// `build_with_size::<u16, _, _>(...)`.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasick, AhoCorasickBuilder};
+    ///
+    /// # fn example() -> Result<(), ::aho_corasick::Error> {
+    /// let patterns = &["foo", "bar", "baz"];
+    /// let ac: AhoCorasick<u8> = AhoCorasickBuilder::new()
+    ///     .build_with_size(patterns)?;
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// # Ok(()) }; example().unwrap()
+    /// ```
+    ///
+    /// Or alternatively, with turbofish:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// # fn example() -> Result<(), ::aho_corasick::Error> {
+    /// let patterns = &["foo", "bar", "baz"];
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .build_with_size::<u8, _, _>(patterns)?;
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// # Ok(()) }; example().unwrap()
+    /// ```
+    pub fn build_with_size<S, I, P>(
+        &self,
+        patterns: I,
+    ) -> Result<AhoCorasick<S>>
+    where
+        S: StateID,
+        I: IntoIterator<Item = P>,
+        P: AsRef<[u8]>,
+    {
+        let nfa = self.nfa_builder.build(patterns)?;
+        let match_kind = nfa.match_kind().clone();
+        let imp = if self.dfa {
+            let dfa = self.dfa_builder.build(&nfa)?;
+            Imp::DFA(dfa)
+        } else {
+            Imp::NFA(nfa)
+        };
+        Ok(AhoCorasick { imp, match_kind })
+    }
+
+    /// Automatically configure the settings on this builder according to the
+    /// patterns that will be used to construct the automaton.
+    ///
+    /// The idea here is to balance space and time automatically. That is, when
+    /// searching a small number of patterns, this will attempt to use the
+    /// fastest possible configuration since the total space required will be
+    /// small anyway. As the number of patterns grows, this will fall back to
+    /// slower configurations that use less space.
+    ///
+    /// This is guaranteed to never set `match_kind`, but any other option may
+    /// be overridden.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// let patterns = &["foo", "bar", "baz"];
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .auto_configure(patterns)
+    ///     .build(patterns);
+    /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
+    /// ```
+    pub fn auto_configure<B: AsRef<[u8]>>(
+        &mut self,
+        patterns: &[B],
+    ) -> &mut AhoCorasickBuilder {
+        // N.B. Currently we only use the length of `patterns` to make a
+        // decision here, and could therefore ask for an `ExactSizeIterator`
+        // instead. But it's conceivable that we might adapt this to look at
+        // the total number of bytes, which would requires a second pass.
+        //
+        // The logic here is fairly rudimentary at the moment, but probably
+        // OK. The idea here is to use the fastest thing possible for a small
+        // number of patterns. That is, a DFA with no byte classes, since byte
+        // classes require an extra indirection for every byte searched. With a
+        // moderate number of patterns, we still want a DFA, but save on both
+        // space and compilation time by enabling byte classes. Finally, fall
+        // back to the slower but smaller NFA.
+        if patterns.len() <= 100 {
+            // N.B. Using byte classes can actually be faster by improving
+            // locality, but this only really applies for multi-megabyte
+            // automata (i.e., automata that don't fit in your CPU's cache).
+            self.dfa(true);
+        } else if patterns.len() <= 5000 {
+            self.dfa(true);
+        }
+        self
+    }
+
+    /// Set the desired match semantics.
+    ///
+    /// The default is `MatchKind::Standard`, which corresponds to the match
+    /// semantics supported by the standard textbook description of the
+    /// Aho-Corasick algorithm. Namely, matches are reported as soon as they
+    /// are found. Moreover, this is the only way to get overlapping matches
+    /// or do stream searching.
+    ///
+    /// The other kinds of match semantics that are supported are
+    /// `MatchKind::LeftmostFirst` and `MatchKind::LeftmostLongest`. The former
+    /// corresponds to the match you would get if you were to try to match
+    /// each pattern at each position in the haystack in the same order that
+    /// you give to the automaton. That is, it returns the leftmost match
+    /// corresponding the earliest pattern given to the automaton. The latter
+    /// corresponds to finding the longest possible match among all leftmost
+    /// matches.
+    ///
+    /// For more details on match semantics, see the
+    /// [documentation for `MatchKind`](enum.MatchKind.html).
+    ///
+    /// # Examples
+    ///
+    /// In these examples, we demonstrate the differences between match
+    /// semantics for a particular set of patterns in a specific order:
+    /// `b`, `abc`, `abcd`.
+    ///
+    /// Standard semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::Standard) // default, not necessary
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("b", &haystack[mat.start()..mat.end()]);
+    /// ```
+    ///
+    /// Leftmost-first semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostFirst)
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("abc", &haystack[mat.start()..mat.end()]);
+    /// ```
+    ///
+    /// Leftmost-longest semantics:
+    ///
+    /// ```
+    /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
+    ///
+    /// let patterns = &["b", "abc", "abcd"];
+    /// let haystack = "abcd";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .match_kind(MatchKind::LeftmostLongest)
+    ///     .build(patterns);
+    /// let mat = ac.find(haystack).expect("should have a match");
+    /// assert_eq!("abcd", &haystack[mat.start()..mat.end()]);
+    /// ```
+    pub fn match_kind(&mut self, kind: MatchKind) -> &mut AhoCorasickBuilder {
+        self.nfa_builder.match_kind(kind);
+        self
+    }
+
+    /// Enable anchored mode, which requires all matches to start at the
+    /// first position in a haystack.
+    ///
+    /// This option is disabled by default.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// let patterns = &["foo", "bar"];
+    /// let haystack = "foobar";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .anchored(true)
+    ///     .build(patterns);
+    /// assert_eq!(1, ac.find_iter(haystack).count());
+    /// ```
+    ///
+    /// When searching for overlapping matches, all matches that start at
+    /// the beginning of a haystack will be reported:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// let patterns = &["foo", "foofoo"];
+    /// let haystack = "foofoo";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .anchored(true)
+    ///     .build(patterns);
+    /// assert_eq!(2, ac.find_overlapping_iter(haystack).count());
+    /// // A non-anchored search would return 3 matches.
+    /// ```
+    pub fn anchored(&mut self, yes: bool) -> &mut AhoCorasickBuilder {
+        self.nfa_builder.anchored(yes);
+        self
+    }
+
+    /// Enable ASCII-aware case insensitive matching.
+    ///
+    /// When this option is enabled, searching will be performed without
+    /// respect to case for ASCII letters (`a-z` and `A-Z`) only.
+    ///
+    /// Enabling this option does not change the search algorithm, but it may
+    /// increase the size of the automaton.
+    ///
+    /// **NOTE:** In the future, support for full Unicode case insensitivity
+    /// may be added, but ASCII case insensitivity is comparatively much
+    /// simpler to add.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use aho_corasick::AhoCorasickBuilder;
+    ///
+    /// let patterns = &["FOO", "bAr", "BaZ"];
+    /// let haystack = "foo bar baz";
+    ///
+    /// let ac = AhoCorasickBuilder::new()
+    ///     .ascii_case_insensitive(true)
+    ///     .build(patterns);
+    /// assert_eq!(3, ac.find_iter(haystack).count());
+    /// ```
+    pub fn ascii_case_insensitive(
+        &mut self,
+        yes: bool,
+    ) -> &mut AhoCorasickBuilder {
+        self.nfa_builder.ascii_case_insensitive(yes);
+        self
+    }
+
+    /// Set the limit on how many NFA states use a dense representation for
+    /// their transitions.
+    ///
+    /// A dense representation uses more space, but supports faster access to
+    /// transitions at search time. Thus, this setting permits the control of a
+    /// space vs time trade off when using the NFA variant of Aho-Corasick.
+    ///
+    /// This limit is expressed in terms of the depth of a state, i.e., the
+    /// number of transitions from the starting state of the NFA. The idea is
+    /// that most of the time searching will be spent near the starting state
+    /// of the automaton, so states near the start state should use a dense
+    /// representation. States further away from the start state would then use
+    /// a sparse representation, which uses less space but is slower to access
+    /// transitions at search time.
+    ///
+    /// By default, this is set to a low but non-zero number.
+    ///
+    /// This setting has no effect if the `dfa` option is enabled.
+    pub fn dense_depth(&mut self, depth: usize) -> &mut AhoCorasickBuilder {
+        self.nfa_builder.dense_depth(depth);
+        self
+    }
+
+    /// Compile the standard Aho-Corasick automaton into a deterministic finite
+    /// automaton (DFA).
+    ///
+    /// When this is disabled (which is the default), then a non-deterministic
+    /// finite automaton (NFA) is used instead.
+    ///
+    /// The main benefit to a DFA is that it can execute searches more quickly
+    /// than a NFA (perhaps 2-4 times as fast). The main drawback is that the
+    /// DFA uses more space and can take much longer to build.
+    ///
+    /// Enabling this option does not change the time complexity for
+    /// constructing the Aho-Corasick automaton (which is `O(p)` where
+    /// `p` is the total number of patterns being compiled). Enabling this
+    /// option does however reduce the time complexity of non-overlapping
+    /// searches from `O(n + p)` to `O(n)`, where `n` is the length of the
+    /// haystack.
+    ///
+    /// In general, it's a good idea to enable this if you're searching a
+    /// small number of fairly short patterns (~1000), or if you want the
+    /// fastest possible search without regard to compilation time or space
+    /// usage.
+    pub fn dfa(&mut self, yes: bool) -> &mut AhoCorasickBuilder {
+        self.dfa = yes;
+        self
+    }
+
+    /// Enable heuristic prefilter optimizations.
+    ///
+    /// When enabled, searching will attempt to quickly skip to match
+    /// candidates using specialized literal search routines. A prefilter
+    /// cannot always be used, and is generally treated as a heuristic. It
+    /// can be useful to disable this if the prefilter is observed to be
+    /// sub-optimal for a particular workload.
+    ///
+    /// This is enabled by default.
+    pub fn prefilter(&mut self, yes: bool) -> &mut AhoCorasickBuilder {
+        self.nfa_builder.prefilter(yes);
+        self
+    }
+
+    /// Shrink the size of the transition alphabet by mapping bytes to their
+    /// equivalence classes. This only has an effect when the `dfa` option is
+    /// enabled.
+    ///
+    /// When enabled, each a DFA will use a map from all possible bytes
+    /// to their corresponding equivalence class. Each equivalence class
+    /// represents a set of bytes that does not discriminate between a match
+    /// and a non-match in the DFA. For example, the patterns `bar` and `baz`
+    /// have at least five equivalence classes: singleton sets of `b`, `a`, `r`
+    /// and `z`, and a final set that contains every other byte.
+    ///
+    /// The advantage of this map is that the size of the transition table can
+    /// be reduced drastically from `#states * 256 * sizeof(id)` to
+    /// `#states * k * sizeof(id)` where `k` is the number of equivalence
+    /// classes. As a result, total space usage can decrease substantially.
+    /// Moreover, since a smaller alphabet is used, compilation becomes faster
+    /// as well.
+    ///
+    /// The disadvantage of this map is that every byte searched must be
+    /// passed through this map before it can be used to determine the next
+    /// transition. This has a small match time performance cost. However, if
+    /// the DFA is otherwise very large without byte classes, then using byte
+    /// classes can greatly improve memory locality and thus lead to better
+    /// overall performance.
+    ///
+    /// This option is enabled by default.
+    #[deprecated(
+        since = "0.7.16",
+        note = "not carrying its weight, will be always enabled, see: https://github.com/BurntSushi/aho-corasick/issues/57"
+    )]
+    pub fn byte_classes(&mut self, yes: bool) -> &mut AhoCorasickBuilder {
+        self.dfa_builder.byte_classes(yes);
+        self
+    }
+
+    /// Premultiply state identifiers in the transition table. This only has
+    /// an effect when the `dfa` option is enabled.
+    ///
+    /// When enabled, state identifiers are premultiplied to point to their
+    /// corresponding row in the transition table. That is, given the `i`th
+    /// state, its corresponding premultiplied identifier is `i * k` where `k`
+    /// is the alphabet size of the automaton. (The alphabet size is at most
+    /// 256, but is in practice smaller if byte classes is enabled.)
+    ///
+    /// When state identifiers are not premultiplied, then the identifier of
+    /// the `i`th state is `i`.
+    ///
+    /// The advantage of premultiplying state identifiers is that is saves a
+    /// multiplication instruction per byte when searching with a DFA. This has
+    /// been observed to lead to a 20% performance benefit in micro-benchmarks.
+    ///
+    /// The primary disadvantage of premultiplying state identifiers is
+    /// that they require a larger integer size to represent. For example,
+    /// if the DFA has 200 states, then its premultiplied form requires 16
+    /// bits to represent every possible state identifier, where as its
+    /// non-premultiplied form only requires 8 bits.
+    ///
+    /// This option is enabled by default.
+    #[deprecated(
+        since = "0.7.16",
+        note = "not carrying its weight, will be always enabled, see: https://github.com/BurntSushi/aho-corasick/issues/57"
+    )]
+    pub fn premultiply(&mut self, yes: bool) -> &mut AhoCorasickBuilder {
+        self.dfa_builder.premultiply(yes);
+        self
+    }
+}
+
+/// A knob for controlling the match semantics of an Aho-Corasick automaton.
+///
+/// There are two generally different ways that Aho-Corasick automatons can
+/// report matches. The first way is the "standard" approach that results from
+/// implementing most textbook explanations of Aho-Corasick. The second way is
+/// to report only the leftmost non-overlapping matches. The leftmost approach
+/// is in turn split into two different ways of resolving ambiguous matches:
+/// leftmost-first and leftmost-longest.
+///
+/// The `Standard` match kind is the default and is the only one that supports
+/// overlapping matches and stream searching. (Trying to find overlapping
+/// or streaming matches using leftmost match semantics will result in a
+/// panic.) The `Standard` match kind will report matches as they are seen.
+/// When searching for overlapping matches, then all possible matches are
+/// reported. When searching for non-overlapping matches, the first match seen
+/// is reported. For example, for non-overlapping matches, given the patterns
+/// `abcd` and `b` and the subject string `abcdef`, only a match for `b` is
+/// reported since it is detected first. The `abcd` match is never reported
+/// since it overlaps with the `b` match.
+///
+/// In contrast, the leftmost match kind always prefers the leftmost match
+/// among all possible matches. Given the same example as above with `abcd` and
+/// `b` as patterns and `abcdef` as the subject string, the leftmost match is
+/// `abcd` since it begins before the `b` match, even though the `b` match is
+/// detected before the `abcd` match. In this case, the `b` match is not
+/// reported at all since it overlaps with the `abcd` match.
+///
+/// The difference between leftmost-first and leftmost-longest is in how they
+/// resolve ambiguous matches when there are multiple leftmost matches to
+/// choose from. Leftmost-first always chooses the pattern that was provided
+/// earliest, where as leftmost-longest always chooses the longest matching
+/// pattern. For example, given the patterns `a` and `ab` and the subject
+/// string `ab`, the leftmost-first match is `a` but the leftmost-longest match
+/// is `ab`. Conversely, if the patterns were given in reverse order, i.e.,
+/// `ab` and `a`, then both the leftmost-first and leftmost-longest matches
+/// would be `ab`. Stated differently, the leftmost-first match depends on the
+/// order in which the patterns were given to the Aho-Corasick automaton.
+/// Because of that, when leftmost-first matching is used, if a pattern `A`
+/// that appears before a pattern `B` is a prefix of `B`, then it is impossible
+/// to ever observe a match of `B`.
+///
+/// If you're not sure which match kind to pick, then stick with the standard
+/// kind, which is the default. In particular, if you need overlapping or
+/// streaming matches, then you _must_ use the standard kind. The leftmost
+/// kinds are useful in specific circumstances. For example, leftmost-first can
+/// be very useful as a way to implement match priority based on the order of
+/// patterns given and leftmost-longest can be useful for dictionary searching
+/// such that only the longest matching words are reported.
+///
+/// # Relationship with regular expression alternations
+///
+/// Understanding match semantics can be a little tricky, and one easy way
+/// to conceptualize non-overlapping matches from an Aho-Corasick automaton
+/// is to think about them as a simple alternation of literals in a regular
+/// expression. For example, let's say we wanted to match the strings
+/// `Sam` and `Samwise`, which would turn into the regex `Sam|Samwise`. It
+/// turns out that regular expression engines have two different ways of
+/// matching this alternation. The first way, leftmost-longest, is commonly
+/// found in POSIX compatible implementations of regular expressions (such as
+/// `grep`). The second way, leftmost-first, is commonly found in backtracking
+/// implementations such as Perl. (Some regex engines, such as RE2 and Rust's
+/// regex engine do not use backtracking, but still implement leftmost-first
+/// semantics in an effort to match the behavior of dominant backtracking
+/// regex engines such as those found in Perl, Ruby, Python, Javascript and
+/// PHP.)
+///
+/// That is, when matching `Sam|Samwise` against `Samwise`, a POSIX regex
+/// will match `Samwise` because it is the longest possible match, but a
+/// Perl-like regex will match `Sam` since it appears earlier in the
+/// alternation. Indeed, the regex `Sam|Samwise` in a Perl-like regex engine
+/// will never match `Samwise` since `Sam` will always have higher priority.
+/// Conversely, matching the regex `Samwise|Sam` against `Samwise` will lead to
+/// a match of `Samwise` in both POSIX and Perl-like regexes since `Samwise` is
+/// still longest match, but it also appears earlier than `Sam`.
+///
+/// The "standard" match semantics of Aho-Corasick generally don't correspond
+/// to the match semantics of any large group of regex implementations, so
+/// there's no direct analogy that can be made here. Standard match semantics
+/// are generally useful for overlapping matches, or if you just want to see
+/// matches as they are detected.
+///
+/// The main conclusion to draw from this section is that the match semantics
+/// can be tweaked to precisely match either Perl-like regex alternations or
+/// POSIX regex alternations.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum MatchKind {
+    /// Use standard match semantics, which support overlapping matches. When
+    /// used with non-overlapping matches, matches are reported as they are
+    /// seen.
+    Standard,
+    /// Use leftmost-first match semantics, which reports leftmost matches.
+    /// When there are multiple possible leftmost matches, the match
+    /// corresponding to the pattern that appeared earlier when constructing
+    /// the automaton is reported.
+    ///
+    /// This does **not** support overlapping matches or stream searching. If
+    /// this match kind is used, attempting to find overlapping matches or
+    /// stream matches will panic.
+    LeftmostFirst,
+    /// Use leftmost-longest match semantics, which reports leftmost matches.
+    /// When there are multiple possible leftmost matches, the longest match
+    /// is chosen.
+    ///
+    /// This does **not** support overlapping matches or stream searching. If
+    /// this match kind is used, attempting to find overlapping matches or
+    /// stream matches will panic.
+    LeftmostLongest,
+    /// Hints that destructuring should not be exhaustive.
+    ///
+    /// This enum may grow additional variants, so this makes sure clients
+    /// don't count on exhaustive matching. (Otherwise, adding a new variant
+    /// could break existing code.)
+    #[doc(hidden)]
+    __Nonexhaustive,
+}
+
+/// The default match kind is `MatchKind::Standard`.
+impl Default for MatchKind {
+    fn default() -> MatchKind {
+        MatchKind::Standard
+    }
+}
+
+impl MatchKind {
+    fn supports_overlapping(&self) -> bool {
+        self.is_standard()
+    }
+
+    fn supports_stream(&self) -> bool {
+        // TODO: It may be possible to support this. It's hard.
+        //
+        // See: https://github.com/rust-lang/regex/issues/425#issuecomment-471367838
+        self.is_standard()
+    }
+
+    pub(crate) fn is_standard(&self) -> bool {
+        *self == MatchKind::Standard
+    }
+
+    pub(crate) fn is_leftmost(&self) -> bool {
+        *self == MatchKind::LeftmostFirst
+            || *self == MatchKind::LeftmostLongest
+    }
+
+    pub(crate) fn is_leftmost_first(&self) -> bool {
+        *self == MatchKind::LeftmostFirst
+    }
+
+    /// Convert this match kind into a packed match kind. If this match kind
+    /// corresponds to standard semantics, then this returns None, since
+    /// packed searching does not support standard semantics.
+    pub(crate) fn as_packed(&self) -> Option<packed::MatchKind> {
+        match *self {
+            MatchKind::Standard => None,
+            MatchKind::LeftmostFirst => Some(packed::MatchKind::LeftmostFirst),
+            MatchKind::LeftmostLongest => {
+                Some(packed::MatchKind::LeftmostLongest)
+            }
+            MatchKind::__Nonexhaustive => unreachable!(),
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn oibits() {
+        use std::panic::{RefUnwindSafe, UnwindSafe};
+
+        fn assert_send<T: Send>() {}
+        fn assert_sync<T: Sync>() {}
+        fn assert_unwind_safe<T: RefUnwindSafe + UnwindSafe>() {}
+
+        assert_send::<AhoCorasick>();
+        assert_sync::<AhoCorasick>();
+        assert_unwind_safe::<AhoCorasick>();
+        assert_send::<AhoCorasickBuilder>();
+        assert_sync::<AhoCorasickBuilder>();
+        assert_unwind_safe::<AhoCorasickBuilder>();
+    }
+}
diff --git a/vendor/aho-corasick/src/automaton.rs b/vendor/aho-corasick/src/automaton.rs
new file mode 100644
index 0000000..b971bf3
--- /dev/null
+++ b/vendor/aho-corasick/src/automaton.rs
@@ -0,0 +1,573 @@
+use crate::ahocorasick::MatchKind;
+use crate::prefilter::{self, Candidate, Prefilter, PrefilterState};
+use crate::state_id::{dead_id, fail_id, StateID};
+use crate::Match;
+
+// NOTE: This trait essentially started as a copy of the same trait from from
+// regex-automata, with some wording changed since we use this trait for
+// NFAs in addition to DFAs in this crate. Additionally, we do not export
+// this trait. It's only used internally to reduce code duplication. The
+// regex-automata crate needs to expose it because its Regex type is generic
+// over implementations of this trait. In this crate, we encapsulate everything
+// behind the AhoCorasick type.
+//
+// This trait is a bit of a mess, but it's not quite clear how to fix it.
+// Basically, there are several competing concerns:
+//
+// * We need performance, so everything effectively needs to get monomorphized.
+// * There are several variations on searching Aho-Corasick automatons:
+//   overlapping, standard and leftmost. Overlapping and standard are somewhat
+//   combined together below, but there is no real way to combine standard with
+//   leftmost. Namely, leftmost requires continuing a search even after a match
+//   is found, in order to correctly disambiguate a match.
+// * On top of that, *sometimes* callers want to know which state the automaton
+//   is in after searching. This is principally useful for overlapping and
+//   stream searches. However, when callers don't care about this, we really
+//   do not want to be forced to compute it, since it sometimes requires extra
+//   work. Thus, there are effectively two copies of leftmost searching: one
+//   for tracking the state ID and one that doesn't. We should ideally do the
+//   same for standard searching, but my sanity stopped me.
+
+// SAFETY RATIONALE: Previously, the code below went to some length to remove
+// all bounds checks. This generally produced tighter assembly and lead to
+// 20-50% improvements in micro-benchmarks on corpora made up of random
+// characters. This somewhat makes sense, since the branch predictor is going
+// to be at its worse on random text.
+//
+// However, using the aho-corasick-debug tool and manually benchmarking
+// different inputs, the code *with* bounds checks actually wound up being
+// slightly faster:
+//
+//     $ cat input
+//     Sherlock Holmes
+//     John Watson
+//     Professor Moriarty
+//     Irene Adler
+//     Mary Watson
+//
+//     $ aho-corasick-debug-safe \
+//         input OpenSubtitles2018.raw.sample.en --kind leftmost-first --dfa
+//     pattern read time: 32.824µs
+//     automaton build time: 444.687µs
+//     automaton heap usage: 72392 bytes
+//     match count: 639
+//     count time: 1.809961702s
+//
+//     $ aho-corasick-debug-master \
+//         input OpenSubtitles2018.raw.sample.en --kind leftmost-first --dfa
+//     pattern read time: 31.425µs
+//     automaton build time: 317.434µs
+//     automaton heap usage: 72392 bytes
+//     match count: 639
+//     count time: 2.059157705s
+//
+// I was able to reproduce this result on two different machines (an i5 and
+// an i7). Therefore, we go the route of safe code for now.
+
+/// A trait describing the interface of an Aho-Corasick finite state machine.
+///
+/// Every automaton has exactly one fail state, one dead state and exactly one
+/// start state. Generally, these correspond to the first, second and third
+/// states, respectively. The failure state is always treated as a sentinel.
+/// That is, no correct Aho-Corasick automaton will ever transition into the
+/// fail state. The dead state, however, can be transitioned into, but only
+/// when leftmost-first or leftmost-longest match semantics are enabled and
+/// only when at least one match has been observed.
+///
+/// Every automaton also has one or more match states, such that
+/// `Automaton::is_match_state(id)` returns `true` if and only if `id`
+/// corresponds to a match state.
+pub trait Automaton {
+    /// The representation used for state identifiers in this automaton.
+    ///
+    /// Typically, this is one of `u8`, `u16`, `u32`, `u64` or `usize`.
+    type ID: StateID;
+
+    /// The type of matching that should be done.
+    fn match_kind(&self) -> &MatchKind;
+
+    /// Returns true if and only if this automaton uses anchored searches.
+    fn anchored(&self) -> bool;
+
+    /// An optional prefilter for quickly skipping to the next candidate match.
+    /// A prefilter must report at least every match, although it may report
+    /// positions that do not correspond to a match. That is, it must not allow
+    /// false negatives, but can allow false positives.
+    ///
+    /// Currently, a prefilter only runs when the automaton is in the start
+    /// state. That is, the position reported by a prefilter should always
+    /// correspond to the start of a potential match.
+    fn prefilter(&self) -> Option<&dyn Prefilter>;
+
+    /// Return the identifier of this automaton's start state.
+    fn start_state(&self) -> Self::ID;
+
+    /// Returns true if and only if the given state identifier refers to a
+    /// valid state.
+    fn is_valid(&self, id: Self::ID) -> bool;
+
+    /// Returns true if and only if the given identifier corresponds to a match
+    /// state.
+    ///
+    /// The state ID given must be valid, or else implementors may panic.
+    fn is_match_state(&self, id: Self::ID) -> bool;
+
+    /// Returns true if and only if the given identifier corresponds to a state
+    /// that is either the dead state or a match state.
+    ///
+    /// Depending on the implementation of the automaton, this routine can
+    /// be used to save a branch in the core matching loop. Nevertheless,
+    /// `is_match_state(id) || id == dead_id()` is always a valid
+    /// implementation. Indeed, this is the default implementation.
+    ///
+    /// The state ID given must be valid, or else implementors may panic.
+    fn is_match_or_dead_state(&self, id: Self::ID) -> bool {
+        id == dead_id() || self.is_match_state(id)
+    }
+
+    /// If the given state is a match state, return the match corresponding
+    /// to the given match index. `end` must be the ending position of the
+    /// detected match. If no match exists or if `match_index` exceeds the
+    /// number of matches in this state, then `None` is returned.
+    ///
+    /// The state ID given must be valid, or else implementors may panic.
+    ///
+    /// If the given state ID is correct and if the `match_index` is less than
+    /// the number of matches for that state, then this is guaranteed to return
+    /// a match.
+    fn get_match(
+        &self,
+        id: Self::ID,
+        match_index: usize,
+        end: usize,
+    ) -> Option<Match>;
+
+    /// Returns the number of matches for the given state. If the given state
+    /// is not a match state, then this returns 0.
+    ///
+    /// The state ID given must be valid, or else implementors must panic.
+    fn match_count(&self, id: Self::ID) -> usize;
+
+    /// Given the current state that this automaton is in and the next input
+    /// byte, this method returns the identifier of the next state. The
+    /// identifier returned must always be valid and may never correspond to
+    /// the fail state. The returned identifier may, however, point to the
+    /// dead state.
+    ///
+    /// This is not safe so that implementors may look up the next state
+    /// without memory safety checks such as bounds checks. As such, callers
+    /// must ensure that the given identifier corresponds to a valid automaton
+    /// state. Implementors must, in turn, ensure that this routine is safe for
+    /// all valid state identifiers and for all possible `u8` values.
+    fn next_state(&self, current: Self::ID, input: u8) -> Self::ID;
+
+    /// Like next_state, but debug_asserts that the underlying
+    /// implementation never returns a `fail_id()` for the next state.
+    fn next_state_no_fail(&self, current: Self::ID, input: u8) -> Self::ID {
+        let next = self.next_state(current, input);
+        // We should never see a transition to the failure state.
+        debug_assert!(
+            next != fail_id(),
+            "automaton should never return fail_id for next state"
+        );
+        next
+    }
+
+    /// Execute a search using standard match semantics.
+    ///
+    /// This can be used even when the automaton was constructed with leftmost
+    /// match semantics when you want to find the earliest possible match. This
+    /// can also be used as part of an overlapping search implementation.
+    ///
+    /// N.B. This does not report a match if `state_id` is given as a matching
+    /// state. As such, this should not be used directly.
+    #[inline(always)]
+    fn standard_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        if let Some(pre) = self.prefilter() {
+            self.standard_find_at_imp(
+                prestate,
+                Some(pre),
+                haystack,
+                at,
+                state_id,
+            )
+        } else {
+            self.standard_find_at_imp(prestate, None, haystack, at, state_id)
+        }
+    }
+
+    // It's important for this to always be inlined. Namely, its only caller
+    // is standard_find_at, and the inlining should remove the case analysis
+    // for prefilter scanning when there is no prefilter available.
+    #[inline(always)]
+    fn standard_find_at_imp(
+        &self,
+        prestate: &mut PrefilterState,
+        prefilter: Option<&dyn Prefilter>,
+        haystack: &[u8],
+        mut at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        while at < haystack.len() {
+            if let Some(pre) = prefilter {
+                if prestate.is_effective(at) && *state_id == self.start_state()
+                {
+                    let c = prefilter::next(prestate, pre, haystack, at)
+                        .into_option();
+                    match c {
+                        None => return None,
+                        Some(i) => {
+                            at = i;
+                        }
+                    }
+                }
+            }
+            // CORRECTNESS: next_state is correct for all possible u8 values,
+            // so the only thing we're concerned about is the validity of
+            // `state_id`. `state_id` either comes from the caller (in which
+            // case, we assume it is correct), or it comes from the return
+            // value of next_state, which is guaranteed to be correct.
+            *state_id = self.next_state_no_fail(*state_id, haystack[at]);
+            at += 1;
+            // This routine always quits immediately after seeing a
+            // match, and since dead states can only come after seeing
+            // a match, seeing a dead state here is impossible. (Unless
+            // we have an anchored automaton, in which case, dead states
+            // are used to stop a search.)
+            debug_assert!(
+                *state_id != dead_id() || self.anchored(),
+                "standard find should never see a dead state"
+            );
+
+            if self.is_match_or_dead_state(*state_id) {
+                return if *state_id == dead_id() {
+                    None
+                } else {
+                    self.get_match(*state_id, 0, at)
+                };
+            }
+        }
+        None
+    }
+
+    /// Execute a search using leftmost (either first or longest) match
+    /// semantics.
+    ///
+    /// The principle difference between searching with standard semantics and
+    /// searching with leftmost semantics is that leftmost searching will
+    /// continue searching even after a match has been found. Once a match
+    /// is found, the search does not stop until either the haystack has been
+    /// exhausted or a dead state is observed in the automaton. (Dead states
+    /// only exist in automatons constructed with leftmost semantics.) That is,
+    /// we rely on the construction of the automaton to tell us when to quit.
+    #[inline(never)]
+    fn leftmost_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        if let Some(pre) = self.prefilter() {
+            self.leftmost_find_at_imp(
+                prestate,
+                Some(pre),
+                haystack,
+                at,
+                state_id,
+            )
+        } else {
+            self.leftmost_find_at_imp(prestate, None, haystack, at, state_id)
+        }
+    }
+
+    // It's important for this to always be inlined. Namely, its only caller
+    // is leftmost_find_at, and the inlining should remove the case analysis
+    // for prefilter scanning when there is no prefilter available.
+    #[inline(always)]
+    fn leftmost_find_at_imp(
+        &self,
+        prestate: &mut PrefilterState,
+        prefilter: Option<&dyn Prefilter>,
+        haystack: &[u8],
+        mut at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        debug_assert!(self.match_kind().is_leftmost());
+        if self.anchored() && at > 0 && *state_id == self.start_state() {
+            return None;
+        }
+        let mut last_match = self.get_match(*state_id, 0, at);
+        while at < haystack.len() {
+            if let Some(pre) = prefilter {
+                if prestate.is_effective(at) && *state_id == self.start_state()
+                {
+                    let c = prefilter::next(prestate, pre, haystack, at)
+                        .into_option();
+                    match c {
+                        None => return None,
+                        Some(i) => {
+                            at = i;
+                        }
+                    }
+                }
+            }
+            // CORRECTNESS: next_state is correct for all possible u8 values,
+            // so the only thing we're concerned about is the validity of
+            // `state_id`. `state_id` either comes from the caller (in which
+            // case, we assume it is correct), or it comes from the return
+            // value of next_state, which is guaranteed to be correct.
+            *state_id = self.next_state_no_fail(*state_id, haystack[at]);
+            at += 1;
+            if self.is_match_or_dead_state(*state_id) {
+                if *state_id == dead_id() {
+                    // The only way to enter into a dead state is if a match
+                    // has been found, so we assert as much. This is different
+                    // from normal automata, where you might enter a dead state
+                    // if you know a subsequent match will never be found
+                    // (regardless of whether a match has already been found).
+                    // For Aho-Corasick, it is built so that we can match at
+                    // any position, so the possibility of a match always
+                    // exists.
+                    //
+                    // (Unless we have an anchored automaton, in which case,
+                    // dead states are used to stop a search.)
+                    debug_assert!(
+                        last_match.is_some() || self.anchored(),
+                        "failure state should only be seen after match"
+                    );
+                    return last_match;
+                }
+                last_match = self.get_match(*state_id, 0, at);
+            }
+        }
+        last_match
+    }
+
+    /// This is like leftmost_find_at, but does not need to track a caller
+    /// provided state id. In other words, the only output of this routine is a
+    /// match, if one exists.
+    ///
+    /// It is regrettable that we need to effectively copy a chunk of
+    /// implementation twice, but when we don't need to track the state ID, we
+    /// can allow the prefilter to report matches immediately without having
+    /// to re-confirm them with the automaton. The re-confirmation step is
+    /// necessary in leftmost_find_at because tracing through the automaton is
+    /// the only way to correctly set the state ID. (Perhaps an alternative
+    /// would be to keep a map from pattern ID to matching state ID, but that
+    /// complicates the code and still doesn't permit us to defer to the
+    /// prefilter entirely when possible.)
+    ///
+    /// I did try a few things to avoid the code duplication here, but nothing
+    /// optimized as well as this approach. (In microbenchmarks, there was
+    /// about a 25% difference.)
+    #[inline(never)]
+    fn leftmost_find_at_no_state(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+    ) -> Option<Match> {
+        if let Some(pre) = self.prefilter() {
+            self.leftmost_find_at_no_state_imp(
+                prestate,
+                Some(pre),
+                haystack,
+                at,
+            )
+        } else {
+            self.leftmost_find_at_no_state_imp(prestate, None, haystack, at)
+        }
+    }
+
+    // It's important for this to always be inlined. Namely, its only caller
+    // is leftmost_find_at_no_state, and the inlining should remove the case
+    // analysis for prefilter scanning when there is no prefilter available.
+    #[inline(always)]
+    fn leftmost_find_at_no_state_imp(
+        &self,
+        prestate: &mut PrefilterState,
+        prefilter: Option<&dyn Prefilter>,
+        haystack: &[u8],
+        mut at: usize,
+    ) -> Option<Match> {
+        debug_assert!(self.match_kind().is_leftmost());
+        if self.anchored() && at > 0 {
+            return None;
+        }
+        // If our prefilter handles confirmation of matches 100% of the
+        // time, and since we don't need to track state IDs, we can avoid
+        // Aho-Corasick completely.
+        if let Some(pre) = prefilter {
+            // We should never have a prefilter during an anchored search.
+            debug_assert!(!self.anchored());
+            if !pre.reports_false_positives() {
+                return match pre.next_candidate(prestate, haystack, at) {
+                    Candidate::None => None,
+                    Candidate::Match(m) => Some(m),
+                    Candidate::PossibleStartOfMatch(_) => unreachable!(),
+                };
+            }
+        }
+
+        let mut state_id = self.start_state();
+        let mut last_match = self.get_match(state_id, 0, at);
+        while at < haystack.len() {
+            if let Some(pre) = prefilter {
+                if prestate.is_effective(at) && state_id == self.start_state()
+                {
+                    match prefilter::next(prestate, pre, haystack, at) {
+                        Candidate::None => return None,
+                        // Since we aren't tracking a state ID, we can
+                        // quit early once we know we have a match.
+                        Candidate::Match(m) => return Some(m),
+                        Candidate::PossibleStartOfMatch(i) => {
+                            at = i;
+                        }
+                    }
+                }
+            }
+            // CORRECTNESS: next_state is correct for all possible u8 values,
+            // so the only thing we're concerned about is the validity of
+            // `state_id`. `state_id` either comes from the caller (in which
+            // case, we assume it is correct), or it comes from the return
+            // value of next_state, which is guaranteed to be correct.
+            state_id = self.next_state_no_fail(state_id, haystack[at]);
+            at += 1;
+            if self.is_match_or_dead_state(state_id) {
+                if state_id == dead_id() {
+                    // The only way to enter into a dead state is if a
+                    // match has been found, so we assert as much. This
+                    // is different from normal automata, where you might
+                    // enter a dead state if you know a subsequent match
+                    // will never be found (regardless of whether a match
+                    // has already been found). For Aho-Corasick, it is
+                    // built so that we can match at any position, so the
+                    // possibility of a match always exists.
+                    //
+                    // (Unless we have an anchored automaton, in which
+                    // case, dead states are used to stop a search.)
+                    debug_assert!(
+                        last_match.is_some() || self.anchored(),
+                        "failure state should only be seen after match"
+                    );
+                    return last_match;
+                }
+                last_match = self.get_match(state_id, 0, at);
+            }
+        }
+        last_match
+    }
+
+    /// Execute an overlapping search.
+    ///
+    /// When executing an overlapping match, the previous state ID in addition
+    /// to the previous match index should be given. If there are more matches
+    /// at the given state, then the match is reported and the given index is
+    /// incremented.
+    #[inline(always)]
+    fn overlapping_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut Self::ID,
+        match_index: &mut usize,
+    ) -> Option<Match> {
+        if self.anchored() && at > 0 && *state_id == self.start_state() {
+            return None;
+        }
+
+        let match_count = self.match_count(*state_id);
+        if *match_index < match_count {
+            // This is guaranteed to return a match since
+            // match_index < match_count.
+            let result = self.get_match(*state_id, *match_index, at);
+            debug_assert!(result.is_some(), "must be a match");
+            *match_index += 1;
+            return result;
+        }
+
+        *match_index = 0;
+        match self.standard_find_at(prestate, haystack, at, state_id) {
+            None => None,
+            Some(m) => {
+                *match_index = 1;
+                Some(m)
+            }
+        }
+    }
+
+    /// Return the earliest match found. This returns as soon as we know that
+    /// we have a match. As such, this does not necessarily correspond to the
+    /// leftmost starting match, but rather, the leftmost position at which a
+    /// match ends.
+    #[inline(always)]
+    fn earliest_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        if *state_id == self.start_state() {
+            if self.anchored() && at > 0 {
+                return None;
+            }
+            if let Some(m) = self.get_match(*state_id, 0, at) {
+                return Some(m);
+            }
+        }
+        self.standard_find_at(prestate, haystack, at, state_id)
+    }
+
+    /// A convenience function for finding the next match according to the
+    /// match semantics of this automaton. For standard match semantics, this
+    /// finds the earliest match. Otherwise, the leftmost match is found.
+    #[inline(always)]
+    fn find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut Self::ID,
+    ) -> Option<Match> {
+        match *self.match_kind() {
+            MatchKind::Standard => {
+                self.earliest_find_at(prestate, haystack, at, state_id)
+            }
+            MatchKind::LeftmostFirst | MatchKind::LeftmostLongest => {
+                self.leftmost_find_at(prestate, haystack, at, state_id)
+            }
+            MatchKind::__Nonexhaustive => unreachable!(),
+        }
+    }
+
+    /// Like find_at, but does not track state identifiers. This permits some
+    /// optimizations when a prefilter that confirms its own matches is
+    /// present.
+    #[inline(always)]
+    fn find_at_no_state(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+    ) -> Option<Match> {
+        match *self.match_kind() {
+            MatchKind::Standard => {
+                let mut state = self.start_state();
+                self.earliest_find_at(prestate, haystack, at, &mut state)
+            }
+            MatchKind::LeftmostFirst | MatchKind::LeftmostLongest => {
+                self.leftmost_find_at_no_state(prestate, haystack, at)
+            }
+            MatchKind::__Nonexhaustive => unreachable!(),
+        }
+    }
+}
diff --git a/vendor/aho-corasick/src/buffer.rs b/vendor/aho-corasick/src/buffer.rs
new file mode 100644
index 0000000..e7339eb
--- /dev/null
+++ b/vendor/aho-corasick/src/buffer.rs
@@ -0,0 +1,132 @@
+use std::cmp;
+use std::io;
+use std::ptr;
+
+/// The default buffer capacity that we use for the stream buffer.
+const DEFAULT_BUFFER_CAPACITY: usize = 8 * (1 << 10); // 8 KB
+
+/// A fairly simple roll buffer for supporting stream searches.
+///
+/// This buffer acts as a temporary place to store a fixed amount of data when
+/// reading from a stream. Its central purpose is to allow "rolling" some
+/// suffix of the data to the beginning of the buffer before refilling it with
+/// more data from the stream. For example, let's say we are trying to match
+/// "foobar" on a stream. When we report the match, we'd like to not only
+/// report the correct offsets at which the match occurs, but also the matching
+/// bytes themselves. So let's say our stream is a file with the following
+/// contents: `test test foobar test test`. Now assume that we happen to read
+/// the aforementioned file in two chunks: `test test foo` and `bar test test`.
+/// Naively, it would not be possible to report a single contiguous `foobar`
+/// match, but this roll buffer allows us to do that. Namely, after the second
+/// read, the contents of the buffer should be `st foobar test test`, where the
+/// search should ultimately resume immediately after `foo`. (The prefix `st `
+/// is included because the roll buffer saves N bytes at the end of the buffer,
+/// where N is the maximum possible length of a match.)
+///
+/// A lot of the logic for dealing with this is unfortunately split out between
+/// this roll buffer and the `StreamChunkIter`.
+#[derive(Debug)]
+pub struct Buffer {
+    /// The raw buffer contents. This has a fixed size and never increases.
+    buf: Vec<u8>,
+    /// The minimum size of the buffer, which is equivalent to the maximum
+    /// possible length of a match. This corresponds to the amount that we
+    /// roll
+    min: usize,
+    /// The end of the contents of this buffer.
+    end: usize,
+}
+
+impl Buffer {
+    /// Create a new buffer for stream searching. The minimum buffer length
+    /// given should be the size of the maximum possible match length.
+    pub fn new(min_buffer_len: usize) -> Buffer {
+        let min = cmp::max(1, min_buffer_len);
+        // The minimum buffer amount is also the amount that we roll our
+        // buffer in order to support incremental searching. To this end,
+        // our actual capacity needs to be at least 1 byte bigger than our
+        // minimum amount, otherwise we won't have any overlap. In actuality,
+        // we want our buffer to be a bit bigger than that for performance
+        // reasons, so we set a lower bound of `8 * min`.
+        //
+        // TODO: It would be good to find a way to test the streaming
+        // implementation with the minimal buffer size. For now, we just
+        // uncomment out the next line and comment out the subsequent line.
+        // let capacity = 1 + min;
+        let capacity = cmp::max(min * 8, DEFAULT_BUFFER_CAPACITY);
+        Buffer { buf: vec![0; capacity], min, end: 0 }
+    }
+
+    /// Return the contents of this buffer.
+    #[inline]
+    pub fn buffer(&self) -> &[u8] {
+        &self.buf[..self.end]
+    }
+
+    /// Return the minimum size of the buffer. The only way a buffer may be
+    /// smaller than this is if the stream itself contains less than the
+    /// minimum buffer amount.
+    #[inline]
+    pub fn min_buffer_len(&self) -> usize {
+        self.min
+    }
+
+    /// Return the total length of the contents in the buffer.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.end
+    }
+
+    /// Return all free capacity in this buffer.
+    fn free_buffer(&mut self) -> &mut [u8] {
+        &mut self.buf[self.end..]
+    }
+
+    /// Refill the contents of this buffer by reading as much as possible into
+    /// this buffer's free capacity. If no more bytes could be read, then this
+    /// returns false. Otherwise, this reads until it has filled the buffer
+    /// past the minimum amount.
+    pub fn fill<R: io::Read>(&mut self, mut rdr: R) -> io::Result<bool> {
+        let mut readany = false;
+        loop {
+            let readlen = rdr.read(self.free_buffer())?;
+            if readlen == 0 {
+                return Ok(readany);
+            }
+            readany = true;
+            self.end += readlen;
+            if self.len() >= self.min {
+                return Ok(true);
+            }
+        }
+    }
+
+    /// Roll the contents of the buffer so that the suffix of this buffer is
+    /// moved to the front and all other contents are dropped. The size of the
+    /// suffix corresponds precisely to the minimum buffer length.
+    ///
+    /// This should only be called when the entire contents of this buffer have
+    /// been searched.
+    pub fn roll(&mut self) {
+        let roll_start = self
+            .end
+            .checked_sub(self.min)
+            .expect("buffer capacity should be bigger than minimum amount");
+        let roll_len = self.min;
+
+        assert!(roll_start + roll_len <= self.end);
+        unsafe {
+            // SAFETY: A buffer contains Copy data, so there's no problem
+            // moving it around. Safety also depends on our indices being in
+            // bounds, which they always should be, given the assert above.
+            //
+            // TODO: Switch to [T]::copy_within once our MSRV is high enough.
+            ptr::copy(
+                self.buf[roll_start..].as_ptr(),
+                self.buf.as_mut_ptr(),
+                roll_len,
+            );
+        }
+        self.end = roll_len;
+    }
+}
diff --git a/vendor/aho-corasick/src/byte_frequencies.rs b/vendor/aho-corasick/src/byte_frequencies.rs
new file mode 100644
index 0000000..c313b62
--- /dev/null
+++ b/vendor/aho-corasick/src/byte_frequencies.rs
@@ -0,0 +1,258 @@
+pub const BYTE_FREQUENCIES: [u8; 256] = [
+    55,  // '\x00'
+    52,  // '\x01'
+    51,  // '\x02'
+    50,  // '\x03'
+    49,  // '\x04'
+    48,  // '\x05'
+    47,  // '\x06'
+    46,  // '\x07'
+    45,  // '\x08'
+    103, // '\t'
+    242, // '\n'
+    66,  // '\x0b'
+    67,  // '\x0c'
+    229, // '\r'
+    44,  // '\x0e'
+    43,  // '\x0f'
+    42,  // '\x10'
+    41,  // '\x11'
+    40,  // '\x12'
+    39,  // '\x13'
+    38,  // '\x14'
+    37,  // '\x15'
+    36,  // '\x16'
+    35,  // '\x17'
+    34,  // '\x18'
+    33,  // '\x19'
+    56,  // '\x1a'
+    32,  // '\x1b'
+    31,  // '\x1c'
+    30,  // '\x1d'
+    29,  // '\x1e'
+    28,  // '\x1f'
+    255, // ' '
+    148, // '!'
+    164, // '"'
+    149, // '#'
+    136, // '$'
+    160, // '%'
+    155, // '&'
+    173, // "'"
+    221, // '('
+    222, // ')'
+    134, // '*'
+    122, // '+'
+    232, // ','
+    202, // '-'
+    215, // '.'
+    224, // '/'
+    208, // '0'
+    220, // '1'
+    204, // '2'
+    187, // '3'
+    183, // '4'
+    179, // '5'
+    177, // '6'
+    168, // '7'
+    178, // '8'
+    200, // '9'
+    226, // ':'
+    195, // ';'
+    154, // '<'
+    184, // '='
+    174, // '>'
+    126, // '?'
+    120, // '@'
+    191, // 'A'
+    157, // 'B'
+    194, // 'C'
+    170, // 'D'
+    189, // 'E'
+    162, // 'F'
+    161, // 'G'
+    150, // 'H'
+    193, // 'I'
+    142, // 'J'
+    137, // 'K'
+    171, // 'L'
+    176, // 'M'
+    185, // 'N'
+    167, // 'O'
+    186, // 'P'
+    112, // 'Q'
+    175, // 'R'
+    192, // 'S'
+    188, // 'T'
+    156, // 'U'
+    140, // 'V'
+    143, // 'W'
+    123, // 'X'
+    133, // 'Y'
+    128, // 'Z'
+    147, // '['
+    138, // '\\'
+    146, // ']'
+    114, // '^'
+    223, // '_'
+    151, // '`'
+    249, // 'a'
+    216, // 'b'
+    238, // 'c'
+    236, // 'd'
+    253, // 'e'
+    227, // 'f'
+    218, // 'g'
+    230, // 'h'
+    247, // 'i'
+    135, // 'j'
+    180, // 'k'
+    241, // 'l'
+    233, // 'm'
+    246, // 'n'
+    244, // 'o'
+    231, // 'p'
+    139, // 'q'
+    245, // 'r'
+    243, // 's'
+    251, // 't'
+    235, // 'u'
+    201, // 'v'
+    196, // 'w'
+    240, // 'x'
+    214, // 'y'
+    152, // 'z'
+    182, // '{'
+    205, // '|'
+    181, // '}'
+    127, // '~'
+    27,  // '\x7f'
+    212, // '\x80'
+    211, // '\x81'
+    210, // '\x82'
+    213, // '\x83'
+    228, // '\x84'
+    197, // '\x85'
+    169, // '\x86'
+    159, // '\x87'
+    131, // '\x88'
+    172, // '\x89'
+    105, // '\x8a'
+    80,  // '\x8b'
+    98,  // '\x8c'
+    96,  // '\x8d'
+    97,  // '\x8e'
+    81,  // '\x8f'
+    207, // '\x90'
+    145, // '\x91'
+    116, // '\x92'
+    115, // '\x93'
+    144, // '\x94'
+    130, // '\x95'
+    153, // '\x96'
+    121, // '\x97'
+    107, // '\x98'
+    132, // '\x99'
+    109, // '\x9a'
+    110, // '\x9b'
+    124, // '\x9c'
+    111, // '\x9d'
+    82,  // '\x9e'
+    108, // '\x9f'
+    118, // '\xa0'
+    141, // '¡'
+    113, // '¢'
+    129, // '£'
+    119, // '¤'
+    125, // '¥'
+    165, // '¦'
+    117, // '§'
+    92,  // '¨'
+    106, // '©'
+    83,  // 'ª'
+    72,  // '«'
+    99,  // '¬'
+    93,  // '\xad'
+    65,  // '®'
+    79,  // '¯'
+    166, // '°'
+    237, // '±'
+    163, // '²'
+    199, // '³'
+    190, // '´'
+    225, // 'µ'
+    209, // '¶'
+    203, // '·'
+    198, // '¸'
+    217, // '¹'
+    219, // 'º'
+    206, // '»'
+    234, // '¼'
+    248, // '½'
+    158, // '¾'
+    239, // '¿'
+    255, // 'À'
+    255, // 'Á'
+    255, // 'Â'
+    255, // 'Ã'
+    255, // 'Ä'
+    255, // 'Å'
+    255, // 'Æ'
+    255, // 'Ç'
+    255, // 'È'
+    255, // 'É'
+    255, // 'Ê'
+    255, // 'Ë'
+    255, // 'Ì'
+    255, // 'Í'
+    255, // 'Î'
+    255, // 'Ï'
+    255, // 'Ð'
+    255, // 'Ñ'
+    255, // 'Ò'
+    255, // 'Ó'
+    255, // 'Ô'
+    255, // 'Õ'
+    255, // 'Ö'
+    255, // '×'
+    255, // 'Ø'
+    255, // 'Ù'
+    255, // 'Ú'
+    255, // 'Û'
+    255, // 'Ü'
+    255, // 'Ý'
+    255, // 'Þ'
+    255, // 'ß'
+    255, // 'à'
+    255, // 'á'
+    255, // 'â'
+    255, // 'ã'
+    255, // 'ä'
+    255, // 'å'
+    255, // 'æ'
+    255, // 'ç'
+    255, // 'è'
+    255, // 'é'
+    255, // 'ê'
+    255, // 'ë'
+    255, // 'ì'
+    255, // 'í'
+    255, // 'î'
+    255, // 'ï'
+    255, // 'ð'
+    255, // 'ñ'
+    255, // 'ò'
+    255, // 'ó'
+    255, // 'ô'
+    255, // 'õ'
+    255, // 'ö'
+    255, // '÷'
+    255, // 'ø'
+    255, // 'ù'
+    255, // 'ú'
+    255, // 'û'
+    255, // 'ü'
+    255, // 'ý'
+    255, // 'þ'
+    255, // 'ÿ'
+];
diff --git a/vendor/aho-corasick/src/classes.rs b/vendor/aho-corasick/src/classes.rs
new file mode 100644
index 0000000..f84ae21
--- /dev/null
+++ b/vendor/aho-corasick/src/classes.rs
@@ -0,0 +1,238 @@
+use std::fmt;
+
+/// A representation of byte oriented equivalence classes.
+///
+/// This is used in an FSM to reduce the size of the transition table. This can
+/// have a particularly large impact not only on the total size of an FSM, but
+/// also on compile times.
+#[derive(Clone, Copy)]
+pub struct ByteClasses([u8; 256]);
+
+impl ByteClasses {
+    /// Creates a new set of equivalence classes where all bytes are mapped to
+    /// the same class.
+    pub fn empty() -> ByteClasses {
+        ByteClasses([0; 256])
+    }
+
+    /// Creates a new set of equivalence classes where each byte belongs to
+    /// its own equivalence class.
+    pub fn singletons() -> ByteClasses {
+        let mut classes = ByteClasses::empty();
+        for i in 0..256 {
+            classes.set(i as u8, i as u8);
+        }
+        classes
+    }
+
+    /// Set the equivalence class for the given byte.
+    #[inline]
+    pub fn set(&mut self, byte: u8, class: u8) {
+        self.0[byte as usize] = class;
+    }
+
+    /// Get the equivalence class for the given byte.
+    #[inline]
+    pub fn get(&self, byte: u8) -> u8 {
+        // SAFETY: This is safe because all dense transitions have
+        // exactly 256 elements, so all u8 values are valid indices.
+        self.0[byte as usize]
+    }
+
+    /// Return the total number of elements in the alphabet represented by
+    /// these equivalence classes. Equivalently, this returns the total number
+    /// of equivalence classes.
+    #[inline]
+    pub fn alphabet_len(&self) -> usize {
+        self.0[255] as usize + 1
+    }
+
+    /// Returns true if and only if every byte in this class maps to its own
+    /// equivalence class. Equivalently, there are 256 equivalence classes
+    /// and each class contains exactly one byte.
+    #[inline]
+    pub fn is_singleton(&self) -> bool {
+        self.alphabet_len() == 256
+    }
+
+    /// Returns an iterator over a sequence of representative bytes from each
+    /// equivalence class. Namely, this yields exactly N items, where N is
+    /// equivalent to the number of equivalence classes. Each item is an
+    /// arbitrary byte drawn from each equivalence class.
+    ///
+    /// This is useful when one is determinizing an NFA and the NFA's alphabet
+    /// hasn't been converted to equivalence classes yet. Picking an arbitrary
+    /// byte from each equivalence class then permits a full exploration of
+    /// the NFA instead of using every possible byte value.
+    pub fn representatives(&self) -> ByteClassRepresentatives<'_> {
+        ByteClassRepresentatives { classes: self, byte: 0, last_class: None }
+    }
+
+    /// Returns all of the bytes in the given equivalence class.
+    ///
+    /// The second element in the tuple indicates the number of elements in
+    /// the array.
+    fn elements(&self, equiv: u8) -> ([u8; 256], usize) {
+        let (mut array, mut len) = ([0; 256], 0);
+        for b in 0..256 {
+            if self.get(b as u8) == equiv {
+                array[len] = b as u8;
+                len += 1;
+            }
+        }
+        (array, len)
+    }
+}
+
+impl fmt::Debug for ByteClasses {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if self.is_singleton() {
+            write!(f, "ByteClasses({{singletons}})")
+        } else {
+            write!(f, "ByteClasses(")?;
+            for equiv in 0..self.alphabet_len() {
+                let (members, len) = self.elements(equiv as u8);
+                write!(f, " {} => {:?}", equiv, &members[..len])?;
+            }
+            write!(f, ")")
+        }
+    }
+}
+
+/// An iterator over representative bytes from each equivalence class.
+#[derive(Debug)]
+pub struct ByteClassRepresentatives<'a> {
+    classes: &'a ByteClasses,
+    byte: usize,
+    last_class: Option<u8>,
+}
+
+impl<'a> Iterator for ByteClassRepresentatives<'a> {
+    type Item = u8;
+
+    fn next(&mut self) -> Option<u8> {
+        while self.byte < 256 {
+            let byte = self.byte as u8;
+            let class = self.classes.get(byte);
+            self.byte += 1;
+
+            if self.last_class != Some(class) {
+                self.last_class = Some(class);
+                return Some(byte);
+            }
+        }
+        None
+    }
+}
+
+/// A byte class builder keeps track of an *approximation* of equivalence
+/// classes of bytes during NFA construction. That is, every byte in an
+/// equivalence class cannot discriminate between a match and a non-match.
+///
+/// For example, in the literals `abc` and `xyz`, the bytes [\x00-`], [d-w]
+/// and [{-\xFF] never discriminate between a match and a non-match, precisely
+/// because they never occur in the literals anywhere.
+///
+/// Note though that this does not necessarily compute the minimal set of
+/// equivalence classes. For example, in the literals above, the byte ranges
+/// [\x00-`], [d-w] and [{-\xFF] are all treated as distinct equivalence
+/// classes even though they could be treated a single class. The reason for
+/// this is implementation complexity. In the future, we should endeavor to
+/// compute the minimal equivalence classes since they can have a rather large
+/// impact on the size of the DFA.
+///
+/// The representation here is 256 booleans, all initially set to false. Each
+/// boolean maps to its corresponding byte based on position. A `true` value
+/// indicates the end of an equivalence class, where its corresponding byte
+/// and all of the bytes corresponding to all previous contiguous `false`
+/// values are in the same equivalence class.
+///
+/// This particular representation only permits contiguous ranges of bytes to
+/// be in the same equivalence class, which means that we can never discover
+/// the true minimal set of equivalence classes.
+#[derive(Debug)]
+pub struct ByteClassBuilder(Vec<bool>);
+
+impl ByteClassBuilder {
+    /// Create a new builder of byte classes where all bytes are part of the
+    /// same equivalence class.
+    pub fn new() -> ByteClassBuilder {
+        ByteClassBuilder(vec![false; 256])
+    }
+
+    /// Indicate the the range of byte given (inclusive) can discriminate a
+    /// match between it and all other bytes outside of the range.
+    pub fn set_range(&mut self, start: u8, end: u8) {
+        debug_assert!(start <= end);
+        if start > 0 {
+            self.0[start as usize - 1] = true;
+        }
+        self.0[end as usize] = true;
+    }
+
+    /// Build byte classes that map all byte values to their corresponding
+    /// equivalence class. The last mapping indicates the largest equivalence
+    /// class identifier (which is never bigger than 255).
+    pub fn build(&self) -> ByteClasses {
+        let mut classes = ByteClasses::empty();
+        let mut class = 0u8;
+        let mut i = 0;
+        loop {
+            classes.set(i as u8, class as u8);
+            if i >= 255 {
+                break;
+            }
+            if self.0[i] {
+                class = class.checked_add(1).unwrap();
+            }
+            i += 1;
+        }
+        classes
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn byte_classes() {
+        let mut set = ByteClassBuilder::new();
+        set.set_range(b'a', b'z');
+
+        let classes = set.build();
+        assert_eq!(classes.get(0), 0);
+        assert_eq!(classes.get(1), 0);
+        assert_eq!(classes.get(2), 0);
+        assert_eq!(classes.get(b'a' - 1), 0);
+        assert_eq!(classes.get(b'a'), 1);
+        assert_eq!(classes.get(b'm'), 1);
+        assert_eq!(classes.get(b'z'), 1);
+        assert_eq!(classes.get(b'z' + 1), 2);
+        assert_eq!(classes.get(254), 2);
+        assert_eq!(classes.get(255), 2);
+
+        let mut set = ByteClassBuilder::new();
+        set.set_range(0, 2);
+        set.set_range(4, 6);
+        let classes = set.build();
+        assert_eq!(classes.get(0), 0);
+        assert_eq!(classes.get(1), 0);
+        assert_eq!(classes.get(2), 0);
+        assert_eq!(classes.get(3), 1);
+        assert_eq!(classes.get(4), 2);
+        assert_eq!(classes.get(5), 2);
+        assert_eq!(classes.get(6), 2);
+        assert_eq!(classes.get(7), 3);
+        assert_eq!(classes.get(255), 3);
+    }
+
+    #[test]
+    fn full_byte_classes() {
+        let mut set = ByteClassBuilder::new();
+        for i in 0..256u16 {
+            set.set_range(i as u8, i as u8);
+        }
+        assert_eq!(set.build().alphabet_len(), 256);
+    }
+}
diff --git a/vendor/aho-corasick/src/dfa.rs b/vendor/aho-corasick/src/dfa.rs
new file mode 100644
index 0000000..a03a254
--- /dev/null
+++ b/vendor/aho-corasick/src/dfa.rs
@@ -0,0 +1,713 @@
+use std::mem::size_of;
+
+use crate::ahocorasick::MatchKind;
+use crate::automaton::Automaton;
+use crate::classes::ByteClasses;
+use crate::error::Result;
+use crate::nfa::{PatternID, PatternLength, NFA};
+use crate::prefilter::{Prefilter, PrefilterObj, PrefilterState};
+use crate::state_id::{dead_id, fail_id, premultiply_overflow_error, StateID};
+use crate::Match;
+
+#[derive(Clone, Debug)]
+pub enum DFA<S> {
+    Standard(Standard<S>),
+    ByteClass(ByteClass<S>),
+    Premultiplied(Premultiplied<S>),
+    PremultipliedByteClass(PremultipliedByteClass<S>),
+}
+
+impl<S: StateID> DFA<S> {
+    fn repr(&self) -> &Repr<S> {
+        match *self {
+            DFA::Standard(ref dfa) => dfa.repr(),
+            DFA::ByteClass(ref dfa) => dfa.repr(),
+            DFA::Premultiplied(ref dfa) => dfa.repr(),
+            DFA::PremultipliedByteClass(ref dfa) => dfa.repr(),
+        }
+    }
+
+    pub fn match_kind(&self) -> &MatchKind {
+        &self.repr().match_kind
+    }
+
+    pub fn heap_bytes(&self) -> usize {
+        self.repr().heap_bytes
+    }
+
+    pub fn max_pattern_len(&self) -> usize {
+        self.repr().max_pattern_len
+    }
+
+    pub fn pattern_count(&self) -> usize {
+        self.repr().pattern_count
+    }
+
+    pub fn prefilter(&self) -> Option<&dyn Prefilter> {
+        self.repr().prefilter.as_ref().map(|p| p.as_ref())
+    }
+
+    pub fn start_state(&self) -> S {
+        self.repr().start_id
+    }
+
+    #[inline(always)]
+    pub fn overlapping_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut S,
+        match_index: &mut usize,
+    ) -> Option<Match> {
+        match *self {
+            DFA::Standard(ref dfa) => dfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+            DFA::ByteClass(ref dfa) => dfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+            DFA::Premultiplied(ref dfa) => dfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+            DFA::PremultipliedByteClass(ref dfa) => dfa.overlapping_find_at(
+                prestate,
+                haystack,
+                at,
+                state_id,
+                match_index,
+            ),
+        }
+    }
+
+    #[inline(always)]
+    pub fn earliest_find_at(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+        state_id: &mut S,
+    ) -> Option<Match> {
+        match *self {
+            DFA::Standard(ref dfa) => {
+                dfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+            DFA::ByteClass(ref dfa) => {
+                dfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+            DFA::Premultiplied(ref dfa) => {
+                dfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+            DFA::PremultipliedByteClass(ref dfa) => {
+                dfa.earliest_find_at(prestate, haystack, at, state_id)
+            }
+        }
+    }
+
+    #[inline(always)]
+    pub fn find_at_no_state(
+        &self,
+        prestate: &mut PrefilterState,
+        haystack: &[u8],
+        at: usize,
+    ) -> Option<Match> {
+        match *self {
+            DFA::Standard(ref dfa) => {
+                dfa.find_at_no_state(prestate, haystack, at)
+            }
+            DFA::ByteClass(ref dfa) => {
+                dfa.find_at_no_state(prestate, haystack, at)
+            }
+            DFA::Premultiplied(ref dfa) => {
+                dfa.find_at_no_state(prestate, haystack, at)
+            }
+            DFA::PremultipliedByteClass(ref dfa) => {
+                dfa.find_at_no_state(prestate, haystack, at)
+            }
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Standard<S>(Repr<S>);
+
+impl<S: StateID> Standard<S> {
+    fn repr(&self) -> &Repr<S> {
+        &self.0
+    }
+}
+
+impl<S: StateID> Automaton for Standard<S> {
+    type ID = S;
+
+    fn match_kind(&self) -> &MatchKind {
+        &self.repr().match_kind
+    }
+
+    fn anchored(&self) -> bool {
+        self.repr().anchored
+    }
+
+    fn prefilter(&self) -> Option<&dyn Prefilter> {
+        self.repr().prefilter.as_ref().map(|p| p.as_ref())
+    }
+
+    fn start_state(&self) -> S {
+        self.repr().start_id
+    }
+
+    fn is_valid(&self, id: S) -> bool {
+        id.to_usize() < self.repr().state_count
+    }
+
+    fn is_match_state(&self, id: S) -> bool {
+        self.repr().is_match_state(id)
+    }
+
+    fn is_match_or_dead_state(&self, id: S) -> bool {
+        self.repr().is_match_or_dead_state(id)
+    }
+
+    fn get_match(
+        &self,
+        id: S,
+        match_index: usize,
+        end: usize,
+    ) -> Option<Match> {
+        self.repr().get_match(id, match_index, end)
+    }
+
+    fn match_count(&self, id: S) -> usize {
+        self.repr().match_count(id)
+    }
+
+    fn next_state(&self, current: S, input: u8) -> S {
+        let o = current.to_usize() * 256 + input as usize;
+        self.repr().trans[o]
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct ByteClass<S>(Repr<S>);
+
+impl<S: StateID> ByteClass<S> {
+    fn repr(&self) -> &Repr<S> {
+        &self.0
+    }
+}
+
+impl<S: StateID> Automaton for ByteClass<S> {
+    type ID = S;
+
+    fn match_kind(&self) -> &MatchKind {
+        &self.repr().match_kind
+    }
+
+    fn anchored(&self) -> bool {
+        self.repr().anchored
+    }
+
+    fn prefilter(&self) -> Option<&dyn Prefilter> {
+        self.repr().prefilter.as_ref().map(|p| p.as_ref())
+    }
+
+    fn start_state(&self) -> S {
+        self.repr().start_id
+    }
+
+    fn is_valid(&self, id: S) -> bool {
+        id.to_usize() < self.repr().state_count
+    }
+
+    fn is_match_state(&self, id: S) -> bool {
+        self.repr().is_match_state(id)
+    }
+
+    fn is_match_or_dead_state(&self, id: S) -> bool {
+        self.repr().is_match_or_dead_state(id)
+    }
+
+    fn get_match(
+        &self,
+        id: S,
+        match_index: usize,
+        end: usize,
+    ) -> Option<Match> {
+        self.repr().get_match(id, match_index, end)
+    }
+
+    fn match_count(&self, id: S) -> usize {
+        self.repr().match_count(id)
+    }
+
+    fn next_state(&self, current: S, input: u8) -> S {
+        let alphabet_len = self.repr().byte_classes.alphabet_len();
+        let input = self.repr().byte_classes.get(input);
+        let o = current.to_usize() * alphabet_len + input as usize;
+        self.repr().trans[o]
+    }
+}
+
+#[derive(Clone, Debug)]