typr_core/components/context/
graph.rs

1use crate::components::context::Context;
2use crate::components::r#type::type_system::TypeSystem;
3use std::collections::HashMap;
4use std::collections::HashSet;
5use std::fmt::Debug;
6use std::ops::Add;
7
8#[derive(Debug, Clone, PartialEq)]
9pub struct Graph<T: TypeSystem> {
10    memory: HashSet<T>,
11    root: Node<T>,
12    subtype_cache: HashMap<(T, T), bool>,
13}
14
15impl<T: TypeSystem> Graph<T> {
16    pub fn new() -> Self {
17        Graph {
18            memory: HashSet::new(),
19            root: Node::new(),
20            subtype_cache: HashMap::new(),
21        }
22    }
23
24    /// Vérifie si le résultat de sous-typage est en cache
25    pub fn check_subtype_cache(&self, t1: &T, t2: &T) -> Option<bool> {
26        self.subtype_cache.get(&(t1.clone(), t2.clone())).copied()
27    }
28
29    /// Enregistre un résultat de sous-typage dans le cache
30    pub fn cache_subtype(self, t1: T, t2: T, result: bool) -> Self {
31        let mut new_cache = self.subtype_cache.clone();
32        new_cache.insert((t1, t2), result);
33        Graph {
34            subtype_cache: new_cache,
35            ..self
36        }
37    }
38
39    pub fn add_type(self, typ: T, context: &Context) -> Self {
40        if self.memory.contains(&typ) {
41            self
42        } else {
43            let new_memory = self
44                .memory
45                .iter()
46                .chain([typ.clone()].iter())
47                .cloned()
48                .collect();
49            let new_root = self.root.add_type(typ.clone(), context);
50            Graph {
51                memory: new_memory,
52                root: new_root,
53                subtype_cache: self.subtype_cache,
54            }
55        }
56    }
57
58    pub fn add_type_trace(self, typ: T, context: &Context) -> Self {
59        if self.memory.contains(&typ) {
60            self
61        } else {
62            Graph {
63                memory: self
64                    .memory
65                    .iter()
66                    .chain([typ.clone()].iter())
67                    .cloned()
68                    .collect(),
69                root: self.root.add_type_trace(typ, context),
70                subtype_cache: self.subtype_cache,
71            }
72        }
73    }
74
75    pub fn get_hierarchy(&self) -> String {
76        self.root.get_hierarchy()
77    }
78
79    pub fn get_type_list(&self) -> String {
80        format!(
81            "{}",
82            T::prettys(&self.memory.iter().cloned().collect::<Vec<_>>())
83        )
84    }
85
86    pub fn print_hierarchy(&self) {
87        eprintln!("{}", self.get_hierarchy());
88    }
89
90    pub fn get_supertypes(&self, typ: &T, context: &Context) -> Vec<T> {
91        self.root
92            .get_supertypes(typ, context)
93            .iter()
94            .cloned()
95            .collect::<HashSet<_>>()
96            .iter()
97            .cloned()
98            .collect::<Vec<_>>()
99    }
100
101    pub fn get_supertypes_trace(&self, typ: &T, context: &Context) -> Vec<T> {
102        self.root
103            .get_supertypes_trace(typ, context)
104            .iter()
105            .cloned()
106            .collect::<HashSet<_>>()
107            .iter()
108            .cloned()
109            .collect::<Vec<_>>()
110    }
111
112    pub fn add_types(self, typs: &[T], context: &Context) -> Self {
113        typs.iter()
114            .cloned()
115            .fold(self, |acc, x| acc.add_type(x, context))
116    }
117}
118
119#[derive(Debug, Clone, PartialEq)]
120pub struct Node<T: TypeSystem> {
121    value: T,
122    subtypes: Vec<Node<T>>,
123}
124
125impl<T: TypeSystem> From<T> for Node<T> {
126    fn from(val: T) -> Self {
127        Node {
128            value: val,
129            subtypes: vec![],
130        }
131    }
132}
133
134impl<T: TypeSystem> Node<T> {
135    pub fn new() -> Self {
136        Node {
137            value: T::default(),
138            subtypes: vec![],
139        }
140    }
141
142    pub fn propagate(self, typ: T, context: &Context) -> Self {
143        let graph = Node {
144            value: self.value.clone(),
145            subtypes: self
146                .subtypes
147                .iter()
148                .cloned()
149                .map(|x| x.add_type(typ.clone(), context))
150                .collect(),
151        };
152        if graph == self {
153            self.add_subtype(typ)
154        } else {
155            graph
156        }
157    }
158
159    pub fn propagate_trace(self, typ: T, context: &Context) -> Self {
160        let graph = Node {
161            value: self.value.clone(),
162            subtypes: self
163                .subtypes
164                .iter()
165                .cloned()
166                .map(|x| x.add_type(typ.clone(), context))
167                .collect(),
168        };
169        if graph == self {
170            eprintln!(
171                "add {} to one of the children of {}",
172                typ.pretty(),
173                self.value.pretty()
174            );
175            self.add_subtype(typ)
176        } else {
177            eprintln!(
178                "{} is not a subtype of {}'s subtypes: {}",
179                typ.pretty(),
180                self.value.pretty(),
181                self.show_subtypes()
182            );
183            graph
184        }
185    }
186
187    pub fn show_subtypes(&self) -> String {
188        "[".to_string()
189            + &self
190                .subtypes
191                .iter()
192                .map(|typ| format!("{}", typ.value.pretty()))
193                .collect::<Vec<_>>()
194                .join(",")
195            + "]"
196    }
197
198    pub fn add_subtype(self, typ: T) -> Self {
199        Node {
200            value: self.value,
201            subtypes: self
202                .subtypes
203                .iter()
204                .chain([Node::from(typ)].iter())
205                .cloned()
206                .collect(),
207        }
208    }
209
210    pub fn set_subtypes(self, subtypes: Vec<Node<T>>) -> Self {
211        Node {
212            value: self.value,
213            subtypes,
214        }
215    }
216
217    fn switch_if_reverse_subtype(self, typ: T, context: &Context) -> Self {
218        if self.value.is_subtype_raw(&typ, context) {
219            Node {
220                value: typ,
221                subtypes: vec![Node::from(self.value).set_subtypes(self.subtypes)],
222            }
223        } else {
224            self
225        }
226    }
227
228    fn switch_if_reverse_subtype_trace(self, typ: T, context: &Context) -> Self {
229        if self.value.is_subtype_raw(&typ, context) {
230            eprintln!(
231                "{} is a subtype of the entry {}",
232                self.value.pretty(),
233                typ.pretty()
234            );
235            Node {
236                value: typ,
237                subtypes: vec![Node::from(self.value).set_subtypes(self.subtypes)],
238            }
239        } else {
240            eprintln!(
241                "{} is not a subtype of {} abort this branch",
242                typ.pretty(),
243                self.value.pretty()
244            );
245            self
246        }
247    }
248
249    pub fn add_type(self, typ: T, context: &Context) -> Self {
250        if self.value == typ {
251            self
252        } else {
253            match (
254                typ.is_subtype_raw(&self.value, context),
255                self.subtypes.len(),
256            ) {
257                (true, 0) => self.add_subtype(typ),
258                (true, _) => self.propagate(typ, context),
259                _ => self.switch_if_reverse_subtype(typ, context),
260            }
261        }
262    }
263
264    pub fn add_type_trace(self, typ: T, context: &Context) -> Self {
265        match (
266            typ.is_subtype_raw(&self.value, context),
267            self.subtypes.len(),
268        ) {
269            (true, 0) => {
270                eprintln!(
271                    "{} is a subtype of the leaf {}",
272                    typ.pretty(),
273                    self.value.pretty()
274                );
275                self.add_subtype(typ)
276            }
277            (true, _) => {
278                eprintln!(
279                    "{} is a subtype of the node {}",
280                    typ.pretty(),
281                    self.value.pretty()
282                );
283                self.propagate_trace(typ, context)
284            }
285            _ => self.switch_if_reverse_subtype_trace(typ, context),
286        }
287    }
288
289    pub fn get_supertypes(&self, target_type: &T, context: &Context) -> Vec<T> {
290        if target_type == &self.value {
291            vec![]
292        } else if target_type.is_subtype_raw(&self.value, context) {
293            self.subtypes
294                .iter()
295                .flat_map(|x| x.get_supertypes(target_type, context))
296                .chain([self.value.clone()].iter().cloned())
297                .collect::<Vec<T>>()
298        } else {
299            vec![]
300        }
301    }
302
303    pub fn get_supertypes_trace(&self, target_type: &T, context: &Context) -> Vec<T> {
304        if target_type == &self.value {
305            eprintln!("found the root of {} we backtrack", target_type.pretty());
306            vec![]
307        } else if target_type.is_subtype_raw(&self.value, context) {
308            eprintln!(
309                "{} is subtype of {} we check the subtypes",
310                target_type.pretty(),
311                self.value.pretty()
312            );
313            self.subtypes
314                .iter()
315                .flat_map(|x| x.get_supertypes_trace(target_type, context))
316                .chain([self.value.clone()].iter().cloned())
317                .collect::<Vec<T>>()
318        } else {
319            eprintln!(
320                "{} is not subtype of {} ABORT this branch",
321                target_type.pretty(),
322                self.value.pretty()
323            );
324            vec![]
325        }
326    }
327
328    pub fn get_hierarchy(&self) -> String {
329        self.get_hierarchy_helper(0)
330    }
331
332    fn tabulation_from_level(level: i32) -> String {
333        (0..level)
334            .into_iter()
335            .map(|_| "  ")
336            .collect::<Vec<_>>()
337            .join("")
338    }
339
340    pub fn get_hierarchy_helper(&self, level: i32) -> String {
341        let tab = Node::<T>::tabulation_from_level(level);
342        let children = self
343            .subtypes
344            .iter()
345            .map(|x| x.get_hierarchy_helper(level + 1))
346            .collect::<Vec<_>>()
347            .join("\n");
348        tab + &self.value.pretty() + "\n" + &children
349    }
350}
351
352use std::fmt;
353impl<T: TypeSystem> fmt::Display for Node<T> {
354    fn fmt(self: &Self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
355        write!(f, "{}", self.get_hierarchy())
356    }
357}
358
359impl<T: TypeSystem> Add for Graph<T> {
360    type Output = Self;
361
362    fn add(self, other: Self) -> Self {
363        let context = Context::default(); // Or apply a parameter if necessary
364        let merged = other
365            .memory
366            .iter()
367            .cloned()
368            .fold(self.clone(), |acc, typ| acc.add_type(typ, &context));
369        // Fusionner les caches de sous-typage
370        let mut new_cache = self.subtype_cache;
371        new_cache.extend(other.subtype_cache);
372        Graph {
373            subtype_cache: new_cache,
374            ..merged
375        }
376    }
377}
typr_core/components/context/graph.rs

typr_core/components/context/
graph.rs
