1use std::{
2 cmp::Reverse,
3 hash::Hash,
4 ops::{Deref, DerefMut},
5 sync::LazyLock,
6};
7
8use anyhow::{Context, Result, bail};
9use bincode::{Decode, Encode};
10use either::Either;
11use indexmap::map::Entry;
12use roaring::RoaringBitmap;
13use rustc_hash::FxHashMap;
14use tracing::Instrument;
15use turbo_rcstr::RcStr;
16use turbo_tasks::{
17 FxIndexMap, FxIndexSet, NonLocalValue, ResolvedVc, TaskInput, TryJoinIterExt, ValueToString,
18 Vc, debug::ValueDebugFormat, turbofmt,
19};
20use turbo_tasks_hash::{DeterministicHash, DeterministicHasher};
21
22use crate::{
23 chunk::ChunkingType,
24 module::Module,
25 module_graph::{GraphTraversalAction, ModuleGraph, RefData},
26};
27
28#[derive(Clone, Debug, Default, PartialEq, ValueDebugFormat, Encode, Decode)]
29#[repr(transparent)]
30pub struct RoaringBitmapWrapper(#[bincode(with_serde)] pub RoaringBitmap);
31
32impl TaskInput for RoaringBitmapWrapper {
33 fn is_transient(&self) -> bool {
34 false
35 }
36}
37
38impl RoaringBitmapWrapper {
39 pub fn is_proper_superset(&self, other: &Self) -> bool {
43 !self.is_subset(other)
44 }
45
46 pub fn into_inner(self) -> RoaringBitmap {
47 self.0
48 }
49}
50unsafe impl NonLocalValue for RoaringBitmapWrapper {}
51
52impl Eq for RoaringBitmapWrapper {}
56
57impl Deref for RoaringBitmapWrapper {
58 type Target = RoaringBitmap;
59 fn deref(&self) -> &Self::Target {
60 &self.0
61 }
62}
63impl DerefMut for RoaringBitmapWrapper {
64 fn deref_mut(&mut self) -> &mut Self::Target {
65 &mut self.0
66 }
67}
68impl Hash for RoaringBitmapWrapper {
69 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
70 struct HasherWriter<'a, H: std::hash::Hasher>(&'a mut H);
71 impl<H: std::hash::Hasher> std::io::Write for HasherWriter<'_, H> {
72 fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
73 self.0.write(buf);
74 Ok(buf.len())
75 }
76 fn flush(&mut self) -> std::io::Result<()> {
77 Ok(())
78 }
79 }
80 self.0.serialize_into(HasherWriter(state)).unwrap();
81 }
82}
83
84impl DeterministicHash for RoaringBitmapWrapper {
85 fn deterministic_hash<H: DeterministicHasher>(&self, state: &mut H) {
86 struct HasherWriter<'a, H: DeterministicHasher>(&'a mut H);
87 impl<H: DeterministicHasher> std::io::Write for HasherWriter<'_, H> {
88 fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
89 self.0.write_bytes(buf);
90 Ok(buf.len())
91 }
92 fn flush(&mut self) -> std::io::Result<()> {
93 Ok(())
94 }
95 }
96 self.0.serialize_into(HasherWriter(state)).unwrap();
98 }
99}
100
101#[turbo_tasks::value(transparent, cell = "keyed")]
102pub struct ModuleToChunkGroups(FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper>);
103
104#[turbo_tasks::value]
105pub struct ChunkGroupWithIndex {
106 pub index: u32,
107 pub chunk_group: ChunkGroup,
108}
109
110#[turbo_tasks::value(transparent)]
111pub struct ChunkGroups(Vec<ChunkGroupWithIndex>);
112
113#[turbo_tasks::value(transparent)]
114pub struct OptionChunkGroupWithIndex(Option<ChunkGroupWithIndex>);
115
116#[turbo_tasks::value(transparent, cell = "keyed")]
123pub struct ChunkGroupKeyToIndex(FxHashMap<ChunkGroupKey, u32>);
124
125#[turbo_tasks::value]
126pub struct ChunkGroupInfo {
127 pub module_chunk_groups: ResolvedVc<ModuleToChunkGroups>,
128 pub async_loader_chunk_groups: ResolvedVc<ModuleToChunkGroups>,
130 #[bincode(with = "turbo_bincode::indexset")]
131 pub chunk_groups: FxIndexSet<ChunkGroup>,
132 #[turbo_tasks(unsafe_ignore)]
133 #[bincode(with = "turbo_bincode::indexset")]
134 pub chunk_group_keys: FxIndexSet<ChunkGroupKey>,
135 pub chunk_group_indices: ResolvedVc<ChunkGroupKeyToIndex>,
138 pub chunking_heuristics: ChunkingHeuristicsInfo,
139}
140
141#[derive(Debug, Default, Clone, PartialEq, Eq, ValueDebugFormat, NonLocalValue, Encode, Decode)]
145pub struct ChunkingHeuristicsInfo {
146 pub clusters: Vec<Vec<u16>>,
152 pub priority_routes: RoaringBitmapWrapper,
158}
159
160#[turbo_tasks::value_impl]
161impl ChunkGroupInfo {
162 #[turbo_tasks::function]
163 pub fn module_chunk_groups(&self) -> Vc<ModuleToChunkGroups> {
164 *self.module_chunk_groups
165 }
166
167 #[turbo_tasks::function]
170 pub fn chunk_group_indices(&self) -> Vc<ChunkGroupKeyToIndex> {
171 *self.chunk_group_indices
172 }
173
174 #[turbo_tasks::function]
177 pub async fn get_chunk_groups_for_module(
178 &self,
179 module: ResolvedVc<Box<dyn Module>>,
180 ) -> Result<Vc<ChunkGroups>> {
181 let module_chunk_groups = self.module_chunk_groups.await?;
182 let Some(groups) = module_chunk_groups.get(&module) else {
183 return Ok(Vc::cell(Vec::new()));
184 };
185 Ok(Vc::cell(
186 groups
187 .iter()
188 .map(|index| ChunkGroupWithIndex {
189 index,
190 chunk_group: self.chunk_groups[index as usize].clone(),
191 })
192 .collect(),
193 ))
194 }
195
196 #[turbo_tasks::function]
202 pub fn get_shared_merged_chunk_group(
203 &self,
204 parent: usize,
205 merge_tag: RcStr,
206 ) -> Vc<OptionChunkGroupWithIndex> {
207 let key = ChunkGroupKey::SharedMerged {
208 parent: ChunkGroupId::from(parent),
209 merge_tag,
210 };
211 Vc::cell(
212 self.chunk_group_keys
213 .get_index_of(&key)
214 .map(|index| ChunkGroupWithIndex {
215 index: index as u32,
216 chunk_group: self.chunk_groups[index].clone(),
217 }),
218 )
219 }
220}
221
222impl ChunkGroupInfo {
223 pub async fn get_index_of(self: Vc<Self>, key: ChunkGroupKey) -> Result<usize> {
234 if let Some(idx) = self.chunk_group_indices().get(&key).await? {
235 Ok(*idx as usize)
236 } else if cfg!(debug_assertions) {
237 let this = self.await?;
239 bail!(
240 "Couldn't find chunk group index for {} in {}",
241 key.debug_str(&this.chunk_group_keys).await?,
242 this.chunk_groups
243 .iter()
244 .map(|c| c.debug_str(&this))
245 .try_join()
246 .await?
247 .join(", ")
248 )
249 } else {
250 bail!("Couldn't find chunk group index")
251 }
252 }
253
254 pub async fn get_chunk_group(self: Vc<Self>, key: ChunkGroupKey) -> Result<ChunkGroup> {
259 let index = self.get_index_of(key).await?;
260 Ok(self.await?.chunk_groups[index].clone())
261 }
262}
263
264#[turbo_tasks::task_input]
266#[derive(Debug, Default, Clone, Hash, PartialEq, Eq, Encode, Decode)]
267pub struct EntryHeuristics {
268 pub clusters: Vec<u16>,
270 pub high_priority: bool,
271}
272
273impl EntryHeuristics {
274 pub fn high_priority() -> Self {
277 Self {
278 clusters: Vec::new(),
279 high_priority: true,
280 }
281 }
282}
283
284#[turbo_tasks::task_input]
286#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
287pub enum ChunkGroupEntry {
288 Entry {
289 modules: Vec<ResolvedVc<Box<dyn Module>>>,
290 heuristics: EntryHeuristics,
291 },
292 Async(ResolvedVc<Box<dyn Module>>),
293 Isolated(ResolvedVc<Box<dyn Module>>),
294 IsolatedMerged {
295 parent: Box<ChunkGroupEntry>,
296 merge_tag: RcStr,
297 entries: Vec<ResolvedVc<Box<dyn Module>>>,
298 },
299 Shared(ResolvedVc<Box<dyn Module>>),
300 SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
301 SharedMerged {
302 parent: Box<ChunkGroupEntry>,
303 merge_tag: RcStr,
304 entries: Vec<ResolvedVc<Box<dyn Module>>>,
305 },
306}
307impl ChunkGroupEntry {
308 pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + '_ {
309 match self {
310 Self::Async(e) | Self::Isolated(e) | Self::Shared(e) => {
311 Either::Left(std::iter::once(*e))
312 }
313 Self::Entry {
314 modules: entries, ..
315 }
316 | Self::IsolatedMerged { entries, .. }
317 | Self::SharedMultiple(entries)
318 | Self::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
319 }
320 }
321}
322
323#[turbo_tasks::task_input]
324#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
325pub enum ChunkGroup {
326 Entry(Vec<ResolvedVc<Box<dyn Module>>>),
329 Async(ResolvedVc<Box<dyn Module>>),
331 Isolated(ResolvedVc<Box<dyn Module>>),
334 IsolatedMerged {
337 parent: usize,
338 merge_tag: RcStr,
339 entries: Vec<ResolvedVc<Box<dyn Module>>>,
340 },
341 Shared(ResolvedVc<Box<dyn Module>>),
344 SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
346 SharedMerged {
349 parent: usize,
350 merge_tag: RcStr,
351 entries: Vec<ResolvedVc<Box<dyn Module>>>,
352 },
353 Collected(ResolvedVc<Box<dyn Module>>),
355}
356
357impl ChunkGroup {
358 pub fn get_merged_parent(&self) -> Option<usize> {
361 match self {
362 ChunkGroup::IsolatedMerged { parent, .. } | ChunkGroup::SharedMerged { parent, .. } => {
363 Some(*parent)
364 }
365 _ => None,
366 }
367 }
368
369 pub fn entries(&self) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + Clone + '_ {
372 match self {
373 ChunkGroup::Async(e)
374 | ChunkGroup::Isolated(e)
375 | ChunkGroup::Shared(e)
376 | ChunkGroup::Collected(e) => Either::Left(std::iter::once(*e)),
377 ChunkGroup::Entry(entries)
378 | ChunkGroup::IsolatedMerged { entries, .. }
379 | ChunkGroup::SharedMultiple(entries)
380 | ChunkGroup::SharedMerged { entries, .. } => Either::Right(entries.iter().copied()),
381 }
382 }
383
384 pub fn key(&self) -> ChunkGroupKey {
391 match self {
392 ChunkGroup::Entry(entries) => ChunkGroupKey::Entry(entries.clone()),
393 ChunkGroup::Async(module) => ChunkGroupKey::Async(*module),
394 ChunkGroup::Isolated(module) => ChunkGroupKey::Isolated(*module),
395 ChunkGroup::IsolatedMerged {
396 parent, merge_tag, ..
397 } => ChunkGroupKey::IsolatedMerged {
398 parent: ChunkGroupId::from(*parent),
399 merge_tag: merge_tag.clone(),
400 },
401 ChunkGroup::Shared(module) => ChunkGroupKey::Shared(*module),
402 ChunkGroup::SharedMultiple(entries) => ChunkGroupKey::SharedMultiple(entries.clone()),
403 ChunkGroup::SharedMerged {
404 parent, merge_tag, ..
405 } => ChunkGroupKey::SharedMerged {
406 parent: ChunkGroupId::from(*parent),
407 merge_tag: merge_tag.clone(),
408 },
409 ChunkGroup::Collected(module) => ChunkGroupKey::Collected(*module),
410 }
411 }
412
413 pub fn entries_count(&self) -> usize {
414 match self {
415 ChunkGroup::Async(_)
416 | ChunkGroup::Isolated(_)
417 | ChunkGroup::Shared(_)
418 | ChunkGroup::Collected(_) => 1,
419 ChunkGroup::Entry(entries)
420 | ChunkGroup::IsolatedMerged { entries, .. }
421 | ChunkGroup::SharedMultiple(entries)
422 | ChunkGroup::SharedMerged { entries, .. } => entries.len(),
423 }
424 }
425
426 pub async fn debug_str(&self, chunk_group_info: &ChunkGroupInfo) -> Result<String> {
427 Ok(match self {
428 ChunkGroup::Entry(entries) => format!(
429 "ChunkGroup::Entry({:?})",
430 entries
431 .iter()
432 .map(|m| m.ident().to_string())
433 .try_join()
434 .await?
435 ),
436 ChunkGroup::Async(entry) => turbofmt!("ChunkGroup::Async({:?})", entry.ident())
437 .await?
438 .to_string(),
439 ChunkGroup::Collected(entry) => turbofmt!("ChunkGroup::Collected({:?})", entry.ident())
440 .await?
441 .to_string(),
442 ChunkGroup::Isolated(entry) => turbofmt!("ChunkGroup::Isolated({:?})", entry.ident())
443 .await?
444 .to_string(),
445 ChunkGroup::Shared(entry) => turbofmt!("ChunkGroup::Shared({:?})", entry.ident())
446 .await?
447 .to_string(),
448 ChunkGroup::SharedMultiple(entries) => format!(
449 "ChunkGroup::SharedMultiple({:?})",
450 entries
451 .iter()
452 .map(|m| m.ident().to_string())
453 .try_join()
454 .await?
455 ),
456 ChunkGroup::IsolatedMerged {
457 parent,
458 merge_tag,
459 entries,
460 } => {
461 format!(
462 "ChunkGroup::IsolatedMerged({}, {}, {:?})",
463 Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
464 .await?,
465 merge_tag,
466 entries
467 .iter()
468 .map(|m| m.ident().to_string())
469 .try_join()
470 .await?
471 )
472 }
473 ChunkGroup::SharedMerged {
474 parent,
475 merge_tag,
476 entries,
477 } => {
478 format!(
479 "ChunkGroup::SharedMerged({}, {}, {:?})",
480 Box::pin(chunk_group_info.chunk_groups[*parent].debug_str(chunk_group_info))
481 .await?,
482 merge_tag,
483 entries
484 .iter()
485 .map(|m| m.ident().to_string())
486 .try_join()
487 .await?
488 )
489 }
490 })
491 }
492}
493
494#[turbo_tasks::task_input]
496#[derive(Debug, Clone, Hash, PartialEq, Eq, Encode, Decode)]
497pub enum ChunkGroupKey {
498 Entry(Vec<ResolvedVc<Box<dyn Module>>>),
499 Async(ResolvedVc<Box<dyn Module>>),
500 Isolated(ResolvedVc<Box<dyn Module>>),
501 IsolatedMerged {
502 parent: ChunkGroupId,
503 merge_tag: RcStr,
504 },
505 Shared(ResolvedVc<Box<dyn Module>>),
506 SharedMultiple(Vec<ResolvedVc<Box<dyn Module>>>),
507 SharedMerged {
508 parent: ChunkGroupId,
509 merge_tag: RcStr,
510 },
511 Collected(ResolvedVc<Box<dyn Module>>),
513}
514
515impl ChunkGroupKey {
516 pub async fn ident_str(
528 &self,
529 keys: &(impl std::ops::Index<usize, Output = Self> + ?Sized),
530 ) -> Result<String> {
531 Ok(match self {
532 ChunkGroupKey::Entry(entries) => format!(
533 "Entry({:?})",
534 entries
535 .iter()
536 .map(|m| m.ident().to_string())
537 .try_join()
538 .await?
539 ),
540 ChunkGroupKey::Async(module) => {
541 turbofmt!("Async({:?})", module.ident()).await?.to_string()
542 }
543 ChunkGroupKey::Collected(module) => turbofmt!("Collected({:?})", module.ident())
544 .await?
545 .to_string(),
546 ChunkGroupKey::Isolated(module) => turbofmt!("Isolated({:?})", module.ident())
547 .await?
548 .to_string(),
549 ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
550 format!(
551 "IsolatedMerged {{ parent: {}, merge_tag: {:?} }}",
552 Box::pin(keys.index(parent.0 as usize).ident_str(keys)).await?,
553 merge_tag
554 )
555 }
556 ChunkGroupKey::Shared(module) => {
557 turbofmt!("Shared({:?})", module.ident()).await?.to_string()
558 }
559 ChunkGroupKey::SharedMultiple(entries) => format!(
560 "SharedMultiple({:?})",
561 entries
562 .iter()
563 .map(|m| m.ident().to_string())
564 .try_join()
565 .await?
566 ),
567 ChunkGroupKey::SharedMerged { parent, merge_tag } => {
568 format!(
569 "SharedMerged {{ parent: {}, merge_tag: {:?} }}",
570 Box::pin(keys.index(parent.0 as usize).ident_str(keys)).await?,
571 merge_tag
572 )
573 }
574 })
575 }
576
577 pub async fn debug_str(
583 &self,
584 keys: &(impl std::ops::Index<usize, Output = Self> + ?Sized),
585 ) -> Result<String> {
586 self.ident_str(keys).await
587 }
588}
589
590#[turbo_tasks::task_input]
591#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Encode, Decode)]
592pub struct ChunkGroupId(u32);
593
594impl From<usize> for ChunkGroupId {
595 fn from(id: usize) -> Self {
596 Self(id as u32)
597 }
598}
599
600impl Deref for ChunkGroupId {
601 type Target = u32;
602 fn deref(&self) -> &Self::Target {
603 &self.0
604 }
605}
606
607pub async fn compute_chunk_group_info(graph: &ModuleGraph) -> Result<Vc<ChunkGroupInfo>> {
608 let span_outer = tracing::info_span!(
609 "compute chunk group info",
610 module_count = tracing::field::Empty,
611 visit_count = tracing::field::Empty,
612 chunk_group_count = tracing::field::Empty
613 );
614
615 let span = span_outer.clone();
616 async move {
617 let mut chunk_groups_map: FxIndexMap<
618 ChunkGroupKey,
619 FxIndexSet<ResolvedVc<Box<dyn Module>>>,
620 > = FxIndexMap::default();
621
622 let mut module_chunk_groups: FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper> =
625 FxHashMap::default();
626 let mut async_loader_chunk_groups: FxHashMap<
627 ResolvedVc<Box<dyn Module>>,
628 RoaringBitmapWrapper,
629 > = FxHashMap::default();
630
631 let module_count = graph
632 .graphs
633 .iter()
634 .map(|g| g.graph.node_count())
635 .sum::<usize>();
636 span.record("module_count", module_count);
637
638 let entries = graph.all_chunk_group_entries().collect::<Vec<_>>();
640
641 let module_rank =
644 graph.reverse_postorder_ranks(entries.iter().flat_map(|e| e.entries()))?;
645 module_chunk_groups.reserve(module_rank.len());
646 for module in module_rank.keys() {
647 module_chunk_groups.insert(*module, RoaringBitmapWrapper::default());
648 }
649
650 fn entry_to_chunk_group_id(
653 entry: ChunkGroupEntry,
654 chunk_groups_map: &mut FxIndexMap<
655 ChunkGroupKey,
656 FxIndexSet<ResolvedVc<Box<dyn Module>>>,
657 >,
658 ) -> ChunkGroupKey {
659 match entry {
660 ChunkGroupEntry::Entry { modules, .. } => ChunkGroupKey::Entry(modules),
661 ChunkGroupEntry::Async(entry) => ChunkGroupKey::Async(entry),
662 ChunkGroupEntry::Isolated(entry) => ChunkGroupKey::Isolated(entry),
663 ChunkGroupEntry::Shared(entry) => ChunkGroupKey::Shared(entry),
664 ChunkGroupEntry::SharedMultiple(entries) => ChunkGroupKey::SharedMultiple(entries),
665 ChunkGroupEntry::IsolatedMerged {
666 parent,
667 merge_tag,
668 entries: _,
669 } => {
670 let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
671 let parent_entry = chunk_groups_map.entry(parent);
672 let parent_id = parent_entry.index();
673 parent_entry.or_default();
674
675 ChunkGroupKey::IsolatedMerged {
676 parent: ChunkGroupId::from(parent_id),
677 merge_tag,
678 }
679 }
680 ChunkGroupEntry::SharedMerged {
681 parent,
682 merge_tag,
683 entries: _,
684 } => {
685 let parent = entry_to_chunk_group_id(*parent, chunk_groups_map);
686 let parent_entry = chunk_groups_map.entry(parent);
687 let parent_id = parent_entry.index();
688 parent_entry.or_default();
689
690 ChunkGroupKey::SharedMerged {
691 parent: ChunkGroupId::from(parent_id),
692 merge_tag,
693 }
694 }
695 }
696 }
697
698 let entry_chunk_group_keys = entries
699 .iter()
700 .flat_map(|&chunk_group| {
701 let chunk_group_key =
702 entry_to_chunk_group_id(chunk_group.clone(), &mut chunk_groups_map);
703 chunk_group
704 .entries()
705 .map(move |e| (e, chunk_group_key.clone()))
706 })
707 .collect::<FxHashMap<_, _>>();
708
709 let mut inherits_from: FxHashMap<u32, RoaringBitmap> = FxHashMap::default();
711
712 let visit_count = graph.traverse_edges_fixed_point_with_priority(
713 entries
714 .iter()
715 .flat_map(|e| e.entries())
716 .map(|e| {
717 Ok((
718 e,
719 Reverse(*module_rank.get(&e).context("Module rank not found")?),
720 ))
721 })
722 .collect::<Result<Vec<_>>>()?,
723 &mut module_chunk_groups,
724 |parent_info: Option<(ResolvedVc<Box<dyn Module>>, &'_ RefData, _)>,
725 node: ResolvedVc<Box<dyn Module>>,
726 _,
727 module_chunk_groups: &mut FxHashMap<
728 ResolvedVc<Box<dyn Module>>,
729 RoaringBitmapWrapper,
730 >|
731 -> Result<GraphTraversalAction> {
732 enum ChunkGroupInheritance<It: Iterator<Item = ChunkGroupKey>> {
733 Inherit(ResolvedVc<Box<dyn Module>>),
734 ChunkGroup(It),
735 }
736 let chunk_groups = if let Some((parent, ref_data, _)) = parent_info {
737 match &ref_data.chunking_type {
738 ChunkingType::Parallel { .. } => ChunkGroupInheritance::Inherit(parent),
739 ChunkingType::Async => {
740 let parent_groups = module_chunk_groups
744 .get(&parent)
745 .context("Module chunk group not found")?;
746 **async_loader_chunk_groups.entry(node).or_default() |=
747 &**parent_groups;
748 ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
749 ChunkGroupKey::Async(node),
750 )))
751 }
752 ChunkingType::Isolated {
753 merge_tag: None, ..
754 } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
755 ChunkGroupKey::Isolated(node),
756 ))),
757 ChunkingType::Shared {
758 merge_tag: None, ..
759 } => ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
760 ChunkGroupKey::Shared(node),
761 ))),
762 ChunkingType::Isolated {
763 merge_tag: Some(merge_tag),
764 ..
765 } => {
766 let parents = module_chunk_groups
767 .get(&parent)
768 .context("Module chunk group not found")?;
769 let chunk_groups =
770 parents.iter().map(|parent| ChunkGroupKey::IsolatedMerged {
771 parent: ChunkGroupId(parent),
772 merge_tag: merge_tag.clone(),
773 });
774 ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Left(
775 chunk_groups,
776 )))
777 }
778 ChunkingType::Shared {
779 merge_tag: Some(merge_tag),
780 ..
781 } => {
782 let parents = module_chunk_groups
783 .get(&parent)
784 .context("Module chunk group not found")?;
785 let chunk_groups =
786 parents.iter().map(|parent| ChunkGroupKey::SharedMerged {
787 parent: ChunkGroupId(parent),
788 merge_tag: merge_tag.clone(),
789 });
790 ChunkGroupInheritance::ChunkGroup(Either::Right(Either::Right(
791 chunk_groups,
792 )))
793 }
794 ChunkingType::Traced { .. } => {
795 return Ok(GraphTraversalAction::Skip);
797 }
798 ChunkingType::Emitted {
799 namespace: _,
800 emit_to_all_entries: _,
801 } => {
802 ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
805 ChunkGroupKey::Collected(node),
806 )))
807 }
808 ChunkingType::Collected { .. } => {
809 unreachable!();
811 }
812 ChunkingType::PerEntry => {
813 ChunkGroupInheritance::Inherit(parent)
819 }
820 }
821 } else {
822 ChunkGroupInheritance::ChunkGroup(Either::Left(std::iter::once(
823 entry_chunk_group_keys
825 .get(&node)
826 .context("Module chunk group not found")?
827 .clone(),
828 )))
829 };
830
831 Ok(match chunk_groups {
832 ChunkGroupInheritance::ChunkGroup(chunk_groups) => {
833 let chunk_group_ids = chunk_groups.map(|chunk_group| {
835 let merged_parent = match &chunk_group {
837 ChunkGroupKey::IsolatedMerged { parent, .. }
838 | ChunkGroupKey::SharedMerged { parent, .. } => Some(parent.0),
839 _ => None,
840 };
841 let id = match chunk_groups_map.entry(chunk_group) {
842 Entry::Occupied(mut e) => {
843 let id = e.index() as u32;
844 if merged_parent.is_some() {
845 e.get_mut().insert(node);
846 }
847 id
848 }
849 Entry::Vacant(e) => {
850 let id = e.index() as u32;
851 let mut set = FxIndexSet::default();
852 if merged_parent.is_some() {
853 set.insert(node);
854 }
855 e.insert(set);
856 id
857 }
858 };
859 if let Some(parent) = merged_parent {
863 inherits_from.entry(parent).or_default().insert(id);
864 } else if let Some((parent_module, _, _)) = parent_info
865 && let Some(parent_groups) = module_chunk_groups.get(&parent_module)
866 {
867 for source in parent_groups.iter() {
868 inherits_from.entry(source).or_default().insert(id);
869 }
870 }
871 id
872 });
873
874 let chunk_groups =
875 RoaringBitmapWrapper(RoaringBitmap::from_iter(chunk_group_ids));
876
877 let bitset = module_chunk_groups
879 .get_mut(&node)
880 .context("Module chunk group not found")?;
881 if chunk_groups.is_proper_superset(bitset) {
882 **bitset |= chunk_groups.into_inner();
884
885 GraphTraversalAction::Continue
886 } else {
887 GraphTraversalAction::Skip
889 }
890 }
891 ChunkGroupInheritance::Inherit(parent) => {
892 if parent == node {
896 GraphTraversalAction::Skip
898 } else {
899 let [Some(parent_chunk_groups), Some(current_chunk_groups)] =
900 module_chunk_groups.get_disjoint_mut([&parent, &node])
901 else {
902 bail!("Module chunk groups not found");
906 };
907
908 if current_chunk_groups.is_empty() {
909 *current_chunk_groups = parent_chunk_groups.clone();
911 GraphTraversalAction::Continue
912 } else if parent_chunk_groups.is_proper_superset(current_chunk_groups) {
913 **current_chunk_groups |= &**parent_chunk_groups;
915 GraphTraversalAction::Continue
916 } else {
917 GraphTraversalAction::Skip
919 }
920 }
921 }
922 })
923 },
924 |successor, _| {
929 Ok(Reverse(
930 *module_rank
931 .get(&successor)
932 .context("Module rank not found")?,
933 ))
934 },
935 )?;
936
937 span.record("visit_count", visit_count);
938 span.record("chunk_group_count", chunk_groups_map.len());
939
940 static PRINT_CHUNK_GROUP_INFO: LazyLock<bool> =
941 LazyLock::new(|| match std::env::var_os("TURBOPACK_PRINT_CHUNK_GROUPS") {
942 Some(v) => v == "1",
943 None => false,
944 });
945 if *PRINT_CHUNK_GROUP_INFO {
946 use std::{
947 collections::{BTreeMap, BTreeSet},
948 path::absolute,
949 };
950
951 let mut buckets = BTreeMap::default();
952 for (module, key) in &module_chunk_groups {
953 if !key.is_empty() {
954 buckets
955 .entry(key.iter().collect::<Vec<_>>())
956 .or_insert(BTreeSet::new())
957 .insert(module.ident().to_string().await?);
958 }
959 }
960
961 let mut result = vec![];
962 result.push("Chunk Groups:".to_string());
963 for (i, (key, _)) in chunk_groups_map.iter().enumerate() {
964 result.push(format!(
965 " {:?}: {}",
966 i,
967 key.debug_str(&chunk_groups_map.keys()).await?
968 ));
969 }
970 result.push("# Module buckets:".to_string());
971 for (key, modules) in buckets.iter() {
972 result.push(format!("## {:?}:", key.iter().collect::<Vec<_>>()));
973 for module in modules {
974 result.push(format!(" {module}"));
975 }
976 result.push("".to_string());
977 }
978 let f = absolute(format!("chunk_group_info_{}.log", visit_count))?;
979 println!("Wrote Chunk Group Info to {}", f.display());
980 std::fs::write(f, result.join("\n"))?;
981 }
982
983 let mut clusters: Vec<RoaringBitmap> = vec![RoaringBitmap::new(); chunk_groups_map.len()];
987 let mut priority_routes = RoaringBitmap::new();
988
989 let mut worklist: Vec<usize> = Vec::new();
990
991 for chunk_group in &entries {
992 let ChunkGroupEntry::Entry {
993 modules,
994 heuristics,
995 } = chunk_group
996 else {
997 continue;
998 };
999 if heuristics.clusters.is_empty() && !heuristics.high_priority {
1000 continue;
1001 }
1002 if let Some(index) =
1003 chunk_groups_map.get_index_of(&ChunkGroupKey::Entry(modules.clone()))
1004 {
1005 if clusters[index].is_empty() && !priority_routes.contains(index as u32) {
1006 worklist.push(index);
1007 }
1008 clusters[index].extend(heuristics.clusters.iter().map(|&c| c as u32));
1009 if heuristics.high_priority {
1010 priority_routes.insert(index as u32);
1011 }
1012 }
1013 }
1014
1015 while let Some(source) = worklist.pop() {
1016 let source_priority_route = priority_routes.contains(source as u32);
1017 let Some(targets) = inherits_from.get(&(source as u32)) else {
1018 continue;
1019 };
1020 for target in targets.iter() {
1021 let target = target as usize;
1022 if target == source {
1023 continue;
1024 }
1025 let [source_clusters, target_clusters] =
1026 clusters.get_disjoint_mut([source, target]).unwrap();
1027 let previous_target_clusters_len = target_clusters.len();
1028 *target_clusters |= &*source_clusters;
1029 let changed = (source_priority_route && priority_routes.insert(target as u32))
1030 || previous_target_clusters_len != target_clusters.len();
1031 if changed {
1032 worklist.push(target);
1033 }
1034 }
1035 }
1036
1037 let chunk_group_clusters: Vec<Vec<u16>> = clusters
1038 .into_iter()
1039 .map(|bm| bm.iter().map(|id| id as u16).collect())
1040 .collect();
1041 let chunk_group_priority_routes = RoaringBitmapWrapper(priority_routes);
1042
1043 Ok(ChunkGroupInfo {
1044 module_chunk_groups: ResolvedVc::cell(module_chunk_groups),
1045 async_loader_chunk_groups: ResolvedVc::cell(async_loader_chunk_groups),
1046 chunk_group_keys: chunk_groups_map.keys().cloned().collect(),
1047 chunk_group_indices: ResolvedVc::cell(
1048 chunk_groups_map
1049 .keys()
1050 .enumerate()
1051 .map(|(index, key)| (key.clone(), index as u32))
1052 .collect(),
1053 ),
1054 chunking_heuristics: ChunkingHeuristicsInfo {
1055 clusters: chunk_group_clusters,
1056 priority_routes: chunk_group_priority_routes,
1057 },
1058 chunk_groups: chunk_groups_map
1059 .into_iter()
1060 .map(|(k, merged_entries)| match k {
1061 ChunkGroupKey::Entry(entries) => ChunkGroup::Entry(entries),
1062 ChunkGroupKey::Async(module) => ChunkGroup::Async(module),
1063 ChunkGroupKey::Collected(module) => ChunkGroup::Collected(module),
1064 ChunkGroupKey::Isolated(module) => ChunkGroup::Isolated(module),
1065 ChunkGroupKey::IsolatedMerged { parent, merge_tag } => {
1066 ChunkGroup::IsolatedMerged {
1067 parent: parent.0 as usize,
1068 merge_tag,
1069 entries: merged_entries.into_iter().collect(),
1070 }
1071 }
1072 ChunkGroupKey::Shared(module) => ChunkGroup::Shared(module),
1073 ChunkGroupKey::SharedMultiple(entries) => ChunkGroup::SharedMultiple(entries),
1074 ChunkGroupKey::SharedMerged { parent, merge_tag } => ChunkGroup::SharedMerged {
1075 parent: parent.0 as usize,
1076 merge_tag,
1077 entries: merged_entries.into_iter().collect(),
1078 },
1079 })
1080 .collect(),
1081 }
1082 .cell())
1083 }
1084 .instrument(span_outer)
1085 .await
1086}