Skip to main content

logicaffeine_language/semantics/
knowledge_graph.rs

1//! Knowledge Graph extraction for hardware verification.
2//!
3//! Extracts a structured Knowledge Graph from parsed hardware specifications,
4//! providing LLMs with formally grounded context for SVA generation.
5//!
6//! ## Ontology (Sprint 0E)
7//!
8//! The formal hardware ontology provides 28+ entity types and 24+ relation types,
9//! replacing AssertionForge's 35 LLM-prompt labels and 59 string labels with
10//! formally grounded, parameterized, serializable types.
11
12use serde::{Deserialize, Serialize};
13
14// ═══════════════════════════════════════════════════════════════════════════
15// HELPER ENUMS FOR ENTITY PARAMETERS
16// ═══════════════════════════════════════════════════════════════════════════
17
18#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
19pub enum PortDirection {
20    Input,
21    Output,
22    Inout,
23}
24
25#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
26pub enum SignalType {
27    Wire,
28    Reg,
29    Logic,
30}
31
32#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
33pub enum ResetPolarity {
34    ActiveHigh,
35    ActiveLow,
36}
37
38#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
39pub enum CounterDirection {
40    Up,
41    Down,
42    UpDown,
43}
44
45#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
46pub enum ArbitrationScheme {
47    RoundRobin,
48    Priority,
49    WeightedRoundRobin,
50}
51
52// ═══════════════════════════════════════════════════════════════════════════
53// FORMAL HARDWARE ONTOLOGY — 28+ ENTITY TYPES
54// ═══════════════════════════════════════════════════════════════════════════
55
56/// Formal hardware entity types with parameterized attributes.
57///
58/// 28 variants organized into 6 categories:
59/// - **Structural (8)**: Module, Port, Signal, Register, Memory, Fifo, Bus, Parameter
60/// - **Control (5)**: Fsm, Counter, Arbiter, Decoder, Mux
61/// - **Temporal (3)**: Clock, Reset, Interrupt
62/// - **Protocol (3)**: Handshake, Pipeline, Transaction
63/// - **Data (3)**: DataPath, Address, Configuration
64/// - **Property (6)**: SafetyProperty, LivenessProperty, FairnessProperty,
65///   ResponseProperty, MutexProperty, StabilityProperty
66#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
67pub enum HwEntityType {
68    // Structural (8)
69    Module {
70        name: String,
71        is_top: bool,
72    },
73    Port {
74        direction: PortDirection,
75        width: u32,
76        domain: Option<String>,
77    },
78    Signal {
79        width: u32,
80        signal_type: SignalType,
81        domain: Option<String>,
82    },
83    Register {
84        width: u32,
85        reset_value: Option<u64>,
86        clock: Option<String>,
87    },
88    Memory {
89        depth: u32,
90        width: u32,
91        ports: u8,
92    },
93    Fifo {
94        depth: u32,
95        width: u32,
96    },
97    Bus {
98        width: u32,
99        protocol: Option<String>,
100    },
101    Parameter {
102        value: String,
103    },
104
105    // Control (5)
106    Fsm {
107        states: Vec<String>,
108        initial: Option<String>,
109    },
110    Counter {
111        width: u32,
112        direction: CounterDirection,
113    },
114    Arbiter {
115        scheme: ArbitrationScheme,
116        ports: u8,
117    },
118    Decoder {
119        input_width: u32,
120        output_width: u32,
121    },
122    Mux {
123        inputs: u8,
124        select_width: u32,
125    },
126
127    // Temporal (3)
128    Clock {
129        frequency: Option<String>,
130        domain: String,
131    },
132    Reset {
133        polarity: ResetPolarity,
134        synchronous: bool,
135    },
136    Interrupt {
137        priority: Option<u8>,
138        edge_triggered: bool,
139    },
140
141    // Protocol (3)
142    Handshake {
143        valid_signal: String,
144        ready_signal: String,
145    },
146    Pipeline {
147        stages: u32,
148        stall_signal: Option<String>,
149    },
150    Transaction {
151        request: String,
152        response: String,
153    },
154
155    // Data (3)
156    DataPath {
157        width: u32,
158        signed: bool,
159    },
160    Address {
161        width: u32,
162        base: Option<u64>,
163        range: Option<u64>,
164    },
165    Configuration {
166        fields: Vec<String>,
167    },
168
169    // Property (6)
170    SafetyProperty {
171        formula: String,
172    },
173    LivenessProperty {
174        formula: String,
175    },
176    FairnessProperty {
177        formula: String,
178    },
179    ResponseProperty {
180        trigger: String,
181        response: String,
182        bound: Option<u32>,
183    },
184    MutexProperty {
185        signals: Vec<String>,
186    },
187    StabilityProperty {
188        signal: String,
189        condition: String,
190    },
191}
192
193// ═══════════════════════════════════════════════════════════════════════════
194// FORMAL HARDWARE ONTOLOGY — 24+ RELATION TYPES
195// ═══════════════════════════════════════════════════════════════════════════
196
197/// Formal hardware relation types with parameterized attributes.
198///
199/// 24 variants organized into 6 categories:
200/// - **Data Flow (5)**: Drives, DrivesRegistered, DataFlow, Reads, Writes
201/// - **Control Flow (4)**: Controls, Selects, Enables, Resets
202/// - **Temporal (5)**: Triggers, Constrains, Follows, Precedes, Preserves
203/// - **Structural (4)**: Contains, Instantiates, ConnectsTo, BelongsToDomain
204/// - **Protocol (3)**: HandshakesWith, Acknowledges, Pipelines
205/// - **Specification (3)**: MutuallyExcludes, EventuallyFollows, AssumedBy
206#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
207pub enum HwRelation {
208    // Data Flow (5)
209    Drives,
210    DrivesRegistered { clock: String },
211    DataFlow,
212    Reads,
213    Writes,
214    // Control Flow (4)
215    Controls,
216    Selects,
217    Enables,
218    Resets,
219    // Temporal (5)
220    Triggers { delay: Option<u32> },
221    Constrains,
222    Follows { min: u32, max: u32 },
223    Precedes,
224    Preserves,
225    // Structural (4)
226    Contains,
227    Instantiates,
228    ConnectsTo,
229    BelongsToDomain { domain: String },
230    // Protocol (3)
231    HandshakesWith,
232    Acknowledges,
233    Pipelines { stages: u32 },
234    // Specification (3)
235    MutuallyExcludes,
236    EventuallyFollows,
237    AssumedBy,
238}
239
240// ═══════════════════════════════════════════════════════════════════════════
241// LEGACY TYPES (kept for backward compatibility with existing KG pipeline)
242// ═══════════════════════════════════════════════════════════════════════════
243
244/// Role of a hardware signal.
245#[derive(Debug, Clone, PartialEq, Eq)]
246pub enum SignalRole {
247    Input,
248    Output,
249    Internal,
250    Clock,
251}
252
253/// A signal node in the Knowledge Graph.
254#[derive(Debug, Clone)]
255pub struct KgSignal {
256    pub name: String,
257    pub width: u32,
258    pub role: SignalRole,
259}
260
261/// A temporal property node.
262#[derive(Debug, Clone)]
263pub struct KgProperty {
264    pub name: String,
265    pub property_type: String,
266    pub operator: String,
267}
268
269/// Relation type for KG edges.
270#[derive(Debug, Clone, PartialEq, Eq)]
271pub enum KgRelation {
272    Temporal,
273    Triggers,
274    Constrains,
275    TypeOf,
276}
277
278/// An edge in the Knowledge Graph.
279#[derive(Debug, Clone)]
280pub struct KgEdge {
281    pub from: String,
282    pub to: String,
283    pub relation: KgRelation,
284    pub property: Option<String>,
285}
286
287/// Hardware Knowledge Graph — extracted from Kripke-lowered FOL.
288#[derive(Debug, Clone)]
289pub struct HwKnowledgeGraph {
290    pub signals: Vec<KgSignal>,
291    pub properties: Vec<KgProperty>,
292    pub edges: Vec<KgEdge>,
293    /// Typed entities from the formal ontology (Sprint 0E).
294    pub entities: Vec<(String, HwEntityType)>,
295    /// Typed relations from the formal ontology (Sprint 0E).
296    pub typed_edges: Vec<(String, String, HwRelation)>,
297}
298
299impl HwKnowledgeGraph {
300    pub fn new() -> Self {
301        Self {
302            signals: Vec::new(),
303            properties: Vec::new(),
304            edges: Vec::new(),
305            entities: Vec::new(),
306            typed_edges: Vec::new(),
307        }
308    }
309
310    pub fn add_entity(&mut self, name: impl Into<String>, entity: HwEntityType) {
311        self.entities.push((name.into(), entity));
312    }
313
314    pub fn add_typed_edge(
315        &mut self,
316        from: impl Into<String>,
317        to: impl Into<String>,
318        relation: HwRelation,
319    ) {
320        self.typed_edges.push((from.into(), to.into(), relation));
321    }
322
323    /// Serialize the KG to JSON for LLM consumption.
324    pub fn to_json(&self) -> String {
325        let mut out = String::from("{\n");
326
327        // Signals
328        out.push_str("  \"signals\": [\n");
329        for (i, sig) in self.signals.iter().enumerate() {
330            let role = match &sig.role {
331                SignalRole::Input => "input",
332                SignalRole::Output => "output",
333                SignalRole::Internal => "internal",
334                SignalRole::Clock => "clock",
335            };
336            out.push_str(&format!(
337                "    {{\"name\": \"{}\", \"width\": {}, \"role\": \"{}\"}}",
338                sig.name, sig.width, role
339            ));
340            if i < self.signals.len() - 1 {
341                out.push(',');
342            }
343            out.push('\n');
344        }
345        out.push_str("  ],\n");
346
347        // Properties
348        out.push_str("  \"properties\": [\n");
349        for (i, prop) in self.properties.iter().enumerate() {
350            out.push_str(&format!(
351                "    {{\"name\": \"{}\", \"type\": \"{}\", \"operator\": \"{}\"}}",
352                prop.name, prop.property_type, prop.operator
353            ));
354            if i < self.properties.len() - 1 {
355                out.push(',');
356            }
357            out.push('\n');
358        }
359        out.push_str("  ],\n");
360
361        // Edges
362        out.push_str("  \"edges\": [\n");
363        for (i, edge) in self.edges.iter().enumerate() {
364            let rel = match &edge.relation {
365                KgRelation::Temporal => "temporal",
366                KgRelation::Triggers => "triggers",
367                KgRelation::Constrains => "constrains",
368                KgRelation::TypeOf => "type_of",
369            };
370            let prop = edge
371                .property
372                .as_deref()
373                .map(|p| format!(", \"property\": \"{}\"", p))
374                .unwrap_or_default();
375            out.push_str(&format!(
376                "    {{\"from\": \"{}\", \"to\": \"{}\", \"relation\": \"{}\"{}}}",
377                edge.from, edge.to, rel, prop
378            ));
379            if i < self.edges.len() - 1 {
380                out.push(',');
381            }
382            out.push('\n');
383        }
384        out.push_str("  ],\n");
385
386        // Typed entities (Sprint 0E ontology)
387        out.push_str("  \"entities\": [\n");
388        for (i, (name, entity)) in self.entities.iter().enumerate() {
389            let entity_json = serde_json::to_string(entity).unwrap_or_else(|_| "{}".to_string());
390            out.push_str(&format!(
391                "    {{\"name\": \"{}\", \"entity_type\": {}}}",
392                name, entity_json
393            ));
394            if i < self.entities.len() - 1 {
395                out.push(',');
396            }
397            out.push('\n');
398        }
399        out.push_str("  ],\n");
400
401        // Typed edges (Sprint 0E ontology)
402        out.push_str("  \"typed_edges\": [\n");
403        for (i, (from, to, rel)) in self.typed_edges.iter().enumerate() {
404            let rel_json = serde_json::to_string(rel).unwrap_or_else(|_| "{}".to_string());
405            out.push_str(&format!(
406                "    {{\"from\": \"{}\", \"to\": \"{}\", \"relation\": {}}}",
407                from, to, rel_json
408            ));
409            if i < self.typed_edges.len() - 1 {
410                out.push(',');
411            }
412            out.push('\n');
413        }
414        out.push_str("  ]\n");
415
416        out.push('}');
417        out
418    }
419
420    pub fn add_signal(&mut self, name: impl Into<String>, width: u32, role: SignalRole) {
421        self.signals.push(KgSignal {
422            name: name.into(),
423            width,
424            role,
425        });
426    }
427
428    pub fn add_property(
429        &mut self,
430        name: impl Into<String>,
431        property_type: impl Into<String>,
432        operator: impl Into<String>,
433    ) {
434        self.properties.push(KgProperty {
435            name: name.into(),
436            property_type: property_type.into(),
437            operator: operator.into(),
438        });
439    }
440
441    pub fn add_edge(
442        &mut self,
443        from: impl Into<String>,
444        to: impl Into<String>,
445        relation: KgRelation,
446        property: Option<String>,
447    ) {
448        self.edges.push(KgEdge {
449            from: from.into(),
450            to: to.into(),
451            relation,
452            property,
453        });
454    }
455}
456
457impl Default for HwKnowledgeGraph {
458    fn default() -> Self {
459        Self::new()
460    }
461}
462
463/// Extract a Knowledge Graph from a Kripke-lowered LogicExpr AST.
464///
465/// Walks the AST to identify:
466/// - Signals: predicates that appear with world arguments
467/// - Properties: temporal patterns (∀w' Accessible_Temporal → ...) → safety, (∃w' Reachable → ...) → liveness
468/// - Edges: implication between predicates → Triggers, negated conjunction → Constrains
469///
470/// Signal roles are inferred from structural position:
471/// - Antecedent-only → Input
472/// - Consequent-only → Output
473/// - Both positions → Internal
474/// - Name contains "clk"/"clock" → Clock (overrides position)
475pub fn extract_from_kripke_ast<'a>(
476    expr: &'a crate::ast::logic::LogicExpr<'a>,
477    interner: &crate::Interner,
478) -> HwKnowledgeGraph {
479    use crate::ast::logic::{LogicExpr, QuantifierKind};
480    use std::collections::HashSet;
481
482    let mut kg = HwKnowledgeGraph::new();
483    let mut seen_signals: HashSet<String> = HashSet::new();
484    // Track signal positions for role inference
485    let mut antecedent_signals: HashSet<String> = HashSet::new();
486    let mut consequent_signals: HashSet<String> = HashSet::new();
487    // Track predicate names for property naming
488    let mut predicate_names: Vec<String> = Vec::new();
489
490    /// Position context for signal role inference.
491    #[derive(Clone, Copy, PartialEq)]
492    enum Position {
493        Neutral,
494        Antecedent,
495        Consequent,
496    }
497
498    fn walk<'a>(
499        expr: &'a LogicExpr<'a>,
500        interner: &crate::Interner,
501        kg: &mut HwKnowledgeGraph,
502        seen: &mut HashSet<String>,
503        antecedent: &mut HashSet<String>,
504        consequent: &mut HashSet<String>,
505        pred_names: &mut Vec<String>,
506        in_safety: bool,
507        in_liveness: bool,
508        position: Position,
509        impl_depth: u32,
510    ) {
511        match expr {
512            LogicExpr::Predicate { name, args, world } => {
513                let pred_name = interner.resolve(*name).to_string();
514
515                // Skip accessibility predicates themselves
516                if pred_name.contains("Accessible")
517                    || pred_name.contains("Reachable")
518                    || pred_name.contains("Next_Temporal")
519                {
520                    return;
521                }
522
523                // Collect predicate names for property naming
524                if !pred_name.starts_with('w') {
525                    pred_names.push(pred_name.clone());
526                }
527
528                // Predicates with world args are signals.
529                // Use both the predicate name and non-world arguments as signal names.
530                if world.is_some() {
531                    // The predicate name itself is a useful signal identifier
532                    let pred_lower = pred_name.to_lowercase();
533                    if !pred_lower.is_empty() {
534                        seen.insert(pred_name.clone());
535                        match position {
536                            Position::Antecedent => {
537                                antecedent.insert(pred_name.clone());
538                            }
539                            Position::Consequent => {
540                                consequent.insert(pred_name.clone());
541                            }
542                            Position::Neutral => {}
543                        }
544                    }
545
546                    for arg in args.iter() {
547                        if let crate::ast::logic::Term::Constant(sym)
548                        | crate::ast::logic::Term::Variable(sym) = arg
549                        {
550                            let arg_name = interner.resolve(*sym).to_string();
551                            // Skip world variables (w0, w1, ...) and single-letter bound vars
552                            if (!arg_name.starts_with('w') || arg_name.len() > 3)
553                                && arg_name.len() > 1
554                            {
555                                seen.insert(arg_name.clone());
556                                match position {
557                                    Position::Antecedent => {
558                                        antecedent.insert(arg_name);
559                                    }
560                                    Position::Consequent => {
561                                        consequent.insert(arg_name);
562                                    }
563                                    Position::Neutral => {}
564                                }
565                            }
566                        }
567                    }
568                }
569            }
570
571            // Universal quantifier with temporal accessibility → safety property
572            LogicExpr::Quantifier {
573                kind: QuantifierKind::Universal,
574                variable,
575                body,
576                ..
577            } => {
578                let var_name = interner.resolve(*variable).to_string();
579                let is_temporal_world = var_name.starts_with('w');
580                walk(
581                    body,
582                    interner,
583                    kg,
584                    seen,
585                    antecedent,
586                    consequent,
587                    pred_names,
588                    in_safety || is_temporal_world,
589                    in_liveness,
590                    position,
591                    impl_depth,
592                );
593            }
594
595            // Existential quantifier with temporal reachability → liveness property
596            LogicExpr::Quantifier {
597                kind: QuantifierKind::Existential,
598                variable,
599                body,
600                ..
601            } => {
602                let var_name = interner.resolve(*variable).to_string();
603                let is_temporal_world = var_name.starts_with('w');
604                walk(
605                    body,
606                    interner,
607                    kg,
608                    seen,
609                    antecedent,
610                    consequent,
611                    pred_names,
612                    in_safety,
613                    in_liveness || is_temporal_world,
614                    position,
615                    impl_depth,
616                );
617            }
618
619            // Counting quantifiers (AtMost, AtLeast, Cardinal, etc.) — recurse into body
620            LogicExpr::Quantifier { body, .. } => {
621                walk(
622                    body,
623                    interner,
624                    kg,
625                    seen,
626                    antecedent,
627                    consequent,
628                    pred_names,
629                    in_safety,
630                    in_liveness,
631                    position,
632                    impl_depth,
633                );
634            }
635
636            // Atom: bare symbol — treat as signal name
637            LogicExpr::Atom(sym) => {
638                let name = interner.resolve(*sym).to_string();
639                if !name.is_empty() && name.len() > 1 {
640                    seen.insert(name.clone());
641                    match position {
642                        Position::Antecedent => {
643                            antecedent.insert(name);
644                        }
645                        Position::Consequent => {
646                            consequent.insert(name);
647                        }
648                        Position::Neutral => {}
649                    }
650                }
651            }
652
653            // Binary connectives: walk both sides
654            LogicExpr::BinaryOp { left, right, op } => {
655                // TokenType::If = user-written conditional (provenance tag).
656                // TokenType::Implies = compiler-generated restriction/accessibility.
657                // Only user conditionals determine antecedent/consequent roles.
658                if matches!(op, crate::token::TokenType::If) {
659                    // User's explicit if...then — sets signal positions
660                    walk(
661                        left,
662                        interner,
663                        kg,
664                        seen,
665                        antecedent,
666                        consequent,
667                        pred_names,
668                        in_safety,
669                        in_liveness,
670                        Position::Antecedent,
671                        impl_depth,
672                    );
673                    walk(
674                        right,
675                        interner,
676                        kg,
677                        seen,
678                        antecedent,
679                        consequent,
680                        pred_names,
681                        in_safety,
682                        in_liveness,
683                        Position::Consequent,
684                        impl_depth,
685                    );
686
687                    // Triggers edge — use hw-aware extraction that prefers restriction
688                    // type names (Request, Grant) over verb predicates (Hold, Have)
689                    if let (Some(left_sig), Some(right_sig)) = (
690                        extract_hw_signal_name(left, interner),
691                        extract_hw_signal_name(right, interner),
692                    ) {
693                        if left_sig != right_sig {
694                            kg.add_edge(&left_sig, &right_sig, KgRelation::Triggers, None);
695
696                            // Sprint D: detect response pattern G(P → X(Q))
697                            let is_next = matches!(
698                                right,
699                                LogicExpr::Temporal {
700                                    operator: crate::ast::logic::TemporalOperator::Next,
701                                    ..
702                                }
703                            ) || is_kripke_next(right, interner);
704                            if is_next && in_safety {
705                                kg.add_entity(
706                                    format!("{}_responds_to_{}", right_sig, left_sig),
707                                    HwEntityType::ResponseProperty {
708                                        trigger: left_sig.clone(),
709                                        response: right_sig.clone(),
710                                        bound: Some(1),
711                                    },
712                                );
713                                kg.add_typed_edge(
714                                    &left_sig,
715                                    &right_sig,
716                                    HwRelation::Triggers { delay: Some(1) },
717                                );
718                            }
719
720                            // Sprint D: detect eventually-follows G(P → F(Q))
721                            let is_eventually = matches!(
722                                right,
723                                LogicExpr::Temporal {
724                                    operator: crate::ast::logic::TemporalOperator::Eventually,
725                                    ..
726                                }
727                            ) || is_kripke_eventually(right, interner);
728                            if is_eventually && in_safety {
729                                kg.add_typed_edge(
730                                    &left_sig,
731                                    &right_sig,
732                                    HwRelation::EventuallyFollows,
733                                );
734                            }
735                        }
736                    }
737                } else if matches!(op, crate::token::TokenType::Implies) {
738                    // Compiler-generated Implies — could be accessibility unwrap OR user conditional.
739                    // If left is an accessibility predicate, this is Kripke structure (skip edge extraction).
740                    // If left is a real predicate, this is a user conditional (extract edges).
741                    let left_is_accessibility = if let LogicExpr::Predicate { name, .. } = left {
742                        let pn = interner.resolve(*name).to_string();
743                        pn.contains("Accessible")
744                            || pn.contains("Reachable")
745                            || pn.contains("Next_Temporal")
746                    } else {
747                        false
748                    };
749
750                    if !left_is_accessibility {
751                        // User conditional lowered to Implies — extract edges but preserve
752                        // position as Neutral to avoid misclassifying restriction types
753                        // (Animal, Mammal) as antecedent/consequent signals.
754                        walk(
755                            left,
756                            interner,
757                            kg,
758                            seen,
759                            antecedent,
760                            consequent,
761                            pred_names,
762                            in_safety,
763                            in_liveness,
764                            position,
765                            impl_depth,
766                        );
767                        walk(
768                            right,
769                            interner,
770                            kg,
771                            seen,
772                            antecedent,
773                            consequent,
774                            pred_names,
775                            in_safety,
776                            in_liveness,
777                            position,
778                            impl_depth,
779                        );
780
781                        if let (Some(left_sig), Some(right_sig)) = (
782                            extract_hw_signal_name(left, interner),
783                            extract_hw_signal_name(right, interner),
784                        ) {
785                            if left_sig != right_sig {
786                                kg.add_edge(&left_sig, &right_sig, KgRelation::Triggers, None);
787
788                                // Detect response pattern G(P → X(Q))
789                                let is_next = matches!(
790                                    right,
791                                    LogicExpr::Temporal {
792                                        operator: crate::ast::logic::TemporalOperator::Next,
793                                        ..
794                                    }
795                                ) || is_kripke_next(right, interner);
796                                if is_next && in_safety {
797                                    kg.add_entity(
798                                        format!("{}_responds_to_{}", right_sig, left_sig),
799                                        HwEntityType::ResponseProperty {
800                                            trigger: left_sig.clone(),
801                                            response: right_sig.clone(),
802                                            bound: Some(1),
803                                        },
804                                    );
805                                    kg.add_typed_edge(
806                                        &left_sig,
807                                        &right_sig,
808                                        HwRelation::Triggers { delay: Some(1) },
809                                    );
810                                }
811
812                                // Detect eventually-follows G(P → F(Q))
813                                let is_eventually = matches!(
814                                    right,
815                                    LogicExpr::Temporal {
816                                        operator: crate::ast::logic::TemporalOperator::Eventually,
817                                        ..
818                                    }
819                                ) || is_kripke_eventually(right, interner);
820                                if is_eventually && in_safety {
821                                    kg.add_typed_edge(
822                                        &left_sig,
823                                        &right_sig,
824                                        HwRelation::EventuallyFollows,
825                                    );
826                                }
827                            }
828                        }
829                    } else {
830                        // Accessibility predicate — just walk both sides
831                        walk(
832                            left,
833                            interner,
834                            kg,
835                            seen,
836                            antecedent,
837                            consequent,
838                            pred_names,
839                            in_safety,
840                            in_liveness,
841                            position,
842                            impl_depth,
843                        );
844                        walk(
845                            right,
846                            interner,
847                            kg,
848                            seen,
849                            antecedent,
850                            consequent,
851                            pred_names,
852                            in_safety,
853                            in_liveness,
854                            position,
855                            impl_depth,
856                        );
857                    }
858                } else {
859                    // Other connectives — preserve position
860                    walk(
861                        left,
862                        interner,
863                        kg,
864                        seen,
865                        antecedent,
866                        consequent,
867                        pred_names,
868                        in_safety,
869                        in_liveness,
870                        position,
871                        impl_depth,
872                    );
873                    walk(
874                        right,
875                        interner,
876                        kg,
877                        seen,
878                        antecedent,
879                        consequent,
880                        pred_names,
881                        in_safety,
882                        in_liveness,
883                        position,
884                        impl_depth,
885                    );
886                }
887            }
888
889            // Negation
890            LogicExpr::UnaryOp { operand, .. } => {
891                walk(
892                    operand,
893                    interner,
894                    kg,
895                    seen,
896                    antecedent,
897                    consequent,
898                    pred_names,
899                    in_safety,
900                    in_liveness,
901                    position,
902                    impl_depth,
903                );
904
905                // Not(And(P, Q)) → Constrains edge + MutexProperty entity
906                if let LogicExpr::BinaryOp {
907                    left,
908                    right,
909                    op: crate::token::TokenType::And,
910                } = operand
911                {
912                    if let (Some(left_sig), Some(right_sig)) = (
913                        extract_signal_name(left, interner),
914                        extract_signal_name(right, interner),
915                    ) {
916                        if left_sig != right_sig {
917                            kg.add_edge(&left_sig, &right_sig, KgRelation::Constrains, None);
918                            // Sprint D: add MutexProperty entity
919                            kg.add_entity(
920                                format!("mutex_{}_{}", left_sig, right_sig),
921                                HwEntityType::MutexProperty {
922                                    signals: vec![left_sig.clone(), right_sig.clone()],
923                                },
924                            );
925                        }
926                    }
927                }
928            }
929
930            // Temporal operators
931            LogicExpr::Temporal { body, .. } => {
932                walk(
933                    body,
934                    interner,
935                    kg,
936                    seen,
937                    antecedent,
938                    consequent,
939                    pred_names,
940                    in_safety,
941                    in_liveness,
942                    position,
943                    impl_depth,
944                );
945            }
946
947            LogicExpr::TemporalBinary {
948                operator,
949                left,
950                right,
951            } => {
952                walk(
953                    left,
954                    interner,
955                    kg,
956                    seen,
957                    antecedent,
958                    consequent,
959                    pred_names,
960                    in_safety,
961                    in_liveness,
962                    position,
963                    impl_depth,
964                );
965                walk(
966                    right,
967                    interner,
968                    kg,
969                    seen,
970                    antecedent,
971                    consequent,
972                    pred_names,
973                    in_safety,
974                    in_liveness,
975                    position,
976                    impl_depth,
977                );
978
979                // Sprint D: Until → Precedes typed edge
980                if matches!(operator, crate::ast::logic::BinaryTemporalOp::Until) {
981                    if let (Some(left_sig), Some(right_sig)) = (
982                        extract_hw_signal_name(left, interner),
983                        extract_hw_signal_name(right, interner),
984                    ) {
985                        if left_sig != right_sig {
986                            kg.add_typed_edge(&left_sig, &right_sig, HwRelation::Precedes);
987                        }
988                    }
989                }
990            }
991
992            // Modal operators
993            LogicExpr::Modal { operand, .. } => {
994                walk(
995                    operand,
996                    interner,
997                    kg,
998                    seen,
999                    antecedent,
1000                    consequent,
1001                    pred_names,
1002                    in_safety,
1003                    in_liveness,
1004                    position,
1005                    impl_depth,
1006                );
1007            }
1008
1009            _ => {}
1010        }
1011    }
1012
1013    walk(
1014        expr,
1015        interner,
1016        &mut kg,
1017        &mut seen_signals,
1018        &mut antecedent_signals,
1019        &mut consequent_signals,
1020        &mut predicate_names,
1021        false,
1022        false,
1023        Position::Neutral,
1024        0,
1025    );
1026
1027    // Sprint D: detect handshake pairs from signal naming patterns
1028    let signal_names: Vec<String> = seen_signals.iter().cloned().collect();
1029    let handshake_pairs: Vec<(&str, &[&str])> = vec![
1030        ("valid", &["ready", "rdy"]),
1031        ("req", &["ack", "gnt", "grant"]),
1032        (
1033            "request",
1034            &["acknowledge", "acknowledgment", "response", "grant"],
1035        ),
1036        ("cmd", &["resp", "response"]),
1037        ("start", &["done", "complete"]),
1038    ];
1039    for (trigger_pattern, response_patterns) in &handshake_pairs {
1040        let trigger_match = signal_names
1041            .iter()
1042            .find(|s| s.to_lowercase().contains(trigger_pattern));
1043        if let Some(trigger_sig) = trigger_match {
1044            for resp_pattern in *response_patterns {
1045                let resp_match = signal_names.iter().find(|s| {
1046                    let lower = s.to_lowercase();
1047                    lower.contains(resp_pattern) && *s != trigger_sig
1048                });
1049                if let Some(resp_sig) = resp_match {
1050                    kg.add_entity(
1051                        format!("handshake_{}_{}", trigger_sig, resp_sig),
1052                        HwEntityType::Handshake {
1053                            valid_signal: trigger_sig.clone(),
1054                            ready_signal: resp_sig.clone(),
1055                        },
1056                    );
1057                    kg.add_typed_edge(trigger_sig, resp_sig, HwRelation::HandshakesWith);
1058                    break; // Only match the first response pattern
1059                }
1060            }
1061        }
1062    }
1063
1064    // Assign roles based on position inference + populate typed entities
1065    for sig_name in &seen_signals {
1066        let in_ante = antecedent_signals.contains(sig_name);
1067        let in_cons = consequent_signals.contains(sig_name);
1068        let name_lower = sig_name.to_lowercase();
1069
1070        let role = if name_lower.contains("clk") || name_lower.contains("clock") {
1071            SignalRole::Clock
1072        } else if in_ante && !in_cons {
1073            SignalRole::Input
1074        } else if in_cons && !in_ante {
1075            SignalRole::Output
1076        } else {
1077            SignalRole::Internal
1078        };
1079
1080        kg.add_signal(sig_name, 1, role.clone());
1081
1082        // Typed entity extraction: derive HwEntityType from signal role
1083        if name_lower.contains("clk") || name_lower.contains("clock") {
1084            kg.add_entity(
1085                sig_name,
1086                HwEntityType::Clock {
1087                    frequency: None,
1088                    domain: sig_name.clone(),
1089                },
1090            );
1091        }
1092    }
1093
1094    // Populate typed edges from legacy edges
1095    let mut mutex_entities: Vec<(String, HwEntityType)> = Vec::new();
1096    for edge in &kg.edges {
1097        let typed_rel = match &edge.relation {
1098            KgRelation::Triggers => HwRelation::Triggers { delay: None },
1099            KgRelation::Constrains => HwRelation::Constrains,
1100            KgRelation::Temporal => HwRelation::Triggers { delay: None },
1101            KgRelation::TypeOf => HwRelation::Contains,
1102        };
1103        kg.typed_edges
1104            .push((edge.from.clone(), edge.to.clone(), typed_rel));
1105
1106        // Sprint D: Constrains edge → MutexProperty entity
1107        if edge.relation == KgRelation::Constrains {
1108            mutex_entities.push((
1109                format!("mutex_{}_{}", edge.from, edge.to),
1110                HwEntityType::MutexProperty {
1111                    signals: vec![edge.from.clone(), edge.to.clone()],
1112                },
1113            ));
1114        }
1115    }
1116    // Add mutex entities from Constrains edges (deferred to avoid borrow conflict)
1117    let already_has_mutex = kg
1118        .entities
1119        .iter()
1120        .any(|(_, e)| matches!(e, HwEntityType::MutexProperty { .. }));
1121    if !already_has_mutex {
1122        for (name, entity) in mutex_entities {
1123            kg.add_entity(name, entity);
1124        }
1125    }
1126
1127    // Sprint D: detect mutex from signal naming patterns
1128    // Signals with same base and different suffixes (e.g., grant_a, grant_b) → mutex
1129    if !kg
1130        .entities
1131        .iter()
1132        .any(|(_, e)| matches!(e, HwEntityType::MutexProperty { .. }))
1133    {
1134        let sig_names: Vec<String> = kg.signals.iter().map(|s| s.name.clone()).collect();
1135        let mut mutex_groups: std::collections::HashMap<String, Vec<String>> =
1136            std::collections::HashMap::new();
1137        for name in &sig_names {
1138            let lower = name.to_lowercase();
1139            // Check for patterns like "grant_a" → base "grant"
1140            if let Some(underscore_pos) = lower.rfind('_') {
1141                let suffix = &lower[underscore_pos + 1..];
1142                if suffix.len() <= 2 {
1143                    // Single char/digit suffix
1144                    let base = lower[..underscore_pos].to_string();
1145                    mutex_groups.entry(base).or_default().push(name.clone());
1146                }
1147            }
1148        }
1149        for (base, group) in &mutex_groups {
1150            if group.len() >= 2
1151                && (base.contains("grant") || base.contains("sel") || base.contains("enable"))
1152            {
1153                kg.add_entity(
1154                    format!("mutex_{}", base),
1155                    HwEntityType::MutexProperty {
1156                        signals: group.clone(),
1157                    },
1158                );
1159                // Add Constrains edges between pairs
1160                for i in 0..group.len() {
1161                    for j in (i + 1)..group.len() {
1162                        kg.add_edge(&group[i], &group[j], KgRelation::Constrains, None);
1163                    }
1164                }
1165            }
1166        }
1167    }
1168
1169    // Determine property type and name from the top-level structure
1170    // Use predicate names for descriptive property naming
1171    let prop_name = predicate_names
1172        .iter()
1173        .find(|n| {
1174            let lower = n.to_lowercase();
1175            !lower.contains("accessible")
1176                && !lower.contains("reachable")
1177                && !lower.contains("next_temporal")
1178                && lower != "and"
1179                && lower != "or"
1180        })
1181        .cloned();
1182
1183    // Build a formula description from predicate names
1184    let formula_desc = predicate_names
1185        .iter()
1186        .filter(|n| {
1187            let lower = n.to_lowercase();
1188            !lower.contains("accessible")
1189                && !lower.contains("reachable")
1190                && !lower.contains("next_temporal")
1191        })
1192        .cloned()
1193        .collect::<Vec<_>>()
1194        .join(", ");
1195
1196    match expr {
1197        LogicExpr::Temporal {
1198            operator: crate::ast::logic::TemporalOperator::Always,
1199            ..
1200        } => {
1201            let name = prop_name.unwrap_or_else(|| "Safety".to_string());
1202            kg.add_property(name.clone(), "safety", "G(...)");
1203            kg.add_entity(
1204                &name,
1205                HwEntityType::SafetyProperty {
1206                    formula: format!("G({})", formula_desc),
1207                },
1208            );
1209        }
1210        LogicExpr::Temporal {
1211            operator: crate::ast::logic::TemporalOperator::Eventually,
1212            ..
1213        } => {
1214            let name = prop_name.unwrap_or_else(|| "Liveness".to_string());
1215            kg.add_property(name.clone(), "liveness", "F(...)");
1216            kg.add_entity(
1217                &name,
1218                HwEntityType::LivenessProperty {
1219                    formula: format!("F({})", formula_desc),
1220                },
1221            );
1222        }
1223        LogicExpr::Quantifier {
1224            kind: QuantifierKind::Universal,
1225            ..
1226        } => {
1227            // Kripke-lowered G produces ∀w'(...)
1228            let name = prop_name.unwrap_or_else(|| "Safety".to_string());
1229            kg.add_property(name.clone(), "safety", "G(...)");
1230            kg.add_entity(
1231                &name,
1232                HwEntityType::SafetyProperty {
1233                    formula: format!("G({})", formula_desc),
1234                },
1235            );
1236        }
1237        LogicExpr::Quantifier {
1238            kind: QuantifierKind::Existential,
1239            ..
1240        } => {
1241            let name = prop_name.unwrap_or_else(|| "Liveness".to_string());
1242            kg.add_property(name.clone(), "liveness", "F(...)");
1243            kg.add_entity(
1244                &name,
1245                HwEntityType::LivenessProperty {
1246                    formula: format!("F({})", formula_desc),
1247                },
1248            );
1249        }
1250        _ => {}
1251    }
1252
1253    kg
1254}
1255
1256/// Check if an expression contains a Kripke-lowered Next: ∀w'(Next_Temporal(w,w') → P(w'))
1257/// Recurses through restriction quantifiers (non-world variables) to find the temporal structure.
1258fn is_kripke_next<'a>(
1259    expr: &'a crate::ast::logic::LogicExpr<'a>,
1260    interner: &crate::Interner,
1261) -> bool {
1262    use crate::ast::logic::{LogicExpr, QuantifierKind};
1263    match expr {
1264        LogicExpr::Quantifier {
1265            kind: QuantifierKind::Universal,
1266            body,
1267            variable,
1268            ..
1269        } => {
1270            let var_name = interner.resolve(*variable).to_string();
1271            if var_name.starts_with('w') {
1272                // World quantifier — check for Next_Temporal in the body
1273                if let LogicExpr::BinaryOp { left, op, .. } = body {
1274                    if matches!(
1275                        op,
1276                        crate::token::TokenType::Implies | crate::token::TokenType::If
1277                    ) {
1278                        if let LogicExpr::Predicate { name, .. } = left {
1279                            let pred_name = interner.resolve(*name).to_string();
1280                            if pred_name == "Next_Temporal" {
1281                                return true;
1282                            }
1283                        }
1284                    }
1285                }
1286            }
1287            // Non-world quantifier (restriction) — recurse into body
1288            is_kripke_next(body, interner)
1289        }
1290        LogicExpr::BinaryOp { right, op, .. } if matches!(op, crate::token::TokenType::Implies) => {
1291            // Restriction: ∀x(Type(x) → Body) — recurse into right side
1292            is_kripke_next(right, interner)
1293        }
1294        LogicExpr::Temporal {
1295            operator: crate::ast::logic::TemporalOperator::Next,
1296            ..
1297        } => true,
1298        _ => false,
1299    }
1300}
1301
1302/// Check if an expression contains a Kripke-lowered Eventually: ∃w'(Reachable_Temporal(w,w') ∧ P(w'))
1303/// Recurses through restriction quantifiers to find the temporal structure.
1304fn is_kripke_eventually<'a>(
1305    expr: &'a crate::ast::logic::LogicExpr<'a>,
1306    interner: &crate::Interner,
1307) -> bool {
1308    use crate::ast::logic::{LogicExpr, QuantifierKind};
1309    match expr {
1310        LogicExpr::Quantifier {
1311            kind: QuantifierKind::Existential,
1312            body,
1313            variable,
1314            ..
1315        } => {
1316            let var_name = interner.resolve(*variable).to_string();
1317            if var_name.starts_with('w') {
1318                if let LogicExpr::BinaryOp {
1319                    left,
1320                    op: crate::token::TokenType::And,
1321                    ..
1322                } = body
1323                {
1324                    if let LogicExpr::Predicate { name, .. } = left {
1325                        let pred_name = interner.resolve(*name).to_string();
1326                        if pred_name == "Reachable_Temporal" {
1327                            return true;
1328                        }
1329                    }
1330                }
1331            }
1332            // Recurse into body for restriction quantifiers
1333            is_kripke_eventually(body, interner)
1334        }
1335        LogicExpr::Quantifier {
1336            kind: QuantifierKind::Universal,
1337            body,
1338            ..
1339        } => {
1340            // Universal restriction quantifier — recurse
1341            is_kripke_eventually(body, interner)
1342        }
1343        LogicExpr::BinaryOp { right, op, .. } if matches!(op, crate::token::TokenType::Implies) => {
1344            is_kripke_eventually(right, interner)
1345        }
1346        LogicExpr::Temporal {
1347            operator: crate::ast::logic::TemporalOperator::Eventually,
1348            ..
1349        } => true,
1350        _ => false,
1351    }
1352}
1353
1354/// Extract a hardware signal name from Kripke-lowered AST, preferring
1355/// restriction predicate names (the TYPE, e.g., "Request") over verb predicates
1356/// (e.g., "Hold/Have"). Used for edge extraction in the walk handler.
1357fn extract_hw_signal_name<'a>(
1358    expr: &'a crate::ast::logic::LogicExpr<'a>,
1359    interner: &crate::Interner,
1360) -> Option<String> {
1361    use crate::ast::logic::LogicExpr;
1362    match expr {
1363        // Quantifier with restriction: ∀x(Request(x) → Hold(x,w')) → "Request"
1364        LogicExpr::Quantifier { body, .. } => extract_hw_signal_name(body, interner),
1365        LogicExpr::BinaryOp { left, right, op } => {
1366            if matches!(op, crate::token::TokenType::Implies) {
1367                // Restriction pattern: left is the type predicate, prefer it
1368                let left_name = extract_signal_name(left, interner);
1369                if left_name.is_some() {
1370                    return left_name;
1371                }
1372                extract_hw_signal_name(right, interner)
1373            } else {
1374                extract_hw_signal_name(left, interner)
1375                    .or_else(|| extract_hw_signal_name(right, interner))
1376            }
1377        }
1378        // Fall through to regular extraction
1379        _ => extract_signal_name(expr, interner),
1380    }
1381}
1382
1383/// Try to extract a signal name from an expression by recursing into
1384/// quantifiers, binary ops, and event structures to find the first
1385/// meaningful predicate argument.
1386fn extract_signal_name<'a>(
1387    expr: &'a crate::ast::logic::LogicExpr<'a>,
1388    interner: &crate::Interner,
1389) -> Option<String> {
1390    use crate::ast::logic::LogicExpr;
1391    match expr {
1392        LogicExpr::Predicate { name, args, .. } => {
1393            let pred_name = interner.resolve(*name).to_string();
1394            // Skip accessibility/meta predicates
1395            if pred_name.contains("Accessible")
1396                || pred_name.contains("Reachable")
1397                || pred_name.contains("Next_Temporal")
1398                || pred_name == "Agent"
1399                || pred_name == "Theme"
1400            {
1401                return None;
1402            }
1403            // Prefer non-world arguments (signal names) over predicate name (verb)
1404            let arg_name = args.iter().find_map(|arg| match arg {
1405                crate::ast::logic::Term::Constant(sym) | crate::ast::logic::Term::Variable(sym) => {
1406                    let aname = interner.resolve(*sym).to_string();
1407                    if (!aname.starts_with('w') || aname.len() > 3) && aname.len() > 1 {
1408                        Some(aname)
1409                    } else {
1410                        None
1411                    }
1412                }
1413                _ => None,
1414            });
1415            if let Some(an) = arg_name {
1416                return Some(an);
1417            }
1418            // Fall back to predicate name if no useful arguments
1419            if pred_name.len() > 1
1420                && pred_name
1421                    .chars()
1422                    .next()
1423                    .map(|c| c.is_uppercase())
1424                    .unwrap_or(false)
1425            {
1426                return Some(pred_name);
1427            }
1428            None
1429        }
1430        // Recurse into quantifiers to find the core predicate
1431        LogicExpr::Quantifier { body, .. } => extract_signal_name(body, interner),
1432        // Recurse into binary ops — for restrictions (Implies), look at the right side (body);
1433        // for conjunctions, try both sides
1434        LogicExpr::BinaryOp { left, right, op } => {
1435            if matches!(op, crate::token::TokenType::Implies) {
1436                // Restriction: ∀x(Type(x) → Body(x)) — signal is in the body
1437                extract_signal_name(right, interner).or_else(|| extract_signal_name(left, interner))
1438            } else {
1439                // Try left first, then right
1440                extract_signal_name(left, interner).or_else(|| extract_signal_name(right, interner))
1441            }
1442        }
1443        // Recurse into existentials (event structures: ∃e(Run(e) ∧ Agent(e,x)))
1444        LogicExpr::NeoEvent(data) => {
1445            let verb_name = interner.resolve(data.verb).to_string();
1446            Some(verb_name)
1447        }
1448        _ => None,
1449    }
1450}