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