Skip to main content

turbopack_core/module_graph/
module_batches.rs

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    /// Use a heuristic based on the module path to create batches. It aims for batches of a good
35    /// size.
36    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    /// If set, this edge is only active when chunking for this page entry.
52    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    // NodeIndex isn't necessarily stable (because of swap_remove), but we never remove nodes.
65    //
66    // HashMaps have nondeterministic order, but this map is only used for lookups and not
67    // iteration.
68    //
69    // This contains Vcs, but they are already contained in the graph.
70    #[turbo_tasks(unsafe_ignore)]
71    #[bincode(with_serde)]
72    entries: FxHashMap<ResolvedVc<Box<dyn Module>>, NodeIndex>,
73    batch_groups: FxHashMap<ModuleOrBatch, ResolvedVc<ModuleBatchGroup>>,
74    /// The first module of each batch. All modules in a batch have the same chunk groups.
75    batch_first_modules: FxHashMap<ResolvedVc<ModuleBatch>, ResolvedVc<Box<dyn Module>>>,
76
77    /// For chunk groups where the postorder of entries is different than the order of the
78    /// `ChunkGroup::entries()` this contains Some with the postorder list of entries of that chunk
79    /// group. The index in this list corresponds to the index in the
80    /// chunk_group_info.chunk_groups.
81    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    // Clippy complains but there's a type error without the bound
154    #[allow(clippy::implied_bounds_in_impls)]
155    /// Traverses all reachable edges in dfs order. The preorder visitor can be used to
156    /// forward state down the graph, and to skip subgraphs
157    ///
158    /// Use this to collect batches/modules in evaluation order.
159    ///
160    /// Target nodes can be revisited (once per incoming edge).
161    /// Edges are traversed in normal order, so should correspond to reference order.
162    ///
163    /// * `entries` - The entry modules to start the traversal from
164    /// * `state` - The state to be passed to the visitors
165    /// * `visit_preorder` - Called before visiting the children of a node.
166    ///    - Receives: (originating &ModuleBatchesGraphNode, edge &ChunkingType), target
167    ///      &ModuleBatchesGraphNode, state &S
168    ///    - Can return [GraphTraversalAction]s to control the traversal
169    /// * `visit_postorder` - Called after visiting the children of a node. Return
170    ///    - Receives: (originating &ModuleBatchesGraphNode, edge &ChunkingType), target
171    ///      &ModuleBatchesGraphNode, state &S
172    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)] // This is a temporary internal structure
200        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                    // they are handled via module_graph.collected_modules now
341                    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        // Walk the module graph and mark all modules that are boundary modules (referenced from a
400        // different chunk group bitmap)
401        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                    // Already a boundary module, can skip check
407                    return Ok(());
408                };
409                if matches!(ty.chunking_type, ChunkingType::Emitted { .. }) {
410                    // they are handled via module_graph.collected_modules now
411                    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                        // This is a boundary module
421                        entry.insert();
422                    }
423                } else {
424                    entry.insert();
425                }
426            }
427            Ok(())
428        })?;
429
430        // All entries are boundary modules too
431        for chunk_group in &chunk_group_info.chunk_groups {
432            pre_batches.boundary_modules.extend(chunk_group.entries());
433        }
434
435        // All collected modules are boundary modules too
436        pre_batches.boundary_modules.extend(
437            collected_modules
438                .values()
439                .flatten()
440                .flat_map(|(_, ms)| ms.iter().map(|(_, m)| *m)),
441        );
442
443        // Pre batches would be incorrect with cycles, so we need to opt-out of pre batches for
444        // cycles that include boundary modules
445        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        // Start with the entries...
466        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        // ...and all collected modules
475        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        // Fill all pre batches
485        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        // Figure out the order of all merged groups
502        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        // Create a map of parallel module to the batches they are contained in.
578        let mut parallel_module_to_pre_batch: FxIndexMap<_, Vec<PreBatchIndex>> =
579            FxIndexMap::default();
580
581        // Modules that are only referenced via `ChunkingType::PerEntry` (i.e. collecting
582        // modules). They are chunked once per entry group via
583        // `ChunkGroupContentInner::collecting_modules`, so their chunk item depends on the entry
584        // group and can't be represented in an entry-independent, shared `ModuleBatchGroup`.
585        // They still need to be in `single_module_entries` because the graph edges below
586        // reference them by index.
587        let mut per_entry_modules: FxHashSet<ResolvedVc<Box<dyn Module>>> = FxHashSet::default();
588
589        // Fill the map and also fill up the single_module_entries
590        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        // We never want a module to occur in multiple batches.
613
614        let mut extracted_shared_items = 0;
615        // Extract shared modules into separate batches
616        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                // Create a new batch for the shared modules
622                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                // Select more matching items that are equal in all batches that contain the shared
641                // module(s)
642                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                // Check if a batch is completely selected. In that case we can replace all other
667                // occurrences with a reference to that batch
668                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                    // Replace all other occurrences with a reference to the exact match
676                    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                    // Create a new batch of the shared part and replace all occurrences with a
694                    // reference to that batch
695                    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        // Now every module is only in one batch
727
728        let mut edges_count = 0;
729
730        // Since batches can only have references followed by a list of parallel chunkable modules,
731        // we need to split batches that have modules before references.
732        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                        // Split the batch
774                        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        // Now batches are in the correct shape. We can create the real batches and the graph.
796
797        // Create the graph
798        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        // Create the Vc<ModuleBatch> instances
805        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        // Create the batch groups by grouping batches with the same chunk groups
858        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            // Modules referenced via `ChunkingType::PerEntry` are chunked per entry group and
866            // must not become part of a (shared, entry-independent) batch group. See
867            // `per_entry_modules` above.
868            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        // Create the batch group instances
882        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        // Insert batches into the graph and store the NodeIndices
903        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        // Also insert single modules into the graph and store the NodeIndices
918        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        // Build a module -> NodeIndex lookup for all modules in the graph
930        let mut module_to_node: FxHashMap<ResolvedVc<Box<dyn Module>>, NodeIndex> =
931            FxHashMap::default();
932        for (module, batches) in &parallel_module_to_pre_batch {
933            // The values in parallel_module_to_pre_batch are guaranteed to be empty or contain
934            // exactly one batch index.
935            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        // Add all the edges to the graph
944        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                            // they are handled via collected_modules now
966                            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        // Add collected reference edges (conditional on page entry)
1004        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        // Find the NodeIndices for our entries of the graph
1045        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}