git clone https://github.com/devongovett/bundler-algorithm
cd bundler-algorithm
# 使用 nightly 版本的 cargo
rustup install nightly && rustup default nightly

# 運(yùn)行 demo
cargo run

// 創(chuàng)建 graph 并獲取對應(yīng)的 entries 對象
let (g, entries) = build_graph();

fn build_graph<'a>() -> (Graph<Asset<'a>, Dependency>, Vec<NodeIndex>) {
  let mut g = Graph::new();
  let mut entries = Vec::new();

  let html = g.add_node(Asset {
    name: "a.html",
    asset_type: AssetType::HTML,
    size: 10
  });
  
  let js = g.add_node(Asset {
    name: "a.js",
    asset_type: AssetType::JavaScript,
    size: 10
  });

  // ...一些資源的初始化過程，這里節(jié)省篇幅跳過...
  g.add_edge(html, js, Dependency {
    is_async: false
  });
  
  entries.push(html);
  entries.push(html2);

  return (g, entries);
}

let mut bundle_roots = HashMap:new();
let mut reacheable_bundles = HashSet::new();
let mut bundle_graph = Graph::new();

// 遍歷 entries，往 bundle_roots 中插入對應(yīng)的 entry 信息以及對應(yīng)的 bundle_id
for entry in &entries {
  let bundle_id = bundle_graph.add_node(Bundle::from_asset(*entry, &g[*entry]));
  bundle_roots.insert(*entry, (bundle_id, bundle_id));
}

let mut stack = LinkedList::new();

depth_first_search(&g, entries, |event| {
  match event {
    // ...
    DfsEvent::TreeEdge(u, v) => {
      let asset_a = &g[u];
      let asset_b = &g[v];
      // 當(dāng)資源類型發(fā)生變化的時候，創(chuàng)建一個新的 bundle
      if asset_a.asset_type != asset_b.asset_type {
        // 舉個例子，這里 a.js -> style.css
        // 這里 bundle_group_id 是 a.html，asset_b 是 style.css
        // style.css 是不同類型的資源被引用，會被拆單獨(dú)的 bundle 出來
        let (_, bundle_group_id) = stack.front().unwrap();
        let bundle_id = bundle_graph.add_node(Bundle::from_asset(v, asset_b));
        bundle_roots.insert(v, (bundle_id, *bundle_group_id));
        bundle_graph.add_edge(*bundle_group_id, bundle_id, 0);
        return
      }
      
      // 當(dāng)存在異步依賴的時候，創(chuàng)建一個新的 bundle
      let dependency = &g[g.find_edge(u, v).unwrap()];
      // 舉個例子，這里 a.js -> async.js 是異步依賴導(dǎo)入
      if dependency.is_async {
        // 因此這里 async.js(這里的 asset_b) 會被處理成一個單獨(dú)的 bundle
        let bundle_id = bundle_graph.add_node(Bundle::from_asset(v, asset_b));
        bundle_roots.insert(v, (bundle_id, bundle_id));
        for (b, _) in &stack {
            let a = &g[*b];
            if a.asset_type != asset_b.asset_type {
              break
            }
            reachable_bundles.insert((*b, v));
          }
      }
    }
    // ...
  }
});

let mut reachable_nodes = HashSet::new();
for (root, _) in &bundle_roots {
  depth_first_search(&g, Some(*root), |event| {
    if let DfsEvent::Discover(n, _) = &event {
      if n == root {
        return Control::Continue
      }

      // 如果命中了 bundle_root 就跳過
      if bundle_roots.contains_key(&n) {
        return Control::<()>::Prune;
      }
      // 否則就添加到可訪問節(jié)點(diǎn)中來
      reachable_nodes.insert((*root, *n));
    }
      Control::Continue
    });
}

// 根據(jù)拿到的可訪問的節(jié)點(diǎn)，構(gòu)造一個 graph 出來
let reachable_graph = Graph::<(), ()>::from_edges(&reachable_nodes);

// 用于存儲 entry asset id 到 bundle id 的映射
let mut bundles: HashMap<Vec<NodeIndex>, NodeIndex> = HashMap::new();

for asset_id in g.node_indices() {
  let reachable: Vec<NodeIndex> = reachable_graph.neighbors_directed(asset_id, Incoming).collect();
  let reachable: Vec<NodeIndex> = reachable.iter().cloned().filter(|b| {
      (&reachable).into_iter().all(|a| !reachable_bundles.contains(&(*a, *b)))
  }).collect();
  
  // 根據(jù)上面的每個 asset 對應(yīng)的可訪問的 bundle 去生成一個 bundle_graph
  if let Some((bundle_id, _)) = bundle_roots.get(&asset_id) {
    // 如果 asset 是個 bundle_root，那么會給這個 bundle_root 在 bundle_graph 添加上對應(yīng)的節(jié)點(diǎn)
    bundles.entry(vec![asset_id]).or_insert(*bundle_id);
    for a in &reachable {
      if *a != asset_id {
          bundle_graph.add_edge(bundle_roots[a].1, *bundle_id, 0);
       }
    }
  } else if reachable.len() > 0 {
    // 如果 asset 對于多個 bundle 都是可訪問的
    // 例如 shared.js(6) 就同時被 a.js(2) 和 b.js(5) 可訪問
    // 這里可以根據(jù)這些 asset 組合為該 asset 創(chuàng)建一個新的 bundle 
  }
}

for asset_id in g.node_indices() {
  let reachable: Vec<NodeIndex> = reachable_graph.neighbors_directed(asset_id, Incoming).collect();
  // 這一步篩掉 async2.js
  let reachable: Vec<NodeIndex> = reachable.iter().cloned().filter(|b| {
      (&reachable).into_iter().all(|a| !reachable_bundles.contains(&(*a, *b)))
  }).collect();
}

for asset_id in g.node_indices() {
   // ... 省略掉獲取 reacheable 這個變量過程
   if let Some((bundle_id, _)) = bundle_roots.get(&asset_id) {
     // 1. 處理 root_bundle，這一步可以理解為給 bundle_graph 添加邊
     bundles.entry(vec![asset_id]).or_insert(*bundle_id);
      for a in &reachable {
        if *a != asset_id {
          bundle_graph.add_edge(bundle_roots[a].1, *bundle_id, 0);
        }
      }
   } else if reachable.len() > 0 {
     // 2. 處理 root_bundle 之外的 asset 為 bundle
     let source_bundles = reachable.iter().map(|a| bundles[&vec![*a]]).collect();
      
      let bundle_id = bundles.entry(reachable.clone()).or_insert_with(|| {
        let mut bundle = Bundle::default();
        bundle.source_bundles = source_bundles;
        bundle_graph.add_node(bundle)
      });

      let bundle = &mut bundle_graph[*bundle_id];
      bundle.asset_ids.push(asset_id);
      bundle.size += g[asset_id].size;

      // 處理完 asset 為 bundle 之后，同樣要添加邊
      for a in reachable {
        if a != *bundle_id {
          bundle_graph.add_edge(bundle_roots[&a].1, *bundle_id, 0);
        }
      }
    }
   }
}

{
  "@parcel/bundler-default": {
    "minBundles": 1,
    "minBundleSize": 3000,
    "maxParallelRequests": 20
  }
}

for bundle_id in bundle_graph.node_indices() {
    let bundle = &bundle_graph[bundle_id];
    // 當(dāng)這個 bundle 本身為 commen bundle 且他本身的體積小于某個值，這里的 demo 默認(rèn)寫為了 10
    // 那么則可以合并掉這個 bundle
    if bundle.source_bundles.len() > 0 && bundle.size < 10 {
      remove_bundle(&g, &mut bundle_graph, bundle_id);
    }
  }
  
  fn remove_bundle(
    asset_graph: &Graph<Asset, Dependency>,
    bundle_graph: &mut Graph<Bundle, i32>,
    bundle_id: NodeIndex
  ) {
    // 在 bundle_graph 中刪除掉對應(yīng)的 bundle
    let bundle = bundle_graph.remove_node(bundle_id).unwrap();
    // 并將該 bundle 合并對其有引用關(guān)系的 bundle 中去
    for asset_id in &bundle.asset_ids {
      for source_bundle_id in &bundle.source_bundles {
        let bundle = &mut bundle_graph[*source_bundle_id];
        bundle.asset_ids.push(*asset_id);
        bundle.size += asset_graph[*asset_id].size;
    }
  }

{
  "@parcel/bundler-default": {
    "minBundles": 1,
    "minBundleSize": 3000,
    "maxParallelRequests": 20
  }
}

// demo 這里默認(rèn)的限制請求數(shù)量為 3
let limit = 3;
for (_, (bundle_id, bundle_group_id)) in bundle_roots {
    if bundle_id != bundle_group_id {
      continue;
    }
    let mut neighbors: Vec<NodeIndex> = bundle_graph.neighbors(bundle_group_id).collect();
    if neighbors.len() > limit {
      neighbors.sort_by(|a, b| bundle_graph[*a].size.cmp(&bundle_graph[*b].size));
      // Remove bundles until the bundle group is within the parallel request limit.
      for bundle_id in &neighbors[0..neighbors.len() - limit] {
        // Add all assets in the shared bundle into the source bundles that are within this bundle group.
        let source_bundles: Vec<NodeIndex> = bundle_graph[*bundle_id].source_bundles.drain_filter(|s| neighbors.contains(s)).collect();
        for source in source_bundles {
          for asset_id in bundle_graph[*bundle_id].asset_ids.clone() {
            let bundle_id = bundles[&vec![source]];
            let bundle = &mut bundle_graph[bundle_id];
            bundle.asset_ids.push(asset_id);
            bundle.size += g[asset_id].size;
          }
        }

        // Remove the edge from this bundle group to the shared bundle.
        bundle_graph.remove_edge(bundle_graph.find_edge(bundle_group_id, *bundle_id).unwrap());

        // If there is now only a single bundle group that contains this bundle,
        // merge it into the remaining source bundles. If it is orphaned entirely, remove it.
        let count = bundle_graph.neighbors_directed(*bundle_id, Incoming).count();
        if count == 1 {
          remove_bundle(&g, &mut bundle_graph, *bundle_id);
        } else if count == 0 {
          bundle_graph.remove_node(*bundle_id);
        }
      }
    }
  }