Repository: vercel/next.js
Pull request: [turbopack] optimize RcStr parsing


`RcStr` has 3 internal forms
 * `INLINE` meaning it is small enough that the bytes are stored inline (7 bytes)
 * `STATIC` meaning it was allocated by `rcstr!` and is stored in a `static` item somewhere
 * `DYNAMIC` meaning it is stored in an `Arc`

The nice thing is that `INLINE` and `STATIC` are not ref-counted which optimizes clones.  The unfortunate thing is that serialization round trips partially defeat these optimizations.  To fix that we do two things

1. decode to a `&str` instead of a `String` so we can defer the allocation to if/when we select the `DYNAMIC` format
2. store all static strings in an inventory managed hashtable (lazily constructed) so we can match against them when deserializing them

This allows us to avoid temporary allocations during decoding for the `inline` case and completely eliminate them for the static case.  The dynamic case simply pays the cost of probing the static hash table and defers the allocation to slightly later.  The hash probe is not free but the table is small ~1500 entries, so this overhead should be negligible


Also i needed to update our `wasm-bindgen` versions to workaround https://github.com/wasm-bindgen/wasm-bindgen/issues/4446 

Changed files:
filename: Cargo.lock
patch: @@ -3638,9 +3638,9 @@ dependencies = [
 
 [[package]]
 name = "js-sys"
-version = "0.3.77"
+version = "0.3.91"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1cfaf33c695fc6e08064efbc1f72ec937429614f25eef83af942d0e227c3a28f"
+checksum = "b49715b7073f385ba4bc528e5747d02e66cb39c6146efb66b781f131f0fb399c"
 dependencies = [
  "once_cell",
  "wasm-bindgen",
@@ -9487,13 +9487,17 @@ dependencies = [
  "bincode 2.0.1",
  "bytes-str",
  "codspeed-criterion-compat",
+ "inventory",
  "napi",
  "new_debug_unreachable",
  "rustc-hash 2.1.1",
  "serde",
  "shrink-to-fit",
+ "smallvec",
  "triomphe 0.1.12",
+ "turbo-bincode",
  "turbo-tasks-hash",
+ "unty",
 ]
 
 [[package]]
@@ -11010,37 +11014,25 @@ dependencies = [
 
 [[package]]
 name = "wasm-bindgen"
-version = "0.2.100"
+version = "0.2.114"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1edc8929d7499fc4e8f0be2262a241556cfc54a0bea223790e71446f2aab1ef5"
+checksum = "6532f9a5c1ece3798cb1c2cfdba640b9b3ba884f5db45973a6f442510a87d38e"
 dependencies = [
  "cfg-if",
  "once_cell",
  "rustversion",
  "wasm-bindgen-macro",
-]
-
-[[package]]
-name = "wasm-bindgen-backend"
-version = "0.2.100"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "2f0a0651a5c2bc21487bde11ee802ccaf4c51935d0d3d42a6101f98161700bc6"
-dependencies = [
- "bumpalo",
- "log",
- "proc-macro2",
- "quote",
- "syn 2.0.104",
  "wasm-bindgen-shared",
 ]
 
 [[package]]
 name = "wasm-bindgen-futures"
-version = "0.4.50"
+version = "0.4.64"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "555d470ec0bc3bb57890405e5d4322cc9ea83cebb085523ced7be4144dac1e61"
+checksum = "e9c5522b3a28661442748e09d40924dfb9ca614b21c00d3fd135720e48b67db8"
 dependencies = [
  "cfg-if",
+ "futures-util",
  "js-sys",
  "once_cell",
  "wasm-bindgen",
@@ -11049,32 +11041,32 @@ dependencies = [
 
 [[package]]
 name = "wasm-bindgen-macro"
-version = "0.2.100"
+version = "0.2.114"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7fe63fc6d09ed3792bd0897b314f53de8e16568c2b3f7982f468c0bf9bd0b407"
+checksum = "18a2d50fcf105fb33bb15f00e7a77b772945a2ee45dcf454961fd843e74c18e6"
 dependencies = [
  "quote",
  "wasm-bindgen-macro-support",
 ]
 
 [[package]]
 name = "wasm-bindgen-macro-support"
-version = "0.2.100"
+version = "0.2.114"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8ae87ea40c9f689fc23f209965b6fb8a99ad69aeeb0231408be24920604395de"
+checksum = "03ce4caeaac547cdf713d280eda22a730824dd11e6b8c3ca9e42247b25c631e3"
 dependencies = [
+ "bumpalo",
  "proc-macro2",
  "quote",
  "syn 2.0.104",
- "wasm-bindgen-backend",
  "wasm-bindgen-shared",
 ]
 
 [[package]]
 name = "wasm-bindgen-shared"
-version = "0.2.100"
+version = "0.2.114"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1a05d73b933a847d6cccdda8f838a22ff101ad9bf93e33684f39c1f5f0eece3d"
+checksum = "75a326b8c223ee17883a4251907455a2431acc2791c98c26279376490c378c16"
 dependencies = [
  "unicode-ident",
 ]
@@ -11494,9 +11486,9 @@ dependencies = [
 
 [[package]]
 name = "web-sys"
-version = "0.3.77"
+version = "0.3.91"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "33b6dd2ef9186f1f2072e409e99cd22a975331a6b3591b12c764e0e55c60d5d2"
+checksum = "854ba17bb104abfb26ba36da9729addc7ce7f06f5c0f90f3c391f8461cca21f9"
 dependencies = [
  "js-sys",
  "wasm-bindgen",

filename: turbopack/crates/turbo-rcstr/Cargo.toml
patch: @@ -18,6 +18,10 @@ new_debug_unreachable = "1.0.6"
 shrink-to-fit = { workspace = true }
 rustc-hash = { workspace = true }
 bytes-str = { workspace = true }
+inventory = { workspace = true }
+smallvec = { workspace = true }
+turbo-bincode = { workspace = true }
+unty = { workspace = true }
 
 [target.'cfg(not(target_family = "wasm"))'.dependencies]
 napi = { workspace = true, optional = true }

filename: turbopack/crates/turbo-rcstr/src/dynamic.rs
patch: @@ -70,10 +70,16 @@ pub(crate) fn new_atom<T: AsRef<str> + Into<String>>(text: T) -> RcStr {
 
     let hash = hash_bytes(text.as_ref().as_bytes());
 
-    let entry: Arc<PrehashedString> = Arc::new(PrehashedString {
+    let prehashed = PrehashedString {
         value: Payload::String(text.into()),
         hash,
-    });
+    };
+    new_atom_from_prehashed(prehashed)
+}
+
+/// Construct a new dynamic RcStr from a PrehashedString
+pub(crate) fn new_atom_from_prehashed(prehashed: PrehashedString) -> RcStr {
+    let entry: Arc<PrehashedString> = Arc::new(prehashed);
     let entry = Arc::into_raw(entry);
 
     let ptr: NonNull<PrehashedString> = unsafe {

filename: turbopack/crates/turbo-rcstr/src/lib.rs
patch: @@ -1,30 +1,34 @@
 use std::{
     borrow::{Borrow, Cow},
+    collections::HashMap,
     ffi::OsStr,
     fmt::{Debug, Display},
     hash::{Hash, Hasher},
     mem::{ManuallyDrop, forget},
     num::NonZeroU8,
     ops::Deref,
     path::{Path, PathBuf},
+    sync::LazyLock,
 };
 
 use bincode::{
     Decode, Encode,
-    de::Decoder,
+    de::{Decoder, read::Reader},
     enc::Encoder,
     error::{DecodeError, EncodeError},
     impl_borrow_decode,
 };
 use bytes_str::BytesStr;
 use debug_unreachable::debug_unreachable;
+use rustc_hash::FxBuildHasher;
 use serde::{Deserialize, Deserializer, Serialize, Serializer};
 use shrink_to_fit::ShrinkToFit;
+use smallvec::SmallVec;
 use triomphe::Arc;
 use turbo_tasks_hash::{DeterministicHash, DeterministicHasher};
 
 use crate::{
-    dynamic::{deref_from, hash_bytes, new_atom},
+    dynamic::{deref_from, hash_bytes, new_atom, new_atom_from_prehashed, new_static_atom},
     tagged_value::TaggedValue,
 };
 
@@ -159,6 +163,32 @@ impl RcStr {
     pub fn map(self, f: impl FnOnce(String) -> String) -> Self {
         RcStr::from(Cow::Owned(f(self.into_owned())))
     }
+
+    /// Create an RcStr from a deserialized string, checking the static constant
+    /// table first. If the string matches an `rcstr!` constant, returns a
+    /// zero-cost static copy instead of allocating a new Arc.
+    ///
+    /// Accepts `&str` so that borrow-decode paths can avoid heap allocation
+    /// entirely for inline strings (≤6 bytes) and static table hits.
+    fn from_deserialized(s: &str) -> Self {
+        let len = s.len();
+        if len >= tagged_value::MAX_INLINE_LEN {
+            let hash = hash_bytes(s.as_bytes());
+            // Check the static table
+            if let Some(entries) = STATIC_TABLE.get(&hash)
+                && let Some(static_phs) = entries.iter().find(|phs| phs.value.as_str() == s)
+            {
+                new_static_atom(static_phs)
+            } else {
+                new_atom_from_prehashed(PrehashedString {
+                    hash,
+                    value: dynamic::Payload::String(s.into()),
+                })
+            }
+        } else {
+            inline_atom(s).unwrap()
+        }
+    }
 }
 
 impl DeterministicHash for RcStr {
@@ -377,8 +407,25 @@ impl Serialize for RcStr {
 
 impl<'de> Deserialize<'de> for RcStr {
     fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
-        let s = String::deserialize(deserializer)?;
-        Ok(RcStr::from(s))
+        struct RcStrVisitor;
+
+        impl serde::de::Visitor<'_> for RcStrVisitor {
+            type Value = RcStr;
+
+            fn expecting(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+                f.write_str("a string")
+            }
+
+            fn visit_str<E: serde::de::Error>(self, v: &str) -> Result<RcStr, E> {
+                Ok(RcStr::from_deserialized(v))
+            }
+
+            fn visit_string<E: serde::de::Error>(self, v: String) -> Result<RcStr, E> {
+                Ok(RcStr::from_deserialized(&v))
+            }
+        }
+
+        deserializer.deserialize_str(RcStrVisitor)
     }
 }
 
@@ -390,7 +437,29 @@ impl Encode for RcStr {
 
 impl<Context> Decode<Context> for RcStr {
     fn decode<D: Decoder<Context = Context>>(decoder: &mut D) -> Result<Self, DecodeError> {
-        Ok(RcStr::from(String::decode(decoder)?))
+        // Decode the length prefix
+        let len = u64::decode(decoder)?;
+        let len: usize = len
+            .try_into()
+            .map_err(|_| DecodeError::OutsideUsizeRange(len))?;
+
+        if unty::type_equal::<D::R, turbo_bincode::TurboBincodeReader>() {
+            // We know the reader is a TurboBincodeReader backed by &[u8], so peek_read
+            // returning None means data corruption (not enough bytes), not "unsupported".
+            let bytes = decoder
+                .reader()
+                .peek_read(len)
+                .ok_or(DecodeError::UnexpectedEnd { additional: len })?;
+            let s = core::str::from_utf8(bytes).map_err(|inner| DecodeError::Utf8 { inner })?;
+            let rcstr = RcStr::from_deserialized(s);
+            decoder.reader().consume(len);
+            Ok(rcstr)
+        } else {
+            unreachable!(
+                "RcStr::decode expected TurboBincodeReader, but was called with a {} reader",
+                std::any::type_name::<D::R>(),
+            )
+        }
     }
 }
 
@@ -433,8 +502,46 @@ pub const fn make_const_prehashed_string(text: &'static str) -> PrehashedString
     }
 }
 
+// Re-export inventory so the rcstr! macro can reference it via $crate::inventory
+#[doc(hidden)]
+pub use inventory;
+
+/// Wrapper for collecting `rcstr!` static constants via `inventory`.
+#[doc(hidden)]
+pub struct StaticRcStr(pub &'static PrehashedString);
+
+inventory::collect!(StaticRcStr);
+
+/// Read-only lookup table mapping precomputed hash -> static PrehashedString.
+/// Built once on first access from all `rcstr!` constants collected by `inventory`.
+///
+/// Multiple `rcstr!` calls with the same string content will each submit to
+/// inventory, but we deduplicate by content here so only one entry per unique
+/// string is stored.
+static STATIC_TABLE: LazyLock<
+    HashMap<u64, SmallVec<[&'static PrehashedString; 1]>, FxBuildHasher>,
+> = LazyLock::new(|| {
+    let mut map: HashMap<u64, SmallVec<[&'static PrehashedString; 1]>, FxBuildHasher> =
+        HashMap::with_hasher(FxBuildHasher);
+    for StaticRcStr(phs) in inventory::iter::<StaticRcStr> {
+        let entries = map.entry(phs.hash).or_default();
+        // Deduplicate: skip if an entry with the same string content exists
+        // Mostly linkers will merge static strings but this isn't guaranteed so we cannot just rely
+        // on pointer equality.
+        if !entries
+            .iter()
+            .any(|e| e.value.as_str() == phs.value.as_str())
+        {
+            entries.push(phs);
+        }
+    }
+    map.shrink_to_fit(); // this map will never change again
+    map
+});
+
 /// Create an rcstr from a string literal.
-/// allocates the RcStr inline when possible otherwise uses a `LazyLock` to manage the allocation.
+/// Allocates the RcStr inline when possible, otherwise uses a static `PrehashedString`.  In either
+/// case this is a compile time constant
 #[macro_export]
 macro_rules! rcstr {
     ($s:expr) => {{
@@ -447,6 +554,8 @@ macro_rules! rcstr {
                 // Allocate static storage for the PrehashedString
                 static RCSTR_STORAGE: $crate::PrehashedString =
                     $crate::make_const_prehashed_string($s);
+                // Register with inventory so deserialization can find this static
+                $crate::inventory::submit!($crate::StaticRcStr(&RCSTR_STORAGE));
                 // This basically just tags a bit onto the raw pointer and wraps it in an RcStr
                 // should be fast enough to do every time.
                 $crate::from_static(&RCSTR_STORAGE)
@@ -624,4 +733,33 @@ mod tests {
             }
         }
     }
+
+    #[test]
+    fn test_bincode_roundtrip() {
+        use turbo_bincode::{turbo_bincode_decode, turbo_bincode_encode};
+
+        // Test inline string
+        let short = RcStr::from("hi");
+        let encoded = turbo_bincode_encode(&short).unwrap();
+        let decoded: RcStr = turbo_bincode_decode(&encoded).unwrap();
+        assert_eq!(decoded, short);
+        assert_eq!(decoded.tag(), INLINE_TAG);
+
+        // Test dynamic string (no static match)
+        let long = RcStr::from("bincode_roundtrip: no matching rcstr constant");
+        let encoded = turbo_bincode_encode(&long).unwrap();
+        let decoded: RcStr = turbo_bincode_decode(&encoded).unwrap();
+        assert_eq!(decoded, long);
+        assert_eq!(decoded.tag(), DYNAMIC_TAG);
+
+        // Test static dedup via decode
+        const STATIC_STR: &str = "bincode_roundtrip: a static constant for testing";
+        let _register = rcstr!(STATIC_STR);
+        let original = RcStr::from(STATIC_STR); // DYNAMIC since from() doesn't check
+        let encoded = turbo_bincode_encode(&original).unwrap();
+        let decoded: RcStr = turbo_bincode_decode(&encoded).unwrap();
+        assert_eq!(decoded.as_str(), STATIC_STR);
+        // Decoded via peek_read path should find the static constant
+        assert_eq!(decoded.tag(), STATIC_TAG);
+    }
 }