Skip to main content

turbopack_core/module_graph/
chunk_group_info.rs

1use std::{
2    cmp::Reverse,
3    hash::Hash,
4    ops::{Deref, DerefMut},
5    sync::LazyLock,
6};
7
8use anyhow::{Context, Result, bail};
9use bincode::{Decode, Encode};
10use either::Either;
11use indexmap::map::Entry;
12use roaring::RoaringBitmap;
13use rustc_hash::FxHashMap;
14use tracing::Instrument;
15use turbo_rcstr::RcStr;
16use turbo_tasks::{
17    FxIndexMap, FxIndexSet, NonLocalValue, ResolvedVc, TaskInput, TryJoinIterExt, ValueToString,
18    Vc, debug::ValueDebugFormat, turbofmt,
19};
20use turbo_tasks_hash::{DeterministicHash, DeterministicHasher};
21
22use crate::{
23    chunk::ChunkingType,
24    module::Module,
25    module_graph::{GraphTraversalAction, ModuleGraph, RefData},
26};
27
28#[derive(Clone, Debug, Default, PartialEq, ValueDebugFormat, Encode, Decode)]
29#[repr(transparent)]
30pub struct RoaringBitmapWrapper(#[bincode(with_serde)] pub RoaringBitmap);
31
32impl TaskInput for RoaringBitmapWrapper {
33    fn is_transient(&self) -> bool {
34        false
35    }
36}
37
38impl RoaringBitmapWrapper {
39    /// Whether `self` contains bits that are not in `other`
40    ///
41    /// The existing `is_superset` method also returns true for equal sets
42    pub fn is_proper_superset(&self, other: &Self) -> bool {
43        !self.is_subset(other)
44    }
45
46    pub fn into_inner(self) -> RoaringBitmap {
47        self.0
48    }
49}
50unsafe impl NonLocalValue for RoaringBitmapWrapper {}
51
52// RoaringBitmap doesn't impl Eq: https://github.com/RoaringBitmap/roaring-rs/issues/302
53// PartialEq can only return true if both bitmaps have the same internal representation, but two
54// bitmaps with the same content should always have the same internal representation
55impl Eq for RoaringBitmapWrapper {}
56
57impl Deref for RoaringBitmapWrapper {
58    type Target = RoaringBitmap;
59    fn deref(&self) -> &Self::Target {
60        &self.0
61    }
62}
63impl DerefMut for RoaringBitmapWrapper {
64    fn deref_mut(&mut self) -> &mut Self::Target {
65        &mut self.0
66    }
67}
68impl Hash for RoaringBitmapWrapper {
69    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
70        struct HasherWriter<'a, H: std::hash::Hasher>(&'a mut H);
71        impl<H: std::hash::Hasher> std::io::Write for HasherWriter<'_, H> {
72            fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
73                self.0.write(buf);
74                Ok(buf.len())
75            }
76            fn flush(&mut self) -> std::io::Result<()> {
77                Ok(())
78            }
79        }
80        self.0.serialize_into(HasherWriter(state)).unwrap();
81    }
82}
83
84impl DeterministicHash for RoaringBitmapWrapper {
85    fn deterministic_hash<H: DeterministicHasher>(&self, state: &mut H) {
86        struct HasherWriter<'a, H: DeterministicHasher>(&'a mut H);
87        impl<H: DeterministicHasher> std::io::Write for HasherWriter<'_, H> {
88            fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
89                self.0.write_bytes(buf);
90                Ok(buf.len())
91            }
92            fn flush(&mut self) -> std::io::Result<()> {
93                Ok(())
94            }
95        }
96        // The serialized form is stable across platforms, unlike the in-memory representation.
97        self.0.serialize_into(HasherWriter(state)).unwrap();
98    }
99}
100
101#[turbo_tasks::value(transparent, cell = "keyed")]
102pub struct ModuleToChunkGroups(FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper>);
103
104#[turbo_tasks::value]
105pub struct ChunkGroupWithIndex {
106    pub index: u32,
107    pub chunk_group: ChunkGroup,
108}
109
110#[turbo_tasks::value(transparent)]
111pub struct ChunkGroups(Vec<ChunkGroupWithIndex>);
112
113#[turbo_tasks::value(transparent)]
114pub struct OptionChunkGroupWithIndex(Option<ChunkGroupWithIndex>);
115
116/// Maps each [`ChunkGroupKey`] to its index in [`ChunkGroupInfo::chunk_groups`], as a keyed cell so
117/// [`ChunkGroupInfo::get_index_of`] depends only on the key it looks up.
118///
119/// This duplicates [`ChunkGroupInfo::chunk_group_keys`], which stays for the index -> key
120/// direction. The `IndexSet` can't be the keyed cell: its `KeyedAccess` yields `()` rather than the
121/// index, and its `KeyedEq` ignores position, so an index that merely shifted would go unnoticed.
122#[turbo_tasks::value(transparent, cell = "keyed")]
123pub struct ChunkGroupKeyToIndex(FxHashMap<ChunkGroupKey, u32>);
124
125#[turbo_tasks::value]
126pub struct ChunkGroupInfo {
127    pub module_chunk_groups: ResolvedVc<ModuleToChunkGroups>,
128    /// For each async module, the chunk groups that contain its async loader.
129    pub async_loader_chunk_groups: ResolvedVc<ModuleToChunkGroups>,
130    #[bincode(with = "turbo_bincode::indexset")]
131    pub chunk_groups: FxIndexSet<ChunkGroup>,
132    #[turbo_tasks(unsafe_ignore)]
133    #[bincode(with = "turbo_bincode::indexset")]
134    pub chunk_group_keys: FxIndexSet<ChunkGroupKey>,
135    /// The same keys as `chunk_group_keys`, mapped to their index, in a keyed cell so a single
136    /// index lookup does not depend on the whole `ChunkGroupInfo`. See [`ChunkGroupKeyToIndex`].
137    pub chunk_group_indices: ResolvedVc<ChunkGroupKeyToIndex>,
138    pub chunking_heuristics: ChunkingHeuristicsInfo,
139}
140
141/// Chunking heuristics computed by [`compute_chunk_group_info`]. `clusters` is indexed by
142/// chunk-group index (same length and order as [`ChunkGroupInfo::chunk_groups`]); `priority_routes`
143/// is a set of those indices.
144#[derive(Debug, Default, Clone, PartialEq, Eq, ValueDebugFormat, NonLocalValue, Encode, Decode)]
145pub struct ChunkingHeuristicsInfo {
146    /// For each chunk group (by index), the set of cluster IDs it belongs to. A cluster ID is the
147    /// index of a configured cluster. A route's chunk group carries that route's clusters; chunk
148    /// groups it pulls in inherit them.
149    ///
150    /// Example: `clusters[5] = [0, 2]` — chunk group 5 is part of clusters 0 and 2.
151    pub clusters: Vec<Vec<u16>>,
152    /// The set of chunk-group indices that belong to a priority route: the priority
153    /// routes themselves, plus every chunk group they pull in.
154    ///
155    /// Example: `priority_routes = {3, 7}` — chunk groups 3 and 7 are served by a priority
156    /// route; any group not in the set (e.g. 4) is not.
157    pub priority_routes: RoaringBitmapWrapper,
158}
159
160#[turbo_tasks::value_impl]
161impl ChunkGroupInfo {
162    #[turbo_tasks::function]
163    pub fn module_chunk_groups(&self) -> Vc<ModuleToChunkGroups> {
164        *self.module_chunk_groups
165    }
166
167    /// The keyed `ChunkGroupKey` -> index map. Read a single entry from it with [`Vc::get`] to
168    /// depend only on that key rather than on all of [`ChunkGroupInfo`].
169    #[turbo_tasks::function]
170    pub fn chunk_group_indices(&self) -> Vc<ChunkGroupKeyToIndex> {
171        *self.chunk_group_indices
172    }
173
174    /// Returns the exact chunk groups that contain `module`, as derived while traversing the module
175    /// graph.
176    #[turbo_tasks::function]
177    pub async fn get_chunk_groups_for_module(
178        &self,
179        module: ResolvedVc<Box<dyn Module>>,
180    ) -> Result<Vc<ChunkGroups>> {
181        let module_chunk_groups = self.module_chunk_groups.await?;
182        let Some(groups) = module_chunk_groups.get(&module) else {
183            return Ok(Vc::cell(Vec::new()));
184        };
185        Ok(Vc::cell(
186            groups
187                .iter()
188                .map(|index| ChunkGroupWithIndex {
189                    index,
190                    chunk_group: self.chunk_groups[index as usize].clone(),
191                })
192                .collect(),
193        ))
194    }
195
196    /// Returns the shared merged chunk group with `merge_tag` that `parent` is the parent of, if
197    /// the graph produced one.
198    ///
199    /// A merge tag collects everything reachable through the tagged shared references of one
200    /// parent group into a single group, so there is at most one such group per parent and tag.
201    #[turbo_tasks::function]
202    pub fn get_shared_merged_chunk_group(
203        &self,
204        parent: usize,
205        merge_tag: RcStr,
206    ) -> Vc<OptionChunkGroupWithIndex> {
207        let key = ChunkGroupKey::SharedMerged {
208            parent: ChunkGroupId::from(parent),
209            merge_tag,
210        };
211        Vc::cell(
212            self.chunk_group_keys
213                .get_index_of(&key)
214                .map(|index| ChunkGroupWithIndex {
215                    index: index as u32,
216                    chunk_group: self.chunk_groups[index].clone(),
217                }),
218        )
219    }
220}
221
222impl ChunkGroupInfo {
223    /// Returns the index of the chunk group identified by `key` in
224    /// [`ChunkGroupInfo::chunk_groups`].
225    ///
226    /// The lookup goes through the keyed [`ChunkGroupKeyToIndex`] cell, so the caller depends only
227    /// on the queried key: adding or changing an unrelated chunk group does not invalidate it.
228    ///
229    /// This is deliberately *not* a `turbo_tasks::function`. Making it one would create a separate
230    /// task per key argument, which is exactly the per-chunk-group overhead the keyed cell is meant
231    /// to avoid; the single argument-less [`ChunkGroupInfo::chunk_group_indices`] task is what
232    /// provides the caching.
233    pub async fn get_index_of(self: Vc<Self>, key: ChunkGroupKey) -> Result<usize> {
234        if let Some(idx) = self.chunk_group_indices().get(&key).await? {
235            Ok(*idx as usize)
236        } else if cfg!(debug_assertions) {
237            // Only taken on the failure path, so the happy path keeps its narrow dependency.
238            let this = self.await?;
239            bail!(
240                "Couldn't find chunk group index for {} in {}",
241                key.debug_str(&this.chunk_group_keys).await?,
242                this.chunk_groups
243                    .iter()
244                    .map(|c| c.debug_str(&this))
245                    .try_join()
246                    .await?
247                    .join(", ")
248            )
249        } else {
250            bail!("Couldn't find chunk group index")
251        }
252    }
253
254    /// Returns the registered chunk group identified by `key`.
255    ///
256    /// Chunking takes a [`ChunkGroupKey`] and resolves the group here, so a group's contents (e.g.
257    /// the entries of a merged group) always come from the module graph rather than the caller.
258    pub async fn get_chunk_group(self: Vc<Self>, key: ChunkGroupKey) -> Result<ChunkGroup> {
259        let index = self.get_index_of(key).await?;
260        Ok(self.await?.chunk_groups[index].clone())
261    }
262}
263
264/// Per-entry chunking heuristics.
265#[turbo_tasks::task_input]
266#[derive(Debug, Default, Clone, Hash, PartialEq, Eq, Encode, Decode)]
267pub struct EntryHeuristics {
268    /// Cluster indices this route belongs to.
269    pub clusters: Vec<u16>,
270    pub high_priority: bool,
271}
272
273impl EntryHeuristics {
274    /// Heuristics for an entry that is a high-priority route: belongs to no clusters and is marked
275    /// as high priority.
276    pub fn high_priority() -> Self {
277        Self {
278            clusters: Vec::new(),
279            high_priority: true,
280        }
281    }
282}
283
284/// See [ChunkGroup] for documentation
285#[turbo_tasks::task_input]
286#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
287pub enum ChunkGroupEntry {
288    Entry {
289        modules: Vec<ResolvedVc<Box<dyn Module>>>,
290        heuristics: EntryHeuristics,
291    },
292    Async(ResolvedVc<Box<dyn Module>>),
293    Isolated(ResolvedVc<Box<dyn Module>>),
294    IsolatedMerged {
295        parent: Box<ChunkGroupEntry>,
296        merge_tag: RcStr,
297        entries: Vec<ResolvedVc<Box<dyn Module>>>,
298    },
299    Shared(ResolvedVc<Box<dyn Module>>),
300    SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
301    SharedMerged {
302        parent: Box<ChunkGroupEntry>,
303        merge_tag: RcStr,
304        entries: Vec<ResolvedVc<Box<dyn Module>>>,
305    },
306}
307impl ChunkGroupEntry {
308    pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + '_ {
309        match self {
310            Self::Async(e) | Self::Isolated(e) | Self::Shared(e) => {
311                Either::Left(std::iter::once(*e))
312            }
313            Self::Entry {
314                modules: entries, ..
315            }
316            | Self::IsolatedMerged { entries, .. }
317            | Self::SharedMultiple(entries)
318            | Self::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
319        }
320    }
321}
322
323#[turbo_tasks::task_input]
324#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
325pub enum ChunkGroup {
326    /// The entry chunk group of the compilation, e.g. src/index.js for a SPA, or app/foo/page.js
327    /// for Next.js.
328    Entry(Vec<ResolvedVc<Box<dyn Module>>>),
329    /// An async chunk group. Corresponds to an incoming [ChunkingType::Async] reference
330    Async(ResolvedVc<Box<dyn Module>>),
331    /// An isolated chunk group. Corresponds to an incoming [ChunkingType::Isolated] reference with
332    /// `merge_tag: None`
333    Isolated(ResolvedVc<Box<dyn Module>>),
334    /// An isolated chunk group. Corresponds to an incoming [ChunkingType::Isolated] reference with
335    /// `merge_tag: Some(_)`
336    IsolatedMerged {
337        parent: usize,
338        merge_tag: RcStr,
339        entries: Vec<ResolvedVc<Box<dyn Module>>>,
340    },
341    /// A shared chunk group. Corresponds to an incoming [ChunkingType::Shared] reference with
342    /// `merge_tag: None`
343    Shared(ResolvedVc<Box<dyn Module>>),
344    /// A shared chunk group with multiple entries.
345    SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
346    /// A shared chunk group. Corresponds to an incoming [ChunkingType::Shared] reference with
347    /// `merge_tag: Some(_)`
348    SharedMerged {
349        parent: usize,
350        merge_tag: RcStr,
351        entries: Vec<ResolvedVc<Box<dyn Module>>>,
352    },
353    /// a module with an incoming collected edge
354    Collected(ResolvedVc<Box<dyn Module>>),
355}
356
357impl ChunkGroup {
358    /// Returns the parent group when this chunk group is a merged group. In that case `entries()`
359    /// are in unspecified order.
360    pub fn get_merged_parent(&self) -> Option<usize> {
361        match self {
362            ChunkGroup::IsolatedMerged { parent, .. } | ChunkGroup::SharedMerged { parent, .. } => {
363                Some(*parent)
364            }
365            _ => None,
366        }
367    }
368
369    /// Iterates over the entries of the chunk group. When `get_merged_parent` is Some, the order is
370    /// unspecified.
371    pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + Clone + '_ {
372        match self {
373            ChunkGroup::Async(e)
374            | ChunkGroup::Isolated(e)
375            | ChunkGroup::Shared(e)
376            | ChunkGroup::Collected(e) => Either::Left(std::iter::once(*e)),
377            ChunkGroup::Entry(entries)
378            | ChunkGroup::IsolatedMerged { entries, .. }
379            | ChunkGroup::SharedMultiple(entries)
380            | ChunkGroup::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
381        }
382    }
383
384    /// Returns the canonical identity used to index this chunk group.
385    ///
386    /// A merged group is identified by its parent and merge tag alone. Those two determine the
387    /// group; its `entries` are the *result* of merging everything reachable through the tagged
388    /// references, not part of its identity, and their order is unspecified. Including them would
389    /// make two values describing the same group compare unequal.
390    pub fn key(&self) -> ChunkGroupKey {
391        match self {
392            ChunkGroup::Entry(entries) => ChunkGroupKey::Entry(entries.clone()),
393            ChunkGroup::Async(module) => ChunkGroupKey::Async(*module),
394            ChunkGroup::Isolated(module) => ChunkGroupKey::Isolated(*module),
395            ChunkGroup::IsolatedMerged {
396                parent, merge_tag, ..
397            } => ChunkGroupKey::IsolatedMerged {
398                parent: ChunkGroupId::from(*parent),
399                merge_tag: merge_tag.clone(),
400            },
401            ChunkGroup::Shared(module) => ChunkGroupKey::Shared(*module),
402            ChunkGroup::SharedMultiple(entries) => ChunkGroupKey::SharedMultiple(entries.clone()),
403            ChunkGroup::SharedMerged {
404                parent, merge_tag, ..
405            } => ChunkGroupKey::SharedMerged {
406                parent: ChunkGroupId::from(*parent),
407                merge_tag: merge_tag.clone(),
408            },
409            ChunkGroup::Collected(module) => ChunkGroupKey::Collected(*module),
410        }
411    }
412
413    pub fn entries_count(&self) -> usize {
414        match self {
415            ChunkGroup::Async(_)
416            | ChunkGroup::Isolated(_)
417            | ChunkGroup::Shared(_)
418            | ChunkGroup::Collected(_) => 1,
419            ChunkGroup::Entry(entries)
420            | ChunkGroup::IsolatedMerged { entries, .. }
421            | ChunkGroup::SharedMultiple(entries)
422            | ChunkGroup::SharedMerged { entries, .. } => entries.len(),
423        }
424    }
425
426    pub async fn debug_str(&self, chunk_group_info: &ChunkGroupInfo) -> Result<String> {
427        Ok(match self {
428            ChunkGroup::Entry(entries) => format!(
429                "ChunkGroup::Entry({:?})",
430                entries
431                    .iter()
432                    .map(|m| m.ident().to_string())
433                    .try_join()
434                    .await?
435            ),
436            ChunkGroup::Async(entry) => turbofmt!("ChunkGroup::Async({:?})", entry.ident())
437                .await?
438                .to_string(),
439            ChunkGroup::Collected(entry) => turbofmt!("ChunkGroup::Collected({:?})", entry.ident())
440                .await?
441                .to_string(),
442            ChunkGroup::Isolated(entry) => turbofmt!("ChunkGroup::Isolated({:?})", entry.ident())
443                .await?
444                .to_string(),
445            ChunkGroup::Shared(entry) => turbofmt!("ChunkGroup::Shared({:?})", entry.ident())
446                .await?
447                .to_string(),
448            ChunkGroup::SharedMultiple(entries) => format!(
449                "ChunkGroup::SharedMultiple({:?})",
450                entries
451                    .iter()
452                    .map(|m| m.ident().to_string())
453                    .try_join()
454                    .await?
455            ),
456            ChunkGroup::IsolatedMerged {
457                parent,
458                merge_tag,
459                entries,
460            } => {
461                format!(
462                    "ChunkGroup::IsolatedMerged({}, {}, {:?})",
463                    Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
464                        .await?,
465                    merge_tag,
466                    entries
467                        .iter()
468                        .map(|m| m.ident().to_string())
469                        .try_join()
470                        .await?
471                )
472            }
473            ChunkGroup::SharedMerged {
474                parent,
475                merge_tag,
476                entries,
477            } => {
478                format!(
479                    "ChunkGroup::SharedMerged({}, {}, {:?})",
480                    Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
481                        .await?,
482                    merge_tag,
483                    entries
484                        .iter()
485                        .map(|m| m.ident().to_string())
486                        .try_join()
487                        .await?
488                )
489            }
490        })
491    }
492}
493
494/// See [ChunkGroup] for documentation
495#[turbo_tasks::task_input]
496#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
497pub enum ChunkGroupKey {
498    Entry(Vec<ResolvedVc<Box<dyn Module>>>),
499    Async(ResolvedVc<Box<dyn Module>>),
500    Isolated(ResolvedVc<Box<dyn Module>>),
501    IsolatedMerged {
502        parent: ChunkGroupId,
503        merge_tag: RcStr,
504    },
505    Shared(ResolvedVc<Box<dyn Module>>),
506    SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
507    SharedMerged {
508        parent: ChunkGroupId,
509        merge_tag: RcStr,
510    },
511    /// a module with an incoming collected edge
512    Collected(ResolvedVc<Box<dyn Module>>),
513}
514
515impl ChunkGroupKey {
516    /// A stable identity of this chunk group, independent of the module graph it was discovered
517    /// in.
518    ///
519    /// The result contains only module idents and merge tags, never a [`ChunkGroupId`], which is
520    /// an index into one [`ChunkGroupInfo`] and denotes an unrelated chunk group in another: the
521    /// parent of a merged chunk group is resolved through `keys` and rendered recursively.
522    ///
523    /// [`crate::chunk::available_chunk_groups::AvailableChunkGroups::hash`] derives output file
524    /// names from this, so two chunk groups must render equally exactly when they are the same
525    /// chunk group. Changing the rendering renames assets; adding anything graph-local to it is a
526    /// correctness bug.
527    pub async fn ident_str(
528        &self,
529        keys: &(impl std::ops::Index<usize, Output = Self> + ?Sized),
530    ) -> Result<String> {
531        Ok(match self {
532            ChunkGroupKey::Entry(entries) => format!(
533                "Entry({:?})",
534                entries
535                    .iter()
536                    .map(|m| m.ident().to_string())
537                    .try_join()
538                    .await?
539            ),
540            ChunkGroupKey::Async(module) => {
541                turbofmt!("Async({:?})", module.ident()).await?.to_string()
542            }
543            ChunkGroupKey::Collected(module) => turbofmt!("Collected({:?})", module.ident())
544                .await?
545                .to_string(),
546            ChunkGroupKey::Isolated(module) => turbofmt!("Isolated({:?})", module.ident())
547                .await?
548                .to_string(),
549            ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
550                format!(
551                    "IsolatedMerged {{ parent: {}, merge_tag: {:?} }}",
552                    Box::pin(keys.index(parent.0 as usize).ident_str(keys)).await?,
553                    merge_tag
554                )
555            }
556            ChunkGroupKey::Shared(module) => {
557                turbofmt!("Shared({:?})", module.ident()).await?.to_string()
558            }
559            ChunkGroupKey::SharedMultiple(entries) => format!(
560                "SharedMultiple({:?})",
561                entries
562                    .iter()
563                    .map(|m| m.ident().to_string())
564                    .try_join()
565                    .await?
566            ),
567            ChunkGroupKey::SharedMerged { parent, merge_tag } => {
568                format!(
569                    "SharedMerged {{ parent: {}, merge_tag: {:?} }}",
570                    Box::pin(keys.index(parent.0 as usize).ident_str(keys)).await?,
571                    merge_tag
572                )
573            }
574        })
575    }
576
577    /// How this chunk group is shown in debug output.
578    ///
579    /// Delegates to [`Self::ident_str`], which already renders the chunk group unambiguously.
580    /// Debug output is free to diverge from it, but note that `ident_str` must stay stable because
581    /// asset idents are derived from it -- change this wrapper rather than `ident_str` itself.
582    pub async fn debug_str(
583        &self,
584        keys: &(impl std::ops::Index<usize, Output = Self> + ?Sized),
585    ) -> Result<String> {
586        self.ident_str(keys).await
587    }
588}
589
590#[turbo_tasks::task_input]
591#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Encode, Decode)]
592pub struct ChunkGroupId(u32);
593
594impl From<usize> for ChunkGroupId {
595    fn from(id: usize) -> Self {
596        Self(id as u32)
597    }
598}
599
600impl Deref for ChunkGroupId {
601    type Target = u32;
602    fn deref(&self) -> &Self::Target {
603        &self.0
604    }
605}
606
607pub async fn compute_chunk_group_info(graph: &ModuleGraph) -> Result<Vc<ChunkGroupInfo>> {
608    let span_outer = tracing::info_span!(
609        "compute chunk group info",
610        module_count = tracing::field::Empty,
611        visit_count = tracing::field::Empty,
612        chunk_group_count = tracing::field::Empty
613    );
614
615    let span = span_outer.clone();
616    async move {
617        let mut chunk_groups_map: FxIndexMap<
618            ChunkGroupKey,
619            FxIndexSet<ResolvedVc<Box<dyn Module>>>,
620        > = FxIndexMap::default();
621
622        // For each module, the indices in the bitmap store which chunk groups in `chunk_groups_map`
623        // that module is part of.
624        let mut module_chunk_groups: FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper> =
625            FxHashMap::default();
626        let mut async_loader_chunk_groups: FxHashMap<
627            ResolvedVc<Box<dyn Module>>,
628            RoaringBitmapWrapper,
629        > = FxHashMap::default();
630
631        let module_count = graph
632            .graphs
633            .iter()
634            .map(|g| g.graph.node_count())
635            .sum::<usize>();
636        span.record("module_count", module_count);
637
638        // use all entries from all graphs
639        let entries = graph.all_chunk_group_entries().collect::<Vec<_>>();
640
641        // First, rank every module in reverse postorder (so that a module is visited after the
642        // modules importing it), and initialize `module_chunk_groups` with empty bitmaps.
643        let module_rank =
644            graph.reverse_postorder_ranks(entries.iter().flat_map(|e| e.entries()))?;
645        module_chunk_groups.reserve(module_rank.len());
646        for module in module_rank.keys() {
647            module_chunk_groups.insert(*module, RoaringBitmapWrapper::default());
648        }
649
650        // ----
651
652        fn entry_to_chunk_group_id(
653            entry: ChunkGroupEntry,
654            chunk_groups_map: &mut FxIndexMap<
655                ChunkGroupKey,
656                FxIndexSet<ResolvedVc<Box<dyn Module>>>,
657            >,
658        ) -> ChunkGroupKey {
659            match entry {
660                ChunkGroupEntry::Entry { modules, .. } => ChunkGroupKey::Entry(modules),
661                ChunkGroupEntry::Async(entry) => ChunkGroupKey::Async(entry),
662                ChunkGroupEntry::Isolated(entry) => ChunkGroupKey::Isolated(entry),
663                ChunkGroupEntry::Shared(entry) => ChunkGroupKey::Shared(entry),
664                ChunkGroupEntry::SharedMultiple(entries) => ChunkGroupKey::SharedMultiple(entries),
665                ChunkGroupEntry::IsolatedMerged {
666                    parent,
667                    merge_tag,
668                    entries: _,
669                } => {
670                    let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
671                    let parent_entry = chunk_groups_map.entry(parent);
672                    let parent_id = parent_entry.index();
673                    parent_entry.or_default();
674
675                    ChunkGroupKey::IsolatedMerged {
676                        parent: ChunkGroupId::from(parent_id),
677                        merge_tag,
678                    }
679                }
680                ChunkGroupEntry::SharedMerged {
681                    parent,
682                    merge_tag,
683                    entries: _,
684                } => {
685                    let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
686                    let parent_entry = chunk_groups_map.entry(parent);
687                    let parent_id = parent_entry.index();
688                    parent_entry.or_default();
689
690                    ChunkGroupKey::SharedMerged {
691                        parent: ChunkGroupId::from(parent_id),
692                        merge_tag,
693                    }
694                }
695            }
696        }
697
698        let entry_chunk_group_keys = entries
699            .iter()
700            .flat_map(|&chunk_group| {
701                let chunk_group_key =
702                    entry_to_chunk_group_id(chunk_group.clone(), &mut chunk_groups_map);
703                chunk_group
704                    .entries()
705                    .map(move |e| (e, chunk_group_key.clone()))
706            })
707            .collect::<FxHashMap<_, _>>();
708
709        // `inherits_from[source]` is the set of chunk groups that inherit heuristics from `source`.
710        let mut inherits_from: FxHashMap<u32, RoaringBitmap> = FxHashMap::default();
711
712        let visit_count = graph.traverse_edges_fixed_point_with_priority(
713            entries
714                .iter()
715                .flat_map(|e| e.entries())
716                .map(|e| {
717                    Ok((
718                        e,
719                        Reverse(*module_rank.get(&e).context("Module rank not found")?),
720                    ))
721                })
722                .collect::<Result<Vec<_>>>()?,
723            &mut module_chunk_groups,
724            |parent_info: Option<(ResolvedVc<Box<dyn Module>>, &'_ RefData, _)>,
725             node: ResolvedVc<Box<dyn Module>>,
726             _,
727             module_chunk_groups: &mut FxHashMap<
728                ResolvedVc<Box<dyn Module>>,
729                RoaringBitmapWrapper,
730            >|
731             -> Result<GraphTraversalAction> {
732                enum ChunkGroupInheritance<It: Iterator<Item = ChunkGroupKey>> {
733                    Inherit(ResolvedVc<Box<dyn Module>>),
734                    ChunkGroup(It),
735                }
736                let chunk_groups = if let Some((parent, ref_data, _)) = parent_info {
737                    match &ref_data.chunking_type {
738                        ChunkingType::Parallel { .. } => ChunkGroupInheritance::Inherit(parent),
739                        ChunkingType::Async => {
740                            // The async loader for `node` is emitted in every chunk group that
741                            // contains the referencing module, so availability checks for async
742                            // loaders can use the same bitmap intersection as regular modules.
743                            let parent_groups = module_chunk_groups
744                                .get(&parent)
745                                .context("Module chunk group not found")?;
746                            **async_loader_chunk_groups.entry(node).or_default() |=
747                                &**parent_groups;
748                            ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
749                                ChunkGroupKey::Async(node),
750                            )))
751                        }
752                        ChunkingType::Isolated {
753                            merge_tag: None, ..
754                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
755                            ChunkGroupKey::Isolated(node),
756                        ))),
757                        ChunkingType::Shared {
758                            merge_tag: None, ..
759                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
760                            ChunkGroupKey::Shared(node),
761                        ))),
762                        ChunkingType::Isolated {
763                            merge_tag: Some(merge_tag),
764                            ..
765                        } => {
766                            let parents = module_chunk_groups
767                                .get(&parent)
768                                .context("Module chunk group not found")?;
769                            let chunk_groups =
770                                parents.iter().map(|parent| ChunkGroupKey::IsolatedMerged {
771                                    parent: ChunkGroupId(parent),
772                                    merge_tag: merge_tag.clone(),
773                                });
774                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Left(
775                                chunk_groups,
776                            )))
777                        }
778                        ChunkingType::Shared {
779                            merge_tag: Some(merge_tag),
780                            ..
781                        } => {
782                            let parents = module_chunk_groups
783                                .get(&parent)
784                                .context("Module chunk group not found")?;
785                            let chunk_groups =
786                                parents.iter().map(|parent| ChunkGroupKey::SharedMerged {
787                                    parent: ChunkGroupId(parent),
788                                    merge_tag: merge_tag.clone(),
789                                });
790                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Right(
791                                chunk_groups,
792                            )))
793                        }
794                        ChunkingType::Traced { .. } => {
795                            // Traced modules are not placed in chunk groups
796                            return Ok(GraphTraversalAction::Skip);
797                        }
798                        ChunkingType::Emitted {
799                            namespace: _,
800                            emit_to_all_entries: _,
801                        } => {
802                            // TODO ideally this would get the chunk group bitset of the parent
803                            // ChunkGroup::Entry
804                            ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
805                                ChunkGroupKey::Collected(node),
806                            )))
807                        }
808                        ChunkingType::Collected { .. } => {
809                            // These only exist in the module_batches graph.
810                            unreachable!();
811                        }
812                        ChunkingType::PerEntry => {
813                            // A collecting module belongs wherever its importer belongs. The
814                            // per-entry behavior is carried by the `chunk_group` argument of
815                            // `CollectingModule::as_chunk_item`, not by chunk group membership.
816                            // This matches `collect.rs`, which inherits the parent's entry
817                            // membership across this edge.
818                            ChunkGroupInheritance::Inherit(parent)
819                        }
820                    }
821                } else {
822                    ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
823                        // TODO remove clone
824                        entry_chunk_group_keys
825                            .get(&node)
826                            .context("Module chunk group not found")?
827                            .clone(),
828                    )))
829                };
830
831                Ok(match chunk_groups {
832                    ChunkGroupInheritance::ChunkGroup(chunk_groups) => {
833                        // Start of a new chunk group, don't inherit anything from parent
834                        let chunk_group_ids = chunk_groups.map(|chunk_group| {
835                            // For merged groups, the parent group id whose heuristics they inherit.
836                            let merged_parent = match &chunk_group {
837                                ChunkGroupKey::IsolatedMerged { parent, .. }
838                                | ChunkGroupKey::SharedMerged { parent, .. } => Some(parent.0),
839                                _ => None,
840                            };
841                            let id = match chunk_groups_map.entry(chunk_group) {
842                                Entry::Occupied(mut e) => {
843                                    let id = e.index() as u32;
844                                    if merged_parent.is_some() {
845                                        e.get_mut().insert(node);
846                                    }
847                                    id
848                                }
849                                Entry::Vacant(e) => {
850                                    let id = e.index() as u32;
851                                    let mut set = FxIndexSet::default();
852                                    if merged_parent.is_some() {
853                                        set.insert(node);
854                                    }
855                                    e.insert(set);
856                                    id
857                                }
858                            };
859                            // Record heuristics-inheritance edges into this chunk group: merged
860                            // groups inherit from their specific parent group; all other groups
861                            // inherit from every chunk group of the referencing module.
862                            if let Some(parent) = merged_parent {
863                                inherits_from.entry(parent).or_default().insert(id);
864                            } else if let Some((parent_module, _, _)) = parent_info
865                                && let Some(parent_groups) = module_chunk_groups.get(&parent_module)
866                            {
867                                for source in parent_groups.iter() {
868                                    inherits_from.entry(source).or_default().insert(id);
869                                }
870                            }
871                            id
872                        });
873
874                        let chunk_groups =
875                            RoaringBitmapWrapper(RoaringBitmap::from_iter(chunk_group_ids));
876
877                        // Assign chunk group to the target node (the entry of the chunk group)
878                        let bitset = module_chunk_groups
879                            .get_mut(&node)
880                            .context("Module chunk group not found")?;
881                        if chunk_groups.is_proper_superset(bitset) {
882                            // Add bits from parent, and continue traversal because changed
883                            **bitset |= chunk_groups.into_inner();
884
885                            GraphTraversalAction::Continue
886                        } else {
887                            // Unchanged, no need to forward to children
888                            GraphTraversalAction::Skip
889                        }
890                    }
891                    ChunkGroupInheritance::Inherit(parent) => {
892                        // Inherit chunk groups from parent, merge parent chunk groups into
893                        // current
894
895                        if parent == node {
896                            // A self-reference
897                            GraphTraversalAction::Skip
898                        } else {
899                            let [Some(parent_chunk_groups), Some(current_chunk_groups)] =
900                                module_chunk_groups.get_disjoint_mut([&parent, &node])
901                            else {
902                                // All modules are inserted in the previous iteration
903                                // Technically unreachable, but could be reached due to eventual
904                                // consistency
905                                bail!("Module chunk groups not found");
906                            };
907
908                            if current_chunk_groups.is_empty() {
909                                // Initial visit, clone instead of merging
910                                *current_chunk_groups = parent_chunk_groups.clone();
911                                GraphTraversalAction::Continue
912                            } else if parent_chunk_groups.is_proper_superset(current_chunk_groups) {
913                                // Add bits from parent, and continue traversal because changed
914                                **current_chunk_groups |= &**parent_chunk_groups;
915                                GraphTraversalAction::Continue
916                            } else {
917                                // Unchanged, no need to forward to children
918                                GraphTraversalAction::Skip
919                            }
920                        }
921                    }
922                })
923            },
924            // Visit modules in reverse postorder (lowest rank first, the traversal visits the
925            // highest priority first). This visits a module only after all of the modules
926            // importing it (except via cycles), so most modules are visited once, with their final
927            // set of chunk groups.
928            |successor, _| {
929                Ok(Reverse(
930                    *module_rank
931                        .get(&successor)
932                        .context("Module rank not found")?,
933                ))
934            },
935        )?;
936
937        span.record("visit_count", visit_count);
938        span.record("chunk_group_count", chunk_groups_map.len());
939
940        static PRINT_CHUNK_GROUP_INFO: LazyLock<bool> =
941            LazyLock::new(|| match std::env::var_os("TURBOPACK_PRINT_CHUNK_GROUPS") {
942                Some(v) => v == "1",
943                None => false,
944            });
945        if *PRINT_CHUNK_GROUP_INFO {
946            use std::{
947                collections::{BTreeMap, BTreeSet},
948                path::absolute,
949            };
950
951            let mut buckets = BTreeMap::default();
952            for (module, key) in &module_chunk_groups {
953                if !key.is_empty() {
954                    buckets
955                        .entry(key.iter().collect::<Vec<_>>())
956                        .or_insert(BTreeSet::new())
957                        .insert(module.ident().to_string().await?);
958                }
959            }
960
961            let mut result = vec![];
962            result.push("Chunk Groups:".to_string());
963            for (i, (key, _)) in chunk_groups_map.iter().enumerate() {
964                result.push(format!(
965                    "  {:?}: {}",
966                    i,
967                    key.debug_str(&chunk_groups_map.keys()).await?
968                ));
969            }
970            result.push("# Module buckets:".to_string());
971            for (key, modules) in buckets.iter() {
972                result.push(format!("## {:?}:", key.iter().collect::<Vec<_>>()));
973                for module in modules {
974                    result.push(format!("  {module}"));
975                }
976                result.push("".to_string());
977            }
978            let f = absolute(format!("chunk_group_info_{}.log", visit_count))?;
979            println!("Wrote Chunk Group Info to {}", f.display());
980            std::fs::write(f, result.join("\n"))?;
981        }
982
983        // Resolve per-chunk-group chunking heuristics. Entry
984        // chunk groups carry their route's clusters / priority-route flag; other chunk groups
985        // inherit the union of clusters (and OR of the flag) from their referencing chunk groups.
986        let mut clusters: Vec<RoaringBitmap> = vec![RoaringBitmap::new(); chunk_groups_map.len()];
987        let mut priority_routes = RoaringBitmap::new();
988
989        let mut worklist: Vec<usize> = Vec::new();
990
991        for chunk_group in &entries {
992            let ChunkGroupEntry::Entry {
993                modules,
994                heuristics,
995            } = chunk_group
996            else {
997                continue;
998            };
999            if heuristics.clusters.is_empty() && !heuristics.high_priority {
1000                continue;
1001            }
1002            if let Some(index) =
1003                chunk_groups_map.get_index_of(&ChunkGroupKey::Entry(modules.clone()))
1004            {
1005                if clusters[index].is_empty() && !priority_routes.contains(index as u32) {
1006                    worklist.push(index);
1007                }
1008                clusters[index].extend(heuristics.clusters.iter().map(|&c| c as u32));
1009                if heuristics.high_priority {
1010                    priority_routes.insert(index as u32);
1011                }
1012            }
1013        }
1014
1015        while let Some(source) = worklist.pop() {
1016            let source_priority_route = priority_routes.contains(source as u32);
1017            let Some(targets) = inherits_from.get(&(source as u32)) else {
1018                continue;
1019            };
1020            for target in targets.iter() {
1021                let target = target as usize;
1022                if target == source {
1023                    continue;
1024                }
1025                let [source_clusters, target_clusters] =
1026                    clusters.get_disjoint_mut([source, target]).unwrap();
1027                let previous_target_clusters_len = target_clusters.len();
1028                *target_clusters |= &*source_clusters;
1029                let changed = (source_priority_route && priority_routes.insert(target as u32))
1030                    || previous_target_clusters_len != target_clusters.len();
1031                if changed {
1032                    worklist.push(target);
1033                }
1034            }
1035        }
1036
1037        let chunk_group_clusters: Vec<Vec<u16>> = clusters
1038            .into_iter()
1039            .map(|bm| bm.iter().map(|id| id as u16).collect())
1040            .collect();
1041        let chunk_group_priority_routes = RoaringBitmapWrapper(priority_routes);
1042
1043        Ok(ChunkGroupInfo {
1044            module_chunk_groups: ResolvedVc::cell(module_chunk_groups),
1045            async_loader_chunk_groups: ResolvedVc::cell(async_loader_chunk_groups),
1046            chunk_group_keys: chunk_groups_map.keys().cloned().collect(),
1047            chunk_group_indices: ResolvedVc::cell(
1048                chunk_groups_map
1049                    .keys()
1050                    .enumerate()
1051                    .map(|(index, key)| (key.clone(), index as u32))
1052                    .collect(),
1053            ),
1054            chunking_heuristics: ChunkingHeuristicsInfo {
1055                clusters: chunk_group_clusters,
1056                priority_routes: chunk_group_priority_routes,
1057            },
1058            chunk_groups: chunk_groups_map
1059                .into_iter()
1060                .map(|(k, merged_entries)| match k {
1061                    ChunkGroupKey::Entry(entries) => ChunkGroup::Entry(entries),
1062                    ChunkGroupKey::Async(module) => ChunkGroup::Async(module),
1063                    ChunkGroupKey::Collected(module) => ChunkGroup::Collected(module),
1064                    ChunkGroupKey::Isolated(module) => ChunkGroup::Isolated(module),
1065                    ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
1066                        ChunkGroup::IsolatedMerged {
1067                            parent: parent.0 as usize,
1068                            merge_tag,
1069                            entries: merged_entries.into_iter().collect(),
1070                        }
1071                    }
1072                    ChunkGroupKey::Shared(module) => ChunkGroup::Shared(module),
1073                    ChunkGroupKey::SharedMultiple(entries) => ChunkGroup::SharedMultiple(entries),
1074                    ChunkGroupKey::SharedMerged { parent, merge_tag } => ChunkGroup::SharedMerged {
1075                        parent: parent.0 as usize,
1076                        merge_tag,
1077                        entries: merged_entries.into_iter().collect(),
1078                    },
1079                })
1080                .collect(),
1081        }
1082        .cell())
1083    }
1084    .instrument(span_outer)
1085    .await
1086}