Bug 1277338 - Part 13: Update vendored crates for newer `js` crate; r=sfink
☠☠ backed out by 59ea29d58ab0 ☠ ☠
authorNick Fitzgerald <fitzgen@gmail.com>
Fri, 01 Sep 2017 16:43:16 -0700
changeset 378421 a8ae266cd61eb004d4f74a989e4d9c6d2ceb5b93
parent 378420 b00ca2e7bda40ed0db38b35d0f97ac5c21b7a7e7
child 378422 3bfaec8923dd64390fbfe53a8c9b98d7fe96276f
push id32429
push userarchaeopteryx@coole-files.de
push dateSat, 02 Sep 2017 08:56:13 +0000
treeherdermozilla-central@a46a5879b878 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1277338
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1277338 - Part 13: Update vendored crates for newer `js` crate; r=sfink
third_party/rust/aho-corasick-0.6.2/.cargo-checksum.json
third_party/rust/aho-corasick-0.6.2/.cargo-ok
third_party/rust/aho-corasick-0.6.2/.travis.yml
third_party/rust/aho-corasick-0.6.2/COPYING
third_party/rust/aho-corasick-0.6.2/Cargo.toml
third_party/rust/aho-corasick-0.6.2/LICENSE-MIT
third_party/rust/aho-corasick-0.6.2/Makefile
third_party/rust/aho-corasick-0.6.2/README.md
third_party/rust/aho-corasick-0.6.2/UNLICENSE
third_party/rust/aho-corasick-0.6.2/benches/bench.rs
third_party/rust/aho-corasick-0.6.2/benches/random.txt
third_party/rust/aho-corasick-0.6.2/ctags.rust
third_party/rust/aho-corasick-0.6.2/examples/dict-search.rs
third_party/rust/aho-corasick-0.6.2/session.vim
third_party/rust/aho-corasick-0.6.2/src/autiter.rs
third_party/rust/aho-corasick-0.6.2/src/full.rs
third_party/rust/aho-corasick-0.6.2/src/lib.rs
third_party/rust/aho-corasick-0.6.2/src/main.rs
third_party/rust/aho-corasick/.cargo-checksum.json
third_party/rust/aho-corasick/Cargo.toml
third_party/rust/aho-corasick/src/autiter.rs
third_party/rust/bindgen-0.29.0/.cargo-checksum.json
third_party/rust/bindgen-0.29.0/.cargo-ok
third_party/rust/bindgen-0.29.0/.github/ISSUE_TEMPLATE.md
third_party/rust/bindgen-0.29.0/.travis.yml
third_party/rust/bindgen-0.29.0/CONTRIBUTING.md
third_party/rust/bindgen-0.29.0/Cargo.toml
third_party/rust/bindgen-0.29.0/LICENSE
third_party/rust/bindgen-0.29.0/README.md
third_party/rust/bindgen-0.29.0/appveyor.yml
third_party/rust/bindgen-0.29.0/book/book.toml
third_party/rust/bindgen-0.29.0/book/src/SUMMARY.md
third_party/rust/bindgen-0.29.0/book/src/blacklisting.md
third_party/rust/bindgen-0.29.0/book/src/chapter_1.md
third_party/rust/bindgen-0.29.0/book/src/command-line-usage.md
third_party/rust/bindgen-0.29.0/book/src/cpp.md
third_party/rust/bindgen-0.29.0/book/src/customizing-generated-bindings.md
third_party/rust/bindgen-0.29.0/book/src/introduction.md
third_party/rust/bindgen-0.29.0/book/src/library-usage.md
third_party/rust/bindgen-0.29.0/book/src/nocopy.md
third_party/rust/bindgen-0.29.0/book/src/opaque.md
third_party/rust/bindgen-0.29.0/book/src/replacing-types.md
third_party/rust/bindgen-0.29.0/book/src/requirements.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-0.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-1.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-2.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-3.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-4.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-5.md
third_party/rust/bindgen-0.29.0/book/src/tutorial-6.md
third_party/rust/bindgen-0.29.0/book/src/using-unions.md
third_party/rust/bindgen-0.29.0/book/src/whitelisting.md
third_party/rust/bindgen-0.29.0/build.rs
third_party/rust/bindgen-0.29.0/ci/assert-docs.sh
third_party/rust/bindgen-0.29.0/ci/assert-no-diff.bat
third_party/rust/bindgen-0.29.0/ci/assert-no-diff.sh
third_party/rust/bindgen-0.29.0/ci/assert-rustfmt.sh
third_party/rust/bindgen-0.29.0/ci/before_install.sh
third_party/rust/bindgen-0.29.0/ci/deploy-book.sh
third_party/rust/bindgen-0.29.0/ci/no-includes.sh
third_party/rust/bindgen-0.29.0/ci/test-book.sh
third_party/rust/bindgen-0.29.0/ci/test.bat
third_party/rust/bindgen-0.29.0/ci/test.sh
third_party/rust/bindgen-0.29.0/example-graphviz-ir.png
third_party/rust/bindgen-0.29.0/rustfmt.toml
third_party/rust/bindgen-0.29.0/src/callbacks.rs
third_party/rust/bindgen-0.29.0/src/clang.rs
third_party/rust/bindgen-0.29.0/src/codegen/error.rs
third_party/rust/bindgen-0.29.0/src/codegen/helpers.rs
third_party/rust/bindgen-0.29.0/src/codegen/mod.rs
third_party/rust/bindgen-0.29.0/src/codegen/struct_layout.rs
third_party/rust/bindgen-0.29.0/src/extra_assertions.rs
third_party/rust/bindgen-0.29.0/src/ir/analysis/derive_debug.rs
third_party/rust/bindgen-0.29.0/src/ir/analysis/has_vtable.rs
third_party/rust/bindgen-0.29.0/src/ir/analysis/mod.rs
third_party/rust/bindgen-0.29.0/src/ir/analysis/template_params.rs
third_party/rust/bindgen-0.29.0/src/ir/annotations.rs
third_party/rust/bindgen-0.29.0/src/ir/comment.rs
third_party/rust/bindgen-0.29.0/src/ir/comp.rs
third_party/rust/bindgen-0.29.0/src/ir/context.rs
third_party/rust/bindgen-0.29.0/src/ir/derive.rs
third_party/rust/bindgen-0.29.0/src/ir/dot.rs
third_party/rust/bindgen-0.29.0/src/ir/enum_ty.rs
third_party/rust/bindgen-0.29.0/src/ir/function.rs
third_party/rust/bindgen-0.29.0/src/ir/int.rs
third_party/rust/bindgen-0.29.0/src/ir/item.rs
third_party/rust/bindgen-0.29.0/src/ir/item_kind.rs
third_party/rust/bindgen-0.29.0/src/ir/layout.rs
third_party/rust/bindgen-0.29.0/src/ir/mod.rs
third_party/rust/bindgen-0.29.0/src/ir/module.rs
third_party/rust/bindgen-0.29.0/src/ir/objc.rs
third_party/rust/bindgen-0.29.0/src/ir/template.rs
third_party/rust/bindgen-0.29.0/src/ir/traversal.rs
third_party/rust/bindgen-0.29.0/src/ir/ty.rs
third_party/rust/bindgen-0.29.0/src/ir/var.rs
third_party/rust/bindgen-0.29.0/src/lib.rs
third_party/rust/bindgen-0.29.0/src/log_stubs.rs
third_party/rust/bindgen-0.29.0/src/main.rs
third_party/rust/bindgen-0.29.0/src/options.rs
third_party/rust/bindgen-0.29.0/src/parse.rs
third_party/rust/bindgen-0.29.0/src/regex_set.rs
third_party/rust/bindgen-0.29.0/src/uses.rs
third_party/rust/bindgen/.cargo-checksum.json
third_party/rust/bindgen/.github/ISSUE_TEMPLATE.md
third_party/rust/bindgen/.travis.yml
third_party/rust/bindgen/CONTRIBUTING.md
third_party/rust/bindgen/Cargo.toml
third_party/rust/bindgen/LICENSE
third_party/rust/bindgen/README.md
third_party/rust/bindgen/appveyor.yml
third_party/rust/bindgen/book/book.toml
third_party/rust/bindgen/book/src/SUMMARY.md
third_party/rust/bindgen/book/src/blacklisting.md
third_party/rust/bindgen/book/src/chapter_1.md
third_party/rust/bindgen/book/src/command-line-usage.md
third_party/rust/bindgen/book/src/cpp.md
third_party/rust/bindgen/book/src/customizing-generated-bindings.md
third_party/rust/bindgen/book/src/introduction.md
third_party/rust/bindgen/book/src/library-usage.md
third_party/rust/bindgen/book/src/nocopy.md
third_party/rust/bindgen/book/src/opaque.md
third_party/rust/bindgen/book/src/replacing-types.md
third_party/rust/bindgen/book/src/requirements.md
third_party/rust/bindgen/book/src/tutorial-0.md
third_party/rust/bindgen/book/src/tutorial-1.md
third_party/rust/bindgen/book/src/tutorial-2.md
third_party/rust/bindgen/book/src/tutorial-3.md
third_party/rust/bindgen/book/src/tutorial-4.md
third_party/rust/bindgen/book/src/tutorial-5.md
third_party/rust/bindgen/book/src/tutorial-6.md
third_party/rust/bindgen/book/src/using-unions.md
third_party/rust/bindgen/book/src/whitelisting.md
third_party/rust/bindgen/build.rs
third_party/rust/bindgen/ci/assert-docs.sh
third_party/rust/bindgen/ci/assert-no-diff.bat
third_party/rust/bindgen/ci/assert-no-diff.sh
third_party/rust/bindgen/ci/assert-rustfmt.sh
third_party/rust/bindgen/ci/before_install.sh
third_party/rust/bindgen/ci/deploy-book.sh
third_party/rust/bindgen/ci/no-includes.sh
third_party/rust/bindgen/ci/test-book.sh
third_party/rust/bindgen/ci/test.bat
third_party/rust/bindgen/ci/test.sh
third_party/rust/bindgen/example-graphviz-ir.png
third_party/rust/bindgen/rustfmt.toml
third_party/rust/bindgen/src/callbacks.rs
third_party/rust/bindgen/src/clang.rs
third_party/rust/bindgen/src/codegen/derive_debug.rs
third_party/rust/bindgen/src/codegen/helpers.rs
third_party/rust/bindgen/src/codegen/mod.rs
third_party/rust/bindgen/src/codegen/struct_layout.rs
third_party/rust/bindgen/src/features.rs
third_party/rust/bindgen/src/ir/analysis/derive_copy.rs
third_party/rust/bindgen/src/ir/analysis/derive_debug.rs
third_party/rust/bindgen/src/ir/analysis/derive_default.rs
third_party/rust/bindgen/src/ir/analysis/derive_hash.rs
third_party/rust/bindgen/src/ir/analysis/derive_partial_eq.rs
third_party/rust/bindgen/src/ir/analysis/has_destructor.rs
third_party/rust/bindgen/src/ir/analysis/has_float.rs
third_party/rust/bindgen/src/ir/analysis/has_type_param_in_array.rs
third_party/rust/bindgen/src/ir/analysis/has_vtable.rs
third_party/rust/bindgen/src/ir/analysis/mod.rs
third_party/rust/bindgen/src/ir/analysis/template_params.rs
third_party/rust/bindgen/src/ir/annotations.rs
third_party/rust/bindgen/src/ir/comment.rs
third_party/rust/bindgen/src/ir/comp.rs
third_party/rust/bindgen/src/ir/context.rs
third_party/rust/bindgen/src/ir/derive.rs
third_party/rust/bindgen/src/ir/dot.rs
third_party/rust/bindgen/src/ir/enum_ty.rs
third_party/rust/bindgen/src/ir/function.rs
third_party/rust/bindgen/src/ir/int.rs
third_party/rust/bindgen/src/ir/item.rs
third_party/rust/bindgen/src/ir/item_kind.rs
third_party/rust/bindgen/src/ir/layout.rs
third_party/rust/bindgen/src/ir/module.rs
third_party/rust/bindgen/src/ir/objc.rs
third_party/rust/bindgen/src/ir/template.rs
third_party/rust/bindgen/src/ir/traversal.rs
third_party/rust/bindgen/src/ir/ty.rs
third_party/rust/bindgen/src/ir/var.rs
third_party/rust/bindgen/src/lib.rs
third_party/rust/bindgen/src/main.rs
third_party/rust/bindgen/src/options.rs
third_party/rust/bindgen/src/parse.rs
third_party/rust/bindgen/src/regex_set.rs
third_party/rust/bindgen/src/uses.rs
third_party/rust/cfg-if-0.1.0/.cargo-checksum.json
third_party/rust/cfg-if-0.1.0/.cargo-ok
third_party/rust/cfg-if-0.1.0/.travis.yml
third_party/rust/cfg-if-0.1.0/Cargo.toml
third_party/rust/cfg-if-0.1.0/README.md
third_party/rust/cfg-if-0.1.0/src/lib.rs
third_party/rust/cfg-if-0.1.0/tests/xcrate.rs
third_party/rust/cfg-if/.cargo-checksum.json
third_party/rust/cfg-if/.travis.yml
third_party/rust/cfg-if/Cargo.toml
third_party/rust/cfg-if/LICENSE-APACHE
third_party/rust/cfg-if/LICENSE-MIT
third_party/rust/cfg-if/src/lib.rs
third_party/rust/clap-2.24.2/.cargo-checksum.json
third_party/rust/clap-2.24.2/.cargo-ok
third_party/rust/clap-2.24.2/.clog.toml
third_party/rust/clap-2.24.2/.github/CONTRIBUTING.md
third_party/rust/clap-2.24.2/.github/ISSUE_TEMPLATE.md
third_party/rust/clap-2.24.2/.travis.yml
third_party/rust/clap-2.24.2/CHANGELOG.md
third_party/rust/clap-2.24.2/CONTRIBUTORS.md
third_party/rust/clap-2.24.2/Cargo.toml
third_party/rust/clap-2.24.2/LICENSE-MIT
third_party/rust/clap-2.24.2/README.md
third_party/rust/clap-2.24.2/appveyor.yml
third_party/rust/clap-2.24.2/clap-test.rs
third_party/rust/clap-2.24.2/index.html
third_party/rust/clap-2.24.2/justfile
third_party/rust/clap-2.24.2/rustfmt.toml
third_party/rust/clap-2.24.2/src/app/help.rs
third_party/rust/clap-2.24.2/src/app/macros.rs
third_party/rust/clap-2.24.2/src/app/meta.rs
third_party/rust/clap-2.24.2/src/app/mod.rs
third_party/rust/clap-2.24.2/src/app/parser.rs
third_party/rust/clap-2.24.2/src/app/settings.rs
third_party/rust/clap-2.24.2/src/app/usage.rs
third_party/rust/clap-2.24.2/src/app/validator.rs
third_party/rust/clap-2.24.2/src/args/any_arg.rs
third_party/rust/clap-2.24.2/src/args/arg.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/base.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/flag.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/mod.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/option.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/positional.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/switched.rs
third_party/rust/clap-2.24.2/src/args/arg_builder/valued.rs
third_party/rust/clap-2.24.2/src/args/arg_matcher.rs
third_party/rust/clap-2.24.2/src/args/arg_matches.rs
third_party/rust/clap-2.24.2/src/args/group.rs
third_party/rust/clap-2.24.2/src/args/macros.rs
third_party/rust/clap-2.24.2/src/args/matched_arg.rs
third_party/rust/clap-2.24.2/src/args/mod.rs
third_party/rust/clap-2.24.2/src/args/settings.rs
third_party/rust/clap-2.24.2/src/args/subcommand.rs
third_party/rust/clap-2.24.2/src/completions/bash.rs
third_party/rust/clap-2.24.2/src/completions/fish.rs
third_party/rust/clap-2.24.2/src/completions/macros.rs
third_party/rust/clap-2.24.2/src/completions/mod.rs
third_party/rust/clap-2.24.2/src/completions/powershell.rs
third_party/rust/clap-2.24.2/src/completions/shell.rs
third_party/rust/clap-2.24.2/src/completions/zsh.rs
third_party/rust/clap-2.24.2/src/errors.rs
third_party/rust/clap-2.24.2/src/fmt.rs
third_party/rust/clap-2.24.2/src/lib.rs
third_party/rust/clap-2.24.2/src/macros.rs
third_party/rust/clap-2.24.2/src/osstringext.rs
third_party/rust/clap-2.24.2/src/strext.rs
third_party/rust/clap-2.24.2/src/suggestions.rs
third_party/rust/clap-2.24.2/src/usage_parser.rs
third_party/rust/clap/.appveyor.yml
third_party/rust/clap/.cargo-checksum.json
third_party/rust/clap/.mention-bot
third_party/rust/clap/CHANGELOG.md
third_party/rust/clap/Cargo.toml
third_party/rust/clap/README.md
third_party/rust/clap/appveyor.yml
third_party/rust/clap/clap-test.rs
third_party/rust/clap/src/app/help.rs
third_party/rust/clap/src/app/macros.rs
third_party/rust/clap/src/app/parser.rs
third_party/rust/clap/src/app/settings.rs
third_party/rust/clap/src/app/usage.rs
third_party/rust/clap/src/app/validator.rs
third_party/rust/clap/src/args/arg_builder/positional.rs
third_party/rust/clap/src/args/group.rs
third_party/rust/clap/src/args/macros.rs
third_party/rust/clap/src/args/settings.rs
third_party/rust/clap/src/completions/powershell.rs
third_party/rust/clap/src/errors.rs
third_party/rust/clap/src/fmt.rs
third_party/rust/clap/src/lib.rs
third_party/rust/clap/src/macros.rs
third_party/rust/clap/src/suggestions.rs
third_party/rust/cmake/.cargo-checksum.json
third_party/rust/cmake/.cargo-ok
third_party/rust/cmake/.travis.yml
third_party/rust/cmake/Cargo.toml
third_party/rust/cmake/LICENSE-APACHE
third_party/rust/cmake/LICENSE-MIT
third_party/rust/cmake/README.md
third_party/rust/cmake/src/lib.rs
third_party/rust/env_logger-0.4.1/.cargo-checksum.json
third_party/rust/env_logger-0.4.1/.cargo-ok
third_party/rust/env_logger-0.4.1/Cargo.toml
third_party/rust/env_logger-0.4.1/LICENSE-APACHE
third_party/rust/env_logger-0.4.1/LICENSE-MIT
third_party/rust/env_logger-0.4.1/src/lib.rs
third_party/rust/env_logger-0.4.1/src/regex.rs
third_party/rust/env_logger-0.4.1/src/string.rs
third_party/rust/env_logger-0.4.1/tests/regexp_filter.rs
third_party/rust/env_logger/.cargo-checksum.json
third_party/rust/env_logger/Cargo.toml
third_party/rust/env_logger/src/lib.rs
third_party/rust/gcc-0.3.42/.cargo-checksum.json
third_party/rust/gcc-0.3.42/.cargo-ok
third_party/rust/gcc-0.3.42/.travis.yml
third_party/rust/gcc-0.3.42/Cargo.toml
third_party/rust/gcc-0.3.42/LICENSE-APACHE
third_party/rust/gcc-0.3.42/LICENSE-MIT
third_party/rust/gcc-0.3.42/README.md
third_party/rust/gcc-0.3.42/appveyor.yml
third_party/rust/gcc-0.3.42/src/bin/gcc-shim.rs
third_party/rust/gcc-0.3.42/src/lib.rs
third_party/rust/gcc-0.3.42/src/registry.rs
third_party/rust/gcc-0.3.42/src/windows_registry.rs
third_party/rust/gcc-0.3.42/tests/cc_env.rs
third_party/rust/gcc-0.3.42/tests/support/mod.rs
third_party/rust/gcc-0.3.42/tests/test.rs
third_party/rust/gcc/.cargo-checksum.json
third_party/rust/gcc/.travis.yml
third_party/rust/gcc/Cargo.toml
third_party/rust/gcc/README.md
third_party/rust/gcc/src/com.rs
third_party/rust/gcc/src/lib.rs
third_party/rust/gcc/src/setup_config.rs
third_party/rust/gcc/src/winapi.rs
third_party/rust/gcc/src/windows_registry.rs
third_party/rust/gcc/tests/test.rs
third_party/rust/libz-sys/.cargo-checksum.json
third_party/rust/libz-sys/Cargo.toml
third_party/rust/libz-sys/appveyor.yml
third_party/rust/libz-sys/build.rs
third_party/rust/log-0.3.6/.cargo-checksum.json
third_party/rust/log-0.3.6/.cargo-ok
third_party/rust/log-0.3.6/.travis.yml
third_party/rust/log-0.3.6/Cargo.toml
third_party/rust/log-0.3.6/LICENSE-APACHE
third_party/rust/log-0.3.6/LICENSE-MIT
third_party/rust/log-0.3.6/README.md
third_party/rust/log-0.3.6/appveyor.yml
third_party/rust/log-0.3.6/src/lib.rs
third_party/rust/log-0.3.6/src/macros.rs
third_party/rust/log-0.3.6/tests/filters.rs
third_party/rust/log/.cargo-checksum.json
third_party/rust/log/.travis.yml
third_party/rust/log/Cargo.toml
third_party/rust/log/README.md
third_party/rust/log/src/lib.rs
third_party/rust/log/src/macros.rs
third_party/rust/num-traits-0.1.37/.cargo-checksum.json
third_party/rust/num-traits-0.1.37/.cargo-ok
third_party/rust/num-traits-0.1.37/Cargo.toml
third_party/rust/num-traits-0.1.37/LICENSE-APACHE
third_party/rust/num-traits-0.1.37/LICENSE-MIT
third_party/rust/num-traits-0.1.37/src/bounds.rs
third_party/rust/num-traits-0.1.37/src/cast.rs
third_party/rust/num-traits-0.1.37/src/float.rs
third_party/rust/num-traits-0.1.37/src/identities.rs
third_party/rust/num-traits-0.1.37/src/int.rs
third_party/rust/num-traits-0.1.37/src/lib.rs
third_party/rust/num-traits-0.1.37/src/ops/checked.rs
third_party/rust/num-traits-0.1.37/src/ops/mod.rs
third_party/rust/num-traits-0.1.37/src/ops/saturating.rs
third_party/rust/num-traits-0.1.37/src/ops/wrapping.rs
third_party/rust/num-traits-0.1.37/src/pow.rs
third_party/rust/num-traits-0.1.37/src/sign.rs
third_party/rust/num-traits/.cargo-checksum.json
third_party/rust/num-traits/Cargo.toml
third_party/rust/num-traits/src/bounds.rs
third_party/rust/num-traits/src/cast.rs
third_party/rust/num-traits/src/identities.rs
third_party/rust/num-traits/src/lib.rs
third_party/rust/num-traits/src/ops/checked.rs
third_party/rust/num-traits/src/ops/wrapping.rs
third_party/rust/num-traits/src/sign.rs
third_party/rust/num_cpus-1.2.1/.cargo-checksum.json
third_party/rust/num_cpus-1.2.1/.cargo-ok
third_party/rust/num_cpus-1.2.1/.travis.yml
third_party/rust/num_cpus-1.2.1/Cargo.toml
third_party/rust/num_cpus-1.2.1/LICENSE-APACHE
third_party/rust/num_cpus-1.2.1/LICENSE-MIT
third_party/rust/num_cpus-1.2.1/README.md
third_party/rust/num_cpus-1.2.1/src/lib.rs
third_party/rust/num_cpus/.appveyor.yml
third_party/rust/num_cpus/.cargo-checksum.json
third_party/rust/num_cpus/Cargo.toml
third_party/rust/num_cpus/README.md
third_party/rust/num_cpus/src/lib.rs
third_party/rust/regex-0.2.1/.cargo-checksum.json
third_party/rust/regex-0.2.1/.cargo-ok
third_party/rust/regex-0.2.1/.travis.yml
third_party/rust/regex-0.2.1/CHANGELOG.md
third_party/rust/regex-0.2.1/Cargo.toml
third_party/rust/regex-0.2.1/HACKING.md
third_party/rust/regex-0.2.1/LICENSE-APACHE
third_party/rust/regex-0.2.1/LICENSE-MIT
third_party/rust/regex-0.2.1/PERFORMANCE.md
third_party/rust/regex-0.2.1/README.md
third_party/rust/regex-0.2.1/appveyor.yml
third_party/rust/regex-0.2.1/ci/after_success.sh
third_party/rust/regex-0.2.1/ci/run-kcov
third_party/rust/regex-0.2.1/ci/run-shootout-test
third_party/rust/regex-0.2.1/ci/script.sh
third_party/rust/regex-0.2.1/examples/regexdna-input.txt
third_party/rust/regex-0.2.1/examples/regexdna-output.txt
third_party/rust/regex-0.2.1/examples/shootout-regex-dna-bytes.rs
third_party/rust/regex-0.2.1/examples/shootout-regex-dna-cheat.rs
third_party/rust/regex-0.2.1/examples/shootout-regex-dna-replace.rs
third_party/rust/regex-0.2.1/examples/shootout-regex-dna-single-cheat.rs
third_party/rust/regex-0.2.1/examples/shootout-regex-dna-single.rs
third_party/rust/regex-0.2.1/examples/shootout-regex-dna.rs
third_party/rust/regex-0.2.1/scripts/frequencies.py
third_party/rust/regex-0.2.1/scripts/regex-match-tests.py
third_party/rust/regex-0.2.1/scripts/unicode.py
third_party/rust/regex-0.2.1/src/backtrack.rs
third_party/rust/regex-0.2.1/src/compile.rs
third_party/rust/regex-0.2.1/src/dfa.rs
third_party/rust/regex-0.2.1/src/error.rs
third_party/rust/regex-0.2.1/src/exec.rs
third_party/rust/regex-0.2.1/src/expand.rs
third_party/rust/regex-0.2.1/src/freqs.rs
third_party/rust/regex-0.2.1/src/input.rs
third_party/rust/regex-0.2.1/src/lib.rs
third_party/rust/regex-0.2.1/src/literals.rs
third_party/rust/regex-0.2.1/src/pattern.rs
third_party/rust/regex-0.2.1/src/pikevm.rs
third_party/rust/regex-0.2.1/src/prog.rs
third_party/rust/regex-0.2.1/src/re_builder.rs
third_party/rust/regex-0.2.1/src/re_bytes.rs
third_party/rust/regex-0.2.1/src/re_plugin.rs
third_party/rust/regex-0.2.1/src/re_set.rs
third_party/rust/regex-0.2.1/src/re_trait.rs
third_party/rust/regex-0.2.1/src/re_unicode.rs
third_party/rust/regex-0.2.1/src/simd_accel/mod.rs
third_party/rust/regex-0.2.1/src/simd_accel/teddy128.rs
third_party/rust/regex-0.2.1/src/simd_fallback/mod.rs
third_party/rust/regex-0.2.1/src/simd_fallback/teddy128.rs
third_party/rust/regex-0.2.1/src/sparse.rs
third_party/rust/regex-0.2.1/src/testdata/LICENSE
third_party/rust/regex-0.2.1/src/testdata/README
third_party/rust/regex-0.2.1/src/testdata/basic.dat
third_party/rust/regex-0.2.1/src/testdata/nullsubexpr.dat
third_party/rust/regex-0.2.1/src/testdata/repetition.dat
third_party/rust/regex-0.2.1/src/utf8.rs
third_party/rust/regex-0.2.1/tests/api.rs
third_party/rust/regex-0.2.1/tests/api_str.rs
third_party/rust/regex-0.2.1/tests/bytes.rs
third_party/rust/regex-0.2.1/tests/crazy.rs
third_party/rust/regex-0.2.1/tests/flags.rs
third_party/rust/regex-0.2.1/tests/fowler.rs
third_party/rust/regex-0.2.1/tests/macros.rs
third_party/rust/regex-0.2.1/tests/macros_bytes.rs
third_party/rust/regex-0.2.1/tests/macros_str.rs
third_party/rust/regex-0.2.1/tests/misc.rs
third_party/rust/regex-0.2.1/tests/multiline.rs
third_party/rust/regex-0.2.1/tests/noparse.rs
third_party/rust/regex-0.2.1/tests/plugin.rs
third_party/rust/regex-0.2.1/tests/regression.rs
third_party/rust/regex-0.2.1/tests/replace.rs
third_party/rust/regex-0.2.1/tests/searcher.rs
third_party/rust/regex-0.2.1/tests/set.rs
third_party/rust/regex-0.2.1/tests/shortest_match.rs
third_party/rust/regex-0.2.1/tests/suffix_reverse.rs
third_party/rust/regex-0.2.1/tests/test_backtrack.rs
third_party/rust/regex-0.2.1/tests/test_backtrack_bytes.rs
third_party/rust/regex-0.2.1/tests/test_backtrack_utf8bytes.rs
third_party/rust/regex-0.2.1/tests/test_default.rs
third_party/rust/regex-0.2.1/tests/test_default_bytes.rs
third_party/rust/regex-0.2.1/tests/test_nfa.rs
third_party/rust/regex-0.2.1/tests/test_nfa_bytes.rs
third_party/rust/regex-0.2.1/tests/test_nfa_utf8bytes.rs
third_party/rust/regex-0.2.1/tests/test_plugin.rs
third_party/rust/regex-0.2.1/tests/unicode.rs
third_party/rust/regex-0.2.1/tests/word_boundary.rs
third_party/rust/regex-0.2.1/tests/word_boundary_ascii.rs
third_party/rust/regex-0.2.1/tests/word_boundary_unicode.rs
third_party/rust/regex-syntax-0.4.0/.cargo-checksum.json
third_party/rust/regex-syntax-0.4.0/.cargo-ok
third_party/rust/regex-syntax-0.4.0/Cargo.toml
third_party/rust/regex-syntax-0.4.0/src/lib.rs
third_party/rust/regex-syntax-0.4.0/src/literals.rs
third_party/rust/regex-syntax-0.4.0/src/parser.rs
third_party/rust/regex-syntax-0.4.0/src/properties.rs
third_party/rust/regex-syntax-0.4.0/src/unicode.rs
third_party/rust/regex-syntax/.cargo-checksum.json
third_party/rust/regex-syntax/Cargo.toml
third_party/rust/regex-syntax/src/lib.rs
third_party/rust/regex-syntax/src/literals.rs
third_party/rust/regex-syntax/src/parser.rs
third_party/rust/regex-syntax/src/properties.rs
third_party/rust/regex/.cargo-checksum.json
third_party/rust/regex/CHANGELOG.md
third_party/rust/regex/Cargo.toml
third_party/rust/regex/README.md
third_party/rust/regex/ci/run-kcov
third_party/rust/regex/examples/bug347.rs
third_party/rust/regex/examples/shootout-regex-redux-1.rs
third_party/rust/regex/examples/shootout-regex-redux-chunked.rs
third_party/rust/regex/examples/shootout-regex-redux.rs
third_party/rust/regex/src/backtrack.rs
third_party/rust/regex/src/compile.rs
third_party/rust/regex/src/exec.rs
third_party/rust/regex/src/lib.rs
third_party/rust/regex/src/re_builder.rs
third_party/rust/regex/src/re_bytes.rs
third_party/rust/regex/src/re_unicode.rs
third_party/rust/regex/src/utf8.rs
third_party/rust/regex/tests/macros.rs
third_party/rust/regex/tests/regression.rs
third_party/rust/regex/tests/set.rs
third_party/rust/regex/tests/test_default_bytes.rs
third_party/rust/rustc-serialize-0.3.22/.cargo-checksum.json
third_party/rust/rustc-serialize-0.3.22/.cargo-ok
third_party/rust/rustc-serialize-0.3.22/.travis.yml
third_party/rust/rustc-serialize-0.3.22/Cargo.toml
third_party/rust/rustc-serialize-0.3.22/LICENSE-APACHE
third_party/rust/rustc-serialize-0.3.22/LICENSE-MIT
third_party/rust/rustc-serialize-0.3.22/README.md
third_party/rust/rustc-serialize-0.3.22/appveyor.yml
third_party/rust/rustc-serialize-0.3.22/benches/base64.rs
third_party/rust/rustc-serialize-0.3.22/benches/hex.rs
third_party/rust/rustc-serialize-0.3.22/benches/json.rs
third_party/rust/rustc-serialize-0.3.22/src/base64.rs
third_party/rust/rustc-serialize-0.3.22/src/collection_impls.rs
third_party/rust/rustc-serialize-0.3.22/src/hex.rs
third_party/rust/rustc-serialize-0.3.22/src/json.rs
third_party/rust/rustc-serialize-0.3.22/src/lib.rs
third_party/rust/rustc-serialize-0.3.22/src/serialize.rs
third_party/rust/rustc-serialize/.cargo-checksum.json
third_party/rust/rustc-serialize/Cargo.toml
third_party/rust/rustc-serialize/README.md
third_party/rust/rustc-serialize/src/base64.rs
third_party/rust/rustc-serialize/src/hex.rs
third_party/rust/rustc-serialize/src/json.rs
third_party/rust/rustc-serialize/src/lib.rs
third_party/rust/textwrap/.appveyor.yml
third_party/rust/textwrap/.cargo-checksum.json
third_party/rust/textwrap/.cargo-ok
third_party/rust/textwrap/.travis.yml
third_party/rust/textwrap/Cargo.toml
third_party/rust/textwrap/LICENSE
third_party/rust/textwrap/README.md
third_party/rust/textwrap/benches/linear.rs
third_party/rust/textwrap/examples/layout.rs
third_party/rust/textwrap/examples/termwidth.rs
third_party/rust/textwrap/src/lib.rs
third_party/rust/thread-id-3.0.0/.appveyor.yml
third_party/rust/thread-id-3.0.0/.cargo-checksum.json
third_party/rust/thread-id-3.0.0/.cargo-ok
third_party/rust/thread-id-3.0.0/.travis.yml
third_party/rust/thread-id-3.0.0/Cargo.toml
third_party/rust/thread-id-3.0.0/license
third_party/rust/thread-id-3.0.0/readme.md
third_party/rust/thread-id-3.0.0/src/lib.rs
third_party/rust/thread-id/.appveyor.yml
third_party/rust/thread-id/.cargo-checksum.json
third_party/rust/thread-id/.travis.yml
third_party/rust/thread-id/Cargo.toml
third_party/rust/thread-id/changelog.md
third_party/rust/thread-id/license
third_party/rust/thread-id/license-apache
third_party/rust/thread-id/license-mit
third_party/rust/thread-id/readme.md
third_party/rust/thread-id/src/lib.rs
third_party/rust/vcpkg/.cargo-checksum.json
third_party/rust/vcpkg/.cargo-ok
third_party/rust/vcpkg/Cargo.toml
third_party/rust/vcpkg/src/lib.rs
third_party/rust/which/.cargo-checksum.json
third_party/rust/which/.cargo-ok
third_party/rust/which/Cargo.toml
third_party/rust/which/LICENSE.txt
third_party/rust/which/README.md
third_party/rust/which/src/lib.rs
copy from third_party/rust/aho-corasick/.cargo-checksum.json
copy to third_party/rust/aho-corasick-0.6.2/.cargo-checksum.json
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/.travis.yml
@@ -0,0 +1,13 @@
+language: rust
+rust:
+  - 1.12.0
+  - stable
+  - beta
+  - nightly
+script:
+  - cargo build --verbose
+  - cargo test --verbose
+  - cargo doc
+  - if [ "$TRAVIS_RUST_VERSION" = "nightly" ]; then
+      cargo bench --verbose;
+    fi
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/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.
copy from third_party/rust/aho-corasick/Cargo.toml
copy to third_party/rust/aho-corasick-0.6.2/Cargo.toml
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/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.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/Makefile
@@ -0,0 +1,14 @@
+all:
+	echo Nothing to do...
+
+ctags:
+	ctags --recurse --options=ctags.rust --languages=Rust
+
+docs:
+	cargo doc
+	in-dir ./target/doc fix-perms
+	rscp ./target/doc/* gopher:~/www/burntsushi.net/rustdoc/
+
+push:
+	git push origin master
+	git push github master
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/README.md
@@ -0,0 +1,55 @@
+This crate provides an implementation of the
+[Aho-Corasick](http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm)
+algorithm. Its intended use case is for fast substring matching, particularly
+when matching multiple substrings in a search text. This is achieved by
+compiling the substrings into a finite state machine.
+
+This implementation provides optimal algorithmic time complexity. Construction
+of the finite state machine is `O(p)` where `p` is the length of the substrings
+concatenated. Matching against search text is `O(n + p + m)`, where `n` is
+the length of the search text and `m` is the number of matches.
+
+[![Build status](https://api.travis-ci.org/BurntSushi/aho-corasick.png)](https://travis-ci.org/BurntSushi/aho-corasick)
+[![](http://meritbadge.herokuapp.com/aho-corasick)](https://crates.io/crates/aho-corasick)
+
+Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
+
+
+### Documentation
+
+[http://burntsushi.net/rustdoc/aho_corasick/](http://burntsushi.net/rustdoc/aho_corasick/).
+
+
+### Example
+
+The documentation contains several examples, and there is a more complete
+example as a full program in `examples/dict-search.rs`.
+
+Here is a quick example showing simple substring matching:
+
+```rust
+use aho_corasick::{Automaton, AcAutomaton, Match};
+
+let aut = AcAutomaton::new(vec!["apple", "maple"]);
+let mut it = aut.find("I like maple apples.");
+assert_eq!(it.next(), Some(Match {
+    pati: 1,
+    start: 7,
+    end: 12,
+}));
+assert_eq!(it.next(), Some(Match {
+    pati: 0,
+    start: 13,
+    end: 18,
+}));
+assert_eq!(it.next(), None);
+```
+
+
+### Alternatives
+
+Aho-Corasick is useful for matching multiple substrings against many long
+strings. If your long string is fixed, then you might consider building a
+[suffix array](https://github.com/BurntSushi/suffix)
+of the search text (which takes `O(n)` time). Matches can then be found in
+`O(plogn)` time.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/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/>
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/benches/bench.rs
@@ -0,0 +1,339 @@
+#![feature(test)]
+
+extern crate aho_corasick;
+extern crate test;
+
+use std::iter;
+
+use aho_corasick::{Automaton, AcAutomaton, Transitions};
+use test::Bencher;
+
+const HAYSTACK_RANDOM: &'static str = include_str!("random.txt");
+const HAYSTACK_SHERLOCK: &'static str = include_str!("sherlock.txt");
+
+fn bench_aut_no_match<P: AsRef<[u8]>, T: Transitions>(
+    b: &mut Bencher,
+    aut: AcAutomaton<P, T>,
+    haystack: &str,
+) {
+    b.bytes = haystack.len() as u64;
+    b.iter(|| assert!(aut.find(haystack).next().is_none()));
+}
+
+fn bench_box_aut_no_match<P: AsRef<[u8]>, T: Transitions>(
+    b: &mut Bencher,
+    aut: AcAutomaton<P, T>,
+    haystack: &str,
+) {
+    b.bytes = haystack.len() as u64;
+    let aut: &Automaton<P> = &aut;
+    b.iter(|| assert!(Automaton::find(&aut, haystack).next().is_none()));
+}
+
+fn bench_full_aut_no_match<P: AsRef<[u8]>, T: Transitions>(
+    b: &mut Bencher,
+    aut: AcAutomaton<P, T>,
+    haystack: &str,
+) {
+    let aut = aut.into_full();
+    b.bytes = haystack.len() as u64;
+    b.iter(|| assert!(aut.find(haystack).next().is_none()));
+}
+
+fn bench_full_aut_overlapping_no_match<P: AsRef<[u8]>, T: Transitions>(
+    b: &mut Bencher,
+    aut: AcAutomaton<P, T>,
+    haystack: &str,
+) {
+    let aut = aut.into_full();
+    b.bytes = haystack.len() as u64;
+    b.iter(|| assert!(aut.find_overlapping(haystack).count() == 0));
+}
+
+fn bench_naive_no_match<S>(b: &mut Bencher, needles: Vec<S>, haystack: &str)
+        where S: Into<String> {
+    b.bytes = haystack.len() as u64;
+    let needles: Vec<String> = needles.into_iter().map(Into::into).collect();
+    b.iter(|| assert!(!naive_find(&needles, haystack)));
+}
+
+fn haystack_same(letter: char) -> String {
+    iter::repeat(letter).take(10000).collect()
+}
+
+macro_rules! aut_benches {
+    ($prefix:ident, $aut:expr, $bench:expr) => {
+        mod $prefix {
+#![allow(unused_imports)]
+use aho_corasick::{Automaton, AcAutomaton, Sparse};
+use test::Bencher;
+
+use super::{
+    HAYSTACK_RANDOM, haystack_same,
+    bench_aut_no_match, bench_box_aut_no_match,
+    bench_full_aut_no_match, bench_full_aut_overlapping_no_match,
+};
+
+#[bench]
+fn ac_one_byte(b: &mut Bencher) {
+    let aut = $aut(vec!["a"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_one_prefix_byte_no_match(b: &mut Bencher) {
+    let aut = $aut(vec!["zbc"]);
+    $bench(b, aut, &haystack_same('y'));
+}
+
+#[bench]
+fn ac_one_prefix_byte_every_match(b: &mut Bencher) {
+    // We lose the benefit of `memchr` because the first byte matches
+    // in every position in the haystack.
+    let aut = $aut(vec!["zbc"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_one_prefix_byte_random(b: &mut Bencher) {
+    let aut = $aut(vec!["zbc\x00"]);
+    $bench(b, aut, HAYSTACK_RANDOM);
+}
+
+#[bench]
+fn ac_two_bytes(b: &mut Bencher) {
+    let aut = $aut(vec!["a", "b"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_two_diff_prefix(b: &mut Bencher) {
+    let aut = $aut(vec!["abcdef", "bmnopq"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_two_one_prefix_byte_every_match(b: &mut Bencher) {
+    let aut = $aut(vec!["zbcdef", "zmnopq"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_two_one_prefix_byte_no_match(b: &mut Bencher) {
+    let aut = $aut(vec!["zbcdef", "zmnopq"]);
+    $bench(b, aut, &haystack_same('y'));
+}
+
+#[bench]
+fn ac_two_one_prefix_byte_random(b: &mut Bencher) {
+    let aut = $aut(vec!["zbcdef\x00", "zmnopq\x00"]);
+    $bench(b, aut, HAYSTACK_RANDOM);
+}
+
+#[bench]
+fn ac_ten_bytes(b: &mut Bencher) {
+    let aut = $aut(vec!["a", "b", "c", "d", "e",
+                        "f", "g", "h", "i", "j"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_ten_diff_prefix(b: &mut Bencher) {
+    let aut = $aut(vec!["abcdef", "bbcdef", "cbcdef", "dbcdef",
+                        "ebcdef", "fbcdef", "gbcdef", "hbcdef",
+                        "ibcdef", "jbcdef"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_ten_one_prefix_byte_every_match(b: &mut Bencher) {
+    let aut = $aut(vec!["zacdef", "zbcdef", "zccdef", "zdcdef",
+                        "zecdef", "zfcdef", "zgcdef", "zhcdef",
+                        "zicdef", "zjcdef"]);
+    $bench(b, aut, &haystack_same('z'));
+}
+
+#[bench]
+fn ac_ten_one_prefix_byte_no_match(b: &mut Bencher) {
+    let aut = $aut(vec!["zacdef", "zbcdef", "zccdef", "zdcdef",
+                        "zecdef", "zfcdef", "zgcdef", "zhcdef",
+                        "zicdef", "zjcdef"]);
+    $bench(b, aut, &haystack_same('y'));
+}
+
+#[bench]
+fn ac_ten_one_prefix_byte_random(b: &mut Bencher) {
+    let aut = $aut(vec!["zacdef\x00", "zbcdef\x00", "zccdef\x00",
+                        "zdcdef\x00", "zecdef\x00", "zfcdef\x00",
+                        "zgcdef\x00", "zhcdef\x00", "zicdef\x00",
+                        "zjcdef\x00"]);
+    $bench(b, aut, HAYSTACK_RANDOM);
+}
+        }
+    }
+}
+
+aut_benches!(dense, AcAutomaton::new, bench_aut_no_match);
+aut_benches!(dense_boxed, AcAutomaton::new, bench_box_aut_no_match);
+aut_benches!(sparse, AcAutomaton::<&str, Sparse>::with_transitions,
+             bench_aut_no_match);
+aut_benches!(full, AcAutomaton::new, bench_full_aut_no_match);
+aut_benches!(full_overlap, AcAutomaton::new, bench_full_aut_overlapping_no_match);
+
+// A naive multi-pattern search.
+// We use this to benchmark *throughput*, so it should never match anything.
+fn naive_find(needles: &[String], haystack: &str) -> bool {
+    for hi in 0..haystack.len() {
+        let rest = &haystack.as_bytes()[hi..];
+        for needle in needles {
+            let needle = needle.as_bytes();
+            if needle.len() > rest.len() {
+                continue;
+            }
+            if needle == &rest[..needle.len()] {
+                // should never happen in throughput benchmarks.
+                return true;
+            }
+        }
+    }
+    false
+}
+
+#[bench]
+fn naive_one_byte(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["a"], &haystack_same('z'));
+}
+
+#[bench]
+fn naive_one_prefix_byte_no_match(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbc"], &haystack_same('y'));
+}
+
+#[bench]
+fn naive_one_prefix_byte_every_match(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbc"], &haystack_same('z'));
+}
+
+#[bench]
+fn naive_one_prefix_byte_random(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbc\x00"], HAYSTACK_RANDOM);
+}
+
+#[bench]
+fn naive_two_bytes(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["a", "b"], &haystack_same('z'));
+}
+
+#[bench]
+fn naive_two_diff_prefix(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["abcdef", "bmnopq"], &haystack_same('z'));
+}
+
+#[bench]
+fn naive_two_one_prefix_byte_every_match(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbcdef", "zmnopq"], &haystack_same('z'));
+}
+
+#[bench]
+fn naive_two_one_prefix_byte_no_match(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbcdef", "zmnopq"], &haystack_same('y'));
+}
+
+#[bench]
+fn naive_two_one_prefix_byte_random(b: &mut Bencher) {
+    bench_naive_no_match(b, vec!["zbcdef\x00", "zmnopq\x00"], HAYSTACK_RANDOM);
+}
+
+#[bench]
+fn naive_ten_bytes(b: &mut Bencher) {
+    let needles = vec!["a", "b", "c", "d", "e",
+                       "f", "g", "h", "i", "j"];
+    bench_naive_no_match(b, needles, &haystack_same('z'));
+}
+
+#[bench]
+fn naive_ten_diff_prefix(b: &mut Bencher) {
+    let needles = vec!["abcdef", "bbcdef", "cbcdef", "dbcdef",
+                       "ebcdef", "fbcdef", "gbcdef", "hbcdef",
+                       "ibcdef", "jbcdef"];
+    bench_naive_no_match(b, needles, &haystack_same('z'));
+}
+
+#[bench]
+fn naive_ten_one_prefix_byte_every_match(b: &mut Bencher) {
+    let needles = vec!["zacdef", "zbcdef", "zccdef", "zdcdef",
+                       "zecdef", "zfcdef", "zgcdef", "zhcdef",
+                       "zicdef", "zjcdef"];
+    bench_naive_no_match(b, needles, &haystack_same('z'));
+}
+
+#[bench]
+fn naive_ten_one_prefix_byte_no_match(b: &mut Bencher) {
+    let needles = vec!["zacdef", "zbcdef", "zccdef", "zdcdef",
+                       "zecdef", "zfcdef", "zgcdef", "zhcdef",
+                       "zicdef", "zjcdef"];
+    bench_naive_no_match(b, needles, &haystack_same('y'));
+}
+
+#[bench]
+fn naive_ten_one_prefix_byte_random(b: &mut Bencher) {
+    let needles = vec!["zacdef\x00", "zbcdef\x00", "zccdef\x00",
+                       "zdcdef\x00", "zecdef\x00", "zfcdef\x00",
+                       "zgcdef\x00", "zhcdef\x00", "zicdef\x00",
+                       "zjcdef\x00"];
+    bench_naive_no_match(b, needles, HAYSTACK_RANDOM);
+}
+
+
+// The organization above is just awful. Let's start over...
+
+mod sherlock {
+    use aho_corasick::{Automaton, AcAutomaton};
+    use test::Bencher;
+    use super::HAYSTACK_SHERLOCK;
+
+    macro_rules! sherlock {
+        ($name:ident, $count:expr, $pats:expr) => {
+            #[bench]
+            fn $name(b: &mut Bencher) {
+                let haystack = HAYSTACK_SHERLOCK;
+                let aut = AcAutomaton::new($pats).into_full();
+                b.bytes = haystack.len() as u64;
+                b.iter(|| assert_eq!($count, aut.find(haystack).count()));
+            }
+        }
+    }
+
+    sherlock!(name_alt1, 158, vec!["Sherlock", "Street"]);
+
+    sherlock!(name_alt2, 558, vec!["Sherlock", "Holmes"]);
+
+    sherlock!(name_alt3, 740, vec![
+        "Sherlock", "Holmes", "Watson", "Irene", "Adler", "John", "Baker",
+    ]);
+
+    sherlock!(name_alt3_nocase, 1764, vec![
+        "ADL", "ADl", "AdL", "Adl", "BAK", "BAk", "BAK", "BaK", "Bak", "BaK",
+        "HOL", "HOl", "HoL", "Hol", "IRE", "IRe", "IrE", "Ire", "JOH", "JOh",
+        "JoH", "Joh", "SHE", "SHe", "ShE", "She", "WAT", "WAt", "WaT", "Wat",
+        "aDL", "aDl", "adL", "adl", "bAK", "bAk", "bAK", "baK", "bak", "baK",
+        "hOL", "hOl", "hoL", "hol", "iRE", "iRe", "irE", "ire", "jOH", "jOh",
+        "joH", "joh", "sHE", "sHe", "shE", "she", "wAT", "wAt", "waT", "wat",
+        "ſHE", "ſHe", "ſhE", "ſhe",
+    ]);
+
+    sherlock!(name_alt4, 582, vec!["Sher", "Hol"]);
+
+    sherlock!(name_alt4_nocase, 1307, vec![
+        "HOL", "HOl", "HoL", "Hol", "SHE", "SHe", "ShE", "She", "hOL", "hOl",
+        "hoL", "hol", "sHE", "sHe", "shE", "she", "ſHE", "ſHe", "ſhE", "ſhe",
+    ]);
+
+    sherlock!(name_alt5, 639, vec!["Sherlock", "Holmes", "Watson"]);
+
+    sherlock!(name_alt5_nocase, 1442, vec![
+        "HOL", "HOl", "HoL", "Hol", "SHE", "SHe", "ShE", "She", "WAT", "WAt",
+        "WaT", "Wat", "hOL", "hOl", "hoL", "hol", "sHE", "sHe", "shE", "she",
+        "wAT", "wAt", "waT", "wat", "ſHE", "ſHe", "ſhE", "ſhe",
+    ]);
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/benches/random.txt
@@ -0,0 +1,513 @@
+
+mnxnsynfvuugtbxsxbfxwreuspglnplefzwsp
+tacfqcwnmodnmgnyiuvqoco
+z
+
+qjuozfkexn
+zoaxzncje
+sldhqtmgxzyurfyzwazmmu
+bbeuv
+mzsrihycwcb
+xzfqozfmlnpmrzpxxxytqs
+xrg
+mcplby
+nmslhfgjowhzfxsvyddydnsyehdskbydbjksqtpet
+indvfw
+bvjvvw
+
+pddufodyqtyixbndtumndyz
+xjjhtuvmsxhuwqulqtjhqrdqrmtbcphvyuqllocrnkpfv
+zemshhz
+wss
+xewlrxfmgxnwgphcgefa
+mbgsgbzrtthxweimcqzcaaheurdmd
+osqefupespvh
+z
+tvvlakwzwjbrgjzfgubsmmonav
+pjdskxcfgapsm
+zqktqgkrcdrlskx
+zwwfebhguskho
+zlvvw
+czwm
+gojnpmboehlsazbexjjnuscqftrfufngygjdxcydib
+d
+afigycivicnknfxl
+ljuwuopctiftfwctxecwipjnljyef
+jonwbkodomzhqvlf
+jdkizhognqsdogunwedjsmsdzho
+zxvni
+oynfjf
+muvokjuqz
+azuwrwtuxzfopwrcex
+ixrjinlvxjmn
+blaegnmbhsgsbmebwazaeguugtkowexgnqtbfkldadddv
+tzabyoftyov
+ctbtqbzscxzviuvcigwuwusrdro
+ljynr
+gnnnyyxslrhsbj
+hhzlw
+hijalf
+rxlfqk
+mhaofforwznvmcgplinludpgkucpa
+gvvxsqqfmu
+xxqhoyosixjfhjuxpv
+faadjpvamjekreepizurntvwdynozfawsfawyms
+
+lcbutr
+aqyxvpozkjrecrkl
+lfmochahrr
+ptqyomjlwo
+vcmslulznx
+lmlsskcihrmxauztuarydlp
+beiqsrfnmvmlmybmwpektjbikvpggthpabqsgmjhnthvysuhwbigillugjsp
+dfsuegseffwcsnvsrqedytblbpzbfeyfsq
+kypvqctrkuds
+ylqeduokzgdqaxelhftxnxbidu
+bprzyayfopxdsmfhhfqowa
+ymiutdtlfaaxpbtaeslv
+ggago
+
+owpbicekdeykzfgcbgzobdvvrtetvcv
+xsrlgingstiez
+gyncqvq
+xasohmeiwyscpehctmzmsnjklg
+xsudghakxlw
+dzqlfptjogzpkvwuticcyugnyopypuqqc
+wlxshxbhdvuherumoppcc
+
+znyaptivzncvkpeyeipynqefjxjjcsgfqbnezeebtowdrbjaqjlbxwvyikrmxjwoxngqgvfpbniftnmszuxg
+umwpwwyvufy
+pallkjtnrmtauqxauewgygwkjjwebbkabhtxticxmxfujpxlrpzlrozfslkzfdsswlmmsbdgjwmjnummk
+dhsxylejzityahtqqzmohrpzjprrsraztpnuagtyzfjdekthvdogfidksrdppr
+ybc
+fyukknoqfnkllkwflwempjijxgo
+dltvlau
+rhvrvlwsribfctuzodfqkdczfzxnetqqzflnhiyl
+goxmcasmq
+wljbhwkpahdotqhhrbhqzijv
+lszewkgdmkezvgmbmllhpksdkoiwgkvqjmurshrptlctqsosuurndcuzjfwherotv
+dudxxihygxblhgchbgzyzffb
+eht
+fvwxvqoltdcsd
+rkuig
+e
+axhsacsmnicugul
+rubtdlhjqndxdzzwfnkuzy
+swxteuyxxsktkjgv
+hzwwodlqaq
+vxgecev
+qnwla
+vdxjuzpyoqhpmuunyffptopmeauhycs
+dkzo
+awrfzatzohslgvqlaezepmli
+qgxatixvpkkhvkumbwmwcagtgyfljdok
+amdnzstpvcqj
+xsrvwvhjirzfgkessve
+qezwbfltfbikbmoasvoflozsjhrljnszqiciuqmflrlqowwkoevuumh
+babskcvavmtvsxqsewirucwzajjcfcqwsydydqo
+ywfurpsl
+edacsjjkjjewkxfoh
+dcgkfpcjezurnuhiatrczcp
+xsatnimwbcciu
+grzmbrsvvcyigcbmcqfwiiknrohveubhyijxeyzfm
+kqyewccgcqrrrznwxmoztlyseagbpyho
+najju
+nis
+awgzdvfjkzlrsjcqfeacx
+oisuflfigrjaex
+desbdulyuwqxuxianyypybxwlql
+ekmqgspvqpftpwswayh
+egbyj
+fznzprhvnnwcxgcc
+wfdsueieosmugirxbymbpmfrspvrktjzguxm
+qkjrufshwnfwwpbhukdjlaqvljlgubmqmhnha
+hwqpudgnblhlxppbrmbznotteivuzguuwlhtkytky
+w
+yofkyzbpg
+cenolnfnllkvhikrpttcxgqxmufvorekjruyjxmr
+
+hyexmpjijgzumawp
+cdbevdilgopbzlo
+fivelagckslkugdxprjxkylizewcptwxfhomzuituujixchadmnjoktnqa
+csojvlinzmmkkfzqueamnuwkanzdzsavgohposbuoamoevehqrmcxdsuyelvvctoejzoertqormhaaxwofvjzekwt
+sbkghhnhutrvwtyjaxndzyjamrhx
+jjyqy
+majwbnrhveuhrsbbbjrwpwuplifeseylqh
+wyvutpxnkrnkuxxetjkkifpqb
+dyzucmbcvgnjeecm
+hz
+uhnuipthxrzkqluosvk
+lwqqzsdwiwvwaqfwlvubadlyizlo
+jbd
+oyzjeu
+kydjkbsqxnbfiuesc
+smeubjqrcxdvhsabzceyglqjzbfmoacmwvwjbhhxbr
+uabipgecujfdfxpmdzrscdyvefizabgspqjrrkmgjt
+xgvdgzryz
+lw
+uimob
+ifhn
+bqph
+ole
+g
+wt
+k
+yslzrkwkundxfdibwqvucemepqxlmlpyngabbeciuzhptpjdetyngrtxrdtzmvq
+ccwapidp
+
+bwvrgvmtshevrophy
+ni
+fdkplu
+mdykey
+i
+rhsrenoetdggpjb
+djmkplpeabsholx
+judxtub
+fooakqwvocvpcrvxqhvtmpvhkrecy
+uuxscjillynilbkrgt
+evtinrmilniguarqritpeipwochmdw
+sxaqzjybydyvnmmjtdcgkjnqfcklbfpkdfyewgcukqoiegyfp
+kg
+ovrwieqhy
+jcxqtkerzjwhs
+xeonglszbgypafhmqcaseimzjgebkvigbqwsayrnrprtuvhsxyitfqygohgorcdnufbcyvevvgzmjrgjqqquwkszplogx
+zdketqqv
+yebckucwayckeezfvtnavglpjh
+zorkfrwk
+pad
+xqaquxudybwtgixbfktinctfirjfdayh
+rieknj
+ebk
+qzbcfywfdmhsdruhopovemafijbscagllkmhmof
+
+asbsnbddlobwoqatfhkbhhsymzqxjuixwreheugvngmgcuqpkjhhfwpbarqaxrwgwnjbanljlds
+etevdvlc
+lqyjrnmenhn
+k
+tsf
+zczgeavcexh
+jlpuxywtsrvnvluruqhecjca
+ir
+rikrgkmhwaosodkxgcnrexfmdrszhnmutpvwztg
+bffjqovvkemctnsgeh
+weysbhzixiipfithjfsk
+usyzvaiyuhmksfluoirfbnsu
+o
+cgawpdakaszeafdtbdkqtlzkrpnoqomqvuaqcfmzgvfegovtfaonelpv
+izmrcjlk
+xmzemniyrzy
+knqexaafsdlimdamcrprlshq
+qkmqw
+dntgjwsibclvposdwjuklvtejjjdjibgpyynqpgprvvaetshhmvfkcpb
+otvazkrkklrxfotpopyjte
+fghkcnpi
+rulyaihsowvcgbzeiblhuhhfbmncqsuuqcxvseorn
+exirzfmojnxcoqom
+zsgpgtokun
+zvamxfocorganbtlafifwdqmqtsnktbwwtewborq
+
+cxlnaspjqvsitjyzyriqsuorjsrvzqenisprttudxntsbqrpjtdkxnwcwgjyxmgtqljcrmrbrmyvosojzlumcmjcgfjsdehec
+mvx
+mt
+mckr
+teulvroifk
+laaicc
+koufy
+bexmwsvyarnznebdfy
+ripvviosbqijsxnjilwddaqaqemzsdarnxmfooxghoypizwtbueo
+ljycycuqwfnzbambibqdixmkkvwtubepla
+cis
+kcg
+vmbbiuuoamenzepuagpfujevfstqtndjxjchdvycfrrrowochtjdmkklgnhf
+pmorrwguxkvdxpluatagaziin
+
+uwvzbmkmykjkmknzppklx
+pnzxuvsrjunqxercsnvayhykcazdeclomdsasgkpqpiufyfqsxhj
+yceizkddwojgweegcllaagpvrpo
+ek
+kuxxgbezqyxvfaxdwnqdgqsmneijunxzlwxkrs
+ldldbrxmvtjlqxifngmactzqcygkvuteffcmvphevilabgukatqakamjlridznodcvblvlogulmcixxfimh
+iuzjootuywjqklolzzhpeaynydjwtufjavbozxnzckuzdodkvkjfmhinelv
+swlfkcufscfcovmghqwcrtxjukwafoeogrkgubbqgwzm
+gjcylkwgzroubdssuqeykqjcmguso
+fzq
+srfvysoxtlylctp
+
+pbfeiuzwoyixews
+ocvvunfsjnrtklmuuzjojw
+xdjcnrpqhmpmpcwacpcdtmbsczvhllkqapzjuaf
+nfnuvjz
+fwnuiyqpn
+wshxxxpzzxp
+hibrxcfeqca
+
+wqhlllarl
+bukcbojv
+plrytapy
+xm
+vlgfqoyzdczqbbaxjwbjjevjhxgopuqvqcrj
+vpjqfbdnsdxlbuuiqocvrhap
+mgumjbvnnzgnrdru
+gcgzugazxdcamrhczfzhtmdjj
+uislwq
+vooai
+zjuqfmebuzsqngzekyajujkopvayxtdzvugwwucvlsbrnhitfotmhhmgddlzlvqrkcponictrfweuilfjiuoabkfdvpjiqjrrgi
+aptjfhmrnxaq
+hbs
+w
+mwmoxqvucwygunplzvxtxpk
+fgmqmtlorfzytjdzffsosfccnfwugrsrynuej
+rpmpenrhsxoefnblyumjqwvuyszyppnttuyvazjdug
+zdzxraxkroknkmqgvuoqeqdtvclsvvuwmdwzfugcpteohlogxubyoebvrzbqzklvehfcqadtdrkpubfhmokzwyosogepwragcpwxo
+ax
+dz
+de
+
+thvkdmnbdws
+
+ejmubw
+umvwkaubzurf
+wyxtxeluaoox
+wwbioobtgmkebxo
+miglgnafmdarzkeblyjctuayzyoeqnfnbtrcbymdzkzg
+loavxq
+kzhllgsenxlbgdbfzwbg
+yxflogzsohlcycbyzegeubfflouvtuatixhjvicjegltjiy
+jigqfjppafdiarc
+mcnmwtachgearonfcymvjbrnljjxmlzkudvzqsarnfysmxlfrtlvjxwvpdbhvwysnvcdozfcruhjwnucdzakkilmlfgjiolcatpfusm
+
+n
+pdjunfcz
+dc
+edxkkxabsbvmvifiinnoccki
+bc
+gwtwsvorwzfqpz
+exidmexstfflkhi
+s
+s
+c
+wtcjfywlayhpbqktcepoybowtkrmnumqsg
+ozclkgjdmdk
+jmegtbunyexurvfexhqptnqzie
+tkoenpagzwqfawlxvzaijsjqhmg
+swodqfjpdqcbkc
+ujokogocyaygdibgpglecis
+shlmdmgonvpuaxlhrymkxtiytmv
+brhk
+jmsyiuomiywxhegilycjprkyfgojdo
+
+wzdzrgpdiosdsvkcw
+odlnmsfnjrcsnflviwvawybpczdkzvdocpwrmavz
+p
+ubowamlskcqhdxuckrxa
+fawhntiwhmdwkddnahmtajqqazpdygttqivhdiodkcpcwv
+gmxujmmaufmbipaiulhurzkfdg
+eixjhmbaeoybiwk
+kumntgrgiofcmujlzbcopuobambsw
+mnjkqiyb
+iktwnsnv
+hfuzcl
+tqiyqvagbqgtowpjbedgjot
+dfemvamelxadkztogliizdtsddoboafawficudlefo
+raecmxiiibljryswntpfed
+mbwrtsebkeegw
+x
+epp
+he
+
+vnztrswhiusokqdkmsnpuswucvfhcthjbtam
+baxlwidsgbdpzvnlj
+tcbjjoadrzo
+aiidahyllzzsg
+
+igebuubweicbssgddpmqxunrawavuglmpxrtkqsvjjtscibqiejjfgfnovokodmqcqitlteiakooupvzkwucucrfdzjvjbqbkgutoybmpfvhbutigdxhfiqfplyciz
+cnrhbjdnjftwfwlwzrdkwhajgsizsi
+qfntnt
+okqyfnbresp
+asyg
+mjqdkdyggdxzwuzglays
+h
+ifaqcazoy
+fol
+vvsusbnugduxsceozmsarbp
+epjwtorx
+bwiuxxiyc
+cw
+bwogruhctwkfvbexjnwircykxyzjmats
+kygiochfwlpsvmxcgmtjrgvfdptd
+q
+qmpqe
+
+z
+jghffhqfoecmszunhxmzmzhlmbrvjabhrkihgjmvckhkfpaygjkg
+
+kfiyfgounmhlvhupswqdgws
+ezzdpyqucqoocsdcjtruqpokldfkmjhqzoynirybsifyaxnaxppthjoqy
+nwetlgzwrhkhtuubbkbepuhbllxspvagxrqokwnrhkbwdwtp
+hlazomrhqogoaxypqaszwfxxmutvbpuuvpdffuqskcbzlwyzcssnflkwiydoveyxjnzllzhyozbsa
+hwnitkwbxcyibbqsluuqywbk
+
+ozpfjsdrc
+yoepefuy
+lvmspzepnetra
+genbrcrmuqfvkaouvuymoxhcxotjjhk
+pcshyqgbmqdubsdajnyfqvxkqvywffzn
+ukhcbyzwslqeq
+otfrmcbnhbyffxqregqoufdxucjunwdhlqqeiiawbxlpqeyzzopfungrryqdykgizrhqodirvazm
+dhpfhzyq
+cloz
+eduupqifolfekve
+qiec
+ishnjukvomntmdthlkajxpiwk
+y
+axl
+tmyskjqkjsvumizlal
+wvvolwewsfxhhdieuagdcuhwsgqvswpbkdkpxskloalmr
+ryfmhe
+z
+mmbpgsyrfvzdatbjrjhuipwt
+llzwizmmuulgwocowwmugtaoewkhnqxparvtynlffffdfcocdbba
+
+pyczkzbmcgrdnxnmezsx
+gsqe
+mcocxcolcynhpecstsn
+opnpplkccobjuhtbhirpzfxuktmpsiwbvsgiaavvdge
+wpaldxzasnrbvtugjwytvtfttrh
+zxecurevkjiyxy
+wtnovebcmglkktic
+fdpwfgvlvovxrwh
+bmwgdullzy
+uzwhagxinwqifxjbcntqzqoxkmpqxhe
+jrfizsnwxwnnhb
+inapddlahrp
+
+ndtvkceobe
+buskgghihdjmjlwfc
+j
+rkvffxwtmzoeruhlsurwtnuh
+cbvkhfepkdishfpqvijzrpleuy
+jzdpxjhcgqnybssfegvrnpgyehdqpgjwudbwrjbavp
+xzzvgqdrdwajmdmj
+vfatwsxvwfdbdhnijdujoyotwvwjipuuetichcfmvgrsnjpqaaezjtkvc
+lbfoqgfshrtwgdqufwnfuitdrjydqctqixlzufkdbp
+zgau
+qefdpmtkecvtj
+kuphldkvnzdtpd
+dti
+fpd
+gfrliyegxsb
+i
+qsddsrmkyfgzrjeqnitmnypbcakh
+vfbvbrpuogzhzrbmklvhji
+nkz
+xlufbaoblbmeub
+alwuzxzmobwdukvwnkiwmuqhuxfhevogdnqtmxjptqznrk
+cngpoty
+
+ms
+qvenfg
+dmeaffm
+jycfgnanbmoamhmarkmjcagbp
+ysqmbhopgx
+jczbzgwedsp
+
+zxzwjrxcwdtleizjlvifjwgxiibezwxhtzywqdi
+mtgnlu
+xboxirdchurkfnklnpkapnqfxnhrxyseiujrznjm
+
+zm
+atddskbghcahlhql
+szshwzmmvu
+befdtpouamwhiisyybispkchpjhownatawjfbx
+
+ennkzbrlygd
+zbt
+upphzpdwzmlhhhbqvjsfmbnrar
+ddcs
+ipbxgzyudjyongtcyygncojdufnufqpdppgvq
+gc
+isu
+foa
+wf
+jdlvqxgfbowhohhyyngbcs
+zjuwjyucdwblatsnywaaoftlcamfbcnw
+lzrioesuhoeevczuwrnltmkahfwiu
+uicggfbddqltnjyxfltbnaekncnyxsit
+zkxsqkqrwrzrxgxbsgxatybfr
+
+ptvmfyxdcglbfipcguqthjygzqnpqssscukzawynidtchjrrxwuxifoe
+w
+ohu
+vg
+zagpowezvbniybgold
+lhqseqcxteiqtgnpanpvrmvvlltxh
+mtfnxn
+wyodtg
+
+rawpbgtpbaktqzmmpzxmrlwpvvmdsl
+widcfbirvswraukbmkhf
+vplrueuxomjkqrtjgyxjdkexttzyozawyq
+hrpbahllznvmjudzxpbbv
+tlavfrxygjfipkupwnbacltcfepeg
+icu
+otxcu
+aewazy
+hl
+
+fmrp
+qaacthwzohenzjr
+xbyebba
+rvkph
+mkhhmh
+swme
+zjmdoypaktglcyzobquunvthcdwegtbywpijxd
+jvkuhnxqc
+gibhqgjojsxt
+bodbktzomiqujtbstqiyquwvqgufphqstenxvddkvtdh
+bpusrxkfi
+zgp
+pmxvgamydyakituvvsucsuidrlznupcsinltmrahulhepxmhoqtfvpjkxzhrrinncuh
+jzgkjjhjqykzelaszvcwvvwbnzsxdeaerfnaravk
+ynanrqyrxo
+zsmuxofullob
+brklgrcqefdyoczy
+qkpls
+snhqumae
+iqdtzjadzzvnqvdvjfsaf
+nfqfdqiramueblxkaqxbbkxwywzgdbndjjiqk
+tc
+kp
+cpuckbjsxhtxmomfesgxdpz
+oseif
+ybhxbvyxrpkrexrhjzoaxxohrhsniewsrktjnaztn
+ggelspdzhzbchruhbjbjidgjwdlhdycetqaswh
+jkgivsngygkbqtlmoj
+dwpnanfvitxg
+ospxbwxp
+wgvmvrnjescemdoiralbkvemalifxnyhrbdgodml
+hjtsnkzknkplbzsiwmneefdkihnhsamjsrxggclyjqgpqltizi
+
+
+sykgbuypwwhweab
+nvdkkkskmtiwpoerkon
+sx
+sbyflwwiqylbskdlxesmylpaz
+dnwcjenaluwesyywfaezznwkdwpoesxpu
+kie
+dslccwfryol
+gfhomgfn
+zprjtfqvkotktzidmoyrivall
+bunvsqkysdelozemnjoeqfolruulpbipm
+ullyzfahpkhkja
+hwd
+kvyqtprpuulgsk
+zotbkcadnxmfvqmtlbxalhughceyfcibtzzj
+vvpjbgxygl
+hpic
+mhrqd
+dv
+thehuzdbaacoidjoljbysnqwrrxxplrdznmgiukkvjqbopb
+moszjt
+rmtbunktkywqirveeqfa
+kse
+wbfflnatgzobjrxghjgvcsyxoruenxhyomutbptswjajawqjpqafpdcstkiyjuilimecgejpqmyciolgcmdpcstzdozbmnza
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/ctags.rust
@@ -0,0 +1,11 @@
+--langdef=Rust
+--langmap=Rust:.rs
+--regex-Rust=/^[ \t]*(#\[[^\]]\][ \t]*)*(pub[ \t]+)?(extern[ \t]+)?("[^"]+"[ \t]+)?(unsafe[ \t]+)?fn[ \t]+([a-zA-Z0-9_]+)/\6/f,functions,function definitions/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?type[ \t]+([a-zA-Z0-9_]+)/\2/T,types,type definitions/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?enum[ \t]+([a-zA-Z0-9_]+)/\2/g,enum,enumeration names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?struct[ \t]+([a-zA-Z0-9_]+)/\2/s,structure names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?mod[ \t]+([a-zA-Z0-9_]+)/\2/m,modules,module names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?static[ \t]+([a-zA-Z0-9_]+)/\2/c,consts,static constants/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?trait[ \t]+([a-zA-Z0-9_]+)/\2/t,traits,traits/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?impl([ \t\n]+<.*>)?[ \t]+([a-zA-Z0-9_]+)/\3/i,impls,trait implementations/
+--regex-Rust=/^[ \t]*macro_rules![ \t]+([a-zA-Z0-9_]+)/\1/d,macros,macro definitions/
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/examples/dict-search.rs
@@ -0,0 +1,151 @@
+// This example demonstrates how to use the Aho-Corasick algorithm to rapidly
+// scan text for matches in a large dictionary of keywords. This example by
+// default reads your system's dictionary (~120,000 words).
+extern crate aho_corasick;
+extern crate csv;
+extern crate docopt;
+extern crate memmap;
+extern crate rustc_serialize;
+
+use std::error::Error;
+use std::fs::File;
+use std::io::{self, BufRead, Write};
+use std::process;
+
+use aho_corasick::{Automaton, AcAutomaton, Match};
+use docopt::Docopt;
+use memmap::{Mmap, Protection};
+
+static USAGE: &'static str = "
+Usage: dict-search [options] <input>
+       dict-search --help
+
+Options:
+    -d <path>, --dict <path>   Path to dictionary of keywords to search.
+                               [default: /usr/share/dict/words]
+    -m <len>, --min-len <len>  The minimum length for a keyword in UTF-8
+                               encoded bytes. [default: 5]
+    --overlapping              Report overlapping matches.
+    -c, --count                Show only the numebr of matches.
+    --memory-usage             Show memory usage of automaton.
+    --full                     Use fully expanded transition matrix.
+                               Warning: may use lots of memory.
+    -h, --help                 Show this usage message.
+";
+
+#[derive(Clone, Debug, RustcDecodable)]
+struct Args {
+    arg_input: String,
+    flag_dict: String,
+    flag_min_len: usize,
+    flag_overlapping: bool,
+    flag_memory_usage: bool,
+    flag_full: bool,
+    flag_count: bool,
+}
+
+fn main() {
+    let args: Args = Docopt::new(USAGE)
+                            .and_then(|d| d.decode())
+                            .unwrap_or_else(|e| e.exit());
+    match run(&args) {
+        Ok(()) => {}
+        Err(err) => {
+            writeln!(&mut io::stderr(), "{}", err).unwrap();
+            process::exit(1);
+        }
+    }
+}
+
+fn run(args: &Args) -> Result<(), Box<Error>> {
+    let aut = try!(build_automaton(&args.flag_dict, args.flag_min_len));
+    if args.flag_memory_usage {
+        let (bytes, states) = if args.flag_full {
+            let aut = aut.into_full();
+            (aut.heap_bytes(), aut.num_states())
+        } else {
+            (aut.heap_bytes(), aut.num_states())
+        };
+        println!("{} bytes, {} states", bytes, states);
+        return Ok(());
+    }
+
+    if args.flag_full {
+        let aut = aut.into_full();
+        if args.flag_overlapping {
+            if args.flag_count {
+                let mmap = Mmap::open_path(
+                    &args.arg_input, Protection::Read).unwrap();
+                let text = unsafe { mmap.as_slice() };
+                println!("{}", aut.find_overlapping(text).count());
+            } else {
+                let rdr = try!(File::open(&args.arg_input));
+                try!(write_matches(&aut, aut.stream_find_overlapping(rdr)));
+            }
+        } else {
+            if args.flag_count {
+                let mmap = Mmap::open_path(
+                    &args.arg_input, Protection::Read).unwrap();
+                let text = unsafe { mmap.as_slice() };
+                println!("{}", aut.find(text).count());
+            } else {
+                let rdr = try!(File::open(&args.arg_input));
+                try!(write_matches(&aut, aut.stream_find(rdr)));
+            }
+        }
+    } else {
+        if args.flag_overlapping {
+            if args.flag_count {
+                let mmap = Mmap::open_path(
+                    &args.arg_input, Protection::Read).unwrap();
+                let text = unsafe { mmap.as_slice() };
+                println!("{}", aut.find_overlapping(text).count());
+            } else {
+                let rdr = try!(File::open(&args.arg_input));
+                try!(write_matches(&aut, aut.stream_find_overlapping(rdr)));
+            }
+        } else {
+            if args.flag_count {
+                let mmap = Mmap::open_path(
+                    &args.arg_input, Protection::Read).unwrap();
+                let text = unsafe { mmap.as_slice() };
+                println!("{}", aut.find(text).count());
+            } else {
+                let rdr = try!(File::open(&args.arg_input));
+                try!(write_matches(&aut, aut.stream_find(rdr)));
+            }
+        }
+    }
+    Ok(())
+}
+
+fn write_matches<A, I>(aut: &A, it: I) -> Result<(), Box<Error>>
+        where A: Automaton<String>, I: Iterator<Item=io::Result<Match>> {
+    let mut wtr = csv::Writer::from_writer(io::stdout());
+    try!(wtr.write(["pattern", "start", "end"].iter()));
+    for m in it {
+        let m = try!(m);
+        try!(wtr.write([
+            aut.pattern(m.pati),
+            &m.start.to_string(),
+            &m.end.to_string(),
+        ].iter()));
+    }
+    try!(wtr.flush());
+    Ok(())
+}
+
+fn build_automaton(
+    dict_path: &str,
+    min_len: usize,
+) -> Result<AcAutomaton<String>, Box<Error>> {
+    let buf = io::BufReader::new(try!(File::open(dict_path)));
+    let mut lines = Vec::with_capacity(1 << 10);
+    for line in buf.lines() {
+        let line = try!(line);
+        if line.len() >= min_len {
+            lines.push(line);
+        }
+    }
+    Ok(AcAutomaton::with_transitions(lines))
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/session.vim
@@ -0,0 +1,1 @@
+au BufWritePost *.rs silent!make ctags > /dev/null 2>&1
copy from third_party/rust/aho-corasick/src/autiter.rs
copy to third_party/rust/aho-corasick-0.6.2/src/autiter.rs
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/src/full.rs
@@ -0,0 +1,136 @@
+use std::fmt;
+use std::mem;
+
+use super::{
+    FAIL_STATE,
+    StateIdx, AcAutomaton, Transitions, Match,
+    usize_bytes, vec_bytes,
+};
+use super::autiter::Automaton;
+
+/// A complete Aho-Corasick automaton.
+///
+/// This uses a single transition matrix that permits each input character
+/// to move to the next state with a single lookup in the matrix.
+///
+/// This is as fast as it gets, but it is guaranteed to use a lot of memory.
+/// Namely, it will use at least `4 * 256 * #states`, where the number of
+/// states is capped at length of all patterns concatenated.
+#[derive(Clone)]
+pub struct FullAcAutomaton<P> {
+    pats: Vec<P>,
+    trans: Vec<StateIdx>,  // row-major, where states are rows
+    out: Vec<Vec<usize>>, // indexed by StateIdx
+    start_bytes: Vec<u8>,
+}
+
+impl<P: AsRef<[u8]>> FullAcAutomaton<P> {
+    /// Build a new expanded Aho-Corasick automaton from an existing
+    /// Aho-Corasick automaton.
+    pub fn new<T: Transitions>(ac: AcAutomaton<P, T>) -> FullAcAutomaton<P> {
+        let mut fac = FullAcAutomaton {
+            pats: vec![],
+            trans: vec![FAIL_STATE; 256 * ac.states.len()],
+            out: vec![vec![]; ac.states.len()],
+            start_bytes: vec![],
+        };
+        fac.build_matrix(&ac);
+        fac.pats = ac.pats;
+        fac.start_bytes = ac.start_bytes;
+        fac
+    }
+
+    #[doc(hidden)]
+    pub fn memory_usage(&self) -> usize {
+        self.pats.iter()
+            .map(|p| vec_bytes() + p.as_ref().len())
+            .fold(0, |a, b| a + b)
+        + (4 * self.trans.len())
+        + self.out.iter()
+              .map(|v| vec_bytes() + (usize_bytes() * v.len()))
+              .fold(0, |a, b| a + b)
+        + self.start_bytes.len()
+    }
+
+    #[doc(hidden)]
+    pub fn heap_bytes(&self) -> usize {
+        self.pats.iter()
+            .map(|p| mem::size_of::<P>() + p.as_ref().len())
+            .fold(0, |a, b| a + b)
+        + (4 * self.trans.len())
+        + self.out.iter()
+              .map(|v| vec_bytes() + (usize_bytes() * v.len()))
+              .fold(0, |a, b| a + b)
+        + self.start_bytes.len()
+    }
+
+    fn set(&mut self, si: StateIdx, i: u8, goto: StateIdx) {
+        let ns = self.num_states();
+        self.trans[i as usize * ns + si as usize] = goto;
+    }
+
+    #[doc(hidden)]
+    #[inline]
+    pub fn num_states(&self) -> usize {
+        self.out.len()
+    }
+}
+
+impl<P: AsRef<[u8]>> Automaton<P> for FullAcAutomaton<P> {
+    #[inline]
+    fn next_state(&self, si: StateIdx, i: u8) -> StateIdx {
+        let at = i as usize * self.num_states() + si as usize;
+        unsafe { *self.trans.get_unchecked(at) }
+    }
+
+    #[inline]
+    fn get_match(&self, si: StateIdx, outi: usize, texti: usize) -> Match {
+        let pati = self.out[si as usize][outi];
+        let patlen = self.pats[pati].as_ref().len();
+        let start = texti + 1 - patlen;
+        Match {
+            pati: pati,
+            start: start,
+            end: start + patlen,
+        }
+    }
+
+    #[inline]
+    fn has_match(&self, si: StateIdx, outi: usize) -> bool {
+        unsafe { outi < self.out.get_unchecked(si as usize).len() }
+    }
+
+    #[inline]
+    fn start_bytes(&self) -> &[u8] {
+        &self.start_bytes
+    }
+
+    #[inline]
+    fn patterns(&self) -> &[P] {
+        &self.pats
+    }
+
+    #[inline]
+    fn pattern(&self, i: usize) -> &P {
+        &self.pats[i]
+    }
+}
+
+impl<P: AsRef<[u8]>> FullAcAutomaton<P> {
+    fn build_matrix<T: Transitions>(&mut self, ac: &AcAutomaton<P, T>) {
+        for (si, s) in ac.states.iter().enumerate().skip(1) {
+            for b in (0..256).map(|b| b as u8) {
+                self.set(si as StateIdx, b, ac.next_state(si as StateIdx, b));
+            }
+            for &pati in &s.out {
+                self.out[si].push(pati);
+            }
+        }
+    }
+}
+
+impl<P: AsRef<[u8]> + fmt::Debug> fmt::Debug for FullAcAutomaton<P> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "FullAcAutomaton({:?})", self.pats)
+    }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/src/lib.rs
@@ -0,0 +1,925 @@
+/*!
+An implementation of the
+[Aho-Corasick string search algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm).
+
+The Aho-Corasick algorithm is principally useful when you need to search many
+large texts for a fixed (possibly large) set of keywords. In particular, the
+Aho-Corasick algorithm preprocesses the set of keywords by constructing a
+finite state machine. The search phase is then a quick linear scan through the
+text. Each character in the search text causes a state transition in the
+automaton. Matches are reported when the automaton enters a match state.
+
+# Examples
+
+The main type exposed by this crate is `AcAutomaton`, which can be constructed
+from an iterator of pattern strings:
+
+```rust
+use aho_corasick::{Automaton, AcAutomaton};
+
+let aut = AcAutomaton::new(vec!["apple", "maple"]);
+
+// AcAutomaton also implements `FromIterator`:
+let aut: AcAutomaton<&str> = ["apple", "maple"].iter().cloned().collect();
+```
+
+Finding matches can be done with `find`:
+
+```rust
+use aho_corasick::{Automaton, AcAutomaton, Match};
+
+let aut = AcAutomaton::new(vec!["apple", "maple"]);
+let mut it = aut.find("I like maple apples.");
+assert_eq!(it.next(), Some(Match {
+    pati: 1,
+    start: 7,
+    end: 12,
+}));
+assert_eq!(it.next(), Some(Match {
+    pati: 0,
+    start: 13,
+    end: 18,
+}));
+assert_eq!(it.next(), None);
+```
+
+Use `find_overlapping` if you want to report all matches, even if they
+overlap with each other.
+
+```rust
+use aho_corasick::{Automaton, AcAutomaton, Match};
+
+let aut = AcAutomaton::new(vec!["abc", "a"]);
+let matches: Vec<_> = aut.find_overlapping("abc").collect();
+assert_eq!(matches, vec![
+    Match { pati: 1, start: 0, end: 1}, Match { pati: 0, start: 0, end: 3 },
+]);
+
+// Regular `find` will report only one match:
+let matches: Vec<_> = aut.find("abc").collect();
+assert_eq!(matches, vec![Match { pati: 1, start: 0, end: 1}]);
+```
+
+Finally, there are also methods for finding matches on *streams*. Namely, the
+search text does not have to live in memory. It's useful to run this on files
+that can't fit into memory:
+
+```no_run
+use std::fs::File;
+
+use aho_corasick::{Automaton, AcAutomaton};
+
+let aut = AcAutomaton::new(vec!["foo", "bar", "baz"]);
+let rdr = File::open("search.txt").unwrap();
+for m in aut.stream_find(rdr) {
+    let m = m.unwrap(); // could be an IO error
+    println!("Pattern '{}' matched at: ({}, {})",
+             aut.pattern(m.pati), m.start, m.end);
+}
+```
+
+There is also `stream_find_overlapping`, which is just like `find_overlapping`,
+but it operates on streams.
+
+Please see `dict-search.rs` in this crate's `examples` directory for a more
+complete example. It creates a large automaton from a dictionary and can do a
+streaming match over arbitrarily large data.
+
+# Memory usage
+
+A key aspect of an Aho-Corasick implementation is how the state transitions
+are represented. The easiest way to make the automaton fast is to store a
+sparse 256-slot map in each state. It maps an input byte to a state index.
+This makes the matching loop extremely fast, since it translates to a simple
+pointer read.
+
+The problem is that as the automaton accumulates more states, you end up paying
+a `256 * 4` (`4` is for the `u32` state index) byte penalty for every state
+regardless of how many transitions it has.
+
+To solve this, only states near the root of the automaton have this sparse
+map representation. States near the leaves of the automaton use a dense mapping
+that requires a linear scan.
+
+(The specific limit currently set is `3`, so that states with a depth less than
+or equal to `3` are less memory efficient. The result is that the memory usage
+of the automaton stops growing rapidly past ~60MB, even for automatons with
+thousands of patterns.)
+
+If you'd like to opt for the less-memory-efficient-but-faster version, then
+you can construct an `AcAutomaton` with a `Sparse` transition strategy:
+
+```rust
+use aho_corasick::{Automaton, AcAutomaton, Match, Sparse};
+
+let aut = AcAutomaton::<&str, Sparse>::with_transitions(vec!["abc", "a"]);
+let matches: Vec<_> = aut.find("abc").collect();
+assert_eq!(matches, vec![Match { pati: 1, start: 0, end: 1}]);
+```
+*/
+
+#![deny(missing_docs)]
+
+extern crate memchr;
+#[cfg(test)] extern crate quickcheck;
+#[cfg(test)] extern crate rand;
+
+use std::collections::VecDeque;
+use std::fmt;
+use std::iter::FromIterator;
+use std::mem;
+
+pub use self::autiter::{
+    Automaton, Match,
+    Matches, MatchesOverlapping, StreamMatches, StreamMatchesOverlapping,
+};
+pub use self::full::FullAcAutomaton;
+
+// We're specifying paths explicitly so that we can use
+// these modules simultaneously from `main.rs`.
+// Should probably make just make `main.rs` a separate crate.
+#[path = "autiter.rs"]
+mod autiter;
+#[path = "full.rs"]
+mod full;
+
+/// The integer type used for the state index.
+///
+/// Limiting this to 32 bit integers can have a big impact on memory usage
+/// when using the `Sparse` transition representation.
+pub type StateIdx = u32;
+
+// Constants for special state indexes.
+const FAIL_STATE: u32 = 0;
+const ROOT_STATE: u32 = 1;
+
+// Limit the depth at which we use a sparse alphabet map. Once the limit is
+// reached, a dense set is used (and lookup becomes O(n)).
+//
+// This does have a performance hit, but the (straight forward) alternative
+// is to have a `256 * 4` byte overhead for every state.
+// Given that Aho-Corasick is typically used for dictionary searching, this
+// can lead to dramatic memory bloat.
+//
+// This limit should only be increased at your peril. Namely, in the worst
+// case, `256^DENSE_DEPTH_THRESHOLD * 4` corresponds to the memory usage in
+// bytes. A value of `1` gives us a good balance. This is also a happy point
+// in the benchmarks. A value of `0` gives considerably worse times on certain
+// benchmarks (e.g., `ac_ten_one_prefix_byte_every_match`) than even a value
+// of `1`. A value of `2` is slightly better than `1` and it looks like gains
+// level off at that point with not much observable difference when set to
+// `3`.
+//
+// Why not make this user configurable? Well, it doesn't make much sense
+// because we pay for it with case analysis in the matching loop. Increasing it
+// doesn't have much impact on performance (outside of pathological cases?).
+//
+// N.B. Someone else seems to have discovered an alternative, but I haven't
+// grokked it yet: https://github.com/mischasan/aho-corasick
+const DENSE_DEPTH_THRESHOLD: u32 = 1;
+
+/// An Aho-Corasick finite automaton.
+///
+/// The type parameter `P` is the type of the pattern that was used to
+/// construct this AcAutomaton.
+#[derive(Clone)]
+pub struct AcAutomaton<P, T=Dense> {
+    pats: Vec<P>,
+    states: Vec<State<T>>,
+    start_bytes: Vec<u8>,
+}
+
+#[derive(Clone)]
+struct State<T> {
+    out: Vec<usize>,
+    fail: StateIdx,
+    goto: T,
+    depth: u32,
+}
+
+impl<P: AsRef<[u8]>> AcAutomaton<P> {
+    /// Create a new automaton from an iterator of patterns.
+    ///
+    /// The patterns must be convertible to bytes (`&[u8]`) via the `AsRef`
+    /// trait.
+    pub fn new<I>(pats: I) -> AcAutomaton<P, Dense>
+            where I: IntoIterator<Item=P> {
+        AcAutomaton::with_transitions(pats)
+    }
+}
+
+impl<P: AsRef<[u8]>, T: Transitions> AcAutomaton<P, T> {
+    /// Create a new automaton from an iterator of patterns.
+    ///
+    /// This constructor allows one to choose the transition representation.
+    ///
+    /// The patterns must be convertible to bytes (`&[u8]`) via the `AsRef`
+    /// trait.
+    pub fn with_transitions<I>(pats: I) -> AcAutomaton<P, T>
+            where I: IntoIterator<Item=P> {
+        AcAutomaton {
+            pats: vec![], // filled in later, avoid wrath of borrow checker
+            states: vec![State::new(0), State::new(0)], // empty and root
+            start_bytes: vec![], // also filled in later
+        }.build(pats.into_iter().collect())
+    }
+
+    /// Build out the entire automaton into a single matrix.
+    ///
+    /// This will make searching as fast as possible at the expense of using
+    /// at least `4 * 256 * #states` bytes of memory.
+    pub fn into_full(self) -> FullAcAutomaton<P> {
+        FullAcAutomaton::new(self)
+    }
+
+    #[doc(hidden)]
+    pub fn num_states(&self) -> usize {
+        self.states.len()
+    }
+
+    #[doc(hidden)]
+    pub fn heap_bytes(&self) -> usize {
+        self.pats.iter()
+            .map(|p| mem::size_of::<P>() + p.as_ref().len())
+            .fold(0, |a, b| a + b)
+        + self.states.iter()
+              .map(|s| mem::size_of::<State<T>>() + s.heap_bytes())
+              .fold(0, |a, b| a + b)
+        + self.start_bytes.len()
+    }
+}
+
+impl<P: AsRef<[u8]>, T: Transitions> Automaton<P> for AcAutomaton<P, T> {
+    #[inline]
+    fn next_state(&self, mut si: StateIdx, b: u8) -> StateIdx {
+        loop {
+            let maybe_si = self.states[si as usize].goto(b);
+            if maybe_si != FAIL_STATE {
+                si = maybe_si;
+                break;
+            } else {
+                si = self.states[si as usize].fail;
+            }
+        }
+        si
+    }
+
+    #[inline]
+    fn get_match(&self, si: StateIdx, outi: usize, texti: usize) -> Match {
+        let pati = self.states[si as usize].out[outi];
+        let patlen = self.pats[pati].as_ref().len();
+        let start = texti + 1 - patlen;
+        Match {
+            pati: pati,
+            start: start,
+            end: start + patlen,
+        }
+    }
+
+    #[inline]
+    fn has_match(&self, si: StateIdx, outi: usize) -> bool {
+        outi < self.states[si as usize].out.len()
+    }
+
+    #[inline]
+    fn start_bytes(&self) -> &[u8] {
+        &self.start_bytes
+    }
+
+    #[inline]
+    fn patterns(&self) -> &[P] {
+        &self.pats
+    }
+
+    #[inline]
+    fn pattern(&self, i: usize) -> &P {
+        &self.pats[i]
+    }
+}
+
+// Below contains code for *building* the automaton. It's a reasonably faithful
+// translation of the description/psuedo-code from:
+// http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
+
+impl<P: AsRef<[u8]>, T: Transitions> AcAutomaton<P, T> {
+    // This is the first phase and builds the initial keyword tree.
+    fn build(mut self, pats: Vec<P>) -> AcAutomaton<P, T> {
+        for (pati, pat) in pats.iter().enumerate() {
+            if pat.as_ref().is_empty() {
+                continue;
+            }
+            let mut previ = ROOT_STATE;
+            for &b in pat.as_ref() {
+                if self.states[previ as usize].goto(b) != FAIL_STATE {
+                    previ = self.states[previ as usize].goto(b);
+                } else {
+                    let depth = self.states[previ as usize].depth + 1;
+                    let nexti = self.add_state(State::new(depth));
+                    self.states[previ as usize].set_goto(b, nexti);
+                    previ = nexti;
+                }
+            }
+            self.states[previ as usize].out.push(pati);
+        }
+        for c in (0..256).into_iter().map(|c| c as u8) {
+            if self.states[ROOT_STATE as usize].goto(c) == FAIL_STATE {
+                self.states[ROOT_STATE as usize].set_goto(c, ROOT_STATE);
+            } else {
+                self.start_bytes.push(c);
+            }
+        }
+        // If any of the start bytes are non-ASCII, then remove them all,
+        // because we don't want to be calling memchr on non-ASCII bytes.
+        // (Well, we could, but it requires being more clever. Simply using
+        // the prefix byte isn't good enough.)
+        if self.start_bytes.iter().any(|&b| b > 0x7F) {
+            self.start_bytes.clear();
+        }
+        self.pats = pats;
+        self.fill()
+    }
+
+    // The second phase that fills in the back links.
+    fn fill(mut self) -> AcAutomaton<P, T> {
+        // Fill up the queue with all non-root transitions out of the root
+        // node. Then proceed by breadth first traversal.
+        let mut q = VecDeque::new();
+        for c in (0..256).into_iter().map(|c| c as u8) {
+            let si = self.states[ROOT_STATE as usize].goto(c);
+            if si != ROOT_STATE {
+                q.push_front(si);
+            }
+        }
+        while let Some(si) = q.pop_back() {
+            for c in (0..256).into_iter().map(|c| c as u8) {
+                let u = self.states[si as usize].goto(c);
+                if u != FAIL_STATE {
+                    q.push_front(u);
+                    let mut v = self.states[si as usize].fail;
+                    while self.states[v as usize].goto(c) == FAIL_STATE {
+                        v = self.states[v as usize].fail;
+                    }
+                    let ufail = self.states[v as usize].goto(c);
+                    self.states[u as usize].fail = ufail;
+                    let ufail_out = self.states[ufail as usize].out.clone();
+                    self.states[u as usize].out.extend(ufail_out);
+                }
+            }
+        }
+        self
+    }
+
+    fn add_state(&mut self, state: State<T>) -> StateIdx {
+        let i = self.states.len();
+        self.states.push(state);
+        i as StateIdx
+    }
+}
+
+impl<T: Transitions> State<T> {
+    fn new(depth: u32) -> State<T> {
+        State {
+            out: vec![],
+            fail: 1,
+            goto: Transitions::new(depth),
+            depth: depth,
+        }
+    }
+
+    fn goto(&self, b: u8) -> StateIdx {
+        self.goto.goto(b)
+    }
+
+    fn set_goto(&mut self, b: u8, si: StateIdx) {
+        self.goto.set_goto(b, si);
+    }
+
+    fn heap_bytes(&self) -> usize {
+        (self.out.len() * usize_bytes())
+        + self.goto.heap_bytes()
+    }
+}
+
+/// An abstraction over state transition strategies.
+///
+/// This is an attempt to let the caller choose the space/time trade offs
+/// used for state transitions.
+///
+/// (It's possible that this interface is merely good enough for just the two
+/// implementations in this crate.)
+pub trait Transitions {
+    /// Return a new state at the given depth.
+    fn new(depth: u32) -> Self;
+    /// Return the next state index given the next character.
+    fn goto(&self, alpha: u8) -> StateIdx;
+    /// Set the next state index for the character given.
+    fn set_goto(&mut self, alpha: u8, si: StateIdx);
+    /// The memory use in bytes (on the heap) of this set of transitions.
+    fn heap_bytes(&self) -> usize;
+}
+
+/// State transitions that can be stored either sparsely or densely.
+///
+/// This uses less space but at the expense of slower matching.
+#[derive(Clone, Debug)]
+pub struct Dense(DenseChoice);
+
+#[derive(Clone, Debug)]
+enum DenseChoice {
+    Sparse(Vec<StateIdx>), // indexed by alphabet
+    Dense(Vec<(u8, StateIdx)>),
+}
+
+impl Transitions for Dense {
+    fn new(depth: u32) -> Dense {
+        if depth <= DENSE_DEPTH_THRESHOLD {
+            Dense(DenseChoice::Sparse(vec![0; 256]))
+        } else {
+            Dense(DenseChoice::Dense(vec![]))
+        }
+    }
+
+    fn goto(&self, b1: u8) -> StateIdx {
+        match self.0 {
+            DenseChoice::Sparse(ref m) => m[b1 as usize],
+            DenseChoice::Dense(ref m) => {
+                for &(b2, si) in m {
+                    if b1 == b2 {
+                        return si;
+                    }
+                }
+                FAIL_STATE
+            }
+        }
+    }
+
+    fn set_goto(&mut self, b: u8, si: StateIdx) {
+        match self.0 {
+            DenseChoice::Sparse(ref mut m) => m[b as usize] = si,
+            DenseChoice::Dense(ref mut m) => m.push((b, si)),
+        }
+    }
+
+    fn heap_bytes(&self) -> usize {
+        match self.0 {
+            DenseChoice::Sparse(ref m) => m.len() * 4,
+            DenseChoice::Dense(ref m) => m.len() * (1 + 4),
+        }
+    }
+}
+
+/// State transitions that are always sparse.
+///
+/// This can use enormous amounts of memory when there are many patterns,
+/// but matching is very fast.
+#[derive(Clone, Debug)]
+pub struct Sparse(Vec<StateIdx>);
+
+impl Transitions for Sparse {
+    fn new(_: u32) -> Sparse {
+        Sparse(vec![0; 256])
+    }
+
+    #[inline]
+    fn goto(&self, b: u8) -> StateIdx {
+        self.0[b as usize]
+    }
+
+    fn set_goto(&mut self, b: u8, si: StateIdx) {
+        self.0[b as usize] = si;
+    }
+
+    fn heap_bytes(&self) -> usize {
+        self.0.len() * 4
+    }
+}
+
+impl<S: AsRef<[u8]>> FromIterator<S> for AcAutomaton<S> {
+    /// Create an automaton from an iterator of strings.
+    fn from_iter<T>(it: T) -> AcAutomaton<S> where T: IntoIterator<Item=S> {
+        AcAutomaton::new(it)
+    }
+}
+
+// Provide some question debug impls for viewing automatons.
+// The custom impls mostly exist for special showing of sparse maps.
+
+impl<P: AsRef<[u8]> + fmt::Debug, T: Transitions>
+        fmt::Debug for AcAutomaton<P, T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use std::iter::repeat;
+
+        try!(writeln!(f, "{}", repeat('-').take(79).collect::<String>()));
+        try!(writeln!(f, "Patterns: {:?}", self.pats));
+        for (i, state) in self.states.iter().enumerate().skip(1) {
+            try!(writeln!(f, "{:3}: {}", i, state.debug(i == 1)));
+        }
+        write!(f, "{}", repeat('-').take(79).collect::<String>())
+    }
+}
+
+impl<T: Transitions> State<T> {
+    fn debug(&self, root: bool) -> String {
+        format!("State {{ depth: {:?}, out: {:?}, fail: {:?}, goto: {{{}}} }}",
+                self.depth, self.out, self.fail, self.goto_string(root))
+    }
+
+    fn goto_string(&self, root: bool) -> String {
+        use std::char::from_u32;
+
+        let mut goto = vec![];
+        for b in (0..256).map(|b| b as u8) {
+            let si = self.goto(b);
+            if (!root && si == FAIL_STATE) || (root && si == ROOT_STATE) {
+                continue;
+            }
+            goto.push(format!("{} => {}", from_u32(b as u32).unwrap(), si));
+        }
+        goto.join(", ")
+    }
+}
+
+impl<T: Transitions> fmt::Debug for State<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.debug(false))
+    }
+}
+
+impl<T: Transitions> AcAutomaton<String, T> {
+    #[doc(hidden)]
+    pub fn dot(&self) -> String {
+        use std::fmt::Write;
+        let mut out = String::new();
+        macro_rules! w {
+            ($w:expr, $($tt:tt)*) => { {write!($w, $($tt)*)}.unwrap() }
+        }
+
+        w!(out, r#"
+digraph automaton {{
+    label=<<FONT POINT-SIZE="20">{}</FONT>>;
+    labelloc="l";
+    labeljust="l";
+    rankdir="LR";
+"#, self.pats.join(", "));
+        for (i, s) in self.states.iter().enumerate().skip(1) {
+            let i = i as u32;
+            if s.out.len() == 0 {
+                w!(out, "    {};\n", i);
+            } else {
+                w!(out, "    {} [peripheries=2];\n", i);
+            }
+            w!(out, "    {} -> {} [style=dashed];\n", i, s.fail);
+            for b in (0..256).map(|b| b as u8) {
+                let si = s.goto(b);
+                if si == FAIL_STATE || (i == ROOT_STATE && si == ROOT_STATE) {
+                    continue;
+                }
+                w!(out, "    {} -> {} [label={}];\n", i, si, b as char);
+            }
+        }
+        w!(out, "}}");
+        out
+    }
+}
+
+fn vec_bytes() -> usize {
+    usize_bytes() * 3
+}
+
+fn usize_bytes() -> usize {
+    let bits = usize::max_value().count_ones() as usize;
+    bits / 8
+}
+
+#[cfg(test)]
+mod tests {
+    use std::collections::HashSet;
+    use std::io;
+
+    use quickcheck::{Arbitrary, Gen, quickcheck};
+
+    use super::{Automaton, AcAutomaton, Match};
+
+    fn aut_find<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        AcAutomaton::new(xs.to_vec()).find(&haystack).collect()
+    }
+
+    fn aut_finds<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        let cur = io::Cursor::new(haystack.as_bytes());
+        AcAutomaton::new(xs.to_vec())
+            .stream_find(cur).map(|r| r.unwrap()).collect()
+    }
+
+    fn aut_findf<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        AcAutomaton::new(xs.to_vec()).into_full().find(haystack).collect()
+    }
+
+    fn aut_findfs<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        let cur = io::Cursor::new(haystack.as_bytes());
+        AcAutomaton::new(xs.to_vec())
+            .into_full()
+            .stream_find(cur).map(|r| r.unwrap()).collect()
+    }
+
+    fn aut_findo<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        AcAutomaton::new(xs.to_vec()).find_overlapping(haystack).collect()
+    }
+
+    fn aut_findos<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        let cur = io::Cursor::new(haystack.as_bytes());
+        AcAutomaton::new(xs.to_vec())
+            .stream_find_overlapping(cur).map(|r| r.unwrap()).collect()
+    }
+
+    fn aut_findfo<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        AcAutomaton::new(xs.to_vec())
+            .into_full().find_overlapping(haystack).collect()
+    }
+
+    fn aut_findfos<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + AsRef<[u8]> {
+        let cur = io::Cursor::new(haystack.as_bytes());
+        AcAutomaton::new(xs.to_vec())
+            .into_full()
+            .stream_find_overlapping(cur).map(|r| r.unwrap()).collect()
+    }
+
+    #[test]
+    fn one_pattern_one_match() {
+        let ns = vec!["a"];
+        let hay = "za";
+        let matches = vec![
+            Match { pati: 0, start: 1, end: 2 },
+        ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn one_pattern_many_match() {
+        let ns = vec!["a"];
+        let hay = "zazazzzza";
+        let matches = vec![
+            Match { pati: 0, start: 1, end: 2 },
+            Match { pati: 0, start: 3, end: 4 },
+            Match { pati: 0, start: 8, end: 9 },
+        ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn one_longer_pattern_one_match() {
+        let ns = vec!["abc"];
+        let hay = "zazabcz";
+        let matches = vec![ Match { pati: 0, start: 3, end: 6 } ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn one_longer_pattern_many_match() {
+        let ns = vec!["abc"];
+        let hay = "zazabczzzzazzzabc";
+        let matches = vec![
+            Match { pati: 0, start: 3, end: 6 },
+            Match { pati: 0, start: 14, end: 17 },
+        ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_pattern_one_match() {
+        let ns = vec!["a", "b"];
+        let hay = "zb";
+        let matches = vec![ Match { pati: 1, start: 1, end: 2 } ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_pattern_many_match() {
+        let ns = vec!["a", "b"];
+        let hay = "zbzazzzzb";
+        let matches = vec![
+            Match { pati: 1, start: 1, end: 2 },
+            Match { pati: 0, start: 3, end: 4 },
+            Match { pati: 1, start: 8, end: 9 },
+        ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_one_match() {
+        let ns = vec!["abc", "xyz"];
+        let hay = "zazxyzz";
+        let matches = vec![ Match { pati: 1, start: 3, end: 6 } ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_many_match() {
+        let ns = vec!["abc", "xyz"];
+        let hay = "zazxyzzzzzazzzabcxyz";
+        let matches = vec![
+            Match { pati: 1, start: 3, end: 6 },
+            Match { pati: 0, start: 14, end: 17 },
+            Match { pati: 1, start: 17, end: 20 },
+        ];
+        assert_eq!(&aut_find(&ns, hay), &matches);
+        assert_eq!(&aut_finds(&ns, hay), &matches);
+        assert_eq!(&aut_findf(&ns, hay), &matches);
+        assert_eq!(&aut_findfs(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_overlap_one_match() {
+        let ns = vec!["abc", "bc"];
+        let hay = "zazabcz";
+        let matches = vec![
+            Match { pati: 0, start: 3, end: 6 },
+            Match { pati: 1, start: 4, end: 6 },
+        ];
+        assert_eq!(&aut_findo(&ns, hay), &matches);
+        assert_eq!(&aut_findos(&ns, hay), &matches);
+        assert_eq!(&aut_findfo(&ns, hay), &matches);
+        assert_eq!(&aut_findfos(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_overlap_one_match_reverse() {
+        let ns = vec!["abc", "bc"];
+        let hay = "xbc";
+        let matches = vec![ Match { pati: 1, start: 1, end: 3 } ];
+        assert_eq!(&aut_findo(&ns, hay), &matches);
+        assert_eq!(&aut_findos(&ns, hay), &matches);
+        assert_eq!(&aut_findfo(&ns, hay), &matches);
+        assert_eq!(&aut_findfos(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_overlap_many_match() {
+        let ns = vec!["abc", "bc", "c"];
+        let hay = "zzzabczzzbczzzc";
+        let matches = vec![
+            Match { pati: 0, start: 3, end: 6 },
+            Match { pati: 1, start: 4, end: 6 },
+            Match { pati: 2, start: 5, end: 6 },
+            Match { pati: 1, start: 9, end: 11 },
+            Match { pati: 2, start: 10, end: 11 },
+            Match { pati: 2, start: 14, end: 15 },
+        ];
+        assert_eq!(&aut_findo(&ns, hay), &matches);
+        assert_eq!(&aut_findos(&ns, hay), &matches);
+        assert_eq!(&aut_findfo(&ns, hay), &matches);
+        assert_eq!(&aut_findfos(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn many_longer_pattern_overlap_many_match_reverse() {
+        let ns = vec!["abc", "bc", "c"];
+        let hay = "zzzczzzbczzzabc";
+        let matches = vec![
+            Match { pati: 2, start: 3, end: 4 },
+            Match { pati: 1, start: 7, end: 9 },
+            Match { pati: 2, start: 8, end: 9 },
+            Match { pati: 0, start: 12, end: 15 },
+            Match { pati: 1, start: 13, end: 15 },
+            Match { pati: 2, start: 14, end: 15 },
+        ];
+        assert_eq!(&aut_findo(&ns, hay), &matches);
+        assert_eq!(&aut_findos(&ns, hay), &matches);
+        assert_eq!(&aut_findfo(&ns, hay), &matches);
+        assert_eq!(&aut_findfos(&ns, hay), &matches);
+    }
+
+    #[test]
+    fn pattern_returns_original_type() {
+        let aut = AcAutomaton::new(vec!["apple", "maple"]);
+
+        // Explicitly given this type to assert that the thing returned
+        // from the function is our original type.
+        let pat: &str = aut.pattern(0);
+        assert_eq!(pat, "apple");
+
+        // Also check the return type of the `patterns` function.
+        let pats: &[&str] = aut.patterns();
+        assert_eq!(pats, &["apple", "maple"]);
+    }
+
+    // Quickcheck time.
+
+    // This generates very small ascii strings, which makes them more likely
+    // to interact in interesting ways with larger haystack strings.
+    #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
+    pub struct SmallAscii(String);
+
+    impl Arbitrary for SmallAscii {
+        fn arbitrary<G: Gen>(g: &mut G) -> SmallAscii {
+            use std::char::from_u32;
+            SmallAscii((0..2)
+                       .map(|_| from_u32(g.gen_range(97, 123)).unwrap())
+                       .collect())
+        }
+
+        fn shrink(&self) -> Box<Iterator<Item=SmallAscii>> {
+            Box::new(self.0.shrink().map(SmallAscii))
+        }
+    }
+
+    impl From<SmallAscii> for String {
+        fn from(s: SmallAscii) -> String { s.0 }
+    }
+
+    impl AsRef<[u8]> for SmallAscii {
+        fn as_ref(&self) -> &[u8] { self.0.as_ref() }
+    }
+
+    // This is the same arbitrary impl as `String`, except it has a bias toward
+    // ASCII characters.
+    #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
+    pub struct BiasAscii(String);
+
+    impl Arbitrary for BiasAscii {
+        fn arbitrary<G: Gen>(g: &mut G) -> BiasAscii {
+            use std::char::from_u32;
+            let size = { let s = g.size(); g.gen_range(0, s) };
+            let mut s = String::with_capacity(size);
+            for _ in 0..size {
+                if g.gen_weighted_bool(3) {
+                    s.push(char::arbitrary(g));
+                } else {
+                    for _ in 0..5 {
+                        s.push(from_u32(g.gen_range(97, 123)).unwrap());
+                    }
+                }
+            }
+            BiasAscii(s)
+        }
+
+        fn shrink(&self) -> Box<Iterator<Item=BiasAscii>> {
+            Box::new(self.0.shrink().map(BiasAscii))
+        }
+    }
+
+    fn naive_find<S>(xs: &[S], haystack: &str) -> Vec<Match>
+            where S: Clone + Into<String> {
+        let needles: Vec<String> =
+            xs.to_vec().into_iter().map(Into::into).collect();
+        let mut matches = vec![];
+        for hi in 0..haystack.len() {
+            for (pati, needle) in needles.iter().enumerate() {
+                let needle = needle.as_bytes();
+                if needle.len() == 0 || needle.len() > haystack.len() - hi {
+                    continue;
+                }
+                if needle == &haystack.as_bytes()[hi..hi+needle.len()] {
+                    matches.push(Match {
+                        pati: pati,
+                        start: hi,
+                        end: hi + needle.len(),
+                    });
+                }
+            }
+        }
+        matches
+    }
+
+    #[test]
+    fn qc_ac_equals_naive() {
+        fn prop(needles: Vec<SmallAscii>, haystack: BiasAscii) -> bool {
+            let aut_matches = aut_findo(&needles, &haystack.0);
+            let naive_matches = naive_find(&needles, &haystack.0);
+            // Ordering isn't always the same. I don't think we care, so do
+            // an unordered comparison.
+            let aset: HashSet<Match> = aut_matches.iter().cloned().collect();
+            let nset: HashSet<Match> = naive_matches.iter().cloned().collect();
+            aset == nset
+        }
+        quickcheck(prop as fn(Vec<SmallAscii>, BiasAscii) -> bool);
+    }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/aho-corasick-0.6.2/src/main.rs
@@ -0,0 +1,13 @@
+extern crate memchr;
+
+use std::env;
+
+use lib::AcAutomaton;
+
+#[allow(dead_code)]
+mod lib;
+
+fn main() {
+    let aut = AcAutomaton::new(env::args().skip(1));
+    println!("{}", aut.dot().trim());
+}
--- a/third_party/rust/aho-corasick/.cargo-checksum.json
+++ b/third_party/rust/aho-corasick/.cargo-checksum.json
@@ -1,1 +1,1 @@
-{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".travis.yml":"e17babe5ba0bdd19ec59a37b4a099fd4313bff58be63a2ff506075f9a97dc172","COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.toml":"367c53caf576e1c811c77b5234f4d00ee23f5b1052d5e11bdc0c3153a8d9ae82","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","Makefile":"a45a128685a2ae7d4fa39d310786674417ee113055ef290a11f88002285865fc","README.md":"9bc60d2cec222b50f87c85cf9475349bb228a36f89796c5d6481c52560ddde3a","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","benches/bench.rs":"acf4844efadeafc7bc396c2b16f2a184e140b6c17d1084dbaf454196de2090cd","benches/random.txt":"9386fb3efedc7ffbd09fb49088347f1056bc2d90a861009fa2f804cdb714efcb","ctags.rust":"3d128d3cc59f702e68953ba2fe6c3f46bc6991fc575308db060482d5da0c79f3","examples/dict-search.rs":"30eb44b1a0b599507db4c23a90f74199faabc64a8ae1d603ecdf3bba7428eb1e","session.vim":"95cb1d7caf0ff7fbe76ec911988d908ddd883381c925ba64b537695bc9f021c4","src/autiter.rs":"dc8817af24825c356842c814d771868fb07b6965addf4780e8b9dea9718344a0","src/full.rs":"b83a9c8ff3ef611c316b68650915df2d7f361a49b59dab103dc2c5476f2d8303","src/lib.rs":"68bf2ed02d58bebee6f7f7579038f1e4b60a2c4acc334263cb837bcbe15ffe94","src/main.rs":"fc867cb5f0b02d0f49ecab06b72c05a247cbcf3bf9228c235de8e787bda7bef5"},"package":"0638fd549427caa90c499814196d1b9e3725eb4d15d7339d6de073a680ed0ca2"}
\ No newline at end of file
+{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".travis.yml":"e17babe5ba0bdd19ec59a37b4a099fd4313bff58be63a2ff506075f9a97dc172","COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.toml":"b3fa06c2147a4749cd984ded69024ddcc8b7d578ab763b60227b3ba474c3ec70","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","Makefile":"a45a128685a2ae7d4fa39d310786674417ee113055ef290a11f88002285865fc","README.md":"9bc60d2cec222b50f87c85cf9475349bb228a36f89796c5d6481c52560ddde3a","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","benches/bench.rs":"acf4844efadeafc7bc396c2b16f2a184e140b6c17d1084dbaf454196de2090cd","benches/random.txt":"9386fb3efedc7ffbd09fb49088347f1056bc2d90a861009fa2f804cdb714efcb","ctags.rust":"3d128d3cc59f702e68953ba2fe6c3f46bc6991fc575308db060482d5da0c79f3","examples/dict-search.rs":"30eb44b1a0b599507db4c23a90f74199faabc64a8ae1d603ecdf3bba7428eb1e","session.vim":"95cb1d7caf0ff7fbe76ec911988d908ddd883381c925ba64b537695bc9f021c4","src/autiter.rs":"98c31a7fbe21cfacaa858f90409f0d86edd46dda1b7651f4e800d929a50afb7b","src/full.rs":"b83a9c8ff3ef611c316b68650915df2d7f361a49b59dab103dc2c5476f2d8303","src/lib.rs":"68bf2ed02d58bebee6f7f7579038f1e4b60a2c4acc334263cb837bcbe15ffe94","src/main.rs":"fc867cb5f0b02d0f49ecab06b72c05a247cbcf3bf9228c235de8e787bda7bef5"},"package":"500909c4f87a9e52355b26626d890833e9e1d53ac566db76c36faa984b889699"}
\ No newline at end of file
--- a/third_party/rust/aho-corasick/Cargo.toml
+++ b/third_party/rust/aho-corasick/Cargo.toml
@@ -1,11 +1,11 @@
 [package]
 name = "aho-corasick"
-version = "0.6.2"  #:version
+version = "0.6.3"  #:version
 authors = ["Andrew Gallant <jamslam@gmail.com>"]
 description = "Fast multiple substring searching with finite state machines."
 documentation = "http://burntsushi.net/rustdoc/aho_corasick/"
 homepage = "https://github.com/BurntSushi/aho-corasick"
 repository = "https://github.com/BurntSushi/aho-corasick"
 readme = "README.md"
 keywords = ["string", "search", "text", "aho", "corasick"]
 license = "Unlicense/MIT"
--- a/third_party/rust/aho-corasick/src/autiter.rs
+++ b/third_party/rust/aho-corasick/src/autiter.rs
@@ -234,16 +234,43 @@ fn skip_to_match<P, A: Automaton<P> + ?S
         si = aut.next_state(si, text[texti]);
         if aut.has_match(si, 0) {
             return Some((texti, si));
         }
         if si == ROOT_STATE {
             texti = skip(aut, text, texti + 1);
         } else {
             texti += 1;
+            if texti + 4 < text.len() {
+                si = aut.next_state(si, text[texti]);
+                if aut.has_match(si, 0) {
+                    return Some((texti, si));
+                }
+                texti += 1;
+                si = aut.next_state(si, text[texti]);
+                if aut.has_match(si, 0) {
+                    return Some((texti, si));
+                }
+                texti += 1;
+                si = aut.next_state(si, text[texti]);
+                if aut.has_match(si, 0) {
+                    return Some((texti, si));
+                }
+                texti += 1;
+                si = aut.next_state(si, text[texti]);
+                if aut.has_match(si, 0) {
+                    return Some((texti, si));
+                }
+                texti += 1;
+                si = aut.next_state(si, text[texti]);
+                if aut.has_match(si, 0) {
+                    return Some((texti, si));
+                }
+                texti += 1;
+            }
         }
     }
     None
 }
 
 #[inline]
 fn skip1<P, A: Automaton<P> + ?Sized>(
     aut: &A,
copy from third_party/rust/bindgen/.cargo-checksum.json
copy to third_party/rust/bindgen-0.29.0/.cargo-checksum.json
new file mode 100644
rename from third_party/rust/bindgen/.github/ISSUE_TEMPLATE.md
rename to third_party/rust/bindgen-0.29.0/.github/ISSUE_TEMPLATE.md
rename from third_party/rust/bindgen/.travis.yml
rename to third_party/rust/bindgen-0.29.0/.travis.yml
rename from third_party/rust/bindgen/CONTRIBUTING.md
rename to third_party/rust/bindgen-0.29.0/CONTRIBUTING.md
copy from third_party/rust/bindgen/Cargo.toml
copy to third_party/rust/bindgen-0.29.0/Cargo.toml
rename from third_party/rust/bindgen/LICENSE
rename to third_party/rust/bindgen-0.29.0/LICENSE
rename from third_party/rust/bindgen/README.md
rename to third_party/rust/bindgen-0.29.0/README.md
rename from third_party/rust/bindgen/appveyor.yml
rename to third_party/rust/bindgen-0.29.0/appveyor.yml
rename from third_party/rust/bindgen/book/book.toml
rename to third_party/rust/bindgen-0.29.0/book/book.toml
rename from third_party/rust/bindgen/book/src/SUMMARY.md
rename to third_party/rust/bindgen-0.29.0/book/src/SUMMARY.md
rename from third_party/rust/bindgen/book/src/blacklisting.md
rename to third_party/rust/bindgen-0.29.0/book/src/blacklisting.md
rename from third_party/rust/bindgen/book/src/chapter_1.md
rename to third_party/rust/bindgen-0.29.0/book/src/chapter_1.md
rename from third_party/rust/bindgen/book/src/command-line-usage.md
rename to third_party/rust/bindgen-0.29.0/book/src/command-line-usage.md
rename from third_party/rust/bindgen/book/src/cpp.md
rename to third_party/rust/bindgen-0.29.0/book/src/cpp.md
rename from third_party/rust/bindgen/book/src/customizing-generated-bindings.md
rename to third_party/rust/bindgen-0.29.0/book/src/customizing-generated-bindings.md
rename from third_party/rust/bindgen/book/src/introduction.md
rename to third_party/rust/bindgen-0.29.0/book/src/introduction.md
rename from third_party/rust/bindgen/book/src/library-usage.md
rename to third_party/rust/bindgen-0.29.0/book/src/library-usage.md
rename from third_party/rust/bindgen/book/src/nocopy.md
rename to third_party/rust/bindgen-0.29.0/book/src/nocopy.md
rename from third_party/rust/bindgen/book/src/opaque.md
rename to third_party/rust/bindgen-0.29.0/book/src/opaque.md
rename from third_party/rust/bindgen/book/src/replacing-types.md
rename to third_party/rust/bindgen-0.29.0/book/src/replacing-types.md
rename from third_party/rust/bindgen/book/src/requirements.md
rename to third_party/rust/bindgen-0.29.0/book/src/requirements.md
rename from third_party/rust/bindgen/book/src/tutorial-0.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-0.md
rename from third_party/rust/bindgen/book/src/tutorial-1.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-1.md
rename from third_party/rust/bindgen/book/src/tutorial-2.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-2.md
rename from third_party/rust/bindgen/book/src/tutorial-3.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-3.md
rename from third_party/rust/bindgen/book/src/tutorial-4.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-4.md
rename from third_party/rust/bindgen/book/src/tutorial-5.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-5.md
rename from third_party/rust/bindgen/book/src/tutorial-6.md
rename to third_party/rust/bindgen-0.29.0/book/src/tutorial-6.md
rename from third_party/rust/bindgen/book/src/using-unions.md
rename to third_party/rust/bindgen-0.29.0/book/src/using-unions.md
rename from third_party/rust/bindgen/book/src/whitelisting.md
rename to third_party/rust/bindgen-0.29.0/book/src/whitelisting.md
copy from third_party/rust/bindgen/build.rs
copy to third_party/rust/bindgen-0.29.0/build.rs
rename from third_party/rust/bindgen/ci/assert-docs.sh
rename to third_party/rust/bindgen-0.29.0/ci/assert-docs.sh
rename from third_party/rust/bindgen/ci/assert-no-diff.bat
rename to third_party/rust/bindgen-0.29.0/ci/assert-no-diff.bat
rename from third_party/rust/bindgen/ci/assert-no-diff.sh
rename to third_party/rust/bindgen-0.29.0/ci/assert-no-diff.sh
rename from third_party/rust/bindgen/ci/assert-rustfmt.sh
rename to third_party/rust/bindgen-0.29.0/ci/assert-rustfmt.sh
rename from third_party/rust/bindgen/ci/before_install.sh
rename to third_party/rust/bindgen-0.29.0/ci/before_install.sh
rename from third_party/rust/bindgen/ci/deploy-book.sh
rename to third_party/rust/bindgen-0.29.0/ci/deploy-book.sh
rename from third_party/rust/bindgen/ci/no-includes.sh
rename to third_party/rust/bindgen-0.29.0/ci/no-includes.sh
rename from third_party/rust/bindgen/ci/test-book.sh
rename to third_party/rust/bindgen-0.29.0/ci/test-book.sh
rename from third_party/rust/bindgen/ci/test.bat
rename to third_party/rust/bindgen-0.29.0/ci/test.bat
rename from third_party/rust/bindgen/ci/test.sh
rename to third_party/rust/bindgen-0.29.0/ci/test.sh
rename from third_party/rust/bindgen/example-graphviz-ir.png
rename to third_party/rust/bindgen-0.29.0/example-graphviz-ir.png
rename from third_party/rust/bindgen/rustfmt.toml
rename to third_party/rust/bindgen-0.29.0/rustfmt.toml
copy from third_party/rust/bindgen/src/callbacks.rs
copy to third_party/rust/bindgen-0.29.0/src/callbacks.rs
copy from third_party/rust/bindgen/src/clang.rs
copy to third_party/rust/bindgen-0.29.0/src/clang.rs
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bindgen-0.29.0/src/codegen/error.rs
@@ -0,0 +1,41 @@
+use std::error;
+use std::fmt;
+
+/// Errors that can occur during code generation.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Error {
+    /// Tried to generate an opaque blob for a type that did not have a layout.
+    NoLayoutForOpaqueBlob,
+
+    /// Tried to instantiate an opaque template definition, or a template
+    /// definition that is too difficult for us to understand (like a partial
+    /// template specialization).
+    InstantiationOfOpaqueType,
+}
+
+impl fmt::Display for Error {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", error::Error::description(self))
+    }
+}
+
+impl error::Error for Error {
+    fn cause(&self) -> Option<&error::Error> {
+        None
+    }
+
+    fn description(&self) -> &'static str {
+        match *self {
+            Error::NoLayoutForOpaqueBlob => {
+                "Tried to generate an opaque blob, but had no layout"
+            }
+            Error::InstantiationOfOpaqueType => {
+                "Instantiation of opaque template type or partial template \
+                 specialization"
+            }
+        }
+    }
+}
+
+/// A `Result` of `T` or an error of `bindgen::codegen::error::Error`.
+pub type Result<T> = ::std::result::Result<T, Error>;
copy from third_party/rust/bindgen/src/codegen/helpers.rs
copy to third_party/rust/bindgen-0.29.0/src/codegen/helpers.rs
copy from third_party/rust/bindgen/src/codegen/mod.rs
copy to third_party/rust/bindgen-0.29.0/src/codegen/mod.rs
copy from third_party/rust/bindgen/src/codegen/struct_layout.rs
copy to third_party/rust/bindgen-0.29.0/src/codegen/struct_layout.rs
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bindgen-0.29.0/src/extra_assertions.rs
@@ -0,0 +1,30 @@
+//! Macros for defining extra assertions that should only be checked in testing
+//! and/or CI when the `testing_only_extra_assertions` feature is enabled.
+
+#[macro_export]
+macro_rules! extra_assert {
+    ( $cond:expr ) => {
+        if cfg!(feature = "testing_only_extra_assertions") {
+            assert!($cond);
+        }
+    };
+    ( $cond:expr , $( $arg:tt )+ ) => {
+        if cfg!(feature = "testing_only_extra_assertions") {
+            assert!($cond, $( $arg )* )
+        }
+    };
+}
+
+#[macro_export]
+macro_rules! extra_assert_eq {
+    ( $lhs:expr , $rhs:expr ) => {
+        if cfg!(feature = "testing_only_extra_assertions") {
+            assert_eq!($lhs, $rhs);
+        }
+    };
+    ( $lhs:expr , $rhs:expr , $( $arg:tt )+ ) => {
+        if cfg!(feature = "testing_only_extra_assertions") {
+            assert!($lhs, $rhs, $( $arg )* );
+        }
+    };
+}
copy from third_party/rust/bindgen/src/ir/analysis/derive_debug.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/analysis/derive_debug.rs
copy from third_party/rust/bindgen/src/ir/analysis/has_vtable.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/analysis/has_vtable.rs
copy from third_party/rust/bindgen/src/ir/analysis/mod.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/analysis/mod.rs
copy from third_party/rust/bindgen/src/ir/analysis/template_params.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/analysis/template_params.rs
copy from third_party/rust/bindgen/src/ir/annotations.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/annotations.rs
copy from third_party/rust/bindgen/src/ir/comment.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/comment.rs
copy from third_party/rust/bindgen/src/ir/comp.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/comp.rs
copy from third_party/rust/bindgen/src/ir/context.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/context.rs
copy from third_party/rust/bindgen/src/ir/derive.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/derive.rs
copy from third_party/rust/bindgen/src/ir/dot.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/dot.rs
copy from third_party/rust/bindgen/src/ir/enum_ty.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/enum_ty.rs
copy from third_party/rust/bindgen/src/ir/function.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/function.rs
copy from third_party/rust/bindgen/src/ir/int.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/int.rs
copy from third_party/rust/bindgen/src/ir/item.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/item.rs
copy from third_party/rust/bindgen/src/ir/item_kind.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/item_kind.rs
copy from third_party/rust/bindgen/src/ir/layout.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/layout.rs
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bindgen-0.29.0/src/ir/mod.rs
@@ -0,0 +1,24 @@
+//! The ir module defines bindgen's intermediate representation.
+//!
+//! Parsing C/C++ generates the IR, while code generation outputs Rust code from
+//! the IR.
+
+pub mod annotations;
+pub mod analysis;
+pub mod comp;
+pub mod comment;
+pub mod context;
+pub mod derive;
+pub mod dot;
+pub mod enum_ty;
+pub mod function;
+pub mod int;
+pub mod item;
+pub mod item_kind;
+pub mod layout;
+pub mod module;
+pub mod template;
+pub mod traversal;
+pub mod ty;
+pub mod var;
+pub mod objc;
copy from third_party/rust/bindgen/src/ir/module.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/module.rs
copy from third_party/rust/bindgen/src/ir/objc.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/objc.rs
copy from third_party/rust/bindgen/src/ir/template.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/template.rs
copy from third_party/rust/bindgen/src/ir/traversal.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/traversal.rs
copy from third_party/rust/bindgen/src/ir/ty.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/ty.rs
copy from third_party/rust/bindgen/src/ir/var.rs
copy to third_party/rust/bindgen-0.29.0/src/ir/var.rs
copy from third_party/rust/bindgen/src/lib.rs
copy to third_party/rust/bindgen-0.29.0/src/lib.rs
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bindgen-0.29.0/src/log_stubs.rs
@@ -0,0 +1,30 @@
+macro_rules! log {
+    (target: $target:expr, $lvl:expr, $($arg:tt)+) => {
+        let _ = $target;
+        let _ = log!($lvl, $($arg)+);
+    };
+    ($lvl:expr, $($arg:tt)+) => {{
+        let _ = $lvl;
+        let _ = format_args!($($arg)+);
+    }};
+}
+macro_rules! error {
+    (target: $target:expr, $($arg:tt)*) => { log!($target, $($arg)*); };
+    ($($arg:tt)*) => { log!("", $($arg)*); };
+}
+macro_rules! warn {
+    (target: $target:expr, $($arg:tt)*) => { log!($target, $($arg)*); };
+    ($($arg:tt)*) => { log!("", $($arg)*); };
+}
+macro_rules! info {
+    (target: $target:expr, $($arg:tt)*) => { log!($target, $($arg)*); };
+    ($($arg:tt)*) => { log!("", $($arg)*); };
+}
+macro_rules! debug {
+    (target: $target:expr, $($arg:tt)*) => { log!($target, $($arg)*); };
+    ($($arg:tt)*) => { log!("", $($arg)*); };
+}
+macro_rules! trace {
+    (target: $target:expr, $($arg:tt)*) => { log!($target, $($arg)*); };
+    ($($arg:tt)*) => { log!("", $($arg)*); };
+}
copy from third_party/rust/bindgen/src/main.rs
copy to third_party/rust/bindgen-0.29.0/src/main.rs
copy from third_party/rust/bindgen/src/options.rs
copy to third_party/rust/bindgen-0.29.0/src/options.rs
copy from third_party/rust/bindgen/src/parse.rs
copy to third_party/rust/bindgen-0.29.0/src/parse.rs
copy from third_party/rust/bindgen/src/regex_set.rs
copy to third_party/rust/bindgen-0.29.0/src/regex_set.rs
rename from third_party/rust/bindgen/src/uses.rs
rename to third_party/rust/bindgen-0.29.0/src/uses.rs
--- a/third_party/rust/bindgen/.cargo-checksum.json
+++ b/third_party/rust/bindgen/.cargo-checksum.json
@@ -1,1 +1,1 @@
-{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".github/ISSUE_TEMPLATE.md":"952c59a2801c6e204801585704469db1af23cade4019281ba8d6027c0a03c553",".travis.yml":"fe5a4cd14f10c5d5c39ad6e22500cd0b68cfa1a5beb625d01577610100a9dfeb","CONTRIBUTING.md":"bef289580b237a158170335a998ab5d77f4e620424ce3636b0cf9fde181b1aaa","Cargo.toml":"bbae95802d3e7044687bef057a47777b409ed898cf370a40de52cb6821263a27","LICENSE":"1d2e4bdb9d94ab020e9550136cae9ec73fc699c3c96a9d98078c542e9b93d294","README.md":"8c4662f1c596d52d134cf5fa628655dc81b4259fb8e5349062eb36626d009efe","appveyor.yml":"6648e724bf3f5981ea0aa299417b3980a6dd1134cabd2ed34072759b70063d1b","book/book.toml":"dbf931141036d1d0eb02b326f7f5d7867dd9a8f0fc49b66b8fd97e9873c08e44","book/src/SUMMARY.md":"471d2494f28b4c9c40e004ec7190479345ee2d29247b712726d8820234172dd6","book/src/blacklisting.md":"a68424cc3643e06e83c5ea4efd5eb501dc64229ff9f4286b9a210a2376c20a9b","book/src/chapter_1.md":"cac4f4a3609ec22eb519b0e07d1d1bdc15ac3d741f29f9b97280f700b96ded66","book/src/command-line-usage.md":"9e3ae32cb5d893f1a93fc539149950bacdf43a18c694169fa45dfe8080617403","book/src/cpp.md":"c7926268d311239caa4475602634d609553d4a8a0e0902fcbd1762d1d405f657","book/src/customizing-generated-bindings.md":"0363ca69719c5e24d624ac3adfef71445896d3ed2b7bb3689c7905e47bdd9cdd","book/src/introduction.md":"c1b11894292f326fa492534c5a9a58b0238d05caccb3e145b70b226069ee674e","book/src/library-usage.md":"62565cf21a6b07a9de9a3f525427e75aa0f05350a1f546ed428c8a6c40cf850c","book/src/nocopy.md":"615f9b2ae474adf32ddf49e2f29f019f857db0fbb3232ed30df3960edd9f3406","book/src/opaque.md":"d6a5d6b7dfad4e8e1f7a1307f57a0a4b723032970bbae0e1290e1ab81e08b21a","book/src/replacing-types.md":"f406f7135299cd4e67a017237a6a9acbe936aa48f37b7f52be2769c90537b73f","book/src/requirements.md":"f6715430e9830593501a9b8c09105058189832df1a0b4d9852400fa408069f0e","book/src/tutorial-0.md":"0343285deac4161a230450ab8e9aa825d2a42f243cb10372b2d0edef8b956c29","book/src/tutorial-1.md":"c341e519ff6f2abb55e63139e106e3161c5169b2154bf694cd9c34c7feb3a89e","book/src/tutorial-2.md":"f6c9cf4ea8e38628c15dedc0ee7f60055a2aa841e95f972465d2932bb71878ad","book/src/tutorial-3.md":"580d25d9754d540af2b7d3eb99a828555479c37a61566e21eec9a00f98f829c3","book/src/tutorial-4.md":"23e82ec5d2de96670e148e5417b61810c203603adea54aefc94a2b16d1d0ede2","book/src/tutorial-5.md":"60e7f50e9be3c7de0e096f6615815d74608afa184c649b4301d71a60c808c646","book/src/tutorial-6.md":"806238e5156b10881489bda6c5480e9bd0aa88208ef2d74dd26c18cd3d024dff","book/src/using-unions.md":"bcd0f5f97a199ac84df4cd4a43dc6ca17d5eff6493b90247f3425b9c2c68c1ff","book/src/whitelisting.md":"b6913e3fc43d28f504331afe4ccc3607caad9aa88d4cb627a86bdc1e72ea0175","build.rs":"5e44ce645edcd487efae5e127efe289d1216c7f55dce65d26248f61f5dde4a3a","ci/assert-docs.sh":"f60a78a7d6f6444389df39a070a08851c78f1b525afff3b2548e852a3ebf6dc6","ci/assert-no-diff.bat":"904a49de6ee9faf8b83cc21d958d2fb37d4b278e9fe48484320aa55f9089f032","ci/assert-no-diff.sh":"af208c40d412e2bce82ae9b4a4e52cae4ae0b4beef9f93eb825bf5d5346a70b2","ci/assert-rustfmt.sh":"b9c810e86ea6d71bce1d6bf8d896839cfe2c198338e042ebc744b75e83af1126","ci/before_install.sh":"51409851cf4e1dee27735461e77247c599e023259c3a57e82fa044f284ca8e87","ci/deploy-book.sh":"67a3df2cc39ee585a2d5353d303e452d9586bec7ea33de6b5aa4a0ecb43c136f","ci/no-includes.sh":"148b146eab4aeb11ad229e03b3d5ebd8cb56a31674df438264d1ebff2d17f52d","ci/test-book.sh":"dfbcfb1381f723b4b29634bb4033ab72ace412d0711631976897c64d57122600","ci/test.bat":"88368377f3907eb34b3693a5ddf8ff69168b17bcc6528807aaf52dc693cb3c47","ci/test.sh":"01059bf60d40053534f9606986d3f4e06e90262848c4b3114df62b7b90f84793","example-graphviz-ir.png":"e1122ab33b4c80e8c9c0cf8abea404c1192f9b2eef97f5766e86103cc95d5e01","rustfmt.toml":"c4f3b593bdd634590df22aaf7b0872244d5c2169aacd0274a05e4aca4708a8d3","src/callbacks.rs":"e0d36d30adac8a4eaab64f0a9df0ab29026fcd5f5c5588bdeb2ad762e4c024ad","src/clang.rs":"79ffe98ef68e889731e1babf63157b75587e81faf96d97ce7e8be48377bfe77e","src/codegen/error.rs":"2613af1d833377fd4a70719f4a09951d9d45dc9227827b9a2a938a1bcaaea2dd","src/codegen/helpers.rs":"501838ff8da3c51c90eefdbee0228e321782e755201147b0d8ed78c2f59b29d1","src/codegen/mod.rs":"1f7ae949d425e3724f62de144b483f0f4257c02071ca00623798170b5dbf9745","src/codegen/struct_layout.rs":"130cf8a2e1cb8348a13e05904af2300333b51bf72cd63f3ec696b768a4a6b52d","src/extra_assertions.rs":"449549c4a7a50c3f0b06332452b2fb6c9b23f31ca8e5e1656fe6c7f21e8ef7fa","src/ir/analysis/derive_debug.rs":"18c9c16f233c2dabed9b5d85a07c2e6c884b318336996d217e1a6b14b023a54a","src/ir/analysis/has_vtable.rs":"6f49e17b1b40f8683d21a89725aec48f9fe4417361a55cf302e568eecbe2d35d","src/ir/analysis/mod.rs":"5758a40600e19278bb7dc4238f7e490971fa5aa83ade9497924fd722da9bf315","src/ir/analysis/template_params.rs":"b74243aab14f50d8a765d9e30f48e8c58ba340e4b4bfb7db9c87f1123842e3aa","src/ir/annotations.rs":"887ad7beaa43eddd60337b67951a109c2e7f51cb8e757b35cad45f744b7ba919","src/ir/comment.rs":"564a9fbf4bd7bf03ecf93104109ef66ed501abeaf4e4784b1d14083df6cade3b","src/ir/comp.rs":"5146cede0fdc3747c4ab12b4665d39b8ab482c0308577582013d878dee595b5f","src/ir/context.rs":"f8cfdaf8f53811eebfe52b9966b70a3780f12ca2baebce08e393178622d108ac","src/ir/derive.rs":"e4e86d86edc957eb38d310852e49e1a160bf4fdd13a70a664373c8a343705b62","src/ir/dot.rs":"79af769bff3b7c8b5c58ee73286429bcc8b9963526e42257cc61ca9a2a5eb4e9","src/ir/enum_ty.rs":"64ec618b9914aac83351624ffb9219e089dafa2959b4e896160f7f30df9e29c4","src/ir/function.rs":"bf374db02a5086b0dfd91fbc17d0b283cb057857dd13d5d9fde1dbd33aad47ef","src/ir/int.rs":"b7bc19668ca6c7c084a3f8d1e07d5a980ee49c0c9a8882c3e72baab4ea7fa403","src/ir/item.rs":"136bd52e1179349c24202d2745330d29d1ad9d1afe891cf149475ba1d6cf8d07","src/ir/item_kind.rs":"64b8b5bede6dfe950ceb15da1aabf888707eeb5883df9213f05ee47797bfb84f","src/ir/layout.rs":"58df6436c7170ab7b2bde2afe4760f6dfc35a6ef3edb50290fbd3a8ea0248453","src/ir/mod.rs":"2eae90f207fad2e45957ec9287064992a419e3fc916aba84faff2ea25cbeb5ee","src/ir/module.rs":"5f33c7bd01891ece61d946c6052b96a8127e3811616f3e698fc220716234ca6c","src/ir/objc.rs":"353be93027d74ad102ac3b0ef8754dd1258a400dcf7d361fa224fdf1ab973c56","src/ir/template.rs":"5650b957ceff3caef4d75ad5c1e5014a07ae3ccb6edd1712babbd543e192f20a","src/ir/traversal.rs":"1b9abed7bcc82f85c18d36dd475a5615984ff00588468ab81f232902f93ec423","src/ir/ty.rs":"8550883f2f65b4e113fc7beefcd5f6e1d701a9e58cc92bae4356d6eeadd69727","src/ir/var.rs":"0b56e6107bf96063c6a9bcb47fcbd1950147d63d242185498e95242174f083d6","src/lib.rs":"ca18b1e54f8be6c32030c15444f52556758e0b5c0e5048ad9389aa1cbffabd95","src/log_stubs.rs":"6dfdd908b7c6453da416cf232893768f9480e551ca4add0858ef88bf71ee6ceb","src/main.rs":"995b35df006ba97d882aa6de91ba42a616314a98687a2ea4f8bbff0669a54f54","src/options.rs":"a0ecd0eb1069df3af236fb5e9a9c9611ed1949321243aaee9e4e257c72ffd8c2","src/parse.rs":"6d88e1dcdb4e99f4f65629ce205c14e18097773bc938973f8e3849ba3bda4f79","src/regex_set.rs":"6c46877238c338e1fc6a35a8983db21f0711c979e44310975f60ad73a50fdbbc","src/uses.rs":"16841e43290424f814a4cb119b782f6987e854429f483ae8001525e3f3620958"},"package":"0c338079dafc81bef7d581f494b906603d12359c4306979eae6ca081925a4984"}
\ No newline at end of file
+{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855","Cargo.toml":"8f81f53eb8f6cfc4d8c0e5eaed51b0a7d85a60c9b710fd9df62d25a1db189f92","build.rs":"deff14b2204700f9fd40ba426148d648626461a4ce372c49b8c0f92e09646c80","src/callbacks.rs":"c5c4e5bc8c49cb191d1b100339772fdc7dd1dbf5025a9de1ecaafb70f86cb48f","src/clang.rs":"541a016580c98c2e2af36c3c11b80127c26090795a380480c925c5f411f8100d","src/codegen/derive_debug.rs":"77e16be27a6999726978bf33dc54227cf3b074101ebd55e90f655340cf05ba8b","src/codegen/error.rs":"2613af1d833377fd4a70719f4a09951d9d45dc9227827b9a2a938a1bcaaea2dd","src/codegen/helpers.rs":"19c5b4a86df9410d7e6cb27c2a8797dd205e4c96eab203798b70cd30dd35e572","src/codegen/mod.rs":"4488f141de2abb5d1fa36df7818daeeebba4f5237a9e43101fc9d805e0a80436","src/codegen/struct_layout.rs":"b92fef035e5deaf3fe9f3c2d4ea61a758b873f6f193fe68693955d9d14a396cb","src/extra_assertions.rs":"449549c4a7a50c3f0b06332452b2fb6c9b23f31ca8e5e1656fe6c7f21e8ef7fa","src/features.rs":"b686a3e4ce5712473d0a7c0f817bef29b9337265ec6df1278087a708e1180108","src/ir/analysis/derive_copy.rs":"e17960cd79d764a36fd7cea8bad944a8994fc9cb3a20080955f28509b9e66c9e","src/ir/analysis/derive_debug.rs":"ffb933c46cc26c0ed7c7ccf16a0a19dddb3b0108ca913bd41b785c3afbd4ee0b","src/ir/analysis/derive_default.rs":"740b281eddf9f9f0606963fef7485e9219e7ebedeb7966c83c63f723d1deb62f","src/ir/analysis/derive_hash.rs":"6c046a54d495e3d6ec666f23c6209212321f72f1ed843523e8a9aa0cd6421c9e","src/ir/analysis/derive_partial_eq.rs":"fdd0d78861f146ce9f62c49979009cfad82ec9b96c8c79415513158fc9bf7ad0","src/ir/analysis/has_destructor.rs":"42fdc74e363bc32dbe51558cb5b330bad0e40d79b4cd3c6ff36b6f418a68c0ad","src/ir/analysis/has_float.rs":"02b7ccf9a99b1d96e3a0ec712de45461ab714184129f2634de46b33fb1758ccd","src/ir/analysis/has_type_param_in_array.rs":"39f10af6a6b7af17ee505777dbd10989942272b44efba2a1e320d8b4bbabe0f0","src/ir/analysis/has_vtable.rs":"33def5eb43270fff87455a0e8d262817876e2cf8c676b8cb6c8ec37e84dd99d1","src/ir/analysis/mod.rs":"10a7817a9c990dd8125e4ca9ed1fe02b9a0e27c4dd0320e909bb55f727ed8191","src/ir/analysis/template_params.rs":"e1a3709c3c07b7be21e3912339820f86992b56af44d923919023b7e015f41755","src/ir/annotations.rs":"ef106afcbe6084c18bd13a37ee3c1cdc9596bfb055db8c773d81f8f15fec3208","src/ir/comment.rs":"36f2a1d3970fdbf3d72c1f094043902747cde395215bdf7e9103926d9df011fd","src/ir/comp.rs":"062ea5ec95717e32b26be39bd4664179ff790831042205d795af1a4654922c8d","src/ir/context.rs":"68dbaa11ae5041965e08de24955852982f10c764decb7ba1de6c82073e95916c","src/ir/derive.rs":"608e9bacd6d6d29f5b4357fe2f7cdda62e79c77271b022e5275d22abc22788d3","src/ir/dot.rs":"173e57c3017182279bff98ea5edfd8e6e007a25e70da27139578a637a0a747bc","src/ir/enum_ty.rs":"d633d4d36a64cafd4e1e4ba82872058d5a0aada007e47353e4905ce1fe7d16ec","src/ir/function.rs":"409b779469c8092100991bc442b0b5bcfe9d5510edb71db12a38181df7519938","src/ir/int.rs":"1f61a472288afe489d9320bc8b13920333ece57891ae8570b4c4f25ab50688e6","src/ir/item.rs":"bff6369353b37a209236d750d274c0282a8669c9f7bee2b0eeea706e17537d1f","src/ir/item_kind.rs":"13048962657436a757ff9483d96f2ce351ec5f827ecab4921ed643f6f115c497","src/ir/layout.rs":"39c415271629fc5a43373bcd5ba8bfa26ebb2544aa9e28598b0141214111bb67","src/ir/mod.rs":"2eae90f207fad2e45957ec9287064992a419e3fc916aba84faff2ea25cbeb5ee","src/ir/module.rs":"5d46d631cec17ef1d1882da60080898760181c2ddf991473afdd464bf8c7d867","src/ir/objc.rs":"52454e14371535ff4da4025cf45fee3d3beadbe36759a6ebf0d1d7048a00714f","src/ir/template.rs":"cc96a205dec677962376cec0bdbf53820d633378fa92d9faeb34953d2943a928","src/ir/traversal.rs":"521fdd685ba8c684199cbc8131561ed39aed852dd0d1e76e17d8d2a3d204428b","src/ir/ty.rs":"263e7c5794b56dd0499db8b102169f70881b5ff1d15ded1fe49fc24c29d9ab34","src/ir/var.rs":"c60354e164e357480e72b20d7f5c2f7188da8af38ad1db0a3f79806ef60388ab","src/lib.rs":"6efe2ba78af7a2c790e73e03ca6876c24a56636b3b2fb74926a866675dc7ee71","src/log_stubs.rs":"6dfdd908b7c6453da416cf232893768f9480e551ca4add0858ef88bf71ee6ceb","src/main.rs":"6ebd647814b339bbd318f5d55f54ef98091138c2c7208436a88204be56a5a49b","src/options.rs":"cced11c8ba947953098df62beb7980dd72d9aa9c6fd3c8dba5aac745bdcd2315","src/parse.rs":"812171946f0ec8a83f26f9041151ad9dcdff11961e5154e4dae4be248f86b296","src/regex_set.rs":"e4cc668c724a80f7dd7d028f4a22146680513b40cf3a5255551c41079d302309"},"package":"33024f55a754d920637461adf87fb485702a69bdf7ac1d307b7e18da93bae505"}
\ No newline at end of file
--- a/third_party/rust/bindgen/Cargo.toml
+++ b/third_party/rust/bindgen/Cargo.toml
@@ -7,89 +7,92 @@
 #
 # 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]
 name = "bindgen"
-version = "0.29.0"
+version = "0.30.0"
 authors = ["Jyun-Yan You <jyyou.tw@gmail.com>", "Emilio Cobos Álvarez <emilio@crisal.io>", "Nick Fitzgerald <fitzgen@gmail.com>", "The Servo project developers"]
 build = "build.rs"
-exclude = ["bindgen-integration", "ci", "tests/**", "*.orig"]
+include = ["Cargo.toml", "build.rs", "src/*.rs", "src/**/*.rs"]
 description = "Automatically generates Rust FFI bindings to C and C++ libraries."
 documentation = "https://docs.rs/bindgen"
 readme = "README.md"
 keywords = ["bindings", "ffi", "code-generation"]
 categories = ["external-ffi-bindings", "development-tools::ffi"]
 license = "BSD-3-Clause"
 repository = "https://github.com/rust-lang-nursery/rust-bindgen"
 
 [lib]
 path = "src/lib.rs"
 
 [[bin]]
 name = "bindgen"
 path = "src/main.rs"
 doc = false
-[dependencies.clap]
-version = "2"
-
-[dependencies.peeking_take_while]
-version = "0.1.2"
-
-[dependencies.cfg-if]
-version = "0.1.0"
-
-[dependencies.regex]
-version = "0.2"
-
-[dependencies.clang-sys]
-version = "0.19.0"
-features = ["runtime", "clang_3_9"]
-
-[dependencies.lazy_static]
-version = "0.2.1"
-
-[dependencies.syntex_syntax]
-version = "0.58"
-
-[dependencies.aster]
-version = "0.41"
-features = ["with-syntex"]
-
 [dependencies.log]
 version = "0.3"
 optional = true
 
 [dependencies.quasi]
 version = "0.32"
 features = ["with-syntex"]
 
-[dependencies.cexpr]
-version = "0.2"
+[dependencies.aster]
+version = "0.41"
+features = ["with-syntex"]
+
+[dependencies.which]
+version = "1.0.2"
+
+[dependencies.clang-sys]
+version = "0.19.0"
+features = ["runtime", "clang_3_9"]
 
 [dependencies.env_logger]
 version = "0.4"
 optional = true
-[dev-dependencies.diff]
+
+[dependencies.syntex_syntax]
+version = "0.58"
+
+[dependencies.lazy_static]
+version = "0.2.1"
+
+[dependencies.cfg-if]
+version = "0.1.0"
+
+[dependencies.peeking_take_while]
+version = "0.1.2"
+
+[dependencies.clap]
+version = "2"
+
+[dependencies.regex]
+version = "0.2"
+
+[dependencies.cexpr]
+version = "0.2"
+[dev-dependencies.shlex]
 version = "0.1"
 
 [dev-dependencies.clap]
 version = "2"
 
-[dev-dependencies.shlex]
+[dev-dependencies.diff]
 version = "0.1"
 [build-dependencies.quasi_codegen]
 version = "0.32"
 
 [features]
 testing_only_extra_assertions = []
+logging = ["env_logger", "log"]
+static = []
+testing_only_libclang_3_9 = []
 testing_only_libclang_4 = []
-testing_only_docs = []
-logging = ["env_logger", "log"]
 default = ["logging"]
+testing_only_docs = []
 testing_only_libclang_3_8 = []
-testing_only_libclang_3_9 = []
-static = []
 [badges.travis-ci]
 repository = "rust-lang-nursery/rust-bindgen"
--- a/third_party/rust/bindgen/build.rs
+++ b/third_party/rust/bindgen/build.rs
@@ -11,57 +11,67 @@ mod codegen {
         let dst = Path::new(&out_dir).join("codegen.rs");
 
         quasi_codegen::expand(&src, &dst).unwrap();
         println!("cargo:rerun-if-changed=src/codegen/mod.rs");
         println!("cargo:rerun-if-changed=src/codegen/error.rs");
         println!("cargo:rerun-if-changed=src/codegen/helpers.rs");
         println!("cargo:rerun-if-changed=src/codegen/struct_layout.rs");
 
-        let mut dst =
-            File::create(Path::new(&out_dir).join("host-target.txt")).unwrap();
-        dst.write_all(env::var("TARGET").unwrap().as_bytes()).unwrap();
+        let mut dst = File::create(Path::new(&out_dir).join("host-target.txt"))
+            .unwrap();
+        dst.write_all(env::var("TARGET").unwrap().as_bytes())
+            .unwrap();
     }
 }
 
 mod testgen {
     use std::char;
     use std::env;
     use std::ffi::OsStr;
     use std::fs::{self, File};
     use std::io::Write;
     use std::path::{Path, PathBuf};
 
     pub fn main() {
         let out_dir = PathBuf::from(env::var("OUT_DIR").unwrap());
-        let mut dst = File::create(Path::new(&out_dir).join("tests.rs")).unwrap();
+        let mut dst = File::create(Path::new(&out_dir).join("tests.rs"))
+            .unwrap();
 
-        let manifest_dir = PathBuf::from(env::var("CARGO_MANIFEST_DIR").unwrap());
+        let manifest_dir =
+            PathBuf::from(env::var("CARGO_MANIFEST_DIR").unwrap());
         let headers_dir = manifest_dir.join("tests").join("headers");
 
         let headers = match fs::read_dir(headers_dir) {
             Ok(dir) => dir,
             // We may not have headers directory after packaging.
             Err(..) => return,
         };
 
         let entries =
             headers.map(|result| result.expect("Couldn't read header file"));
 
         println!("cargo:rerun-if-changed=tests/headers");
 
         for entry in entries {
             match entry.path().extension().and_then(OsStr::to_str) {
                 Some("h") | Some("hpp") => {
-                    let func = entry.file_name().to_str().unwrap()
+                    let func = entry
+                        .file_name()
+                        .to_str()
+                        .unwrap()
                         .replace(|c| !char::is_alphanumeric(c), "_")
                         .replace("__", "_")
                         .to_lowercase();
-                    writeln!(dst, "test_header!(header_{}, {:?});",
-                             func, entry.path()).unwrap();
+                    writeln!(
+                        dst,
+                        "test_header!(header_{}, {:?});",
+                        func,
+                        entry.path()
+                    ).unwrap();
                 }
                 _ => {}
             }
         }
 
         dst.flush().unwrap();
     }
 }
--- a/third_party/rust/bindgen/src/callbacks.rs
+++ b/third_party/rust/bindgen/src/callbacks.rs
@@ -3,29 +3,29 @@
 pub use ir::enum_ty::{EnumVariantCustomBehavior, EnumVariantValue};
 pub use ir::int::IntKind;
 use std::fmt;
 use std::panic::UnwindSafe;
 
 /// A trait to allow configuring different kinds of types in different
 /// situations.
 pub trait ParseCallbacks: fmt::Debug + UnwindSafe {
-
     /// This function will be run on every macro that is identified
     fn parsed_macro(&self, _name: &str) {}
 
     /// The integer kind an integer macro should have, given a name and the
     /// value of that macro, or `None` if you want the default to be chosen.
     fn int_macro(&self, _name: &str, _value: i64) -> Option<IntKind> {
         None
     }
 
     /// This function should return whether, given the a given enum variant
     /// name, and value, returns whether this enum variant will forcibly be a
     /// constant.
-    fn enum_variant_behavior(&self,
-                             _enum_name: Option<&str>,
-                             _variant_name: &str,
-                             _variant_value: EnumVariantValue)
-                             -> Option<EnumVariantCustomBehavior> {
+    fn enum_variant_behavior(
+        &self,
+        _enum_name: Option<&str>,
+        _variant_name: &str,
+        _variant_value: EnumVariantValue,
+    ) -> Option<EnumVariantCustomBehavior> {
         None
     }
 }
--- a/third_party/rust/bindgen/src/clang.rs
+++ b/third_party/rust/bindgen/src/clang.rs
@@ -19,22 +19,24 @@ use std::os::raw::{c_char, c_int, c_uint
 /// We call the AST node pointed to by the cursor the cursor's "referent".
 #[derive(Copy, Clone)]
 pub struct Cursor {
     x: CXCursor,
 }
 
 impl fmt::Debug for Cursor {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt,
-               "Cursor({} kind: {}, loc: {}, usr: {:?})",
-               self.spelling(),
-               kind_to_str(self.kind()),
-               self.location(),
-               self.usr())
+        write!(
+            fmt,
+            "Cursor({} kind: {}, loc: {}, usr: {:?})",
+            self.spelling(),
+            kind_to_str(self.kind()),
+            self.location(),
+            self.usr()
+        )
     }
 }
 
 impl Cursor {
     /// Get the Unified Symbol Resolution for this cursor's referent, if
     /// available.
     ///
     /// The USR can be used to compare entities across translation units.
@@ -208,21 +210,22 @@ impl Cursor {
         }
     }
 
     /// Is the referent a top level construct?
     pub fn is_toplevel(&self) -> bool {
         let mut semantic_parent = self.fallible_semantic_parent();
 
         while semantic_parent.is_some() &&
-              (semantic_parent.unwrap().kind() == CXCursor_Namespace ||
-               semantic_parent.unwrap().kind() == CXCursor_NamespaceAlias ||
-               semantic_parent.unwrap().kind() == CXCursor_NamespaceRef) {
-            semantic_parent = semantic_parent.unwrap()
-                .fallible_semantic_parent();
+            (semantic_parent.unwrap().kind() == CXCursor_Namespace ||
+                 semantic_parent.unwrap().kind() == CXCursor_NamespaceAlias ||
+                 semantic_parent.unwrap().kind() == CXCursor_NamespaceRef)
+        {
+            semantic_parent =
+                semantic_parent.unwrap().fallible_semantic_parent();
         }
 
         let tu = self.translation_unit();
         // Yes, this can happen with, e.g., macro definitions.
         semantic_parent == tu.fallible_semantic_parent()
     }
 
     /// There are a few kinds of types that we need to treat specially, mainly
@@ -251,18 +254,18 @@ impl Cursor {
     pub fn is_template_specialization(&self) -> bool {
         self.specialized().is_some()
     }
 
     /// Is the referent a fully specialized template specialization without any
     /// remaining free template arguments?
     pub fn is_fully_specialized_template(&self) -> bool {
         self.is_template_specialization() &&
-        self.kind() != CXCursor_ClassTemplatePartialSpecialization &&
-        self.num_template_args().unwrap_or(0) > 0
+            self.kind() != CXCursor_ClassTemplatePartialSpecialization &&
+            self.num_template_args().unwrap_or(0) > 0
     }
 
     /// Is the referent a template specialization that still has remaining free
     /// template arguments?
     pub fn is_in_non_fully_specialized_template(&self) -> bool {
         if self.is_toplevel() {
             return false;
         }
@@ -383,22 +386,25 @@ impl Cursor {
     pub fn template_kind(&self) -> CXCursorKind {
         unsafe { clang_getTemplateCursorKind(self.x) }
     }
 
     /// Traverse this cursor's referent and its children.
     ///
     /// Call the given function on each AST node traversed.
     pub fn visit<Visitor>(&self, mut visitor: Visitor)
-        where Visitor: FnMut(Cursor) -> CXChildVisitResult,
+    where
+        Visitor: FnMut(Cursor) -> CXChildVisitResult,
     {
         unsafe {
-            clang_visitChildren(self.x,
-                                visit_children::<Visitor>,
-                                mem::transmute(&mut visitor));
+            clang_visitChildren(
+                self.x,
+                visit_children::<Visitor>,
+                mem::transmute(&mut visitor),
+            );
         }
     }
 
     /// Collect all of this cursor's children into a vec and return them.
     pub fn collect_children(&self) -> Vec<Cursor> {
         let mut children = vec![];
         self.visit(|c| {
             children.push(c);
@@ -446,17 +452,17 @@ impl Cursor {
         });
 
         found
     }
 
     /// Is the referent an inlined function?
     pub fn is_inlined_function(&self) -> bool {
         clang_Cursor_isFunctionInlined::is_loaded() &&
-        unsafe { clang_Cursor_isFunctionInlined(self.x) != 0 }
+            unsafe { clang_Cursor_isFunctionInlined(self.x) != 0 }
     }
 
     /// Get the width of this cursor's referent bit field, or `None` if the
     /// referent is not a bit field.
     pub fn bit_width(&self) -> Option<u32> {
         unsafe {
             let w = clang_getFieldDeclBitWidth(self.x);
             if w == -1 { None } else { Some(w as u32) }
@@ -567,17 +573,17 @@ impl Cursor {
     pub fn access_specifier(&self) -> CX_CXXAccessSpecifier {
         unsafe { clang_getCXXAccessSpecifier(self.x) }
     }
 
     /// Is this cursor's referent a field declaration that is marked as
     /// `mutable`?
     pub fn is_mutable_field(&self) -> bool {
         clang_CXXField_isMutable::is_loaded() &&
-        unsafe { clang_CXXField_isMutable(self.x) != 0 }
+            unsafe { clang_CXXField_isMutable(self.x) != 0 }
     }
 
     /// Get the offset of the field represented by the Cursor.
     pub fn offset_of_field(&self) -> Result<usize, LayoutError> {
         if !clang_Cursor_getOffsetOfField::is_loaded() {
             return Err(LayoutError::from(-1));
         }
 
@@ -623,28 +629,31 @@ impl Cursor {
         if rt.is_valid() { Some(rt) } else { None }
     }
 }
 
 /// Checks whether the name looks like an identifier, i.e. is alphanumeric
 /// (including '_') and does not start with a digit.
 pub fn is_valid_identifier(name: &str) -> bool {
     let mut chars = name.chars();
-    let first_valid = chars.next()
+    let first_valid = chars
+        .next()
         .map(|c| c.is_alphabetic() || c == '_')
         .unwrap_or(false);
 
     first_valid && chars.all(|c| c.is_alphanumeric() || c == '_')
 }
 
-extern "C" fn visit_children<Visitor>(cur: CXCursor,
-                                      _parent: CXCursor,
-                                      data: CXClientData)
-                                      -> CXChildVisitResult
-    where Visitor: FnMut(Cursor) -> CXChildVisitResult,
+extern "C" fn visit_children<Visitor>(
+    cur: CXCursor,
+    _parent: CXCursor,
+    data: CXClientData,
+) -> CXChildVisitResult
+where
+    Visitor: FnMut(Cursor) -> CXChildVisitResult,
 {
     let func: &mut Visitor = unsafe { mem::transmute(data) };
     let child = Cursor {
         x: cur,
     };
 
     (*func)(child)
 }
@@ -674,23 +683,25 @@ impl PartialEq for Type {
         unsafe { clang_equalTypes(self.x, other.x) != 0 }
     }
 }
 
 impl Eq for Type {}
 
 impl fmt::Debug for Type {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt,
-               "Type({}, kind: {}, cconv: {}, decl: {:?}, canon: {:?})",
-               self.spelling(),
-               type_to_str(self.kind()),
-               self.call_conv(),
-               self.declaration(),
-               self.declaration().canonical())
+        write!(
+            fmt,
+            "Type({}, kind: {}, cconv: {}, decl: {:?}, canon: {:?})",
+            self.spelling(),
+            type_to_str(self.kind()),
+            self.call_conv(),
+            self.declaration(),
+            self.declaration().canonical()
+        )
     }
 }
 
 /// An error about the layout of a struct, class, or type.
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 pub enum LayoutError {
     /// Asked for the layout of an invalid type.
     Invalid,
@@ -733,19 +744,20 @@ impl Type {
         unsafe {
             Cursor {
                 x: clang_getTypeDeclaration(self.x),
             }
         }
     }
 
     /// Get the canonical declaration of this type, if it is available.
-    pub fn canonical_declaration(&self,
-                                 location: Option<&Cursor>)
-                                 -> Option<CanonicalTypeDeclaration> {
+    pub fn canonical_declaration(
+        &self,
+        location: Option<&Cursor>,
+    ) -> Option<CanonicalTypeDeclaration> {
         let mut declaration = self.declaration();
         if !declaration.is_valid() {
             if let Some(location) = location {
                 let mut location = *location;
                 if let Some(referenced) = location.referenced() {
                     location = referenced;
                 }
                 if location.is_template_like() {
@@ -952,22 +964,22 @@ impl Type {
     }
 
     /// Is this type a fully instantiated template?
     pub fn is_fully_instantiated_template(&self) -> bool {
         // Yep, the spelling of this containing type-parameter is extremely
         // nasty... But can happen in <type_traits>. Unfortunately I couldn't
         // reduce it enough :(
         self.template_args().map_or(false, |args| args.len() > 0) &&
-        match self.declaration().kind() {
-            CXCursor_ClassTemplatePartialSpecialization |
-            CXCursor_TypeAliasTemplateDecl |
-            CXCursor_TemplateTemplateParameter => false,
-            _ => true,
-        }
+            match self.declaration().kind() {
+                CXCursor_ClassTemplatePartialSpecialization |
+                CXCursor_TypeAliasTemplateDecl |
+                CXCursor_TemplateTemplateParameter => false,
+                _ => true,
+            }
     }
 
     /// Is this type an associated template type? Eg `T::Associated` in
     /// this example:
     ///
     /// ```c++
     /// template <typename T>
     /// class Foo {
@@ -980,18 +992,18 @@ impl Type {
             lazy_static! {
                 static ref ASSOC_TYPE_RE: regex::Regex =
                     regex::Regex::new(r"typename type\-parameter\-\d+\-\d+::.+").unwrap();
             }
             ASSOC_TYPE_RE.is_match(spelling.as_ref())
         }
 
         self.kind() == CXType_Unexposed &&
-        (hacky_parse_associated_type(self.spelling()) ||
-         hacky_parse_associated_type(self.canonical_type().spelling()))
+            (hacky_parse_associated_type(self.spelling()) ||
+                 hacky_parse_associated_type(self.canonical_type().spelling()))
     }
 }
 
 /// The `CanonicalTypeDeclaration` type exists as proof-by-construction that its
 /// cursor is the canonical declaration for its type. If you have a
 /// `CanonicalTypeDeclaration` instance, you know for sure that the type and
 /// cursor match up in a canonical declaration relationship, and it simply
 /// cannot be otherwise.
@@ -1049,27 +1061,31 @@ impl SourceLocation {
     /// Get the (file, line, column, byte offset) tuple for this source
     /// location.
     pub fn location(&self) -> (File, usize, usize, usize) {
         unsafe {
             let mut file = mem::zeroed();
             let mut line = 0;
             let mut col = 0;
             let mut off = 0;
-            clang_getSpellingLocation(self.x,
-                                      &mut file,
-                                      &mut line,
-                                      &mut col,
-                                      &mut off);
-            (File {
-                 x: file,
-             },
-             line as usize,
-             col as usize,
-             off as usize)
+            clang_getSpellingLocation(
+                self.x,
+                &mut file,
+                &mut line,
+                &mut col,
+                &mut off,
+            );
+            (
+                File {
+                    x: file,
+                },
+                line as usize,
+                col as usize,
+                off as usize,
+            )
         }
     }
 }
 
 impl fmt::Display for SourceLocation {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         let (file, line, col, _) = self.location();
         if let Some(name) = file.name() {
@@ -1159,21 +1175,23 @@ impl Iterator for CommentAttributesItera
     type Item = CommentAttribute;
     fn next(&mut self) -> Option<CommentAttribute> {
         if self.index < self.length {
             let idx = self.index;
             self.index += 1;
             Some(CommentAttribute {
                 name: unsafe {
                     cxstring_into_string(
-                        clang_HTMLStartTag_getAttrName(self.x, idx))
+                        clang_HTMLStartTag_getAttrName(self.x, idx),
+                    )
                 },
                 value: unsafe {
                     cxstring_into_string(
-                        clang_HTMLStartTag_getAttrValue(self.x, idx))
+                        clang_HTMLStartTag_getAttrValue(self.x, idx),
+                    )
                 },
             })
         } else {
             None
         }
     }
 }
 
@@ -1259,37 +1277,42 @@ pub struct TranslationUnit {
 impl fmt::Debug for TranslationUnit {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
         write!(fmt, "TranslationUnit {{ }}")
     }
 }
 
 impl TranslationUnit {
     /// Parse a source file into a translation unit.
-    pub fn parse(ix: &Index,
-                 file: &str,
-                 cmd_args: &[String],
-                 unsaved: &[UnsavedFile],
-                 opts: CXTranslationUnit_Flags)
-                 -> Option<TranslationUnit> {
+    pub fn parse(
+        ix: &Index,
+        file: &str,
+        cmd_args: &[String],
+        unsaved: &[UnsavedFile],
+        opts: CXTranslationUnit_Flags,
+    ) -> Option<TranslationUnit> {
         let fname = CString::new(file).unwrap();
-        let _c_args: Vec<CString> =
-            cmd_args.iter().map(|s| CString::new(s.clone()).unwrap()).collect();
+        let _c_args: Vec<CString> = cmd_args
+            .iter()
+            .map(|s| CString::new(s.clone()).unwrap())
+            .collect();
         let c_args: Vec<*const c_char> =
             _c_args.iter().map(|s| s.as_ptr()).collect();
         let mut c_unsaved: Vec<CXUnsavedFile> =
             unsaved.iter().map(|f| f.x).collect();
         let tu = unsafe {
-            clang_parseTranslationUnit(ix.x,
-                                       fname.as_ptr(),
-                                       c_args.as_ptr(),
-                                       c_args.len() as c_int,
-                                       c_unsaved.as_mut_ptr(),
-                                       c_unsaved.len() as c_uint,
-                                       opts)
+            clang_parseTranslationUnit(
+                ix.x,
+                fname.as_ptr(),
+                c_args.as_ptr(),
+                c_args.len() as c_int,
+                c_unsaved.as_mut_ptr(),
+                c_unsaved.len() as c_uint,
+                opts,
+            )
         };
         if tu.is_null() {
             None
         } else {
             Some(TranslationUnit {
                 x: tu,
             })
         }
@@ -1332,18 +1355,18 @@ impl TranslationUnit {
         unsafe {
             let mut token_ptr = ptr::null_mut();
             let mut num_tokens: c_uint = 0;
             clang_tokenize(self.x, range, &mut token_ptr, &mut num_tokens);
             if token_ptr.is_null() {
                 return None;
             }
 
-            let token_array = slice::from_raw_parts(token_ptr,
-                                                    num_tokens as usize);
+            let token_array =
+                slice::from_raw_parts(token_ptr, num_tokens as usize);
             for &token in token_array.iter() {
                 let kind = clang_getTokenKind(token);
                 let spelling =
                     cxstring_into_string(clang_getTokenSpelling(self.x, token));
 
                 tokens.push(Token {
                     kind: kind,
                     spelling: spelling,
@@ -1351,36 +1374,37 @@ impl TranslationUnit {
             }
             clang_disposeTokens(self.x, token_ptr, num_tokens);
         }
         Some(tokens)
     }
 
     /// Convert a set of tokens from clang into `cexpr` tokens, for further
     /// processing.
-    pub fn cexpr_tokens(&self,
-                        cursor: &Cursor)
-                        -> Option<Vec<cexpr::token::Token>> {
+    pub fn cexpr_tokens(
+        &self,
+        cursor: &Cursor,
+    ) -> Option<Vec<cexpr::token::Token>> {
         use cexpr::token;
 
         self.tokens(cursor).map(|tokens| {
             tokens
                 .into_iter()
                 .filter_map(|token| {
                     let kind = match token.kind {
                         CXToken_Punctuation => token::Kind::Punctuation,
                         CXToken_Literal => token::Kind::Literal,
                         CXToken_Identifier => token::Kind::Identifier,
                         CXToken_Keyword => token::Kind::Keyword,
                         // NB: cexpr is not too happy about comments inside
                         // expressions, so we strip them down here.
                         CXToken_Comment => return None,
                         _ => {
                             error!("Found unexpected token kind: {:?}", token);
-                            return None
+                            return None;
                         }
                     };
 
                     Some(token::Token {
                         kind: kind,
                         raw: token.spelling.into_bytes().into_boxed_slice(),
                     })
                 })
@@ -1452,20 +1476,22 @@ impl UnsavedFile {
             name: name,
             contents: contents,
         }
     }
 }
 
 impl fmt::Debug for UnsavedFile {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt,
-               "UnsavedFile(name: {:?}, contents: {:?})",
-               self.name,
-               self.contents)
+        write!(
+            fmt,
+            "UnsavedFile(name: {:?}, contents: {:?})",
+            self.name,
+            self.contents
+        )
     }
 }
 
 /// Convert a cursor kind into a static string.
 pub fn kind_to_str(x: CXCursorKind) -> String {
     unsafe { cxstring_into_string(clang_getCursorKindSpelling(x)) }
 }
 
@@ -1480,139 +1506,165 @@ pub fn ast_dump(c: &Cursor, depth: isize
         for _ in 0..depth {
             print!("    ");
         }
         println!("{}", s.as_ref());
     }
 
     fn print_cursor<S: AsRef<str>>(depth: isize, prefix: S, c: &Cursor) {
         let prefix = prefix.as_ref();
-        print_indent(depth,
-                     format!(" {}kind = {}", prefix, kind_to_str(c.kind())));
-        print_indent(depth,
-                     format!(" {}spelling = \"{}\"", prefix, c.spelling()));
+        print_indent(
+            depth,
+            format!(" {}kind = {}", prefix, kind_to_str(c.kind())),
+        );
+        print_indent(
+            depth,
+            format!(" {}spelling = \"{}\"", prefix, c.spelling()),
+        );
         print_indent(depth, format!(" {}location = {}", prefix, c.location()));
-        print_indent(depth,
-                     format!(" {}is-definition? {}",
-                             prefix,
-                             c.is_definition()));
-        print_indent(depth,
-                     format!(" {}is-declaration? {}",
-                             prefix,
-                             c.is_declaration()));
-        print_indent(depth,
-                     format!(" {}is-inlined-function? {}",
-                             prefix,
-                             c.is_inlined_function()));
+        print_indent(
+            depth,
+            format!(" {}is-definition? {}", prefix, c.is_definition()),
+        );
+        print_indent(
+            depth,
+            format!(" {}is-declaration? {}", prefix, c.is_declaration()),
+        );
+        print_indent(
+            depth,
+            format!(
+                " {}is-inlined-function? {}",
+                prefix,
+                c.is_inlined_function()
+            ),
+        );
 
         let templ_kind = c.template_kind();
         if templ_kind != CXCursor_NoDeclFound {
-            print_indent(depth,
-                         format!(" {}template-kind = {}",
-                                 prefix,
-                                 kind_to_str(templ_kind)));
+            print_indent(
+                depth,
+                format!(" {}template-kind = {}", prefix, kind_to_str(templ_kind)),
+            );
         }
         if let Some(usr) = c.usr() {
             print_indent(depth, format!(" {}usr = \"{}\"", prefix, usr));
         }
         if let Ok(num) = c.num_args() {
             print_indent(depth, format!(" {}number-of-args = {}", prefix, num));
         }
         if let Some(num) = c.num_template_args() {
-            print_indent(depth,
-                         format!(" {}number-of-template-args = {}",
-                                 prefix,
-                                 num));
+            print_indent(
+                depth,
+                format!(" {}number-of-template-args = {}", prefix, num),
+            );
         }
         if let Some(width) = c.bit_width() {
             print_indent(depth, format!(" {}bit-width = {}", prefix, width));
         }
         if let Some(ty) = c.enum_type() {
-            print_indent(depth,
-                         format!(" {}enum-type = {}",
-                                 prefix,
-                                 type_to_str(ty.kind())));
+            print_indent(
+                depth,
+                format!(" {}enum-type = {}", prefix, type_to_str(ty.kind())),
+            );
         }
         if let Some(val) = c.enum_val_signed() {
             print_indent(depth, format!(" {}enum-val = {}", prefix, val));
         }
         if let Some(ty) = c.typedef_type() {
-            print_indent(depth,
-                         format!(" {}typedef-type = {}",
-                                 prefix,
-                                 type_to_str(ty.kind())));
+            print_indent(
+                depth,
+                format!(" {}typedef-type = {}", prefix, type_to_str(ty.kind())),
+            );
         }
         if let Some(ty) = c.ret_type() {
-            print_indent(depth,
-                         format!(" {}ret-type = {}",
-                                 prefix,
-                                 type_to_str(ty.kind())));
+            print_indent(
+                depth,
+                format!(" {}ret-type = {}", prefix, type_to_str(ty.kind())),
+            );
         }
 
         if let Some(refd) = c.referenced() {
             if refd != *c {
                 println!("");
-                print_cursor(depth,
-                             String::from(prefix) + "referenced.",
-                             &refd);
+                print_cursor(
+                    depth,
+                    String::from(prefix) + "referenced.",
+                    &refd,
+                );
             }
         }
 
         let canonical = c.canonical();
         if canonical != *c {
             println!("");
-            print_cursor(depth,
-                         String::from(prefix) + "canonical.",
-                         &canonical);
+            print_cursor(
+                depth,
+                String::from(prefix) + "canonical.",
+                &canonical,
+            );
         }
 
         if let Some(specialized) = c.specialized() {
             if specialized != *c {
                 println!("");
-                print_cursor(depth,
-                             String::from(prefix) + "specialized.",
-                             &specialized);
+                print_cursor(
+                    depth,
+                    String::from(prefix) + "specialized.",
+                    &specialized,
+                );
             }
         }
 
         if let Some(parent) = c.fallible_semantic_parent() {
             println!("");
-            print_cursor(depth,
-                         String::from(prefix) + "semantic-parent.",
-                         &parent);
+            print_cursor(
+                depth,
+                String::from(prefix) + "semantic-parent.",
+                &parent,
+            );
         }
     }
 
     fn print_type<S: AsRef<str>>(depth: isize, prefix: S, ty: &Type) {
         let prefix = prefix.as_ref();
 
         let kind = ty.kind();
         print_indent(depth, format!(" {}kind = {}", prefix, type_to_str(kind)));
         if kind == CXType_Invalid {
             return;
         }
 
         print_indent(depth, format!(" {}cconv = {}", prefix, ty.call_conv()));
 
-        print_indent(depth,
-                     format!(" {}spelling = \"{}\"", prefix, ty.spelling()));
+        print_indent(
+            depth,
+            format!(" {}spelling = \"{}\"", prefix, ty.spelling()),
+        );
         let num_template_args =
             unsafe { clang_Type_getNumTemplateArguments(ty.x) };
         if num_template_args >= 0 {
-            print_indent(depth,
-                         format!(" {}number-of-template-args = {}",
-                                 prefix,
-                                 num_template_args));
+            print_indent(
+                depth,
+                format!(
+                    " {}number-of-template-args = {}",
+                    prefix,
+                    num_template_args
+                ),
+            );
         }
         if let Some(num) = ty.num_elements() {
-            print_indent(depth,
-                         format!(" {}number-of-elements = {}", prefix, num));
+            print_indent(
+                depth,
+                format!(" {}number-of-elements = {}", prefix, num),
+            );
         }
-        print_indent(depth,
-                     format!(" {}is-variadic? {}", prefix, ty.is_variadic()));
+        print_indent(
+            depth,
+            format!(" {}is-variadic? {}", prefix, ty.is_variadic()),
+        );
 
         let canonical = ty.canonical_type();
         if canonical != *ty {
             println!("");
             print_type(depth, String::from(prefix) + "canonical.", &canonical);
         }
 
         if let Some(pointee) = ty.pointee_type() {
@@ -1694,17 +1746,18 @@ impl EvalResult {
         // the assertion aborts the process, and we don't want that. Clang
         // *also* doesn't expose any API for finding variadic vs non-variadic
         // template type references, let alone whether a type referenced is a
         // template type, instead they seem to show up as type references to an
         // unexposed type. Our solution is to just flat out ban all
         // `CXType_Unexposed` from evaluation.
         let mut found_cant_eval = false;
         cursor.visit(|c| if c.kind() == CXCursor_TypeRef &&
-                            c.cur_type().kind() == CXType_Unexposed {
+            c.cur_type().kind() == CXType_Unexposed
+        {
             found_cant_eval = true;
             CXChildVisit_Break
         } else {
             CXChildVisit_Recurse
         });
         if found_cant_eval {
             return None;
         }
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bindgen/src/codegen/derive_debug.rs
@@ -0,0 +1,223 @@
+use ir::comp::{BitfieldUnit, CompKind, Field, FieldData, FieldMethods};
+use ir::context::BindgenContext;
+use ir::derive::CanTriviallyDeriveDebug;
+use ir::item::{HasTypeParamInArray, IsOpaque, Item, ItemCanonicalName};
+use ir::ty::{RUST_DERIVE_IN_ARRAY_LIMIT, TypeKind};
+use syntax::ast;
+use syntax::codemap::DUMMY_SP;
+use syntax::parse::token::Token;
+
+use syntax::tokenstream::TokenTree;
+
+pub fn gen_debug_impl(
+    ctx: &BindgenContext,
+    fields: &[Field],
+    item: &Item,
+    kind: CompKind,
+) -> Vec<ast::ImplItem> {
+    let struct_name = item.canonical_name(ctx);
+    let mut format_string = format!("{} {{{{ ", struct_name);
+    let mut tokens: Vec<TokenTree> = Vec::new();
+
+    if item.is_opaque(ctx, &()) {
+        format_string.push_str("opaque");
+    } else {
+        match kind {
+            CompKind::Union => {
+                format_string.push_str("union");
+            }
+            CompKind::Struct => {
+                let processed_fields = fields.iter().filter_map(|f| match f {
+                    &Field::DataMember(ref fd) => fd.impl_debug(ctx, ()),
+                    &Field::Bitfields(ref bu) => bu.impl_debug(ctx, ()),
+                });
+
+
+                for (i, (fstring, token)) in processed_fields.enumerate() {
+                    if i > 0 {
+                        format_string.push_str(", ");
+                    }
+                    if !token.is_empty() {
+                        tokens.push(TokenTree::Token(DUMMY_SP, Token::Comma));
+                        tokens.extend(token);
+                    }
+                    format_string.push_str(&fstring);
+                }
+            }
+        }
+    }
+
+    format_string.push_str(" }}");
+
+    let impl_ = quote_item!(ctx.ext_cx(),
+                            impl X {
+                                fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+                                    write!(f, $format_string $tokens)
+                                }    
+                            });
+
+    match impl_.unwrap().node {
+        ast::ItemKind::Impl(_, _, _, _, _, ref items) => items.clone(),
+        _ => unreachable!(),
+    }
+}
+
+/// A trait for the things which we can codegen tokens that contribute towards a
+/// generated `impl Debug`.
+pub trait ImplDebug<'a> {
+    /// Any extra parameter required by this a particular `ImplDebug` implementation.
+    type Extra;
+
+    /// Generate a format string snippet to be included in the larger `impl Debug`
+    /// format string, and the code to get the format string's interpolation values.
+    fn impl_debug(
+        &self,
+        ctx: &BindgenContext,
+        extra: Self::Extra,
+    ) -> Option<(String, Vec<TokenTree>)>;
+}
+
+impl<'a> ImplDebug<'a> for FieldData {
+    type Extra = ();
+
+    fn impl_debug(
+        &self,
+        ctx: &BindgenContext,
+        _: Self::Extra,
+    ) -> Option<(String, Vec<TokenTree>)> {
+        if let Some(name) = self.name() {
+            ctx.resolve_item(self.ty()).impl_debug(ctx, name)
+        } else {
+            None
+        }
+    }
+}
+
+impl<'a> ImplDebug<'a> for BitfieldUnit {
+    type Extra = ();
+
+    fn impl_debug(
+        &self,
+        ctx: &BindgenContext,
+        _: Self::Extra,
+    ) -> Option<(String, Vec<TokenTree>)> {
+        let mut format_string = String::new();
+        let mut tokens = Vec::new();
+        for (i, bu) in self.bitfields().iter().enumerate() {
+            if i > 0 {
+                format_string.push_str(", ");
+                tokens.push(TokenTree::Token(DUMMY_SP, Token::Comma));
+            }
+            format_string.push_str(&format!("{} : {{:?}}", bu.name()));
+            let name_ident = ctx.rust_ident_raw(bu.name());
+            tokens.extend(quote_tokens!(ctx.ext_cx(), self.$name_ident()));
+        }
+
+        Some((format_string, tokens))
+    }
+}
+
+impl<'a> ImplDebug<'a> for Item {
+    type Extra = &'a str;
+
+    fn impl_debug(
+        &self,
+        ctx: &BindgenContext,
+        name: Self::Extra,
+    ) -> Option<(String, Vec<TokenTree>)> {
+        let name_ident = ctx.rust_ident_raw(name);
+
+        let ty = match self.as_type() {
+            Some(ty) => ty,
+            None => {
+                return None;
+            }
+        };
+
+        fn debug_print(
+            ctx: &BindgenContext,
+            name: &str,
+            name_ident: ast::Ident,
+        ) -> Option<(String, Vec<TokenTree>)> {
+            Some((
+                format!("{}: {{:?}}", name),
+                quote_tokens!(ctx.ext_cx(), self.$name_ident),
+            ))
+        }
+
+        match *ty.kind() {
+            // Handle the simple cases.
+            TypeKind::Void |
+            TypeKind::NullPtr |
+            TypeKind::Int(..) |
+            TypeKind::Float(..) |
+            TypeKind::Complex(..) |
+            TypeKind::Function(..) |
+            TypeKind::Enum(..) |
+            TypeKind::Reference(..) |
+            TypeKind::BlockPointer |
+            TypeKind::UnresolvedTypeRef(..) |
+            TypeKind::ObjCInterface(..) |
+            TypeKind::ObjCId |
+            TypeKind::Comp(..) |
+            TypeKind::ObjCSel => debug_print(ctx, name, name_ident),
+
+            TypeKind::TemplateInstantiation(ref inst) => {
+                if inst.is_opaque(ctx, self) {
+                    Some((format!("{}: opaque", name), vec![]))
+                } else {
+                    debug_print(ctx, name, name_ident)
+                }
+            } 
+
+            // The generic is not required to implement Debug, so we can not debug print that type
+            TypeKind::TypeParam => {
+                Some((format!("{}: Non-debuggable generic", name), vec![]))
+            }
+
+            TypeKind::Array(_, len) => {
+                // Generics are not required to implement Debug
+                if self.has_type_param_in_array(ctx) {
+                    Some(
+                        (format!("{}: Array with length {}", name, len), vec![]),
+                    )
+                } else if len < RUST_DERIVE_IN_ARRAY_LIMIT {
+                    // The simple case
+                    debug_print(ctx, name, name_ident)
+                } else {
+                    // Let's implement our own print function
+                    Some((
+                        format!("{}: [{{}}]", name),
+                        quote_tokens!(
+                        ctx.ext_cx(),
+                        self.$name_ident
+                            .iter()
+                            .enumerate()
+                            .map(|(i, v)| format!("{}{:?}", if i > 0 { ", " } else { "" }, v))
+                            .collect::<String>()),
+                    ))
+                }
+            }
+
+            TypeKind::ResolvedTypeRef(t) |
+            TypeKind::TemplateAlias(t, _) |
+            TypeKind::Alias(t) => {
+                // We follow the aliases
+                ctx.resolve_item(t).impl_debug(ctx, name)
+            }
+
+            TypeKind::Pointer(inner) => {
+                let inner_type = ctx.resolve_type(inner).canonical_type(ctx);
+                match *inner_type.kind() {
+                    TypeKind::Function(ref sig)
+                        if !sig.can_trivially_derive_debug() => {
+                        Some((format!("{}: FunctionPointer", name), vec![]))
+                    }
+                    _ => debug_print(ctx, name, name_ident),
+                }
+            }
+
+            TypeKind::Opaque => None,
+        }
+    }
+}
--- a/third_party/rust/bindgen/src/codegen/helpers.rs
+++ b/third_party/rust/bindgen/src/codegen/helpers.rs
@@ -6,80 +6,87 @@ use syntax::ast;
 use syntax::ptr::P;
 
 
 pub mod attributes {
     use aster;
     use syntax::ast;
 
     pub fn allow(which_ones: &[&str]) -> ast::Attribute {
-        aster::AstBuilder::new().attr().list("allow").words(which_ones).build()
+        aster::AstBuilder::new()
+            .attr()
+            .list("allow")
+            .words(which_ones)
+            .build()
     }
 
     pub fn repr(which: &str) -> ast::Attribute {
-        aster::AstBuilder::new().attr().list("repr").words(&[which]).build()
+        aster::AstBuilder::new()
+            .attr()
+            .list("repr")
+            .words(&[which])
+            .build()
     }
 
     pub fn repr_list(which_ones: &[&str]) -> ast::Attribute {
-        aster::AstBuilder::new().attr().list("repr").words(which_ones).build()
+        aster::AstBuilder::new()
+            .attr()
+            .list("repr")
+            .words(which_ones)
+            .build()
     }
 
     pub fn derives(which_ones: &[&str]) -> ast::Attribute {
-        aster::AstBuilder::new().attr().list("derive").words(which_ones).build()
+        aster::AstBuilder::new()
+            .attr()
+            .list("derive")
+            .words(which_ones)
+            .build()
     }
 
     pub fn inline() -> ast::Attribute {
         aster::AstBuilder::new().attr().word("inline")
     }
 
     pub fn doc(comment: String) -> ast::Attribute {
         aster::AstBuilder::new().attr().doc(&*comment)
     }
 
     pub fn link_name(name: &str) -> ast::Attribute {
-        aster::AstBuilder::new().attr().name_value("link_name").str(name)
+        aster::AstBuilder::new()
+            .attr()
+            .name_value("link_name")
+            .str(name)
     }
 }
 
 /// Generates a proper type for a field or type with a given `Layout`, that is,
 /// a type with the correct size and alignment restrictions.
-pub struct BlobTyBuilder {
-    layout: Layout,
-}
-
-impl BlobTyBuilder {
-    pub fn new(layout: Layout) -> Self {
-        BlobTyBuilder {
-            layout: layout,
-        }
-    }
-
-    pub fn build(self) -> P<ast::Ty> {
-        let opaque = self.layout.opaque();
+pub fn blob(layout: Layout) -> P<ast::Ty> {
+    let opaque = layout.opaque();
 
-        // FIXME(emilio, #412): We fall back to byte alignment, but there are
-        // some things that legitimately are more than 8-byte aligned.
-        //
-        // Eventually we should be able to `unwrap` here, but...
-        let ty_name = match opaque.known_rust_type_for_array() {
-            Some(ty) => ty,
-            None => {
-                warn!("Found unknown alignment on code generation!");
-                "u8"
-            }
-        };
+    // FIXME(emilio, #412): We fall back to byte alignment, but there are
+    // some things that legitimately are more than 8-byte aligned.
+    //
+    // Eventually we should be able to `unwrap` here, but...
+    let ty_name = match opaque.known_rust_type_for_array() {
+        Some(ty) => ty,
+        None => {
+            warn!("Found unknown alignment on code generation!");
+            "u8"
+        }
+    };
 
-        let data_len = opaque.array_size().unwrap_or(self.layout.size);
+    let data_len = opaque.array_size().unwrap_or(layout.size);
 
-        let inner_ty = aster::AstBuilder::new().ty().path().id(ty_name).build();
-        if data_len == 1 {
-            inner_ty
-        } else {
-            aster::ty::TyBuilder::new().array(data_len).build(inner_ty)
-        }
+    let inner_ty = aster::AstBuilder::new().ty().path().id(ty_name).build();
+    if data_len == 1 {
+        inner_ty
+    } else {
+        aster::ty::TyBuilder::new().array(data_len).build(inner_ty)
     }
 }
 
 pub mod ast_ty {
     use aster;
     use ir::context::BindgenContext;
     use ir::function::FunctionSig;
     use ir::ty::FloatKind;
@@ -92,19 +99,20 @@ pub mod ast_ty {
             Some(ref prefix) => {
                 let prefix = ctx.rust_ident_raw(prefix);
                 quote_ty!(ctx.ext_cx(), $prefix::$ident)
             }
             None => quote_ty!(ctx.ext_cx(), ::std::os::raw::$ident),
         }
     }
 
-    pub fn float_kind_rust_type(ctx: &BindgenContext,
-                                fk: FloatKind)
-                                -> P<ast::Ty> {
+    pub fn float_kind_rust_type(
+        ctx: &BindgenContext,
+        fk: FloatKind,
+    ) -> P<ast::Ty> {
         // TODO: we probably should just take the type layout into
         // account?
         //
         // Also, maybe this one shouldn't be the default?
         //
         // FIXME: `c_longdouble` doesn't seem to be defined in some
         // systems, so we use `c_double` directly.
         match (fk, ctx.options().convert_floats) {
@@ -148,36 +156,40 @@ pub mod ast_ty {
 
         let kind = ast::ExprKind::Array(vec);
 
         aster::AstBuilder::new().expr().build_expr_kind(kind)
     }
 
     pub fn cstr_expr(mut string: String) -> P<ast::Expr> {
         string.push('\0');
-        aster::AstBuilder::new()
-            .expr()
-            .build_lit(aster::AstBuilder::new().lit().byte_str(string))
+        aster::AstBuilder::new().expr().build_lit(
+            aster::AstBuilder::new()
+                .lit()
+                .byte_str(string),
+        )
     }
 
-    pub fn float_expr(ctx: &BindgenContext,
-                      f: f64)
-                      -> Result<P<ast::Expr>, ()> {
+    pub fn float_expr(
+        ctx: &BindgenContext,
+        f: f64,
+    ) -> Result<P<ast::Expr>, ()> {
         use aster::symbol::ToSymbol;
 
         if f.is_finite() {
             let mut string = f.to_string();
 
             // So it gets properly recognised as a floating point constant.
             if !string.contains('.') {
                 string.push('.');
             }
 
-            let kind = ast::LitKind::FloatUnsuffixed(string.as_str().to_symbol());
-            return Ok(aster::AstBuilder::new().expr().lit().build_lit(kind))
+            let kind =
+                ast::LitKind::FloatUnsuffixed(string.as_str().to_symbol());
+            return Ok(aster::AstBuilder::new().expr().lit().build_lit(kind));
         }
 
         let prefix = ctx.trait_prefix();
         if f.is_nan() {
             return Ok(quote_expr!(ctx.ext_cx(), ::$prefix::f64::NAN));
         }
 
         if f.is_infinite() {
@@ -187,23 +199,25 @@ pub mod ast_ty {
                 quote_expr!(ctx.ext_cx(), ::$prefix::f64::NEG_INFINITY)
             });
         }
 
         warn!("Unknown non-finite float number: {:?}", f);
         return Err(());
     }
 
-    pub fn arguments_from_signature(signature: &FunctionSig,
-                                    ctx: &BindgenContext)
-                                    -> Vec<P<ast::Expr>> {
+    pub fn arguments_from_signature(
+        signature: &FunctionSig,
+        ctx: &BindgenContext,
+    ) -> Vec<P<ast::Expr>> {
         // TODO: We need to keep in sync the argument names, so we should unify
         // this with the other loop that decides them.
         let mut unnamed_arguments = 0;
-        signature.argument_types()
+        signature
+            .argument_types()
             .iter()
             .map(|&(ref name, _ty)| {
                 let arg_name = match *name {
                     Some(ref name) => ctx.rust_mangle(name).into_owned(),
                     None => {
                         unnamed_arguments += 1;
                         format!("arg{}", unnamed_arguments)
                     }
--- a/third_party/rust/bindgen/src/codegen/mod.rs
+++ b/third_party/rust/bindgen/src/codegen/mod.rs
@@ -1,24 +1,26 @@
+mod derive_debug;
 mod error;
 mod helpers;
 pub mod struct_layout;
 
-use self::helpers::{BlobTyBuilder, attributes};
+use self::helpers::attributes;
 use self::struct_layout::StructLayoutTracker;
 
 use aster;
 use aster::struct_field::StructFieldBuilder;
 
 use ir::annotations::FieldAccessorKind;
-use ir::comp::{Base, BitfieldUnit, Bitfield, CompInfo, CompKind, Field,
+use ir::comment;
+use ir::comp::{Base, Bitfield, BitfieldUnit, CompInfo, CompKind, Field,
                FieldData, FieldMethods, Method, MethodKind};
-use ir::comment;
 use ir::context::{BindgenContext, ItemId};
-use ir::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
+use ir::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault,
+                 CanDeriveHash, CanDerivePartialEq, CanDeriveEq};
 use ir::dot;
 use ir::enum_ty::{Enum, EnumVariant, EnumVariantValue};
 use ir::function::{Abi, Function, FunctionSig};
 use ir::int::IntKind;
 use ir::item::{IsOpaque, Item, ItemCanonicalName, ItemCanonicalPath};
 use ir::item_kind::ItemKind;
 use ir::layout::Layout;
 use ir::module::Module;
@@ -78,16 +80,19 @@ fn root_import(ctx: &BindgenContext, mod
 
 struct CodegenResult<'a> {
     items: Vec<P<ast::Item>>,
 
     /// A monotonic counter used to add stable unique id's to stuff that doesn't
     /// need to be referenced by anything.
     codegen_id: &'a Cell<usize>,
 
+    /// Whether a bindgen union has been generated at least once.
+    saw_bindgen_union: bool,
+
     /// Whether an union has been generated at least once.
     saw_union: bool,
 
     /// Whether an incomplete array has been generated at least once.
     saw_incomplete_array: bool,
 
     /// Whether Objective C types have been seen at least once.
     saw_objc: bool,
@@ -118,30 +123,36 @@ struct CodegenResult<'a> {
     overload_counters: HashMap<String, u32>,
 }
 
 impl<'a> CodegenResult<'a> {
     fn new(codegen_id: &'a Cell<usize>) -> Self {
         CodegenResult {
             items: vec![],
             saw_union: false,
+            saw_bindgen_union: false,
             saw_incomplete_array: false,
             saw_objc: false,
             codegen_id: codegen_id,
             items_seen: Default::default(),
             functions_seen: Default::default(),
             vars_seen: Default::default(),
             overload_counters: Default::default(),
         }
     }
 
     fn saw_union(&mut self) {
         self.saw_union = true;
     }
 
+    fn saw_bindgen_union(&mut self) {
+        self.saw_union();
+        self.saw_bindgen_union = true;
+    }
+
     fn saw_incomplete_array(&mut self) {
         self.saw_incomplete_array = true;
     }
 
     fn saw_objc(&mut self) {
         self.saw_objc = true;
     }
 
@@ -160,33 +171,33 @@ impl<'a> CodegenResult<'a> {
     fn saw_function(&mut self, name: &str) {
         self.functions_seen.insert(name.into());
     }
 
     /// Get the overload number for the given function name. Increments the
     /// counter internally so the next time we ask for the overload for this
     /// name, we get the incremented value, and so on.
     fn overload_number(&mut self, name: &str) -> u32 {
-        let mut counter =
-            self.overload_counters.entry(name.into()).or_insert(0);
+        let counter = self.overload_counters.entry(name.into()).or_insert(0);
         let number = *counter;
         *counter += 1;
         number
     }
 
     fn seen_var(&self, name: &str) -> bool {
         self.vars_seen.contains(name)
     }
 
     fn saw_var(&mut self, name: &str) {
         self.vars_seen.insert(name.into());
     }
 
     fn inner<F>(&mut self, cb: F) -> Vec<P<ast::Item>>
-        where F: FnOnce(&mut Self),
+    where
+        F: FnOnce(&mut Self),
     {
         let mut new = Self::new(self.codegen_id);
 
         cb(&mut new);
 
         self.saw_union |= new.saw_union;
         self.saw_incomplete_array |= new.saw_incomplete_array;
         self.saw_objc |= new.saw_objc;
@@ -225,17 +236,18 @@ impl ForeignModBuilder {
 
     fn with_foreign_item(mut self, item: ast::ForeignItem) -> Self {
         self.inner.items.push(item);
         self
     }
 
     #[allow(dead_code)]
     fn with_foreign_items<I>(mut self, items: I) -> Self
-        where I: IntoIterator<Item = ast::ForeignItem>,
+    where
+        I: IntoIterator<Item = ast::ForeignItem>,
     {
         self.inner.items.extend(items.into_iter());
         self
     }
 
     fn build(self, ctx: &BindgenContext) -> P<ast::Item> {
         P(ast::Item {
             ident: ctx.rust_ident(""),
@@ -274,37 +286,43 @@ impl ToPtr for P<ast::Ty> {
         })
     }
 }
 
 trait CodeGenerator {
     /// Extra information from the caller.
     type Extra;
 
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   extra: &Self::Extra);
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        extra: &Self::Extra,
+    );
 }
 
 impl CodeGenerator for Item {
     type Extra = ();
 
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   _extra: &()) {
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        _extra: &(),
+    ) {
         if !self.is_enabled_for_codegen(ctx) {
             return;
         }
 
         if self.is_hidden(ctx) || result.seen(self.id()) {
-            debug!("<Item as CodeGenerator>::codegen: Ignoring hidden or seen: \
-                   self = {:?}",
-                   self);
+            debug!(
+                "<Item as CodeGenerator>::codegen: Ignoring hidden or seen: \
+                 self = {:?}",
+                self
+            );
             return;
         }
 
         debug!("<Item as CodeGenerator>::codegen: self = {:?}", self);
         if !ctx.codegen_items().contains(&self.id()) {
             // TODO(emilio, #453): Figure out what to do when this happens
             // legitimately, we could track the opaque stuff and disable the
             // assertion there I guess.
@@ -328,50 +346,53 @@ impl CodeGenerator for Item {
             }
         }
     }
 }
 
 impl CodeGenerator for Module {
     type Extra = Item;
 
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   item: &Item) {
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        item: &Item,
+    ) {
         debug!("<Module as CodeGenerator>::codegen: item = {:?}", item);
 
         let codegen_self = |result: &mut CodegenResult,
                             found_any: &mut bool| {
             for child in self.children() {
                 if ctx.codegen_items().contains(child) {
                     *found_any = true;
-                    ctx.resolve_item(*child)
-                        .codegen(ctx, result, &());
+                    ctx.resolve_item(*child).codegen(ctx, result, &());
                 }
             }
 
             if item.id() == ctx.root_module() {
-                if result.saw_union && !ctx.options().unstable_rust {
+                if result.saw_bindgen_union {
                     utils::prepend_union_types(ctx, &mut *result);
                 }
                 if result.saw_incomplete_array {
                     utils::prepend_incomplete_array_types(ctx, &mut *result);
                 }
                 if ctx.need_bindegen_complex_type() {
                     utils::prepend_complex_type(ctx, &mut *result);
                 }
                 if result.saw_objc {
                     utils::prepend_objc_header(ctx, &mut *result);
                 }
             }
         };
 
         if !ctx.options().enable_cxx_namespaces ||
-           (self.is_inline() && !ctx.options().conservative_inline_namespaces) {
+            (self.is_inline() &&
+                !ctx.options().conservative_inline_namespaces)
+        {
             codegen_self(result, &mut false);
             return;
         }
 
         let mut found_any = false;
         let inner_items = result.inner(|result| {
             result.push(root_import(ctx, item));
             codegen_self(result, &mut found_any);
@@ -383,39 +404,42 @@ impl CodeGenerator for Module {
         }
 
         let module = ast::ItemKind::Mod(ast::Mod {
             inner: ctx.span(),
             items: inner_items,
         });
 
         let name = item.canonical_name(ctx);
-        let item_builder = aster::AstBuilder::new()
-            .item()
-            .pub_();
+        let item_builder = aster::AstBuilder::new().item().pub_();
         let item = if name == "root" {
-            let attrs = &["non_snake_case",
+            let attrs = &[
+                "non_snake_case",
                 "non_camel_case_types",
-                "non_upper_case_globals"];
-            item_builder.with_attr(attributes::allow(attrs))
+                "non_upper_case_globals",
+            ];
+            item_builder
+                .with_attr(attributes::allow(attrs))
                 .build_item_kind(name, module)
         } else {
             item_builder.build_item_kind(name, module)
         };
 
         result.push(item);
     }
 }
 
 impl CodeGenerator for Var {
     type Extra = Item;
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   item: &Item) {
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        item: &Item,
+    ) {
         use ir::var::VarType;
         debug!("<Var as CodeGenerator>::codegen: item = {:?}", item);
         debug_assert!(item.is_enabled_for_codegen(ctx));
 
         let canonical_name = item.canonical_name(ctx);
 
         if result.seen_var(&canonical_name) {
             return;
@@ -452,31 +476,30 @@ impl CodeGenerator for Var {
                     //
                     // TODO: Here we ignore the type we just made up, probably
                     // we should refactor how the variable type and ty id work.
                     let len = bytes.len() + 1;
                     let ty = quote_ty!(ctx.ext_cx(), [u8; $len]);
 
                     match String::from_utf8(bytes.clone()) {
                         Ok(string) => {
-                            const_item.build(helpers::ast_ty::cstr_expr(string))
+                            const_item
+                                .build(helpers::ast_ty::cstr_expr(string))
                                 .build(quote_ty!(ctx.ext_cx(), &'static $ty))
                         }
                         Err(..) => {
                             const_item
                                 .build(helpers::ast_ty::byte_array_expr(bytes))
                                 .build(ty)
                         }
                     }
                 }
                 VarType::Float(f) => {
                     match helpers::ast_ty::float_expr(ctx, f) {
-                        Ok(expr) => {
-                            const_item.build(expr).build(ty)
-                        }
+                        Ok(expr) => const_item.build(expr).build(ty),
                         Err(..) => return,
                     }
                 }
                 VarType::Char(c) => {
                     const_item
                         .build(aster::AstBuilder::new().expr().lit().byte(c))
                         .build(ty)
                 }
@@ -506,47 +529,47 @@ impl CodeGenerator for Var {
             result.push(item);
         }
     }
 }
 
 impl CodeGenerator for Type {
     type Extra = Item;
 
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   item: &Item) {
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        item: &Item,
+    ) {
         debug!("<Type as CodeGenerator>::codegen: item = {:?}", item);
         debug_assert!(item.is_enabled_for_codegen(ctx));
 
         match *self.kind() {
             TypeKind::Void |
             TypeKind::NullPtr |
             TypeKind::Int(..) |
             TypeKind::Float(..) |
             TypeKind::Complex(..) |
             TypeKind::Array(..) |
             TypeKind::Pointer(..) |
             TypeKind::BlockPointer |
             TypeKind::Reference(..) |
             TypeKind::Function(..) |
             TypeKind::ResolvedTypeRef(..) |
             TypeKind::Opaque |
-            TypeKind::Named => {
+            TypeKind::TypeParam => {
                 // These items don't need code generation, they only need to be
                 // converted to rust types in fields, arguments, and such.
                 return;
             }
             TypeKind::TemplateInstantiation(ref inst) => {
                 inst.codegen(ctx, result, item)
             }
-            TypeKind::Comp(ref ci) => {
-                ci.codegen(ctx, result, item)
-            }
+            TypeKind::Comp(ref ci) => ci.codegen(ctx, result, item),
             TypeKind::TemplateAlias(inner, _) |
             TypeKind::Alias(inner) => {
                 let inner_item = ctx.resolve_item(inner);
                 let name = item.canonical_name(ctx);
 
                 // Try to catch the common pattern:
                 //
                 // typedef struct foo { ... } foo;
@@ -567,101 +590,110 @@ impl CodeGenerator for Type {
                 let mut used_template_params = item.used_template_params(ctx);
                 let inner_rust_type = if item.is_opaque(ctx, &()) {
                     used_template_params = None;
                     self.to_opaque(ctx, item)
                 } else {
                     // Its possible that we have better layout information than
                     // the inner type does, so fall back to an opaque blob based
                     // on our layout if converting the inner item fails.
-                    inner_item.try_to_rust_ty_or_opaque(ctx, &())
+                    inner_item
+                        .try_to_rust_ty_or_opaque(ctx, &())
                         .unwrap_or_else(|_| self.to_opaque(ctx, item))
                 };
 
                 {
                     // FIXME(emilio): This is a workaround to avoid generating
                     // incorrect type aliases because of types that we haven't
                     // been able to resolve (because, eg, they depend on a
                     // template parameter).
                     //
                     // It's kind of a shame not generating them even when they
                     // could be referenced, but we already do the same for items
                     // with invalid template parameters, and at least this way
                     // they can be replaced, instead of generating plain invalid
                     // code.
-                    let inner_canon_type = inner_item.expect_type()
-                        .canonical_type(ctx);
-                    if inner_canon_type.is_invalid_named_type() {
-                        warn!("Item contained invalid named type, skipping: \
-                              {:?}, {:?}",
-                              item,
-                              inner_item);
+                    let inner_canon_type =
+                        inner_item.expect_type().canonical_type(ctx);
+                    if inner_canon_type.is_invalid_type_param() {
+                        warn!(
+                            "Item contained invalid named type, skipping: \
+                             {:?}, {:?}",
+                            item,
+                            inner_item
+                        );
                         return;
                     }
                 }
 
                 let rust_name = ctx.rust_ident(&name);
                 let mut typedef = aster::AstBuilder::new().item().pub_();
 
                 if let Some(comment) = item.comment(ctx) {
                     typedef = typedef.with_attr(attributes::doc(comment));
                 }
 
                 // We prefer using `pub use` over `pub type` because of:
                 // https://github.com/rust-lang/rust/issues/26264
                 let simple_enum_path = match inner_rust_type.node {
                     ast::TyKind::Path(None, ref p) => {
                         if used_template_params.is_none() &&
-                           inner_item.expect_type()
-                            .canonical_type(ctx)
-                            .is_enum() &&
-                           p.segments.iter().all(|p| p.parameters.is_none()) {
+                            inner_item
+                                .expect_type()
+                                .canonical_type(ctx)
+                                .is_enum() &&
+                            p.segments.iter().all(|p| p.parameters.is_none())
+                        {
                             Some(p.clone())
                         } else {
                             None
                         }
                     }
                     _ => None,
                 };
 
                 let typedef = if let Some(mut p) = simple_enum_path {
                     for ident in top_level_path(ctx, item).into_iter().rev() {
-                        p.segments.insert(0,
-                                          ast::PathSegment {
-                                              identifier: ident,
-                                              parameters: None,
-                                          });
+                        p.segments.insert(
+                            0,
+                            ast::PathSegment {
+                                identifier: ident,
+                                parameters: None,
+                            },
+                        );
                     }
                     typedef.use_().build(p).as_(rust_name)
                 } else {
                     let mut generics = typedef.type_(rust_name).generics();
                     if let Some(ref params) = used_template_params {
                         for template_param in params {
-                            if let Some(id) =
-                                template_param.as_template_param(ctx, &()) {
+                            if let Some(id) = template_param
+                                .as_template_param(ctx, &())
+                            {
                                 let template_param = ctx.resolve_type(id);
-                                if template_param.is_invalid_named_type() {
-                                    warn!("Item contained invalid template \
-                                           parameter: {:?}",
-                                          item);
+                                if template_param.is_invalid_type_param() {
+                                    warn!(
+                                        "Item contained invalid template \
+                                         parameter: {:?}",
+                                        item
+                                    );
                                     return;
                                 }
                                 generics =
-                                    generics.ty_param_id(template_param.name()
-                                        .unwrap());
+                                    generics.ty_param_id(
+                                        template_param.name().unwrap(),
+                                    );
                             }
                         }
                     }
                     generics.build().build_ty(inner_rust_type)
                 };
                 result.push(typedef)
             }
-            TypeKind::Enum(ref ei) => {
-                ei.codegen(ctx, result, item)
-            }
+            TypeKind::Enum(ref ei) => ei.codegen(ctx, result, item),
             TypeKind::ObjCId | TypeKind::ObjCSel => {
                 result.saw_objc();
             }
             TypeKind::ObjCInterface(ref interface) => {
                 interface.codegen(ctx, result, item)
             }
             ref u @ TypeKind::UnresolvedTypeRef(..) => {
                 unreachable!("Should have been resolved after parsing {:?}!", u)
@@ -674,35 +706,38 @@ struct Vtable<'a> {
     item_id: ItemId,
     #[allow(dead_code)]
     methods: &'a [Method],
     #[allow(dead_code)]
     base_classes: &'a [Base],
 }
 
 impl<'a> Vtable<'a> {
-    fn new(item_id: ItemId,
-           methods: &'a [Method],
-           base_classes: &'a [Base])
-           -> Self {
+    fn new(
+        item_id: ItemId,
+        methods: &'a [Method],
+        base_classes: &'a [Base],
+    ) -> Self {
         Vtable {
             item_id: item_id,
             methods: methods,
             base_classes: base_classes,
         }
     }
 }
 
 impl<'a> CodeGenerator for Vtable<'a> {
     type Extra = Item;
 
-    fn codegen<'b>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'b>,
-                   item: &Item) {
+    fn codegen<'b>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'b>,
+        item: &Item,
+    ) {
         assert_eq!(item.id(), self.item_id);
         debug_assert!(item.is_enabled_for_codegen(ctx));
 
         // For now, generate an empty struct, later we should generate function
         // pointers and whatnot.
         let attributes = vec![attributes::repr("C")];
 
         let vtable = aster::AstBuilder::new()
@@ -721,57 +756,62 @@ impl<'a> ItemCanonicalName for Vtable<'a
     fn canonical_name(&self, ctx: &BindgenContext) -> String {
         format!("{}__bindgen_vtable", self.item_id.canonical_name(ctx))
     }
 }
 
 impl<'a> TryToRustTy for Vtable<'a> {
     type Extra = ();
 
-    fn try_to_rust_ty(&self,
-                      ctx: &BindgenContext,
-                      _: &()) -> error::Result<P<ast::Ty>> {
+    fn try_to_rust_ty(
+        &self,
+        ctx: &BindgenContext,
+        _: &(),
+    ) -> error::Result<P<ast::Ty>> {
         Ok(aster::ty::TyBuilder::new().id(self.canonical_name(ctx)))
     }
 }
 
 impl CodeGenerator for TemplateInstantiation {
     type Extra = Item;
 
-    fn codegen<'a>(&self,
-                   ctx: &BindgenContext,
-                   result: &mut CodegenResult<'a>,
-                   item: &Item) {
+    fn codegen<'a>(
+        &self,
+        ctx: &BindgenContext,
+        result: &mut CodegenResult<'a>,
+        item: &Item,
+    ) {
         debug_assert!(item.is_enabled_for_codegen(ctx));
 
         // Although uses of instantiations don't need code generation, and are
         // just converted to rust types in fields, vars, etc, we take this
         // opportunity to generate tests for their layout here. If the
         // instantiation is opaque, then its presumably because we don't
         // properly understand it (maybe because of specializations), and so we
         // shouldn't emit layout tests either.
         if !ctx.options().layout_tests || self.is_opaque(ctx, item) {
-            return
+            return;
         }
 
         // If there are any unbound type parameters, then we can't generate a
         // layout test because we aren't dealing with a concrete type with a
         // concrete size and alignment.
         if ctx.uses_any_template_parameters(item.id()) {
             return;
         }
 
         let layout = item.kind().expect_type().layout(ctx);
 
         if let Some(layout) = layout {
             let size = layout.size;
             let align = layout.align;
 
             let name = item.full_disambiguated_name(ctx);
-            let mut fn_name = format!("__bindgen_test_layout_{}_instantiation", name);
+            let mut fn_name =
+                format!("__bindgen_test_layout_{}_instantiation", name);
             let times_seen = result.overload_number(&fn_name);
             if times_seen > 0 {
                 write!(&mut fn_name, "_{}", times_seen).unwrap();
             }
 
             let fn_name = ctx.rust_ident_raw(&fn_name);
 
             let prefix = ctx.trait_prefix();
@@ -786,18 +826,17 @@ impl CodeGenerator for TemplateInstantia
                 #[test]
                 fn $fn_name() {
                     assert_eq!($size_of_expr, $size,
                                concat!("Size of template specialization: ",
                                        stringify!($ident)));
                     assert_eq!($align_of_expr, $align,
                                concat!("Alignment of template specialization: ",
                                        stringify!($ident)));
-                })
-                .unwrap();
+                }).unwrap();
 
             result.push(item);
         }
     }
 }
 
 /// Generates an infinite number of anonymous field names.
 struct AnonFieldNames(usize);
@@ -816,173 +855,182 @@ impl Iterator for AnonFieldNames {
         Some(format!("__bindgen_anon_{}", self.0))
     }
 }
 
 /// Trait for implementing the code generation of a struct or union field.
 trait FieldCodegen<'a> {
     type Extra;
 
-    fn codegen<F, M>(&self,
-                     ctx: &BindgenContext,
-                     fields_should_be_private: bool,
-                     codegen_depth: usize,
-                     accessor_kind: FieldAccessorKind,
-                     parent: &CompInfo,
-                     anon_field_names: &mut AnonFieldNames,
-                     result: &mut CodegenResult,
-                     struct_layout: &mut StructLayoutTracker,
-                     fields: &mut F,
-                     methods: &mut M,
-                     extra: Self::Extra)
-        where F: Extend<ast::StructField>,
-              M: Extend<ast::ImplItem>;
+    fn codegen<F, M>(
+        &self,
+        ctx: &BindgenContext,
+        fields_should_be_private: bool,
+        codegen_depth: usize,
+        accessor_kind: FieldAccessorKind,
+        parent: &CompInfo,
+        anon_field_names: &mut AnonFieldNames,
+        result: &mut CodegenResult,
+        struct_layout: &mut StructLayoutTracker,
+        fields: &mut F,
+        methods: &mut M,
+        extra: Self::Extra,
+    ) where
+        F: Extend<ast::StructField>,
+        M: Extend<ast::ImplItem>;
 }
 
 impl<'a> FieldCodegen<'a> for Field {
     type Extra = ();
 
-    fn codegen<F, M>(&self,
-                     ctx: &BindgenContext,
-                     fields_should_be_private: bool,
-                     codegen_depth: usize,
-                     accessor_kind: FieldAccessorKind,
-                     parent: &CompInfo,
-                     anon_field_names: &mut AnonFieldNames,
-                     result: &mut CodegenResult,
-                     struct_layout: &mut StructLayoutTracker,
-                     fields: &mut F,
-                     methods: &mut M,
-                     _: ())
-        where F: Extend<ast::StructField>,
-              M: Extend<ast::ImplItem>
+    fn codegen<F, M>(
+        &self,
+        ctx: &BindgenContext,
+        fields_should_be_private: bool,
+        codegen_depth: usize,
+        accessor_kind: FieldAccessorKind,
+        parent: &CompInfo,
+        anon_field_names: &mut AnonFieldNames,
+        result: &mut CodegenResult,
+        struct_layout: &mut StructLayoutTracker,
+        fields: &mut F,
+        methods: &mut M,
+        _: (),
+    ) where
+        F: Extend<ast::StructField>,
+        M: Extend<ast::ImplItem>,
     {
         match *self {
             Field::DataMember(ref data) => {
-                data.codegen(ctx,
-                             fields_should_be_private,
-                             codegen_depth,
-                             accessor_kind,
-                             parent,
-                             anon_field_names,
-                             result,
-                             struct_layout,
-                             fields,
-                             methods,
-                             ());
+                data.codegen(
+                    ctx,
+                    fields_should_be_private,
+                    codegen_depth,
+                    accessor_kind,
+                    parent,
+                    anon_field_names,
+                    result,
+                    struct_layout,
+                    fields,
+                    methods,
+                    (),
+                );
             }
             Field::Bitfields(ref unit) => {
-                unit.codegen(ctx,
-                             fields_should_be_private,
-                             codegen_depth,
-                             accessor_kind,
-                             parent,
-                             anon_field_names,
-                             result,
-                             struct_layout,
-                             fields,
-                             methods,
-                             ());
+                unit.codegen(
+                    ctx,
+                    fields_should_be_private,
+                    codegen_depth,
+                    accessor_kind,
+                    parent,
+                    anon_field_names,
+                    result,
+                    struct_layout,
+                    fields,
+                    methods,
+                    (),
+                );
             }
         }
     }
 }
 
 impl<'a> FieldCodegen<'a> for FieldData {
     type Extra = ();
 
-    fn codegen<F, M>(&self,
-                     ctx: &BindgenContext,
-                     fields_should_be_private: bool,
-                     codegen_depth: usize,
-                     accessor_kind: FieldAccessorKind,
-                     parent: &CompInfo,
-                     anon_field_names: &mut AnonFieldNames,