stack_graphs/serde/
graph.rs

1// -*- coding: utf-8 -*-
2// ------------------------------------------------------------------------------------------------
3// Copyright © 2023, stack-graphs authors.
4// Licensed under either of Apache License, Version 2.0, or MIT license, at your option.
5// Please see the LICENSE-APACHE or LICENSE-MIT files in this distribution for license details.
6// ------------------------------------------------------------------------------------------------
7
8use thiserror::Error;
9
10use crate::arena::Handle;
11
12use super::Filter;
13use super::ImplicationFilter;
14use super::NoFilter;
15
16#[derive(Clone, Debug, Default, Eq, PartialEq)]
17#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
18#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
19pub struct StackGraph {
20    pub files: Files,
21    pub nodes: Nodes,
22    pub edges: Edges,
23}
24
25#[derive(Debug, Error, Eq, PartialEq)]
26pub enum Error {
27    #[error("failed to load file `{0}`")]
28    FileNotFound(String),
29    #[error("duplicate file `{0}`")]
30    FileAlreadyPresent(String),
31    #[error("node `{0}` is an invalid node")]
32    InvalidGlobalNodeID(u32),
33    #[error("variable `{0}` is an invalid stack variable")]
34    InvalidStackVariable(u32),
35    #[error("failed to locate node `{0}` in graph")]
36    NodeNotFound(NodeID),
37}
38
39impl StackGraph {
40    pub fn from_graph<'a>(graph: &crate::graph::StackGraph) -> Self {
41        Self::from_graph_filter(graph, &NoFilter)
42    }
43
44    pub fn from_graph_filter<'a>(graph: &crate::graph::StackGraph, filter: &'a dyn Filter) -> Self {
45        let filter = ImplicationFilter(filter);
46        let files = graph.filter_files(&filter);
47        let nodes = graph.filter_nodes(&filter);
48        let edges = graph.filter_edges(&filter);
49        Self {
50            files,
51            nodes,
52            edges,
53        }
54    }
55
56    pub fn load_into(&self, graph: &mut crate::graph::StackGraph) -> Result<(), Error> {
57        self.load_files(graph)?;
58        self.load_nodes(graph)?;
59        self.load_edges(graph)?;
60        Ok(())
61    }
62
63    fn load_files(&self, graph: &mut crate::graph::StackGraph) -> Result<(), Error> {
64        for file in self.files.data.iter() {
65            graph
66                .add_file(&file)
67                .map_err(|_| Error::FileAlreadyPresent(file.to_owned()))?;
68        }
69
70        Ok(())
71    }
72
73    fn load_nodes(&self, graph: &mut crate::graph::StackGraph) -> Result<(), Error> {
74        for node in &self.nodes.data {
75            let handle = match node {
76                Node::DropScopes { id, .. } => {
77                    let node_id = id.to_node_id(graph)?;
78                    graph.add_drop_scopes_node(node_id)
79                }
80                Node::PopScopedSymbol {
81                    id,
82                    symbol,
83                    is_definition,
84                    ..
85                } => {
86                    let node_id = id.to_node_id(graph)?;
87                    let symbol_handle = graph.add_symbol(&symbol);
88                    graph.add_pop_scoped_symbol_node(node_id, symbol_handle, *is_definition)
89                }
90                Node::PopSymbol {
91                    id,
92                    symbol,
93                    is_definition,
94                    ..
95                } => {
96                    let node_id = id.to_node_id(graph)?;
97                    let symbol_handle = graph.add_symbol(&symbol);
98                    graph.add_pop_symbol_node(node_id, symbol_handle, *is_definition)
99                }
100                Node::PushScopedSymbol {
101                    id,
102                    symbol,
103                    scope,
104                    is_reference,
105                    ..
106                } => {
107                    let node_id = id.to_node_id(graph)?;
108                    let scope_id = scope.to_node_id(graph)?;
109                    let symbol_handle = graph.add_symbol(&symbol);
110                    graph.add_push_scoped_symbol_node(
111                        node_id,
112                        symbol_handle,
113                        scope_id,
114                        *is_reference,
115                    )
116                }
117                Node::PushSymbol {
118                    id,
119                    symbol,
120                    is_reference,
121                    ..
122                } => {
123                    let node_id = id.to_node_id(graph)?;
124                    let symbol_handle = graph.add_symbol(&symbol);
125                    graph.add_push_symbol_node(node_id, symbol_handle, *is_reference)
126                }
127                Node::Scope {
128                    id, is_exported, ..
129                } => {
130                    let node_id = id.to_node_id(graph)?;
131                    graph.add_scope_node(node_id, *is_exported)
132                }
133                Node::JumpToScope { .. } | Node::Root { .. } => None,
134            };
135
136            if let Some(handle) = handle {
137                // load source-info of each node
138                if let Some(source_info) = node.source_info() {
139                    *graph.source_info_mut(handle) = crate::graph::SourceInfo {
140                        span: source_info.span.clone(),
141                        syntax_type: source_info
142                            .syntax_type
143                            .as_ref()
144                            .map(|st| graph.add_string(&st))
145                            .into(),
146                        ..Default::default()
147                    };
148                }
149
150                // load debug-info of each node
151                if let Some(debug_info) = node.debug_info() {
152                    *graph.node_debug_info_mut(handle) = debug_info.data.iter().fold(
153                        crate::graph::DebugInfo::default(),
154                        |mut info, entry| {
155                            let key = graph.add_string(&entry.key);
156                            let value = graph.add_string(&entry.value);
157                            info.add(key, value);
158                            info
159                        },
160                    );
161                }
162            }
163        }
164        Ok(())
165    }
166
167    fn load_edges(&self, graph: &mut crate::graph::StackGraph) -> Result<(), Error> {
168        // load edges into stack-graph
169        for Edge {
170            source,
171            sink,
172            precedence,
173            debug_info,
174        } in &self.edges.data
175        {
176            let source_id = source.to_node_id(graph)?;
177            let sink_id = sink.to_node_id(graph)?;
178
179            let source_handle = graph
180                .node_for_id(source_id)
181                .ok_or(Error::InvalidGlobalNodeID(source.local_id))?;
182            let sink_handle = graph
183                .node_for_id(sink_id)
184                .ok_or(Error::InvalidGlobalNodeID(sink.local_id))?;
185
186            graph.add_edge(source_handle, sink_handle, *precedence);
187
188            // load debug-info of each node
189            if let Some(debug_info) = debug_info {
190                *graph.edge_debug_info_mut(source_handle, sink_handle) = debug_info
191                    .data
192                    .iter()
193                    .fold(crate::graph::DebugInfo::default(), |mut info, entry| {
194                        let key = graph.add_string(&entry.key);
195                        let value = graph.add_string(&entry.value);
196                        info.add(key, value);
197                        info
198                    });
199            }
200        }
201        Ok(())
202    }
203}
204
205#[derive(Clone, Debug, Default, Eq, PartialEq)]
206#[cfg_attr(
207    feature = "serde",
208    derive(serde::Deserialize, serde::Serialize),
209    serde(transparent)
210)]
211#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
212pub struct Files {
213    pub data: Vec<String>,
214}
215
216#[derive(Clone, Debug, Default, Eq, PartialEq)]
217#[cfg_attr(
218    feature = "serde",
219    derive(serde::Deserialize, serde::Serialize),
220    serde(transparent)
221)]
222#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
223pub struct Nodes {
224    pub data: Vec<Node>,
225}
226
227#[derive(Clone, Debug, Eq, PartialEq)]
228#[cfg_attr(
229    feature = "serde",
230    serde_with::skip_serializing_none, // must come before derive
231    derive(serde::Deserialize, serde::Serialize),
232    serde(tag = "type", rename_all = "snake_case"),
233)]
234#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
235pub enum Node {
236    DropScopes {
237        id: NodeID,
238        source_info: Option<SourceInfo>,
239        debug_info: Option<DebugInfo>,
240    },
241
242    JumpToScope {
243        id: NodeID,
244        source_info: Option<SourceInfo>,
245        debug_info: Option<DebugInfo>,
246    },
247
248    PopScopedSymbol {
249        id: NodeID,
250        symbol: String,
251        is_definition: bool,
252        source_info: Option<SourceInfo>,
253        debug_info: Option<DebugInfo>,
254    },
255
256    PopSymbol {
257        id: NodeID,
258        symbol: String,
259        is_definition: bool,
260        source_info: Option<SourceInfo>,
261        debug_info: Option<DebugInfo>,
262    },
263
264    PushScopedSymbol {
265        id: NodeID,
266        symbol: String,
267        scope: NodeID,
268        is_reference: bool,
269        source_info: Option<SourceInfo>,
270        debug_info: Option<DebugInfo>,
271    },
272
273    PushSymbol {
274        id: NodeID,
275        symbol: String,
276        is_reference: bool,
277        source_info: Option<SourceInfo>,
278        debug_info: Option<DebugInfo>,
279    },
280
281    Root {
282        id: NodeID,
283        source_info: Option<SourceInfo>,
284        debug_info: Option<DebugInfo>,
285    },
286
287    Scope {
288        id: NodeID,
289        is_exported: bool,
290        source_info: Option<SourceInfo>,
291        debug_info: Option<DebugInfo>,
292    },
293}
294
295impl Node {
296    fn source_info(&self) -> Option<&SourceInfo> {
297        match self {
298            Self::DropScopes { source_info, .. } => source_info,
299            Self::JumpToScope { source_info, .. } => source_info,
300            Self::PopScopedSymbol { source_info, .. } => source_info,
301            Self::PopSymbol { source_info, .. } => source_info,
302            Self::PushScopedSymbol { source_info, .. } => source_info,
303            Self::PushSymbol { source_info, .. } => source_info,
304            Self::Root { source_info, .. } => source_info,
305            Self::Scope { source_info, .. } => source_info,
306        }
307        .as_ref()
308    }
309
310    fn debug_info(&self) -> Option<&DebugInfo> {
311        match self {
312            Self::DropScopes { debug_info, .. } => debug_info,
313            Self::JumpToScope { debug_info, .. } => debug_info,
314            Self::PopScopedSymbol { debug_info, .. } => debug_info,
315            Self::PopSymbol { debug_info, .. } => debug_info,
316            Self::PushScopedSymbol { debug_info, .. } => debug_info,
317            Self::PushSymbol { debug_info, .. } => debug_info,
318            Self::Root { debug_info, .. } => debug_info,
319            Self::Scope { debug_info, .. } => debug_info,
320        }
321        .as_ref()
322    }
323}
324
325#[derive(Clone, Debug, Eq, PartialEq)]
326#[cfg_attr(
327    feature = "serde",
328    serde_with::skip_serializing_none, // must come before derive
329    derive(serde::Deserialize, serde::Serialize),
330)]
331#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
332pub struct SourceInfo {
333    pub span: lsp_positions::Span,
334    pub syntax_type: Option<String>,
335}
336
337#[derive(Clone, Debug, Eq, PartialEq)]
338#[cfg_attr(
339    feature = "serde",
340    derive(serde::Deserialize, serde::Serialize),
341    serde(transparent)
342)]
343#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
344pub struct DebugInfo {
345    pub data: Vec<DebugEntry>,
346}
347
348#[derive(Clone, Debug, Eq, PartialEq)]
349#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
350#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
351pub struct DebugEntry {
352    pub key: String,
353    pub value: String,
354}
355
356#[derive(Clone, Debug, Eq, PartialEq)]
357#[cfg_attr(
358    feature = "serde",
359    serde_with::skip_serializing_none, // must come before derive
360    derive(serde::Deserialize, serde::Serialize),
361)]
362#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
363pub struct NodeID {
364    pub file: Option<String>,
365    pub local_id: u32,
366}
367
368impl NodeID {
369    pub fn from_node_id(graph: &crate::graph::StackGraph, value: crate::graph::NodeID) -> Self {
370        Self {
371            file: value.file().map(|f| graph[f].to_string()),
372            local_id: value.local_id(),
373        }
374    }
375
376    pub fn to_node_id(
377        &self,
378        graph: &crate::graph::StackGraph,
379    ) -> Result<crate::graph::NodeID, Error> {
380        if let Some(file) = &self.file {
381            let file = graph
382                .get_file(file)
383                .ok_or_else(|| Error::FileNotFound(file.clone()))?;
384            Ok(crate::graph::NodeID::new_in_file(file, self.local_id))
385        } else if self.local_id == crate::graph::JUMP_TO_NODE_ID {
386            Ok(crate::graph::NodeID::jump_to())
387        } else if self.local_id == crate::graph::ROOT_NODE_ID {
388            Ok(crate::graph::NodeID::root())
389        } else {
390            Err(Error::InvalidGlobalNodeID(self.local_id))
391        }
392    }
393
394    pub fn from_node(graph: &crate::graph::StackGraph, handle: Handle<crate::graph::Node>) -> Self {
395        Self::from_node_id(graph, graph[handle].id())
396    }
397
398    pub fn to_node(
399        &self,
400        graph: &mut crate::graph::StackGraph,
401    ) -> Result<Handle<crate::graph::Node>, Error> {
402        let value = self.to_node_id(graph)?;
403        Ok(graph
404            .node_for_id(value)
405            .ok_or_else(|| Error::NodeNotFound(self.clone()))?)
406    }
407}
408
409impl std::fmt::Display for NodeID {
410    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
411        if let Some(file) = &self.file {
412            write!(f, "{}:", file)?;
413        }
414        write!(f, "{}", self.local_id)
415    }
416}
417
418#[derive(Clone, Debug, Default, Eq, PartialEq)]
419#[cfg_attr(
420    feature = "serde",
421    derive(serde::Deserialize, serde::Serialize),
422    serde(transparent)
423)]
424#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
425pub struct Edges {
426    pub data: Vec<Edge>,
427}
428
429#[derive(Clone, Debug, Eq, PartialEq)]
430#[cfg_attr(
431    feature = "serde",
432    serde_with::skip_serializing_none, // must come before derive
433    derive(serde::Deserialize, serde::Serialize),
434)]
435#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
436pub struct Edge {
437    pub source: NodeID,
438    pub sink: NodeID,
439    pub precedence: i32,
440    pub debug_info: Option<DebugInfo>,
441}
442
443impl crate::graph::StackGraph {
444    pub fn to_serializable(&self) -> StackGraph {
445        self.to_serializable_filter(&NoFilter)
446    }
447
448    pub fn to_serializable_filter<'a>(&self, f: &'a dyn Filter) -> StackGraph {
449        crate::serde::StackGraph::from_graph_filter(self, f)
450    }
451
452    fn filter_files<'a>(&self, filter: &'a dyn Filter) -> Files {
453        Files {
454            data: self
455                .iter_files()
456                .filter(|f| filter.include_file(self, f))
457                .map(|f| self[f].name().to_owned())
458                .collect::<Vec<_>>(),
459        }
460    }
461
462    fn filter_node<'a>(&self, _filter: &'a dyn Filter, id: crate::graph::NodeID) -> NodeID {
463        let file = id.file().map(|idx| self[idx].name().to_owned());
464        let local_id = id.local_id();
465        NodeID { file, local_id }
466    }
467
468    fn filter_source_info<'a>(
469        &self,
470        _filter: &'a dyn Filter,
471        handle: Handle<crate::graph::Node>,
472    ) -> Option<SourceInfo> {
473        self.source_info(handle).map(|info| SourceInfo {
474            span: info.span.clone(),
475            syntax_type: info.syntax_type.into_option().map(|ty| self[ty].to_owned()),
476        })
477    }
478
479    fn filter_node_debug_info<'a>(
480        &self,
481        _filter: &'a dyn Filter,
482        handle: Handle<crate::graph::Node>,
483    ) -> Option<DebugInfo> {
484        self.node_debug_info(handle).map(|info| DebugInfo {
485            data: info
486                .iter()
487                .map(|entry| DebugEntry {
488                    key: self[entry.key].to_owned(),
489                    value: self[entry.value].to_owned(),
490                })
491                .collect(),
492        })
493    }
494
495    fn filter_nodes<'a>(&self, filter: &'a dyn Filter) -> Nodes {
496        Nodes {
497            data: self
498                .iter_nodes()
499                .filter(|n| filter.include_node(self, &n))
500                .map(|handle| {
501                    let node = &self[handle];
502                    let id = self.filter_node(filter, node.id());
503                    let source_info = self.filter_source_info(filter, handle);
504                    let debug_info = self.filter_node_debug_info(filter, handle);
505
506                    match node {
507                        crate::graph::Node::DropScopes(_node) => Node::DropScopes {
508                            id,
509                            source_info,
510                            debug_info,
511                        },
512                        crate::graph::Node::JumpTo(_node) => Node::JumpToScope {
513                            id,
514                            source_info,
515                            debug_info,
516                        },
517                        crate::graph::Node::PopScopedSymbol(node) => Node::PopScopedSymbol {
518                            id,
519                            symbol: self[node.symbol].to_owned(),
520                            is_definition: node.is_definition,
521                            source_info,
522                            debug_info,
523                        },
524                        crate::graph::Node::PopSymbol(node) => Node::PopSymbol {
525                            id,
526                            symbol: self[node.symbol].to_owned(),
527                            is_definition: node.is_definition,
528                            source_info,
529                            debug_info,
530                        },
531                        crate::graph::Node::PushScopedSymbol(node) => Node::PushScopedSymbol {
532                            id,
533                            symbol: self[node.symbol].to_owned(),
534                            scope: self.filter_node(filter, node.scope),
535                            is_reference: node.is_reference,
536                            source_info,
537                            debug_info,
538                        },
539                        crate::graph::Node::PushSymbol(node) => Node::PushSymbol {
540                            id,
541                            symbol: self[node.symbol].to_owned(),
542                            is_reference: node.is_reference,
543                            source_info,
544                            debug_info,
545                        },
546                        crate::graph::Node::Root(_node) => Node::Root {
547                            id,
548                            source_info,
549                            debug_info,
550                        },
551                        crate::graph::Node::Scope(node) => Node::Scope {
552                            id,
553                            is_exported: node.is_exported,
554                            source_info,
555                            debug_info,
556                        },
557                    }
558                })
559                .collect::<Vec<_>>(),
560        }
561    }
562
563    fn filter_edges<'a>(&self, filter: &'a dyn Filter) -> Edges {
564        Edges {
565            data: self
566                .iter_nodes()
567                .map(|source| {
568                    self.outgoing_edges(source)
569                        .filter(|e| filter.include_edge(self, &e.source, &e.sink))
570                        .map(|e| Edge {
571                            source: self.filter_node(filter, self[e.source].id()),
572                            sink: self.filter_node(filter, self[e.sink].id()),
573                            precedence: e.precedence,
574                            debug_info: self.filter_edge_debug_info(filter, e.source, e.sink),
575                        })
576                })
577                .flatten()
578                .collect::<Vec<_>>(),
579        }
580    }
581
582    fn filter_edge_debug_info<'a>(
583        &self,
584        _filter: &'a dyn Filter,
585        source_handle: Handle<crate::graph::Node>,
586        sink_handle: Handle<crate::graph::Node>,
587    ) -> Option<DebugInfo> {
588        self.edge_debug_info(source_handle, sink_handle)
589            .map(|info| DebugInfo {
590                data: info
591                    .iter()
592                    .map(|entry| DebugEntry {
593                        key: self[entry.key].to_owned(),
594                        value: self[entry.value].to_owned(),
595                    })
596                    .collect(),
597            })
598    }
599}
stack_graphs/serde/graph.rs

stack_graphs/serde/
graph.rs
