go_types/check/
initorder.rs

1// Copyright 2022 The Goscript Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4//
5//
6// This code is adapted from the offical Go code written in Go
7// with license as follows:
8// Copyright 2013 The Go Authors. All rights reserved.
9// Use of this source code is governed by a BSD-style
10// license that can be found in the LICENSE file.
11
12#![allow(dead_code)]
13use crate::SourceRead;
14
15use super::super::objects::{DeclInfoKey, ObjKey, TCObjects};
16use super::check::{Checker, Initializer};
17use super::resolver::DeclInfo;
18use go_parser::Map;
19use std::cell::RefCell;
20use std::collections::HashSet;
21use std::rc::Rc;
22
23#[derive(Debug)]
24struct GraphEdges {
25    pred: Rc<RefCell<HashSet<ObjKey>>>,
26    succ: Rc<RefCell<HashSet<ObjKey>>>,
27}
28
29struct GraphNode {
30    obj: ObjKey,
31    ndeps: usize,
32    pos: usize,
33}
34
35impl GraphEdges {
36    fn new(succ: Rc<RefCell<HashSet<ObjKey>>>) -> GraphEdges {
37        GraphEdges {
38            pred: Rc::new(RefCell::new(HashSet::new())),
39            succ: succ,
40        }
41    }
42}
43
44impl<'a, S: SourceRead> Checker<'a, S> {
45    pub fn init_order(&mut self) {
46        let (mut nodes, edges) = self.dependency_graph();
47        nodes.sort_by(|a, b| a.ndeps.cmp(&b.ndeps)); // sort by n_deps
48        let len = nodes.len();
49        let mut nodes = &mut nodes[0..len];
50        let mut order: Vec<ObjKey> = vec![];
51        let mut emitted: HashSet<DeclInfoKey> = HashSet::new();
52
53        loop {
54            if nodes.len() == 0 {
55                break;
56            }
57            let mut first_dependant = nodes
58                .iter()
59                .enumerate()
60                .find(|(_, n)| n.ndeps > 0)
61                .map_or(nodes.len(), |(i, _)| i);
62            if first_dependant == 0 {
63                // we have a cycle with the first node
64                let visited = &mut HashSet::new();
65                let obj = nodes[0].obj;
66                // If obj is not part of the cycle (e.g., obj->b->c->d->c),
67                // cycle will be nil. Don't report anything in that case since
68                // the cycle is reported when the algorithm gets to an object
69                // in the cycle.
70                // Furthermore, once an object in the cycle is encountered,
71                // the cycle will be broken (dependency count will be reduced
72                // below), and so the remaining nodes in the cycle don't trigger
73                // another error (unless they are part of multiple cycles).
74                if let Some(cycle) = find_path(&self.obj_map, obj, obj, visited, self.tc_objs) {
75                    self.report_cycle(&cycle);
76                }
77                // Ok to continue, but the variable initialization order
78                // will be incorrect at this point since it assumes no
79                // cycle errors.
80                // set first_dependant to 1 to remove the first node,
81                first_dependant = 1;
82            }
83
84            let mut indep: Vec<ObjKey> = nodes[0..first_dependant].iter().map(|n| n.obj).collect();
85            indep.sort_by(|a, b| self.lobj(*a).order().cmp(&self.lobj(*b).order()));
86            order.append(&mut indep);
87
88            // reduce dependency count of all dependent nodes
89            let to_sub: Map<ObjKey, usize> =
90                nodes[0..first_dependant]
91                    .iter()
92                    .fold(Map::new(), |mut init, x| {
93                        for p in edges[&x.obj].pred.borrow().iter() {
94                            *init.entry(*p).or_insert(0) += 1;
95                        }
96                        init
97                    });
98            // remove resolved nodes
99            nodes = &mut nodes[first_dependant..];
100            for n in nodes.iter_mut() {
101                n.ndeps -= *to_sub.get(&n.obj).unwrap_or(&0);
102            }
103            // sort nodes, shoud be fast as it's almost sorted
104            nodes.sort_by(|a, b| a.ndeps.cmp(&b.ndeps));
105        }
106
107        // record the init order for variables with initializers only
108        let init_order = order
109            .into_iter()
110            .filter_map(|x| {
111                let decl_key = self.obj_map[&x];
112                match &self.tc_objs.decls[decl_key] {
113                    DeclInfo::Var(var) => {
114                        if var.init.is_none() {
115                            return None;
116                        }
117                        // n:1 variable declarations such as: a, b = f()
118                        // introduce a node for each lhs variable (here: a, b);
119                        // but they all have the same initializer - emit only
120                        // one, for the first variable seen
121                        if emitted.contains(&decl_key) {
122                            return None;
123                        }
124                        emitted.insert(decl_key);
125                        let lhs = var.lhs.clone().unwrap_or(vec![x]);
126                        Some(Initializer {
127                            lhs: lhs,
128                            rhs: var.init.clone().unwrap(),
129                        })
130                    }
131                    _ => None,
132                }
133            })
134            .collect();
135        self.result.record_init_order(init_order);
136    }
137
138    /// dependency_graph returns the object dependency graph from the given obj_map,
139    /// with any function nodes removed. The resulting graph contains only constants
140    /// and variables.
141    fn dependency_graph(&self) -> (Vec<GraphNode>, Map<ObjKey, GraphEdges>) {
142        // map is the dependency (Object) -> graphNode mapping
143        let map: Map<ObjKey, GraphEdges> = self.obj_map.iter().fold(
144            Map::new(),
145            |mut init: Map<ObjKey, GraphEdges>, (&x, &decl_key)| {
146                if self.lobj(x).entity_type().is_dependency() {
147                    let decl = &self.tc_objs.decls[decl_key];
148                    let deps: HashSet<ObjKey> = decl.deps().iter().map(|z| *z).collect();
149                    init.insert(x, GraphEdges::new(Rc::new(RefCell::new(deps))));
150                }
151                init
152            },
153        );
154
155        // add the edges for the other direction
156        for (o, node) in map.iter() {
157            for s in node.succ.borrow().iter() {
158                map[s].pred.borrow_mut().insert(*o);
159            }
160        }
161
162        // remove function nodes and collect remaining graph nodes in graph
163        // (Mutually recursive functions may introduce cycles among themselves
164        // which are permitted. Yet such cycles may incorrectly inflate the dependency
165        // count for variables which in turn may not get scheduled for initialization
166        // in correct order.)
167        let mut nodes: Vec<GraphNode> = map
168            .iter()
169            .filter_map(|(o, node)| {
170                if self.lobj(*o).entity_type().is_func() {
171                    for p in node.pred.borrow().iter() {
172                        if p != o {
173                            for s in node.succ.borrow().iter() {
174                                if s != o {
175                                    map[p].succ.borrow_mut().insert(*s);
176                                    map[s].pred.borrow_mut().insert(*p);
177                                    map[s].pred.borrow_mut().remove(o);
178                                }
179                            }
180                            map[p].succ.borrow_mut().remove(o);
181                        }
182                    }
183                    None
184                } else {
185                    Some(GraphNode {
186                        obj: *o,
187                        ndeps: node.succ.borrow().len(),
188                        pos: self.lobj(*o).pos(),
189                    })
190                }
191            })
192            .collect();
193
194        nodes.sort_by(|a, b| a.pos.cmp(&b.pos)); // sort by pos
195        (nodes, map)
196    }
197
198    fn report_cycle(&self, cycle: &Vec<ObjKey>) {
199        let o = self.lobj(cycle[0]);
200        self.error(o.pos(), format!("initialization cycle for {}", o.name()));
201        self.error(o.pos(), format!("\t{} refers to", o.name()));
202        for okey in cycle[1..].iter().rev() {
203            let o = self.lobj(*okey);
204            self.error(o.pos(), format!("\t{} refers to", o.name()));
205        }
206        let o = self.lobj(cycle[0]);
207        self.error(o.pos(), format!("\t{}", o.name()));
208    }
209}
210
211/// find_path returns the (reversed) list of objects Vec<ObjKey>{to, ... from}
212/// such that there is a path of object dependencies from 'from' to 'to'.
213/// If there is no such path, the result is None.
214fn find_path(
215    map: &Map<ObjKey, DeclInfoKey>,
216    from: ObjKey,
217    to: ObjKey,
218    visited: &mut HashSet<ObjKey>,
219    tc_objs: &TCObjects,
220) -> Option<Vec<ObjKey>> {
221    if visited.contains(&from) {
222        return None;
223    }
224    visited.insert(from);
225
226    let decl = &tc_objs.decls[map[&from]];
227    for &d in decl.deps().iter() {
228        if d == to {
229            return Some(vec![d]);
230        }
231        if let Some(mut p) = find_path(map, d, to, visited, tc_objs) {
232            p.push(d);
233            return Some(p);
234        }
235    }
236    None
237}
go_types/check/initorder.rs

go_types/check/
initorder.rs
