| 1 | use std::path::{Path, PathBuf}; |
| 2 | |
| 3 | use serde::{Deserialize, Serialize}; |
| 4 | |
| 5 | /// A conservative resource claim calculated before a tool may execute. |
| 6 | /// |
| 7 | /// The prepared-call seam records these claims before authority checks and the |
| 8 | /// product scheduler uses them to keep parallel batches non-conflicting. |
| 9 | #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] |
| 10 | #[serde(rename_all = "snake_case")] |
| 11 | pub enum ResourceClaim { |
| 12 | ReadPath(PathBuf), |
| 13 | WritePath(PathBuf), |
| 14 | ReadTree(PathBuf), |
| 15 | WriteTree(PathBuf), |
| 16 | Terminal(String), |
| 17 | GlobalExclusive, |
| 18 | } |
| 19 | |
| 20 | impl ResourceClaim { |
| 21 | #[must_use] |
| 22 | pub fn conflicts_with(&self, other: &Self) -> bool { |
| 23 | use ResourceClaim::{GlobalExclusive, ReadPath, ReadTree, Terminal, WritePath, WriteTree}; |
| 24 | |
| 25 | match (self, other) { |
| 26 | (GlobalExclusive, _) | (_, GlobalExclusive) => true, |
| 27 | (Terminal(left), Terminal(right)) => left == right, |
| 28 | (ReadPath(_), ReadPath(_)) => false, |
| 29 | (ReadPath(left), WritePath(right)) | (WritePath(right), ReadPath(left)) => { |
| 30 | left == right |
| 31 | } |
| 32 | (WritePath(left), WritePath(right)) => left == right, |
| 33 | (ReadTree(_), ReadTree(_)) => false, |
| 34 | (ReadTree(_), ReadPath(_)) | (ReadPath(_), ReadTree(_)) => false, |
| 35 | (ReadTree(tree), WritePath(path)) | (WritePath(path), ReadTree(tree)) => { |
| 36 | path.starts_with(tree) |
| 37 | } |
| 38 | (WriteTree(tree), ReadPath(path)) | (ReadPath(path), WriteTree(tree)) => { |
| 39 | path.starts_with(tree) |
| 40 | } |
| 41 | (WriteTree(tree), WritePath(path)) | (WritePath(path), WriteTree(tree)) => { |
| 42 | path.starts_with(tree) |
| 43 | } |
| 44 | (ReadTree(left), WriteTree(right)) | (WriteTree(right), ReadTree(left)) => { |
| 45 | trees_overlap(left, right) |
| 46 | } |
| 47 | (WriteTree(left), WriteTree(right)) => trees_overlap(left, right), |
| 48 | _ => false, |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | fn trees_overlap(left: &Path, right: &Path) -> bool { |
| 54 | left.starts_with(right) || right.starts_with(left) |
| 55 | } |
| 56 | |
| 57 | /// Build deterministic parallel batches. Items with no conflicting resource |
| 58 | /// claims share a batch; conflicting items retain their original order. |
| 59 | #[must_use] |
| 60 | pub fn schedule_non_conflicting<T>(items: Vec<(T, Vec<ResourceClaim>)>) -> Vec<Vec<T>> { |
| 61 | let mut batches = Vec::new(); |
| 62 | let mut batch = Vec::new(); |
| 63 | let mut batch_claims = Vec::new(); |
| 64 | |
| 65 | for (item, claims) in items { |
| 66 | let global_barrier = !batch.is_empty() |
| 67 | && (claims.contains(&ResourceClaim::GlobalExclusive) |
| 68 | || batch_claims.contains(&ResourceClaim::GlobalExclusive)); |
| 69 | let conflicts = global_barrier |
| 70 | || claims.iter().any(|claim| { |
| 71 | batch_claims |
| 72 | .iter() |
| 73 | .any(|existing| claim.conflicts_with(existing)) |
| 74 | }); |
| 75 | if conflicts && !batch.is_empty() { |
| 76 | batches.push(std::mem::take(&mut batch)); |
| 77 | batch_claims.clear(); |
| 78 | } |
| 79 | |
| 80 | batch.push(item); |
| 81 | batch_claims.extend(claims); |
| 82 | } |
| 83 | |
| 84 | if !batch.is_empty() { |
| 85 | batches.push(batch); |
| 86 | } |
| 87 | |
| 88 | batches |
| 89 | } |
| 90 | |
| 91 | #[cfg(test)] |
| 92 | mod tests { |
| 93 | use super::*; |
| 94 | |
| 95 | #[test] |
| 96 | fn two_reads_share_a_batch_but_write_is_ordered() { |
| 97 | let path = PathBuf::from("src/lib.rs"); |
| 98 | let batches = schedule_non_conflicting(vec![ |
| 99 | ("read-a", vec![ResourceClaim::ReadPath(path.clone())]), |
| 100 | ("read-b", vec![ResourceClaim::ReadPath(path.clone())]), |
| 101 | ("write", vec![ResourceClaim::WritePath(path)]), |
| 102 | ]); |
| 103 | assert_eq!(batches, vec![vec!["read-a", "read-b"], vec!["write"]]); |
| 104 | } |
| 105 | |
| 106 | #[test] |
| 107 | fn unrelated_writes_can_run_together() { |
| 108 | let batches = schedule_non_conflicting(vec![ |
| 109 | ("a", vec![ResourceClaim::WritePath(PathBuf::from("a.rs"))]), |
| 110 | ("b", vec![ResourceClaim::WritePath(PathBuf::from("b.rs"))]), |
| 111 | ]); |
| 112 | assert_eq!(batches, vec![vec!["a", "b"]]); |
| 113 | } |
| 114 | |
| 115 | #[test] |
| 116 | fn intervening_conflict_preserves_contiguous_order() { |
| 117 | let path = PathBuf::from("src/lib.rs"); |
| 118 | let batches = schedule_non_conflicting(vec![ |
| 119 | ("read-before", vec![ResourceClaim::ReadPath(path.clone())]), |
| 120 | ("write", vec![ResourceClaim::WritePath(path.clone())]), |
| 121 | ("read-after", vec![ResourceClaim::ReadPath(path)]), |
| 122 | ]); |
| 123 | assert_eq!( |
| 124 | batches, |
| 125 | vec![vec!["read-before"], vec!["write"], vec!["read-after"]] |
| 126 | ); |
| 127 | } |
| 128 | |
| 129 | #[test] |
| 130 | fn tree_claims_conflict_only_when_a_write_scope_overlaps() { |
| 131 | let src = PathBuf::from("workspace/src"); |
| 132 | let nested = PathBuf::from("workspace/src/nested"); |
| 133 | let source_file = PathBuf::from("workspace/src/lib.rs"); |
| 134 | let test_file = PathBuf::from("workspace/tests/test.rs"); |
| 135 | |
| 136 | assert!( |
| 137 | !ResourceClaim::ReadTree(src.clone()) |
| 138 | .conflicts_with(&ResourceClaim::ReadPath(source_file.clone())) |
| 139 | ); |
| 140 | assert!( |
| 141 | ResourceClaim::ReadTree(src.clone()) |
| 142 | .conflicts_with(&ResourceClaim::WritePath(source_file.clone())) |
| 143 | ); |
| 144 | assert!( |
| 145 | !ResourceClaim::ReadTree(src.clone()) |
| 146 | .conflicts_with(&ResourceClaim::WritePath(test_file)) |
| 147 | ); |
| 148 | assert!( |
| 149 | ResourceClaim::WriteTree(src.clone()) |
| 150 | .conflicts_with(&ResourceClaim::ReadPath(source_file)) |
| 151 | ); |
| 152 | assert!(ResourceClaim::WriteTree(src).conflicts_with(&ResourceClaim::ReadTree(nested))); |
| 153 | } |
| 154 | |
| 155 | #[test] |
| 156 | fn global_exclusive_stays_a_singleton_barrier() { |
| 157 | let batches = schedule_non_conflicting(vec![ |
| 158 | ("before", Vec::new()), |
| 159 | ("global", vec![ResourceClaim::GlobalExclusive]), |
| 160 | ("after", Vec::new()), |
| 161 | ]); |
| 162 | assert_eq!(batches, vec![vec!["before"], vec!["global"], vec!["after"]]); |
| 163 | } |
| 164 | |
| 165 | #[test] |
| 166 | fn global_exclusive_conflicts_with_every_claim() { |
| 167 | for claim in [ |
| 168 | ResourceClaim::ReadPath(PathBuf::from("src/lib.rs")), |
| 169 | ResourceClaim::Terminal("shell-1".to_string()), |
| 170 | ResourceClaim::GlobalExclusive, |
| 171 | ] { |
| 172 | assert!(ResourceClaim::GlobalExclusive.conflicts_with(&claim)); |
| 173 | assert!(claim.conflicts_with(&ResourceClaim::GlobalExclusive)); |
| 174 | } |
| 175 | } |
| 176 | } |
| 177 |