turbopack_core/module_graph/
chunk_group_info.rs

1use std::{
2    hash::Hash,
3    ops::{Deref, DerefMut},
4};
5
6use anyhow::{Context, Result, bail};
7use either::Either;
8use indexmap::map::Entry;
9use roaring::RoaringBitmap;
10use rustc_hash::FxHashMap;
11use serde::{Deserialize, Serialize};
12use tracing::Instrument;
13use turbo_rcstr::RcStr;
14use turbo_tasks::{
15    FxIndexMap, FxIndexSet, NonLocalValue, ResolvedVc, TaskInput, TryJoinIterExt, ValueToString,
16    Vc, debug::ValueDebugFormat, trace::TraceRawVcs,
17};
18
19use crate::{
20    chunk::ChunkingType,
21    module::Module,
22    module_graph::{GraphTraversalAction, ModuleGraphRef, RefData, SingleModuleGraphModuleNode},
23};
24
25#[derive(
26    Clone, Debug, Default, PartialEq, Serialize, Deserialize, TraceRawVcs, ValueDebugFormat,
27)]
28#[repr(transparent)]
29pub struct RoaringBitmapWrapper(#[turbo_tasks(trace_ignore)] pub RoaringBitmap);
30
31impl TaskInput for RoaringBitmapWrapper {
32    fn is_transient(&self) -> bool {
33        false
34    }
35}
36
37impl RoaringBitmapWrapper {
38    /// Whether `self` contains bits that are not in `other`
39    ///
40    /// The existing `is_superset` method also returns true for equal sets
41    pub fn is_proper_superset(&self, other: &Self) -> bool {
42        !self.is_subset(other)
43    }
44
45    pub fn into_inner(self) -> RoaringBitmap {
46        self.0
47    }
48}
49unsafe impl NonLocalValue for RoaringBitmapWrapper {}
50
51// RoaringBitmap doesn't impl Eq: https://github.com/RoaringBitmap/roaring-rs/issues/302
52// PartialEq can only return true if both bitmaps have the same internal representation, but two
53// bitmaps with the same content should always have the same internal representation
54impl Eq for RoaringBitmapWrapper {}
55
56impl Deref for RoaringBitmapWrapper {
57    type Target = RoaringBitmap;
58    fn deref(&self) -> &Self::Target {
59        &self.0
60    }
61}
62impl DerefMut for RoaringBitmapWrapper {
63    fn deref_mut(&mut self) -> &mut Self::Target {
64        &mut self.0
65    }
66}
67impl Hash for RoaringBitmapWrapper {
68    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
69        struct HasherWriter<'a, H: std::hash::Hasher>(&'a mut H);
70        impl<H: std::hash::Hasher> std::io::Write for HasherWriter<'_, H> {
71            fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
72                self.0.write(buf);
73                Ok(buf.len())
74            }
75            fn flush(&mut self) -> std::io::Result<()> {
76                Ok(())
77            }
78        }
79        self.0.serialize_into(HasherWriter(state)).unwrap();
80    }
81}
82
83#[turbo_tasks::value]
84pub struct ChunkGroupInfo {
85    pub module_chunk_groups: FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper>,
86    #[turbo_tasks(trace_ignore)]
87    pub chunk_groups: FxIndexSet<ChunkGroup>,
88    #[turbo_tasks(trace_ignore)]
89    pub chunk_group_keys: FxIndexSet<ChunkGroupKey>,
90}
91
92#[turbo_tasks::value_impl]
93impl ChunkGroupInfo {
94    #[turbo_tasks::function]
95    pub async fn get_index_of(&self, chunk_group: ChunkGroup) -> Result<Vc<usize>> {
96        if let Some(idx) = self.chunk_groups.get_index_of(&chunk_group) {
97            Ok(Vc::cell(idx))
98        } else {
99            bail!(
100                "Couldn't find chunk group index for {} in {}",
101                chunk_group.debug_str(self).await?,
102                self.chunk_groups
103                    .iter()
104                    .map(|c| c.debug_str(self))
105                    .try_join()
106                    .await?
107                    .join(", ")
108            );
109        }
110    }
111}
112
113#[derive(
114    Debug, Clone, Hash, TaskInput, PartialEq, Eq, Serialize, Deserialize, TraceRawVcs, NonLocalValue,
115)]
116pub enum ChunkGroupEntry {
117    /// e.g. a page
118    Entry(Vec<ResolvedVc<Box<dyn Module>>>),
119    /// a module with an incoming async edge
120    Async(ResolvedVc<Box<dyn Module>>),
121    /// a module with an incoming non-merged isolated edge
122    Isolated(ResolvedVc<Box<dyn Module>>),
123    /// a module with an incoming merging isolated edge
124    IsolatedMerged {
125        parent: Box<ChunkGroupEntry>,
126        merge_tag: RcStr,
127        entries: Vec<ResolvedVc<Box<dyn Module>>>,
128    },
129    /// a module with an incoming non-merging shared edge
130    Shared(ResolvedVc<Box<dyn Module>>),
131    /// a module with an incoming merging shared edge
132    SharedMerged {
133        parent: Box<ChunkGroupEntry>,
134        merge_tag: RcStr,
135        entries: Vec<ResolvedVc<Box<dyn Module>>>,
136    },
137}
138impl ChunkGroupEntry {
139    pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + '_ {
140        match self {
141            Self::Async(e) | Self::Isolated(e) | Self::Shared(e) => {
142                Either::Left(std::iter::once(*e))
143            }
144            Self::Entry(entries)
145            | Self::IsolatedMerged { entries, .. }
146            | Self::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
147        }
148    }
149}
150
151#[derive(Debug, Clone, Hash, TaskInput, PartialEq, Eq, Serialize, Deserialize, TraceRawVcs)]
152pub enum ChunkGroup {
153    /// e.g. a page
154    Entry(Vec<ResolvedVc<Box<dyn Module>>>),
155    /// a module with an incoming async edge
156    Async(ResolvedVc<Box<dyn Module>>),
157    /// a module with an incoming non-merged isolated edge
158    Isolated(ResolvedVc<Box<dyn Module>>),
159    /// a module with an incoming merging isolated edge
160    IsolatedMerged {
161        parent: usize,
162        merge_tag: RcStr,
163        entries: Vec<ResolvedVc<Box<dyn Module>>>,
164    },
165    /// a module with an incoming non-merging shared edge
166    Shared(ResolvedVc<Box<dyn Module>>),
167    /// a module with an incoming merging shared edge
168    SharedMerged {
169        parent: usize,
170        merge_tag: RcStr,
171        entries: Vec<ResolvedVc<Box<dyn Module>>>,
172    },
173}
174
175impl ChunkGroup {
176    /// Returns the parent group when this chunk group is a merged group. In that case `entries()`
177    /// are in unspecified order.
178    pub fn get_merged_parent(&self) -> Option<usize> {
179        match self {
180            ChunkGroup::IsolatedMerged { parent, .. } | ChunkGroup::SharedMerged { parent, .. } => {
181                Some(*parent)
182            }
183            _ => None,
184        }
185    }
186
187    /// Iterates over the entries of the chunk group. When `get_merged_parent` is Some, the order is
188    /// unspecified.
189    pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + Clone + '_ {
190        match self {
191            ChunkGroup::Async(e) | ChunkGroup::Isolated(e) | ChunkGroup::Shared(e) => {
192                Either::Left(std::iter::once(*e))
193            }
194            ChunkGroup::Entry(entries)
195            | ChunkGroup::IsolatedMerged { entries, .. }
196            | ChunkGroup::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
197        }
198    }
199
200    pub fn entries_count(&self) -> usize {
201        match self {
202            ChunkGroup::Async(_) | ChunkGroup::Isolated(_) | ChunkGroup::Shared(_) => 1,
203            ChunkGroup::Entry(entries)
204            | ChunkGroup::IsolatedMerged { entries, .. }
205            | ChunkGroup::SharedMerged { entries, .. } => entries.len(),
206        }
207    }
208
209    pub async fn debug_str(&self, chunk_group_info: &ChunkGroupInfo) -> Result<String> {
210        Ok(match self {
211            ChunkGroup::Entry(entries) => format!(
212                "ChunkGroup::Entry({:?})",
213                entries
214                    .iter()
215                    .map(|m| m.ident().to_string())
216                    .try_join()
217                    .await?
218            ),
219            ChunkGroup::Async(entry) => {
220                format!("ChunkGroup::Async({:?})", entry.ident().to_string().await?)
221            }
222            ChunkGroup::Isolated(entry) => {
223                format!(
224                    "ChunkGroup::Isolated({:?})",
225                    entry.ident().to_string().await?
226                )
227            }
228            ChunkGroup::Shared(entry) => {
229                format!("ChunkGroup::Shared({:?})", entry.ident().to_string().await?)
230            }
231            ChunkGroup::IsolatedMerged {
232                parent,
233                merge_tag,
234                entries,
235            } => {
236                format!(
237                    "ChunkGroup::IsolatedMerged({}, {}, {:?})",
238                    Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
239                        .await?,
240                    merge_tag,
241                    entries
242                        .iter()
243                        .map(|m| m.ident().to_string())
244                        .try_join()
245                        .await?
246                )
247            }
248            ChunkGroup::SharedMerged {
249                parent,
250                merge_tag,
251                entries,
252            } => {
253                format!(
254                    "ChunkGroup::SharedMerged({}, {}, {:?})",
255                    Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
256                        .await?,
257                    merge_tag,
258                    entries
259                        .iter()
260                        .map(|m| m.ident().to_string())
261                        .try_join()
262                        .await?
263                )
264            }
265        })
266    }
267}
268
269#[derive(Debug, Clone, Hash, PartialEq, Eq, Serialize, Deserialize)]
270pub enum ChunkGroupKey {
271    /// e.g. a page
272    Entry(Vec<ResolvedVc<Box<dyn Module>>>),
273    /// a module with an incoming async edge
274    Async(ResolvedVc<Box<dyn Module>>),
275    /// a module with an incoming non-merging isolated edge
276    Isolated(ResolvedVc<Box<dyn Module>>),
277    /// a module with an incoming merging isolated edge
278    IsolatedMerged {
279        parent: ChunkGroupId,
280        merge_tag: RcStr,
281    },
282    /// a module with an incoming non-merging shared edge
283    Shared(ResolvedVc<Box<dyn Module>>),
284    /// a module with an incoming merging shared edge
285    SharedMerged {
286        parent: ChunkGroupId,
287        merge_tag: RcStr,
288    },
289}
290
291impl ChunkGroupKey {
292    pub async fn debug_str(
293        &self,
294        keys: impl std::ops::Index<usize, Output = Self>,
295    ) -> Result<String> {
296        Ok(match self {
297            ChunkGroupKey::Entry(entries) => format!(
298                "Entry({:?})",
299                entries
300                    .iter()
301                    .map(|m| m.ident().to_string())
302                    .try_join()
303                    .await?
304            ),
305            ChunkGroupKey::Async(module) => {
306                format!("Async({:?})", module.ident().to_string().await?)
307            }
308            ChunkGroupKey::Isolated(module) => {
309                format!("Isolated({:?})", module.ident().to_string().await?)
310            }
311            ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
312                format!(
313                    "IsolatedMerged {{ parent: {}, merge_tag: {:?} }}",
314                    Box::pin(keys.index(parent.0 as usize).clone().debug_str(keys)).await?,
315                    merge_tag
316                )
317            }
318            ChunkGroupKey::Shared(module) => {
319                format!("Shared({:?})", module.ident().to_string().await?)
320            }
321            ChunkGroupKey::SharedMerged { parent, merge_tag } => {
322                format!(
323                    "SharedMerged {{ parent: {}, merge_tag: {:?} }}",
324                    Box::pin(keys.index(parent.0 as usize).clone().debug_str(keys)).await?,
325                    merge_tag
326                )
327            }
328        })
329    }
330}
331
332#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
333pub struct ChunkGroupId(u32);
334
335impl From<usize> for ChunkGroupId {
336    fn from(id: usize) -> Self {
337        Self(id as u32)
338    }
339}
340
341impl Deref for ChunkGroupId {
342    type Target = u32;
343    fn deref(&self) -> &Self::Target {
344        &self.0
345    }
346}
347
348#[derive(Debug, Clone, PartialEq, Eq)]
349struct TraversalPriority {
350    depth: usize,
351    chunk_group_len: u64,
352}
353impl PartialOrd for TraversalPriority {
354    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
355        Some(self.cmp(other))
356    }
357}
358impl Ord for TraversalPriority {
359    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
360        // BinaryHeap prioritizes high values
361
362        // Smaller depth has higher priority
363        let depth_order = self.depth.cmp(&other.depth).reverse();
364        // Smaller group length has higher priority
365        let chunk_group_len_order = self.chunk_group_len.cmp(&other.chunk_group_len).reverse();
366
367        depth_order.then(chunk_group_len_order)
368    }
369}
370
371pub async fn compute_chunk_group_info(graph: &ModuleGraphRef) -> Result<Vc<ChunkGroupInfo>> {
372    let span_outer = tracing::info_span!(
373        "compute chunk group info",
374        module_count = tracing::field::Empty,
375        visit_count = tracing::field::Empty,
376        chunk_group_count = tracing::field::Empty
377    );
378
379    let span = span_outer.clone();
380    async move {
381        #[allow(clippy::type_complexity)]
382        let mut chunk_groups_map: FxIndexMap<
383            ChunkGroupKey,
384            (ChunkGroupId, FxIndexSet<ResolvedVc<Box<dyn Module>>>),
385        > = FxIndexMap::default();
386
387        // For each module, the indices in the bitmap store which chunk groups in `chunk_groups_map`
388        // that module is part of.
389        let mut module_chunk_groups: FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper> =
390            FxHashMap::default();
391
392        let module_count = graph
393            .graphs
394            .iter()
395            .map(|g| g.graph.node_count())
396            .sum::<usize>();
397        span.record("module_count", module_count);
398
399        // use all entries from all graphs
400        let entries = graph
401            .graphs
402            .iter()
403            .flat_map(|g| g.entries.iter())
404            .collect::<Vec<_>>();
405
406        // First, compute the depth for each module in the graph
407        let module_depth: FxHashMap<ResolvedVc<Box<dyn Module>>, usize> = {
408            let mut module_depth =
409                FxHashMap::with_capacity_and_hasher(module_count, Default::default());
410            graph.traverse_edges_from_entries_bfs(
411                entries.iter().flat_map(|e| e.entries()),
412                |parent, node| {
413                    if let Some((parent, _)) = parent {
414                        let parent_depth = *module_depth
415                            .get(&parent.module)
416                            .context("Module depth not found")?;
417                        module_depth.entry(node.module).or_insert(parent_depth + 1);
418                    } else {
419                        module_depth.insert(node.module, 0);
420                    };
421
422                    module_chunk_groups.insert(node.module, RoaringBitmapWrapper::default());
423
424                    Ok(GraphTraversalAction::Continue)
425                },
426            )?;
427            module_depth
428        };
429
430        // ----
431
432        #[allow(clippy::type_complexity)]
433        fn entry_to_chunk_group_id(
434            entry: ChunkGroupEntry,
435            chunk_groups_map: &mut FxIndexMap<
436                ChunkGroupKey,
437                (ChunkGroupId, FxIndexSet<ResolvedVc<Box<dyn Module>>>),
438            >,
439        ) -> ChunkGroupKey {
440            match entry {
441                ChunkGroupEntry::Entry(entries) => ChunkGroupKey::Entry(entries),
442                ChunkGroupEntry::Async(entry) => ChunkGroupKey::Async(entry),
443                ChunkGroupEntry::Isolated(entry) => ChunkGroupKey::Isolated(entry),
444                ChunkGroupEntry::Shared(entry) => ChunkGroupKey::Shared(entry),
445                ChunkGroupEntry::IsolatedMerged {
446                    parent,
447                    merge_tag,
448                    entries: _,
449                } => {
450                    let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
451                    let len = chunk_groups_map.len();
452                    let parent = chunk_groups_map
453                        .entry(parent)
454                        .or_insert_with(|| (ChunkGroupId(len as u32), FxIndexSet::default()))
455                        .0;
456
457                    ChunkGroupKey::IsolatedMerged {
458                        parent: ChunkGroupId(*parent as u32),
459                        merge_tag,
460                    }
461                }
462                ChunkGroupEntry::SharedMerged {
463                    parent,
464                    merge_tag,
465                    entries: _,
466                } => {
467                    let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
468                    let len = chunk_groups_map.len();
469                    let parent = chunk_groups_map
470                        .entry(parent)
471                        .or_insert_with(|| (ChunkGroupId(len as u32), FxIndexSet::default()))
472                        .0;
473
474                    ChunkGroupKey::SharedMerged {
475                        parent: ChunkGroupId(*parent as u32),
476                        merge_tag,
477                    }
478                }
479            }
480        }
481
482        let entry_chunk_group_keys = graph
483            .graphs
484            .iter()
485            .flat_map(|g| g.entries.iter())
486            .flat_map(|chunk_group| {
487                let chunk_group_key =
488                    entry_to_chunk_group_id(chunk_group.clone(), &mut chunk_groups_map);
489                chunk_group
490                    .entries()
491                    .map(move |e| (e, chunk_group_key.clone()))
492            })
493            .collect::<FxHashMap<_, _>>();
494
495        let visit_count = graph.traverse_edges_fixed_point_with_priority(
496            entries
497                .iter()
498                .flat_map(|e| e.entries())
499                .map(|e| {
500                    Ok((
501                        e,
502                        TraversalPriority {
503                            depth: *module_depth.get(&e).context("Module depth not found")?,
504                            chunk_group_len: 0,
505                        },
506                    ))
507                })
508                .collect::<Result<Vec<_>>>()?,
509            &mut module_chunk_groups,
510            |parent_info: Option<(&'_ SingleModuleGraphModuleNode, &'_ RefData)>,
511             node: &'_ SingleModuleGraphModuleNode,
512             module_chunk_groups: &mut FxHashMap<
513                ResolvedVc<Box<dyn Module>>,
514                RoaringBitmapWrapper,
515            >|
516             -> Result<GraphTraversalAction> {
517                enum ChunkGroupInheritance<It: Iterator<Item = ChunkGroupKey>> {
518                    Inherit(ResolvedVc<Box<dyn Module>>),
519                    ChunkGroup(It),
520                }
521                let chunk_groups = if let Some((parent, ref_data)) = parent_info {
522                    match &ref_data.chunking_type {
523                        ChunkingType::Parallel { .. } => {
524                            ChunkGroupInheritance::Inherit(parent.module)
525                        }
526                        ChunkingType::Async => ChunkGroupInheritance::ChunkGroup(Either::Left(
527                            std::iter::once(ChunkGroupKey::Async(node.module)),
528                        )),
529                        ChunkingType::Isolated {
530                            merge_tag: None, ..
531                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
532                            ChunkGroupKey::Isolated(node.module),
533                        ))),
534                        ChunkingType::Shared {
535                            merge_tag: None, ..
536                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
537                            ChunkGroupKey::Shared(node.module),
538                        ))),
539                        ChunkingType::Isolated {
540                            merge_tag: Some(merge_tag),
541                            ..
542                        } => {
543                            let parents = module_chunk_groups
544                                .get(&parent.module)
545                                .context("Module chunk group not found")?;
546                            let chunk_groups =
547                                parents.iter().map(|parent| ChunkGroupKey::IsolatedMerged {
548                                    parent: ChunkGroupId(parent),
549                                    merge_tag: merge_tag.clone(),
550                                });
551                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Left(
552                                chunk_groups,
553                            )))
554                        }
555                        ChunkingType::Shared {
556                            merge_tag: Some(merge_tag),
557                            ..
558                        } => {
559                            let parents = module_chunk_groups
560                                .get(&parent.module)
561                                .context("Module chunk group not found")?;
562                            let chunk_groups =
563                                parents.iter().map(|parent| ChunkGroupKey::SharedMerged {
564                                    parent: ChunkGroupId(parent),
565                                    merge_tag: merge_tag.clone(),
566                                });
567                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Right(
568                                chunk_groups,
569                            )))
570                        }
571                        ChunkingType::Traced => {
572                            // Traced modules are not placed in chunk groups
573                            return Ok(GraphTraversalAction::Skip);
574                        }
575                    }
576                } else {
577                    ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
578                        // TODO remove clone
579                        entry_chunk_group_keys
580                            .get(&node.module)
581                            .context("Module chunk group not found")?
582                            .clone(),
583                    )))
584                };
585
586                Ok(match chunk_groups {
587                    ChunkGroupInheritance::ChunkGroup(chunk_groups) => {
588                        // Start of a new chunk group, don't inherit anything from parent
589                        let chunk_group_ids = chunk_groups.map(|chunk_group| {
590                            let len = chunk_groups_map.len();
591                            let is_merged = matches!(
592                                chunk_group,
593                                ChunkGroupKey::IsolatedMerged { .. }
594                                    | ChunkGroupKey::SharedMerged { .. }
595                            );
596                            match chunk_groups_map.entry(chunk_group) {
597                                Entry::Occupied(mut e) => {
598                                    let (id, merged_entries) = e.get_mut();
599                                    if is_merged {
600                                        merged_entries.insert(node.module);
601                                    }
602                                    **id
603                                }
604                                Entry::Vacant(e) => {
605                                    let chunk_group_id = len as u32;
606                                    let mut set = FxIndexSet::default();
607                                    if is_merged {
608                                        set.insert(node.module);
609                                    }
610                                    e.insert((ChunkGroupId(chunk_group_id), set));
611                                    chunk_group_id
612                                }
613                            }
614                        });
615
616                        let chunk_groups =
617                            RoaringBitmapWrapper(RoaringBitmap::from_iter(chunk_group_ids));
618
619                        // Assign chunk group to the target node (the entry of the chunk group)
620                        let bitset = module_chunk_groups
621                            .get_mut(&node.module)
622                            .context("Module chunk group not found")?;
623                        if chunk_groups.is_proper_superset(bitset) {
624                            // Add bits from parent, and continue traversal because changed
625                            **bitset |= chunk_groups.into_inner();
626
627                            GraphTraversalAction::Continue
628                        } else {
629                            // Unchanged, no need to forward to children
630                            GraphTraversalAction::Skip
631                        }
632                    }
633                    ChunkGroupInheritance::Inherit(parent) => {
634                        // Inherit chunk groups from parent, merge parent chunk groups into
635                        // current
636
637                        if parent == node.module {
638                            // A self-reference
639                            GraphTraversalAction::Skip
640                        } else {
641                            let [Some(parent_chunk_groups), Some(current_chunk_groups)] =
642                                module_chunk_groups.get_disjoint_mut([&parent, &node.module])
643                            else {
644                                // All modules are inserted in the previous iteration
645                                // Technically unreachable, but could be reached due to eventual
646                                // consistency
647                                bail!("Module chunk groups not found");
648                            };
649
650                            if current_chunk_groups.is_empty() {
651                                // Initial visit, clone instead of merging
652                                *current_chunk_groups = parent_chunk_groups.clone();
653                                GraphTraversalAction::Continue
654                            } else if parent_chunk_groups.is_proper_superset(current_chunk_groups) {
655                                // Add bits from parent, and continue traversal because changed
656                                **current_chunk_groups |= &**parent_chunk_groups;
657                                GraphTraversalAction::Continue
658                            } else {
659                                // Unchanged, no need to forward to children
660                                GraphTraversalAction::Skip
661                            }
662                        }
663                    }
664                })
665            },
666            // This priority is used as a heuristic to keep the number of retraversals down, by
667            // - keeping it similar to a BFS via the depth priority
668            // - prioritizing smaller chunk groups which are expected to themselves reference
669            //   bigger chunk groups (i.e. shared code deeper down in the graph).
670            //
671            // Both try to first visit modules with a large dependency subgraph first (which
672            // would be higher in the graph and are included by few chunks themselves).
673            |successor, module_chunk_groups| {
674                Ok(TraversalPriority {
675                    depth: *module_depth
676                        .get(&successor.module)
677                        .context("Module depth not found")?,
678                    chunk_group_len: module_chunk_groups
679                        .get(&successor.module)
680                        .context("Module chunk group not found")?
681                        .len(),
682                })
683            },
684        )?;
685
686        span.record("visit_count", visit_count);
687        span.record("chunk_group_count", chunk_groups_map.len());
688
689        #[cfg(debug_assertions)]
690        {
691            use once_cell::sync::Lazy;
692            static PRINT_CHUNK_GROUP_INFO: Lazy<bool> =
693                Lazy::new(|| match std::env::var_os("TURBOPACK_PRINT_CHUNK_GROUPS") {
694                    Some(v) => v == "1",
695                    None => false,
696                });
697            if *PRINT_CHUNK_GROUP_INFO {
698                use std::{
699                    collections::{BTreeMap, BTreeSet},
700                    path::absolute,
701                };
702
703                let mut buckets = BTreeMap::default();
704                for (module, key) in &module_chunk_groups {
705                    if !key.is_empty() {
706                        buckets
707                            .entry(key.iter().collect::<Vec<_>>())
708                            .or_insert(BTreeSet::new())
709                            .insert(module.ident().to_string().await?);
710                    }
711                }
712
713                let mut result = vec![];
714                result.push("Chunk Groups:".to_string());
715                for (i, (key, _)) in chunk_groups_map.iter().enumerate() {
716                    result.push(format!(
717                        "  {:?}: {}",
718                        i,
719                        key.debug_str(chunk_groups_map.keys()).await?
720                    ));
721                }
722                result.push("# Module buckets:".to_string());
723                for (key, modules) in buckets.iter() {
724                    result.push(format!("## {:?}:", key.iter().collect::<Vec<_>>()));
725                    for module in modules {
726                        result.push(format!("  {module}"));
727                    }
728                    result.push("".to_string());
729                }
730                let f = absolute("chunk_group_info.log")?;
731                println!("written to {}", f.display());
732                std::fs::write(f, result.join("\n"))?;
733            }
734        }
735
736        Ok(ChunkGroupInfo {
737            module_chunk_groups,
738            chunk_group_keys: chunk_groups_map.keys().cloned().collect(),
739            chunk_groups: chunk_groups_map
740                .into_iter()
741                .map(|(k, (_, merged_entries))| match k {
742                    ChunkGroupKey::Entry(entries) => ChunkGroup::Entry(entries),
743                    ChunkGroupKey::Async(module) => ChunkGroup::Async(module),
744                    ChunkGroupKey::Isolated(module) => ChunkGroup::Isolated(module),
745                    ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
746                        ChunkGroup::IsolatedMerged {
747                            parent: parent.0 as usize,
748                            merge_tag,
749                            entries: merged_entries.into_iter().collect(),
750                        }
751                    }
752                    ChunkGroupKey::Shared(module) => ChunkGroup::Shared(module),
753                    ChunkGroupKey::SharedMerged { parent, merge_tag } => ChunkGroup::SharedMerged {
754                        parent: parent.0 as usize,
755                        merge_tag,
756                        entries: merged_entries.into_iter().collect(),
757                    },
758                })
759                .collect(),
760        }
761        .cell())
762    }
763    .instrument(span_outer)
764    .await
765}
turbopack_core/module_graph/chunk_group_info.rs

turbopack_core/module_graph/
chunk_group_info.rs
