Package: RecursiveLoops

RecursiveLoops

nameinstructionbranchcomplexitylinemethod
RecursiveLoops()
M: 0 C: 9
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 3
100%
M: 0 C: 1
100%
addApplyExp(PDefinition, AApplyExp, PDefinition)
M: 0 C: 32
100%
M: 0 C: 6
100%
M: 0 C: 4
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
addCycle(ILexNameToken, List)
M: 0 C: 28
100%
M: 0 C: 4
100%
M: 0 C: 3
100%
M: 0 C: 9
100%
M: 0 C: 1
100%
getCallMap(ApplyFinder)
M: 1 C: 28
97%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 1 C: 6
86%
M: 0 C: 1
100%
getCycleNames(List)
M: 0 C: 23
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
getCycles(ILexNameToken)
M: 0 C: 6
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
getInstance()
M: 0 C: 8
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 3
100%
M: 0 C: 1
100%
reachable(ILexNameToken, Map)
M: 0 C: 25
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
reachable(ILexNameToken, Set, Map, Stack, Set)
M: 2 C: 75
97%
M: 1 C: 13
93%
M: 1 C: 7
88%
M: 1 C: 20
95%
M: 0 C: 1
100%
reset()
M: 0 C: 11
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 3
100%
M: 0 C: 1
100%
static {...}
M: 0 C: 3
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
typeCheckClasses(List, ITypeCheckerAssistantFactory)
M: 0 C: 89
100%
M: 0 C: 8
100%
M: 0 C: 5
100%
M: 0 C: 17
100%
M: 0 C: 1
100%
typeCheckModules(List, ITypeCheckerAssistantFactory)
M: 0 C: 89
100%
M: 0 C: 8
100%
M: 0 C: 5
100%
M: 0 C: 17
100%
M: 0 C: 1
100%

Coverage

1: /*******************************************************************************
2: *
3: *        Copyright (c) 2019 Nick Battle.
4: *
5: *        Author: Nick Battle
6: *
7: *        This file is part of VDMJ.
8: *
9: *        VDMJ is free software: you can redistribute it and/or modify
10: *        it under the terms of the GNU General Public License as published by
11: *        the Free Software Foundation, either version 3 of the License, or
12: *        (at your option) any later version.
13: *
14: *        VDMJ is distributed in the hope that it will be useful,
15: *        but WITHOUT ANY WARRANTY; without even the implied warranty of
16: *        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17: *        GNU General Public License for more details.
18: *
19: *        You should have received a copy of the GNU General Public License
20: *        along with VDMJ. If not, see <http://www.gnu.org/licenses/>.
21: *
22: ******************************************************************************/
23:
24: package org.overture.typechecker;
25:
26: import java.util.HashMap;
27: import java.util.HashSet;
28: import java.util.List;
29: import java.util.Map;
30: import java.util.Set;
31: import java.util.Stack;
32: import java.util.Vector;
33:
34: import org.overture.ast.analysis.AnalysisException;
35: import org.overture.ast.definitions.AExplicitFunctionDefinition;
36: import org.overture.ast.definitions.AImplicitFunctionDefinition;
37: import org.overture.ast.definitions.PDefinition;
38: import org.overture.ast.definitions.SClassDefinition;
39: import org.overture.ast.expressions.AApplyExp;
40: import org.overture.ast.intf.lex.ILexNameToken;
41: import org.overture.ast.modules.AModuleModules;
42: import org.overture.typechecker.assistant.ITypeCheckerAssistantFactory;
43: import org.overture.typechecker.assistant.definition.SFunctionDefinitionAssistantTC;
44: import org.overture.typechecker.utilities.expression.ApplyFinder;
45:
46: /**
47: * A class to hold recursive loop data, which is used to detect mutual recursion and
48: * missing measure functions.
49: */
50: public class RecursiveLoops
51: {
52:         private static final int LOOP_SIZE_LIMIT = 8;
53:         private static RecursiveLoops INSTANCE = null;
54:
55:         private static class Apply
56:         {
57:                 public final AApplyExp apply;
58:                 public final PDefinition calling;
59:
60:                 public Apply(AApplyExp apply, PDefinition calling)
61:                 {
62:                         this.apply = apply;
63:                         this.calling = calling;
64:                 }
65:         }
66:
67:         private Map<PDefinition, List<Apply>> applymap = null;
68:         private Map<ILexNameToken, List<List<PDefinition>>> recursiveLoops = null;
69:
70:         public static RecursiveLoops getInstance()
71:         {
72:•                if (INSTANCE == null)
73:                 {
74:                         INSTANCE = new RecursiveLoops();
75:                 }
76:
77:                 return INSTANCE;
78:         }
79:
80:         public void reset()
81:         {
82:                 recursiveLoops = new HashMap<ILexNameToken, List<List<PDefinition>>>();
83:                 applymap = new HashMap<PDefinition, List<Apply>>();
84:         }
85:
86:         public void addApplyExp(PDefinition parent, AApplyExp apply, PDefinition calling)
87:         {
88:•                if (calling instanceof AExplicitFunctionDefinition ||
89:                         calling instanceof AImplicitFunctionDefinition)
90:                 {
91:•                        if (!applymap.containsKey(parent))
92:                         {
93:                                 applymap.put(parent, new Vector<Apply>());
94:                         }
95:
96:                         applymap.get(parent).add(new Apply(apply, calling));
97:                 }
98:         }
99:
100:         private Map<ILexNameToken, Set<ILexNameToken>> getCallMap(ApplyFinder finder)
101:         {
102:                 Map<ILexNameToken, Set<ILexNameToken>> callmap = new HashMap<ILexNameToken, Set<ILexNameToken>>();
103:
104:•                for (PDefinition def: applymap.keySet())
105:                 {
106:                         try
107:                         {
108:                                 callmap.put(def.getName(), def.apply(finder));
109:                         }
110:                         catch (AnalysisException e)
111:                         {
112:                                 // doesn't happen
113:                         }
114:                 }
115:
116:                 return callmap;
117:         }
118:
119:         public void typeCheckClasses(List<SClassDefinition> classes, ITypeCheckerAssistantFactory af)
120:         {
121:                 SFunctionDefinitionAssistantTC assistant = af.createSFunctionDefinitionAssistant();
122:                 ApplyFinder finder = new ApplyFinder(assistant);
123:                 finder.setClasses(classes);
124:                 Map<ILexNameToken, Set<ILexNameToken>> callmap = getCallMap(finder);
125:                 recursiveLoops.clear();
126:
127:•                for (ILexNameToken name: callmap.keySet())
128:                 {
129:•                        for (Stack<ILexNameToken> cycle: reachable(name, callmap))
130:                         {
131:                                 addCycle(name, assistant.findClassDefinitions(cycle, classes));
132:                         }
133:                 }
134:
135:•                for (PDefinition parent: applymap.keySet())
136:                 {
137:•                        for (Apply pair: applymap.get(parent))
138:                         {
139:                                 assistant.typeCheckCycles(pair.apply, parent, pair.calling);
140:                         }
141:                 }
142:
143:                 reset();        // save space!
144:         }
145:
146:         public void typeCheckModules(List<AModuleModules> modules, ITypeCheckerAssistantFactory af)
147:         {
148:                 SFunctionDefinitionAssistantTC assistant = af.createSFunctionDefinitionAssistant();
149:                 ApplyFinder finder = new ApplyFinder(assistant);
150:                 finder.setModules(modules);
151:                 Map<ILexNameToken, Set<ILexNameToken>> callmap = getCallMap(finder);
152:                 recursiveLoops.clear();
153:
154:•                for (ILexNameToken name: callmap.keySet())
155:                 {
156:•                        for (Stack<ILexNameToken> cycle: reachable(name, callmap))
157:                         {
158:                                 addCycle(name, assistant.findModuleDefinitions(cycle, modules));
159:                         }
160:                 }
161:
162:•                for (PDefinition parent: applymap.keySet())
163:                 {
164:•                        for (Apply pair: applymap.get(parent))
165:                         {
166:                                 assistant.typeCheckCycles(pair.apply, parent, pair.calling);
167:                         }
168:                 }
169:
170:                 reset();        // save space!
171:         }
172:
173:         private void addCycle(ILexNameToken name, List<PDefinition> defs)
174:         {
175:•                if (defs != null)
176:                 {
177:                         List<List<PDefinition>> existing = getCycles(name);
178:
179:•                        if (existing == null)
180:                         {
181:                                 List<List<PDefinition>> list = new Vector<List<PDefinition>>();
182:                                 list.add(defs);
183:                                 recursiveLoops.put(name, list);
184:                         }
185:                         else
186:                         {
187:                                 existing.add(defs);
188:                         }
189:                 }
190:         }
191:
192:         public List<List<PDefinition>> getCycles(ILexNameToken name)
193:         {
194:                 return recursiveLoops.get(name);
195:         }
196:
197:         public List<String> getCycleNames(List<PDefinition> cycle)
198:         {
199:                 List<String> calls = new Vector<String>();
200:
201:•                for (PDefinition d: cycle)
202:                 {
203:                         calls.add(d.getName().toString());        // ie. include PP param types
204:                 }
205:
206:                 return calls;
207:         }
208:
209:         /**
210:          * Return true if the name sought is reachable via the next set of names passed using
211:          * the dependency map. The stack passed records the path taken to find a cycle.
212:          */
213:         private Set<Stack<ILexNameToken>> reachable(ILexNameToken name,
214:                         Map<ILexNameToken, Set<ILexNameToken>> callmap)
215:         {
216:                 Stack<ILexNameToken> stack = new Stack<ILexNameToken>();
217:                 Set<Stack<ILexNameToken>> loops = new HashSet<Stack<ILexNameToken>>();
218:                 stack.push(name);
219:
220:                 reachable(name, callmap.get(name), callmap, stack, loops);
221:
222:                 return loops;
223:         }
224:
225:         private boolean reachable(ILexNameToken sought, Set<ILexNameToken> nextset,
226:                 Map<ILexNameToken, Set<ILexNameToken>> dependencies, Stack<ILexNameToken> stack,
227:                 Set<Stack<ILexNameToken>> loops)
228:         {
229:•                if (nextset == null)
230:                 {
231:                         return false;
232:                 }
233:
234:                 boolean found = false;
235:
236:•                if (nextset.contains(sought))
237:                 {
238:                         stack.push(sought);
239:                         Stack<ILexNameToken> loop = new Stack<ILexNameToken>();
240:                         loop.addAll(stack);
241:                         loops.add(loop);
242:                         stack.pop();
243:                         found = true;
244:                 }
245:
246:•                if (System.getProperty("skip.recursion.check") != null)
247:                 {
248:                         return found;                // For now, to allow us to skip if there are issues.
249:                 }
250:
251:•                if (stack.size() < LOOP_SIZE_LIMIT)
252:                 {
253:•                        for (ILexNameToken nextname: nextset)
254:                         {
255:•                                if (!stack.contains(nextname))        // Been here before!
256:                                 {
257:                                         stack.push(nextname);
258:                 
259:•                                        if (reachable(sought, dependencies.get(nextname), dependencies, stack, loops))
260:                                         {
261:                                                 found = true;
262:                                         }
263:                 
264:                                         stack.pop();
265:                                 }
266:                         }
267:                 }
268:
269:                 return found;
270:         }
271: }