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},
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)
416                            .context("Module depth not found")?;
417                        module_depth.entry(node).or_insert(parent_depth + 1);
418                    } else {
419                        module_depth.insert(node, 0);
420                    };
421
422                    module_chunk_groups.insert(node, 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<(ResolvedVc<Box<dyn Module>>, &'_ RefData)>,
511             node: ResolvedVc<Box<dyn Module>>,
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 { .. } => ChunkGroupInheritance::Inherit(parent),
524                        ChunkingType::Async => ChunkGroupInheritance::ChunkGroup(Either::Left(
525                            std::iter::once(ChunkGroupKey::Async(node)),
526                        )),
527                        ChunkingType::Isolated {
528                            merge_tag: None, ..
529                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
530                            ChunkGroupKey::Isolated(node),
531                        ))),
532                        ChunkingType::Shared {
533                            merge_tag: None, ..
534                        } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
535                            ChunkGroupKey::Shared(node),
536                        ))),
537                        ChunkingType::Isolated {
538                            merge_tag: Some(merge_tag),
539                            ..
540                        } => {
541                            let parents = module_chunk_groups
542                                .get(&parent)
543                                .context("Module chunk group not found")?;
544                            let chunk_groups =
545                                parents.iter().map(|parent| ChunkGroupKey::IsolatedMerged {
546                                    parent: ChunkGroupId(parent),
547                                    merge_tag: merge_tag.clone(),
548                                });
549                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Left(
550                                chunk_groups,
551                            )))
552                        }
553                        ChunkingType::Shared {
554                            merge_tag: Some(merge_tag),
555                            ..
556                        } => {
557                            let parents = module_chunk_groups
558                                .get(&parent)
559                                .context("Module chunk group not found")?;
560                            let chunk_groups =
561                                parents.iter().map(|parent| ChunkGroupKey::SharedMerged {
562                                    parent: ChunkGroupId(parent),
563                                    merge_tag: merge_tag.clone(),
564                                });
565                            ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Right(
566                                chunk_groups,
567                            )))
568                        }
569                        ChunkingType::Traced => {
570                            // Traced modules are not placed in chunk groups
571                            return Ok(GraphTraversalAction::Skip);
572                        }
573                    }
574                } else {
575                    ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
576                        // TODO remove clone
577                        entry_chunk_group_keys
578                            .get(&node)
579                            .context("Module chunk group not found")?
580                            .clone(),
581                    )))
582                };
583
584                Ok(match chunk_groups {
585                    ChunkGroupInheritance::ChunkGroup(chunk_groups) => {
586                        // Start of a new chunk group, don't inherit anything from parent
587                        let chunk_group_ids = chunk_groups.map(|chunk_group| {
588                            let len = chunk_groups_map.len();
589                            let is_merged = matches!(
590                                chunk_group,
591                                ChunkGroupKey::IsolatedMerged { .. }
592                                    | ChunkGroupKey::SharedMerged { .. }
593                            );
594                            match chunk_groups_map.entry(chunk_group) {
595                                Entry::Occupied(mut e) => {
596                                    let (id, merged_entries) = e.get_mut();
597                                    if is_merged {
598                                        merged_entries.insert(node);
599                                    }
600                                    **id
601                                }
602                                Entry::Vacant(e) => {
603                                    let chunk_group_id = len as u32;
604                                    let mut set = FxIndexSet::default();
605                                    if is_merged {
606                                        set.insert(node);
607                                    }
608                                    e.insert((ChunkGroupId(chunk_group_id), set));
609                                    chunk_group_id
610                                }
611                            }
612                        });
613
614                        let chunk_groups =
615                            RoaringBitmapWrapper(RoaringBitmap::from_iter(chunk_group_ids));
616
617                        // Assign chunk group to the target node (the entry of the chunk group)
618                        let bitset = module_chunk_groups
619                            .get_mut(&node)
620                            .context("Module chunk group not found")?;
621                        if chunk_groups.is_proper_superset(bitset) {
622                            // Add bits from parent, and continue traversal because changed
623                            **bitset |= chunk_groups.into_inner();
624
625                            GraphTraversalAction::Continue
626                        } else {
627                            // Unchanged, no need to forward to children
628                            GraphTraversalAction::Skip
629                        }
630                    }
631                    ChunkGroupInheritance::Inherit(parent) => {
632                        // Inherit chunk groups from parent, merge parent chunk groups into
633                        // current
634
635                        if parent == node {
636                            // A self-reference
637                            GraphTraversalAction::Skip
638                        } else {
639                            let [Some(parent_chunk_groups), Some(current_chunk_groups)] =
640                                module_chunk_groups.get_disjoint_mut([&parent, &node])
641                            else {
642                                // All modules are inserted in the previous iteration
643                                // Technically unreachable, but could be reached due to eventual
644                                // consistency
645                                bail!("Module chunk groups not found");
646                            };
647
648                            if current_chunk_groups.is_empty() {
649                                // Initial visit, clone instead of merging
650                                *current_chunk_groups = parent_chunk_groups.clone();
651                                GraphTraversalAction::Continue
652                            } else if parent_chunk_groups.is_proper_superset(current_chunk_groups) {
653                                // Add bits from parent, and continue traversal because changed
654                                **current_chunk_groups |= &**parent_chunk_groups;
655                                GraphTraversalAction::Continue
656                            } else {
657                                // Unchanged, no need to forward to children
658                                GraphTraversalAction::Skip
659                            }
660                        }
661                    }
662                })
663            },
664            // This priority is used as a heuristic to keep the number of retraversals down, by
665            // - keeping it similar to a BFS via the depth priority
666            // - prioritizing smaller chunk groups which are expected to themselves reference
667            //   bigger chunk groups (i.e. shared code deeper down in the graph).
668            //
669            // Both try to first visit modules with a large dependency subgraph first (which
670            // would be higher in the graph and are included by few chunks themselves).
671            |successor, module_chunk_groups| {
672                Ok(TraversalPriority {
673                    depth: *module_depth
674                        .get(&successor)
675                        .context("Module depth not found")?,
676                    chunk_group_len: module_chunk_groups
677                        .get(&successor)
678                        .context("Module chunk group not found")?
679                        .len(),
680                })
681            },
682        )?;
683
684        span.record("visit_count", visit_count);
685        span.record("chunk_group_count", chunk_groups_map.len());
686
687        #[cfg(debug_assertions)]
688        {
689            use once_cell::sync::Lazy;
690            static PRINT_CHUNK_GROUP_INFO: Lazy<bool> =
691                Lazy::new(|| match std::env::var_os("TURBOPACK_PRINT_CHUNK_GROUPS") {
692                    Some(v) => v == "1",
693                    None => false,
694                });
695            if *PRINT_CHUNK_GROUP_INFO {
696                use std::{
697                    collections::{BTreeMap, BTreeSet},
698                    path::absolute,
699                };
700
701                let mut buckets = BTreeMap::default();
702                for (module, key) in &module_chunk_groups {
703                    if !key.is_empty() {
704                        buckets
705                            .entry(key.iter().collect::<Vec<_>>())
706                            .or_insert(BTreeSet::new())
707                            .insert(module.ident().to_string().await?);
708                    }
709                }
710
711                let mut result = vec![];
712                result.push("Chunk Groups:".to_string());
713                for (i, (key, _)) in chunk_groups_map.iter().enumerate() {
714                    result.push(format!(
715                        "  {:?}: {}",
716                        i,
717                        key.debug_str(chunk_groups_map.keys()).await?
718                    ));
719                }
720                result.push("# Module buckets:".to_string());
721                for (key, modules) in buckets.iter() {
722                    result.push(format!("## {:?}:", key.iter().collect::<Vec<_>>()));
723                    for module in modules {
724                        result.push(format!("  {module}"));
725                    }
726                    result.push("".to_string());
727                }
728                let f = absolute("chunk_group_info.log")?;
729                println!("written to {}", f.display());
730                std::fs::write(f, result.join("\n"))?;
731            }
732        }
733
734        Ok(ChunkGroupInfo {
735            module_chunk_groups,
736            chunk_group_keys: chunk_groups_map.keys().cloned().collect(),
737            chunk_groups: chunk_groups_map
738                .into_iter()
739                .map(|(k, (_, merged_entries))| match k {
740                    ChunkGroupKey::Entry(entries) => ChunkGroup::Entry(entries),
741                    ChunkGroupKey::Async(module) => ChunkGroup::Async(module),
742                    ChunkGroupKey::Isolated(module) => ChunkGroup::Isolated(module),
743                    ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
744                        ChunkGroup::IsolatedMerged {
745                            parent: parent.0 as usize,
746                            merge_tag,
747                            entries: merged_entries.into_iter().collect(),
748                        }
749                    }
750                    ChunkGroupKey::Shared(module) => ChunkGroup::Shared(module),
751                    ChunkGroupKey::SharedMerged { parent, merge_tag } => ChunkGroup::SharedMerged {
752                        parent: parent.0 as usize,
753                        merge_tag,
754                        entries: merged_entries.into_iter().collect(),
755                    },
756                })
757                .collect(),
758        }
759        .cell())
760    }
761    .instrument(span_outer)
762    .await
763}
turbopack_core/module_graph/chunk_group_info.rs

turbopack_core/module_graph/
chunk_group_info.rs
