Skip to contentPackage: AnalyzeInheritanceTreesTask$1$1
AnalyzeInheritanceTreesTask$1$1
Coverage
1: package de.fhdw.wtf.walker.tasks;
2:
3: import java.util.HashMap;
4: import java.util.Iterator;
5: import java.util.LinkedList;
6: import java.util.List;
7: import java.util.Map;
8: import java.util.Map.Entry;
9:
10: import de.fhdw.wtf.common.ast.Attribute;
11: import de.fhdw.wtf.common.ast.ConstructorOrOperation;
12: import de.fhdw.wtf.common.ast.Group;
13: import de.fhdw.wtf.common.ast.Model;
14: import de.fhdw.wtf.common.ast.type.AtomicType;
15: import de.fhdw.wtf.common.ast.type.ClassType;
16: import de.fhdw.wtf.common.ast.type.CompositeType;
17: import de.fhdw.wtf.common.ast.type.ListType;
18: import de.fhdw.wtf.common.ast.type.MapType;
19: import de.fhdw.wtf.common.ast.type.ProductType;
20: import de.fhdw.wtf.common.ast.type.SumType;
21: import de.fhdw.wtf.common.ast.type.ThrownType;
22: import de.fhdw.wtf.common.ast.type.Type;
23: import de.fhdw.wtf.common.ast.type.TypeProxy;
24: import de.fhdw.wtf.common.ast.visitor.CompositeTypeVisitorReturn;
25: import de.fhdw.wtf.common.ast.visitor.TypeVisitorReturn;
26: import de.fhdw.wtf.common.exception.walker.TaskException;
27: import de.fhdw.wtf.common.task.TaskExecutor;
28: import de.fhdw.wtf.walker.walker.SimpleWalkerTask;
29:
30: /**
31: * Analyzes the inheritance trees of the given model. Enriches the model with useful information regarding necessary
32: * constructor calls.
33: */
34: public final class AnalyzeInheritanceTreesTask extends SimpleWalkerTask {
35:
36: /**
37: * Used to identify the type Anything.
38: */
39: private static final String ANYTHING = "Anything";
40:
41: /**
42: * Returns a new instance of {@link AnalyzeInheritanceTreesTask}.
43: *
44: * @param model
45: * The model to perform this task on.
46: * @param taskmanager
47: * The executor which performs this task.
48: * @return a new instance of {@link AnalyzeInheritanceTreesTask}
49: */
50: public static AnalyzeInheritanceTreesTask create(final Model model, final TaskExecutor taskmanager) {
51: return new AnalyzeInheritanceTreesTask(model, taskmanager);
52: }
53:
54: /**
55: * Instantiates a new instance of {@link AnalyzeInheritanceTreesTask}.
56: *
57: * @param model
58: * The model to perform this task on.
59: * @param taskmanager
60: * The executor which performs this task.
61: */
62: private AnalyzeInheritanceTreesTask(final Model model, final TaskExecutor taskmanager) {
63: super(model, taskmanager);
64: }
65:
66: /**
67: * Helper class which represents one path along the inheritance-hierarchy of a root class.
68: */
69: private class InheritancePath {
70: /**
71: * Types ordered along this InheritancePath.
72: */
73: private final List<Type> pathElements;
74:
75: /**
76: * Constructs an empty InheritancePath.
77: */
78: private InheritancePath() {
79: this.pathElements = new LinkedList<>();
80: }
81:
82: /**
83: * Constructs an InheritancePath with first as its root.
84: *
85: * @param first
86: * the first element of this path.
87: */
88: InheritancePath(final Type first) {
89: this();
90: this.addElement(first);
91: }
92:
93: /**
94: * Constructs an InheritancePath with firsts as its path elements.
95: *
96: * @param firsts
97: * the path elements for this.
98: */
99: InheritancePath(final List<Type> firsts) {
100: this();
101: this.addElements(firsts);
102: }
103:
104: /**
105: * Constructs an InheritancePath which is identical to firsts.
106: *
107: * @param firsts
108: * the path to copy.
109: */
110: InheritancePath(final InheritancePath firsts) {
111: this(firsts.pathElements);
112: }
113:
114: /**
115: * Adds element to the end of this path.
116: *
117: * @param element
118: * the new end of this path.
119: */
120: void addElement(final Type element) {
121: this.pathElements.add(element);
122: }
123:
124: /**
125: * Adds elements to this path so that these elements remain in the order provided in elements.
126: *
127: * @param elements
128: * the elements added to this.
129: */
130: void addElements(final List<Type> elements) {
131: this.pathElements.addAll(elements);
132: }
133:
134: /**
135: * Returns true if element is also an element of this. False otherwise.
136: *
137: * @param element
138: * to check.
139: * @return true if element is part of this. False otherwise.
140: */
141: boolean contains(final Type element) {
142: return this.pathElements.contains(element);
143: }
144:
145: /**
146: * Returns all elements that this and other have in common. The common elements will be provided the order
147: * provided by this.
148: *
149: * @param other
150: * the path to intersect with.
151: * @return common elements in the order of their existence in this path.
152: */
153: List<Type> intersect(final InheritancePath other) {
154: final List<Type> result = new LinkedList<>();
155: final Iterator<Type> myElements = this.pathElements.iterator();
156: while (myElements.hasNext()) {
157: final Type myElement = myElements.next();
158: if (other.contains(myElement)) {
159: result.add(myElement);
160: }
161: }
162: return result;
163: }
164:
165: /**
166: * Makes one step in the inheritance-tree. Alternative paths will be returned.
167: *
168: * @return alternative paths if any exist. An empty llist otherwise.
169: */
170: List<InheritancePath> step() {
171: final List<InheritancePath> alternativePaths = new LinkedList<>();
172: final Type lastElement = this.pathElements.get(this.pathElements.size() - 1);
173: final Iterator<Type> followers = lastElement.getSuperTypes().iterator();
174: if (followers.hasNext()) {
175: final Type firstFollower = followers.next();
176: while (followers.hasNext()) {
177: final Type follower = followers.next();
178: if (!follower.toString().equals(ANYTHING)) {
179: final InheritancePath alternativePath = new InheritancePath(this);
180: alternativePath.addElement(follower);
181: alternativePaths.add(alternativePath);
182: }
183: }
184: if (!firstFollower.toString().equals(ANYTHING)) {
185: this.addElement(firstFollower);
186: }
187: }
188: return alternativePaths;
189: }
190:
191: /**
192: * Calculates all inheritance paths reachable from the end of this path and returns them.
193: *
194: * @return a list with all paths reachable from the last element of this.
195: */
196: List<InheritancePath> run() {
197: final List<InheritancePath> result = new LinkedList<>();
198: final List<InheritancePath> preResult = new LinkedList<>();
199: int oldSize = this.pathElements.size();
200: List<InheritancePath> alternativePaths = this.step();
201: while (this.pathElements.size() != oldSize || !alternativePaths.isEmpty()) {
202: preResult.addAll(alternativePaths);
203: oldSize = this.pathElements.size();
204: alternativePaths = this.step();
205: }
206: final Iterator<InheritancePath> paths = preResult.iterator();
207: while (paths.hasNext()) {
208: result.addAll(paths.next().run());
209: }
210: result.add(this);
211: return result;
212: }
213:
214: @Override
215: public String toString() {
216: return this.pathElements.toString();
217: }
218:
219: @Override
220: public boolean equals(final Object o) {
221: if (o instanceof InheritancePath) {
222: final InheritancePath oAsInheritancePath = (InheritancePath) o;
223: return this.pathElements.equals(oAsInheritancePath.pathElements);
224: }
225: return false;
226: }
227:
228: @Override
229: public int hashCode() {
230: return this.pathElements.hashCode();
231: }
232:
233: }
234:
235: @Override
236: public void handleClass(final ClassType c) throws TaskException {
237: final List<InheritancePath> allPaths = new LinkedList<>();
238: final Iterator<Type> superTypes = c.getSuperTypes().iterator();
239: while (superTypes.hasNext()) {
240: final Type current = superTypes.next();
241: if (!current.toString().equals(ANYTHING)) {
242: allPaths.addAll(new InheritancePath(current).run());
243: }
244: }
245: this.mapCalls(c, allPaths);
246: }
247:
248: /**
249: * Maps c to all types it has to instantiate during runtime. Uses the map "calls" for this purpose. Maps to an empty
250: * list if c has no responsibilities in the regard of instantiating super types.
251: *
252: * @param c
253: * the root of the inheritance tree to map types from.
254: * @param allPaths
255: * The inheritance tree with c as root in form of all paths that have the direct super types of c as
256: * root.
257: */
258: private void mapCalls(final ClassType c, final List<InheritancePath> allPaths) {
259: final Map<Type, Integer> callPriorities = new HashMap<>();
260: final List<Type> definitiveResponsibilities = new LinkedList<>();
261: final List<InheritancePath> copy = new LinkedList<>();
262: copy.addAll(allPaths);
263: final Iterator<InheritancePath> copyPaths = copy.iterator();
264: while (copyPaths.hasNext()) {
265: final InheritancePath copyPath = copyPaths.next();
266: final Iterator<InheritancePath> paths = allPaths.iterator();
267: while (paths.hasNext()) {
268: final InheritancePath path = paths.next();
269: final List<Type> interception = path.intersect(copyPath);
270: this.gatherResponsibilities(interception, callPriorities, definitiveResponsibilities);
271:
272: }
273: copyPaths.remove();
274: }
275: this.addToCalls(c, definitiveResponsibilities, callPriorities);
276: }
277:
278: /**
279: * Adds all types in definitiveResponsibilities and direct super types of c as list values to the calls map and uses
280: * c as key. Additionally ensures that the order of the elements in the list will be a valid constructor-call-order
281: * when instantiating c.
282: *
283: * @param c
284: * the key to use.
285: * @param definitiveResponsibilities
286: * those classes that c is definitely responsible to call. Every type in this list must also be a key in
287: * callPriorities with a valid value != null;
288: * @param callPriorities
289: * the priorities which are used to determine the call order of the super constructors for c. Will be
290: * empty after a call to this method!
291: */
292: private void addToCalls(final ClassType c,
293: final List<Type> definitiveResponsibilities,
294: final Map<Type, Integer> callPriorities) {
295: final List<Type> callList = new LinkedList<>();
296: if (!definitiveResponsibilities.isEmpty()) {
297: while (!callPriorities.isEmpty()) {
298: final Type max = this.findAndRemoveHighestPathCountType(callPriorities);
299: if (definitiveResponsibilities.contains(max)) {
300: final boolean containedInSumType = this.isSumTypeAndContainedInSumType(c, max);
301: if (!containedInSumType) {
302: callList.add(max);
303: }
304: }
305: }
306: }
307: final Iterator<Type> directSuperTypes = c.getSuperTypes().iterator();
308: while (directSuperTypes.hasNext()) {
309: final Type superType = directSuperTypes.next();
310: if (!superType.toString().equals(ANYTHING) && !definitiveResponsibilities.contains(superType)) {
311: callList.add(superType);
312: }
313: }
314: this.getModel().putConstructorCallDependency(c, callList);
315: }
316:
317: /**
318: * Returns true if c is part of the given type when type is a sum type. Returns false otherwise.
319: *
320: * @param c
321: * a ClassType.
322: * @param type
323: * some type.
324: * @return true if c is part of the given type when type is a sum type. Returns false otherwise.
325: */
326: private boolean isSumTypeAndContainedInSumType(final ClassType c, final Type type) {
327: return type.accept(new TypeVisitorReturn<Boolean>() {
328:
329: @Override
330: public Boolean handle(final AtomicType atomicType) {
331: return false;
332: }
333:
334: @Override
335: public Boolean handle(final CompositeType compositeType) {
336: return compositeType.accept(new CompositeTypeVisitorReturn<Boolean>() {
337:
338: @Override
339: public Boolean handle(final ListType list) {
340: return false;
341: }
342:
343: @Override
344: public Boolean handle(final MapType map) {
345: return false;
346: }
347:
348: @Override
349: public Boolean handle(final ProductType product) {
350: return false;
351: }
352:
353: @Override
354: public Boolean handle(final SumType sum) {
355: return sum.getElements().contains(c);
356: }
357:
358: @Override
359: public Boolean handle(final ThrownType thrownType) {
360: return false;
361: }
362:
363: });
364: }
365:
366: @Override
367: public Boolean handle(final TypeProxy typeProxy) {
368: return AnalyzeInheritanceTreesTask.this.isSumTypeAndContainedInSumType(c, typeProxy.getTarget());
369: }
370:
371: });
372: }
373:
374: /**
375: * Removes the key with the highest integer value as value from callPriorities and returns that key. removes and
376: * returns the first key found if more than one value is at the current maximum. Returns null if callPriorities is
377: * empty.
378: *
379: * @param callPriorities
380: * the map to remove a key from.
381: * @return null if callPriorities is empty. The first key with the highest integer as value found in callPriorities.
382: */
383: private Type findAndRemoveHighestPathCountType(final Map<Type, Integer> callPriorities) {
384: final Iterator<Entry<Type, Integer>> entries = callPriorities.entrySet().iterator();
385: int highestPathCount = 0;
386: Type highestPathCountType = null;
387: while (entries.hasNext()) {
388: final Entry<Type, Integer> entry = entries.next();
389: final int pathCount = entry.getValue();
390: if (pathCount > highestPathCount) {
391: highestPathCount = pathCount;
392: highestPathCountType = entry.getKey();
393: }
394: }
395: callPriorities.remove(highestPathCountType);
396: return highestPathCountType;
397: }
398:
399: /**
400: * Adds all types in intersection to callPriorities and increments the corresponding value for a key by one. Also
401: * adds the first type in intersection to definitiveResponsibilities (no duplicates will be added).
402: *
403: * @param intersection
404: * an intersection of two InheritancePaths.
405: * @param callPriorities
406: * a map with call priorities.
407: * @param definitiveResponsibilities
408: * a list with types that have to be instantiated by a certain sub type.
409: */
410: private void gatherResponsibilities(final List<Type> intersection,
411: final Map<Type, Integer> callPriorities,
412: final List<Type> definitiveResponsibilities) {
413: final Iterator<Type> commonTypes = intersection.iterator();
414: if (commonTypes.hasNext()) {
415: final Type definitiveOne = commonTypes.next();
416: this.addToPriorities(definitiveOne, callPriorities);
417: if (!definitiveResponsibilities.contains(definitiveOne)) {
418: definitiveResponsibilities.add(definitiveOne);
419: }
420: }
421: while (commonTypes.hasNext()) {
422: this.addToPriorities(commonTypes.next(), callPriorities);
423: }
424: }
425:
426: /**
427: * Adds the pair (type,2) to callPriorities if type is not a key of callPriorities. Increments the the value of type
428: * by one if type is a key of callPriorities. The initial value is 2 because it represents the amount of paths a
429: * type has been found in.
430: *
431: * @param type
432: * the key to add/ to find.
433: * @param callPriorities
434: * the map too search in.
435: */
436: private void addToPriorities(final Type type, final Map<Type, Integer> callPriorities) {
437: if (!callPriorities.containsKey(type)) {
438: callPriorities.put(type, 1);
439: }
440: callPriorities.put(type, callPriorities.get(type) + 1);
441: }
442:
443: @Override
444: public void handleGroup(final Group g) throws TaskException {
445: // Nothing to do.
446: }
447:
448: @Override
449: public void handleAttribute(final Attribute a, final ClassType owner) throws TaskException {
450: // Nothing to do.
451: }
452:
453: @Override
454: public void handleConstructorOrOperation(final ConstructorOrOperation coo, final ClassType owner)
455: throws TaskException {
456: // Nothing to do.
457: }
458:
459: @Override
460: public void finalizeTask() throws TaskException {
461: // Nothing to do.
462: }
463:
464: @Override
465: public void beginTask() throws TaskException {
466: // Nothing to do.
467: }
468:
469: }
![[Jenkins]](/jenkins/static/5c0124f8/images/svgs/logo.svg){kind=logo}
