Package: SortDependencies

SortDependencies

nameinstructionbranchcomplexitylinemethod
SortDependencies(LinkedList)
M: 0 C: 23
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 7
100%
M: 0 C: 1
100%
caseAModuleDeclIR(AModuleDeclIR)
M: 0 C: 22
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
init()
M: 0 C: 39
100%
M: 0 C: 4
100%
M: 0 C: 3
100%
M: 0 C: 8
100%
M: 0 C: 1
100%
sortDeps()
M: 0 C: 26
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 7
100%
M: 0 C: 1
100%
visit(SDeclIR, Set, Set)
M: 5 C: 46
90%
M: 1 C: 5
83%
M: 1 C: 3
75%
M: 1 C: 10
91%
M: 0 C: 1
100%

Coverage

1: /*
2: * #%~
3: * The VDM to Isabelle Translator
4: * %%
5: * Copyright (C) 2008 - 2015 Overture
6: * %%
7: * This program is free software: you can redistribute it and/or modify
8: * it under the terms of the GNU General Public License as
9: * published by the Free Software Foundation, either version 3 of the
10: * License, or (at your option) any later version.
11: *
12: * This program is distributed in the hope that it will be useful,
13: * but WITHOUT ANY WARRANTY; without even the implied warranty of
14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15: * GNU General Public License for more details.
16: *
17: * You should have received a copy of the GNU General Public
18: * License along with this program. If not, see
19: * <http://www.gnu.org/licenses/gpl-3.0.html>.
20: * #~%
21: */
22: package org.overturetool.cgisa.transformations;
23:
24: import java.util.HashMap;
25: import java.util.HashSet;
26: import java.util.LinkedList;
27: import java.util.List;
28: import java.util.Map;
29: import java.util.Set;
30: import java.util.Vector;
31:
32: import org.overture.codegen.ir.SDeclIR;
33: import org.overture.codegen.ir.analysis.AnalysisException;
34: import org.overture.codegen.ir.analysis.DepthFirstAnalysisAdaptor;
35: import org.overture.codegen.ir.declarations.AModuleDeclIR;
36:
37: public class SortDependencies extends DepthFirstAnalysisAdaptor
38: {
39:         List<SDeclIR> decls;
40:         Map<SDeclIR, List<SDeclIR>> depGraph;
41:         private List<SDeclIR> sorted;
42:
43:         protected Dependencies depUtils;
44:
45:         public SortDependencies(LinkedList<SDeclIR> linkedList)
46:         {
47:                 this.depUtils = new Dependencies();
48:                 this.depGraph = new HashMap<>();
49:                 this.sorted = new Vector<SDeclIR>();
50:                 this.decls = linkedList;
51:                 init();
52:         }
53:
54:         @Override
55:         public void caseAModuleDeclIR(AModuleDeclIR node) throws AnalysisException
56:         {
57:                 node.getDecls().clear();
58:•                for (SDeclIR d : sorted)
59:                 {
60:                         node.getDecls().add(d.clone());
61:                 }
62:         }
63:
64:         private void init()
65:         {
66:                 this.depGraph = depUtils.calcDepsAsMap(decls);
67:
68:                 // add definitions w/no deps right away (to preserve order)
69:•                for (SDeclIR d : decls)
70:                 {
71:•                        if (depGraph.get(d).isEmpty())
72:                         {
73:                                 sorted.add(d);
74:                                 depGraph.remove(d);
75:                         }
76:                 }
77:                 sortDeps();
78:         }
79:
80:         private void sortDeps()
81:         {
82:                 Set<SDeclIR> unmarked = depGraph.keySet();
83:                 Set<SDeclIR> tempMarks = new HashSet<>();
84:
85:•                while (!unmarked.isEmpty())
86:                 {
87:                         SDeclIR n = unmarked.toArray(new SDeclIR[1])[0];
88:                         visit(n, tempMarks, unmarked);
89:                 }
90:         }
91:
92:         private void visit(SDeclIR n, Set<SDeclIR> tempMarks, Set<SDeclIR> unmarked)
93:         {
94:•                if (tempMarks.contains(n))
95:                 {
96:                         throw new RuntimeException("Cyclic dependency");
97:                 }
98:•                if (unmarked.contains(n))
99:                 {
100:                         tempMarks.add(n);
101:
102:•                        for (SDeclIR d : depGraph.get(n))
103:                         {
104:                                 visit(d, tempMarks, unmarked);
105:                         }
106:                         unmarked.remove(n);
107:                         tempMarks.remove(n);
108:                         sorted.add(n); // we want reverse topological order since its dependencies.
109:                 }
110:         }
111: }