lace_sans_io/logic/
exchange_plan.rs

1//! Deterministic 040 exchange-plan compilation and local lowering.
2//!
3//! The runtime executes a flat lowered 030 program internally, while its
4//! construction surface is the current 040 exchange-plan route:
5//! two faceted interlace-module operands are assigned fixed `side0`/`side1` origins,
6//! compiled to a canonical exchange-plan transcript and identifier, then
7//! lowered to a local executable policy artifact. The transcript is derived
8//! locally and is not a transferred resource.
9
10use std::collections::BTreeSet;
11
12use super::AdvertisementFieldRequirements;
13use super::dependency_graph::DependencyGraph;
14use super::exposure_view::ExposureView;
15use super::limits::DatalogLimits;
16use super::policy_source::{scope_policy_rules, scoped_facet_name};
17use super::profile::{
18    ADVERTISED, ADVERTISED_FIELD, EXPOSE_RECORD, GENERATED_MAY_REQUEST, GENERATED_MAY_SEND, HAVE,
19    RX_DISABLED, SELECT_ADVERTISED_CANDIDATE, SELECT_STORED_RECORD, TX_DISABLED,
20};
21use crate::lacegram::{CanonicalLacegram, canonicalize_lacegram_source, prepare_lacegram_rules};
22use crate::records::{RecordHash, blob::blob_hash};
23use crate::types::{BodyAtom, Lacegram, Predicate, Rule, Symbol, Term};
24
25#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
26pub enum ExchangePlanSlot {
27    Slot0,
28    Slot1,
29}
30
31impl ExchangePlanSlot {
32    pub const fn index(self) -> usize {
33        match self {
34            Self::Slot0 => 0,
35            Self::Slot1 => 1,
36        }
37    }
38    pub const fn other(self) -> Self {
39        match self {
40            Self::Slot0 => Self::Slot1,
41            Self::Slot1 => Self::Slot0,
42        }
43    }
44}
45
46/// Opaque immutable result of compiling exactly two ordered modules.
47#[derive(Clone, Debug)]
48pub struct ExchangePlan {
49    modules: [crate::logic::InterlaceModule; 2],
50    advertisement_fields: AdvertisementFieldRequirements,
51}
52
53impl ExchangePlan {
54    pub fn id(&self) -> RecordHash {
55        exchange_plan_id(&self.transcript())
56    }
57    pub fn transcript(&self) -> String {
58        let fields = self.advertisement_fields.fields.iter().cloned().collect();
59        serialize_exchange_plan_transcript(
60            &self.modules,
61            self.advertisement_fields.require_all,
62            &fields,
63        )
64    }
65    pub fn advertisement_field_requirements(&self) -> &AdvertisementFieldRequirements {
66        &self.advertisement_fields
67    }
68    pub(crate) fn operand(&self, slot: ExchangePlanSlot) -> &crate::logic::InterlaceModule {
69        &self.modules[slot.index()]
70    }
71    /// Whether lowering omits `slot`'s `MaySend` output, so that side's
72    /// listing is empty in every round: an operand defines no
73    /// `SelectStoredRecord/1`, or that side's `TxDisabled` or the other
74    /// side's `RxDisabled` has a rule whose body is `true`.
75    pub(crate) fn never_sends(&self, slot: ExchangePlanSlot) -> bool {
76        output_omitted(
77            self,
78            SELECT_STORED_RECORD.name,
79            [
80                (slot.index(), TX_DISABLED.name),
81                (slot.other().index(), RX_DISABLED.name),
82            ],
83        )
84    }
85}
86
87/// Canonicalize ordinary Datalog source to 030 lacegram text.
88pub fn canonicalize_lacegram_text(text: &str, limits: DatalogLimits) -> Result<String, String> {
89    canonicalize_lacegram_source(text, limits)
90        .map(|canonical| canonical.text)
91        .map_err(Into::into)
92}
93
94/// Compute the Blob record hash for canonical lacegram text.
95pub fn lacegram_resource_hash(canonical_text: &str) -> RecordHash {
96    blob_resource_hash(canonical_text)
97}
98
99/// Compute the Blob record hash for one canonical text resource.
100pub fn blob_resource_hash(canonical_text: &str) -> RecordHash {
101    blob_hash(canonical_text.as_bytes())
102}
103
104pub fn compile_exchange_plan(modules: [crate::logic::InterlaceModule; 2]) -> ExchangePlan {
105    let (require_all, fields) = infer_advertisement_requirements(&modules);
106    ExchangePlan {
107        modules,
108        advertisement_fields: AdvertisementFieldRequirements {
109            require_all,
110            fields: fields.into_iter().collect(),
111        },
112    }
113}
114
115fn serialize_exchange_plan_transcript(
116    modules: &[crate::logic::InterlaceModule; 2],
117    require_all_advertisement_fields: bool,
118    required_advertisement_fields: &BTreeSet<String>,
119) -> String {
120    let mut lines = vec!["ExchangePlanProfile('lace-040-exchange-plan-v13')".to_string()];
121    for (index, module) in modules.iter().enumerate() {
122        lines.push(format!(
123            "ExchangePlanOperand('{}','{}')",
124            index,
125            esc(module.id().as_str())
126        ));
127    }
128    if require_all_advertisement_fields {
129        lines.push("ExchangePlanRequireAllAdvertisedFields()".into());
130    } else {
131        for field in required_advertisement_fields {
132            lines.push(format!(
133                "ExchangePlanRequireAdvertisedField('{}')",
134                esc(field)
135            ));
136        }
137    }
138    lines[1..].sort();
139    lines.join("\n")
140}
141
142/// One side's lowered local executable.
143///
144/// The local operand keeps ordinary 020 record fact predicates, while the peer
145/// operand reads generated scoped wrappers constrained by the local operand's
146/// `ExposeRecord/1` facet. The generated send and request outputs keep
147/// exposure policy above the store boundary.
148#[derive(Debug, Clone)]
149pub struct LocalExecutablePolicy {
150    canonical: CanonicalLacegram,
151}
152
153impl LocalExecutablePolicy {
154    /// A program evaluated entirely in the local view, with no peer operand.
155    pub(crate) fn local(canonical: CanonicalLacegram) -> Self {
156        Self { canonical }
157    }
158
159    pub(crate) fn program(&self) -> &Lacegram {
160        &self.canonical.program
161    }
162}
163
164/// Lower an exchange plan to the local executable for one slot.
165pub fn lower_exchange_plan_for_local_side(
166    plan: &ExchangePlan,
167    local_slot: ExchangePlanSlot,
168) -> Result<LocalExecutablePolicy, String> {
169    let local_index = local_slot.index();
170    let peer_index = 1 - local_index;
171    let local_scope = format!("op{local_index}_");
172    let mut output_rules = Vec::new();
173    if !facet_is_defined(plan.modules[local_index].program(), EXPOSE_RECORD.name, 1) {
174        // An absent facet is empty. Its scoped helper still needs a definition;
175        // positive self-recursion has an empty least fixed point without IO.
176        let expose = Symbol::from(scoped_facet_name(&local_scope, EXPOSE_RECORD.name));
177        output_rules.push(Rule {
178            head_predicate: expose.clone(),
179            head_terms: vec![Term::var("Record")],
180            body: vec![BodyAtom::Positive {
181                predicate: expose,
182                terms: vec![Term::var("Record")],
183            }],
184        });
185    }
186    let local_exposure = scoped_facet_name(&local_scope, EXPOSE_RECORD.name);
187    for (index, module) in plan.modules.iter().enumerate() {
188        let scope = format!("op{index}_");
189        let rules = scope_policy_rules(module, &scope);
190        output_rules.extend(if index == local_index {
191            rules
192        } else {
193            ExposureView {
194                gate: &local_exposure,
195                prefix: &scope,
196                specialize: true,
197            }
198            .confine(rules)?
199        });
200    }
201    output_rules.extend(merged_output(
202        plan,
203        SELECT_STORED_RECORD.name,
204        GENERATED_MAY_SEND,
205        vec![BodyAtom::Positive {
206            predicate: local_exposure.clone().into(),
207            terms: vec![Term::var("Record")],
208        }],
209        [
210            (local_index, TX_DISABLED.name),
211            (peer_index, RX_DISABLED.name),
212        ],
213    ));
214    output_rules.extend(merged_output(
215        plan,
216        SELECT_ADVERTISED_CANDIDATE.name,
217        GENERATED_MAY_REQUEST,
218        vec![
219            BodyAtom::Positive {
220                predicate: ADVERTISED.name.into(),
221                terms: vec![Term::var("Record")],
222            },
223            BodyAtom::Negated {
224                predicate: HAVE.name.into(),
225                terms: vec![Term::var("Record")],
226            },
227        ],
228        [
229            (peer_index, TX_DISABLED.name),
230            (local_index, RX_DISABLED.name),
231        ],
232    ));
233    Ok(LocalExecutablePolicy {
234        canonical: prepare_lacegram_rules(output_rules, DatalogLimits::for_generated_rules())?,
235    })
236}
237
238/// Canonical text of one side's lowered local executable.
239pub fn compile_local_executable_policy(
240    plan: &ExchangePlan,
241    local_slot: ExchangePlanSlot,
242) -> Result<String, String> {
243    lower_exchange_plan_for_local_side(plan, local_slot).map(|policy| policy.canonical.text)
244}
245
246/// Intersect both operands' facet and the gates directly into the output.
247/// A statically true veto omits the output, so its evaluation is empty.
248fn merged_output(
249    plan: &ExchangePlan,
250    facet: &str,
251    output: &str,
252    gates: Vec<BodyAtom>,
253    vetoes: [(usize, &str); 2],
254) -> Vec<Rule> {
255    if output_omitted(plan, facet, vetoes) {
256        return Vec::new();
257    }
258    let record = || vec![Term::var("Record")];
259    let scoped = |index: usize, facet: &str| scoped_facet_name(&format!("op{index}_"), facet);
260    let vetoes = vetoes.map(|(index, veto)| {
261        (
262            index,
263            veto,
264            facet_state(plan.modules[index].program(), veto),
265        )
266    });
267    let mut body = (0..2)
268        .map(|index| BodyAtom::Positive {
269            predicate: scoped(index, facet).into(),
270            terms: record(),
271        })
272        .collect::<Vec<_>>();
273    body.extend(gates);
274    body.extend(
275        vetoes
276            .into_iter()
277            .filter(|(_, _, state)| *state == FacetState::Dynamic)
278            .map(|(index, veto, _)| BodyAtom::Negated {
279                predicate: scoped(index, veto).into(),
280                terms: Vec::new(),
281            }),
282    );
283    vec![Rule {
284        head_predicate: output.into(),
285        head_terms: record(),
286        body,
287    }]
288}
289
290/// An output is omitted when an operand leaves its facet undefined or one of
291/// its vetoes is statically true.
292fn output_omitted(plan: &ExchangePlan, facet: &str, vetoes: [(usize, &str); 2]) -> bool {
293    !plan
294        .modules
295        .iter()
296        .all(|module| facet_is_defined(module.program(), facet, 1))
297        || vetoes.iter().any(|(index, veto)| {
298            facet_state(plan.modules[*index].program(), veto) == FacetState::Always
299        })
300}
301
302fn facet_is_defined(program: &Lacegram, facet: &str, arity: usize) -> bool {
303    program
304        .strata
305        .iter()
306        .flatten()
307        .any(|rule| rule.head_predicate == facet && rule.head_terms.len() == arity)
308}
309
310#[derive(Clone, Copy, PartialEq, Eq)]
311enum FacetState {
312    Absent,
313    Always,
314    Dynamic,
315}
316
317fn facet_state(program: &Lacegram, facet: &str) -> FacetState {
318    let mut found = false;
319    for rule in program
320        .strata
321        .iter()
322        .flatten()
323        .filter(|rule| rule.head_predicate == facet && rule.head_terms.is_empty())
324    {
325        found = true;
326        if rule.body.len() == 1 && matches!(rule.body[0], BodyAtom::True) {
327            return FacetState::Always;
328        }
329    }
330    if found {
331        FacetState::Dynamic
332    } else {
333        FacetState::Absent
334    }
335}
336
337/// Collect `AdvertisedField/4` names reachable from `SelectAdvertisedCandidate/1`;
338/// a dynamic field name requires all fields.
339fn infer_advertisement_requirements(
340    modules: &[crate::logic::InterlaceModule; 2],
341) -> (bool, BTreeSet<String>) {
342    let mut require_all = false;
343    let mut fields = BTreeSet::new();
344    for program in modules.iter().map(crate::logic::InterlaceModule::program) {
345        let rules = program.strata.iter().flatten();
346        let reachable = DependencyGraph::new(rules.clone()).reachable(&[Predicate::new(
347            SELECT_ADVERTISED_CANDIDATE.name,
348            SELECT_ADVERTISED_CANDIDATE.arity(),
349        )]);
350        for rule in rules.filter(|rule| {
351            reachable.contains(&Predicate::new(&rule.head_predicate, rule.head_terms.len()))
352        }) {
353            for (predicate, terms, _) in rule.body.iter().filter_map(BodyAtom::relation) {
354                if predicate == ADVERTISED_FIELD.name && terms.len() == ADVERTISED_FIELD.arity() {
355                    match &terms[1] {
356                        Term::Const(name) => {
357                            fields.insert(name.to_string());
358                        }
359                        _ => require_all = true,
360                    }
361                }
362            }
363        }
364    }
365    (require_all, fields)
366}
367
368fn exchange_plan_id(transcript: &str) -> RecordHash {
369    blob_resource_hash(transcript)
370}
371
372fn esc(s: &str) -> String {
373    s.replace('\\', "\\\\").replace('\'', "\\'")
374}
375
376#[cfg(test)]
377mod structured_lowering_tests;
378
379#[cfg(test)]
380mod side_origin_tests {
381    use super::*;
382
383    const MODULE: &str = "ExposeRecord(P) :- Have(P).\nSelectAdvertisedCandidate(P) :- Advertised(P).\nSelectStoredRecord(P) :- Have(P).";
384
385    fn compile_plan(op0: &str, op1: &str) -> ExchangePlan {
386        compile_exchange_plan([
387            crate::logic::InterlaceModule::from_text(op0).unwrap(),
388            crate::logic::InterlaceModule::from_text(op1).unwrap(),
389        ])
390    }
391
392    #[test]
393    fn compiled_plan_has_minimal_slot_tagged_transcript() {
394        let plan = compile_plan(MODULE, MODULE);
395        let transcript = plan.transcript();
396        let lines = transcript.lines().collect::<Vec<_>>();
397        assert_eq!(lines.len(), 3);
398        assert_eq!(
399            lines[0],
400            "ExchangePlanProfile('lace-040-exchange-plan-v13')"
401        );
402        assert!(lines[1].starts_with("ExchangePlanOperand('0','B."));
403        assert!(lines[2].starts_with("ExchangePlanOperand('1','B."));
404        let module_id = crate::logic::InterlaceModule::from_text(MODULE)
405            .unwrap()
406            .lacegram_resource_hash();
407        assert!(lines[1].contains(module_id.as_str()));
408        assert_eq!(
409            plan.id().as_str(),
410            "B.QCb2mW8gaK7_Lop2VzKMQ3HVBMA2N8lQbjCl982dWu8.H3"
411        );
412    }
413
414    #[test]
415    fn canonical_v13_plan_vector_matches_the_specification() {
416        let module = "ExposeRecord(Record) :- Have(Record), Field(Record,'App',_,'chat').\nSelectAdvertisedCandidate(Record) :- Advertised(Record), AdvertisedField(Record,'App',_,'chat').\nSelectStoredRecord(Record) :- Have(Record), Field(Record,'App',_,'chat').";
417        let operand = crate::logic::InterlaceModule::from_text(module).unwrap();
418        assert_eq!(
419            operand.id().as_str(),
420            "B.iqoRCCeq_CgxobqVC0gYoCBIUKbq3P~7mHmopRj6mBO.H3"
421        );
422        let plan = compile_exchange_plan([operand.clone(), operand]);
423        assert_eq!(plan.transcript().len(), 243);
424        assert_eq!(
425            plan.transcript(),
426            "ExchangePlanProfile('lace-040-exchange-plan-v13')\nExchangePlanOperand('0','B.iqoRCCeq_CgxobqVC0gYoCBIUKbq3P~7mHmopRj6mBO.H3')\nExchangePlanOperand('1','B.iqoRCCeq_CgxobqVC0gYoCBIUKbq3P~7mHmopRj6mBO.H3')\nExchangePlanRequireAdvertisedField('App')"
427        );
428        assert_eq!(
429            plan.id().as_str(),
430            "B.B_HirqJFeSbm26gMM96xw8LaV6Sk3qXXtt1pOnSMSmd.H3"
431        );
432    }
433
434    #[test]
435    fn advertisement_schema_recognizes_static_by_and_dynamic_all_fields() {
436        let static_by =
437            "SelectAdvertisedCandidate(P) :- Advertised(P), AdvertisedField(P,'By',_,by_value).";
438        let plan = compile_plan(static_by, static_by);
439        assert!(!plan.advertisement_field_requirements().require_all);
440        assert_eq!(plan.advertisement_field_requirements().fields, vec!["By"]);
441        assert!(
442            plan.transcript()
443                .contains("ExchangePlanRequireAdvertisedField('By')")
444        );
445
446        let dynamic =
447            "SelectAdvertisedCandidate(P) :- Advertised(P), AdvertisedField(P,name,_,value).";
448        let plan = compile_plan(dynamic, dynamic);
449        assert!(plan.advertisement_field_requirements().require_all);
450        assert!(
451            plan.transcript()
452                .contains("ExchangePlanRequireAllAdvertisedFields()")
453        );
454    }
455
456    #[test]
457    fn lowering_preserves_peer_exposure_view() {
458        let peer = "selected(P) :- Have(P), Field(P,'Topic',_,'secret').\nSelectAdvertisedCandidate(P) :- Advertised(P).\nSelectStoredRecord(P) :- selected(P).";
459        let local = "ExposeRecord(P) :- Have(P), Field(P,'Topic',_,'public').\nSelectAdvertisedCandidate(P) :- Advertised(P).\nSelectStoredRecord(P) :- Have(P).";
460        let plan = compile_plan(local, peer);
461        let lowered = compile_local_executable_policy(&plan, ExchangePlanSlot::Slot0).unwrap();
462        assert!(lowered.contains("op1_exposed_have(P)"));
463        assert!(lowered.contains("op1_exposed_field(P,'Topic',_,'secret')"));
464        assert_eq!(
465            rules_with_head(&lowered, "op1_exposed_field("),
466            [
467                "op1_exposed_field(Record,'Topic',index,'secret') :- Field(Record,'Topic',index,'secret'), op0_facet_exposerecord(Record)."
468            ],
469            "{lowered}"
470        );
471    }
472
473    #[test]
474    fn peer_admission_order_comparison_gates_both_records() {
475        let peer = "later(Later,Earlier) :- Have(Later), Have(Earlier), Compare(AdmitOrder(Later),'>',AdmitOrder(Earlier)).\nSelectAdvertisedCandidate(P) :- Advertised(P).\nSelectStoredRecord(P) :- Have(P), later(P,Earlier).";
476        let local = "ExposeRecord(P) :- Have(P).\nSelectAdvertisedCandidate(P) :- Advertised(P).\nSelectStoredRecord(P) :- Have(P).";
477        let plan = compile_plan(local, peer);
478        let lowered = compile_local_executable_policy(&plan, ExchangePlanSlot::Slot0).unwrap();
479        assert!(lowered.contains("Compare(AdmitOrder(Later),'>',AdmitOrder(Earlier)), op0_facet_exposerecord(Earlier), op0_facet_exposerecord(Later)"), "{lowered}");
480    }
481
482    #[test]
483    fn disabled_facets_lower_slot_relative_and_static_veto_removes_output() {
484        let dynamic = format!("{MODULE}\nTxDisabled() :- Have(P), Field(P,'Label',_,'pause').");
485        let plan = compile_plan(&dynamic, MODULE);
486        let side0 = compile_local_executable_policy(&plan, ExchangePlanSlot::Slot0).unwrap();
487        let side1 = compile_local_executable_policy(&plan, ExchangePlanSlot::Slot1).unwrap();
488        assert!(
489            side0.contains(
490                "lace_may_send(Record) :- op0_facet_selectstoredrecord(Record), op1_facet_selectstoredrecord(Record), op0_facet_exposerecord(Record), not op0_facet_txdisabled()."
491            ),
492            "{side0}"
493        );
494        assert!(side1.contains("lace_may_request(Record) :- op0_facet_selectadvertisedcandidate(Record), op1_facet_selectadvertisedcandidate(Record), Advertised(Record), not Have(Record), not op0_facet_txdisabled()."), "{side1}");
495
496        assert!(!plan.never_sends(ExchangePlanSlot::Slot0));
497        assert!(!plan.never_sends(ExchangePlanSlot::Slot1));
498
499        let static_veto = format!("{MODULE}\nRxDisabled() :- true.");
500        let plan = compile_plan(&static_veto, MODULE);
501        let side0 = compile_local_executable_policy(&plan, ExchangePlanSlot::Slot0).unwrap();
502        assert_eq!(
503            rules_with_head(&side0, "lace_"),
504            [
505                "lace_may_send(Record) :- op0_facet_selectstoredrecord(Record), op1_facet_selectstoredrecord(Record), op0_facet_exposerecord(Record)."
506            ],
507            "{side0}"
508        );
509        // Slot0 receives nothing, so slot1's listing is always empty.
510        assert!(plan.never_sends(ExchangePlanSlot::Slot1));
511        assert!(!plan.never_sends(ExchangePlanSlot::Slot0));
512        let static_tx = format!("{MODULE}\nTxDisabled() :- true.");
513        let plan = compile_plan(MODULE, &static_tx);
514        assert!(plan.never_sends(ExchangePlanSlot::Slot1));
515        assert!(!plan.never_sends(ExchangePlanSlot::Slot0));
516    }
517
518    /// The rules of `text` whose head starts with `prefix`.
519    fn rules_with_head<'a>(text: &'a str, prefix: &str) -> Vec<&'a str> {
520        text.lines()
521            .filter(|line| line.starts_with(prefix))
522            .collect()
523    }
524}
lace_sans_io/logic/exchange_plan.rs

lace_sans_io/logic/
exchange_plan.rs
