typr_core/components/context/
graph.rs

1use crate::components::context::Context;
2use crate::components::r#type::type_system::TypeSystem;
3use serde::Deserialize;
4use serde::Serialize;
5use std::collections::HashMap;
6use std::collections::HashSet;
7use std::fmt::Debug;
8use std::ops::Add;
9use std::sync::Arc;
10
11/// `memory`/`root` hold the whole-program subtype registry (grows with every
12/// distinct type seen — stdlib signatures included), and used to be
13/// deep-cloned on every `Graph::clone()` (in turn triggered by every
14/// `Context::clone()`). `Arc`-wrapping makes that clone O(1); mutators
15/// (`add_type`, `cache_subtype`) recover an owned value via
16/// `Arc::unwrap_or_clone`, which only actually copies when another live
17/// `Arc` still shares the allocation.
18#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
19#[serde(bound = "T: Serialize + for<'a> Deserialize<'a>")]
20pub struct Graph<T: TypeSystem> {
21    memory: Arc<HashSet<T>>,
22    root: Arc<Node<T>>,
23    #[serde(skip)]
24    subtype_cache: Arc<HashMap<(T, T), bool>>,
25}
26
27impl<T: TypeSystem> Default for Graph<T> {
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33impl<T: TypeSystem> Graph<T> {
34    pub fn new() -> Self {
35        Graph {
36            memory: Arc::new(HashSet::new()),
37            root: Arc::new(Node::new()),
38            subtype_cache: Arc::new(HashMap::new()),
39        }
40    }
41
42    /// Vérifie si le résultat de sous-typage est en cache
43    pub fn check_subtype_cache(&self, t1: &T, t2: &T) -> Option<bool> {
44        self.subtype_cache.get(&(t1.clone(), t2.clone())).copied()
45    }
46
47    /// Enregistre un résultat de sous-typage dans le cache
48    pub fn cache_subtype(self, t1: T, t2: T, result: bool) -> Self {
49        let mut subtype_cache = Arc::unwrap_or_clone(self.subtype_cache);
50        subtype_cache.insert((t1, t2), result);
51        Graph {
52            memory: self.memory,
53            root: self.root,
54            subtype_cache: Arc::new(subtype_cache),
55        }
56    }
57
58    pub fn add_type(self, typ: T, context: &Context) -> Self {
59        if self.memory.contains(&typ) {
60            self
61        } else {
62            let root = Arc::unwrap_or_clone(self.root);
63            let new_root = root.add_type(typ.clone(), context);
64            let mut new_memory = Arc::unwrap_or_clone(self.memory);
65            new_memory.insert(typ);
66            Graph {
67                memory: Arc::new(new_memory),
68                root: Arc::new(new_root),
69                subtype_cache: self.subtype_cache,
70            }
71        }
72    }
73
74    pub fn get_hierarchy(&self) -> String {
75        self.root.get_hierarchy()
76    }
77
78    /// Deterministic rendering of the graph for fingerprinting: only the
79    /// insertion-ordered node tree. `memory` (a `HashSet`) and the subtype
80    /// cache iterate in random order and must not reach a fingerprint.
81    pub fn structure_debug(&self) -> String {
82        format!("{:?}", self.root)
83    }
84
85    // Deduplicates while preserving the walk order: the result feeds R class
86    // vectors (`struct(c(...))` in types.R), where order drives S3 dispatch
87    // and must be stable from one build to the next.
88    pub fn get_supertypes(&self, typ: &T, context: &Context) -> Vec<T> {
89        self.get_ordered_supertypes(typ, context)
90    }
91
92    pub fn get_ordered_supertypes(&self, typ: &T, context: &Context) -> Vec<T> {
93        let raw = self.root.get_supertypes(typ, context);
94        let mut seen = HashSet::new();
95        let mut result = Vec::new();
96        for item in raw {
97            if seen.insert(item.clone()) {
98                result.push(item);
99            }
100        }
101        result
102    }
103
104    pub fn add_types(self, typs: &[T], context: &Context) -> Self {
105        typs.iter().cloned().fold(self, |acc, x| acc.add_type(x, context))
106    }
107}
108
109#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
110#[serde(bound = "T: Serialize + for<'a> Deserialize<'a>")]
111pub struct Node<T: TypeSystem> {
112    value: T,
113    subtypes: Vec<Node<T>>,
114}
115
116impl<T: TypeSystem> From<T> for Node<T> {
117    fn from(val: T) -> Self {
118        Node {
119            value: val,
120            subtypes: vec![],
121        }
122    }
123}
124
125impl<T: TypeSystem> Default for Node<T> {
126    fn default() -> Self {
127        Self::new()
128    }
129}
130
131impl<T: TypeSystem> Node<T> {
132    pub fn new() -> Self {
133        Node {
134            value: T::default(),
135            subtypes: vec![],
136        }
137    }
138
139    pub fn propagate(self, typ: T, context: &Context) -> Self {
140        let graph = Node {
141            value: self.value.clone(),
142            subtypes: self
143                .subtypes
144                .iter()
145                .cloned()
146                .map(|x| x.add_type(typ.clone(), context))
147                .collect(),
148        };
149        if graph == self {
150            self.add_subtype(typ)
151        } else {
152            graph
153        }
154    }
155
156    pub fn add_subtype(self, typ: T) -> Self {
157        Node {
158            value: self.value,
159            subtypes: self.subtypes.iter().chain([Node::from(typ)].iter()).cloned().collect(),
160        }
161    }
162
163    pub fn set_subtypes(self, subtypes: Vec<Node<T>>) -> Self {
164        Node {
165            value: self.value,
166            subtypes,
167        }
168    }
169
170    fn switch_if_reverse_subtype(self, typ: T, context: &Context) -> Self {
171        if self.value.is_subtype_raw(&typ, context) {
172            Node {
173                value: typ,
174                subtypes: vec![Node::from(self.value).set_subtypes(self.subtypes)],
175            }
176        } else {
177            self
178        }
179    }
180
181    pub fn add_type(self, typ: T, context: &Context) -> Self {
182        if self.value == typ {
183            self
184        } else {
185            match (typ.is_subtype_raw(&self.value, context), self.subtypes.len()) {
186                (true, 0) => self.add_subtype(typ),
187                (true, _) => self.propagate(typ, context),
188                _ => self.switch_if_reverse_subtype(typ, context),
189            }
190        }
191    }
192
193    pub fn get_supertypes(&self, target_type: &T, context: &Context) -> Vec<T> {
194        if target_type == &self.value {
195            vec![]
196        } else if target_type.is_subtype_raw(&self.value, context) {
197            self.subtypes
198                .iter()
199                .flat_map(|x| x.get_supertypes(target_type, context))
200                .chain([self.value.clone()].iter().cloned())
201                .collect::<Vec<T>>()
202        } else {
203            vec![]
204        }
205    }
206
207    pub fn get_hierarchy(&self) -> String {
208        self.get_hierarchy_helper(0)
209    }
210
211    fn tabulation_from_level(level: i32) -> String {
212        (0..level).map(|_| "  ").collect::<Vec<_>>().join("")
213    }
214
215    pub fn get_hierarchy_helper(&self, level: i32) -> String {
216        let tab = Node::<T>::tabulation_from_level(level);
217        let children = self
218            .subtypes
219            .iter()
220            .map(|x| x.get_hierarchy_helper(level + 1))
221            .collect::<Vec<_>>()
222            .join("\n");
223        tab + &self.value.pretty() + "\n" + &children
224    }
225}
226
227use std::fmt;
228impl<T: TypeSystem> fmt::Display for Node<T> {
229    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
230        write!(f, "{}", self.get_hierarchy())
231    }
232}
233
234impl<T: TypeSystem> Add for Graph<T> {
235    type Output = Self;
236
237    fn add(self, other: Self) -> Self {
238        let context = Context::default(); // Or apply a parameter if necessary
239        let merged = other
240            .memory
241            .iter()
242            .cloned()
243            .fold(self.clone(), |acc, typ| acc.add_type(typ, &context));
244        // Fusionner les caches de sous-typage
245        let mut new_cache = Arc::unwrap_or_clone(self.subtype_cache);
246        new_cache.extend(other.subtype_cache.iter().map(|(k, v)| (k.clone(), *v)));
247        Graph {
248            subtype_cache: Arc::new(new_cache),
249            ..merged
250        }
251    }
252}
typr_core/components/context/graph.rs

typr_core/components/context/
graph.rs
