1use std::{
2 collections::{VecDeque, hash_map::Entry},
3 hash::BuildHasherDefault,
4 mem::take,
5};
6
7use anyhow::{Context, Result, bail};
8use bincode::{Decode, Encode};
9use either::Either;
10use itertools::Itertools;
11use petgraph::graph::{DiGraph, EdgeIndex, NodeIndex};
12use rustc_hash::{FxHashMap, FxHashSet, FxHasher};
13use serde::{Deserialize, Serialize};
14use tracing::Instrument;
15use turbo_prehash::BuildHasherExt;
16use turbo_tasks::{
17 FxIndexMap, FxIndexSet, JoinIterExt, NonLocalValue, ResolvedVc, TryJoinIterExt, ValueToString,
18 Vc, turbobail,
19};
20
21use crate::{
22 chunk::{ChunkableModule, ChunkingType},
23 module::Module,
24 module_graph::{
25 GraphTraversalAction, ModuleGraph,
26 chunk_group_info::{ChunkGroupInfo, ChunkGroupKey, RoaringBitmapWrapper},
27 module_batch::{ChunkableModuleOrBatch, ModuleBatch, ModuleBatchGroup, ModuleOrBatch},
28 traced_di_graph::{TracedDiGraph, iter_neighbors_rev},
29 },
30};
31#[turbo_tasks::value(task_input)]
32#[derive(Debug, Clone, Default, Hash)]
33pub struct BatchingConfig {
34 pub use_heuristic: bool,
37}
38
39#[turbo_tasks::value_impl]
40impl BatchingConfig {
41 #[turbo_tasks::function]
42 pub fn new(config: BatchingConfig) -> Vc<Self> {
43 config.cell()
44 }
45}
46
47#[derive(Debug, Clone, Serialize, Deserialize, NonLocalValue)]
48pub struct ModuleBatchesGraphEdge {
49 pub ty: ChunkingType,
50 pub module: Option<ResolvedVc<Box<dyn Module>>>,
51 pub active_for_page_entry: Option<ResolvedVc<Box<dyn Module>>>,
53}
54
55#[derive(Debug, Clone, NonLocalValue, Encode, Decode)]
56struct EntriesList(
57 #[bincode(with = "turbo_bincode::indexset")] pub FxIndexSet<ResolvedVc<Box<dyn Module>>>,
58);
59
60#[turbo_tasks::value(cell = "new", eq = "manual")]
61pub struct ModuleBatchesGraph {
62 graph: TracedDiGraph<ModuleOrBatch, ModuleBatchesGraphEdge>,
63
64 #[turbo_tasks(unsafe_ignore)]
71 #[bincode(with_serde)]
72 entries: FxHashMap<ResolvedVc<Box<dyn Module>>, NodeIndex>,
73 batch_groups: FxHashMap<ModuleOrBatch, ResolvedVc<ModuleBatchGroup>>,
74 batch_first_modules: FxHashMap<ResolvedVc<ModuleBatch>, ResolvedVc<Box<dyn Module>>>,
76
77 ordered_entries: Vec<Option<EntriesList>>,
82}
83
84impl ModuleBatchesGraph {
85 pub async fn get_entry_index(&self, entry: ResolvedVc<Box<dyn Module>>) -> Result<NodeIndex> {
86 let Some(entry) = self.entries.get(&entry) else {
87 if cfg!(debug_assertions) {
88 let possible_entries = format!(
89 "{:#?}",
90 self.entries
91 .keys()
92 .map(|e| e.ident().to_string())
93 .try_join()
94 .await?
95 );
96 turbobail!(
97 "Entry {} is not in graph (possible entries: {})",
98 entry.ident(),
99 possible_entries
100 );
101 } else {
102 bail!("Entry is not in graph");
103 }
104 };
105 Ok(*entry)
106 }
107
108 pub fn get_ordered_entries<'l>(
109 &'l self,
110 chunk_group_info: &'l ChunkGroupInfo,
111 idx: usize,
112 ) -> impl Iterator<Item = ResolvedVc<Box<dyn Module>>> + 'l {
113 if let Some(EntriesList(ordered_entries)) = self
114 .ordered_entries
115 .get(idx)
116 .as_ref()
117 .and_then(|o| o.as_ref())
118 {
119 if let Some(chunk_group) = chunk_group_info.chunk_groups.get_index(idx) {
120 debug_assert_eq!(ordered_entries.len(), chunk_group.entries_count());
121 }
122 Either::Left(Either::Left(ordered_entries.iter().copied()))
123 } else if let Some(chunk_group) = chunk_group_info.chunk_groups.get_index(idx) {
124 Either::Right(chunk_group.entries())
125 } else {
126 Either::Left(Either::Right(std::iter::empty()))
127 }
128 }
129
130 pub fn get_batch_group(
131 &self,
132 module_or_batch: &ModuleOrBatch,
133 ) -> Option<ResolvedVc<ModuleBatchGroup>> {
134 self.batch_groups.get(module_or_batch).copied()
135 }
136
137 pub async fn get_entry(&self, entry: ResolvedVc<Box<dyn Module>>) -> Result<ModuleOrBatch> {
138 let entry = self.get_entry_index(entry).await?;
139 Ok(*self.graph.node_weight(entry).unwrap())
140 }
141
142 pub(crate) fn get_first_module(
143 &self,
144 item: ChunkableModuleOrBatch,
145 ) -> Option<ResolvedVc<Box<dyn Module>>> {
146 match item {
147 ChunkableModuleOrBatch::Module(module) => Some(ResolvedVc::upcast(module)),
148 ChunkableModuleOrBatch::Batch(batch) => self.batch_first_modules.get(&batch).copied(),
149 ChunkableModuleOrBatch::None(_) => None,
150 }
151 }
152
153 #[allow(clippy::implied_bounds_in_impls)]
155 pub fn traverse_edges_from_entries_dfs<'a, S>(
173 &'a self,
174 entries: impl IntoIterator<
175 Item = NodeIndex,
176 IntoIter = impl Iterator<Item = NodeIndex> + DoubleEndedIterator,
177 >,
178 active_page_entries: Option<&FxHashSet<ResolvedVc<Box<dyn Module>>>>,
179 state: &mut S,
180 mut visit_preorder: impl FnMut(
181 Option<(&'a ModuleOrBatch, &'a ModuleBatchesGraphEdge)>,
182 &'a ModuleOrBatch,
183 &mut S,
184 ) -> Result<GraphTraversalAction>,
185 mut visit_postorder: impl FnMut(
186 Option<(&'a ModuleOrBatch, &'a ModuleBatchesGraphEdge)>,
187 &'a ModuleOrBatch,
188 &mut S,
189 ),
190 ) -> Result<()> {
191 let graph = &self.graph;
192
193 enum ReverseDFSPass {
194 Visit,
195 ExpandAndVisit,
196 }
197
198 let entries = entries.into_iter();
199 #[allow(clippy::type_complexity)] let mut stack: Vec<(ReverseDFSPass, Option<(NodeIndex, EdgeIndex)>, NodeIndex)> = entries
201 .rev()
202 .map(|e| (ReverseDFSPass::ExpandAndVisit, None, e))
203 .collect();
204 let mut expanded = FxHashSet::default();
205 while let Some((pass, parent, current)) = stack.pop() {
206 let parent_arg = parent.map(|(node, edge)| {
207 (
208 graph.node_weight(node).unwrap(),
209 graph.edge_weight(edge).unwrap(),
210 )
211 });
212 match pass {
213 ReverseDFSPass::Visit => {
214 let current_node = graph.node_weight(current).unwrap();
215 visit_postorder(parent_arg, current_node, state);
216 }
217 ReverseDFSPass::ExpandAndVisit => {
218 let current_node = graph.node_weight(current).unwrap();
219 let action = visit_preorder(parent_arg, current_node, state)?;
220 if action == GraphTraversalAction::Exclude {
221 continue;
222 }
223 stack.push((ReverseDFSPass::Visit, parent, current));
224 if action == GraphTraversalAction::Continue && expanded.insert(current) {
225 stack.extend(
226 iter_neighbors_rev(graph, current)
227 .filter(|&(edge_idx, _)| {
228 let edge = graph.edge_weight(edge_idx).unwrap();
229 match &edge.active_for_page_entry {
230 None => true,
231 Some(entry) => active_page_entries
232 .is_some_and(|entries| entries.contains(entry)),
233 }
234 })
235 .map(|(edge, child)| {
236 (ReverseDFSPass::ExpandAndVisit, Some((current, edge)), child)
237 }),
238 );
239 }
240 }
241 }
242 }
243
244 Ok(())
245 }
246}
247
248type PreBatchIndex = usize;
249
250#[derive(Hash, PartialEq, Eq, Clone, Debug)]
251enum PreBatchItem {
252 ParallelModule(ResolvedVc<Box<dyn Module>>),
253 ParallelReference(PreBatchIndex),
254 NonParallelEdge(ChunkingType, ResolvedVc<Box<dyn Module>>),
255}
256
257struct PreBatch {
258 items: FxIndexSet<PreBatchItem>,
259 chunk_groups: RoaringBitmapWrapper,
260}
261
262impl PreBatch {
263 fn new(chunk_groups: RoaringBitmapWrapper) -> Self {
264 Self {
265 items: FxIndexSet::default(),
266 chunk_groups,
267 }
268 }
269}
270
271struct TraversalState<'l> {
272 items: Vec<PreBatchItem>,
273 this: &'l mut PreBatches,
274}
275
276struct PreBatches {
277 boundary_modules: FxHashSet<ResolvedVc<Box<dyn Module>>>,
278 batches: Vec<PreBatch>,
279 entries: FxHashMap<ResolvedVc<Box<dyn Module>>, PreBatchIndex>,
280 single_module_entries: FxIndexSet<ResolvedVc<Box<dyn Module>>>,
281}
282
283impl PreBatches {
284 fn new() -> Self {
285 Self {
286 boundary_modules: FxHashSet::default(),
287 batches: Vec::new(),
288 entries: FxHashMap::default(),
289 single_module_entries: FxIndexSet::default(),
290 }
291 }
292
293 fn ensure_pre_batch_for_module(
294 &mut self,
295 module: ResolvedVc<Box<dyn Module>>,
296 module_chunk_groups: &FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper>,
297 queue: &mut VecDeque<(ResolvedVc<Box<dyn Module>>, PreBatchIndex)>,
298 ) -> Result<PreBatchIndex> {
299 Ok(match self.entries.entry(module) {
300 Entry::Vacant(e) => {
301 let index = self.batches.len();
302 queue.push_back((module, index));
303 let chunk_groups = module_chunk_groups
304 .get(&module)
305 .context("all modules need to have chunk group info")?;
306 let batch = PreBatch::new((*chunk_groups).clone());
307 self.batches.push(batch);
308 e.insert(index);
309 index
310 }
311 Entry::Occupied(e) => *e.get(),
312 })
313 }
314
315 async fn get_pre_batch_items(
316 &mut self,
317 entry: ResolvedVc<Box<dyn Module>>,
318 module_chunk_groups: &FxHashMap<ResolvedVc<Box<dyn Module>>, RoaringBitmapWrapper>,
319 module_graph: &ModuleGraph,
320 queue: &mut VecDeque<(ResolvedVc<Box<dyn Module>>, PreBatchIndex)>,
321 ) -> Result<Vec<PreBatchItem>> {
322 let mut state = TraversalState {
323 items: Vec::new(),
324 this: self,
325 };
326 let mut visited = FxHashSet::default();
327 module_graph.traverse_edges_dfs(
328 std::iter::once(entry),
329 &mut state,
330 |parent_info, node, state| {
331 let ty = parent_info.map_or(
332 &ChunkingType::Parallel {
333 inherit_async: false,
334 hoisted: false,
335 },
336 |(_, ty)| &ty.chunking_type,
337 );
338 let module = node;
339 if matches!(ty, ChunkingType::Emitted { .. }) {
340 return Ok(GraphTraversalAction::Exclude);
342 }
343 if !ty.is_parallel() {
344 state.items.push(PreBatchItem::NonParallelEdge(
345 ty.without_inherit_async(),
346 module,
347 ));
348 return Ok(GraphTraversalAction::Exclude);
349 }
350 if visited.insert(module) {
351 if parent_info.is_some() && state.this.boundary_modules.contains(&module) {
352 let idx = state.this.ensure_pre_batch_for_module(
353 module,
354 module_chunk_groups,
355 queue,
356 )?;
357 state.items.push(PreBatchItem::ParallelReference(idx));
358 return Ok(GraphTraversalAction::Exclude);
359 }
360 Ok(GraphTraversalAction::Continue)
361 } else {
362 Ok(GraphTraversalAction::Exclude)
363 }
364 },
365 |_, node, state| {
366 let item = PreBatchItem::ParallelModule(node);
367 state.items.push(item);
368 Ok(())
369 },
370 false,
371 false,
372 )?;
373 Ok(state.items)
374 }
375}
376
377pub async fn compute_module_batches(
378 module_graph: Vc<ModuleGraph>,
379 _config: &BatchingConfig,
380) -> Result<Vc<ModuleBatchesGraph>> {
381 let outer_span = tracing::info_span!(
382 "compute module batches",
383 initial_pre_batch_items = tracing::field::Empty,
384 initial_pre_batches = tracing::field::Empty,
385 extracted_shared_items = tracing::field::Empty,
386 batches = tracing::field::Empty,
387 modules = tracing::field::Empty,
388 edges = tracing::field::Empty
389 );
390 let span = outer_span.clone();
391 async move {
392 let chunk_group_info = module_graph.chunk_group_info().await?;
393 let module_chunk_groups = chunk_group_info.module_chunk_groups.await?;
394 let collected_modules = module_graph.collected_modules().await?;
395 let module_graph = module_graph.await?;
396
397 let mut pre_batches = PreBatches::new();
398
399 module_graph.traverse_edges_unordered(|parent, node| {
402 if let Some((parent, ty)) = parent {
403 let std::collections::hash_set::Entry::Vacant(entry) =
404 pre_batches.boundary_modules.entry(node)
405 else {
406 return Ok(());
408 };
409 if matches!(ty.chunking_type, ChunkingType::Emitted { .. }) {
410 return Ok(());
412 } else if ty.chunking_type.is_parallel() {
413 let parent_chunk_groups = module_chunk_groups
414 .get(&parent)
415 .context("all modules need to have chunk group info")?;
416 let chunk_groups = module_chunk_groups
417 .get(&node)
418 .context("all modules need to have chunk group info")?;
419 if parent_chunk_groups != chunk_groups {
420 entry.insert();
422 }
423 } else {
424 entry.insert();
425 }
426 }
427 Ok(())
428 })?;
429
430 for chunk_group in &chunk_group_info.chunk_groups {
432 pre_batches.boundary_modules.extend(chunk_group.entries());
433 }
434
435 pre_batches.boundary_modules.extend(
437 collected_modules
438 .values()
439 .flatten()
440 .flat_map(|(_, ms)| ms.iter().map(|(_, m)| *m)),
441 );
442
443 module_graph.traverse_cycles(
446 |ref_data| ref_data.chunking_type.is_parallel(),
447 |cycle| {
448 if cycle.len() > 1
449 && cycle
450 .iter()
451 .any(|node| pre_batches.boundary_modules.contains(node))
452 {
453 pre_batches
454 .boundary_modules
455 .extend(cycle.iter().map(|node| **node));
456 }
457 Ok(())
458 },
459 )?;
460
461 let mut queue: VecDeque<(ResolvedVc<Box<dyn Module>>, PreBatchIndex)> = VecDeque::new();
462
463 let mut chunk_group_indices_with_merged_children = FxHashSet::default();
464
465 for chunk_group in &chunk_group_info.chunk_groups {
467 for entry in chunk_group.entries() {
468 pre_batches.ensure_pre_batch_for_module(entry, &module_chunk_groups, &mut queue)?;
469 }
470 if let Some(parent) = chunk_group.get_merged_parent() {
471 chunk_group_indices_with_merged_children.insert(parent);
472 }
473 }
474 for entry in collected_modules
476 .values()
477 .flatten()
478 .flat_map(|(_, ms)| ms.iter().map(|(_, m)| *m))
479 {
480 pre_batches.ensure_pre_batch_for_module(entry, &module_chunk_groups, &mut queue)?;
481 }
482
483 let mut initial_pre_batch_items = 0;
484 while let Some((chunkable_module, idx)) = queue.pop_front() {
486 let items = pre_batches
487 .get_pre_batch_items(
488 chunkable_module,
489 &module_chunk_groups,
490 &module_graph,
491 &mut queue,
492 )
493 .await?;
494 initial_pre_batch_items += items.len();
495 let batch = &mut pre_batches.batches[idx];
496 batch.items.extend(items);
497 }
498 span.record("initial_pre_batch_items", initial_pre_batch_items);
499 span.record("initial_pre_batches", pre_batches.batches.len());
500
501 let mut ordered_entries: Vec<Option<EntriesList>> =
503 vec![None; chunk_group_info.chunk_groups.len()];
504 for (i, chunk_group) in chunk_group_info.chunk_groups.iter().enumerate() {
505 if !chunk_group_indices_with_merged_children.contains(&i) {
506 continue;
507 }
508 let mut merged_modules: FxHashMap<ChunkingType, FxIndexSet<_>> = FxHashMap::default();
509 let mut stack = ordered_entries[i]
510 .as_ref()
511 .map_or_else(
512 || Either::Left(chunk_group.entries()),
513 |v| Either::Right(v.0.iter().copied()),
514 )
515 .map(|module| {
516 let idx = *pre_batches
517 .entries
518 .get(&module)
519 .context("could not prebatch for module")?;
520 Ok((idx, 0))
521 })
522 .collect::<Result<Vec<_>>>()?;
523 stack.reverse();
524 let mut visited = FxHashSet::default();
525 while let Some((idx, mut pos)) = stack.pop() {
526 let batch = &pre_batches.batches[idx];
527 while let Some(item) = batch.items.get_index(pos) {
528 match item {
529 PreBatchItem::ParallelModule(_) => {}
530 PreBatchItem::ParallelReference(other_idx) => {
531 if visited.insert(*other_idx) {
532 stack.push((idx, pos + 1));
533 stack.push((*other_idx, 0));
534 break;
535 }
536 }
537 PreBatchItem::NonParallelEdge(chunking_type, module) => {
538 if chunking_type.is_merged() {
539 merged_modules
540 .entry(chunking_type.clone())
541 .or_default()
542 .insert(*module);
543 }
544 }
545 }
546 pos += 1;
547 }
548 }
549 if !merged_modules.is_empty() {
550 for (ty, merged_modules) in merged_modules {
551 let chunk_group_key = match ty {
552 ChunkingType::Isolated {
553 merge_tag: Some(merge_tag),
554 ..
555 } => ChunkGroupKey::IsolatedMerged {
556 parent: i.into(),
557 merge_tag: merge_tag.clone(),
558 },
559 ChunkingType::Shared {
560 merge_tag: Some(merge_tag),
561 ..
562 } => ChunkGroupKey::SharedMerged {
563 parent: i.into(),
564 merge_tag: merge_tag.clone(),
565 },
566 _ => unreachable!(),
567 };
568 let idx = chunk_group_info
569 .chunk_group_keys
570 .get_index_of(&chunk_group_key)
571 .context("could not find chunk group key for merged chunk group")?;
572 ordered_entries[idx] = Some(EntriesList(merged_modules));
573 }
574 }
575 }
576
577 let mut parallel_module_to_pre_batch: FxIndexMap<_, Vec<PreBatchIndex>> =
579 FxIndexMap::default();
580
581 let mut per_entry_modules: FxHashSet<ResolvedVc<Box<dyn Module>>> = FxHashSet::default();
588
589 for (idx, pre_batch) in pre_batches.batches.iter().enumerate() {
591 for item in &pre_batch.items {
592 match item {
593 PreBatchItem::ParallelModule(module) => {
594 parallel_module_to_pre_batch
595 .entry(*module)
596 .or_default()
597 .push(idx);
598 }
599 PreBatchItem::NonParallelEdge(ty, module) => {
600 if !pre_batches.entries.contains_key(module) {
601 pre_batches.single_module_entries.insert(*module);
602 }
603 if matches!(ty, ChunkingType::PerEntry) {
604 per_entry_modules.insert(*module);
605 }
606 }
607 PreBatchItem::ParallelReference(_) => {}
608 }
609 }
610 }
611
612 let mut extracted_shared_items = 0;
615 for i in 0..parallel_module_to_pre_batch.len() {
617 let (&module, batches) = parallel_module_to_pre_batch
618 .get_index(i)
619 .context("could not find parallel module to pre batch index")?;
620 if batches.len() > 1 {
621 let batches_with_item_index = batches
623 .iter()
624 .map(|&idx| {
625 let batch_items = &pre_batches.batches[idx].items;
626 let item_idx = batch_items
627 .get_index_of(&PreBatchItem::ParallelModule(module))
628 .context("could not find batch item index for parallel module")?;
629 Ok((idx, item_idx))
630 })
631 .collect::<Result<Vec<_>>>()?;
632 let mut selected_items = 1;
633 fn get_item_at(
634 pre_batches: &PreBatches,
635 batch_idx: PreBatchIndex,
636 item_idx: usize,
637 ) -> Option<&PreBatchItem> {
638 pre_batches.batches[batch_idx].items.get_index(item_idx)
639 }
640 loop {
643 if let Some(PreBatchItem::ParallelModule(next_module)) = get_item_at(
644 &pre_batches,
645 batches_with_item_index[0].0,
646 batches_with_item_index[0].1 + selected_items,
647 ) && parallel_module_to_pre_batch
648 .get(next_module)
649 .context("could not find pre batch for parallel module")?
650 .len()
651 == batches.len()
652 && batches_with_item_index[1..]
653 .iter()
654 .all(|&(batch_idx, item_idx)| {
655 get_item_at(&pre_batches, batch_idx, item_idx + selected_items)
656 == Some(&PreBatchItem::ParallelModule(*next_module))
657 })
658 {
659 selected_items += 1;
660 continue;
661 }
662 break;
663 }
664 extracted_shared_items += selected_items;
665
666 let exact_match = batches_with_item_index
669 .iter()
670 .find(|&&(batch_idx, item_idx)| {
671 item_idx == 0
672 && pre_batches.batches[batch_idx].items.len() == selected_items
673 });
674 if let Some(&(exact_match, _)) = exact_match {
675 for &(batch_index, item_start) in batches_with_item_index.iter() {
677 if batch_index != exact_match {
678 pre_batches.batches[batch_index].items.splice(
679 item_start..item_start + selected_items,
680 std::iter::once(PreBatchItem::ParallelReference(exact_match)),
681 );
682 }
683 }
684 for item in pre_batches.batches[exact_match].items.iter() {
685 if let PreBatchItem::ParallelModule(module) = item {
686 parallel_module_to_pre_batch
687 .get_mut(module)
688 .context("could not find pre batch for parallel module")?
689 .clear();
690 }
691 }
692 } else {
693 let first_batch_index = batches_with_item_index[0].0;
696 let first_batch_item_index = batches_with_item_index[0].1;
697 let new_batch_index = pre_batches.batches.len();
698 let mut new_batch =
699 PreBatch::new(pre_batches.batches[first_batch_index].chunk_groups.clone());
700 new_batch
701 .items
702 .extend(pre_batches.batches[first_batch_index].items.splice(
703 first_batch_item_index..first_batch_item_index + selected_items,
704 std::iter::once(PreBatchItem::ParallelReference(new_batch_index)),
705 ));
706 for item in new_batch.items.iter() {
707 if let PreBatchItem::ParallelModule(module) = item {
708 parallel_module_to_pre_batch
709 .get_mut(module)
710 .context("could not find pre batch for parallel module")?
711 .clear();
712 }
713 }
714 pre_batches.batches.push(new_batch);
715 for &(batch_index, item_start) in batches_with_item_index[1..].iter() {
716 pre_batches.batches[batch_index].items.splice(
717 item_start..item_start + selected_items,
718 std::iter::once(PreBatchItem::ParallelReference(new_batch_index)),
719 );
720 }
721 }
722 }
723 }
724 span.record("extracted_shared_items", extracted_shared_items);
725
726 let mut edges_count = 0;
729
730 for i in 0..pre_batches.batches.len() {
733 let items = take(&mut pre_batches.batches[i].items);
734 let mut new_items =
735 FxIndexSet::with_capacity_and_hasher(items.len(), Default::default());
736 enum Mode {
737 ParallelChunkableModule,
738 Other,
739 }
740 let mut mode = Mode::Other;
741 for item in items {
742 let chunkable_module = if let PreBatchItem::ParallelModule(module) = &item {
743 ResolvedVc::try_downcast::<Box<dyn ChunkableModule>>(*module)
744 } else {
745 None
746 };
747 let item = if let PreBatchItem::ParallelModule(module) = item {
748 if chunkable_module.is_some() {
749 PreBatchItem::ParallelModule(module)
750 } else {
751 pre_batches.single_module_entries.insert(module);
752 PreBatchItem::NonParallelEdge(
753 ChunkingType::Parallel {
754 inherit_async: false,
755 hoisted: false,
756 },
757 module,
758 )
759 }
760 } else {
761 item
762 };
763 match (&mode, chunkable_module) {
764 (_, Some(_)) => {
765 mode = Mode::ParallelChunkableModule;
766 new_items.insert(item);
767 }
768 (Mode::Other, _) => {
769 edges_count += 1;
770 new_items.insert(item);
771 }
772 (Mode::ParallelChunkableModule, _) => {
773 let idx = pre_batches.batches.len();
775 let mut new_batch =
776 PreBatch::new(pre_batches.batches[i].chunk_groups.clone());
777 new_batch.items.extend(new_items.drain(..));
778 pre_batches.batches.push(new_batch);
779 edges_count += 1;
780 new_items.insert(PreBatchItem::ParallelReference(idx));
781 if chunkable_module.is_some() {
782 new_items.insert(item);
783 } else {
784 edges_count += 1;
785 mode = Mode::Other;
786 new_items.insert(item);
787 }
788 }
789 }
790 }
791 pre_batches.batches[i].items = new_items;
792 }
793 span.record("pre_batches", pre_batches.batches.len());
794
795 let mut graph: DiGraph<ModuleOrBatch, ModuleBatchesGraphEdge, u32> =
799 petgraph::graph::DiGraph::with_capacity(
800 pre_batches.batches.len() + pre_batches.single_module_entries.len(),
801 edges_count,
802 );
803
804 let batches = pre_batches
806 .batches
807 .iter_mut()
808 .enumerate()
809 .map(async |(i, pre_batch)| {
810 let mut modules = pre_batch.items.iter().filter_map(|item| {
811 if let PreBatchItem::ParallelModule(module) = item {
812 ResolvedVc::try_downcast(*module)
813 } else {
814 None
815 }
816 });
817 let Some(first) = modules.next() else {
818 return Ok(ModuleOrBatch::None(i));
819 };
820 if let Some(second) = modules.next() {
821 let batch = ModuleBatch::new(
822 [first, second]
823 .into_iter()
824 .chain(modules)
825 .map(|m| *m)
826 .collect::<Vec<_>>(),
827 Some(pre_batch.chunk_groups.clone()),
828 );
829 Ok(ModuleOrBatch::Batch(batch.to_resolved().await?))
830 } else {
831 Ok(ModuleOrBatch::Module(ResolvedVc::upcast(first)))
832 }
833 })
834 .try_join()
835 .await?;
836
837 let batch_first_modules = pre_batches
838 .batches
839 .iter()
840 .zip(&batches)
841 .filter_map(|(pre_batch, item)| {
842 let ModuleOrBatch::Batch(batch) = item else {
843 return None;
844 };
845 pre_batch.items.iter().find_map(|item| match item {
846 PreBatchItem::ParallelModule(module)
847 if ResolvedVc::try_downcast::<Box<dyn ChunkableModule>>(*module)
848 .is_some() =>
849 {
850 Some((*batch, *module))
851 }
852 _ => None,
853 })
854 })
855 .collect();
856
857 let mut batch_groups: FxHashMap<_, Vec<_>> = FxHashMap::default();
859 for (i, pre_batch) in pre_batches.batches.iter().enumerate() {
860 let key = BuildHasherDefault::<FxHasher>::default().prehash(&pre_batch.chunk_groups);
861 let batch = batches[i];
862 batch_groups.entry(key).or_default().push(batch);
863 }
864 for &module in &pre_batches.single_module_entries {
865 if per_entry_modules.contains(&module) {
869 continue;
870 }
871 let chunk_groups = module_chunk_groups
872 .get(&module)
873 .context("all modules need to have chunk group info")?;
874 let key = BuildHasherDefault::<FxHasher>::default().prehash(chunk_groups);
875 batch_groups
876 .entry(key)
877 .or_default()
878 .push(ModuleOrBatch::Module(module));
879 }
880
881 let batch_groups = batch_groups
883 .into_iter()
884 .map(async |(key, items)| {
885 if items.len() == 1 {
886 anyhow::Ok(Either::Left(std::iter::empty()))
887 } else {
888 let batch_group = ModuleBatchGroup::new(items.clone(), (*key).clone())
889 .to_resolved()
890 .await?;
891 Ok(Either::Right(
892 items.into_iter().map(move |item| (item, batch_group)),
893 ))
894 }
895 })
896 .join()
897 .await
898 .into_iter()
899 .flatten_ok()
900 .collect::<Result<FxHashMap<_, _>>>()?;
901
902 let mut batches_count = 0;
904 let mut modules_count = 0;
905 let batch_indices = batches
906 .into_iter()
907 .map(|batch| {
908 match &batch {
909 ModuleOrBatch::Batch(_) => batches_count += 1,
910 ModuleOrBatch::Module(_) => modules_count += 1,
911 ModuleOrBatch::None(_) => {}
912 }
913 graph.add_node(batch)
914 })
915 .collect::<Vec<_>>();
916
917 let single_module_indices = pre_batches
919 .single_module_entries
920 .iter()
921 .map(|module| graph.add_node(ModuleOrBatch::Module(*module)))
922 .collect::<Vec<_>>();
923
924 span.record("batches", batches_count);
925 modules_count += pre_batches.single_module_entries.len();
926 span.record("modules", modules_count);
927 span.record("edges", edges_count);
928
929 let mut module_to_node: FxHashMap<ResolvedVc<Box<dyn Module>>, NodeIndex> =
931 FxHashMap::default();
932 for (module, batches) in ¶llel_module_to_pre_batch {
933 if let Some(&first_batch) = batches.first() {
936 module_to_node.insert(*module, batch_indices[first_batch]);
937 }
938 }
939 for (idx, module) in pre_batches.single_module_entries.iter().enumerate() {
940 module_to_node.insert(*module, single_module_indices[idx]);
941 }
942
943 for (i, pre_batch) in pre_batches.batches.into_iter().enumerate() {
945 let index = batch_indices[i];
946 let items = pre_batch.items;
947 for item in items {
948 match item {
949 PreBatchItem::ParallelReference(idx) => {
950 graph.add_edge(
951 index,
952 batch_indices[idx],
953 ModuleBatchesGraphEdge {
954 ty: ChunkingType::Parallel {
955 inherit_async: false,
956 hoisted: false,
957 },
958 module: None,
959 active_for_page_entry: None,
960 },
961 );
962 }
963 PreBatchItem::NonParallelEdge(ty, module) => {
964 if matches!(ty, ChunkingType::Emitted { .. }) {
965 continue;
967 }
968 if let Some(batch) = pre_batches.entries.get(&module).copied() {
969 graph.add_edge(
970 index,
971 batch_indices[batch],
972 ModuleBatchesGraphEdge {
973 ty,
974 module: Some(module),
975 active_for_page_entry: None,
976 },
977 );
978 continue;
979 }
980 let idx = pre_batches
981 .single_module_entries
982 .get_index_of(&module)
983 .context("could not find single module entry index")?;
984 let idx = single_module_indices[idx];
985 graph.add_edge(
986 index,
987 idx,
988 ModuleBatchesGraphEdge {
989 ty,
990 module: Some(module),
991 active_for_page_entry: None,
992 },
993 );
994 }
995 PreBatchItem::ParallelModule(_) => {}
996 }
997 }
998 }
999
1000 debug_assert_eq!(graph.capacity().0, graph.node_count());
1001 debug_assert_eq!(graph.capacity().1, graph.edge_count());
1002
1003 for (collecting_module, refs) in &collected_modules {
1005 for (entry_modules, refs) in refs {
1006 let source_node = *module_to_node
1007 .get(collecting_module)
1008 .context("could not find single module entry index")?;
1009 for (ref_data, target_module) in refs {
1010 if let Some(batch) = pre_batches.entries.get(target_module).copied() {
1011 for entry_module in entry_modules {
1012 graph.add_edge(
1013 source_node,
1014 batch_indices[batch],
1015 ModuleBatchesGraphEdge {
1016 ty: ref_data.chunking_type.clone(),
1017 module: Some(*target_module),
1018 active_for_page_entry: Some(*entry_module),
1019 },
1020 );
1021 }
1022 continue;
1023 }
1024 let idx = pre_batches
1025 .single_module_entries
1026 .get_index_of(target_module)
1027 .context("could not find single module entry index")?;
1028 let idx = single_module_indices[idx];
1029 for entry_module in entry_modules {
1030 graph.add_edge(
1031 source_node,
1032 idx,
1033 ModuleBatchesGraphEdge {
1034 ty: ref_data.chunking_type.clone(),
1035 module: Some(*target_module),
1036 active_for_page_entry: Some(*entry_module),
1037 },
1038 );
1039 }
1040 }
1041 }
1042 }
1043
1044 let mut entries = FxHashMap::default();
1046 for chunk_group in &chunk_group_info.chunk_groups {
1047 for module in chunk_group.entries() {
1048 if let Some(batch) = pre_batches.entries.get(&module).copied() {
1049 entries.insert(module, batch_indices[batch]);
1050 continue;
1051 }
1052 let idx = pre_batches
1053 .single_module_entries
1054 .get_index_of(&module)
1055 .context("could not find single module entry index")?;
1056 let idx = single_module_indices[idx];
1057 entries.insert(module, idx);
1058 }
1059 }
1060
1061 Ok(ModuleBatchesGraph {
1062 graph: TracedDiGraph(graph),
1063 entries,
1064 batch_groups,
1065 batch_first_modules,
1066 ordered_entries,
1067 }
1068 .cell())
1069 }
1070 .instrument(outer_span)
1071 .await
1072}