omena_cross_file_summary/
lib.rs

1//! Cross-file summary hypergraph substrate shared by query and demand-sliced monotone fact propagation.
2
3use std::collections::{BTreeMap, BTreeSet, VecDeque};
4
5use omena_abstract_value::{LinearProvenanceV0, NaturalCountProvenanceSemiringV0};
6use serde::Serialize;
7
8pub type OmenaCrossFileLinearProvenanceV0 = LinearProvenanceV0<NaturalCountProvenanceSemiringV0>;
9
10#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
11#[serde(rename_all = "camelCase")]
12pub struct OmenaQueryCrossFileSummaryV0 {
13    pub schema_version: &'static str,
14    pub product: &'static str,
15    pub status: &'static str,
16    pub summary_scope: &'static str,
17    pub style_count: usize,
18    pub summary_edge_count: usize,
19    pub edge_kind_counts: Vec<OmenaQueryCrossFileSummaryEdgeKindCountV0>,
20    pub summary_hash: String,
21    pub edges: Vec<OmenaQueryCrossFileSummaryEdgeV0>,
22    pub capabilities: OmenaQueryCrossFileSummaryCapabilitiesV0,
23    pub next_priorities: Vec<&'static str>,
24}
25
26#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
27#[serde(rename_all = "camelCase")]
28pub struct OmenaQueryCrossFileSummaryEdgeKindCountV0 {
29    pub edge_kind: &'static str,
30    pub count: usize,
31}
32
33#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
34#[serde(rename_all = "camelCase")]
35pub struct OmenaCrossFileSummaryViewReportV0 {
36    pub schema_version: &'static str,
37    pub product: &'static str,
38    pub status: &'static str,
39    pub raw_edge_kind_catalog_count: usize,
40    pub node_role_catalog_count: usize,
41    pub summary_edge_count: usize,
42    pub existing_edge_kind_counts: Vec<OmenaQueryCrossFileSummaryEdgeKindCountV0>,
43    pub recomputed_edge_kind_counts: Vec<OmenaQueryCrossFileSummaryEdgeKindCountV0>,
44    pub invalid_raw_edge_kinds: Vec<String>,
45    pub invalid_node_roles: Vec<String>,
46    pub all_raw_edge_kinds_in_catalog: bool,
47    pub all_node_roles_in_catalog: bool,
48    pub edge_kind_counts_match_existing_field: bool,
49    pub summary_view_ready: bool,
50}
51
52#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
53#[serde(rename_all = "camelCase")]
54pub struct OmenaCrossFileGraphDeltaV0 {
55    pub schema_version: &'static str,
56    pub product: &'static str,
57    pub status: &'static str,
58    pub before_edge_count: usize,
59    pub after_edge_count: usize,
60    pub added_edges: Vec<OmenaCrossFileGraphDeltaEdgeV0>,
61    pub removed_edges: Vec<OmenaCrossFileGraphDeltaEdgeV0>,
62    pub invalid_delta_edge_ids: Vec<String>,
63    pub all_delta_edges_typed: bool,
64}
65
66#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
67#[serde(rename_all = "camelCase")]
68pub struct OmenaCrossFileGraphDeltaEdgeV0 {
69    pub edge_id: String,
70    pub raw_edge_kind: &'static str,
71    pub folded_edge_kind: UnifiedHypergraphEdgeKindV0,
72    pub folded_by_lossy_catch_all: bool,
73    pub from_role: OmenaCrossFileSummaryNodeRoleV0,
74    pub target_role: Option<OmenaCrossFileSummaryNodeRoleV0>,
75    pub from_path: String,
76    pub target_path: Option<String>,
77}
78
79#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
80#[serde(rename_all = "camelCase")]
81pub struct OmenaQueryCrossFileSummaryEdgeV0 {
82    pub edge_id: String,
83    pub edge_kind: &'static str,
84    pub from_kind: &'static str,
85    pub from_path: String,
86    pub target_kind: Option<&'static str>,
87    pub target_path: Option<String>,
88    pub source: Option<String>,
89    pub owner_selector_name: Option<String>,
90    pub local_name: Option<String>,
91    pub remote_name: Option<String>,
92    pub target_names: Vec<String>,
93    pub status: &'static str,
94    pub provenance: Vec<&'static str>,
95    pub linear_provenance: OmenaCrossFileLinearProvenanceV0,
96}
97
98#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
99#[serde(rename_all = "camelCase")]
100pub enum OmenaCrossFileSummaryNodeRoleV0 {
101    Source,
102    Style,
103}
104
105impl OmenaCrossFileSummaryNodeRoleV0 {
106    pub const fn as_wire_label(self) -> &'static str {
107        match self {
108            Self::Source => "source",
109            Self::Style => "style",
110        }
111    }
112}
113
114#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
115#[serde(rename_all = "camelCase")]
116pub enum OmenaCrossFileSummaryRawEdgeKindV0 {
117    ComposesExternal,
118    ComposesGlobal,
119    ComposesLocal,
120    CssModulesComposesClosure,
121    CssModulesComposesImport,
122    CssModulesIcssClosure,
123    CssModulesIcssImport,
124    CssModulesImport,
125    CssModulesValueClosure,
126    CssModulesValueImport,
127    ForeignReference,
128    Icss,
129    LessImport,
130    LessModuleGraphClosure,
131    SassForward,
132    SassImport,
133    SassModuleGraphClosure,
134    SassUse,
135    SourceSelectorPrefixReference,
136    SourceSelectorReference,
137    StyleDesignTokenReference,
138    Value,
139}
140
141impl OmenaCrossFileSummaryRawEdgeKindV0 {
142    pub const fn as_wire_label(self) -> &'static str {
143        match self {
144            Self::ComposesExternal => "composesExternal",
145            Self::ComposesGlobal => "composesGlobal",
146            Self::ComposesLocal => "composesLocal",
147            Self::CssModulesComposesClosure => "cssModulesComposesClosure",
148            Self::CssModulesComposesImport => "cssModulesComposesImport",
149            Self::CssModulesIcssClosure => "cssModulesIcssClosure",
150            Self::CssModulesIcssImport => "cssModulesIcssImport",
151            Self::CssModulesImport => "cssModulesImport",
152            Self::CssModulesValueClosure => "cssModulesValueClosure",
153            Self::CssModulesValueImport => "cssModulesValueImport",
154            Self::ForeignReference => "foreignReference",
155            Self::Icss => "icss",
156            Self::LessImport => "lessImport",
157            Self::LessModuleGraphClosure => "lessModuleGraphClosure",
158            Self::SassForward => "sassForward",
159            Self::SassImport => "sassImport",
160            Self::SassModuleGraphClosure => "sassModuleGraphClosure",
161            Self::SassUse => "sassUse",
162            Self::SourceSelectorPrefixReference => "sourceSelectorPrefixReference",
163            Self::SourceSelectorReference => "sourceSelectorReference",
164            Self::StyleDesignTokenReference => "styleDesignTokenReference",
165            Self::Value => "value",
166        }
167    }
168
169    pub const fn folded_edge_kind(self) -> UnifiedHypergraphEdgeKindV0 {
170        match self {
171            Self::ComposesLocal => UnifiedHypergraphEdgeKindV0::ComposesLocal,
172            Self::ComposesGlobal => UnifiedHypergraphEdgeKindV0::ComposesGlobal,
173            Self::CssModulesComposesImport
174            | Self::CssModulesComposesClosure
175            | Self::ComposesExternal => UnifiedHypergraphEdgeKindV0::ComposesExternal,
176            Self::SassUse => UnifiedHypergraphEdgeKindV0::SassUse,
177            Self::SassForward => UnifiedHypergraphEdgeKindV0::SassForward,
178            Self::SassImport => UnifiedHypergraphEdgeKindV0::SassImport,
179            Self::LessImport => UnifiedHypergraphEdgeKindV0::LessImport,
180            Self::LessModuleGraphClosure => UnifiedHypergraphEdgeKindV0::LessModuleGraphClosure,
181            Self::CssModulesValueImport | Self::CssModulesValueClosure | Self::Value => {
182                UnifiedHypergraphEdgeKindV0::Value
183            }
184            Self::CssModulesIcssImport | Self::CssModulesIcssClosure | Self::Icss => {
185                UnifiedHypergraphEdgeKindV0::Icss
186            }
187            Self::CssModulesImport
188            | Self::ForeignReference
189            | Self::SassModuleGraphClosure
190            | Self::SourceSelectorPrefixReference
191            | Self::SourceSelectorReference
192            | Self::StyleDesignTokenReference => UnifiedHypergraphEdgeKindV0::ForeignReference,
193        }
194    }
195
196    pub const fn folded_by_lossy_catch_all(self) -> bool {
197        matches!(
198            self,
199            Self::CssModulesImport
200                | Self::ForeignReference
201                | Self::SassModuleGraphClosure
202                | Self::SourceSelectorPrefixReference
203                | Self::SourceSelectorReference
204                | Self::StyleDesignTokenReference
205        )
206    }
207
208    pub const fn order_relevance(self) -> EdgeOrderRelevanceV0 {
209        match self {
210            Self::CssModulesImport => EdgeOrderRelevanceV0::OrderBearing,
211            Self::ForeignReference
212            | Self::SassModuleGraphClosure
213            | Self::SourceSelectorPrefixReference
214            | Self::SourceSelectorReference
215            | Self::StyleDesignTokenReference => EdgeOrderRelevanceV0::OrderNeutral,
216            _ => self.folded_edge_kind().order_relevance(),
217        }
218    }
219}
220
221pub const UNIFIED_HYPERGRAPH_EDGE_KIND_VARIANTS_V0: [UnifiedHypergraphEdgeKindV0; 11] = [
222    UnifiedHypergraphEdgeKindV0::ComposesLocal,
223    UnifiedHypergraphEdgeKindV0::ComposesGlobal,
224    UnifiedHypergraphEdgeKindV0::ComposesExternal,
225    UnifiedHypergraphEdgeKindV0::SassUse,
226    UnifiedHypergraphEdgeKindV0::SassForward,
227    UnifiedHypergraphEdgeKindV0::SassImport,
228    UnifiedHypergraphEdgeKindV0::LessImport,
229    UnifiedHypergraphEdgeKindV0::LessModuleGraphClosure,
230    UnifiedHypergraphEdgeKindV0::Value,
231    UnifiedHypergraphEdgeKindV0::Icss,
232    UnifiedHypergraphEdgeKindV0::ForeignReference,
233];
234
235pub const CROSS_FILE_SUMMARY_RAW_EDGE_KIND_VARIANTS_V0: [OmenaCrossFileSummaryRawEdgeKindV0; 22] = [
236    OmenaCrossFileSummaryRawEdgeKindV0::ComposesExternal,
237    OmenaCrossFileSummaryRawEdgeKindV0::ComposesGlobal,
238    OmenaCrossFileSummaryRawEdgeKindV0::ComposesLocal,
239    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesComposesClosure,
240    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesComposesImport,
241    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesIcssClosure,
242    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesIcssImport,
243    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesImport,
244    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesValueClosure,
245    OmenaCrossFileSummaryRawEdgeKindV0::CssModulesValueImport,
246    OmenaCrossFileSummaryRawEdgeKindV0::ForeignReference,
247    OmenaCrossFileSummaryRawEdgeKindV0::Icss,
248    OmenaCrossFileSummaryRawEdgeKindV0::LessImport,
249    OmenaCrossFileSummaryRawEdgeKindV0::LessModuleGraphClosure,
250    OmenaCrossFileSummaryRawEdgeKindV0::SassForward,
251    OmenaCrossFileSummaryRawEdgeKindV0::SassImport,
252    OmenaCrossFileSummaryRawEdgeKindV0::SassModuleGraphClosure,
253    OmenaCrossFileSummaryRawEdgeKindV0::SassUse,
254    OmenaCrossFileSummaryRawEdgeKindV0::SourceSelectorPrefixReference,
255    OmenaCrossFileSummaryRawEdgeKindV0::SourceSelectorReference,
256    OmenaCrossFileSummaryRawEdgeKindV0::StyleDesignTokenReference,
257    OmenaCrossFileSummaryRawEdgeKindV0::Value,
258];
259
260pub const CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0: [&str; 22] = [
261    "composesExternal",
262    "composesGlobal",
263    "composesLocal",
264    "cssModulesComposesClosure",
265    "cssModulesComposesImport",
266    "cssModulesIcssClosure",
267    "cssModulesIcssImport",
268    "cssModulesImport",
269    "cssModulesValueClosure",
270    "cssModulesValueImport",
271    "foreignReference",
272    "icss",
273    "lessImport",
274    "lessModuleGraphClosure",
275    "sassForward",
276    "sassImport",
277    "sassModuleGraphClosure",
278    "sassUse",
279    "sourceSelectorPrefixReference",
280    "sourceSelectorReference",
281    "styleDesignTokenReference",
282    "value",
283];
284
285pub const CROSS_FILE_SUMMARY_NODE_ROLE_LABELS_V0: [&str; 2] = ["source", "style"];
286
287pub fn parse_cross_file_summary_node_role_v0(
288    label: &str,
289) -> Option<OmenaCrossFileSummaryNodeRoleV0> {
290    match label {
291        "source" => Some(OmenaCrossFileSummaryNodeRoleV0::Source),
292        "style" => Some(OmenaCrossFileSummaryNodeRoleV0::Style),
293        _ => None,
294    }
295}
296
297pub fn parse_cross_file_summary_raw_edge_kind_v0(
298    label: &str,
299) -> Option<OmenaCrossFileSummaryRawEdgeKindV0> {
300    match label {
301        "composesExternal" => Some(OmenaCrossFileSummaryRawEdgeKindV0::ComposesExternal),
302        "composesGlobal" => Some(OmenaCrossFileSummaryRawEdgeKindV0::ComposesGlobal),
303        "composesLocal" => Some(OmenaCrossFileSummaryRawEdgeKindV0::ComposesLocal),
304        "cssModulesComposesClosure" => {
305            Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesComposesClosure)
306        }
307        "cssModulesComposesImport" => {
308            Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesComposesImport)
309        }
310        "cssModulesIcssClosure" => Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesIcssClosure),
311        "cssModulesIcssImport" => Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesIcssImport),
312        "cssModulesImport" => Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesImport),
313        "cssModulesValueClosure" => {
314            Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesValueClosure)
315        }
316        "cssModulesValueImport" => Some(OmenaCrossFileSummaryRawEdgeKindV0::CssModulesValueImport),
317        "foreignReference" => Some(OmenaCrossFileSummaryRawEdgeKindV0::ForeignReference),
318        "icss" => Some(OmenaCrossFileSummaryRawEdgeKindV0::Icss),
319        "lessImport" => Some(OmenaCrossFileSummaryRawEdgeKindV0::LessImport),
320        "lessModuleGraphClosure" => {
321            Some(OmenaCrossFileSummaryRawEdgeKindV0::LessModuleGraphClosure)
322        }
323        "sassForward" => Some(OmenaCrossFileSummaryRawEdgeKindV0::SassForward),
324        "sassImport" => Some(OmenaCrossFileSummaryRawEdgeKindV0::SassImport),
325        "sassModuleGraphClosure" => {
326            Some(OmenaCrossFileSummaryRawEdgeKindV0::SassModuleGraphClosure)
327        }
328        "sassUse" => Some(OmenaCrossFileSummaryRawEdgeKindV0::SassUse),
329        "sourceSelectorPrefixReference" => {
330            Some(OmenaCrossFileSummaryRawEdgeKindV0::SourceSelectorPrefixReference)
331        }
332        "sourceSelectorReference" => {
333            Some(OmenaCrossFileSummaryRawEdgeKindV0::SourceSelectorReference)
334        }
335        "styleDesignTokenReference" => {
336            Some(OmenaCrossFileSummaryRawEdgeKindV0::StyleDesignTokenReference)
337        }
338        "value" => Some(OmenaCrossFileSummaryRawEdgeKindV0::Value),
339        _ => None,
340    }
341}
342
343#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
344#[serde(rename_all = "camelCase")]
345pub struct OmenaQueryCrossFileSummaryCapabilitiesV0 {
346    pub css_modules_composes_edges_ready: bool,
347    pub css_modules_value_edges_ready: bool,
348    pub css_modules_icss_edges_ready: bool,
349    pub sass_module_edges_ready: bool,
350    pub style_design_token_reference_edges_ready: bool,
351    pub source_selector_reference_edges_ready: bool,
352    pub stable_summary_hash_ready: bool,
353    pub linear_provenance_ready: bool,
354    pub linear_provenance_round_trip_ready: bool,
355    pub linear_provenance_semiring_laws_hold: bool,
356}
357
358#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
359#[serde(rename_all = "camelCase")]
360pub struct ReverseDependencyIndexV0 {
361    pub rev: BTreeMap<String, BTreeSet<String>>,
362    pub edges_by_from: BTreeMap<String, BTreeSet<String>>,
363}
364
365impl OmenaQueryCrossFileSummaryEdgeV0 {
366    pub fn linear_provenance_round_trips_legacy_labels(&self) -> bool {
367        self.linear_provenance.labels() == self.provenance
368    }
369}
370
371impl OmenaQueryCrossFileSummaryV0 {
372    pub fn linear_provenance_round_trips_legacy_labels(&self) -> bool {
373        self.edges
374            .iter()
375            .all(OmenaQueryCrossFileSummaryEdgeV0::linear_provenance_round_trips_legacy_labels)
376    }
377
378    pub fn recompute_stable_summary_hash(&self) -> String {
379        stable_omena_query_cross_file_summary_hash(self.edges.as_slice())
380    }
381}
382
383pub fn summarize_cross_file_summary_view_v0(
384    summary: &OmenaQueryCrossFileSummaryV0,
385) -> OmenaCrossFileSummaryViewReportV0 {
386    let recomputed_edge_kind_counts =
387        recompute_cross_file_summary_raw_edge_kind_counts_v0(summary.edges.as_slice());
388    let invalid_raw_edge_kinds = invalid_raw_edge_kinds_for_summary(summary);
389    let invalid_node_roles = invalid_node_roles_for_summary(summary);
390    let edge_kind_counts_match_existing_field =
391        recomputed_edge_kind_counts == summary.edge_kind_counts;
392    let all_raw_edge_kinds_in_catalog = invalid_raw_edge_kinds.is_empty();
393    let all_node_roles_in_catalog = invalid_node_roles.is_empty();
394    let summary_view_ready = all_raw_edge_kinds_in_catalog
395        && all_node_roles_in_catalog
396        && edge_kind_counts_match_existing_field;
397
398    OmenaCrossFileSummaryViewReportV0 {
399        schema_version: "0",
400        product: "omena-cross-file-summary.summary-view",
401        status: if summary_view_ready {
402            "ready"
403        } else {
404            "needsInput"
405        },
406        raw_edge_kind_catalog_count: CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0.len(),
407        node_role_catalog_count: CROSS_FILE_SUMMARY_NODE_ROLE_LABELS_V0.len(),
408        summary_edge_count: summary.summary_edge_count,
409        existing_edge_kind_counts: summary.edge_kind_counts.clone(),
410        recomputed_edge_kind_counts,
411        invalid_raw_edge_kinds,
412        invalid_node_roles,
413        all_raw_edge_kinds_in_catalog,
414        all_node_roles_in_catalog,
415        edge_kind_counts_match_existing_field,
416        summary_view_ready,
417    }
418}
419
420pub fn recompute_cross_file_summary_raw_edge_kind_counts_v0(
421    edges: &[OmenaQueryCrossFileSummaryEdgeV0],
422) -> Vec<OmenaQueryCrossFileSummaryEdgeKindCountV0> {
423    let mut counts = BTreeMap::<&'static str, usize>::new();
424    for edge in edges {
425        *counts.entry(edge.edge_kind).or_default() += 1;
426    }
427    counts
428        .into_iter()
429        .map(|(edge_kind, count)| OmenaQueryCrossFileSummaryEdgeKindCountV0 { edge_kind, count })
430        .collect()
431}
432
433pub fn summarize_cross_file_graph_delta_v0(
434    before: &OmenaQueryCrossFileSummaryV0,
435    after: &OmenaQueryCrossFileSummaryV0,
436) -> OmenaCrossFileGraphDeltaV0 {
437    let before_edges = before
438        .edges
439        .iter()
440        .map(|edge| (edge.edge_id.as_str(), edge))
441        .collect::<BTreeMap<_, _>>();
442    let after_edges = after
443        .edges
444        .iter()
445        .map(|edge| (edge.edge_id.as_str(), edge))
446        .collect::<BTreeMap<_, _>>();
447
448    let mut invalid_delta_edge_ids = Vec::new();
449    let mut added_edges = Vec::new();
450    let mut removed_edges = Vec::new();
451
452    for (edge_id, edge) in &after_edges {
453        if before_edges.contains_key(edge_id) {
454            continue;
455        }
456        if let Some(typed_edge) = typed_graph_delta_edge_from_summary_edge(edge) {
457            added_edges.push(typed_edge);
458        } else {
459            invalid_delta_edge_ids.push((*edge_id).to_string());
460        }
461    }
462    for (edge_id, edge) in &before_edges {
463        if after_edges.contains_key(edge_id) {
464            continue;
465        }
466        if let Some(typed_edge) = typed_graph_delta_edge_from_summary_edge(edge) {
467            removed_edges.push(typed_edge);
468        } else {
469            invalid_delta_edge_ids.push((*edge_id).to_string());
470        }
471    }
472
473    added_edges.sort_by_key(|edge| edge.edge_id.clone());
474    removed_edges.sort_by_key(|edge| edge.edge_id.clone());
475    invalid_delta_edge_ids.sort();
476    let all_delta_edges_typed = invalid_delta_edge_ids.is_empty();
477
478    OmenaCrossFileGraphDeltaV0 {
479        schema_version: "0",
480        product: "omena-cross-file-summary.graph-delta",
481        status: if all_delta_edges_typed {
482            "ready"
483        } else {
484            "needsInput"
485        },
486        before_edge_count: before.summary_edge_count,
487        after_edge_count: after.summary_edge_count,
488        added_edges,
489        removed_edges,
490        invalid_delta_edge_ids,
491        all_delta_edges_typed,
492    }
493}
494
495fn invalid_raw_edge_kinds_for_summary(summary: &OmenaQueryCrossFileSummaryV0) -> Vec<String> {
496    summary
497        .edges
498        .iter()
499        .filter(|edge| parse_cross_file_summary_raw_edge_kind_v0(edge.edge_kind).is_none())
500        .map(|edge| edge.edge_kind.to_string())
501        .collect::<BTreeSet<_>>()
502        .into_iter()
503        .collect()
504}
505
506fn invalid_node_roles_for_summary(summary: &OmenaQueryCrossFileSummaryV0) -> Vec<String> {
507    let mut invalid = BTreeSet::new();
508    for edge in &summary.edges {
509        if parse_cross_file_summary_node_role_v0(edge.from_kind).is_none() {
510            invalid.insert(edge.from_kind.to_string());
511        }
512        if let Some(target_kind) = edge.target_kind
513            && parse_cross_file_summary_node_role_v0(target_kind).is_none()
514        {
515            invalid.insert(target_kind.to_string());
516        }
517    }
518    invalid.into_iter().collect()
519}
520
521fn typed_graph_delta_edge_from_summary_edge(
522    edge: &OmenaQueryCrossFileSummaryEdgeV0,
523) -> Option<OmenaCrossFileGraphDeltaEdgeV0> {
524    let raw_edge_kind = parse_cross_file_summary_raw_edge_kind_v0(edge.edge_kind)?;
525    let from_role = parse_cross_file_summary_node_role_v0(edge.from_kind)?;
526    let target_role = match edge.target_kind {
527        Some(target_kind) => Some(parse_cross_file_summary_node_role_v0(target_kind)?),
528        None => None,
529    };
530    Some(OmenaCrossFileGraphDeltaEdgeV0 {
531        edge_id: edge.edge_id.clone(),
532        raw_edge_kind: raw_edge_kind.as_wire_label(),
533        folded_edge_kind: raw_edge_kind.folded_edge_kind(),
534        folded_by_lossy_catch_all: raw_edge_kind.folded_by_lossy_catch_all(),
535        from_role,
536        target_role,
537        from_path: edge.from_path.clone(),
538        target_path: edge.target_path.clone(),
539    })
540}
541
542pub fn reverse_dependency_index_from_edges_v0(
543    edges: &[OmenaQueryCrossFileSummaryEdgeV0],
544) -> ReverseDependencyIndexV0 {
545    let mut index = ReverseDependencyIndexV0 {
546        rev: BTreeMap::new(),
547        edges_by_from: BTreeMap::new(),
548    };
549    for edge in edges {
550        let Some(target_path) = edge.target_path.as_ref() else {
551            continue;
552        };
553        index
554            .edges_by_from
555            .entry(edge.from_path.clone())
556            .or_default()
557            .insert(target_path.clone());
558        index
559            .rev
560            .entry(target_path.clone())
561            .or_default()
562            .insert(edge.from_path.clone());
563    }
564    index
565}
566
567pub fn apply_reverse_dependency_delta_v0(
568    index: &mut ReverseDependencyIndexV0,
569    next_edges: &[OmenaQueryCrossFileSummaryEdgeV0],
570) -> usize {
571    let next_groups = reverse_dependency_groups_by_from_path(next_edges);
572    let mut from_paths = index.edges_by_from.keys().cloned().collect::<BTreeSet<_>>();
573    from_paths.extend(next_groups.keys().cloned());
574
575    let mut patched_groups = 0;
576    for from_path in from_paths {
577        let old_targets = index
578            .edges_by_from
579            .get(from_path.as_str())
580            .cloned()
581            .unwrap_or_default();
582        let new_targets = next_groups
583            .get(from_path.as_str())
584            .cloned()
585            .unwrap_or_default();
586        if old_targets == new_targets {
587            continue;
588        }
589        patched_groups += 1;
590        for target in &old_targets {
591            if let Some(dependents) = index.rev.get_mut(target.as_str()) {
592                dependents.remove(from_path.as_str());
593                if dependents.is_empty() {
594                    index.rev.remove(target.as_str());
595                }
596            }
597        }
598        if new_targets.is_empty() {
599            index.edges_by_from.remove(from_path.as_str());
600        } else {
601            for target in &new_targets {
602                index
603                    .rev
604                    .entry(target.clone())
605                    .or_default()
606                    .insert(from_path.clone());
607            }
608            index.edges_by_from.insert(from_path, new_targets);
609        }
610    }
611    patched_groups
612}
613
614pub fn reverse_dependency_closure_v0(
615    index: &ReverseDependencyIndexV0,
616    seeds: &BTreeSet<String>,
617) -> BTreeSet<String> {
618    let mut visited = BTreeSet::new();
619    let mut queue = seeds.iter().cloned().collect::<VecDeque<_>>();
620    while let Some(path) = queue.pop_front() {
621        if let Some(dependents) = index.rev.get(path.as_str()) {
622            for dependent in dependents {
623                if visited.insert(dependent.clone()) {
624                    queue.push_back(dependent.clone());
625                }
626            }
627        }
628    }
629    visited
630}
631
632/// The declared read-set of ONE style target's workspace diagnostics, as a
633/// path set over the summary's edge graph: the target itself, its FORWARD
634/// closure (modules whose contents the target's resolution, token, cascade,
635/// replica-ensemble, and reachability arms read), and its DIRECT reverse
636/// neighbors (style and source files whose references decide the target's
637/// usage-derived diagnostics). This is the verifying-trace manifest for the
638/// disk diagnostics cache: completeness is oracle-gated in the LSP crate
639/// (a manifest-verified hit must be byte-identical to a fresh compute), so
640/// any diagnostics arm that grows a wider read window fails the oracle
641/// instead of silently serving stale shards.
642pub fn diagnostics_read_set_for_target_v0(
643    index: &ReverseDependencyIndexV0,
644    target_path: &str,
645) -> BTreeSet<String> {
646    let mut read_set = BTreeSet::from([target_path.to_string()]);
647    let mut queue = VecDeque::from([target_path.to_string()]);
648    while let Some(path) = queue.pop_front() {
649        if let Some(targets) = index.edges_by_from.get(path.as_str()) {
650            for next in targets {
651                if read_set.insert(next.clone()) {
652                    queue.push_back(next.clone());
653                }
654            }
655        }
656    }
657    if let Some(dependents) = index.rev.get(target_path) {
658        read_set.extend(dependents.iter().cloned());
659    }
660    read_set
661}
662
663fn reverse_dependency_groups_by_from_path(
664    edges: &[OmenaQueryCrossFileSummaryEdgeV0],
665) -> BTreeMap<String, BTreeSet<String>> {
666    let mut groups = BTreeMap::<String, BTreeSet<String>>::new();
667    for edge in edges {
668        let Some(target_path) = edge.target_path.as_ref() else {
669            continue;
670        };
671        groups
672            .entry(edge.from_path.clone())
673            .or_default()
674            .insert(target_path.clone());
675    }
676    groups
677}
678
679#[non_exhaustive]
680#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
681#[serde(rename_all = "camelCase")]
682pub enum UnifiedHypergraphEdgeKindV0 {
683    ComposesLocal,
684    ComposesGlobal,
685    ComposesExternal,
686    SassUse,
687    SassForward,
688    SassImport,
689    LessImport,
690    LessModuleGraphClosure,
691    Value,
692    Icss,
693    ForeignReference,
694}
695
696#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
697#[serde(rename_all = "camelCase")]
698pub enum EdgeOrderRelevanceV0 {
699    OrderBearing,
700    OrderNeutral,
701}
702
703impl EdgeOrderRelevanceV0 {
704    pub const fn as_wire_label(self) -> &'static str {
705        match self {
706            Self::OrderBearing => "orderBearing",
707            Self::OrderNeutral => "orderNeutral",
708        }
709    }
710}
711
712impl UnifiedHypergraphEdgeKindV0 {
713    pub const fn as_wire_label(self) -> &'static str {
714        match self {
715            Self::ComposesLocal => "composesLocal",
716            Self::ComposesGlobal => "composesGlobal",
717            Self::ComposesExternal => "composesExternal",
718            Self::SassUse => "sassUse",
719            Self::SassForward => "sassForward",
720            Self::SassImport => "sassImport",
721            Self::LessImport => "lessImport",
722            Self::LessModuleGraphClosure => "lessModuleGraphClosure",
723            Self::Value => "value",
724            Self::Icss => "icss",
725            Self::ForeignReference => "foreignReference",
726        }
727    }
728
729    pub const fn order_relevance(self) -> EdgeOrderRelevanceV0 {
730        match self {
731            Self::ComposesLocal
732            | Self::ComposesGlobal
733            | Self::ComposesExternal
734            | Self::SassUse
735            | Self::SassForward
736            | Self::SassImport
737            | Self::LessImport
738            | Self::Value
739            | Self::Icss => EdgeOrderRelevanceV0::OrderBearing,
740            Self::LessModuleGraphClosure | Self::ForeignReference => {
741                EdgeOrderRelevanceV0::OrderNeutral
742            }
743        }
744    }
745
746    pub const fn is_order_significant(self) -> bool {
747        matches!(self.order_relevance(), EdgeOrderRelevanceV0::OrderBearing)
748    }
749}
750
751#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
752#[serde(rename_all = "camelCase")]
753pub struct UnifiedHypergraphHyperedgeV0 {
754    pub schema_version: &'static str,
755    pub product: &'static str,
756    pub layer_marker: &'static str,
757    pub feature_gate: &'static str,
758    pub hyperedge_id: String,
759    pub edge_kind: UnifiedHypergraphEdgeKindV0,
760    pub source_summary_edge_id: String,
761    pub source_edge_kind: &'static str,
762    pub source_status: &'static str,
763    pub tail_node_ids: Vec<String>,
764    pub head_node_id: String,
765    pub order_significant_tail: bool,
766}
767
768#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
769#[serde(rename_all = "camelCase")]
770pub struct HypergraphMonotoneFactPropagationSummaryEdgeV0 {
771    pub schema_version: &'static str,
772    pub product: &'static str,
773    pub layer_marker: &'static str,
774    pub feature_gate: &'static str,
775    pub summary_edge_id: String,
776    pub projection_edge_id: String,
777    pub hyperedge_id: String,
778    pub from_node_id: String,
779    pub to_node_id: String,
780    pub edge_kind: UnifiedHypergraphEdgeKindV0,
781    pub status: &'static str,
782    pub provenance: Vec<&'static str>,
783    pub linear_provenance: OmenaCrossFileLinearProvenanceV0,
784}
785
786/// Compatibility summary edge retained for the published 0.3 nominal surface.
787/// Owner: `omena-cross-file-summary` maintainers. Removal condition: not before
788/// 1.0, after downstream migration and zero audited non-compatibility uses.
789#[deprecated(
790    since = "0.4.0",
791    note = "use HypergraphMonotoneFactPropagationSummaryEdgeV0; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
792)]
793#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
794#[serde(rename_all = "camelCase")]
795pub struct HypergraphIFDSSummaryEdgeV0 {
796    pub schema_version: &'static str,
797    pub product: &'static str,
798    pub layer_marker: &'static str,
799    pub feature_gate: &'static str,
800    pub summary_edge_id: String,
801    pub projection_edge_id: String,
802    pub hyperedge_id: String,
803    pub from_node_id: String,
804    pub to_node_id: String,
805    pub edge_kind: UnifiedHypergraphEdgeKindV0,
806    pub status: &'static str,
807    pub provenance: Vec<&'static str>,
808    pub linear_provenance: OmenaCrossFileLinearProvenanceV0,
809}
810
811#[allow(deprecated)]
812#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
813#[serde(rename_all = "camelCase")]
814pub struct OmenaQueryUnifiedCrossFileHypergraphV0 {
815    pub schema_version: &'static str,
816    pub product: &'static str,
817    pub status: &'static str,
818    pub layer_marker: &'static str,
819    pub feature_gate: &'static str,
820    pub node_count: usize,
821    pub hyperedge_count: usize,
822    pub summary_edge_count: usize,
823    pub projection_edge_ids: Vec<String>,
824    pub hyperedges: Vec<UnifiedHypergraphHyperedgeV0>,
825    /// Published compatibility field. Use the monotone-fact-propagation aggregate
826    /// for new code.
827    #[deprecated(
828        since = "0.4.0",
829        note = "use OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0::summary_edges; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
830    )]
831    pub summary_edges: Vec<HypergraphIFDSSummaryEdgeV0>,
832    pub gate_predicates: Vec<&'static str>,
833}
834
835#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
836#[serde(rename_all = "camelCase")]
837pub struct OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0 {
838    pub schema_version: &'static str,
839    pub product: &'static str,
840    pub status: &'static str,
841    pub layer_marker: &'static str,
842    pub feature_gate: &'static str,
843    pub node_count: usize,
844    pub hyperedge_count: usize,
845    pub summary_edge_count: usize,
846    pub projection_edge_ids: Vec<String>,
847    pub hyperedges: Vec<UnifiedHypergraphHyperedgeV0>,
848    pub summary_edges: Vec<HypergraphMonotoneFactPropagationSummaryEdgeV0>,
849    pub gate_predicates: Vec<&'static str>,
850}
851
852#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
853#[serde(rename_all = "camelCase")]
854pub struct OmenaQueryCrossFileSccEvidenceV0 {
855    pub schema_version: &'static str,
856    pub product: &'static str,
857    pub feature_gate: &'static str,
858    pub claim_level: &'static str,
859    pub theorem_claimed: bool,
860    pub connectivity_backend: &'static str,
861    pub polylog_bound_scope: &'static str,
862    pub scc_id: String,
863    pub node_count: usize,
864    pub directed_edge_count: usize,
865    pub cross_file: bool,
866    pub node_ids: Vec<String>,
867    pub style_paths: Vec<String>,
868    pub edge_kinds: Vec<&'static str>,
869    pub summary_edge_ids: Vec<String>,
870}
871
872#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
873#[serde(rename_all = "camelCase")]
874pub struct OmenaQueryUnifiedCrossFileSccReportV0 {
875    pub schema_version: &'static str,
876    pub product: &'static str,
877    pub feature_gate: &'static str,
878    pub claim_level: &'static str,
879    pub theorem_claimed: bool,
880    pub connectivity_backend: &'static str,
881    pub polylog_bound_scope: &'static str,
882    pub node_count: usize,
883    pub directed_edge_count: usize,
884    pub cyclic_scc_count: usize,
885    pub sccs: Vec<OmenaQueryCrossFileSccEvidenceV0>,
886    pub gate_predicates: Vec<&'static str>,
887}
888
889#[derive(Debug, Clone, PartialEq, Eq)]
890pub struct HypergraphClosurePath<N> {
891    pub origin: N,
892    pub target: N,
893    pub depth: usize,
894    pub path_labels: Vec<String>,
895}
896
897#[derive(Debug, Clone, Copy, PartialEq, Eq)]
898pub enum HypergraphClosureMode {
899    CanonicalFirstTarget,
900    RawAllPaths,
901}
902
903pub trait OmenaUnifiedHypergraphConnectivityOracle {
904    fn reachable_node_ids(
905        &self,
906        start_node_id: &str,
907        hyperedges: &[UnifiedHypergraphHyperedgeV0],
908    ) -> Vec<String>;
909}
910
911#[derive(Debug, Clone, Copy, Default)]
912pub struct BatchHypergraphConnectivityOracle;
913
914impl OmenaUnifiedHypergraphConnectivityOracle for BatchHypergraphConnectivityOracle {
915    fn reachable_node_ids(
916        &self,
917        start_node_id: &str,
918        hyperedges: &[UnifiedHypergraphHyperedgeV0],
919    ) -> Vec<String> {
920        collect_reachable_node_ids(start_node_id, &build_adjacency(hyperedges))
921    }
922}
923
924/// The single shared reachability BFS loop for the cross-file engine: forward closure over a
925/// deterministic `BTreeMap` adjacency, returned sorted (BTreeSet order). Generic over the
926/// adjacency key type so each caller keeps its OWN adjacency builder (the distinct node spaces
927/// comment-2 point 4 demands) while sharing exactly one traversal loop. (The substrate diagnostics
928/// reachability is a separate borrowed-`&str` DFS over inline-filtered `resolved` edges and is
929/// intentionally NOT one of the two BFS impls this collapses.)
930pub fn collect_reachable_node_ids<K>(
931    start_node_id: &str,
932    adjacency: &BTreeMap<K, BTreeSet<String>>,
933) -> Vec<String>
934where
935    K: Ord + std::borrow::Borrow<str>,
936{
937    let mut seen = BTreeSet::new();
938    let mut pending = VecDeque::from([start_node_id.to_string()]);
939    while let Some(current) = pending.pop_front() {
940        for target in adjacency.get(current.as_str()).into_iter().flatten() {
941            if seen.insert(target.clone()) {
942                pending.push_back(target.clone());
943            }
944        }
945    }
946    seen.into_iter().collect()
947}
948
949pub fn collect_reachable_node_ids_bitset<K>(
950    start_node_id: &str,
951    adjacency: &BTreeMap<K, BTreeSet<String>>,
952) -> Vec<String>
953where
954    K: Ord + std::borrow::Borrow<str>,
955{
956    let dense_index = DenseNodeIndexV0::from_adjacency(start_node_id, adjacency);
957    let Some(start_index) = dense_index.index_of(start_node_id) else {
958        return Vec::new();
959    };
960    let dense_adjacency = dense_index.dense_adjacency(adjacency);
961    let mut seen = DenseBitsetV0::new(dense_index.len());
962    let mut pending = VecDeque::from([start_index]);
963    while let Some(current) = pending.pop_front() {
964        for target in dense_adjacency
965            .get(current)
966            .into_iter()
967            .flat_map(|targets| targets.iter().copied())
968        {
969            if seen.insert(target) {
970                pending.push_back(target);
971            }
972        }
973    }
974    dense_index.ids_for_bitset(&seen)
975}
976
977#[derive(Debug, Clone)]
978struct DenseNodeIndexV0 {
979    ids: Vec<String>,
980    positions: BTreeMap<String, usize>,
981}
982
983impl DenseNodeIndexV0 {
984    fn from_adjacency<K>(start_node_id: &str, adjacency: &BTreeMap<K, BTreeSet<String>>) -> Self
985    where
986        K: Ord + std::borrow::Borrow<str>,
987    {
988        let mut ids = BTreeSet::from([start_node_id.to_string()]);
989        for (source, targets) in adjacency {
990            ids.insert(source.borrow().to_string());
991            ids.extend(targets.iter().cloned());
992        }
993        let ids = ids.into_iter().collect::<Vec<_>>();
994        let positions = ids
995            .iter()
996            .enumerate()
997            .map(|(index, node_id)| (node_id.clone(), index))
998            .collect::<BTreeMap<_, _>>();
999        Self { ids, positions }
1000    }
1001
1002    fn len(&self) -> usize {
1003        self.ids.len()
1004    }
1005
1006    fn index_of(&self, node_id: &str) -> Option<usize> {
1007        self.positions.get(node_id).copied()
1008    }
1009
1010    fn dense_adjacency<K>(&self, adjacency: &BTreeMap<K, BTreeSet<String>>) -> Vec<Vec<usize>>
1011    where
1012        K: Ord + std::borrow::Borrow<str>,
1013    {
1014        let mut dense_adjacency = vec![Vec::new(); self.ids.len()];
1015        for (source, targets) in adjacency {
1016            let Some(source_index) = self.index_of(source.borrow()) else {
1017                continue;
1018            };
1019            dense_adjacency[source_index] = targets
1020                .iter()
1021                .filter_map(|target| self.index_of(target))
1022                .collect();
1023        }
1024        dense_adjacency
1025    }
1026
1027    fn ids_for_bitset(&self, bitset: &DenseBitsetV0) -> Vec<String> {
1028        self.ids
1029            .iter()
1030            .enumerate()
1031            .filter(|(index, _)| bitset.contains(*index))
1032            .map(|(_, node_id)| node_id.clone())
1033            .collect()
1034    }
1035}
1036
1037#[derive(Debug, Clone)]
1038struct DenseBitsetV0 {
1039    words: Vec<u64>,
1040}
1041
1042impl DenseBitsetV0 {
1043    fn new(len: usize) -> Self {
1044        Self {
1045            words: vec![0; len.div_ceil(64)],
1046        }
1047    }
1048
1049    fn insert(&mut self, index: usize) -> bool {
1050        let word_index = index / 64;
1051        let mask = 1u64 << (index % 64);
1052        let word = &mut self.words[word_index];
1053        let was_empty = *word & mask == 0;
1054        *word |= mask;
1055        was_empty
1056    }
1057
1058    fn contains(&self, index: usize) -> bool {
1059        self.words
1060            .get(index / 64)
1061            .is_some_and(|word| word & (1u64 << (index % 64)) != 0)
1062    }
1063}
1064
1065pub fn tabulate_hypergraph_monotone_fact_propagation_summary_edges(
1066    hyperedges: &[UnifiedHypergraphHyperedgeV0],
1067    projected_edges: Vec<HypergraphMonotoneFactPropagationSummaryEdgeV0>,
1068) -> Vec<HypergraphMonotoneFactPropagationSummaryEdgeV0> {
1069    let hyperedge_ids = hyperedges
1070        .iter()
1071        .map(|edge| edge.hyperedge_id.as_str())
1072        .collect::<BTreeSet<_>>();
1073    let mut edges = projected_edges
1074        .into_iter()
1075        .filter(|edge| hyperedge_ids.contains(edge.hyperedge_id.as_str()))
1076        .collect::<Vec<_>>();
1077    edges.sort_by(|left, right| {
1078        left.projection_edge_id
1079            .cmp(&right.projection_edge_id)
1080            .then(left.hyperedge_id.cmp(&right.hyperedge_id))
1081    });
1082    edges
1083}
1084
1085#[allow(deprecated)]
1086#[deprecated(
1087    since = "0.4.0",
1088    note = "compatibility conversion owned by omena-cross-file-summary maintainers; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
1089)]
1090fn hypergraph_summary_edge_into_compatibility_wire_v0(
1091    edge: HypergraphMonotoneFactPropagationSummaryEdgeV0,
1092) -> HypergraphIFDSSummaryEdgeV0 {
1093    HypergraphIFDSSummaryEdgeV0 {
1094        schema_version: edge.schema_version,
1095        product: "omena-query.hypergraph-ifds-summary-edge",
1096        layer_marker: "hypergraph-ifds",
1097        feature_gate: "hypergraph-ifds",
1098        summary_edge_id: edge.summary_edge_id.replacen(
1099            "monotone-fact-propagation-summary:",
1100            "ifds-summary:",
1101            1,
1102        ),
1103        projection_edge_id: edge.projection_edge_id,
1104        hyperedge_id: edge.hyperedge_id,
1105        from_node_id: edge.from_node_id,
1106        to_node_id: edge.to_node_id,
1107        edge_kind: edge.edge_kind,
1108        status: edge.status,
1109        provenance: edge.provenance,
1110        linear_provenance: edge.linear_provenance,
1111    }
1112}
1113
1114#[allow(deprecated)]
1115#[deprecated(
1116    since = "0.4.0",
1117    note = "compatibility conversion owned by omena-cross-file-summary maintainers; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
1118)]
1119fn hypergraph_summary_edge_into_canonical_v0(
1120    edge: HypergraphIFDSSummaryEdgeV0,
1121) -> HypergraphMonotoneFactPropagationSummaryEdgeV0 {
1122    HypergraphMonotoneFactPropagationSummaryEdgeV0 {
1123        schema_version: edge.schema_version,
1124        product: "omena-query.hypergraph-monotone-fact-propagation-summary-edge",
1125        layer_marker: "hypergraph-monotone-fact-propagation",
1126        feature_gate: "hypergraph-monotone-fact-propagation",
1127        summary_edge_id: edge.summary_edge_id.replacen(
1128            "ifds-summary:",
1129            "monotone-fact-propagation-summary:",
1130            1,
1131        ),
1132        projection_edge_id: edge.projection_edge_id,
1133        hyperedge_id: edge.hyperedge_id,
1134        from_node_id: edge.from_node_id,
1135        to_node_id: edge.to_node_id,
1136        edge_kind: edge.edge_kind,
1137        status: edge.status,
1138        provenance: edge.provenance,
1139        linear_provenance: edge.linear_provenance,
1140    }
1141}
1142
1143/// Published 0.3 compatibility wrapper. New callers should use the monotone
1144/// fact-propagation spelling above.
1145#[allow(deprecated)]
1146#[deprecated(
1147    since = "0.4.0",
1148    note = "use tabulate_hypergraph_monotone_fact_propagation_summary_edges; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
1149)]
1150pub fn tabulate_hypergraph_ifds_summary_edges(
1151    hyperedges: &[UnifiedHypergraphHyperedgeV0],
1152    projected_edges: Vec<HypergraphIFDSSummaryEdgeV0>,
1153) -> Vec<HypergraphIFDSSummaryEdgeV0> {
1154    tabulate_hypergraph_monotone_fact_propagation_summary_edges(
1155        hyperedges,
1156        projected_edges
1157            .into_iter()
1158            .map(hypergraph_summary_edge_into_canonical_v0)
1159            .collect(),
1160    )
1161    .into_iter()
1162    .map(hypergraph_summary_edge_into_compatibility_wire_v0)
1163    .collect()
1164}
1165
1166pub fn summarize_omena_query_unified_cross_file_scc_report(
1167    hypergraph: &OmenaQueryUnifiedCrossFileHypergraphV0,
1168) -> OmenaQueryUnifiedCrossFileSccReportV0 {
1169    #[allow(deprecated)]
1170    let canonical_summary_edges = hypergraph
1171        .summary_edges
1172        .iter()
1173        .cloned()
1174        .map(hypergraph_summary_edge_into_canonical_v0)
1175        .collect::<Vec<_>>();
1176    let adjacency = build_directed_projection_adjacency(&canonical_summary_edges);
1177    let mut sccs = collect_directed_graph_sccs(&adjacency)
1178        .into_iter()
1179        .filter_map(|node_ids| summarize_cyclic_scc(&node_ids, &canonical_summary_edges))
1180        .collect::<Vec<_>>();
1181    sccs.sort_by(|left, right| {
1182        left.node_ids
1183            .cmp(&right.node_ids)
1184            .then(left.summary_edge_ids.cmp(&right.summary_edge_ids))
1185    });
1186    for (index, scc) in sccs.iter_mut().enumerate() {
1187        scc.scc_id = format!("exact-tarjan-scc:{}", index + 1);
1188    }
1189
1190    OmenaQueryUnifiedCrossFileSccReportV0 {
1191        schema_version: "0",
1192        product: "omena-query.unified-cross-file-scc-report",
1193        feature_gate: "cross-file-scc-v0",
1194        claim_level: "fixtureWitnessExactTarjanScc",
1195        theorem_claimed: false,
1196        connectivity_backend: "exactTarjanScc",
1197        polylog_bound_scope: "notClaimedExactTraversal",
1198        node_count: adjacency.len(),
1199        directed_edge_count: canonical_summary_edges
1200            .iter()
1201            .filter(|edge| summary_edge_has_supported_target(edge.status))
1202            .count(),
1203        cyclic_scc_count: sccs.len(),
1204        sccs,
1205        gate_predicates: vec![
1206            "exactTarjanSccBackend",
1207            "theorem_claimed=false",
1208            "polylog_bound_scope=notClaimedExactTraversal",
1209        ],
1210    }
1211}
1212
1213#[allow(deprecated)]
1214pub fn summarize_omena_query_unified_cross_file_hypergraph(
1215    summary: &OmenaQueryCrossFileSummaryV0,
1216) -> OmenaQueryUnifiedCrossFileHypergraphV0 {
1217    hypergraph_into_compatibility_wire_v0(
1218        summarize_omena_query_unified_cross_file_monotone_fact_propagation_hypergraph(summary),
1219    )
1220}
1221
1222pub fn summarize_omena_query_unified_cross_file_monotone_fact_propagation_hypergraph(
1223    summary: &OmenaQueryCrossFileSummaryV0,
1224) -> OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0 {
1225    let mut builder = UnifiedCrossFileHypergraphBuilder::default();
1226    for edge in &summary.edges {
1227        builder.add_summary_edge(edge);
1228    }
1229    builder.finish()
1230}
1231
1232#[allow(deprecated)]
1233#[deprecated(
1234    since = "0.4.0",
1235    note = "compatibility conversion owned by omena-cross-file-summary maintainers; removal is not before 1.0 and requires downstream migration plus zero audited non-compatibility uses"
1236)]
1237fn hypergraph_into_compatibility_wire_v0(
1238    hypergraph: OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0,
1239) -> OmenaQueryUnifiedCrossFileHypergraphV0 {
1240    let hyperedges = hypergraph
1241        .hyperedges
1242        .into_iter()
1243        .map(|mut edge| {
1244            edge.layer_marker = "hypergraph-ifds";
1245            edge.feature_gate = "hypergraph-ifds";
1246            edge
1247        })
1248        .collect();
1249    let summary_edges = hypergraph
1250        .summary_edges
1251        .into_iter()
1252        .map(hypergraph_summary_edge_into_compatibility_wire_v0)
1253        .collect();
1254    OmenaQueryUnifiedCrossFileHypergraphV0 {
1255        schema_version: hypergraph.schema_version,
1256        product: hypergraph.product,
1257        status: "hypergraphIfdsProjection",
1258        layer_marker: "hypergraph-ifds",
1259        feature_gate: "hypergraph-ifds",
1260        node_count: hypergraph.node_count,
1261        hyperedge_count: hypergraph.hyperedge_count,
1262        summary_edge_count: hypergraph.summary_edge_count,
1263        projection_edge_ids: hypergraph.projection_edge_ids,
1264        hyperedges,
1265        summary_edges,
1266        gate_predicates: hypergraph.gate_predicates,
1267    }
1268}
1269
1270pub fn collect_hypergraph_transitive_closure_paths<N, F>(
1271    graph: &BTreeMap<N, BTreeSet<N>>,
1272    mut label: F,
1273) -> (Vec<HypergraphClosurePath<N>>, Vec<Vec<String>>)
1274where
1275    N: Clone + Ord,
1276    F: FnMut(&N) -> String,
1277{
1278    collect_hypergraph_transitive_closure_paths_with_mode(
1279        graph,
1280        &mut label,
1281        HypergraphClosureMode::CanonicalFirstTarget,
1282    )
1283}
1284
1285pub fn collect_hypergraph_transitive_closure_paths_with_mode<N, F>(
1286    graph: &BTreeMap<N, BTreeSet<N>>,
1287    label: &mut F,
1288    mode: HypergraphClosureMode,
1289) -> (Vec<HypergraphClosurePath<N>>, Vec<Vec<String>>)
1290where
1291    N: Clone + Ord,
1292    F: FnMut(&N) -> String,
1293{
1294    let mut closure_paths = Vec::new();
1295    let mut cycle_paths = Vec::new();
1296    let mut seen_cycles = BTreeSet::new();
1297    let first_target = mode == HypergraphClosureMode::CanonicalFirstTarget;
1298
1299    for start in graph.keys() {
1300        let mut visited = BTreeSet::new();
1301        let mut pending = VecDeque::from([(start.clone(), vec![start.clone()])]);
1302        while let Some((current, path)) = pending.pop_front() {
1303            for target in graph.get(&current).into_iter().flatten() {
1304                if let Some(cycle_start) = path.iter().position(|node| node == target) {
1305                    let mut cycle = path[cycle_start..].to_vec();
1306                    cycle.push(target.clone());
1307                    let mut labels = cycle.iter().map(&mut *label).collect::<Vec<_>>();
1308                    if first_target {
1309                        labels = canonical_hypergraph_cycle_labels(labels);
1310                    }
1311                    if !labels.is_empty() && seen_cycles.insert(labels.clone()) {
1312                        cycle_paths.push(labels);
1313                    }
1314                    continue;
1315                }
1316                if first_target && !visited.insert(target.clone()) {
1317                    continue;
1318                }
1319                let mut edge_path = path.clone();
1320                edge_path.push(target.clone());
1321                closure_paths.push(HypergraphClosurePath {
1322                    origin: start.clone(),
1323                    target: target.clone(),
1324                    depth: edge_path.len().saturating_sub(1),
1325                    path_labels: edge_path.iter().map(&mut *label).collect(),
1326                });
1327                pending.push_back((target.clone(), edge_path));
1328            }
1329        }
1330    }
1331    (closure_paths, cycle_paths)
1332}
1333
1334/// Generous per-SCC enumeration work budget; real module-graph SCCs are tiny (a cycle is a user
1335/// error to report), so the cap is a backstop that never fires in practice.
1336const DEFAULT_CYCLE_ENUMERATION_WORK_CAP: usize = 1 << 16;
1337
1338/// All elementary directed circuits of `adjacency`, found per strongly-connected component:
1339/// partition with `collect_directed_graph_sccs`, then enumerate the simple cycles CONFINED to each
1340/// non-trivial SCC (a back-edge to the start closes a circuit). Each circuit is canonicalized via
1341/// `canonical_hypergraph_cycle_labels` (lex-smallest rotation, emitted CLOSED so a consumer's
1342/// `windows(2)` successor lookup resolves), deduped and sorted. This is the cross-file CYCLE owner,
1343/// decoupled from the all-paths closure scan so the latter can be replaced without touching cycles.
1344pub fn collect_directed_graph_cycles(
1345    adjacency: &BTreeMap<String, BTreeSet<String>>,
1346) -> Vec<Vec<String>> {
1347    collect_directed_graph_cycles_with_work_cap(adjacency, DEFAULT_CYCLE_ENUMERATION_WORK_CAP)
1348}
1349
1350/// `collect_directed_graph_cycles` with an explicit per-SCC work cap (for tests). On cap-hit a
1351/// dense SCC degrades to its lex-smallest representative circuit — a witnessed shrink, NEVER a
1352/// silent drop.
1353pub fn collect_directed_graph_cycles_with_work_cap(
1354    adjacency: &BTreeMap<String, BTreeSet<String>>,
1355    per_scc_work_cap: usize,
1356) -> Vec<Vec<String>> {
1357    let mut circuits = BTreeSet::new();
1358    for scc in collect_directed_graph_sccs(adjacency) {
1359        let self_loop = scc.len() == 1
1360            && adjacency
1361                .get(scc[0].as_str())
1362                .is_some_and(|targets| targets.contains(&scc[0]));
1363        if scc.len() < 2 && !self_loop {
1364            continue;
1365        }
1366        let scc_nodes = scc.iter().map(String::as_str).collect::<BTreeSet<_>>();
1367        let mut found = BTreeSet::new();
1368        let mut work = 0usize;
1369        let mut capped = false;
1370        'starts: for start in &scc {
1371            // BFS over simple paths so the shortest circuits surface first (so the cap-fallback
1372            // representative is a real, short circuit).
1373            let mut pending = VecDeque::from([(start.clone(), vec![start.clone()])]);
1374            while let Some((current, path)) = pending.pop_front() {
1375                work += 1;
1376                if work > per_scc_work_cap {
1377                    capped = true;
1378                    break 'starts;
1379                }
1380                for target in adjacency.get(current.as_str()).into_iter().flatten() {
1381                    if !scc_nodes.contains(target.as_str()) {
1382                        continue;
1383                    }
1384                    if target == start {
1385                        let mut ring = path.clone();
1386                        ring.push(target.clone());
1387                        let canonical = canonical_hypergraph_cycle_labels(ring);
1388                        if !canonical.is_empty() {
1389                            found.insert(canonical);
1390                        }
1391                    } else if !path.iter().any(|node| node == target) {
1392                        let mut next = path.clone();
1393                        next.push(target.clone());
1394                        pending.push_back((target.clone(), next));
1395                    }
1396                }
1397            }
1398        }
1399        if capped {
1400            circuits.extend(found.into_iter().next());
1401        } else {
1402            circuits.extend(found);
1403        }
1404    }
1405    circuits.into_iter().collect()
1406}
1407
1408fn canonical_hypergraph_cycle_labels(mut labels: Vec<String>) -> Vec<String> {
1409    if labels.len() > 1 && labels.first() == labels.last() {
1410        labels.pop();
1411    }
1412    if labels.is_empty() {
1413        return labels;
1414    }
1415    let mut best = labels.clone();
1416    for offset in 1..labels.len() {
1417        let mut rotated = labels[offset..].to_vec();
1418        rotated.extend_from_slice(&labels[..offset]);
1419        best = best.min(rotated);
1420    }
1421    best.push(best[0].clone());
1422    best
1423}
1424
1425fn build_adjacency(
1426    hyperedges: &[UnifiedHypergraphHyperedgeV0],
1427) -> BTreeMap<&str, BTreeSet<String>> {
1428    let mut adjacency = BTreeMap::<&str, BTreeSet<String>>::new();
1429    for edge in hyperedges {
1430        for tail in &edge.tail_node_ids {
1431            adjacency
1432                .entry(tail.as_str())
1433                .or_default()
1434                .insert(edge.head_node_id.clone());
1435        }
1436    }
1437    adjacency
1438}
1439
1440#[derive(Default)]
1441struct UnifiedCrossFileHypergraphBuilder {
1442    node_ids: BTreeSet<String>,
1443    hyperedges: Vec<UnifiedHypergraphHyperedgeV0>,
1444    summary_edges: Vec<HypergraphMonotoneFactPropagationSummaryEdgeV0>,
1445}
1446
1447impl UnifiedCrossFileHypergraphBuilder {
1448    fn add_summary_edge(&mut self, edge: &OmenaQueryCrossFileSummaryEdgeV0) {
1449        let edge_kind = unified_edge_kind_for_summary_edge(edge);
1450        let from_node_id = endpoint_node_id(edge, false);
1451        let to_node_id = endpoint_node_id(edge, true);
1452        let tail_node_ids = if edge_kind.is_order_significant() && !edge.target_names.is_empty() {
1453            edge.target_names
1454                .iter()
1455                .map(|target_name| {
1456                    node_id(
1457                        "styleSymbol",
1458                        edge.target_path
1459                            .as_deref()
1460                            .unwrap_or(edge.from_path.as_str()),
1461                        Some(target_name),
1462                    )
1463                })
1464                .collect::<Vec<_>>()
1465        } else {
1466            vec![from_node_id.clone()]
1467        };
1468        self.node_ids.insert(from_node_id.clone());
1469        self.node_ids.insert(to_node_id.clone());
1470        self.node_ids.extend(tail_node_ids.iter().cloned());
1471
1472        let hyperedge_id = format!(
1473            "hyperedge:{}|{}|{}",
1474            edge_kind.as_wire_label(),
1475            edge.edge_id,
1476            tail_node_ids.join(">")
1477        );
1478        self.hyperedges.push(UnifiedHypergraphHyperedgeV0 {
1479            schema_version: "0",
1480            product: "omena-query.unified-hypergraph-hyperedge",
1481            layer_marker: "hypergraph-monotone-fact-propagation",
1482            feature_gate: "hypergraph-monotone-fact-propagation",
1483            hyperedge_id: hyperedge_id.clone(),
1484            edge_kind,
1485            source_summary_edge_id: edge.edge_id.clone(),
1486            source_edge_kind: edge.edge_kind,
1487            source_status: edge.status,
1488            tail_node_ids,
1489            head_node_id: to_node_id.clone(),
1490            order_significant_tail: edge_kind.is_order_significant(),
1491        });
1492        self.summary_edges
1493            .push(HypergraphMonotoneFactPropagationSummaryEdgeV0 {
1494                schema_version: "0",
1495                product: "omena-query.hypergraph-monotone-fact-propagation-summary-edge",
1496                layer_marker: "hypergraph-monotone-fact-propagation",
1497                feature_gate: "hypergraph-monotone-fact-propagation",
1498                summary_edge_id: format!("monotone-fact-propagation-summary:{}", edge.edge_id),
1499                projection_edge_id: edge.edge_id.clone(),
1500                hyperedge_id,
1501                from_node_id,
1502                to_node_id,
1503                edge_kind,
1504                status: edge.status,
1505                provenance: edge.provenance.clone(),
1506                linear_provenance: edge.linear_provenance.clone(),
1507            });
1508    }
1509
1510    fn finish(mut self) -> OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0 {
1511        self.hyperedges
1512            .sort_by_key(|edge| edge.hyperedge_id.clone());
1513        let summary_edges = tabulate_hypergraph_monotone_fact_propagation_summary_edges(
1514            &self.hyperedges,
1515            self.summary_edges,
1516        );
1517        let projection_edge_ids = summary_edges
1518            .iter()
1519            .map(|edge| edge.projection_edge_id.clone())
1520            .collect::<Vec<_>>();
1521
1522        OmenaQueryUnifiedCrossFileMonotoneFactPropagationHypergraphV0 {
1523            schema_version: "0",
1524            product: "omena-query.unified-cross-file-hypergraph",
1525            status: "hypergraphMonotoneFactPropagationProjection",
1526            layer_marker: "hypergraph-monotone-fact-propagation",
1527            feature_gate: "hypergraph-monotone-fact-propagation",
1528            node_count: self.node_ids.len(),
1529            hyperedge_count: self.hyperedges.len(),
1530            summary_edge_count: summary_edges.len(),
1531            projection_edge_ids,
1532            hyperedges: self.hyperedges,
1533            summary_edges,
1534            gate_predicates: vec![
1535                "P1.typeIntroduction",
1536                "P2.byteEqualAdjacencyProjection",
1537                "P3.sccUnification",
1538                "P4.summaryEdgeSetEquality",
1539                "P5.projectionHelper",
1540                "P6.closureBodySwitchOver",
1541                "P7.v0Publication",
1542                "batchConnectivityOracle",
1543                "streamingOracleWireCompatible",
1544                "composesTailOrderingUsesVec",
1545            ],
1546        }
1547    }
1548}
1549
1550fn endpoint_node_id(edge: &OmenaQueryCrossFileSummaryEdgeV0, target: bool) -> String {
1551    let (kind, path, symbol) = if target {
1552        (
1553            node_kind_for_summary_kind(edge.target_kind.unwrap_or(edge.from_kind), true),
1554            edge.target_path
1555                .as_deref()
1556                .unwrap_or(edge.from_path.as_str()),
1557            edge.remote_name
1558                .as_deref()
1559                .or_else(|| edge.target_names.first().map(String::as_str)),
1560        )
1561    } else {
1562        (
1563            node_kind_for_summary_kind(edge.from_kind, false),
1564            edge.from_path.as_str(),
1565            edge.owner_selector_name
1566                .as_deref()
1567                .or(edge.local_name.as_deref()),
1568        )
1569    };
1570    node_id(kind, path, symbol)
1571}
1572
1573fn node_id(kind: &'static str, path: &str, symbol: Option<&str>) -> String {
1574    format!("{}|{}|{}", kind, path, symbol.unwrap_or("-"))
1575}
1576
1577fn node_kind_for_summary_kind(kind: &str, target: bool) -> &'static str {
1578    match (kind, target) {
1579        ("style", false) => "styleModule",
1580        ("style", true) => "styleSymbol",
1581        ("source", false) => "sourceModule",
1582        ("source", true) => "sourceSymbol",
1583        _ => "foreignSymbol",
1584    }
1585}
1586
1587fn unified_edge_kind_for_summary_edge(
1588    edge: &OmenaQueryCrossFileSummaryEdgeV0,
1589) -> UnifiedHypergraphEdgeKindV0 {
1590    match edge.edge_kind {
1591        "composesLocal" => UnifiedHypergraphEdgeKindV0::ComposesLocal,
1592        "composesGlobal" => UnifiedHypergraphEdgeKindV0::ComposesGlobal,
1593        "cssModulesComposesImport" | "cssModulesComposesClosure" | "composesExternal" => {
1594            UnifiedHypergraphEdgeKindV0::ComposesExternal
1595        }
1596        "sassUse" => UnifiedHypergraphEdgeKindV0::SassUse,
1597        "sassForward" => UnifiedHypergraphEdgeKindV0::SassForward,
1598        "sassImport" => UnifiedHypergraphEdgeKindV0::SassImport,
1599        "lessImport" => UnifiedHypergraphEdgeKindV0::LessImport,
1600        "lessModuleGraphClosure" => UnifiedHypergraphEdgeKindV0::LessModuleGraphClosure,
1601        "cssModulesValueImport" | "cssModulesValueClosure" | "value" => {
1602            UnifiedHypergraphEdgeKindV0::Value
1603        }
1604        "cssModulesIcssImport" | "cssModulesIcssClosure" | "icss" => {
1605            UnifiedHypergraphEdgeKindV0::Icss
1606        }
1607        _ => UnifiedHypergraphEdgeKindV0::ForeignReference,
1608    }
1609}
1610
1611fn build_directed_projection_adjacency(
1612    summary_edges: &[HypergraphMonotoneFactPropagationSummaryEdgeV0],
1613) -> BTreeMap<String, BTreeSet<String>> {
1614    let mut adjacency = BTreeMap::<String, BTreeSet<String>>::new();
1615    for edge in summary_edges {
1616        if !summary_edge_has_supported_target(edge.status) {
1617            continue;
1618        }
1619        let from_node_id = canonical_scc_node_id(edge.from_node_id.as_str());
1620        let to_node_id = canonical_scc_node_id(edge.to_node_id.as_str());
1621        adjacency.entry(from_node_id.clone()).or_default();
1622        adjacency.entry(to_node_id.clone()).or_default();
1623        adjacency
1624            .entry(from_node_id)
1625            .or_default()
1626            .insert(to_node_id);
1627    }
1628    adjacency
1629}
1630
1631/// The single shared strongly-connected-components primitive for the cross-file engine: exact
1632/// Tarjan over a deterministic `BTreeMap` adjacency, each component sorted, components in Tarjan
1633/// reverse-topological discovery order. Consumed by both this crate's unified SCC report and
1634/// `omena-streaming-ifds` (which previously carried a byte-identical duplicate).
1635pub fn collect_directed_graph_sccs(
1636    adjacency: &BTreeMap<String, BTreeSet<String>>,
1637) -> Vec<Vec<String>> {
1638    let mut state = TarjanState::default();
1639    for node_id in adjacency.keys() {
1640        if !state.indices.contains_key(node_id) {
1641            state.visit(node_id, adjacency);
1642        }
1643    }
1644    state.components
1645}
1646
1647#[derive(Default)]
1648struct TarjanState {
1649    next_index: usize,
1650    stack: Vec<String>,
1651    on_stack: BTreeSet<String>,
1652    indices: BTreeMap<String, usize>,
1653    lowlinks: BTreeMap<String, usize>,
1654    components: Vec<Vec<String>>,
1655}
1656
1657impl TarjanState {
1658    fn visit(&mut self, node_id: &str, adjacency: &BTreeMap<String, BTreeSet<String>>) {
1659        let index = self.next_index;
1660        self.next_index += 1;
1661        self.indices.insert(node_id.to_string(), index);
1662        self.lowlinks.insert(node_id.to_string(), index);
1663        self.stack.push(node_id.to_string());
1664        self.on_stack.insert(node_id.to_string());
1665
1666        if let Some(targets) = adjacency.get(node_id) {
1667            for target in targets {
1668                if !self.indices.contains_key(target.as_str()) {
1669                    self.visit(target, adjacency);
1670                    let target_lowlink = self.lowlinks[target.as_str()];
1671                    let current_lowlink = self.lowlinks[node_id];
1672                    self.lowlinks
1673                        .insert(node_id.to_string(), current_lowlink.min(target_lowlink));
1674                } else if self.on_stack.contains(target.as_str()) {
1675                    let target_index = self.indices[target.as_str()];
1676                    let current_lowlink = self.lowlinks[node_id];
1677                    self.lowlinks
1678                        .insert(node_id.to_string(), current_lowlink.min(target_index));
1679                }
1680            }
1681        }
1682
1683        if self.lowlinks[node_id] == self.indices[node_id] {
1684            let mut component = Vec::new();
1685            while let Some(stack_node) = self.stack.pop() {
1686                self.on_stack.remove(stack_node.as_str());
1687                let done = stack_node == node_id;
1688                component.push(stack_node);
1689                if done {
1690                    break;
1691                }
1692            }
1693            component.sort();
1694            self.components.push(component);
1695        }
1696    }
1697}
1698
1699fn summarize_cyclic_scc(
1700    node_ids: &[String],
1701    summary_edges: &[HypergraphMonotoneFactPropagationSummaryEdgeV0],
1702) -> Option<OmenaQueryCrossFileSccEvidenceV0> {
1703    let node_set = node_ids.iter().map(String::as_str).collect::<BTreeSet<_>>();
1704    let internal_edges = summary_edges
1705        .iter()
1706        .filter(|edge| summary_edge_has_supported_target(edge.status))
1707        .filter(|edge| {
1708            let from_node_id = canonical_scc_node_id(edge.from_node_id.as_str());
1709            let to_node_id = canonical_scc_node_id(edge.to_node_id.as_str());
1710            node_set.contains(from_node_id.as_str()) && node_set.contains(to_node_id.as_str())
1711        })
1712        .collect::<Vec<_>>();
1713    let has_self_loop = internal_edges.iter().any(|edge| {
1714        canonical_scc_node_id(edge.from_node_id.as_str())
1715            == canonical_scc_node_id(edge.to_node_id.as_str())
1716    });
1717    if node_ids.len() < 2 && !has_self_loop {
1718        return None;
1719    }
1720
1721    let style_paths = node_ids
1722        .iter()
1723        .filter_map(|node_id| style_path_from_node_id(node_id))
1724        .collect::<BTreeSet<_>>()
1725        .into_iter()
1726        .collect::<Vec<_>>();
1727    let edge_kinds = internal_edges
1728        .iter()
1729        .map(|edge| edge.edge_kind.as_wire_label())
1730        .collect::<BTreeSet<_>>()
1731        .into_iter()
1732        .collect::<Vec<_>>();
1733    let summary_edge_ids = internal_edges
1734        .iter()
1735        .map(|edge| edge.projection_edge_id.clone())
1736        .collect::<BTreeSet<_>>()
1737        .into_iter()
1738        .collect::<Vec<_>>();
1739
1740    Some(OmenaQueryCrossFileSccEvidenceV0 {
1741        schema_version: "0",
1742        product: "omena-query.cross-file-scc-evidence",
1743        feature_gate: "cross-file-scc-v0",
1744        claim_level: "fixtureWitnessExactTarjanScc",
1745        theorem_claimed: false,
1746        connectivity_backend: "exactTarjanScc",
1747        polylog_bound_scope: "notClaimedExactTraversal",
1748        scc_id: String::new(),
1749        node_count: node_ids.len(),
1750        directed_edge_count: internal_edges.len(),
1751        cross_file: style_paths.len() > 1,
1752        node_ids: node_ids.to_vec(),
1753        style_paths,
1754        edge_kinds,
1755        summary_edge_ids,
1756    })
1757}
1758
1759fn style_path_from_node_id(node_id: &str) -> Option<String> {
1760    let mut parts = node_id.splitn(3, '|');
1761    let _kind = parts.next()?;
1762    let path = parts.next()?;
1763    Some(path.to_string())
1764}
1765
1766fn canonical_scc_node_id(node_id: &str) -> String {
1767    let mut parts = node_id.splitn(3, '|');
1768    let Some(kind) = parts.next() else {
1769        return node_id.to_string();
1770    };
1771    let Some(path) = parts.next() else {
1772        return node_id.to_string();
1773    };
1774    let Some(symbol) = parts.next() else {
1775        return node_id.to_string();
1776    };
1777    if kind == "styleModule" && symbol != "-" {
1778        return format!("styleSymbol|{path}|{symbol}");
1779    }
1780    node_id.to_string()
1781}
1782
1783fn summary_edge_has_supported_target(status: &str) -> bool {
1784    matches!(
1785        status,
1786        "resolved" | "reachable" | "localResolved" | "importResolved" | "external"
1787    )
1788}
1789
1790fn stable_omena_query_cross_file_summary_hash(
1791    edges: &[OmenaQueryCrossFileSummaryEdgeV0],
1792) -> String {
1793    let mut hash = 0xcbf29ce484222325u64;
1794    stable_omena_query_hash_piece(&mut hash, "omena-query.cross-file-summary");
1795    stable_omena_query_hash_piece(&mut hash, "0");
1796    for edge in edges {
1797        stable_omena_query_hash_piece(&mut hash, edge.edge_id.as_str());
1798        stable_omena_query_hash_piece(&mut hash, edge.status);
1799        stable_omena_query_hash_piece(&mut hash, edge.linear_provenance.semiring_identifier());
1800        let term_count = edge.linear_provenance.term_count.to_string();
1801        stable_omena_query_hash_piece(&mut hash, term_count.as_str());
1802        for term in &edge.linear_provenance.terms {
1803            let coefficient = term.coefficient.to_string();
1804            stable_omena_query_hash_piece(&mut hash, coefficient.as_str());
1805            stable_omena_query_hash_piece(&mut hash, term.label);
1806        }
1807    }
1808    format!("{hash:016x}")
1809}
1810
1811fn stable_omena_query_hash_piece(hash: &mut u64, piece: &str) {
1812    for byte in piece.as_bytes() {
1813        *hash ^= u64::from(*byte);
1814        *hash = hash.wrapping_mul(0x100000001b3);
1815    }
1816    *hash ^= 0xff;
1817    *hash = hash.wrapping_mul(0x100000001b3);
1818}
1819
1820#[cfg(test)]
1821mod tests {
1822    use sha2::{Digest, Sha256};
1823
1824    use super::*;
1825
1826    #[test]
1827    #[allow(deprecated)]
1828    fn compatibility_and_canonical_hypergraphs_keep_distinct_exact_wire_bytes()
1829    -> Result<(), serde_json::Error> {
1830        let summary = summary_from_edges(vec![fixture_edge_with_kind(
1831            "sassUse",
1832            "style",
1833            "/workspace/a.scss",
1834            "style",
1835            "/workspace/b.scss",
1836        )]);
1837        let compatibility = summarize_omena_query_unified_cross_file_hypergraph(&summary);
1838        let canonical =
1839            summarize_omena_query_unified_cross_file_monotone_fact_propagation_hypergraph(&summary);
1840        let compatibility_json = serde_json::to_string(&compatibility)?;
1841        let canonical_json = serde_json::to_string(&canonical)?;
1842        let digest = |bytes: &[u8]| {
1843            Sha256::digest(bytes)
1844                .iter()
1845                .map(|byte| format!("{byte:02x}"))
1846                .collect::<String>()
1847        };
1848        assert_eq!(compatibility_json.len(), 2_109);
1849        assert_eq!(
1850            digest(compatibility_json.as_bytes()),
1851            "3e937371e24d00ee36cc10874fb2b9a84e2e4d3b341c352e9fac7e96057a94ee"
1852        );
1853        assert_eq!(canonical_json.len(), 2_296);
1854        assert_eq!(
1855            digest(canonical_json.as_bytes()),
1856            "1440656b0991e00dde7782e3cabc34037ce1eaf5ddaa91c3755f5d526fd08f12"
1857        );
1858        assert_ne!(compatibility_json, canonical_json);
1859        Ok(())
1860    }
1861
1862    #[test]
1863    fn bitset_reachability_matches_btreeset_closure_order_and_cycles() {
1864        let adjacency = BTreeMap::from([
1865            (
1866                "module:root".to_string(),
1867                BTreeSet::from(["symbol:base".to_string(), "symbol:theme".to_string()]),
1868            ),
1869            (
1870                "symbol:base".to_string(),
1871                BTreeSet::from(["symbol:terminal".to_string()]),
1872            ),
1873            (
1874                "symbol:theme".to_string(),
1875                BTreeSet::from(["module:root".to_string(), "symbol:terminal".to_string()]),
1876            ),
1877        ]);
1878
1879        let btreeset = collect_reachable_node_ids("module:root", &adjacency);
1880        let bitset = collect_reachable_node_ids_bitset("module:root", &adjacency);
1881
1882        assert_eq!(
1883            bitset,
1884            vec![
1885                "module:root".to_string(),
1886                "symbol:base".to_string(),
1887                "symbol:terminal".to_string(),
1888                "symbol:theme".to_string(),
1889            ]
1890        );
1891        assert_eq!(bitset, btreeset);
1892    }
1893
1894    #[test]
1895    fn reverse_dependency_delta_matches_from_scratch_index_across_edge_edits() {
1896        let sequences = reverse_dependency_edit_sequences();
1897        assert!(sequences.len() >= 12);
1898        assert!(
1899            sequences
1900                .iter()
1901                .any(|sequence| sequence_has_add_and_remove_for_same_origin(sequence)),
1902            "fixture corpus must include add/remove edits for an existing origin"
1903        );
1904
1905        for sequence in sequences {
1906            let mut incremental = reverse_dependency_index_from_edges_v0(&[]);
1907            let mut patched_total = 0;
1908            for next_edges in &sequence {
1909                patched_total += apply_reverse_dependency_delta_v0(&mut incremental, next_edges);
1910            }
1911            let final_edges = sequence.last().map(Vec::as_slice).unwrap_or(&[]);
1912            let from_scratch = reverse_dependency_index_from_edges_v0(final_edges);
1913
1914            assert_eq!(incremental, from_scratch);
1915            assert_eq!(
1916                reverse_dependency_index_fingerprint(&incremental),
1917                reverse_dependency_index_fingerprint(&from_scratch)
1918            );
1919            assert!(patched_total > 0);
1920            assert_eq!(
1921                apply_reverse_dependency_delta_v0(&mut incremental, final_edges),
1922                0,
1923                "unchanged edge groups must not be patched"
1924            );
1925        }
1926    }
1927
1928    #[test]
1929    fn reverse_dependency_closure_keeps_transitive_source_dependents() {
1930        let edges = vec![
1931            fixture_edge(
1932                "style",
1933                "/workspace/src/Mid.module.scss",
1934                "style",
1935                "/workspace/src/Base.module.scss",
1936            ),
1937            fixture_edge(
1938                "source",
1939                "/workspace/src/App.tsx",
1940                "style",
1941                "/workspace/src/Mid.module.scss",
1942            ),
1943            fixture_edge(
1944                "source",
1945                "/workspace/src/Other.tsx",
1946                "style",
1947                "/workspace/src/Other.module.scss",
1948            ),
1949        ];
1950        let index = reverse_dependency_index_from_edges_v0(edges.as_slice());
1951        let seeds = BTreeSet::from(["/workspace/src/Base.module.scss".to_string()]);
1952        let closure = reverse_dependency_closure_v0(&index, &seeds);
1953
1954        assert!(closure.contains("/workspace/src/Mid.module.scss"));
1955        assert!(closure.contains("/workspace/src/App.tsx"));
1956        assert!(!closure.contains("/workspace/src/Other.tsx"));
1957    }
1958
1959    #[test]
1960    fn typed_vocabulary_keeps_raw_catalog_and_lossy_fold_visible() {
1961        assert_eq!(UNIFIED_HYPERGRAPH_EDGE_KIND_VARIANTS_V0.len(), 11);
1962        assert_eq!(CROSS_FILE_SUMMARY_RAW_EDGE_KIND_VARIANTS_V0.len(), 22);
1963        assert_eq!(CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0.len(), 22);
1964        assert_eq!(
1965            CROSS_FILE_SUMMARY_RAW_EDGE_KIND_VARIANTS_V0
1966                .iter()
1967                .map(|kind| kind.as_wire_label())
1968                .collect::<Vec<_>>(),
1969            CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0
1970        );
1971        assert!(
1972            CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0.contains(&"sourceSelectorPrefixReference")
1973        );
1974
1975        let prefix_kind =
1976            parse_cross_file_summary_raw_edge_kind_v0("sourceSelectorPrefixReference");
1977        assert_eq!(
1978            prefix_kind.map(OmenaCrossFileSummaryRawEdgeKindV0::folded_edge_kind),
1979            Some(UnifiedHypergraphEdgeKindV0::ForeignReference)
1980        );
1981        assert_eq!(
1982            prefix_kind.map(OmenaCrossFileSummaryRawEdgeKindV0::folded_by_lossy_catch_all),
1983            Some(true)
1984        );
1985        assert!(parse_cross_file_summary_raw_edge_kind_v0("strayEdgeKind").is_none());
1986        assert!(parse_cross_file_summary_node_role_v0("runtime").is_none());
1987    }
1988
1989    #[test]
1990    fn raw_edge_catalog_has_total_order_relevance() {
1991        let classified = CROSS_FILE_SUMMARY_RAW_EDGE_KIND_VARIANTS_V0
1992            .iter()
1993            .map(|kind| (kind.as_wire_label(), kind.order_relevance().as_wire_label()))
1994            .collect::<Vec<_>>();
1995
1996        assert_eq!(
1997            classified.len(),
1998            CROSS_FILE_SUMMARY_RAW_EDGE_KIND_LABELS_V0.len()
1999        );
2000        assert!(classified.iter().all(|(kind, relevance)| {
2001            !kind.is_empty() && matches!(*relevance, "orderBearing" | "orderNeutral")
2002        }));
2003        assert_eq!(
2004            OmenaCrossFileSummaryRawEdgeKindV0::CssModulesImport.order_relevance(),
2005            EdgeOrderRelevanceV0::OrderBearing
2006        );
2007        assert_eq!(
2008            OmenaCrossFileSummaryRawEdgeKindV0::SourceSelectorReference.order_relevance(),
2009            EdgeOrderRelevanceV0::OrderNeutral
2010        );
2011    }
2012
2013    #[test]
2014    fn summary_view_recomputes_raw_counts_from_edges() {
2015        let edges = vec![
2016            fixture_edge_with_kind(
2017                "cssModulesComposesImport",
2018                "style",
2019                "/workspace/src/Button.module.scss",
2020                "style",
2021                "/workspace/src/Base.module.scss",
2022            ),
2023            fixture_edge_with_kind(
2024                "sourceSelectorPrefixReference",
2025                "source",
2026                "/workspace/src/Button.tsx",
2027                "style",
2028                "/workspace/src/Button.module.scss",
2029            ),
2030        ];
2031        let summary = summary_from_edges(edges);
2032        let view = summarize_cross_file_summary_view_v0(&summary);
2033        assert!(view.summary_view_ready);
2034        assert_eq!(view.recomputed_edge_kind_counts, summary.edge_kind_counts);
2035
2036        let mut perturbed = summary.clone();
2037        perturbed.edge_kind_counts = vec![OmenaQueryCrossFileSummaryEdgeKindCountV0 {
2038            edge_kind: "cssModulesComposesImport",
2039            count: 99,
2040        }];
2041        let perturbed_view = summarize_cross_file_summary_view_v0(&perturbed);
2042        assert!(!perturbed_view.edge_kind_counts_match_existing_field);
2043        assert_eq!(
2044            perturbed_view.recomputed_edge_kind_counts,
2045            summary.edge_kind_counts
2046        );
2047
2048        let invalid = summary_from_edges(vec![fixture_edge_with_kind(
2049            "strayEdgeKind",
2050            "style",
2051            "/workspace/src/Button.module.scss",
2052            "style",
2053            "/workspace/src/Base.module.scss",
2054        )]);
2055        let invalid_view = summarize_cross_file_summary_view_v0(&invalid);
2056        assert!(!invalid_view.all_raw_edge_kinds_in_catalog);
2057        assert_eq!(invalid_view.invalid_raw_edge_kinds, vec!["strayEdgeKind"]);
2058    }
2059
2060    #[test]
2061    fn graph_delta_records_typed_added_and_removed_edges() {
2062        let stable_edge = fixture_edge_with_kind(
2063            "sourceSelectorReference",
2064            "source",
2065            "/workspace/src/App.tsx",
2066            "style",
2067            "/workspace/src/App.module.scss",
2068        );
2069        let removed_edge = fixture_edge_with_kind(
2070            "cssModulesValueImport",
2071            "style",
2072            "/workspace/src/Tokens.module.scss",
2073            "style",
2074            "/workspace/src/LegacyTokens.module.scss",
2075        );
2076        let added_edge = fixture_edge_with_kind(
2077            "cssModulesComposesImport",
2078            "style",
2079            "/workspace/src/Button.module.scss",
2080            "style",
2081            "/workspace/src/Base.module.scss",
2082        );
2083        let before = summary_from_edges(vec![stable_edge.clone(), removed_edge.clone()]);
2084        let after = summary_from_edges(vec![stable_edge, added_edge.clone()]);
2085        let delta = summarize_cross_file_graph_delta_v0(&before, &after);
2086
2087        assert!(delta.all_delta_edges_typed);
2088        assert_eq!(delta.added_edges.len(), 1);
2089        assert_eq!(delta.removed_edges.len(), 1);
2090        assert_eq!(delta.added_edges[0].edge_id, added_edge.edge_id);
2091        assert_eq!(
2092            delta.added_edges[0].raw_edge_kind,
2093            "cssModulesComposesImport"
2094        );
2095        assert_eq!(
2096            delta.added_edges[0].folded_edge_kind,
2097            UnifiedHypergraphEdgeKindV0::ComposesExternal
2098        );
2099        assert_eq!(delta.removed_edges[0].edge_id, removed_edge.edge_id);
2100    }
2101
2102    fn reverse_dependency_edit_sequences() -> Vec<Vec<Vec<OmenaQueryCrossFileSummaryEdgeV0>>> {
2103        let empty = Vec::new();
2104        let source_a = fixture_edge(
2105            "source",
2106            "/workspace/src/App.tsx",
2107            "style",
2108            "/workspace/src/A.module.scss",
2109        );
2110        let source_b = fixture_edge(
2111            "source",
2112            "/workspace/src/App.tsx",
2113            "style",
2114            "/workspace/src/B.module.scss",
2115        );
2116        let other_b = fixture_edge(
2117            "source",
2118            "/workspace/src/Other.tsx",
2119            "style",
2120            "/workspace/src/B.module.scss",
2121        );
2122        let mid_a = fixture_edge(
2123            "style",
2124            "/workspace/src/Mid.module.scss",
2125            "style",
2126            "/workspace/src/A.module.scss",
2127        );
2128        let source_mid = fixture_edge(
2129            "source",
2130            "/workspace/src/App.tsx",
2131            "style",
2132            "/workspace/src/Mid.module.scss",
2133        );
2134        let leaf_mid = fixture_edge(
2135            "style",
2136            "/workspace/src/Leaf.module.scss",
2137            "style",
2138            "/workspace/src/Mid.module.scss",
2139        );
2140        let source_leaf = fixture_edge(
2141            "source",
2142            "/workspace/src/Deep.tsx",
2143            "style",
2144            "/workspace/src/Leaf.module.scss",
2145        );
2146        let value_a = fixture_edge(
2147            "style",
2148            "/workspace/src/Value.module.scss",
2149            "style",
2150            "/workspace/src/A.module.scss",
2151        );
2152
2153        vec![
2154            vec![
2155                empty.clone(),
2156                vec![source_a.clone()],
2157                vec![source_a.clone(), other_b.clone()],
2158            ],
2159            vec![
2160                vec![source_a.clone()],
2161                vec![source_b.clone()],
2162                vec![source_b.clone(), other_b.clone()],
2163            ],
2164            vec![
2165                vec![source_a.clone(), other_b.clone()],
2166                vec![other_b.clone()],
2167                vec![source_a.clone(), other_b.clone()],
2168            ],
2169            vec![
2170                vec![mid_a.clone()],
2171                vec![mid_a.clone(), source_mid.clone()],
2172                vec![source_mid.clone()],
2173            ],
2174            vec![
2175                vec![mid_a.clone(), source_mid.clone()],
2176                vec![mid_a.clone(), source_mid.clone(), leaf_mid.clone()],
2177                vec![leaf_mid.clone(), source_leaf.clone()],
2178            ],
2179            vec![
2180                vec![source_leaf.clone()],
2181                vec![source_leaf.clone(), value_a.clone()],
2182                vec![value_a.clone()],
2183            ],
2184            vec![
2185                empty.clone(),
2186                vec![source_b.clone(), other_b.clone()],
2187                vec![source_a.clone(), other_b.clone()],
2188            ],
2189            vec![vec![value_a.clone()], empty.clone(), vec![value_a.clone()]],
2190            vec![
2191                vec![leaf_mid.clone()],
2192                vec![leaf_mid.clone(), source_leaf.clone()],
2193                vec![source_leaf.clone()],
2194            ],
2195            vec![
2196                vec![source_mid.clone(), source_leaf.clone()],
2197                vec![source_mid.clone()],
2198                vec![source_mid.clone(), source_leaf.clone()],
2199            ],
2200            vec![
2201                vec![mid_a.clone(), value_a.clone()],
2202                vec![value_a.clone()],
2203                vec![mid_a.clone(), value_a.clone()],
2204            ],
2205            vec![
2206                vec![source_a.clone()],
2207                vec![source_a.clone(), mid_a.clone()],
2208                vec![mid_a, source_mid],
2209            ],
2210        ]
2211    }
2212
2213    fn sequence_has_add_and_remove_for_same_origin(
2214        sequence: &[Vec<OmenaQueryCrossFileSummaryEdgeV0>],
2215    ) -> bool {
2216        sequence.windows(3).any(|window| {
2217            let first = reverse_dependency_groups_by_from_path(window[0].as_slice());
2218            let second = reverse_dependency_groups_by_from_path(window[1].as_slice());
2219            let third = reverse_dependency_groups_by_from_path(window[2].as_slice());
2220            first.keys().any(|from_path| {
2221                let first_targets = first.get(from_path).cloned().unwrap_or_default();
2222                let second_targets = second.get(from_path).cloned().unwrap_or_default();
2223                let third_targets = third.get(from_path).cloned().unwrap_or_default();
2224                first_targets != second_targets
2225                    && first_targets == third_targets
2226                    && !first_targets.is_empty()
2227            })
2228        })
2229    }
2230
2231    fn fixture_edge(
2232        from_kind: &'static str,
2233        from_path: &str,
2234        target_kind: &'static str,
2235        target_path: &str,
2236    ) -> OmenaQueryCrossFileSummaryEdgeV0 {
2237        fixture_edge_with_kind(
2238            "fixtureDependency",
2239            from_kind,
2240            from_path,
2241            target_kind,
2242            target_path,
2243        )
2244    }
2245
2246    fn fixture_edge_with_kind(
2247        edge_kind: &'static str,
2248        from_kind: &'static str,
2249        from_path: &str,
2250        target_kind: &'static str,
2251        target_path: &str,
2252    ) -> OmenaQueryCrossFileSummaryEdgeV0 {
2253        OmenaQueryCrossFileSummaryEdgeV0 {
2254            edge_id: format!("{from_kind}:{from_path}->{target_kind}:{target_path}"),
2255            edge_kind,
2256            from_kind,
2257            from_path: from_path.to_string(),
2258            target_kind: Some(target_kind),
2259            target_path: Some(target_path.to_string()),
2260            source: None,
2261            owner_selector_name: None,
2262            local_name: None,
2263            remote_name: None,
2264            target_names: Vec::new(),
2265            status: "resolved",
2266            provenance: vec!["omena-query.cross-file-summary.fixture"],
2267            linear_provenance: OmenaCrossFileLinearProvenanceV0::from_static_labels(&[
2268                "omena-query.cross-file-summary.fixture",
2269            ]),
2270        }
2271    }
2272
2273    fn summary_from_edges(
2274        edges: Vec<OmenaQueryCrossFileSummaryEdgeV0>,
2275    ) -> OmenaQueryCrossFileSummaryV0 {
2276        OmenaQueryCrossFileSummaryV0 {
2277            schema_version: "0",
2278            product: "omena-query.cross-file-summary",
2279            status: "fixtureSummary",
2280            summary_scope: "workspaceStyleAndSource",
2281            style_count: 1,
2282            summary_edge_count: edges.len(),
2283            edge_kind_counts: recompute_cross_file_summary_raw_edge_kind_counts_v0(
2284                edges.as_slice(),
2285            ),
2286            summary_hash: stable_omena_query_cross_file_summary_hash(edges.as_slice()),
2287            edges,
2288            capabilities: OmenaQueryCrossFileSummaryCapabilitiesV0 {
2289                css_modules_composes_edges_ready: true,
2290                css_modules_value_edges_ready: true,
2291                css_modules_icss_edges_ready: true,
2292                sass_module_edges_ready: true,
2293                style_design_token_reference_edges_ready: true,
2294                source_selector_reference_edges_ready: true,
2295                stable_summary_hash_ready: true,
2296                linear_provenance_ready: true,
2297                linear_provenance_round_trip_ready: true,
2298                linear_provenance_semiring_laws_hold: true,
2299            },
2300            next_priorities: Vec::new(),
2301        }
2302    }
2303
2304    fn reverse_dependency_index_fingerprint(index: &ReverseDependencyIndexV0) -> String {
2305        let mut parts = Vec::new();
2306        for (target, dependents) in &index.rev {
2307            parts.push(format!(
2308                "rev:{target}={}",
2309                dependents.iter().cloned().collect::<Vec<_>>().join(",")
2310            ));
2311        }
2312        for (from_path, targets) in &index.edges_by_from {
2313            parts.push(format!(
2314                "from:{from_path}={}",
2315                targets.iter().cloned().collect::<Vec<_>>().join(",")
2316            ));
2317        }
2318        parts.join("|")
2319    }
2320}
omena_cross_file_summary/lib.rs

omena_cross_file_summary/
lib.rs
