turbopack/
global_module_ids.rs

1use anyhow::{Context, Result};
2use rustc_hash::FxHashMap;
3use smallvec::SmallVec;
4use tracing::Instrument;
5use turbo_rcstr::RcStr;
6use turbo_tasks::{ReadRef, ResolvedVc, TryJoinIterExt, ValueToString, Vc};
7use turbo_tasks_hash::hash_xxh3_hash64;
8use turbopack_core::{
9    chunk::{ChunkableModule, ChunkingType, module_id_strategies::GlobalModuleIdStrategy},
10    ident::AssetIdent,
11    module::Module,
12    module_graph::{ModuleGraph, RefData},
13};
14use turbopack_ecmascript::async_chunk::module::AsyncLoaderModule;
15
16#[turbo_tasks::function]
17pub async fn get_global_module_id_strategy(
18    module_graph: ResolvedVc<ModuleGraph>,
19) -> Result<Vc<GlobalModuleIdStrategy>> {
20    let span = tracing::info_span!("compute module id map");
21    async move {
22        let module_graph = module_graph.await?;
23        let graphs = module_graph.graphs.iter().try_join().await?;
24
25        // All modules in the graph
26        let module_idents = graphs
27            .iter()
28            .flat_map(|graph| graph.iter_nodes())
29            .map(|m| m.module.ident());
30
31        // And additionally, all the modules that are inserted by chunking (i.e. async loaders)
32        let mut async_idents = vec![];
33        module_graph
34            .traverse_all_edges_unordered(|parent, current| {
35                if let (
36                    _,
37                    &RefData {
38                        chunking_type: ChunkingType::Async,
39                        ..
40                    },
41                ) = parent
42                {
43                    let module =
44                        ResolvedVc::try_sidecast::<Box<dyn ChunkableModule>>(current.module)
45                            .context("expected chunkable module for async reference")?;
46                    async_idents.push(AsyncLoaderModule::asset_ident_for(*module));
47                }
48                Ok(())
49            })
50            .await?;
51
52        let mut module_id_map = module_idents
53            .chain(async_idents.into_iter())
54            .map(|ident| async move {
55                let ident = ident.to_resolved().await?;
56                let ident_str = ident.to_string().await?;
57                let hash = hash_xxh3_hash64(&ident_str);
58                Ok((ident, (ident_str, hash)))
59            })
60            .try_join()
61            .await?
62            .into_iter()
63            .collect::<FxHashMap<_, _>>();
64
65        finalize_module_ids(&mut module_id_map);
66
67        Ok(GlobalModuleIdStrategy {
68            module_id_map: module_id_map
69                .into_iter()
70                .map(|(ident, (_, hash))| (ident, hash))
71                .collect(),
72        }
73        .cell())
74    }
75    .instrument(span)
76    .await
77}
78
79const JS_MAX_SAFE_INTEGER: u64 = (1u64 << 53) - 1;
80
81/// Shorten hashes and handle any collisions.
82fn finalize_module_ids(
83    merged_module_ids: &mut FxHashMap<ResolvedVc<AssetIdent>, (ReadRef<RcStr>, u64)>,
84) {
85    // 5% fill rate, as done in Webpack
86    // https://github.com/webpack/webpack/blob/27cf3e59f5f289dfc4d76b7a1df2edbc4e651589/lib/ids/IdHelpers.js#L366-L405
87    let optimal_range = merged_module_ids.len() * 20;
88    let digit_mask = std::cmp::min(
89        10u64.pow((optimal_range as f64).log10().ceil() as u32),
90        JS_MAX_SAFE_INTEGER,
91    );
92
93    let mut used_ids =
94        FxHashMap::<u64, SmallVec<[(ResolvedVc<AssetIdent>, ReadRef<RcStr>); 1]>>::default();
95
96    // Run in multiple passes, to not depend on the order of the `merged_module_ids` (i.e. the order
97    // of imports). Hashes could still change if modules are added or removed.
98
99    // Find pass: shorten hashes, potentially causing (more) collisions
100    for (ident, (ident_str, full_hash)) in merged_module_ids.iter_mut() {
101        let first_pass_hash = *full_hash % digit_mask;
102        used_ids
103            .entry(first_pass_hash)
104            .or_default()
105            .push((*ident, ident_str.clone()));
106        *full_hash = first_pass_hash;
107    }
108
109    // Filter conflicts
110    let mut conflicting_hashes = used_ids
111        .iter()
112        .filter(|(_, list)| (list.len() > 1))
113        .map(|(hash, _)| *hash)
114        .collect::<Vec<_>>();
115    conflicting_hashes.sort();
116
117    // Second pass over the conflicts to resolve them
118    for hash in conflicting_hashes.into_iter() {
119        let list = used_ids.get_mut(&hash).unwrap();
120        // Take the vector but keep the (empty) entry, so that the "contains_key" check below works
121        let mut list = std::mem::take(list);
122        list.sort_by(|a, b| a.1.cmp(&b.1));
123
124        // Skip the first one, one module can keep the original hash
125        for (ident, _) in list.into_iter().skip(1) {
126            let hash = &mut merged_module_ids.get_mut(&ident).unwrap().1;
127
128            // the original algorithm since all that runs in deterministic order now
129            let mut i = 1;
130            let mut trimmed_hash;
131            loop {
132                // If the id is already used, find the next available hash.
133                trimmed_hash = hash_xxh3_hash64((*hash, i)) % digit_mask;
134                if !used_ids.contains_key(&trimmed_hash) {
135                    break;
136                }
137                i += 1;
138            }
139            // At this point, we don't care about the values anymore, just the keys
140            used_ids.entry(trimmed_hash).or_default();
141            *hash = trimmed_hash;
142        }
143    }
144}
turbopack/global_module_ids.rs

turbopack/
global_module_ids.rs
