Repository: bytecodealliance/wasm-tools
Pull request #1550 (2024-05-10 20:14:37)

Remove a special cased error message in roundtrip tests
Use the features on `BinaryReader` to dictate what the valid flags are for a global.


Patch:
diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index a22a19de..6090cd8f 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -40,7 +40,7 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - run: rustup update stable --no-self-update && rustup default stable
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
     - uses: bytecodealliance/wasmtime/.github/actions/binary-compatible-builds@v20.0.0
       with:
         name: ${{ matrix.build }}
@@ -56,34 +56,42 @@ jobs:
         name: bins-${{ matrix.build }}
         path: dist
 
+  test-no-hash-maps:
+    name: Test (no-hash-maps)
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v4
+        with:
+          submodules: true
+      - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
+      - name: Test (no-hash-maps)
+        run: cargo test --workspace --locked --features no-hash-maps
+
   test:
     name: Test
     runs-on: ${{ matrix.os }}
     strategy:
       matrix:
-        build: [stable, beta, nightly, macos, windows]
         include:
-          - build: stable
-            os: ubuntu-latest
-            rust: stable
-          - build: beta
-            os: ubuntu-latest
+          - os: ubuntu-latest
+            rust: default
+          - os: ubuntu-latest
             rust: beta
-          - build: nightly
-            os: ubuntu-latest
+          - os: ubuntu-latest
             rust: nightly
-          - build: macos
-            os: macos-latest
-            rust: stable
-          - build: windows
-            os: windows-latest
-            rust: stable
+          - os: macos-latest
+            rust: default
+          - os: windows-latest
+            rust: default
+          - os: ubuntu-latest
+            rust: msrv
     steps:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - name: Install Rust (rustup)
-      run: rustup update ${{ matrix.rust }} --no-self-update && rustup default ${{ matrix.rust }}
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
+      with:
+        toolchain: ${{ matrix.rust }}
     - run: cargo test --locked --all
 
   test_extra_features:
@@ -93,7 +101,7 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - run: rustup update stable --no-self-update && rustup default stable
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
     - run: cargo test --locked -p wasmparser --benches
     - run: cargo test --locked -p wasm-encoder --all-features
     - run: cargo test -p wasm-smith --features wasmparser
@@ -111,7 +119,7 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - run: rustup update stable --no-self-update && rustup default stable
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
     - run: cmake -S examples -B examples/build -DCMAKE_BUILD_TYPE=Release
     - run: cmake --build examples/build --config Release
 
@@ -122,13 +130,13 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - name: Install Rust (rustup)
-      run: rustup update 1.77.0 --no-self-update && rustup default 1.77.0
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
+      with:
+        toolchain: 1.77.0
     - run: |
         curl -LO https://github.com/WebAssembly/wasi-sdk/releases/download/wasi-sdk-21/wasi-sdk-21.0-linux.tar.gz
         tar xf wasi-sdk-21.0-linux.tar.gz
         export WASI_SDK_PATH=$(pwd)/wasi-sdk-21.0
-        rustup target add wasm32-wasi
         cd crates/wit-component/dl && bash check.sh
 
   wasm:
@@ -138,9 +146,7 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - name: Install Rust
-      run: rustup update stable --no-self-update && rustup default stable
-    - run: rustup target add wasm32-wasi
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
     - run: |
         tag=v10.0.1
         curl -LO https://github.com/bytecodealliance/wasmtime/releases/download/${tag}/wasmtime-${tag}-x86_64-linux.tar.xz
@@ -160,8 +166,8 @@ jobs:
     runs-on: ubuntu-latest
     steps:
     - uses: actions/checkout@v4
-    - name: Install Rust
-      run: rustup update stable && rustup default stable && rustup component add rustfmt
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
+    - run: rustup component add rustfmt
     # Note that this doesn't use `cargo fmt` because that doesn't format
     # modules-defined-in-macros which is in use in `wast` for example. This is
     # the best alternative I can come up with at this time
@@ -174,8 +180,9 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - name: Install Rust
-      run: rustup update nightly && rustup default nightly
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
+      with:
+        toolchain: nightly
     - run: cargo install cargo-fuzz
     - run: cargo fuzz build --dev -s none
     - run: cargo fuzz build --dev --features wasmtime -s none
@@ -184,6 +191,7 @@ jobs:
     runs-on: ubuntu-latest
     steps:
       - uses: actions/checkout@v4
+      - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
       - run: rustup target add x86_64-unknown-none
       - run: cargo check --benches -p wasm-smith
       - run: cargo check --no-default-features
@@ -234,7 +242,7 @@ jobs:
     - uses: actions/checkout@v4
       with:
         submodules: true
-    - run: rustup update stable && rustup default stable
+    - uses: bytecodealliance/wasmtime/.github/actions/install-rust@v20.0.0
     - run: rustc ci/publish.rs
     # Make sure the tree is publish-able as-is
     - run: ./publish verify
diff --git a/Cargo.toml b/Cargo.toml
index d96f6d2d..cca0f3ca 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,6 +11,7 @@ keywords = ["webassembly", "wasm"]
 repository = "https://github.com/bytecodealliance/wasm-tools"
 readme = "README.md"
 exclude = ['tests/wabt', 'tests/testsuite', 'tests/snapshots', 'ci']
+rust-version.workspace = true
 
 [lints]
 workspace = true
@@ -34,6 +35,9 @@ all = "allow"
 [workspace.package]
 edition = '2021'
 version = "0.207.0"
+# Current policy for wasm-tools is the same as Wasmtime which is that this
+# number can be no larger than the current stable release of Rust minus 2.
+rust-version = "1.76.0"
 
 [workspace.dependencies]
 anyhow = "1.0.58"
diff --git a/crates/c-api/Cargo.toml b/crates/c-api/Cargo.toml
index c993d4a0..93e04c56 100644
--- a/crates/c-api/Cargo.toml
+++ b/crates/c-api/Cargo.toml
@@ -8,6 +8,7 @@ license = "Apache-2.0 WITH LLVM-exception"
 readme = "./README.md"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/c-api"
 publish = false
+rust-version.workspace = true
 
 [lib]
 name = "wasmtools"
diff --git a/crates/fuzz-stats/Cargo.toml b/crates/fuzz-stats/Cargo.toml
index 78048b53..10f8848f 100644
--- a/crates/fuzz-stats/Cargo.toml
+++ b/crates/fuzz-stats/Cargo.toml
@@ -2,6 +2,7 @@
 name = "fuzz-stats"
 edition.workspace = true
 publish = false
+rust-version.workspace = true
 
 [dependencies]
 anyhow = { workspace = true }
diff --git a/crates/wasm-compose/Cargo.toml b/crates/wasm-compose/Cargo.toml
index 5b9db593..92d2889b 100644
--- a/crates/wasm-compose/Cargo.toml
+++ b/crates/wasm-compose/Cargo.toml
@@ -9,6 +9,7 @@ repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wa
 homepage = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-compose"
 documentation = "https://docs.rs/wasm-compose"
 description = "A library for composing WebAssembly components."
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-compose/example/middleware/Cargo.toml b/crates/wasm-compose/example/middleware/Cargo.toml
index b3f4ca7f..a8270bea 100644
--- a/crates/wasm-compose/example/middleware/Cargo.toml
+++ b/crates/wasm-compose/example/middleware/Cargo.toml
@@ -3,6 +3,7 @@ name = "middleware"
 version = "0.1.0"
 edition = "2021"
 publish = false
+rust-version.workspace = true
 
 [dependencies]
 flate2 = "1.0.24"
diff --git a/crates/wasm-compose/example/server/Cargo.toml b/crates/wasm-compose/example/server/Cargo.toml
index bcb474c1..10ab9b3d 100644
--- a/crates/wasm-compose/example/server/Cargo.toml
+++ b/crates/wasm-compose/example/server/Cargo.toml
@@ -3,6 +3,7 @@ name = "host"
 version = "0.1.0"
 edition = "2021"
 publish = false
+rust-version.workspace = true
 
 [dependencies]
 async-std = { version = "1.12.0", features = ["attributes"] }
diff --git a/crates/wasm-compose/example/service/Cargo.toml b/crates/wasm-compose/example/service/Cargo.toml
index 1abc5d3d..e1ace4ad 100644
--- a/crates/wasm-compose/example/service/Cargo.toml
+++ b/crates/wasm-compose/example/service/Cargo.toml
@@ -3,6 +3,7 @@ name = "svc"
 version = "0.1.0"
 edition = "2021"
 publish = false
+rust-version.workspace = true
 
 [dependencies]
 cargo-component-bindings = "0.6.0"
diff --git a/crates/wasm-compose/src/encoding.rs b/crates/wasm-compose/src/encoding.rs
index 39dd232f..daa2bd98 100644
--- a/crates/wasm-compose/src/encoding.rs
+++ b/crates/wasm-compose/src/encoding.rs
@@ -730,7 +730,10 @@ impl<'a> TypeEncoder<'a> {
         index
     }
 
-    fn flags(encodable: &mut Encodable, names: &wasmparser::map::IndexSet<KebabString>) -> u32 {
+    fn flags(
+        encodable: &mut Encodable,
+        names: &wasmparser::collections::IndexSet<KebabString>,
+    ) -> u32 {
         let index = encodable.type_count();
         encodable
             .ty()
@@ -739,7 +742,10 @@ impl<'a> TypeEncoder<'a> {
         index
     }
 
-    fn enum_type(encodable: &mut Encodable, cases: &wasmparser::map::IndexSet<KebabString>) -> u32 {
+    fn enum_type(
+        encodable: &mut Encodable,
+        cases: &wasmparser::collections::IndexSet<KebabString>,
+    ) -> u32 {
         let index = encodable.type_count();
         encodable
             .ty()
diff --git a/crates/wasm-encoder/Cargo.toml b/crates/wasm-encoder/Cargo.toml
index b936e01b..6a7478df 100644
--- a/crates/wasm-encoder/Cargo.toml
+++ b/crates/wasm-encoder/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wasm-encoder"
 description = """
 A low-level WebAssembly encoder.
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-metadata/Cargo.toml b/crates/wasm-metadata/Cargo.toml
index 0bccc0b1..354d6e48 100644
--- a/crates/wasm-metadata/Cargo.toml
+++ b/crates/wasm-metadata/Cargo.toml
@@ -5,6 +5,7 @@ edition.workspace = true
 license = "Apache-2.0 WITH LLVM-exception"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-metadata"
 description = "Read and manipulate WebAssembly metadata"
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-mutate-stats/Cargo.toml b/crates/wasm-mutate-stats/Cargo.toml
index d8513543..04db6f09 100644
--- a/crates/wasm-mutate-stats/Cargo.toml
+++ b/crates/wasm-mutate-stats/Cargo.toml
@@ -2,6 +2,7 @@
 name = "wasm-mutate-stats"
 edition.workspace = true
 publish = false
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-mutate/Cargo.toml b/crates/wasm-mutate/Cargo.toml
index c7f15418..6a96c9ed 100644
--- a/crates/wasm-mutate/Cargo.toml
+++ b/crates/wasm-mutate/Cargo.toml
@@ -5,6 +5,7 @@ edition.workspace = true
 license = "Apache-2.0 WITH LLVM-exception"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-mutate"
 description = "A WebAssembly test case mutator"
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-shrink/Cargo.toml b/crates/wasm-shrink/Cargo.toml
index ee4a3b6e..fbf9283f 100644
--- a/crates/wasm-shrink/Cargo.toml
+++ b/crates/wasm-shrink/Cargo.toml
@@ -9,6 +9,7 @@ readme = "./README.md"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-shrink"
 name = "wasm-shrink"
 version.workspace = true
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wasm-smith/Cargo.toml b/crates/wasm-smith/Cargo.toml
index 4ce621a9..16e4810d 100644
--- a/crates/wasm-smith/Cargo.toml
+++ b/crates/wasm-smith/Cargo.toml
@@ -10,6 +10,7 @@ readme = "./README.md"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wasm-smith"
 version.workspace = true
 exclude = ["/benches/corpus"]
+rust-version.workspace = true
 
 [[bench]]
 name = "corpus"
diff --git a/crates/wasmparser/Cargo.toml b/crates/wasmparser/Cargo.toml
index 8b22640e..b08f47c0 100644
--- a/crates/wasmparser/Cargo.toml
+++ b/crates/wasmparser/Cargo.toml
@@ -11,6 +11,7 @@ A simple event-driven library for parsing WebAssembly binary files.
 """
 edition.workspace = true
 exclude = ["benches/*.wasm"]
+rust-version.workspace = true
 
 [lints]
 workspace = true
@@ -45,6 +46,12 @@ default = ['std', 'validate']
 # library's source of randomness for seeding hash maps.
 std = ['indexmap/std']
 
+# Tells the wasmparser crate to avoid using hash based maps and sets.
+#
+# Some embedded environments cannot provide a random source which is required
+# to properly initialize hashmap based data structures for resilience against
+# malious actors that control their inputs.
+no-hash-maps = []
 # A feature that enables validating WebAssembly files. This is enabled by
 # default but not required if you're only parsing a file, for example, as
 # opposed to validating all of its contents.
diff --git a/crates/wasmparser/src/map.rs b/crates/wasmparser/src/collections/hash.rs
similarity index 78%
rename from crates/wasmparser/src/map.rs
rename to crates/wasmparser/src/collections/hash.rs
index fc3049d8..8ec388d4 100644
--- a/crates/wasmparser/src/map.rs
+++ b/crates/wasmparser/src/collections/hash.rs
@@ -1,24 +1,7 @@
-//! Type aliases for maps used by `wasmparser`
-//!
-//! This module contains type aliases used for [`HashMap`], [`HashSet`],
-//! [`IndexMap`], and [`IndexSet`]. Note that these differ from upstream types
-//! in the `indexmap` crate and the standard library due to customization of the
-//! hash algorithm type parameter.
+//! Utilities for hashmap initialization based on random sources.
 
 use core::hash::{BuildHasher, Hasher};
 
-/// Wasmparser-specific type alias for an ordered map.
-pub type IndexMap<K, V> = indexmap::IndexMap<K, V, RandomState>;
-
-/// Wasmparser-specific type alias for an ordered set.
-pub type IndexSet<K> = indexmap::IndexSet<K, RandomState>;
-
-/// Wasmparser-specific type alias for hash map.
-pub type HashMap<K, V> = hashbrown::HashMap<K, V, RandomState>;
-
-/// Wasmparser-specific type alias for hash set.
-pub type HashSet<K> = hashbrown::HashSet<K, RandomState>;
-
 /// Wasmparser's hashing state stored per-map.
 ///
 /// This is DoS-resistant when the `std` feature is activated and still somewhat
diff --git a/crates/wasmparser/src/collections/index_map.rs b/crates/wasmparser/src/collections/index_map.rs
new file mode 100644
index 00000000..8a25f6ba
--- /dev/null
+++ b/crates/wasmparser/src/collections/index_map.rs
@@ -0,0 +1,549 @@
+//! Type definitions for an ordered map.
+
+use core::borrow::Borrow;
+use core::hash::Hash;
+use core::iter::FusedIterator;
+use core::ops::Index;
+
+mod detail;
+
+#[cfg(test)]
+mod tests;
+
+/// A hash table where the iteration order of the key-value pairs is independent of the hash values of the keys.
+///
+/// Provides an API compatible with both [`IndexMap`] and a custom implementation based on [`BTreeMap`].
+///
+/// [`IndexMap`]: indexmap::IndexMap
+/// [`BTreeMap`]: alloc::collections::BTreeMap
+#[derive(Debug, Clone)]
+pub struct IndexMap<K, V> {
+    inner: detail::IndexMapImpl<K, V>,
+}
+
+impl<K, V> Default for IndexMap<K, V> {
+    fn default() -> Self {
+        Self {
+            inner: detail::IndexMapImpl::default(),
+        }
+    }
+}
+
+impl<K, V> IndexMap<K, V> {
+    /// Clears the [`IndexMap`], removing all elements.
+    pub fn clear(&mut self) {
+        self.inner.clear()
+    }
+
+    /// Returns the number of elements in the [`IndexMap`].
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Returns `true` if the [`IndexMap`] contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    /// Returns an iterator that yields the items in the [`IndexMap`].
+    pub fn iter(&self) -> Iter<'_, K, V> {
+        Iter {
+            inner: self.inner.iter(),
+        }
+    }
+
+    /// Returns an iterator that yields the mutable items in the [`IndexMap`].
+    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
+        IterMut {
+            inner: self.inner.iter_mut(),
+        }
+    }
+
+    /// Returns an iterator that yields the keys in the [`IndexMap`].
+    pub fn keys(&self) -> Keys<'_, K, V> {
+        Keys {
+            inner: self.inner.keys(),
+        }
+    }
+
+    /// Returns an iterator that yields the values in the [`IndexMap`].
+    pub fn values(&self) -> Values<'_, K, V> {
+        Values {
+            inner: self.inner.values(),
+        }
+    }
+
+    /// Returns a mutable iterator that yields the values in the [`IndexMap`].
+    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
+        ValuesMut {
+            inner: self.inner.values_mut(),
+        }
+    }
+
+    /// Returns the key-value entry at the given `index` if any.
+    pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
+        self.inner.get_index(index)
+    }
+
+    /// Returns the mutable key-value entry at the given `index` if any.
+    pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
+        self.inner.get_index_mut(index)
+    }
+}
+
+impl<K, V> IndexMap<K, V>
+where
+    K: Hash + Eq + Ord + Clone,
+{
+    /// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexMap`].
+    pub fn reserve(&mut self, additional: usize) {
+        #[cfg(not(feature = "no-hash-maps"))]
+        self.inner.reserve(additional);
+        #[cfg(feature = "no-hash-maps")]
+        let _ = additional;
+    }
+
+    /// Returns true if `key` is contains in the [`IndexMap`].
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.contains_key(key)
+    }
+
+    /// Returns a reference to the value corresponding to the `key`.
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.get(key)
+    }
+
+    /// Return references to the key-value pair stored for `key`,
+    /// if it is present, else `None`.
+    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.get_key_value(key)
+    }
+
+    /// Returns the key-value pair corresponding to the supplied key
+    /// as well as the unique index of the returned key-value pair.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type,
+    /// but the ordering on the borrowed form *must* match the ordering
+    /// on the key type.
+    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
+    where
+        K: Borrow<Q> + Ord,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.get_full(key)
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.get_mut(key)
+    }
+
+    /// Inserts a key-value pair into the [`IndexMap`].
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical.
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
+        self.inner.insert(key, value)
+    }
+
+    /// Remove the key-value pair equivalent to `key` and return its value.
+    ///
+    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
+    /// last element of the map and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `None` if `key` is not in map.
+    ///
+    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
+    pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.swap_remove(key)
+    }
+
+    /// Remove and return the key-value pair equivalent to `key`.
+    ///
+    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
+    /// last element of the map and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `None` if `key` is not in map.
+    ///
+    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
+    pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.swap_remove_entry(key)
+    }
+
+    /// Gets the given key's corresponding entry in the [`IndexMap`] for in-place manipulation.
+    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+        match self.inner.entry(key) {
+            detail::EntryImpl::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
+            detail::EntryImpl::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
+        }
+    }
+}
+
+impl<K, Q, V> Index<&Q> for IndexMap<K, V>
+where
+    K: Borrow<Q> + Hash + Eq + Ord,
+    Q: ?Sized + Hash + Eq + Ord,
+{
+    type Output = V;
+
+    fn index(&self, key: &Q) -> &V {
+        &self.inner[key]
+    }
+}
+
+impl<K, V> Index<usize> for IndexMap<K, V>
+where
+    K: Hash + Eq + Ord,
+{
+    type Output = V;
+
+    fn index(&self, key: usize) -> &V {
+        &self.inner[key]
+    }
+}
+
+impl<K, V> Extend<(K, V)> for IndexMap<K, V>
+where
+    K: Eq + Hash + Ord + Clone,
+{
+    fn extend<Iter: IntoIterator<Item = (K, V)>>(&mut self, iter: Iter) {
+        self.inner.extend(iter)
+    }
+}
+
+/// A view into a single entry in a [`IndexMap`], which may either be vacant or occupied.
+///
+/// This enum is constructed from the entry method on [`IndexMap`].
+#[derive(Debug)]
+pub enum Entry<'a, K: Ord, V> {
+    /// An occupied entry.
+    Occupied(OccupiedEntry<'a, K, V>),
+    /// A vacant entry.
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Hash + Eq + Ord + Clone,
+{
+    /// Returns a reference to this entry's key.
+    pub fn key(&self) -> &K {
+        match *self {
+            Self::Occupied(ref entry) => entry.key(),
+            Self::Vacant(ref entry) => entry.key(),
+        }
+    }
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Hash + Eq + Ord + Clone,
+    V: Default,
+{
+    /// Ensures a value is in the entry by inserting the default value if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_default(self) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(Default::default()),
+        }
+    }
+}
+
+/// A view into an occupied entry in a [`IndexMap`].
+///
+/// It is part of the [`Entry`] enum.
+#[derive(Debug)]
+pub struct OccupiedEntry<'a, K: Ord, V> {
+    inner: detail::OccupiedEntryImpl<'a, K, V>,
+}
+
+impl<'a, K: 'a, V: 'a> OccupiedEntry<'a, K, V>
+where
+    K: Ord + Clone,
+{
+    /// Gets a reference to the key in the entry.
+    pub fn key(&self) -> &K {
+        self.inner.key()
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V {
+        self.inner.get()
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    pub fn get_mut(&mut self) -> &mut V {
+        self.inner.get_mut()
+    }
+
+    /// Sets the value of the entry with the [`OccupiedEntry`]'s key, and returns the entry's old value.
+    pub fn insert(&mut self, value: V) -> V {
+        self.inner.insert(value)
+    }
+
+    /// Converts the [`OccupiedEntry`] into a mutable reference to the value in the entry
+    /// with a lifetime bound to the map itself.
+    pub fn into_mut(self) -> &'a mut V {
+        self.inner.into_mut()
+    }
+}
+
+/// A view into a vacant entry in a [`IndexMap`].
+///
+/// It is part of the [`Entry`] enum.
+#[derive(Debug)]
+pub struct VacantEntry<'a, K: Ord, V> {
+    inner: detail::VacantEntryImpl<'a, K, V>,
+}
+
+impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V>
+where
+    K: Ord + Clone,
+{
+    /// Gets a reference to the key in the entry.
+    pub fn key(&self) -> &K {
+        self.inner.key()
+    }
+
+    /// Take ownership of the key.
+    pub fn into_key(self) -> K {
+        self.inner.into_key()
+    }
+
+    /// Sets the value of the entry with the [`VacantEntry`]'s key, and returns a mutable reference to it.
+    pub fn insert(self, value: V) -> &'a mut V
+    where
+        K: Hash,
+    {
+        self.inner.insert(value)
+    }
+}
+
+impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
+where
+    K: Hash + Ord + Eq + Clone,
+{
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = (K, V)>,
+    {
+        Self {
+            inner: <detail::IndexMapImpl<K, V>>::from_iter(iter),
+        }
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
+    type Item = (&'a K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+/// An iterator over the items of a [`IndexMap`].
+#[derive(Debug, Clone)]
+pub struct Iter<'a, K, V> {
+    inner: detail::IterImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
+
+impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
+    type Item = (&'a K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+/// An iterator over the mutable items of a [`IndexMap`].
+#[derive(Debug)]
+pub struct IterMut<'a, K, V> {
+    inner: detail::IterMutImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
+
+impl<K, V> IntoIterator for IndexMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            inner: self.inner.into_iter(),
+        }
+    }
+}
+
+/// An iterator over the owned items of an [`IndexMap`].
+#[derive(Debug)]
+pub struct IntoIter<K, V> {
+    inner: detail::IntoIterImpl<K, V>,
+}
+
+impl<'a, K, V> Iterator for IntoIter<K, V> {
+    type Item = (K, V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for IntoIter<K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for IntoIter<K, V> {}
+
+/// An iterator over the keys of a [`IndexMap`].
+#[derive(Debug, Clone)]
+pub struct Keys<'a, K, V> {
+    inner: detail::KeysImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
+
+/// An iterator over the values of a [`IndexMap`].
+#[derive(Debug, Clone)]
+pub struct Values<'a, K, V> {
+    inner: detail::ValuesImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
+
+/// An mutable iterator over the values of a [`IndexMap`].
+#[derive(Debug)]
+pub struct ValuesMut<'a, K, V> {
+    inner: detail::ValuesMutImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+    type Item = &'a mut V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
diff --git a/crates/wasmparser/src/collections/index_map/detail.rs b/crates/wasmparser/src/collections/index_map/detail.rs
new file mode 100644
index 00000000..402fbdd8
--- /dev/null
+++ b/crates/wasmparser/src/collections/index_map/detail.rs
@@ -0,0 +1,1024 @@
+//! An ordered map based on a B-Tree that keeps insertion order of elements.
+
+#[cfg(not(feature = "no-hash-maps"))]
+mod impls {
+    use crate::collections::hash;
+    use indexmap::IndexMap;
+
+    pub type IndexMapImpl<K, V> = IndexMap<K, V, hash::RandomState>;
+    pub type EntryImpl<'a, K, V> = indexmap::map::Entry<'a, K, V>;
+    pub type OccupiedEntryImpl<'a, K, V> = indexmap::map::OccupiedEntry<'a, K, V>;
+    pub type VacantEntryImpl<'a, K, V> = indexmap::map::VacantEntry<'a, K, V>;
+    pub type IterImpl<'a, K, V> = indexmap::map::Iter<'a, K, V>;
+    pub type IterMutImpl<'a, K, V> = indexmap::map::IterMut<'a, K, V>;
+    pub type IntoIterImpl<K, V> = indexmap::map::IntoIter<K, V>;
+    pub type KeysImpl<'a, K, V> = indexmap::map::Keys<'a, K, V>;
+    pub type ValuesImpl<'a, K, V> = indexmap::map::Values<'a, K, V>;
+    pub type ValuesMutImpl<'a, K, V> = indexmap::map::ValuesMut<'a, K, V>;
+}
+
+#[cfg(feature = "no-hash-maps")]
+mod impls {
+    pub type IndexMapImpl<K, V> = super::IndexMap<K, V>;
+    pub type EntryImpl<'a, K, V> = super::Entry<'a, K, V>;
+    pub type OccupiedEntryImpl<'a, K, V> = super::OccupiedEntry<'a, K, V>;
+    pub type VacantEntryImpl<'a, K, V> = super::VacantEntry<'a, K, V>;
+    pub type IterImpl<'a, K, V> = super::Iter<'a, K, V>;
+    pub type IterMutImpl<'a, K, V> = super::IterMut<'a, K, V>;
+    pub type IntoIterImpl<K, V> = super::IntoIter<K, V>;
+    pub type KeysImpl<'a, K, V> = super::Keys<'a, K, V>;
+    pub type ValuesImpl<'a, K, V> = super::Values<'a, K, V>;
+    pub type ValuesMutImpl<'a, K, V> = super::ValuesMut<'a, K, V>;
+}
+
+pub use self::impls::*;
+
+use alloc::collections::{btree_map, BTreeMap};
+use alloc::vec::IntoIter as VecIntoIter;
+use alloc::vec::Vec;
+use core::borrow::Borrow;
+use core::fmt;
+use core::iter::FusedIterator;
+use core::mem::replace;
+use core::ops::{Index, IndexMut};
+use core::slice::Iter as SliceIter;
+use core::slice::IterMut as SliceIterMut;
+
+/// A slot index referencing a slot in an [`IndexMap`].
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct SlotIndex(usize);
+
+impl SlotIndex {
+    /// Returns the raw `usize` index of the [`SlotIndex`].
+    pub fn index(self) -> usize {
+        self.0
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Slot<K, V> {
+    /// The key of the [`Slot`].
+    key: K,
+    /// The value of the [`Slot`].
+    value: V,
+}
+
+impl<K, V> Slot<K, V> {
+    /// Creates a new [`Slot`] from the given `key` and `value`.
+    pub fn new(key: K, value: V) -> Self {
+        Self { key, value }
+    }
+
+    /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
+    pub fn as_pair(&self) -> (&K, &V) {
+        (&self.key, &self.value)
+    }
+
+    /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
+    pub fn as_pair_mut(&mut self) -> (&K, &mut V) {
+        (&self.key, &mut self.value)
+    }
+
+    /// Converts the [`Slot`] into a pair of its `key` and `value`.
+    pub fn into_pair(self) -> (K, V) {
+        (self.key, self.value)
+    }
+
+    /// Returns a shared reference to the key of the [`Slot`].
+    pub fn key(&self) -> &K {
+        &self.key
+    }
+
+    /// Returns a shared reference to the value of the [`Slot`].
+    pub fn value(&self) -> &V {
+        &self.value
+    }
+
+    /// Returns an exclusive reference to the value of the [`Slot`].
+    pub fn value_mut(&mut self) -> &mut V {
+        &mut self.value
+    }
+}
+
+/// A b-tree map where the iteration order of the key-value
+/// pairs is independent of the ordering of the keys.
+///
+/// The interface is closely compatible with the [`indexmap` crate]
+/// and a subset of the features that is relevant for the
+/// [`wasmparser-nostd` crate].
+///
+/// # Differences to original `IndexMap`
+///
+/// Since the goal of this crate was to maintain a simple
+/// `no_std` compatible fork of the [`indexmap` crate] there are some
+/// downsides and differences.
+///
+/// - Some operations such as `IndexMap::insert` now require `K: Clone`.
+/// - It is to be expected that this fork performs worse than the original
+/// [`indexmap` crate] implementation.
+/// - The implementation is based on `BTreeMap` internally instead of
+/// `HashMap` which has the effect that methods no longer require `K: Hash`
+/// but `K: Ord` instead.
+///
+/// [`indexmap` crate]: https://crates.io/crates/indexmap
+/// [`wasmparser-nostd` crate]: https://crates.io/crates/wasmparser-nostd
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+pub struct IndexMap<K, V> {
+    /// A mapping from keys to slot indices.
+    key2slot: BTreeMap<K, SlotIndex>,
+    /// A vector holding all slots of key value pairs.
+    slots: Vec<Slot<K, V>>,
+}
+
+impl<K, V> Default for IndexMap<K, V> {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<K, V> IndexMap<K, V> {
+    /// Makes a new, empty [`IndexMap`].
+    ///
+    /// Does not allocate anything on its own.
+    pub fn new() -> Self {
+        Self {
+            key2slot: BTreeMap::new(),
+            slots: Vec::new(),
+        }
+    }
+
+    /// Constructs a new, empty [`IndexMap`] with at least the specified capacity.
+    ///
+    /// Does not allocate if `capacity` is zero.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            key2slot: BTreeMap::new(),
+            slots: Vec::with_capacity(capacity),
+        }
+    }
+
+    /// Reserve capacity for at least `additional` more key-value pairs.
+    pub fn reserve(&mut self, additional: usize) {
+        self.slots.reserve(additional);
+    }
+
+    /// Returns the number of elements in the map.
+    pub fn len(&self) -> usize {
+        self.slots.len()
+    }
+
+    /// Returns `true` if the map contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Returns true if the map contains a value for the specified key.
+    ///
+    /// The key may be any borrowed form of the map’s key type,
+    /// but the ordering on the borrowed form must match the ordering on the key type.
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
+    where
+        K: Borrow<Q> + Ord,
+        Q: Ord,
+    {
+        self.key2slot.contains_key(key)
+    }
+
+    /// Inserts a key-value pair into the map.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical.
+    pub fn insert(&mut self, key: K, value: V) -> Option<V>
+    where
+        K: Ord + Clone,
+    {
+        self.insert_full(key, value).1
+    }
+
+    /// Inserts a key-value pair into the map.
+    ///
+    /// Returns the unique index to the key-value pair alongside the previous value.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical.
+    pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)
+    where
+        K: Ord + Clone,
+    {
+        match self.key2slot.entry(key.clone()) {
+            btree_map::Entry::Vacant(entry) => {
+                let index = self.slots.len();
+                entry.insert(SlotIndex(index));
+                self.slots.push(Slot::new(key, value));
+                (index, None)
+            }
+            btree_map::Entry::Occupied(entry) => {
+                let index = entry.get().index();
+                let new_slot = Slot::new(key, value);
+                let old_slot = replace(&mut self.slots[index], new_slot);
+                (index, Some(old_slot.value))
+            }
+        }
+    }
+
+    /// Remove the key-value pair equivalent to `key` and return it and
+    /// the index it had.
+    ///
+    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
+    /// last element of the map and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `None` if `key` is not in map.
+    pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
+    where
+        K: Borrow<Q> + Ord,
+        Q: ?Sized + Ord,
+    {
+        self.swap_remove_full(key)
+            .map(|(_index, _key, value)| value)
+    }
+
+    /// Remove and return the key-value pair equivalent to `key`.
+    ///
+    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
+    /// last element of the map and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `None` if `key` is not in map.
+    ///
+    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
+    pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
+    where
+        K: Borrow<Q> + Ord,
+        Q: ?Sized + Ord,
+    {
+        self.swap_remove_full(key)
+            .map(|(_index, key, value)| (key, value))
+    }
+
+    /// Remove the key-value pair equivalent to `key` and return it and
+    /// the index it had.
+    ///
+    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
+    /// last element of the map and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `None` if `key` is not in map.
+    pub fn swap_remove_full<Q>(&mut self, key: &Q) -> Option<(usize, K, V)>
+    where
+        K: Borrow<Q> + Ord,
+        Q: ?Sized + Ord,
+    {
+        let index = self.key2slot.remove(key)?.0;
+        let removed = self.slots.swap_remove(index);
+        if index != self.len() {
+            // If the index was referring the last element
+            // `swap_remove` would not swap any other element
+            // thus adjustments are only needed if this was not the case.
+            let swapped = self.slots[index].key.borrow();
+            let swapped_index = self
+                .key2slot
+                .get_mut(swapped)
+                .expect("the swapped entry's key must be present");
+            *swapped_index = SlotIndex(index);
+        }
+        Some((index, removed.key, removed.value))
+    }
+
+    /// Gets the given key’s corresponding entry in the map for in-place manipulation.
+    pub fn entry(&mut self, key: K) -> Entry<K, V>
+    where
+        K: Ord + Clone,
+    {
+        match self.key2slot.entry(key) {
+            btree_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
+                vacant: entry,
+                slots: &mut self.slots,
+            }),
+            btree_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry {
+                occupied: entry,
+                slots: &mut self.slots,
+            }),
+        }
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map’s key type,
+    /// but the ordering on the borrowed form must match the ordering on the key type.
+    pub fn get<Q>(&self, key: &Q) -> Option<&V>
+    where
+        K: Borrow<Q> + Ord,
+        Q: ?Sized + Ord,
+    {
+        self.key2slot
+            .get(key)
+            .map(|slot| &self.slots[slot.index()].value)
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map’s key type,
+    /// but the ordering on the borrowed form must match the ordering on the key type.
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q> + Ord,
+        Q: Ord,
+    {
+        self.key2slot
+            .get(key)
+            .map(|slot| &mut self.slots[slot.index()].value)
+    }
+
+    /// Returns the key-value pair corresponding to the supplied key.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type,
+    /// but the ordering on the borrowed form *must* match the ordering
+    /// on the key type.
+    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
+    where
+        K: Borrow<Q> + Ord,
+        Q: Ord,
+    {
+        self.key2slot
+            .get_key_value(key)
+            .map(|(key, slot)| (key, &self.slots[slot.index()].value))
+    }
+
+    /// Returns the key-value pair corresponding to the supplied key
+    /// as well as the unique index of the returned key-value pair.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type,
+    /// but the ordering on the borrowed form *must* match the ordering
+    /// on the key type.
+    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
+    where
+        K: Borrow<Q> + Ord,
+        Q: Ord,
+    {
+        self.key2slot.get_key_value(key).map(|(key, slot)| {
+            let index = slot.index();
+            let value = &self.slots[index].value;
+            (index, key, value)
+        })
+    }
+
+    /// Returns the unique index corresponding to the supplied key.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type,
+    /// but the ordering on the borrowed form *must* match the ordering
+    /// on the key type.
+    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
+    where
+        K: Borrow<Q> + Ord,
+        Q: Ord,
+    {
+        self.key2slot.get(key).copied().map(SlotIndex::index)
+    }
+
+    /// Returns a shared reference to the key-value pair at the given index.
+    pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
+        self.slots.get(index).map(Slot::as_pair)
+    }
+
+    /// Returns an exclusive reference to the key-value pair at the given index.
+    pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
+        self.slots.get_mut(index).map(Slot::as_pair_mut)
+    }
+
+    /// Gets an iterator over the entries of the map, sorted by key.
+    pub fn iter(&self) -> Iter<K, V> {
+        Iter {
+            iter: self.slots.iter(),
+        }
+    }
+
+    /// Gets a mutable iterator over the entries of the map, sorted by key.
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        IterMut {
+            iter: self.slots.iter_mut(),
+        }
+    }
+
+    /// Gets an iterator over the values of the map, in order by key.
+    pub fn keys(&self) -> Keys<K, V> {
+        Keys {
+            iter: self.slots.iter(),
+        }
+    }
+
+    /// Gets an iterator over the values of the map, in order by key.
+    pub fn values(&self) -> Values<K, V> {
+        Values {
+            iter: self.slots.iter(),
+        }
+    }
+
+    /// Gets a mutable iterator over the values of the map, in order by key.
+    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
+        ValuesMut {
+            iter: self.slots.iter_mut(),
+        }
+    }
+
+    /// Clears the map, removing all elements.
+    pub fn clear(&mut self) {
+        self.key2slot.clear();
+        self.slots.clear();
+    }
+}
+
+impl<'a, K, Q, V> Index<&'a Q> for IndexMap<K, V>
+where
+    K: Borrow<Q> + Ord,
+    Q: ?Sized + Ord,
+{
+    type Output = V;
+
+    fn index(&self, key: &'a Q) -> &Self::Output {
+        self.get(key).expect("no entry found for key")
+    }
+}
+
+impl<K, V> Index<usize> for IndexMap<K, V> {
+    type Output = V;
+
+    fn index(&self, index: usize) -> &Self::Output {
+        let (_key, value) = self
+            .get_index(index)
+            .expect("IndexMap: index out of bounds");
+        value
+    }
+}
+
+impl<K, V> IndexMut<usize> for IndexMap<K, V> {
+    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
+        let (_key, value) = self
+            .get_index_mut(index)
+            .expect("IndexMap: index out of bounds");
+        value
+    }
+}
+
+impl<'a, K, V> Extend<(&'a K, &'a V)> for IndexMap<K, V>
+where
+    K: Ord + Copy,
+    V: Copy,
+{
+    fn extend<T>(&mut self, iter: T)
+    where
+        T: IntoIterator<Item = (&'a K, &'a V)>,
+    {
+        self.extend(iter.into_iter().map(|(key, value)| (*key, *value)))
+    }
+}
+
+impl<K, V> Extend<(K, V)> for IndexMap<K, V>
+where
+    K: Ord + Clone,
+{
+    fn extend<T>(&mut self, iter: T)
+    where
+        T: IntoIterator<Item = (K, V)>,
+    {
+        iter.into_iter().for_each(move |(k, v)| {
+            self.insert(k, v);
+        });
+    }
+}
+
+impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
+where
+    K: Ord + Clone,
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = (K, V)>,
+    {
+        let mut map = IndexMap::new();
+        map.extend(iter);
+        map
+    }
+}
+
+impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V>
+where
+    K: Ord + Clone,
+{
+    fn from(items: [(K, V); N]) -> Self {
+        items.into_iter().collect()
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
+    type Item = (&'a K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
+    type Item = (&'a K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+impl<K, V> IntoIterator for IndexMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            iter: self.slots.into_iter(),
+        }
+    }
+}
+
+/// An iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`iter`]: IndexMap::iter
+#[derive(Debug, Clone)]
+pub struct Iter<'a, K, V> {
+    iter: SliceIter<'a, Slot<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::as_pair)
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::as_pair)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
+
+/// A mutable iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`iter_mut`]: IndexMap::iter_mut
+#[derive(Debug)]
+pub struct IterMut<'a, K, V> {
+    iter: SliceIterMut<'a, Slot<K, V>>,
+}
+
+impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::as_pair_mut)
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::as_pair_mut)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
+
+/// An owning iterator over the entries of a [`IndexMap`].
+///
+/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
+/// (provided by the [`IntoIterator`] trait). See its documentation for more.
+///
+/// [`into_iter`]: IntoIterator::into_iter
+/// [`IntoIterator`]: core::iter::IntoIterator
+#[derive(Debug)]
+pub struct IntoIter<K, V> {
+    iter: VecIntoIter<Slot<K, V>>,
+}
+
+impl<K, V> Iterator for IntoIter<K, V> {
+    type Item = (K, V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::into_pair)
+    }
+}
+
+impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::into_pair)
+    }
+}
+
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<K, V> FusedIterator for IntoIter<K, V> {}
+
+/// An iterator over the keys of an [`IndexMap`].
+///
+/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`keys`]: IndexMap::keys
+#[derive(Debug, Clone)]
+pub struct Keys<'a, K, V> {
+    iter: SliceIter<'a, Slot<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::key)
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::key)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
+
+/// An iterator over the values of an [`IndexMap`].
+///
+/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`values`]: IndexMap::values
+#[derive(Debug, Clone)]
+pub struct Values<'a, K, V> {
+    iter: SliceIter<'a, Slot<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::value)
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::value)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
+
+/// An iterator over the values of an [`IndexMap`].
+///
+/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`values`]: IndexMap::values
+#[derive(Debug)]
+pub struct ValuesMut<'a, K, V> {
+    iter: SliceIterMut<'a, Slot<K, V>>,
+}
+
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+    type Item = &'a mut V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(Slot::value_mut)
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(Slot::value_mut)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This `enum` is constructed from the [`entry`] method on [`IndexMap`].
+///
+/// [`entry`]: IndexMap::entry
+pub enum Entry<'a, K, V> {
+    /// A vacant entry.
+    Vacant(VacantEntry<'a, K, V>),
+    /// An occupied entry.
+    Occupied(OccupiedEntry<'a, K, V>),
+}
+
+impl<'a, K: Ord, V> Entry<'a, K, V> {
+    /// Ensures a value is in the entry by inserting the default if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_insert(self, default: V) -> &'a mut V
+    where
+        K: Clone,
+    {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(default),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the result
+    /// of the default function if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
+    where
+        K: Clone,
+    {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(default()),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting,
+    /// if empty, the result of the default function.
+    ///
+    /// This method allows for generating key-derived values for
+    /// insertion by providing the default function a reference
+    /// to the key that was moved during the `.entry(key)` method call.
+    ///
+    /// The reference to the moved key is provided
+    /// so that cloning or copying the key is
+    /// unnecessary, unlike with `.or_insert_with(|| ... )`.
+    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
+    where
+        K: Clone,
+    {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => {
+                let value = default(entry.key());
+                entry.insert(value)
+            }
+        }
+    }
+
+    /// Returns a reference to this entry’s key.
+    pub fn key(&self) -> &K {
+        match *self {
+            Self::Occupied(ref entry) => entry.key(),
+            Self::Vacant(ref entry) => entry.key(),
+        }
+    }
+
+    /// Provides in-place mutable access to an occupied entry
+    /// before any potential inserts into the map.
+    pub fn and_modify<F>(self, f: F) -> Self
+    where
+        F: FnOnce(&mut V),
+    {
+        match self {
+            Self::Occupied(mut entry) => {
+                f(entry.get_mut());
+                Self::Occupied(entry)
+            }
+            Self::Vacant(entry) => Self::Vacant(entry),
+        }
+    }
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Ord + Clone,
+    V: Default,
+{
+    /// Ensures a value is in the entry by inserting the default value if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_default(self) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(Default::default()),
+        }
+    }
+}
+
+impl<'a, K, V> fmt::Debug for Entry<'a, K, V>
+where
+    K: fmt::Debug + Ord,
+    V: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Entry::Vacant(entry) => entry.fmt(f),
+            Entry::Occupied(entry) => entry.fmt(f),
+        }
+    }
+}
+
+/// A view into a vacant entry in an [`IndexMap`]. It is part of the [`Entry`] `enum`.
+pub struct VacantEntry<'a, K, V> {
+    /// The underlying vacant entry.
+    vacant: btree_map::VacantEntry<'a, K, SlotIndex>,
+    /// The vector that stores all slots.
+    slots: &'a mut Vec<Slot<K, V>>,
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V>
+where
+    K: Ord,
+{
+    /// Gets a reference to the key that would be used when inserting a value through the VacantEntry.
+    pub fn key(&self) -> &K {
+        self.vacant.key()
+    }
+
+    /// Take ownership of the key.
+    pub fn into_key(self) -> K {
+        self.vacant.into_key()
+    }
+
+    /// Sets the value of the entry with the `VacantEntry`’s key,
+    /// and returns a mutable reference to it.
+    pub fn insert(self, value: V) -> &'a mut V
+    where
+        K: Clone,
+    {
+        let index = self.slots.len();
+        let key = self.vacant.key().clone();
+        self.vacant.insert(SlotIndex(index));
+        self.slots.push(Slot::new(key, value));
+        &mut self.slots[index].value
+    }
+}
+
+impl<'a, K, V> fmt::Debug for VacantEntry<'a, K, V>
+where
+    K: fmt::Debug + Ord,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("VacantEntry")
+            .field("key", self.key())
+            .finish()
+    }
+}
+
+/// A view into an occupied entry in a [`IndexMap`]. It is part of the [`Entry`] `enum`.
+pub struct OccupiedEntry<'a, K, V> {
+    /// The underlying occupied entry.
+    occupied: btree_map::OccupiedEntry<'a, K, SlotIndex>,
+    /// The vector that stores all slots.
+    slots: &'a mut Vec<Slot<K, V>>,
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V>
+where
+    K: Ord,
+{
+    /// Gets a reference to the key in the entry.
+    pub fn key(&self) -> &K {
+        self.occupied.key()
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V {
+        let index = self.occupied.get().index();
+        &self.slots[index].value
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    ///
+    /// If you need a reference to the `OccupiedEntry` that may outlive the
+    /// destruction of the `Entry` value, see [`into_mut`].
+    ///
+    /// [`into_mut`]: OccupiedEntry::into_mut
+    pub fn get_mut(&mut self) -> &mut V {
+        let index = self.occupied.get().index();
+        &mut self.slots[index].value
+    }
+
+    /// Converts the entry into a mutable reference to its value.
+    ///
+    /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
+    ///
+    /// [`get_mut`]: OccupiedEntry::get_mut
+    pub fn into_mut(self) -> &'a mut V {
+        let index = self.occupied.get().index();
+        &mut self.slots[index].value
+    }
+
+    /// Sets the value of the entry with the `OccupiedEntry`’s key,
+    /// and returns the entry’s old value.
+    pub fn insert(&mut self, value: V) -> V
+    where
+        K: Clone,
+    {
+        let index = self.occupied.get().index();
+        let key = self.key().clone();
+        let new_slot = Slot::new(key, value);
+        let old_slot = replace(&mut self.slots[index], new_slot);
+        old_slot.value
+    }
+}
+
+impl<'a, K, V> fmt::Debug for OccupiedEntry<'a, K, V>
+where
+    K: fmt::Debug + Ord,
+    V: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("OccupiedEntry")
+            .field("key", self.key())
+            .field("value", self.get())
+            .finish()
+    }
+}
diff --git a/crates/wasmparser/src/collections/index_set.rs b/crates/wasmparser/src/collections/index_set.rs
new file mode 100644
index 00000000..230e33d5
--- /dev/null
+++ b/crates/wasmparser/src/collections/index_set.rs
@@ -0,0 +1,243 @@
+//! Type definitions for an ordered set.
+
+use crate::collections::IndexMap;
+use core::{borrow::Borrow, hash::Hash, iter::FusedIterator, ops::Index};
+
+/// A default set of values.
+///
+/// Provides an API compatible with both [`IndexSet`] and a custom implementation based on [`BTreeMap`].
+///
+/// [`IndexSet`]: indexmap::IndexSet
+/// [`BTreeMap`]: alloc::collections::BTreeMap
+#[derive(Debug, Clone)]
+pub struct IndexSet<T> {
+    inner: IndexMap<T, ()>,
+}
+
+impl<T> Default for IndexSet<T> {
+    fn default() -> Self {
+        Self {
+            inner: IndexMap::default(),
+        }
+    }
+}
+
+impl<T> IndexSet<T> {
+    /// Clears the [`IndexSet`], removing all elements.
+    pub fn clear(&mut self) {
+        self.inner.clear()
+    }
+
+    /// Returns the number of elements in the [`IndexSet`].
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Returns `true` if the [`IndexSet`] contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    /// Returns an iterator that yields the items in the [`IndexSet`].
+    pub fn iter(&self) -> Iter<'_, T> {
+        Iter {
+            inner: self.inner.iter(),
+        }
+    }
+}
+
+impl<T> IndexSet<T>
+where
+    T: Eq + Hash + Ord + Clone,
+{
+    /// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexSet`].
+    pub fn reserve(&mut self, additional: usize) {
+        self.inner.reserve(additional);
+    }
+
+    /// Returns true if the [`IndexSet`] contains an element equal to the `value`.
+    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
+    where
+        T: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.contains_key(value)
+    }
+
+    /// Returns a reference to the element in the [`IndexSet`], if any, that is equal to the `value`.
+    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
+    where
+        T: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.get_key_value(value).map(|(x, &())| x)
+    }
+
+    /// Adds `value` to the [`IndexSet`].
+    ///
+    /// Returns whether the value was newly inserted:
+    ///
+    /// - Returns `true` if the set did not previously contain an equal value.
+    /// - Returns `false` otherwise and the entry is not updated.
+    pub fn insert(&mut self, value: T) -> bool {
+        self.inner.insert(value, ()).is_none()
+    }
+
+    /// Remove the value from the [`IndexSet`], and return `true` if it was present.
+    ///
+    /// Like [`Vec::swap_remove`], the value is removed by swapping it with the
+    /// last element of the set and popping it off. **This perturbs
+    /// the position of what used to be the last element!**
+    ///
+    /// Return `false` if `value` was not in the set.
+    ///
+    /// Computes in **O(1)** time (average).
+    ///
+    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
+    pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
+    where
+        T: Borrow<Q>,
+        Q: Hash + Eq + Ord,
+    {
+        self.inner.swap_remove(value).is_some()
+    }
+
+    /// Adds a value to the [`IndexSet`], replacing the existing value, if any, that is equal to the given
+    /// one. Returns the replaced value.
+    pub fn replace(&mut self, value: T) -> Option<T> {
+        let removed = self.inner.swap_remove_entry(&value);
+        self.inner.insert(value, ());
+        removed.map(|(key, _value)| key)
+    }
+
+    /// Returns `true` if `self` has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    pub fn is_disjoint(&self, other: &Self) -> bool {
+        if self.len() <= other.len() {
+            self.iter().all(move |value| !other.contains(value))
+        } else {
+            other.iter().all(move |value| !self.contains(value))
+        }
+    }
+
+    /// Returns `true` if the [`IndexSet`] is a subset of another,
+    /// i.e., `other` contains at least all the values in `self`.
+    pub fn is_subset(&self, other: &Self) -> bool {
+        self.len() <= other.len() && self.iter().all(move |value| other.contains(value))
+    }
+
+    /// Returns `true` if the [`IndexSet`] is a superset of another,
+    /// i.e., `self` contains at least all the values in `other`.
+    pub fn is_superset(&self, other: &Self) -> bool {
+        other.is_subset(self)
+    }
+}
+
+impl<T> Index<usize> for IndexSet<T>
+where
+    T: Hash + Eq + Ord,
+{
+    type Output = T;
+
+    fn index(&self, index: usize) -> &T {
+        let Some((value, _)) = self.inner.get_index(index) else {
+            panic!("out of bounds index: {index}");
+        };
+        value
+    }
+}
+
+impl<T> FromIterator<T> for IndexSet<T>
+where
+    T: Hash + Eq + Ord + Clone,
+{
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = T>,
+    {
+        Self {
+            inner: <IndexMap<T, ()>>::from_iter(iter.into_iter().map(|value| (value, ()))),
+        }
+    }
+}
+
+impl<'a, T> IntoIterator for &'a IndexSet<T> {
+    type Item = &'a T;
+    type IntoIter = Iter<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<T> Extend<T> for IndexSet<T>
+where
+    T: Hash + Eq + Ord + Clone,
+{
+    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
+        self.inner.extend(iter.into_iter().map(|value| (value, ())))
+    }
+}
+
+/// An iterator over the items of a [`IndexSet`].
+#[derive(Debug, Clone)]
+pub struct Iter<'a, T> {
+    inner: <&'a IndexMap<T, ()> as IntoIterator>::IntoIter,
+}
+
+impl<'a, T> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next().map(|(key, _value)| key)
+    }
+}
+
+impl<'a, T> ExactSizeIterator for Iter<'a, T> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, T> FusedIterator for Iter<'a, T> {}
+
+impl<T> IntoIterator for IndexSet<T> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            inner: self.inner.into_iter(),
+        }
+    }
+}
+
+/// An iterator over the owned items of an [`IndexSet`].
+#[derive(Debug)]
+pub struct IntoIter<T> {
+    inner: <IndexMap<T, ()> as IntoIterator>::IntoIter,
+}
+
+impl<T> Iterator for IntoIter<T> {
+    type Item = T;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next().map(|(key, _value)| key)
+    }
+}
+
+impl<T> ExactSizeIterator for IntoIter<T> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<T> FusedIterator for IntoIter<T> {}
diff --git a/crates/wasmparser/src/collections/map.rs b/crates/wasmparser/src/collections/map.rs
new file mode 100644
index 00000000..14980c24
--- /dev/null
+++ b/crates/wasmparser/src/collections/map.rs
@@ -0,0 +1,740 @@
+//! Type definitions for a default map.
+
+use core::fmt::Debug;
+use core::{borrow::Borrow, hash::Hash, iter::FusedIterator, ops::Index};
+
+#[cfg(not(feature = "no-hash-maps"))]
+mod detail {
+    use crate::collections::hash;
+    use hashbrown::hash_map;
+
+    pub type MapImpl<K, V> = hash_map::HashMap<K, V, hash::RandomState>;
+    pub type EntryImpl<'a, K, V> = hash_map::Entry<'a, K, V, hash::RandomState>;
+    pub type OccupiedEntryImpl<'a, K, V> = hash_map::OccupiedEntry<'a, K, V, hash::RandomState>;
+    pub type VacantEntryImpl<'a, K, V> = hash_map::VacantEntry<'a, K, V, hash::RandomState>;
+    pub type IterImpl<'a, K, V> = hash_map::Iter<'a, K, V>;
+    pub type IterMutImpl<'a, K, V> = hash_map::IterMut<'a, K, V>;
+    pub type IntoIterImpl<K, V> = hash_map::IntoIter<K, V>;
+    pub type KeysImpl<'a, K, V> = hash_map::Keys<'a, K, V>;
+    pub type ValuesImpl<'a, K, V> = hash_map::Values<'a, K, V>;
+    pub type ValuesMutImpl<'a, K, V> = hash_map::ValuesMut<'a, K, V>;
+    pub type IntoKeysImpl<K, V> = hash_map::IntoKeys<K, V>;
+    pub type IntoValuesImpl<K, V> = hash_map::IntoValues<K, V>;
+}
+
+#[cfg(feature = "no-hash-maps")]
+mod detail {
+    use alloc::collections::btree_map;
+
+    pub type MapImpl<K, V> = btree_map::BTreeMap<K, V>;
+    pub type EntryImpl<'a, K, V> = btree_map::Entry<'a, K, V>;
+    pub type OccupiedEntryImpl<'a, K, V> = btree_map::OccupiedEntry<'a, K, V>;
+    pub type VacantEntryImpl<'a, K, V> = btree_map::VacantEntry<'a, K, V>;
+    pub type IterImpl<'a, K, V> = btree_map::Iter<'a, K, V>;
+    pub type IterMutImpl<'a, K, V> = btree_map::IterMut<'a, K, V>;
+    pub type IntoIterImpl<K, V> = btree_map::IntoIter<K, V>;
+    pub type KeysImpl<'a, K, V> = btree_map::Keys<'a, K, V>;
+    pub type ValuesImpl<'a, K, V> = btree_map::Values<'a, K, V>;
+    pub type ValuesMutImpl<'a, K, V> = btree_map::ValuesMut<'a, K, V>;
+    pub type IntoKeysImpl<K, V> = btree_map::IntoKeys<K, V>;
+    pub type IntoValuesImpl<K, V> = btree_map::IntoValues<K, V>;
+}
+
+/// A default key-value mapping.
+///
+/// Provides an API compatible with both [`HashMap`] and [`BTreeMap`].
+///
+/// [`HashMap`]: hashbrown::HashMap
+/// [`BTreeMap`]: alloc::collections::BTreeMap
+#[derive(Debug, Clone)]
+pub struct Map<K, V> {
+    inner: detail::MapImpl<K, V>,
+}
+
+impl<K, V> Default for Map<K, V> {
+    fn default() -> Self {
+        Self {
+            inner: detail::MapImpl::default(),
+        }
+    }
+}
+
+impl<K, V> Map<K, V> {
+    /// Creates a new empty [`Map`].
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    /// Clears the [`Map`], removing all elements.
+    pub fn clear(&mut self) {
+        self.inner.clear()
+    }
+
+    /// Returns the number of elements in the [`Map`].
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Returns `true` if the [`Map`] contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    /// Returns an iterator that yields the items in the [`Map`].
+    pub fn iter(&self) -> Iter<'_, K, V> {
+        Iter {
+            inner: self.inner.iter(),
+        }
+    }
+
+    /// Returns a mutable iterator that yields the items in the [`Map`].
+    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
+        IterMut {
+            inner: self.inner.iter_mut(),
+        }
+    }
+
+    /// Returns an iterator that yields the keys in the [`Map`].
+    pub fn keys(&self) -> Keys<'_, K, V> {
+        Keys {
+            inner: self.inner.keys(),
+        }
+    }
+
+    /// Creates a consuming iterator visiting all the keys in arbitrary order.
+    ///
+    /// The [`Map`] cannot be used after calling this.
+    /// The iterator element type is `K`.
+    pub fn into_keys(self) -> IntoKeys<K, V> {
+        IntoKeys {
+            inner: self.inner.into_keys(),
+        }
+    }
+
+    /// Returns an iterator that yields the values in the [`Map`].
+    pub fn values(&self) -> Values<'_, K, V> {
+        Values {
+            inner: self.inner.values(),
+        }
+    }
+
+    /// Creates a consuming iterator visiting all the values in arbitrary order.
+    ///
+    /// The [`Map`] cannot be used after calling this.
+    /// The iterator element type is `V`.
+    pub fn into_values(self) -> IntoValues<K, V> {
+        IntoValues {
+            inner: self.inner.into_values(),
+        }
+    }
+
+    /// Returns a mutable iterator that yields the values in the [`Map`].
+    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
+        ValuesMut {
+            inner: self.inner.values_mut(),
+        }
+    }
+}
+
+impl<K, V> Map<K, V>
+where
+    K: Hash + Eq + Ord,
+{
+    /// Reserves capacity for at least `additional` more elements to be inserted in the [`Map`].
+    pub fn reserve(&mut self, additional: usize) {
+        #[cfg(not(feature = "no-hash-maps"))]
+        self.inner.reserve(additional);
+        #[cfg(feature = "no-hash-maps")]
+        let _ = additional;
+    }
+
+    /// Returns true if `key` is contains in the [`Map`].
+    pub fn contains_key<Q>(&self, key: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.contains_key(key)
+    }
+
+    /// Returns a reference to the value corresponding to the `key`.
+    pub fn get<Q>(&self, key: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.get(key)
+    }
+
+    /// Returns the key-value pair corresponding to the supplied key.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.get_key_value(key)
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.get_mut(key)
+    }
+
+    /// Inserts a key-value pair into the [`Map`].
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical.
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
+        self.inner.insert(key, value)
+    }
+
+    /// Removes a key from the [`Map`], returning the value at the key if the key was previously in the map.
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.remove(key)
+    }
+
+    /// Removes a key from the [`Map`], returning the stored key and value if the key
+    /// was previously in the map.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
+    where
+        K: Borrow<Q>,
+        Q: ?Sized + Hash + Ord,
+    {
+        self.inner.remove_entry(key)
+    }
+
+    /// Gets the given key's corresponding entry in the [`Map`] for in-place manipulation.
+    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+        match self.inner.entry(key) {
+            detail::EntryImpl::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
+            detail::EntryImpl::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
+        }
+    }
+
+    /// Retains only the elements specified by the predicate.
+    ///
+    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
+    /// The elements are visited in ascending key order.
+    pub fn retain<F>(&mut self, f: F)
+    where
+        F: FnMut(&K, &mut V) -> bool,
+    {
+        self.inner.retain(f)
+    }
+}
+
+impl<K, V> PartialEq for Map<K, V>
+where
+    K: Eq + Hash,
+    V: Eq,
+{
+    fn eq(&self, other: &Self) -> bool {
+        self.inner == other.inner
+    }
+}
+
+impl<K, V> Eq for Map<K, V>
+where
+    K: Eq + Hash,
+    V: Eq,
+{
+}
+
+impl<K, Q, V> Index<&Q> for Map<K, V>
+where
+    K: Borrow<Q> + Hash + Eq + Ord,
+    Q: ?Sized + Hash + Eq + Ord,
+{
+    type Output = V;
+
+    fn index(&self, key: &Q) -> &V {
+        &self.inner[key]
+    }
+}
+
+impl<'a, K, V> Extend<(&'a K, &'a V)> for Map<K, V>
+where
+    K: Eq + Hash + Ord + Copy,
+    V: Copy,
+{
+    fn extend<Iter: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: Iter) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<K, V> Extend<(K, V)> for Map<K, V>
+where
+    K: Eq + Hash + Ord,
+{
+    fn extend<Iter: IntoIterator<Item = (K, V)>>(&mut self, iter: Iter) {
+        self.inner.extend(iter)
+    }
+}
+
+/// A view into a single entry in a [`Map`], which may either be vacant or occupied.
+///
+/// This enum is constructed from the entry method on [`Map`].
+#[derive(Debug)]
+pub enum Entry<'a, K: Ord, V> {
+    /// An occupied entry.
+    Occupied(OccupiedEntry<'a, K, V>),
+    /// A vacant entry.
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Hash + Ord,
+{
+    /// Ensures a value is in the entry by inserting the default if empty, and returns
+    /// a mutable reference to the value in the entry.
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(default),
+        }
+    }
+
+    /// Ensures a value is in the [`Entry`] by inserting the result of the default function if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(default()),
+        }
+    }
+
+    /// Ensures a value is in the [`Entry`] by inserting, if empty, the result of the default function.
+    /// This method allows for generating key-derived values for insertion by providing the default
+    /// function a reference to the key that was moved during the `.entry(key)` method call.
+    ///
+    /// The reference to the moved key is provided so that cloning or copying the key is
+    /// unnecessary, unlike with `.or_insert_with(|| ... )`.
+    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => {
+                let value = default(entry.key());
+                entry.insert(value)
+            }
+        }
+    }
+
+    /// Returns a reference to this [`Entry`]'s key.
+    pub fn key(&self) -> &K {
+        match *self {
+            Self::Occupied(ref entry) => entry.key(),
+            Self::Vacant(ref entry) => entry.key(),
+        }
+    }
+
+    /// Provides in-place mutable access to an occupied [`Entry`] before any
+    /// potential inserts into the map.
+    pub fn and_modify<F>(self, f: F) -> Self
+    where
+        F: FnOnce(&mut V),
+    {
+        match self {
+            Self::Occupied(mut entry) => {
+                f(entry.get_mut());
+                Self::Occupied(entry)
+            }
+            Self::Vacant(entry) => Self::Vacant(entry),
+        }
+    }
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Hash + Ord,
+    V: Default,
+{
+    /// Ensures a value is in the [`Entry`] by inserting the default value if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_default(self) -> &'a mut V {
+        match self {
+            Self::Occupied(entry) => entry.into_mut(),
+            Self::Vacant(entry) => entry.insert(Default::default()),
+        }
+    }
+}
+
+/// A view into an occupied entry in a [`Map`].
+///
+/// It is part of the [`Entry`] enum.
+pub struct OccupiedEntry<'a, K, V> {
+    inner: detail::OccupiedEntryImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Debug for OccupiedEntry<'a, K, V>
+where
+    K: Debug + Ord + 'a,
+    V: Debug + 'a,
+{
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V>
+where
+    K: Ord + 'a,
+    V: 'a,
+{
+    /// Gets a reference to the key in the entry.
+    pub fn key(&self) -> &K {
+        self.inner.key()
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V {
+        self.inner.get()
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    pub fn get_mut(&mut self) -> &mut V {
+        self.inner.get_mut()
+    }
+
+    /// Sets the value of the entry with the [`OccupiedEntry`]'s key, and returns the entry's old value.
+    pub fn insert(&mut self, value: V) -> V {
+        self.inner.insert(value)
+    }
+
+    /// Converts the [`OccupiedEntry`] into a mutable reference to the value in the entry
+    /// with a lifetime bound to the map itself.
+    pub fn into_mut(self) -> &'a mut V {
+        self.inner.into_mut()
+    }
+
+    /// Take ownership of the key and value from the [`Map`].
+    pub fn remove_entry(self) -> (K, V) {
+        self.inner.remove_entry()
+    }
+
+    /// Takes the value of the entry out of the [`Map`], and returns it.
+    pub fn remove(self) -> V {
+        self.inner.remove()
+    }
+}
+
+/// A view into a vacant entry in a [`Map`].
+///
+/// It is part of the [`Entry`] enum.
+pub struct VacantEntry<'a, K, V> {
+    inner: detail::VacantEntryImpl<'a, K, V>,
+}
+
+impl<'a, K, V> Debug for VacantEntry<'a, K, V>
+where
+    K: Debug + Ord + 'a,
+    V: Debug + 'a,
+{
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V>
+where
+    K: Ord + 'a,
+    V: 'a,
+{
+    /// Gets a reference to the key in the entry.
+    pub fn key(&self) -> &K {
+        self.inner.key()
+    }
+
+    /// Take ownership of the key.
+    pub fn into_key(self) -> K {
+        self.inner.into_key()
+    }
+
+    /// Sets the value of the entry with the [`VacantEntry`]'s key, and returns a mutable reference to it.
+    pub fn insert(self, value: V) -> &'a mut V
+    where
+        K: Hash,
+    {
+        self.inner.insert(value)
+    }
+}
+
+impl<K, V> FromIterator<(K, V)> for Map<K, V>
+where
+    K: Hash + Eq + Ord,
+{
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = (K, V)>,
+    {
+        Self {
+            inner: <detail::MapImpl<K, V>>::from_iter(iter),
+        }
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a Map<K, V> {
+    type Item = (&'a K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+/// An iterator over the items of a [`Map`].
+#[derive(Debug, Clone)]
+pub struct Iter<'a, K, V> {
+    inner: detail::IterImpl<'a, K, V>,
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> FusedIterator for Iter<'a, K, V> where
+    detail::IterImpl<'a, K, V>: FusedIterator
+{
+}
+
+impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut Map<K, V> {
+    type Item = (&'a K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+/// An iterator over the mutable items of a [`Map`].
+#[derive(Debug)]
+pub struct IterMut<'a, K, V> {
+    inner: detail::IterMutImpl<'a, K, V>,
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> FusedIterator for IterMut<'a, K, V> where
+    detail::IterMutImpl<'a, K, V>: FusedIterator
+{
+}
+
+impl<K, V> IntoIterator for Map<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            inner: self.inner.into_iter(),
+        }
+    }
+}
+
+/// An iterator over the owned items of an [`Map`].
+#[derive(Debug)]
+pub struct IntoIter<K, V> {
+    inner: detail::IntoIterImpl<K, V>,
+}
+
+impl<K, V> Iterator for IntoIter<K, V> {
+    type Item = (K, V);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<K, V> FusedIterator for IntoIter<K, V> where detail::IntoIterImpl<K, V>: FusedIterator {}
+
+/// An iterator over the keys of a [`Map`].
+#[derive(Debug, Clone)]
+pub struct Keys<'a, K, V> {
+    inner: detail::KeysImpl<'a, K, V>,
+}
+
+impl<'a, K: 'a, V> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K: 'a, V> ExactSizeIterator for Keys<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K: 'a, V> FusedIterator for Keys<'a, K, V> where detail::KeysImpl<'a, K, V>: FusedIterator {}
+
+/// An iterator over the values of a [`Map`].
+#[derive(Debug, Clone)]
+pub struct Values<'a, K, V> {
+    inner: detail::ValuesImpl<'a, K, V>,
+}
+
+impl<'a, K, V: 'a> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V: 'a> ExactSizeIterator for Values<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V: 'a> FusedIterator for Values<'a, K, V> where
+    detail::ValuesImpl<'a, K, V>: FusedIterator
+{
+}
+
+/// An mutable iterator over the values of a [`Map`].
+#[derive(Debug)]
+pub struct ValuesMut<'a, K, V> {
+    inner: detail::ValuesMutImpl<'a, K, V>,
+}
+
+impl<'a, K, V: 'a> Iterator for ValuesMut<'a, K, V> {
+    type Item = &'a mut V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, K, V: 'a> ExactSizeIterator for ValuesMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V: 'a> FusedIterator for ValuesMut<'a, K, V> where
+    detail::ValuesMutImpl<'a, K, V>: FusedIterator
+{
+}
+
+/// An iterator over the owned keys of a [`Map`].
+#[derive(Debug)]
+pub struct IntoKeys<K, V> {
+    inner: detail::IntoKeysImpl<K, V>,
+}
+
+impl<K, V> Iterator for IntoKeys<K, V> {
+    type Item = K;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<K, V> FusedIterator for IntoKeys<K, V> where detail::IntoKeysImpl<K, V>: FusedIterator {}
+
+/// An iterator over the owned values of a [`Map`].
+#[derive(Debug)]
+pub struct IntoValues<K, V> {
+    inner: detail::IntoValuesImpl<K, V>,
+}
+
+impl<K, V> Iterator for IntoValues<K, V> {
+    type Item = V;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<K, V> ExactSizeIterator for IntoValues<K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<K, V> FusedIterator for IntoValues<K, V> where detail::IntoValuesImpl<K, V>: FusedIterator {}
diff --git a/crates/wasmparser/src/collections/mod.rs b/crates/wasmparser/src/collections/mod.rs
new file mode 100644
index 00000000..f9a7cb26
--- /dev/null
+++ b/crates/wasmparser/src/collections/mod.rs
@@ -0,0 +1,24 @@
+//! Type definitions for maps and sets used by the `wasmparser` crate.
+//!
+//! This module contains type definitions for [`Map`], [`Set`], [`IndexMap`], and [`IndexSet`].
+//! These types are thin-wrappers around either hash-map based or B-tree-map based data structures.
+//! Users can strictly use the `btree`-map based variants by enabling the `no-hash-maps` crate feature.
+//!
+//! - [`Map`]: Either backed by [`hashbrown::HashMap`] or Rust's [`BTreeMap`].
+//! - [`Set`]: Either backed by [`hashbrown::HashSet`] or Rust's [`BTreeSet`].
+//! - [`IndexMap`]: Either backed by [`indexmap::IndexMap`] or a custom implementation based on Rust's [`BTreeMap`].
+//! - [`IndexSet`]: Either backed by [`indexmap::IndexSet`] or a custom implementation based on Rust's [`BTreeMap`].
+//!
+//! For the hash-map based type definitions the hash algorithm type parameter is fixed.
+//!
+//! [`BTreeMap`]: alloc::collections::BTreeMap
+//! [`BTreeSet`]: alloc::collections::BTreeSet
+
+pub mod hash;
+pub mod index_map;
+pub mod index_set;
+pub mod map;
+pub mod set;
+
+#[doc(inline)]
+pub use self::{index_map::IndexMap, index_set::IndexSet, map::Map, set::Set};
diff --git a/crates/wasmparser/src/collections/set.rs b/crates/wasmparser/src/collections/set.rs
new file mode 100644
index 00000000..0314fc30
--- /dev/null
+++ b/crates/wasmparser/src/collections/set.rs
@@ -0,0 +1,584 @@
+//! Type definitions for a default set.
+
+use core::{
+    borrow::Borrow,
+    fmt::{self, Debug},
+    hash::Hash,
+    iter::FusedIterator,
+    ops::{BitAnd, BitOr, BitXor, Sub},
+};
+
+#[cfg(not(feature = "no-hash-maps"))]
+mod detail {
+    use crate::collections::hash;
+    use hashbrown::hash_set;
+
+    pub type SetImpl<T> = hash_set::HashSet<T, hash::RandomState>;
+    pub type IterImpl<'a, T> = hash_set::Iter<'a, T>;
+    pub type IntoIterImpl<T> = hash_set::IntoIter<T>;
+    pub type DifferenceImpl<'a, T> = hash_set::Difference<'a, T, hash::RandomState>;
+    pub type IntersectionImpl<'a, T> = hash_set::Intersection<'a, T, hash::RandomState>;
+    pub type SymmetricDifferenceImpl<'a, T> =
+        hash_set::SymmetricDifference<'a, T, hash::RandomState>;
+    pub type UnionImpl<'a, T> = hash_set::Union<'a, T, hash::RandomState>;
+}
+
+#[cfg(feature = "no-hash-maps")]
+mod detail {
+    use alloc::collections::btree_set;
+
+    pub type SetImpl<T> = btree_set::BTreeSet<T>;
+    pub type IterImpl<'a, T> = btree_set::Iter<'a, T>;
+    pub type IntoIterImpl<T> = btree_set::IntoIter<T>;
+    pub type DifferenceImpl<'a, T> = btree_set::Difference<'a, T>;
+    pub type IntersectionImpl<'a, T> = btree_set::Intersection<'a, T>;
+    pub type SymmetricDifferenceImpl<'a, T> = btree_set::SymmetricDifference<'a, T>;
+    pub type UnionImpl<'a, T> = btree_set::Union<'a, T>;
+}
+
+/// A default set of values.
+///
+/// Provides an API compatible with both [`HashSet`] and [`BTreeSet`].
+///
+/// [`HashSet`]: hashbrown::HashSet
+/// [`BTreeSet`]: alloc::collections::BTreeSet
+#[derive(Debug, Clone)]
+pub struct Set<T> {
+    /// The underlying hash-set or btree-set data structure used.
+    inner: detail::SetImpl<T>,
+}
+
+impl<T> Default for Set<T> {
+    fn default() -> Self {
+        Self {
+            inner: detail::SetImpl::default(),
+        }
+    }
+}
+
+impl<T> Set<T> {
+    /// Clears the [`Set`], removing all elements.
+    pub fn clear(&mut self) {
+        self.inner.clear()
+    }
+
+    /// Retains only the elements specified by the predicate.
+    ///
+    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
+    /// The elements are visited in unsorted (and unspecified) order.
+    pub fn retain<F>(&mut self, f: F)
+    where
+        T: Ord,
+        F: FnMut(&T) -> bool,
+    {
+        self.inner.retain(f)
+    }
+
+    /// Returns the number of elements in the [`Set`].
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Returns `true` if the [`Set`] contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    /// Returns an iterator that yields the items in the [`Set`].
+    pub fn iter(&self) -> Iter<'_, T> {
+        Iter {
+            inner: self.inner.iter(),
+        }
+    }
+}
+
+impl<T> Set<T>
+where
+    T: Eq + Hash + Ord,
+{
+    /// Reserves capacity for at least `additional` more elements to be inserted in the [`Set`].
+    pub fn reserve(&mut self, additional: usize) {
+        #[cfg(not(feature = "no-hash-maps"))]
+        self.inner.reserve(additional);
+        #[cfg(feature = "no-hash-maps")]
+        let _ = additional;
+    }
+
+    /// Returns true if the [`Set`] contains an element equal to the `value`.
+    pub fn contains<Q>(&self, value: &Q) -> bool
+    where
+        T: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.contains(value)
+    }
+
+    /// Returns a reference to the element in the [`Set`], if any, that is equal to the `value`.
+    pub fn get<Q>(&self, value: &Q) -> Option<&T>
+    where
+        T: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.get(value)
+    }
+
+    /// Adds `value` to the [`Set`].
+    ///
+    /// Returns whether the value was newly inserted:
+    ///
+    /// - Returns `true` if the set did not previously contain an equal value.
+    /// - Returns `false` otherwise and the entry is not updated.
+    pub fn insert(&mut self, value: T) -> bool {
+        self.inner.insert(value)
+    }
+
+    /// If the set contains an element equal to the value, removes it from the [`Set`] and drops it.
+    ///
+    /// Returns `true` if such an element was present, otherwise `false`.
+    pub fn remove<Q>(&mut self, value: &Q) -> bool
+    where
+        T: Borrow<Q>,
+        Q: ?Sized + Hash + Eq + Ord,
+    {
+        self.inner.remove(value)
+    }
+
+    /// Removes and returns the element in the [`Set`], if any, that is equal to
+    /// the value.
+    ///
+    /// The value may be any borrowed form of the set's element type,
+    /// but the ordering on the borrowed form *must* match the
+    /// ordering on the element type.
+    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
+    where
+        T: Borrow<Q>,
+        Q: ?Sized + Hash + Ord,
+    {
+        self.inner.take(value)
+    }
+
+    /// Adds a value to the [`Set`], replacing the existing value, if any, that is equal to the given
+    /// one. Returns the replaced value.
+    pub fn replace(&mut self, value: T) -> Option<T> {
+        self.inner.replace(value)
+    }
+
+    /// Returns `true` if `self` has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    pub fn is_disjoint(&self, other: &Self) -> bool {
+        self.inner.is_disjoint(&other.inner)
+    }
+
+    /// Returns `true` if the [`Set`] is a subset of another,
+    /// i.e., `other` contains at least all the values in `self`.
+    pub fn is_subset(&self, other: &Self) -> bool {
+        self.inner.is_subset(&other.inner)
+    }
+
+    /// Returns `true` if the [`Set`] is a superset of another,
+    /// i.e., `self` contains at least all the values in `other`.
+    pub fn is_superset(&self, other: &Self) -> bool {
+        self.inner.is_superset(&other.inner)
+    }
+
+    /// Visits the values representing the difference,
+    /// i.e., the values that are in `self` but not in `other`.
+    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> {
+        Difference {
+            inner: self.inner.difference(&other.inner),
+        }
+    }
+
+    /// Visits the values representing the symmetric difference,
+    /// i.e., the values that are in `self` or in `other` but not in both.
+    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T> {
+        SymmetricDifference {
+            inner: self.inner.symmetric_difference(&other.inner),
+        }
+    }
+
+    /// Visits the values representing the intersection,
+    /// i.e., the values that are both in `self` and `other`.
+    ///
+    /// When an equal element is present in `self` and `other`
+    /// then the resulting `Intersection` may yield references to
+    /// one or the other. This can be relevant if `T` contains fields which
+    /// are not compared by its `Eq` implementation, and may hold different
+    /// value between the two equal copies of `T` in the two sets.
+    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
+        Intersection {
+            inner: self.inner.intersection(&other.inner),
+        }
+    }
+
+    /// Visits the values representing the union,
+    /// i.e., all the values in `self` or `other`, without duplicates.
+    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
+        Union {
+            inner: self.inner.union(&other.inner),
+        }
+    }
+}
+
+impl<T> PartialEq for Set<T>
+where
+    T: Eq + Hash,
+{
+    fn eq(&self, other: &Self) -> bool {
+        self.inner == other.inner
+    }
+}
+
+impl<T> Eq for Set<T> where T: Eq + Hash {}
+
+impl<T> FromIterator<T> for Set<T>
+where
+    T: Hash + Eq + Ord,
+{
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = T>,
+    {
+        Self {
+            inner: <detail::SetImpl<T>>::from_iter(iter),
+        }
+    }
+}
+
+impl<'a, T> IntoIterator for &'a Set<T> {
+    type Item = &'a T;
+    type IntoIter = Iter<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, T> Extend<&'a T> for Set<T>
+where
+    T: Hash + Eq + Ord + Copy + 'a,
+{
+    fn extend<Iter: IntoIterator<Item = &'a T>>(&mut self, iter: Iter) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<T> Extend<T> for Set<T>
+where
+    T: Hash + Eq + Ord,
+{
+    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<'a, T> BitAnd<Self> for &'a Set<T>
+where
+    T: Eq + Hash + Ord + Clone + 'a,
+{
+    type Output = Set<T>;
+
+    fn bitand(self, rhs: Self) -> Set<T> {
+        Set {
+            inner: BitAnd::bitand(&self.inner, &rhs.inner),
+        }
+    }
+}
+
+impl<'a, T> BitOr<Self> for &'a Set<T>
+where
+    T: Eq + Hash + Ord + Clone + 'a,
+{
+    type Output = Set<T>;
+
+    fn bitor(self, rhs: Self) -> Set<T> {
+        Set {
+            inner: BitOr::bitor(&self.inner, &rhs.inner),
+        }
+    }
+}
+
+impl<'a, T> BitXor<Self> for &'a Set<T>
+where
+    T: Eq + Hash + Ord + Clone + 'a,
+{
+    type Output = Set<T>;
+
+    fn bitxor(self, rhs: Self) -> Set<T> {
+        Set {
+            inner: BitXor::bitxor(&self.inner, &rhs.inner),
+        }
+    }
+}
+
+impl<'a, T> Sub<Self> for &'a Set<T>
+where
+    T: Eq + Hash + Ord + Clone + 'a,
+{
+    type Output = Set<T>;
+
+    fn sub(self, rhs: Self) -> Set<T> {
+        Set {
+            inner: Sub::sub(&self.inner, &rhs.inner),
+        }
+    }
+}
+
+/// An iterator over the items of a [`Set`].
+#[derive(Debug, Clone)]
+pub struct Iter<'a, T> {
+    inner: detail::IterImpl<'a, T>,
+}
+
+impl<'a, T: 'a> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<'a, T: 'a> ExactSizeIterator for Iter<'a, T> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, T: 'a> FusedIterator for Iter<'a, T> where detail::IterImpl<'a, T>: FusedIterator {}
+
+impl<T> IntoIterator for Set<T> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            inner: self.inner.into_iter(),
+        }
+    }
+}
+
+/// An iterator over the owned items of an [`Set`].
+#[derive(Debug)]
+pub struct IntoIter<T> {
+    inner: detail::IntoIterImpl<T>,
+}
+
+impl<T> Iterator for IntoIter<T> {
+    type Item = T;
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+}
+
+impl<T> ExactSizeIterator for IntoIter<T> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<T> FusedIterator for IntoIter<T> where detail::IntoIterImpl<T>: FusedIterator {}
+
+/// A lazy iterator producing elements in the difference of [`Set`]s.
+///
+/// This `struct` is created by the [`difference`] method on [`Set`].
+/// See its documentation for more.
+///
+/// [`difference`]: Set::difference
+pub struct Difference<'a, T: 'a> {
+    inner: detail::DifferenceImpl<'a, T>,
+}
+
+impl<T> Debug for Difference<'_, T>
+where
+    T: Debug + Hash + Eq,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<T> Clone for Difference<'_, T> {
+    fn clone(&self) -> Self {
+        Self {
+            inner: self.inner.clone(),
+        }
+    }
+}
+
+impl<'a, T> Iterator for Difference<'a, T>
+where
+    T: Hash + Eq + Ord,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, T> FusedIterator for Difference<'a, T>
+where
+    T: Hash + Eq + Ord,
+    detail::DifferenceImpl<'a, T>: FusedIterator,
+{
+}
+
+/// A lazy iterator producing elements in the intersection of [`Set`]s.
+///
+/// This `struct` is created by the [`intersection`] method on [`Set`].
+/// See its documentation for more.
+///
+/// [`intersection`]: Set::intersection
+pub struct Intersection<'a, T: 'a> {
+    inner: detail::IntersectionImpl<'a, T>,
+}
+
+impl<T> Debug for Intersection<'_, T>
+where
+    T: Debug + Hash + Eq,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<T> Clone for Intersection<'_, T> {
+    fn clone(&self) -> Self {
+        Self {
+            inner: self.inner.clone(),
+        }
+    }
+}
+
+impl<'a, T> Iterator for Intersection<'a, T>
+where
+    T: Hash + Eq + Ord,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, T> FusedIterator for Intersection<'a, T>
+where
+    T: Hash + Eq + Ord,
+    detail::IntersectionImpl<'a, T>: FusedIterator,
+{
+}
+
+/// A lazy iterator producing elements in the symmetric difference of [`Set`]s.
+///
+/// This `struct` is created by the [`symmetric_difference`] method on
+/// [`Set`]. See its documentation for more.
+///
+/// [`symmetric_difference`]: Set::symmetric_difference
+pub struct SymmetricDifference<'a, T: 'a> {
+    inner: detail::SymmetricDifferenceImpl<'a, T>,
+}
+
+impl<T> Debug for SymmetricDifference<'_, T>
+where
+    T: Debug + Hash + Eq,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<T> Clone for SymmetricDifference<'_, T> {
+    fn clone(&self) -> Self {
+        Self {
+            inner: self.inner.clone(),
+        }
+    }
+}
+
+impl<'a, T> Iterator for SymmetricDifference<'a, T>
+where
+    T: Hash + Eq + Ord,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, T> FusedIterator for SymmetricDifference<'a, T>
+where
+    T: Hash + Eq + Ord,
+    detail::SymmetricDifferenceImpl<'a, T>: FusedIterator,
+{
+}
+
+/// A lazy iterator producing elements in the union of [`Set`]s.
+///
+/// This `struct` is created by the [`union`] method on
+/// [`Set`]. See its documentation for more.
+///
+/// [`union`]: Set::union
+pub struct Union<'a, T: 'a> {
+    inner: detail::UnionImpl<'a, T>,
+}
+
+impl<T> Debug for Union<'_, T>
+where
+    T: Debug + Hash + Eq,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<T> Clone for Union<'_, T> {
+    fn clone(&self) -> Self {
+        Self {
+            inner: self.inner.clone(),
+        }
+    }
+}
+
+impl<'a, T> Iterator for Union<'a, T>
+where
+    T: Hash + Eq + Ord,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, T> FusedIterator for Union<'a, T>
+where
+    T: Hash + Eq + Ord,
+    detail::UnionImpl<'a, T>: FusedIterator,
+{
+}
diff --git a/crates/wasmparser/src/lib.rs b/crates/wasmparser/src/lib.rs
index 227442c6..28cc15bb 100644
--- a/crates/wasmparser/src/lib.rs
+++ b/crates/wasmparser/src/lib.rs
@@ -50,7 +50,7 @@ mod prelude {
     pub use alloc::vec::Vec;
 
     #[cfg(feature = "validate")]
-    pub use crate::map::{HashMap, HashSet, IndexMap, IndexSet};
+    pub use crate::collections::{IndexMap, IndexSet, Map, Set};
 }
 
 /// A helper macro to conveniently iterate over all opcodes recognized by this
@@ -804,4 +804,4 @@ pub use crate::resources::*;
 pub use crate::validator::*;
 
 #[cfg(feature = "validate")]
-pub mod map;
+pub mod collections;
diff --git a/crates/wasmparser/src/parser.rs b/crates/wasmparser/src/parser.rs
index 5e555504..a0f54c8a 100644
--- a/crates/wasmparser/src/parser.rs
+++ b/crates/wasmparser/src/parser.rs
@@ -715,6 +715,7 @@ impl Parser {
                         self.max_size -= u64::from(len);
                         self.offset += u64::from(len);
                         let mut parser = Parser::new(usize_to_u64(reader.original_position()));
+                        parser.features = self.features;
                         parser.max_size = u64::from(len);
 
                         Ok(match id {
diff --git a/crates/wasmparser/src/readers/core/globals.rs b/crates/wasmparser/src/readers/core/globals.rs
index 6413db8d..b96c545b 100644
--- a/crates/wasmparser/src/readers/core/globals.rs
+++ b/crates/wasmparser/src/readers/core/globals.rs
@@ -39,8 +39,18 @@ impl<'a> FromReader<'a> for GlobalType {
     fn from_reader(reader: &mut BinaryReader<'a>) -> Result<Self> {
         let content_type = reader.read()?;
         let flags = reader.read_u8()?;
-        if flags > 0b11 {
-            bail!(reader.original_position() - 1, "malformed global flags")
+        if reader.features().shared_everything_threads() {
+            if flags > 0b11 {
+                bail!(reader.original_position() - 1, "malformed global flags")
+            }
+        } else {
+            if flags > 0b1 {
+                bail!(
+                    reader.original_position() - 1,
+                    "malformed mutability -- or shared globals \
+                     require the shared-everything-threads proposal"
+                )
+            }
         }
         Ok(GlobalType {
             content_type,
diff --git a/crates/wasmparser/src/readers/core/types.rs b/crates/wasmparser/src/readers/core/types.rs
index d015f035..3297a269 100644
--- a/crates/wasmparser/src/readers/core/types.rs
+++ b/crates/wasmparser/src/readers/core/types.rs
@@ -21,6 +21,7 @@ use crate::prelude::*;
 #[cfg(feature = "validate")]
 use crate::types::CoreTypeId;
 use crate::{BinaryReader, BinaryReaderError, FromReader, Result, SectionLimited};
+use core::cmp::Ordering;
 use core::fmt::{self, Debug};
 use core::hash::{Hash, Hasher};
 
@@ -58,7 +59,7 @@ pub(crate) use self::matches::{Matches, WithRecGroup};
 // * `01`: The `index` is an index into the containing type's recursion group.
 //
 // * `10`: The `index` is a `CoreTypeId`.
-#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct PackedIndex(u32);
 
 // Assert that we can fit indices up to `MAX_WASM_TYPES` inside `RefType`.
@@ -428,8 +429,22 @@ impl PartialEq for RecGroup {
 
 impl Eq for RecGroup {}
 
+impl Ord for RecGroup {
+    fn cmp(&self, other: &Self) -> Ordering {
+        let self_tys = self.types();
+        let other_tys = other.types();
+        self_tys.cmp(other_tys)
+    }
+}
+
+impl PartialOrd for RecGroup {
+    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 /// Represents a subtype of possible other types in a WebAssembly module.
-#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
 pub struct SubType {
     /// Is the subtype final.
     pub is_final: bool,
@@ -511,7 +526,7 @@ impl SubType {
 }
 
 /// Represents a composite type in a WebAssembly module.
-#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
 pub enum CompositeType {
     /// The type is for a function.
     Func(FuncType),
@@ -558,7 +573,7 @@ impl CompositeType {
 }
 
 /// Represents a type of a function in a WebAssembly module.
-#[derive(Clone, Eq, PartialEq, Hash)]
+#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 pub struct FuncType {
     /// The combined parameters and result types.
     params_results: Box<[ValType]>,
@@ -657,11 +672,11 @@ impl FuncType {
 }
 
 /// Represents a type of an array in a WebAssembly module.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 pub struct ArrayType(pub FieldType);
 
 /// Represents a field type of an array or a struct.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 pub struct FieldType {
     /// Array element type.
     pub element_type: StorageType,
@@ -684,7 +699,7 @@ impl FieldType {
 }
 
 /// Represents storage types introduced in the GC spec for array and struct fields.
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum StorageType {
     /// The storage type is i8.
     I8,
@@ -725,14 +740,14 @@ impl StorageType {
 }
 
 /// Represents a type of a struct in a WebAssembly module.
-#[derive(Debug, Clone, Eq, PartialEq, Hash)]
+#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 pub struct StructType {
     /// Struct fields.
     pub fields: Box<[FieldType]>,
 }
 
 /// Represents the types of values in a WebAssembly module.
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum ValType {
     /// The value type is i32.
     I32,
@@ -883,7 +898,7 @@ impl ValType {
 //
 //   0000 = none
 //   ```
-#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct RefType([u8; 3]);
 
 impl fmt::Debug for RefType {
diff --git a/crates/wasmparser/src/validator.rs b/crates/wasmparser/src/validator.rs
index df86eed9..5902b925 100644
--- a/crates/wasmparser/src/validator.rs
+++ b/crates/wasmparser/src/validator.rs
@@ -455,7 +455,9 @@ impl Validator {
     pub fn validate_all(&mut self, bytes: &[u8]) -> Result<Types> {
         let mut functions_to_validate = Vec::new();
         let mut last_types = None;
-        for payload in Parser::new(0).parse_all(bytes) {
+        let mut parser = Parser::new(0);
+        parser.set_features(self.features);
+        for payload in parser.parse_all(bytes) {
             match self.payload(&payload?)? {
                 ValidPayload::Func(a, b) => {
                     functions_to_validate.push((a, b));
diff --git a/crates/wasmparser/src/validator/component.rs b/crates/wasmparser/src/validator/component.rs
index 13aa18e8..f013aa3f 100644
--- a/crates/wasmparser/src/validator/component.rs
+++ b/crates/wasmparser/src/validator/component.rs
@@ -10,6 +10,7 @@ use super::{
         ModuleType, RecordType, Remapping, ResourceId, TypeAlloc, TypeList, VariantCase,
     },
 };
+use crate::collections::index_map::Entry;
 use crate::prelude::*;
 use crate::validator::names::{ComponentName, ComponentNameKind, KebabStr, KebabString};
 use crate::{
@@ -25,7 +26,6 @@ use crate::{
     WasmFeatures,
 };
 use core::mem;
-use indexmap::map::Entry;
 
 fn to_kebab_str<'a>(s: &'a str, desc: &str, offset: usize) -> Result<&'a KebabStr> {
     match KebabStr::new(s) {
@@ -152,10 +152,10 @@ pub(crate) struct ComponentState {
     ///
     /// This set is consulted whenever an exported item is added since all
     /// referenced types must be members of this set.
-    exported_types: HashSet<ComponentAnyTypeId>,
+    exported_types: Set<ComponentAnyTypeId>,
 
     /// Same as `exported_types`, but for imports.
-    imported_types: HashSet<ComponentAnyTypeId>,
+    imported_types: Set<ComponentAnyTypeId>,
 
     /// The set of top-level resource exports and their names.
     ///
@@ -185,7 +185,7 @@ pub enum ComponentKind {
 struct ComponentNameContext {
     /// A map from a resource type id to an index in the `all_resource_names`
     /// set for the name of that resource.
-    resource_name_map: HashMap<AliasableResourceId, usize>,
+    resource_name_map: Map<AliasableResourceId, usize>,
 
     /// All known resource names in this context, used to validate static method
     /// names to by ensuring that static methods' resource names are somewhere
@@ -669,7 +669,7 @@ impl ComponentState {
         &self,
         types: &TypeAlloc,
         id: ComponentAnyTypeId,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         match id {
             // Resource types, in isolation, are always valid to import or
@@ -694,7 +694,7 @@ impl ComponentState {
         &self,
         types: &TypeAlloc,
         id: ComponentInstanceTypeId,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         // Instances must recursively have all referenced types named.
         let ty = &types[id];
@@ -719,7 +719,7 @@ impl ComponentState {
         &self,
         types: &TypeAlloc,
         id: ComponentDefinedTypeId,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         let ty = &types[id];
         match ty {
@@ -766,7 +766,7 @@ impl ComponentState {
         &self,
         types: &TypeAlloc,
         id: ComponentFuncTypeId,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         let ty = &types[id];
         // Function types must have all their parameters/results named.
@@ -1656,14 +1656,15 @@ impl ComponentState {
     ) -> Result<ComponentFuncType> {
         let mut info = TypeInfo::new();
 
-        let mut set = HashSet::default();
+        let mut set = Set::default();
+        #[cfg(not(feature = "no-hash-maps"))] // TODO: remove when unified map type is available
         set.reserve(core::cmp::max(ty.params.len(), ty.results.type_count()));
 
         let params = ty
             .params
             .iter()
             .map(|(name, ty)| {
-                let name = to_kebab_str(name, "function parameter", offset)?;
+                let name: &KebabStr = to_kebab_str(name, "function parameter", offset)?;
                 if !set.insert(name) {
                     bail!(
                         offset,
@@ -3211,7 +3212,7 @@ mod append_only {
 
     impl<K, V> IndexMapAppendOnly<K, V>
     where
-        K: Hash + Eq + PartialEq,
+        K: Hash + Eq + Ord + PartialEq + Clone,
     {
         pub fn insert(&mut self, key: K, value: V) {
             let prev = self.0.insert(key, value);
diff --git a/crates/wasmparser/src/validator/core.rs b/crates/wasmparser/src/validator/core.rs
index 0f11fd48..a36d958a 100644
--- a/crates/wasmparser/src/validator/core.rs
+++ b/crates/wasmparser/src/validator/core.rs
@@ -525,7 +525,7 @@ pub(crate) struct Module {
     // Stores indexes into `types`.
     pub functions: Vec<u32>,
     pub tags: Vec<CoreTypeId>,
-    pub function_references: HashSet<u32>,
+    pub function_references: Set<u32>,
     pub imports: IndexMap<(String, String), Vec<EntityType>>,
     pub exports: IndexMap<String, EntityType>,
     pub type_size: u32,
diff --git a/crates/wasmparser/src/validator/names.rs b/crates/wasmparser/src/validator/names.rs
index 86fd813f..66f9c311 100644
--- a/crates/wasmparser/src/validator/names.rs
+++ b/crates/wasmparser/src/validator/names.rs
@@ -4,6 +4,7 @@
 use crate::prelude::*;
 use crate::{Result, WasmFeatures};
 use core::borrow::Borrow;
+use core::cmp::Ordering;
 use core::fmt;
 use core::hash::{Hash, Hasher};
 use core::ops::Deref;
@@ -101,6 +102,20 @@ impl PartialEq<KebabString> for KebabStr {
     }
 }
 
+impl Ord for KebabStr {
+    fn cmp(&self, other: &Self) -> Ordering {
+        let self_chars = self.chars().map(|c| c.to_ascii_lowercase());
+        let other_chars = other.chars().map(|c| c.to_ascii_lowercase());
+        self_chars.cmp(other_chars)
+    }
+}
+
+impl PartialOrd for KebabStr {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl Hash for KebabStr {
     fn hash<H: Hasher>(&self, state: &mut H) {
         self.len().hash(state);
@@ -175,6 +190,18 @@ impl Borrow<KebabStr> for KebabString {
     }
 }
 
+impl Ord for KebabString {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.as_kebab_str().cmp(other.as_kebab_str())
+    }
+}
+
+impl PartialOrd for KebabString {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.as_kebab_str().partial_cmp(other.as_kebab_str())
+    }
+}
+
 impl PartialEq for KebabString {
     fn eq(&self, other: &Self) -> bool {
         self.as_kebab_str().eq(other.as_kebab_str())
@@ -230,7 +257,7 @@ pub struct ComponentName {
     kind: ParsedComponentNameKind,
 }
 
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 enum ParsedComponentNameKind {
     Label,
     Constructor,
@@ -347,6 +374,18 @@ impl PartialEq for ComponentName {
 
 impl Eq for ComponentName {}
 
+impl Ord for ComponentName {
+    fn cmp(&self, other: &ComponentName) -> Ordering {
+        self.kind().cmp(&other.kind())
+    }
+}
+
+impl PartialOrd for ComponentName {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.kind.partial_cmp(&other.kind)
+    }
+}
+
 impl fmt::Display for ComponentName {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         self.raw.fmt(f)
@@ -359,6 +398,54 @@ impl fmt::Debug for ComponentName {
     }
 }
 
+impl ComponentNameKind<'_> {
+    /// Returns the [`ParsedComponentNameKind`] of the [`ComponentNameKind`].
+    fn kind(&self) -> ParsedComponentNameKind {
+        match self {
+            Self::Label(_) => ParsedComponentNameKind::Label,
+            Self::Constructor(_) => ParsedComponentNameKind::Constructor,
+            Self::Method(_) => ParsedComponentNameKind::Method,
+            Self::Static(_) => ParsedComponentNameKind::Static,
+            Self::Interface(_) => ParsedComponentNameKind::Interface,
+            Self::Dependency(_) => ParsedComponentNameKind::Dependency,
+            Self::Url(_) => ParsedComponentNameKind::Url,
+            Self::Hash(_) => ParsedComponentNameKind::Hash,
+        }
+    }
+}
+
+impl Ord for ComponentNameKind<'_> {
+    fn cmp(&self, other: &Self) -> Ordering {
+        match self.kind().cmp(&other.kind()) {
+            Ordering::Equal => (),
+            unequal => return unequal,
+        }
+        match (self, other) {
+            (ComponentNameKind::Label(lhs), ComponentNameKind::Label(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Constructor(lhs), ComponentNameKind::Constructor(rhs)) => {
+                lhs.cmp(rhs)
+            }
+            (ComponentNameKind::Method(lhs), ComponentNameKind::Method(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Method(lhs), ComponentNameKind::Static(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Static(lhs), ComponentNameKind::Method(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Static(lhs), ComponentNameKind::Static(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Interface(lhs), ComponentNameKind::Interface(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Dependency(lhs), ComponentNameKind::Dependency(rhs)) => {
+                lhs.cmp(rhs)
+            }
+            (ComponentNameKind::Url(lhs), ComponentNameKind::Url(rhs)) => lhs.cmp(rhs),
+            (ComponentNameKind::Hash(lhs), ComponentNameKind::Hash(rhs)) => lhs.cmp(rhs),
+            _ => unreachable!("already compared for different kinds above"),
+        }
+    }
+}
+
+impl PartialOrd for ComponentNameKind<'_> {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl Hash for ComponentNameKind<'_> {
     fn hash<H: Hasher>(&self, hasher: &mut H) {
         use ComponentNameKind::*;
@@ -409,7 +496,7 @@ impl PartialEq for ComponentNameKind<'_> {
 impl Eq for ComponentNameKind<'_> {}
 
 /// A resource name and its function, stored as `a.b`.
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
 pub struct ResourceFunc<'a>(&'a str);
 
 impl<'a> ResourceFunc<'a> {
@@ -426,7 +513,7 @@ impl<'a> ResourceFunc<'a> {
 }
 
 /// An interface name, stored as `a:b/c@1.2.3`
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
 pub struct InterfaceName<'a>(&'a str);
 
 impl<'a> InterfaceName<'a> {
@@ -471,7 +558,7 @@ impl<'a> InterfaceName<'a> {
 
 /// A dependency on an implementation either as `locked-dep=...` or
 /// `unlocked-dep=...`
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
 pub struct DependencyName<'a>(&'a str);
 
 impl<'a> DependencyName<'a> {
@@ -483,7 +570,7 @@ impl<'a> DependencyName<'a> {
 
 /// A dependency on an implementation either as `url=...` or
 /// `relative-url=...`
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
 pub struct UrlName<'a>(&'a str);
 
 impl<'a> UrlName<'a> {
@@ -494,7 +581,7 @@ impl<'a> UrlName<'a> {
 }
 
 /// A dependency on an implementation either as `integrity=...`.
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
 pub struct HashName<'a>(&'a str);
 
 impl<'a> HashName<'a> {
diff --git a/crates/wasmparser/src/validator/types.rs b/crates/wasmparser/src/validator/types.rs
index 5403b0cd..5a9892d7 100644
--- a/crates/wasmparser/src/validator/types.rs
+++ b/crates/wasmparser/src/validator/types.rs
@@ -4,6 +4,7 @@ use super::{
     component::{ComponentState, ExternKind},
     core::Module,
 };
+use crate::collections::map::Entry;
 use crate::prelude::*;
 use crate::{validator::names::KebabString, HeapType, ValidatorId};
 use crate::{
@@ -19,7 +20,6 @@ use core::{
     hash::{Hash, Hasher},
     mem,
 };
-use hashbrown::hash_map::Entry;
 
 /// The maximum number of parameters in the canonical ABI that can be passed by value.
 ///
@@ -201,7 +201,7 @@ macro_rules! define_type_id {
         #[doc = "Represents a unique identifier for a "]
         #[doc = $type_str]
         #[doc = " type known to a [`crate::Validator`]."]
-        #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+        #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
         #[repr(C)] // Use fixed field layout to ensure minimal size.
         pub struct $name {
             /// The index into the associated list of types.
@@ -258,7 +258,7 @@ pub enum CoreType {
 
 /// Represents a unique identifier for a core type type known to a
 /// [`crate::Validator`]
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 #[repr(C)]
 pub struct CoreTypeId {
     index: u32,
@@ -426,7 +426,7 @@ macro_rules! define_transitive_conversions {
 
 define_wrapper_id! {
     /// An identifier pointing to any kind of type, component or core.
-    #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
     pub enum AnyTypeId {
         #[unwrap = unwrap_component_core_type]
         /// A core type.
@@ -461,7 +461,7 @@ impl AnyTypeId {
 
 define_wrapper_id! {
     /// An identifier for a core type or a core module's type.
-    #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
     pub enum ComponentCoreTypeId {
         #[unwrap = unwrap_sub]
         /// A core type.
@@ -485,7 +485,7 @@ impl ComponentCoreTypeId {
 }
 
 /// An aliasable resource identifier.
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 pub struct AliasableResourceId {
     id: ResourceId,
     alias_id: u32,
@@ -523,7 +523,7 @@ impl AliasableResourceId {
 
 define_wrapper_id! {
     /// An identifier for any kind of component type.
-    #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
     pub enum ComponentAnyTypeId {
         #[unwrap = unwrap_resource]
         /// The type is a resource with the specified id.
@@ -646,7 +646,7 @@ define_type_id!(
 
 /// Represents a unique identifier for a component type type known to a
 /// [`crate::Validator`].
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 #[repr(C)]
 pub struct ComponentDefinedTypeId {
     index: u32,
@@ -712,7 +712,7 @@ impl Aliasable for ComponentDefinedTypeId {
 /// information, and then one more bit is used for whether or not a borrow is
 /// used. Currently this uses the low 24 bits for the type size and the MSB for
 /// the borrow bit.
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 // Only public because it shows up in a public trait's `doc(hidden)` method.
 #[doc(hidden)]
 pub struct TypeInfo(u32);
@@ -871,6 +871,22 @@ impl PartialEq for (dyn ModuleImportKey + '_) {
 
 impl Eq for (dyn ModuleImportKey + '_) {}
 
+impl Ord for (dyn ModuleImportKey + '_) {
+    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
+        match self.module().cmp(other.module()) {
+            core::cmp::Ordering::Equal => (),
+            order => return order,
+        };
+        self.name().cmp(other.name())
+    }
+}
+
+impl PartialOrd for (dyn ModuleImportKey + '_) {
+    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl ModuleImportKey for (String, String) {
     fn module(&self) -> &str {
         &self.0
@@ -2426,7 +2442,7 @@ impl<T> Default for SnapshotList<T> {
 #[doc(hidden)]
 pub struct TypeList {
     // Keeps track of which `alias_id` is an alias of which other `alias_id`.
-    alias_mappings: HashMap<u32, u32>,
+    alias_mappings: Map<u32, u32>,
     // Counter for generating new `alias_id`s.
     alias_counter: u32,
     // Snapshots of previously committed `TypeList`s' aliases.
@@ -2451,7 +2467,7 @@ pub struct TypeList {
     //
     // This is `None` when a list is "committed" meaning that no more insertions
     // can happen.
-    canonical_rec_groups: Option<HashMap<RecGroup, RecGroupId>>,
+    canonical_rec_groups: Option<Map<RecGroup, RecGroupId>>,
 
     // Component model types.
     components: SnapshotList<ComponentType>,
@@ -2469,7 +2485,7 @@ struct TypeListAliasSnapshot {
     alias_counter: u32,
 
     // The alias mappings in this snapshot.
-    alias_mappings: HashMap<u32, u32>,
+    alias_mappings: Map<u32, u32>,
 }
 
 struct TypeListCheckpoint {
@@ -2885,7 +2901,7 @@ impl TypeList {
         });
 
         TypeList {
-            alias_mappings: HashMap::default(),
+            alias_mappings: Map::default(),
             alias_counter: self.alias_counter,
             alias_snapshots: self.alias_snapshots.clone(),
             core_types: self.core_types.commit(),
@@ -3197,7 +3213,7 @@ impl TypeAlloc {
     pub(crate) fn type_named_type_id(
         &self,
         id: ComponentDefinedTypeId,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         let ty = &self[id];
         match ty {
@@ -3240,7 +3256,7 @@ impl TypeAlloc {
     pub(crate) fn type_named_valtype(
         &self,
         ty: &ComponentValType,
-        set: &HashSet<ComponentAnyTypeId>,
+        set: &Set<ComponentAnyTypeId>,
     ) -> bool {
         match ty {
             ComponentValType::Primitive(_) => true,
@@ -3516,12 +3532,12 @@ where
 #[derive(Debug, Default)]
 pub struct Remapping {
     /// A mapping from old resource ID to new resource ID.
-    pub(crate) resources: HashMap<ResourceId, ResourceId>,
+    pub(crate) resources: Map<ResourceId, ResourceId>,
 
     /// A mapping filled in during the remapping process which records how a
     /// type was remapped, if applicable. This avoids remapping multiple
     /// references to the same type and instead only processing it once.
-    types: HashMap<ComponentAnyTypeId, ComponentAnyTypeId>,
+    types: Map<ComponentAnyTypeId, ComponentAnyTypeId>,
 }
 
 impl Remap for TypeAlloc {
@@ -4086,7 +4102,7 @@ impl<'a> SubtypeCx<'a> {
                 None => bail!(offset, "missing {} named `{name}`", kind.desc()),
             }
         }
-        let mut type_map = HashMap::default();
+        let mut type_map = Map::default();
         for (i, (actual, expected)) in to_typecheck.into_iter().enumerate() {
             let result = self.with_checkpoint(|this| {
                 let mut expected = expected;
@@ -4381,7 +4397,7 @@ impl<'a> SubtypeCx<'a> {
         &self,
         actual: ComponentEntityType,
         expected: ComponentEntityType,
-        type_map: &mut HashMap<ComponentAnyTypeId, ComponentAnyTypeId>,
+        type_map: &mut Map<ComponentAnyTypeId, ComponentAnyTypeId>,
     ) {
         match (expected, actual) {
             (
diff --git a/crates/wasmprinter/Cargo.toml b/crates/wasmprinter/Cargo.toml
index 90859b74..802dcccd 100644
--- a/crates/wasmprinter/Cargo.toml
+++ b/crates/wasmprinter/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wasmprinter"
 description = """
 Rust converter from the WebAssembly binary format to the text format.
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wast/Cargo.toml b/crates/wast/Cargo.toml
index 981c9f43..f7f82aee 100644
--- a/crates/wast/Cargo.toml
+++ b/crates/wast/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wast"
 description = """
 Customizable Rust parsers for the WebAssembly Text formats WAT and WAST
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wast/src/lib.rs b/crates/wast/src/lib.rs
index c995b857..fa741d08 100644
--- a/crates/wast/src/lib.rs
+++ b/crates/wast/src/lib.rs
@@ -347,12 +347,16 @@ pub mod lexer;
 pub mod parser;
 pub mod token;
 
+#[cfg(feature = "wasm-module")]
 mod encode;
 mod error;
+#[cfg(feature = "wasm-module")]
 mod gensym;
+#[cfg(feature = "wasm-module")]
 mod names;
 pub use self::error::*;
 
+#[cfg(feature = "wasm-module")]
 macro_rules! id {
     ($($t:tt)*) => ($($t)*)
 }
diff --git a/crates/wast/src/parser.rs b/crates/wast/src/parser.rs
index 7a20ebe2..cb65502b 100644
--- a/crates/wast/src/parser.rs
+++ b/crates/wast/src/parser.rs
@@ -82,6 +82,7 @@ use std::usize;
 /// modules/components which be far trickier. For now we just say that when
 /// the parser goes too deep we return an error saying there's too many
 /// nested items. It would be great to not return an error here, though!
+#[cfg(feature = "wasm-module")]
 pub(crate) const MAX_PARENS_DEPTH: usize = 100;
 
 /// A top-level convenience parsing function that parses a `T` from `buf` and
@@ -483,6 +484,7 @@ impl<'a> Parser<'a> {
         }
     }
 
+    #[cfg(feature = "wasm-module")]
     pub(crate) fn has_meaningful_tokens(self) -> bool {
         self.buf.lexer.iter(0).any(|t| match t {
             Ok(token) => !matches!(
@@ -759,6 +761,7 @@ impl<'a> Parser<'a> {
     }
 
     /// Checks that the parser parens depth hasn't exceeded the maximum depth.
+    #[cfg(feature = "wasm-module")]
     pub(crate) fn depth_check(&self) -> Result<()> {
         if self.parens_depth() > MAX_PARENS_DEPTH {
             Err(self.error("item nesting too deep"))
diff --git a/crates/wast/src/token.rs b/crates/wast/src/token.rs
index b2963410..8094183d 100644
--- a/crates/wast/src/token.rs
+++ b/crates/wast/src/token.rs
@@ -75,6 +75,7 @@ impl<'a> Id<'a> {
         }
     }
 
+    #[cfg(feature = "wasm-module")]
     pub(crate) fn gensym(span: Span, gen: u32) -> Id<'a> {
         Id {
             name: "gensym",
@@ -95,6 +96,7 @@ impl<'a> Id<'a> {
         self.span
     }
 
+    #[cfg(feature = "wasm-module")]
     pub(crate) fn is_gensym(&self) -> bool {
         self.gen != 0
     }
@@ -180,6 +182,7 @@ impl Index<'_> {
         }
     }
 
+    #[cfg(feature = "wasm-module")]
     pub(crate) fn is_resolved(&self) -> bool {
         matches!(self, Index::Num(..))
     }
diff --git a/crates/wat/Cargo.toml b/crates/wat/Cargo.toml
index 143a8d6c..af07f43a 100644
--- a/crates/wat/Cargo.toml
+++ b/crates/wat/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wat"
 description = """
 Rust parser for the WebAssembly Text format, WAT
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wit-component/Cargo.toml b/crates/wit-component/Cargo.toml
index 4bf0f129..8bd969c4 100644
--- a/crates/wit-component/Cargo.toml
+++ b/crates/wit-component/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wit-component"
 description = """
 Tooling for working with `*.wit` and component files together.
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wit-component/dl/Cargo.toml b/crates/wit-component/dl/Cargo.toml
index 2c192015..6d52bfc8 100644
--- a/crates/wit-component/dl/Cargo.toml
+++ b/crates/wit-component/dl/Cargo.toml
@@ -1,10 +1,11 @@
 [package]
 name = "dl"
 version = "0.1.0"
-edition = "2021"
+edition.workspace = true
 publish = false
+rust-version.workspace = true
 
 [lib]
 crate-type = [ "staticlib" ]
-
-[dependencies]
+test = false
+doctest = false
diff --git a/crates/wit-parser/Cargo.toml b/crates/wit-parser/Cargo.toml
index 55c27418..386be969 100644
--- a/crates/wit-parser/Cargo.toml
+++ b/crates/wit-parser/Cargo.toml
@@ -11,6 +11,7 @@ documentation = "https://docs.rs/wit-parser"
 description = """
 Tooling for parsing `*.wit` files and working with their contents.
 """
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/crates/wit-parser/fuzz/Cargo.toml b/crates/wit-parser/fuzz/Cargo.toml
index 734cdb48..f3a20af2 100644
--- a/crates/wit-parser/fuzz/Cargo.toml
+++ b/crates/wit-parser/fuzz/Cargo.toml
@@ -2,6 +2,7 @@
 name = "wit-parser-fuzz"
 publish = false
 edition.workspace = true
+rust-version.workspace = true
 
 [package.metadata]
 cargo-fuzz = true
diff --git a/crates/wit-parser/src/decoding.rs b/crates/wit-parser/src/decoding.rs
index d36235ad..8c3c9e01 100644
--- a/crates/wit-parser/src/decoding.rs
+++ b/crates/wit-parser/src/decoding.rs
@@ -585,7 +585,7 @@ impl WitPackageDecoder<'_> {
     fn decode_interface<'a>(
         &mut self,
         name: &str,
-        imports: &wasmparser::map::IndexMap<String, types::ComponentEntityType>,
+        imports: &wasmparser::collections::IndexMap<String, types::ComponentEntityType>,
         ty: &types::ComponentInstanceType,
         fields: &mut PackageFields<'a>,
     ) -> Result<PackageName> {
diff --git a/crates/wit-smith/Cargo.toml b/crates/wit-smith/Cargo.toml
index 16c2c15c..3956466d 100644
--- a/crates/wit-smith/Cargo.toml
+++ b/crates/wit-smith/Cargo.toml
@@ -6,6 +6,7 @@ license = "Apache-2.0 WITH LLVM-exception"
 name = "wit-smith"
 repository = "https://github.com/bytecodealliance/wasm-tools/tree/main/crates/wit-smith"
 version.workspace = true
+rust-version.workspace = true
 
 [lints]
 workspace = true
diff --git a/fuzz/Cargo.toml b/fuzz/Cargo.toml
index 9175f957..c85c29c7 100644
--- a/fuzz/Cargo.toml
+++ b/fuzz/Cargo.toml
@@ -2,6 +2,7 @@
 name = "wasm-tools-fuzz"
 publish = false
 edition.workspace = true
+rust-version.workspace = true
 
 [package.metadata]
 cargo-fuzz = true
diff --git a/src/bin/wasm-tools/main.rs b/src/bin/wasm-tools/main.rs
index 1a084b54..8d2cce14 100644
--- a/src/bin/wasm-tools/main.rs
+++ b/src/bin/wasm-tools/main.rs
@@ -76,6 +76,9 @@ subcommands! {
     (json_from_wast, "json-from-wast")
 }
 
+// when all features are disabled then `WasmTools` is an empty enum so suppress
+// some lints about how rustc detects that everything afterwards is unreachable.
+#[allow(unreachable_code, unused_variables)]
 fn main() -> ExitCode {
     let args = <WasmTools as Parser>::parse();
     args.general_opts().init_logger();


Test patch:
diff --git a/crates/wasmparser/src/collections/index_map/tests.rs b/crates/wasmparser/src/collections/index_map/tests.rs
new file mode 100644
index 00000000..b024081e
--- /dev/null
+++ b/crates/wasmparser/src/collections/index_map/tests.rs
@@ -0,0 +1,183 @@
+use super::detail::{Entry, IndexMap};
+
+type TestMap = IndexMap<char, i32>;
+
+fn assert_get(map: &mut TestMap, key: char, expected: impl Into<Option<(usize, i32)>>) {
+    let mut expected = expected.into();
+    assert_eq!(map.contains_key(&key), expected.is_some());
+    assert_eq!(
+        map.get(&key),
+        expected.as_ref().map(|(_index, value)| value)
+    );
+    assert_eq!(
+        map.get_key_value(&key),
+        expected.as_ref().map(|(_index, value)| (&key, value))
+    );
+    assert_eq!(
+        map.get_full(&key),
+        expected
+            .as_ref()
+            .map(|(index, value)| (*index, &key, value))
+    );
+    assert_eq!(
+        map.get_index_of(&key),
+        expected.map(|(index, _value)| index)
+    );
+    if let Some((index, _value)) = expected {
+        assert_eq!(
+            map.get_index(index),
+            expected.as_ref().map(|(_index, value)| (&key, value))
+        );
+        assert_eq!(
+            map.get_index_mut(index),
+            expected.as_mut().map(|(_index, value)| (&key, value))
+        );
+    }
+}
+
+#[test]
+fn new_works() {
+    let mut map = <IndexMap<char, i32>>::new();
+    assert!(map.is_empty());
+    assert_eq!(map.len(), 0);
+    assert!(map.iter().eq([]));
+    assert!(map.keys().eq([].iter()));
+    assert!(map.values().eq([].iter()));
+    assert!(map.values_mut().eq([].iter()));
+    assert!(map.iter_mut().eq([]));
+    assert!(map.into_iter().eq([]));
+}
+
+#[test]
+fn insert_works() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let (k0, None) = map.insert_full('a', 10) else {
+        panic!()
+    };
+    assert_get(&mut map, 'a', (k0, 10));
+    let (k1, None) = map.insert_full('b', 20) else {
+        panic!()
+    };
+    assert_get(&mut map, 'b', (k1, 20));
+    assert_eq!(map.insert('a', 30), Some(10));
+    assert_get(&mut map, 'a', (k0, 30));
+    assert_eq!(map.len(), 2);
+    assert!(!map.is_empty());
+}
+
+#[test]
+fn extend_works() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let mut values = [('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)];
+    map.extend(values);
+    assert!(!map.is_empty());
+    assert_eq!(map.len(), values.len());
+    for (index, (key, value)) in values.into_iter().enumerate() {
+        assert_get(&mut map, key, (index, value));
+    }
+    assert!(map.iter().eq(values.iter().map(|(k, v)| (k, v))));
+    assert!(map.iter_mut().eq(values.iter_mut().map(|(k, v)| (&*k, v))));
+    assert!(map.keys().eq(values.iter().map(|(k, _v)| k)));
+    assert!(map.values().eq(values.iter().map(|(_k, v)| v)));
+    assert!(map.values_mut().eq(values.iter_mut().map(|(_k, v)| v)));
+    assert!(map.into_iter().eq(values));
+}
+
+#[test]
+fn clear_works() {
+    let mut map = <IndexMap<char, i32>>::new();
+    map.extend([('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)]);
+    map.clear();
+    assert!(map.is_empty());
+    assert_eq!(map.len(), 0);
+    assert!(map.iter().eq([]));
+    assert!(map.keys().eq([].iter()));
+    assert!(map.values().eq([].iter()));
+    assert!(map.values_mut().eq([].iter()));
+    assert!(map.iter_mut().eq([]));
+    assert!(map.into_iter().eq([]));
+}
+
+#[test]
+fn swap_remove_works_ascending() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let values = [('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)];
+    map.extend(values);
+    assert_eq!(map.swap_remove_full(&'a'), Some((0, 'a', 0))); // moves 'f' to 0
+    assert_eq!(map.swap_remove(&'a'), None);
+    assert_eq!(map.swap_remove_full(&'b'), Some((1, 'b', 1))); // moves 'e' to 1
+    assert_eq!(map.swap_remove(&'b'), None);
+    assert_eq!(map.swap_remove_full(&'c'), Some((2, 'c', 2))); // moves 'd' to 2
+    assert_eq!(map.swap_remove(&'c'), None);
+    assert_eq!(map.swap_remove_full(&'d'), Some((2, 'd', 3)));
+    assert_eq!(map.swap_remove(&'d'), None);
+    assert_eq!(map.swap_remove_full(&'e'), Some((1, 'e', 4)));
+    assert_eq!(map.swap_remove(&'e'), None);
+    assert_eq!(map.swap_remove_full(&'f'), Some((0, 'f', 5)));
+    assert_eq!(map.swap_remove(&'f'), None);
+    for (key, _value) in values {
+        assert_get(&mut map, key, None);
+    }
+}
+
+#[test]
+fn swap_remove_works_descending() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let values = [('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)];
+    map.extend(values);
+    assert_eq!(map.swap_remove_full(&'f'), Some((5, 'f', 5)));
+    assert_eq!(map.swap_remove(&'f'), None);
+    assert_eq!(map.swap_remove_full(&'e'), Some((4, 'e', 4)));
+    assert_eq!(map.swap_remove(&'e'), None);
+    assert_eq!(map.swap_remove_full(&'d'), Some((3, 'd', 3)));
+    assert_eq!(map.swap_remove(&'d'), None);
+    assert_eq!(map.swap_remove_full(&'c'), Some((2, 'c', 2)));
+    assert_eq!(map.swap_remove(&'c'), None);
+    assert_eq!(map.swap_remove_full(&'b'), Some((1, 'b', 1)));
+    assert_eq!(map.swap_remove(&'b'), None);
+    assert_eq!(map.swap_remove_full(&'a'), Some((0, 'a', 0)));
+    assert_eq!(map.swap_remove(&'a'), None);
+    for (key, _value) in values {
+        assert_get(&mut map, key, None);
+    }
+}
+
+#[test]
+fn entry_works_occupied() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let values = [('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)];
+    map.extend(values);
+    for (key, mut value) in values {
+        match map.entry(key) {
+            Entry::Occupied(mut entry) => {
+                assert_eq!(entry.get(), &value);
+                assert_eq!(entry.get_mut(), &mut value);
+                assert_eq!(entry.key(), &key);
+                let new_value = value + 10;
+                assert_eq!(entry.insert(new_value), value);
+                assert_eq!(entry.get(), &new_value);
+            }
+            Entry::Vacant(_) => panic!(),
+        }
+    }
+}
+
+#[test]
+fn entry_works_vacant() {
+    let mut map = <IndexMap<char, i32>>::new();
+    let values = [('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('f', 5)];
+    for (key, mut value) in values {
+        match map.entry(key) {
+            Entry::Occupied(_) => panic!(),
+            Entry::Vacant(entry) => {
+                assert_eq!(entry.key(), &key);
+                assert_eq!(entry.insert(value), &mut value);
+            }
+        }
+    }
+    assert!(!map.is_empty());
+    assert_eq!(map.len(), values.len());
+    for (index, (key, value)) in values.into_iter().enumerate() {
+        assert_get(&mut map, key, (index, value));
+    }
+}
diff --git a/tests/roundtrip.rs b/tests/roundtrip.rs
index e4f42e2a..563ef28a 100644
--- a/tests/roundtrip.rs
+++ b/tests/roundtrip.rs
@@ -818,16 +818,6 @@ fn error_matches(error: &str, message: &str) -> bool {
         return error.starts_with("type mismatch");
     }
 
-    if message == "malformed mutability" {
-        // When parsing a global `shared` type (e.g., `global (mut shared i32)
-        // ...`), many spec tests expect a `malformed mutability` error.
-        // Previously, `0x2` was an invalid flag but it now means `shared`. We
-        // accept either (a) a new, more accurate error message or (b) a
-        // validation error instead.
-        return error.contains("malformed global flags")
-            || error.contains("require the shared-everything-threads proposal");
-    }
-
     if message == "table size must be at most 2^32-1" {
         return error.contains("invalid u32 number: constant out of range");
     }