omena_parser/closed_world/
authority.rs1use std::collections::{BTreeMap, BTreeSet, VecDeque};
4
5use super::contract::{
6 ClosedWorldBundleBuildErrorV0, ClosedWorldBundleV0, ClosedWorldInterfaceHashAvailabilityV0,
7 ClosedWorldInterfaceHashEntryV0, ClosedWorldInterfaceHashSetV0, ClosedWorldLinkedModuleV0,
8 ClosedWorldModuleMetadataV0, ClosedWorldReachabilityBitsetParityReportV0,
9 ClosedWorldSourcePrecisionSummaryV0, ModuleInstanceKeyV0, ModuleQualifiedSymbolSetV0,
10 ReachabilityIndexV0,
11};
12
13impl ClosedWorldBundleV0 {
14 pub fn try_from_linked_modules(
15 entrypoints: Vec<ModuleInstanceKeyV0>,
16 linked_modules: Vec<ClosedWorldLinkedModuleV0>,
17 ) -> Result<Self, ClosedWorldBundleBuildErrorV0> {
18 Self::try_from_linked_modules_with_metadata(entrypoints, linked_modules, Vec::new())
19 }
20
21 pub fn try_from_linked_modules_with_metadata(
22 entrypoints: Vec<ModuleInstanceKeyV0>,
23 linked_modules: Vec<ClosedWorldLinkedModuleV0>,
24 module_metadata: Vec<ClosedWorldModuleMetadataV0>,
25 ) -> Result<Self, ClosedWorldBundleBuildErrorV0> {
26 if entrypoints.is_empty() {
27 return Err(ClosedWorldBundleBuildErrorV0::EmptyEntrypoints);
28 }
29
30 let mut by_instance = BTreeMap::new();
31 for module in linked_modules {
32 by_instance.insert(module.instance.clone(), module);
33 }
34 let metadata_by_instance = module_metadata
35 .into_iter()
36 .map(|metadata| (metadata.module_instance().clone(), metadata))
37 .collect::<BTreeMap<_, _>>();
38
39 let reachability = compute_reachability(entrypoints.as_slice(), &by_instance)?;
40 let linked_modules = reachability.module_instances().to_vec();
41 let interface_hashes =
42 interface_hashes_for_reachable_modules(&linked_modules, &metadata_by_instance);
43 let source_precision =
44 source_precision_for_reachable_modules(&linked_modules, &metadata_by_instance);
45 let closure_hash = stable_closure_hash(entrypoints.as_slice(), &by_instance, &reachability);
46
47 Ok(Self::seal(
48 entrypoints,
49 linked_modules,
50 reachability,
51 closure_hash,
52 interface_hashes,
53 source_precision,
54 ))
55 }
56}
57
58fn interface_hashes_for_reachable_modules(
59 reachable: &[ModuleInstanceKeyV0],
60 metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
61) -> ClosedWorldInterfaceHashSetV0 {
62 ClosedWorldInterfaceHashSetV0::new(
63 reachable
64 .iter()
65 .map(|instance| ClosedWorldInterfaceHashEntryV0 {
66 module_instance: instance.clone(),
67 availability: metadata_by_instance
68 .get(instance)
69 .and_then(|metadata| metadata.interface_hash())
70 .map_or(
71 ClosedWorldInterfaceHashAvailabilityV0::Absent,
72 |interface_hash| ClosedWorldInterfaceHashAvailabilityV0::Known {
73 interface_hash: interface_hash.to_string(),
74 },
75 ),
76 })
77 .collect(),
78 )
79}
80
81fn source_precision_for_reachable_modules(
82 reachable: &[ModuleInstanceKeyV0],
83 metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
84) -> Option<ClosedWorldSourcePrecisionSummaryV0> {
85 let mut aggregate = ClosedWorldSourcePrecisionSummaryV0::default();
86 let mut observed = false;
87 for instance in reachable {
88 if let Some(source_precision) = metadata_by_instance
89 .get(instance)
90 .and_then(ClosedWorldModuleMetadataV0::source_precision)
91 {
92 aggregate.merge(source_precision);
93 observed = true;
94 }
95 }
96 observed.then_some(aggregate)
97}
98
99pub fn summarize_closed_world_reachability_bitset_parity_v0(
100 entrypoints: Vec<ModuleInstanceKeyV0>,
101 linked_modules: Vec<ClosedWorldLinkedModuleV0>,
102) -> Result<ClosedWorldReachabilityBitsetParityReportV0, ClosedWorldBundleBuildErrorV0> {
103 if entrypoints.is_empty() {
104 return Err(ClosedWorldBundleBuildErrorV0::EmptyEntrypoints);
105 }
106
107 let mut by_instance = BTreeMap::new();
108 for module in linked_modules {
109 by_instance.insert(module.instance.clone(), module);
110 }
111
112 let btreeset_reachability = compute_reachability(entrypoints.as_slice(), &by_instance)?;
113 let bitset_reachability = compute_reachability_bitset(entrypoints.as_slice(), &by_instance)?;
114 let btreeset_closure_hash =
115 stable_closure_hash(entrypoints.as_slice(), &by_instance, &btreeset_reachability);
116 let bitset_closure_hash =
117 stable_closure_hash(entrypoints.as_slice(), &by_instance, &bitset_reachability);
118 let symbol_name_count = bitset_reachability
119 .class_names()
120 .len()
121 .saturating_add(bitset_reachability.keyframe_names().len())
122 .saturating_add(bitset_reachability.value_names().len())
123 .saturating_add(bitset_reachability.custom_property_names().len());
124
125 Ok(ClosedWorldReachabilityBitsetParityReportV0 {
126 schema_version: "0",
127 product: "omena-parser.closed-world-reachability-bitset-parity",
128 module_instance_count: bitset_reachability.module_instances().len(),
129 symbol_name_count,
130 module_qualified_symbols: btreeset_reachability.module_qualified_symbols().to_vec(),
131 reachability_equal: btreeset_reachability == bitset_reachability,
132 closure_hash_equal: btreeset_closure_hash == bitset_closure_hash,
133 btreeset_closure_hash,
134 bitset_closure_hash,
135 })
136}
137
138fn compute_reachability(
139 entrypoints: &[ModuleInstanceKeyV0],
140 by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
141) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
142 let mut queue = VecDeque::new();
143 let mut seen = BTreeSet::new();
144 for entrypoint in entrypoints {
145 if !by_instance.contains_key(entrypoint) {
146 return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
147 module: entrypoint.clone(),
148 });
149 }
150 queue.push_back(entrypoint.clone());
151 }
152
153 while let Some(instance) = queue.pop_front() {
154 if !seen.insert(instance.clone()) {
155 continue;
156 }
157 let Some(module) = by_instance.get(&instance) else {
158 return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint { module: instance });
159 };
160 for dependency in &module.dependencies {
161 if !by_instance.contains_key(dependency) {
162 return Err(ClosedWorldBundleBuildErrorV0::MissingDependency {
163 module: instance.clone(),
164 dependency: dependency.clone(),
165 });
166 }
167 queue.push_back(dependency.clone());
168 }
169 }
170
171 reachability_index_from_seen(&seen, by_instance)
172}
173
174fn compute_reachability_bitset(
175 entrypoints: &[ModuleInstanceKeyV0],
176 by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
177) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
178 for entrypoint in entrypoints {
179 if !by_instance.contains_key(entrypoint) {
180 return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
181 module: entrypoint.clone(),
182 });
183 }
184 }
185 let dense_index = DenseModuleInstanceIndexV0::from_modules(entrypoints, by_instance);
186 let mut seen = DenseModuleInstanceBitsetV0::new(dense_index.len());
187 let mut queue = entrypoints
188 .iter()
189 .filter_map(|entrypoint| dense_index.index_of(entrypoint))
190 .collect::<VecDeque<_>>();
191
192 while let Some(instance_index) = queue.pop_front() {
193 if !seen.insert(instance_index) {
194 continue;
195 }
196 let instance = dense_index.instance(instance_index);
197 let Some(module) = by_instance.get(instance) else {
198 return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
199 module: instance.clone(),
200 });
201 };
202 for dependency in &module.dependencies {
203 if !by_instance.contains_key(dependency) {
204 return Err(ClosedWorldBundleBuildErrorV0::MissingDependency {
205 module: instance.clone(),
206 dependency: dependency.clone(),
207 });
208 }
209 if let Some(dependency_index) = dense_index.index_of(dependency) {
210 queue.push_back(dependency_index);
211 }
212 }
213 }
214
215 let seen_instances = dense_index.instances_for_bitset(&seen);
216 reachability_index_from_seen(&seen_instances, by_instance)
217}
218
219fn reachability_index_from_seen(
220 seen: &BTreeSet<ModuleInstanceKeyV0>,
221 by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
222) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
223 let mut class_names = BTreeSet::new();
224 let mut keyframe_names = BTreeSet::new();
225 let mut value_names = BTreeSet::new();
226 let mut custom_property_names = BTreeSet::new();
227 let mut module_qualified_symbols = Vec::with_capacity(by_instance.len());
228
229 for (instance, module) in by_instance {
230 let reachable = seen.contains(instance);
231 if reachable {
232 class_names.extend(module.class_names.iter().cloned());
233 keyframe_names.extend(module.keyframe_names.iter().cloned());
234 value_names.extend(module.value_names.iter().cloned());
235 custom_property_names.extend(module.custom_property_names.iter().cloned());
236 }
237 let qualified_class_names = if reachable {
238 dedupe_symbol_names(&module.class_names)
239 } else {
240 Vec::new()
241 };
242 let qualified_keyframe_names = if reachable {
243 dedupe_symbol_names(&module.keyframe_names)
244 } else {
245 Vec::new()
246 };
247 let qualified_value_names = if reachable {
248 dedupe_symbol_names(&module.value_names)
249 } else {
250 Vec::new()
251 };
252 let qualified_custom_property_names = if reachable {
253 dedupe_symbol_names(&module.custom_property_names)
254 } else {
255 Vec::new()
256 };
257 module_qualified_symbols.push(ModuleQualifiedSymbolSetV0::new(
258 instance.clone(),
259 reachable,
260 qualified_class_names,
261 qualified_keyframe_names,
262 qualified_value_names,
263 qualified_custom_property_names,
264 ));
265 }
266
267 Ok(ReachabilityIndexV0::from_parts(
268 seen.iter().cloned().collect(),
269 module_qualified_symbols,
270 class_names.into_iter().collect(),
271 keyframe_names.into_iter().collect(),
272 value_names.into_iter().collect(),
273 custom_property_names.into_iter().collect(),
274 ))
275}
276
277fn dedupe_symbol_names(names: &[String]) -> Vec<String> {
278 names
279 .iter()
280 .cloned()
281 .collect::<BTreeSet<_>>()
282 .into_iter()
283 .collect()
284}
285
286#[derive(Debug, Clone)]
287struct DenseModuleInstanceIndexV0 {
288 instances: Vec<ModuleInstanceKeyV0>,
289 positions: BTreeMap<ModuleInstanceKeyV0, usize>,
290}
291
292impl DenseModuleInstanceIndexV0 {
293 fn from_modules(
294 entrypoints: &[ModuleInstanceKeyV0],
295 by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
296 ) -> Self {
297 let mut instances = BTreeSet::new();
298 instances.extend(entrypoints.iter().cloned());
299 for (instance, module) in by_instance {
300 instances.insert(instance.clone());
301 instances.extend(module.dependencies.iter().cloned());
302 }
303 let instances = instances.into_iter().collect::<Vec<_>>();
304 let positions = instances
305 .iter()
306 .enumerate()
307 .map(|(index, instance)| (instance.clone(), index))
308 .collect::<BTreeMap<_, _>>();
309 Self {
310 instances,
311 positions,
312 }
313 }
314
315 fn len(&self) -> usize {
316 self.instances.len()
317 }
318
319 fn index_of(&self, instance: &ModuleInstanceKeyV0) -> Option<usize> {
320 self.positions.get(instance).copied()
321 }
322
323 fn instance(&self, index: usize) -> &ModuleInstanceKeyV0 {
324 &self.instances[index]
325 }
326
327 fn instances_for_bitset(
328 &self,
329 bitset: &DenseModuleInstanceBitsetV0,
330 ) -> BTreeSet<ModuleInstanceKeyV0> {
331 self.instances
332 .iter()
333 .enumerate()
334 .filter(|(index, _)| bitset.contains(*index))
335 .map(|(_, instance)| instance.clone())
336 .collect()
337 }
338}
339
340#[derive(Debug, Clone)]
341struct DenseModuleInstanceBitsetV0 {
342 words: Vec<u64>,
343}
344
345impl DenseModuleInstanceBitsetV0 {
346 fn new(len: usize) -> Self {
347 Self {
348 words: vec![0; len.div_ceil(64)],
349 }
350 }
351
352 fn insert(&mut self, index: usize) -> bool {
353 let word_index = index / 64;
354 let mask = 1u64 << (index % 64);
355 let word = &mut self.words[word_index];
356 let was_empty = *word & mask == 0;
357 *word |= mask;
358 was_empty
359 }
360
361 fn contains(&self, index: usize) -> bool {
362 self.words
363 .get(index / 64)
364 .is_some_and(|word| word & (1u64 << (index % 64)) != 0)
365 }
366}
367
368fn stable_closure_hash(
369 entrypoints: &[ModuleInstanceKeyV0],
370 by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
371 reachability: &ReachabilityIndexV0,
372) -> String {
373 let mut hash = StableFnv64::new();
374 hash.piece("omena-parser.closed-world-bundle");
375 for entrypoint in entrypoints {
376 hash.instance(entrypoint);
377 }
378 for instance in reachability.module_instances() {
379 hash.instance(instance);
380 if let Some(module) = by_instance.get(instance) {
381 for dependency in &module.dependencies {
382 hash.instance(dependency);
383 }
384 }
385 }
386 for name in reachability.class_names() {
387 hash.piece("class");
388 hash.piece(name);
389 }
390 for name in reachability.keyframe_names() {
391 hash.piece("keyframe");
392 hash.piece(name);
393 }
394 for name in reachability.value_names() {
395 hash.piece("value");
396 hash.piece(name);
397 }
398 for name in reachability.custom_property_names() {
399 hash.piece("custom-property");
400 hash.piece(name);
401 }
402 hash.finish_hex()
403}
404
405struct StableFnv64(u64);
406
407impl StableFnv64 {
408 fn new() -> Self {
409 Self(0xcbf2_9ce4_8422_2325)
410 }
411
412 fn piece(&mut self, value: &str) {
413 for byte in value.as_bytes().iter().copied().chain([0]) {
414 self.0 ^= u64::from(byte);
415 self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
416 }
417 }
418
419 fn instance(&mut self, instance: &ModuleInstanceKeyV0) {
420 self.piece(instance.module().as_str());
421 self.piece(instance.configuration().as_str());
422 }
423
424 fn finish_hex(self) -> String {
425 format!("{:016x}", self.0)
426 }
427}