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

turbopack_core/module_graph/
chunk_group_info.rs
