veryl_analyzer/
type_dag.rs

1use crate::AnalyzerError;
2use crate::namespace::Namespace;
3use crate::namespace_table;
4use crate::symbol::{ParameterKind, Symbol, SymbolId, SymbolKind};
5use crate::symbol_path::{GenericSymbolPath, GenericSymbolPathNamespace, SymbolPath};
6use crate::symbol_table;
7use crate::{HashMap, HashSet};
8use bimap::BiMap;
9use daggy::petgraph::visit::Dfs;
10use daggy::{Dag, NodeIndex, Walker, petgraph::algo};
11use std::cell::RefCell;
12use veryl_parser::resource_table::PathId;
13use veryl_parser::veryl_token::Token;
14
15#[derive(Clone, Debug)]
16pub enum TypeDagCandidate {
17    Path {
18        path: Box<GenericSymbolPath>,
19        namespace: Namespace,
20        project_namespace: Namespace,
21        parent: Option<(SymbolId, Context)>,
22    },
23    Symbol {
24        id: SymbolId,
25        context: Context,
26        project_namespace: Namespace,
27        parent: Option<(SymbolId, Context)>,
28        import: Vec<GenericSymbolPathNamespace>,
29    },
30}
31
32impl TypeDagCandidate {
33    pub fn set_parent(&mut self, x: (SymbolId, Context)) {
34        match self {
35            TypeDagCandidate::Path { parent, .. } => {
36                *parent = Some(x);
37            }
38            TypeDagCandidate::Symbol { parent, .. } => {
39                *parent = Some(x);
40            }
41        }
42    }
43}
44
45#[derive(Clone, Default)]
46pub struct TypeDag {
47    dag: Dag<(), Context, u32>,
48    /// One-to-one relation between SymbolId and DAG NodeIdx
49    nodes: BiMap<SymbolId, u32>,
50    /// Map between NodeIdx and Symbol Resolve Information
51    paths: HashMap<u32, TypeResolveInfo>,
52    symbols: HashMap<u32, Symbol>,
53    source: u32,
54    candidates: Vec<TypeDagCandidate>,
55    errors: Vec<DagError>,
56    dag_owned: HashMap<u32, HashSet<u32>>,
57    file_dag: Dag<(), (), u32>,
58    file_nodes: BiMap<PathId, u32>,
59}
60
61#[derive(Clone, Debug)]
62pub struct TypeResolveInfo {
63    pub symbol_id: SymbolId,
64    pub name: String,
65    pub token: Token,
66}
67
68#[derive(Default, Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq)]
69pub enum Context {
70    #[default]
71    Irrelevant,
72    Struct,
73    Union,
74    Enum,
75    Function,
76    TypeDef,
77    Const,
78    Alias,
79    Module,
80    Interface,
81    Package,
82    Modport,
83    GenericInstance,
84    Embed,
85}
86
87#[derive(Debug, Clone)]
88pub enum DagError {
89    Cyclic(Box<Symbol>, Box<Symbol>),
90}
91
92impl From<DagError> for AnalyzerError {
93    fn from(value: DagError) -> Self {
94        let DagError::Cyclic(s, e) = value;
95        AnalyzerError::cyclic_type_dependency(
96            &s.token.to_string(),
97            &e.token.to_string(),
98            &e.token.into(),
99        )
100    }
101}
102
103impl TypeDag {
104    #[allow(dead_code)]
105    fn new() -> Self {
106        let mut dag = Dag::<(), Context, u32>::new();
107        let source = dag.add_node(()).index() as u32;
108        Self {
109            dag,
110            nodes: BiMap::new(),
111            paths: HashMap::default(),
112            symbols: HashMap::default(),
113            source,
114            candidates: Vec::new(),
115            errors: Vec::new(),
116            dag_owned: HashMap::default(),
117            file_dag: Dag::new(),
118            file_nodes: BiMap::new(),
119        }
120    }
121
122    fn add(&mut self, cand: TypeDagCandidate) {
123        self.candidates.push(cand);
124    }
125
126    fn apply(&mut self) -> Vec<AnalyzerError> {
127        symbol_table::suppress_cache_clear();
128        let candidates: Vec<_> = self.candidates.drain(..).collect();
129
130        // Process symbol declarations at first to construct dag_owned
131        for cand in &candidates {
132            if let TypeDagCandidate::Symbol {
133                id,
134                context,
135                project_namespace,
136                parent,
137                import,
138            } = cand
139                && let Some(symbol) = symbol_table::get(*id)
140                && let Some(child) = self.insert_declaration_symbol(&symbol, parent)
141            {
142                for x in import {
143                    if let Ok(import) = symbol_table::resolve(x)
144                        && let Some(import) = self.insert_symbol(&import.found)
145                    {
146                        self.insert_dag_edge(child, import, *context, false);
147                    }
148                }
149
150                for map in symbol.generic_maps() {
151                    for arg_path in map.map.values() {
152                        // insert edge between given generic arg and base symbol
153                        self.insert_path(
154                            arg_path,
155                            &symbol.namespace,
156                            project_namespace,
157                            &Some((*id, *context)),
158                        );
159                    }
160                }
161            }
162        }
163
164        // Process symbol references using dag_owned
165        for cand in &candidates {
166            if let TypeDagCandidate::Path {
167                path,
168                namespace,
169                project_namespace,
170                parent,
171            } = cand
172            {
173                self.insert_path(path, namespace, project_namespace, parent);
174            }
175        }
176
177        symbol_table::resume_cache_clear();
178        self.errors.drain(..).map(|x| x.into()).collect()
179    }
180
181    fn insert_path(
182        &mut self,
183        path: &GenericSymbolPath,
184        namespace: &Namespace,
185        project_namespace: &Namespace,
186        parent: &Option<(SymbolId, Context)>,
187    ) {
188        namespace_table::set_default(&project_namespace.paths);
189
190        let mut path = path.clone();
191        path.resolve_imported(namespace, None);
192
193        for i in 0..path.len() {
194            let Some(base_symbol) =
195                Self::resolve_symbol_path(&path.slice(i).generic_path(), namespace)
196            else {
197                continue;
198            };
199
200            if let Some((parent_symbol, parent_context)) =
201                parent.map(|(id, context)| (symbol_table::get(id).unwrap(), context))
202            {
203                if !base_symbol.namespace.included(&parent_symbol.namespace) {
204                    let (parent_symbol, parent_context) =
205                        if let Some(symbol) = parent_symbol.get_parent_component() {
206                            let context = if symbol.is_module(true) {
207                                Context::Module
208                            } else if symbol.is_interface(true) {
209                                Context::Interface
210                            } else {
211                                Context::Package
212                            };
213                            (symbol, context)
214                        } else {
215                            (parent_symbol, parent_context)
216                        };
217                    let base_symbol = if let Some(symbol) = base_symbol.get_parent_component() {
218                        symbol
219                    } else {
220                        base_symbol
221                    };
222                    let recursive_ref = namespace.included(&base_symbol.inner_namespace());
223                    self.insert_path_symbols(
224                        &parent_symbol,
225                        parent_context,
226                        &base_symbol,
227                        recursive_ref,
228                    );
229                } else {
230                    let recursive_ref = namespace.included(&base_symbol.inner_namespace());
231                    self.insert_path_symbols(
232                        &parent_symbol,
233                        parent_context,
234                        &base_symbol,
235                        recursive_ref,
236                    );
237                }
238            } else {
239                self.insert_symbol(&base_symbol);
240            }
241        }
242    }
243
244    fn resolve_symbol_path(path: &SymbolPath, namespace: &Namespace) -> Option<Symbol> {
245        let symbol = symbol_table::resolve((path, namespace)).ok()?;
246        if let Some(alias_path) = symbol.found.alias_target(false) {
247            // alias referenced as generic arg for generic instance put on the same namespace
248            // causes cyclic dependency error.
249            // https://github.com/veryl-lang/veryl/blob/52b46337148340b43f8ab1c8f2ab67f58cd3c943/crates/analyzer/src/tests.rs#L3740-L3743
250            // Need to use the target symbol of the alias instead of it to prevent this situation.
251            Self::resolve_symbol_path(&alias_path.generic_path(), &symbol.found.namespace)
252        } else {
253            Some((*symbol.found).clone())
254        }
255    }
256
257    fn insert_path_symbols(
258        &mut self,
259        parent_symbol: &Symbol,
260        parent_context: Context,
261        base_symbol: &Symbol,
262        recursive_ref: bool,
263    ) {
264        let Some(base) = self.insert_symbol(base_symbol) else {
265            return;
266        };
267        if let Some(parent) = self.insert_symbol(parent_symbol)
268            && !self.is_dag_owned(parent, base)
269        {
270            self.insert_dag_edge(parent, base, parent_context, recursive_ref);
271        }
272    }
273
274    fn insert_symbol(&mut self, symbol: &Symbol) -> Option<u32> {
275        let is_dag_symbol = match symbol.kind {
276            SymbolKind::Module(_)
277            | SymbolKind::AliasModule(_)
278            | SymbolKind::Interface(_)
279            | SymbolKind::AliasInterface(_)
280            | SymbolKind::Modport(_)
281            | SymbolKind::Package(_)
282            | SymbolKind::AliasPackage(_)
283            | SymbolKind::Enum(_)
284            | SymbolKind::TypeDef(_)
285            | SymbolKind::Struct(_)
286            | SymbolKind::Union(_)
287            | SymbolKind::Function(_)
288            | SymbolKind::Test(_)
289            | SymbolKind::Embed => true,
290            SymbolKind::Parameter(ref x) => matches!(x.kind, ParameterKind::Const),
291            _ => false,
292        };
293        if !is_dag_symbol {
294            return None;
295        }
296
297        let name = symbol.token.to_string();
298        match self.insert_node(symbol.id, &name) {
299            Ok(n) => Some(n),
300            Err(x) => {
301                self.errors.push(x);
302                None
303            }
304        }
305    }
306
307    fn insert_declaration_symbol(
308        &mut self,
309        symbol: &Symbol,
310        parent: &Option<(SymbolId, Context)>,
311    ) -> Option<u32> {
312        if let Some(child) = self.insert_symbol(symbol) {
313            if let Some(parent) = parent {
314                let parent_symbol = symbol_table::get(parent.0).unwrap();
315                let parent_context = parent.1;
316                if let Some(parent) = self.insert_symbol(&parent_symbol) {
317                    self.insert_dag_owned(parent, child);
318                    self.insert_dag_edge(child, parent, parent_context, false);
319                }
320            }
321            Some(child)
322        } else {
323            None
324        }
325    }
326
327    fn insert_dag_edge(&mut self, parent: u32, child: u32, context: Context, recursive_ref: bool) {
328        // Reversing this order to make traversal work
329        if let Err(x) = self.insert_edge(child, parent, context, recursive_ref) {
330            self.errors.push(x);
331        }
332    }
333
334    fn insert_dag_owned(&mut self, parent: u32, child: u32) {
335        // If there is already edge to owned type, remove it.
336        // Argument order should be the same as insert_edge.
337        if self.exist_edge(child, parent) {
338            self.remove_edge(child, parent);
339        }
340        self.dag_owned.entry(parent).or_default().insert(child);
341    }
342
343    fn is_dag_owned(&self, parent: u32, child: u32) -> bool {
344        if let Some(owned) = self.dag_owned.get(&parent) {
345            owned.contains(&child)
346        } else {
347            false
348        }
349    }
350
351    fn insert_node(&mut self, symbol_id: SymbolId, name: &str) -> Result<u32, DagError> {
352        let symbol = symbol_table::get(symbol_id).unwrap();
353        let trinfo = TypeResolveInfo {
354            symbol_id,
355            name: name.into(),
356            token: symbol.token,
357        };
358        if let Some(node_index) = self.nodes.get_by_left(&symbol_id) {
359            Ok(*node_index)
360        } else {
361            if let Some(path) = symbol.token.source.get_path() {
362                let file_node = self.file_dag.add_node(()).index() as u32;
363                self.file_nodes.insert(path, file_node);
364            }
365
366            let node_index = self.dag.add_node(()).index() as u32;
367            self.insert_edge(self.source, node_index, Context::Irrelevant, false)?;
368            self.nodes.insert(symbol_id, node_index);
369            self.paths.insert(node_index, trinfo);
370            self.symbols.insert(node_index, symbol);
371            Ok(node_index)
372        }
373    }
374
375    fn get_symbol(&self, node: u32) -> Symbol {
376        match self.symbols.get(&node) {
377            Some(x) => x.clone(),
378            None => {
379                panic!("Must insert node before accessing");
380            }
381        }
382    }
383
384    fn insert_edge(
385        &mut self,
386        start: u32,
387        end: u32,
388        edge: Context,
389        recursive_ref: bool,
390    ) -> Result<(), DagError> {
391        match self.dag.add_edge(start.into(), end.into(), edge) {
392            Ok(_) => {
393                self.insert_file_edge(start, end);
394                Ok(())
395            }
396            Err(_) => {
397                let is_allowed_direct_reference = match edge {
398                    Context::Module | Context::Interface | Context::Function => {
399                        // Direct recursion of module/interface/function is allowed
400                        start == end
401                    }
402                    Context::Package => {
403                        // Self reference given as generic arg
404                        start == end && !recursive_ref
405                    }
406                    _ => false,
407                };
408                if is_allowed_direct_reference {
409                    Ok(())
410                } else {
411                    let ssym = self.get_symbol(start);
412                    let esym = self.get_symbol(end);
413                    Err(DagError::Cyclic(Box::new(ssym), Box::new(esym)))
414                }
415            }
416        }
417    }
418
419    fn insert_file_edge(&mut self, start: u32, end: u32) {
420        if start != self.source {
421            let start = self.get_symbol(start);
422            let end = self.get_symbol(end);
423            if let (Some(start), Some(end)) =
424                (start.token.source.get_path(), end.token.source.get_path())
425            {
426                let start = self.file_nodes.get_by_left(&start).unwrap();
427                let end = self.file_nodes.get_by_left(&end).unwrap();
428                let start: NodeIndex = (*start).into();
429                let end: NodeIndex = (*end).into();
430                if start != end && self.file_dag.find_edge(start, end).is_none() {
431                    let err = self.file_dag.add_edge(start, end, ());
432                    // cyclic error should be caught by dag
433                    err.unwrap();
434                }
435            }
436        }
437    }
438
439    fn exist_edge(&self, start: u32, end: u32) -> bool {
440        self.dag.find_edge(start.into(), end.into()).is_some()
441    }
442
443    fn remove_edge(&mut self, start: u32, end: u32) {
444        while let Some(x) = self.dag.find_edge(start.into(), end.into()) {
445            self.dag.remove_edge(x);
446        }
447    }
448
449    fn toposort(&self) -> Vec<Symbol> {
450        let nodes = algo::toposort(self.dag.graph(), None).unwrap();
451        let mut ret = vec![];
452        for node in nodes {
453            let index = node.index() as u32;
454            if self.paths.contains_key(&index) {
455                let sym = self.get_symbol(index);
456                ret.push(sym);
457            }
458        }
459        ret
460    }
461
462    fn connected_components(&self) -> Vec<Vec<Symbol>> {
463        let mut ret = Vec::new();
464        let mut graph = self.dag.graph().clone();
465
466        // Reverse edge to traverse nodes which are called from parent node
467        graph.reverse();
468
469        for node in self.symbols.keys() {
470            let mut connected = Vec::new();
471            let mut dfs = Dfs::new(&graph, (*node).into());
472            while let Some(x) = dfs.next(&graph) {
473                let index = x.index() as u32;
474                if self.paths.contains_key(&index) {
475                    let symbol = self.get_symbol(index);
476                    connected.push(symbol);
477                }
478            }
479            if !connected.is_empty() {
480                ret.push(connected);
481            }
482        }
483
484        ret
485    }
486
487    fn dependent_files(&self) -> HashMap<PathId, Vec<PathId>> {
488        let mut ret = HashMap::default();
489        let graph = self.file_dag.graph().clone();
490
491        for node in self.file_nodes.right_values() {
492            let mut dependents = Vec::new();
493            let mut dfs = Dfs::new(&graph, (*node).into());
494            while let Some(x) = dfs.next(&graph) {
495                let index = x.index() as u32;
496                if index != *node
497                    && let Some(x) = self.file_nodes.get_by_right(&index)
498                {
499                    dependents.push(*x);
500                }
501            }
502            if !dependents.is_empty()
503                && let Some(x) = self.file_nodes.get_by_right(node)
504            {
505                ret.insert(*x, dependents);
506            }
507        }
508
509        ret
510    }
511
512    fn dump(&self) -> String {
513        let mut nodes = algo::toposort(self.dag.graph(), None).unwrap();
514        let mut ret = "".to_string();
515
516        nodes.sort_by_key(|x| {
517            let idx = x.index() as u32;
518            if let Some(path) = self.paths.get(&idx) {
519                path.name.clone()
520            } else {
521                "".to_string()
522            }
523        });
524
525        let mut max_width = 0;
526        for node in &nodes {
527            let idx = node.index() as u32;
528            if let Some(path) = self.paths.get(&idx) {
529                max_width = max_width.max(path.name.len());
530                for parent in self.dag.parents(*node).iter(&self.dag) {
531                    let node = parent.1.index() as u32;
532                    if let Some(path) = self.paths.get(&node) {
533                        max_width = max_width.max(path.name.len() + 4);
534                    }
535                }
536            }
537        }
538
539        for node in &nodes {
540            let idx = node.index() as u32;
541            if let Some(path) = self.paths.get(&idx) {
542                let symbol = self.symbols.get(&idx).unwrap();
543                ret.push_str(&format!(
544                    "{}{} : {}\n",
545                    path.name,
546                    " ".repeat(max_width - path.name.len()),
547                    symbol.kind
548                ));
549                let mut set = HashSet::default();
550                for parent in self.dag.parents(*node).iter(&self.dag) {
551                    let node = parent.1.index() as u32;
552                    if !set.contains(&node) {
553                        set.insert(node);
554                        if let Some(path) = self.paths.get(&node) {
555                            let symbol = self.symbols.get(&node).unwrap();
556                            ret.push_str(&format!(
557                                " |- {}{} : {}\n",
558                                path.name,
559                                " ".repeat(max_width - path.name.len() - 4),
560                                symbol.kind
561                            ));
562                        }
563                    }
564                }
565            }
566        }
567        ret
568    }
569
570    fn dump_file(&self) -> String {
571        let nodes = algo::toposort(self.file_dag.graph(), None).unwrap();
572        let mut ret = "".to_string();
573
574        for node in &nodes {
575            let idx = node.index() as u32;
576            if let Some(path) = self.file_nodes.get_by_right(&idx) {
577                ret.push_str(&format!("{path}\n"));
578                for parent in self.file_dag.parents(*node).iter(&self.file_dag) {
579                    let idx = parent.1.index() as u32;
580                    if let Some(path) = self.file_nodes.get_by_right(&idx) {
581                        ret.push_str(&format!(" |- {path}\n"));
582                    }
583                }
584            }
585        }
586        ret
587    }
588
589    fn clear(&mut self) {
590        self.clone_from(&Self::new());
591    }
592}
593
594thread_local!(static TYPE_DAG: RefCell<TypeDag> = RefCell::new(TypeDag::new()));
595
596pub fn add(cand: TypeDagCandidate) {
597    TYPE_DAG.with(|f| f.borrow_mut().add(cand))
598}
599
600pub fn apply() -> Vec<AnalyzerError> {
601    TYPE_DAG.with(|f| f.borrow_mut().apply())
602}
603
604pub fn toposort() -> Vec<Symbol> {
605    TYPE_DAG.with(|f| f.borrow().toposort())
606}
607
608pub fn connected_components() -> Vec<Vec<Symbol>> {
609    TYPE_DAG.with(|f| f.borrow().connected_components())
610}
611
612pub fn dependent_files() -> HashMap<PathId, Vec<PathId>> {
613    TYPE_DAG.with(|f| f.borrow().dependent_files())
614}
615
616pub fn dump() -> String {
617    TYPE_DAG.with(|f| f.borrow().dump())
618}
619
620pub fn dump_file() -> String {
621    TYPE_DAG.with(|f| f.borrow().dump_file())
622}
623
624pub fn clear() {
625    TYPE_DAG.with(|f| f.borrow_mut().clear())
626}
veryl_analyzer/type_dag.rs

veryl_analyzer/
type_dag.rs
