presolve_compiler/
production_deduplication.rs

1//! K4 canonical generated-program fingerprinting and safe alias projection.
2
3use std::collections::BTreeMap;
4
5use crate::ExecutableProgramFingerprint;
6
7#[derive(Clone, Debug, Eq, PartialEq)]
8pub struct ExecutableProgramCanonicalStream {
9    pub semantic_program_id: String,
10    pub bytes: Vec<u8>,
11}
12#[derive(Clone, Debug, Eq, PartialEq)]
13pub struct ExecutableProgramCandidate {
14    pub semantic_program_id: String,
15    pub program_kind: String,
16    pub opcode_stream: Vec<String>,
17    pub required_protocol: String,
18    pub instance_owned_identity: Option<String>,
19    pub schedule_identity: Option<String>,
20    pub native_default_policy: Option<String>,
21    pub stable_failure_identity: Option<String>,
22}
23#[derive(Clone, Debug, Eq, PartialEq)]
24pub struct ExecutableProgramFingerprintRegistry {
25    pub streams: Vec<ExecutableProgramCanonicalStream>,
26    pub fingerprints: Vec<ExecutableProgramFingerprint>,
27}
28#[derive(Clone, Debug, Eq, PartialEq)]
29pub struct ProgramAliasRecord {
30    pub semantic_program_id: String,
31    pub implementation_program_id: String,
32}
33#[derive(Clone, Debug, Eq, PartialEq)]
34pub struct DeduplicatedProgramRegistry {
35    pub implementations: Vec<String>,
36    pub aliases: Vec<ProgramAliasRecord>,
37}
38#[derive(Clone, Debug, Eq, PartialEq)]
39pub struct ProgramDeduplicationReport {
40    pub aliases: Vec<ProgramAliasRecord>,
41    pub rejected_program_ids: Vec<String>,
42}
43
44#[must_use]
45pub fn deduplicate_generated_programs(
46    candidates: &[ExecutableProgramCandidate],
47) -> (
48    ExecutableProgramFingerprintRegistry,
49    DeduplicatedProgramRegistry,
50    ProgramDeduplicationReport,
51) {
52    deduplicate_with(candidates, |stream| {
53        ExecutableProgramFingerprint::for_canonical_opcode_stream(stream)
54    })
55}
56
57fn deduplicate_with<F>(
58    candidates: &[ExecutableProgramCandidate],
59    fingerprint: F,
60) -> (
61    ExecutableProgramFingerprintRegistry,
62    DeduplicatedProgramRegistry,
63    ProgramDeduplicationReport,
64)
65where
66    F: Fn(&[u8]) -> ExecutableProgramFingerprint,
67{
68    let mut candidates = candidates.to_vec();
69    candidates.sort_by(|a, b| a.semantic_program_id.cmp(&b.semantic_program_id));
70    let streams = candidates.iter().map(canonical_stream).collect::<Vec<_>>();
71    let fingerprints = streams
72        .iter()
73        .map(|stream| fingerprint(&stream.bytes))
74        .collect::<Vec<_>>();
75    let mut canonical = BTreeMap::<
76        ExecutableProgramFingerprint,
77        Vec<(ExecutableProgramCanonicalStream, bool)>,
78    >::new();
79    for (stream, candidate) in streams.iter().cloned().zip(candidates.iter()) {
80        canonical
81            .entry(fingerprint(&stream.bytes))
82            .or_default()
83            .push((stream, safe(candidate)));
84    }
85    let mut implementations = Vec::new();
86    let mut aliases = Vec::new();
87    let mut rejected = Vec::new();
88    for entries in canonical.values() {
89        let representative = &entries[0].0;
90        implementations.push(representative.semantic_program_id.clone());
91        for (stream, permitted) in entries.iter().skip(1) {
92            if *permitted && stream.bytes == representative.bytes {
93                aliases.push(ProgramAliasRecord {
94                    semantic_program_id: stream.semantic_program_id.clone(),
95                    implementation_program_id: representative.semantic_program_id.clone(),
96                });
97            } else {
98                rejected.push(stream.semantic_program_id.clone());
99                implementations.push(stream.semantic_program_id.clone());
100            }
101        }
102    }
103    implementations.sort();
104    implementations.dedup();
105    aliases.sort_by(|a, b| a.semantic_program_id.cmp(&b.semantic_program_id));
106    rejected.sort();
107    (
108        ExecutableProgramFingerprintRegistry {
109            streams,
110            fingerprints,
111        },
112        DeduplicatedProgramRegistry {
113            implementations,
114            aliases: aliases.clone(),
115        },
116        ProgramDeduplicationReport {
117            aliases,
118            rejected_program_ids: rejected,
119        },
120    )
121}
122
123fn canonical_stream(candidate: &ExecutableProgramCandidate) -> ExecutableProgramCanonicalStream {
124    let bytes = format!(
125        "kind:{}\nprotocol:{}\nopcodes:{}\ninstance:{}\nschedule:{}\nnative-default:{}\nfailure:{}",
126        candidate.program_kind,
127        candidate.required_protocol,
128        candidate.opcode_stream.join("\n"),
129        candidate.instance_owned_identity.as_deref().unwrap_or(""),
130        candidate.schedule_identity.as_deref().unwrap_or(""),
131        candidate.native_default_policy.as_deref().unwrap_or(""),
132        candidate.stable_failure_identity.as_deref().unwrap_or("")
133    )
134    .into_bytes();
135    ExecutableProgramCanonicalStream {
136        semantic_program_id: candidate.semantic_program_id.clone(),
137        bytes,
138    }
139}
140fn safe(candidate: &ExecutableProgramCandidate) -> bool {
141    candidate.instance_owned_identity.is_none()
142        && candidate.schedule_identity.is_none()
143        && candidate.native_default_policy.is_none()
144        && candidate.stable_failure_identity.is_none()
145}
146
147#[cfg(test)]
148mod tests {
149    use super::{deduplicate_generated_programs, deduplicate_with, ExecutableProgramCandidate};
150    use crate::ExecutableProgramFingerprint;
151    #[test]
152    fn k4_deduplicates_only_identical_stateless_programs_and_rejects_boundaries() {
153        let base = |id: &str| ExecutableProgramCandidate {
154            semantic_program_id: id.to_string(),
155            program_kind: "kernel".to_string(),
156            opcode_stream: vec!["return".to_string()],
157            required_protocol: "v1".to_string(),
158            instance_owned_identity: None,
159            schedule_identity: None,
160            native_default_policy: None,
161            stable_failure_identity: None,
162        };
163        let mut slot = base("slot");
164        slot.instance_owned_identity = Some("slot:a".to_string());
165        let mut event = base("event");
166        event.native_default_policy = Some("prevent".to_string());
167        let mut schedule = base("schedule");
168        schedule.schedule_identity = Some("first".to_string());
169        let (_, registry, report) =
170            deduplicate_generated_programs(&[base("b"), base("a"), slot, event, schedule]);
171        assert_eq!(registry.aliases[0].semantic_program_id, "b");
172        assert_eq!(registry.aliases[0].implementation_program_id, "a");
173        assert!(report.rejected_program_ids.is_empty());
174    }
175    #[test]
176    fn k4_collision_hook_requires_byte_equality() {
177        let candidate = |id: &str, opcode: &str| ExecutableProgramCandidate {
178            semantic_program_id: id.to_string(),
179            program_kind: "kernel".to_string(),
180            opcode_stream: vec![opcode.to_string()],
181            required_protocol: "v1".to_string(),
182            instance_owned_identity: None,
183            schedule_identity: None,
184            native_default_policy: None,
185            stable_failure_identity: None,
186        };
187        let (_, registry, report) =
188            deduplicate_with(&[candidate("a", "one"), candidate("b", "two")], |_| {
189                ExecutableProgramFingerprint::for_canonical_opcode_stream(b"collision")
190            });
191        assert!(registry.aliases.is_empty());
192        assert_eq!(report.rejected_program_ids, vec!["b"]);
193    }
194}
presolve_compiler/production_deduplication.rs

presolve_compiler/
production_deduplication.rs
