Skip to contentMethod: hashCode()
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 currentSuperType = superTypes.next();
231: if (!currentSuperType.toString().equals(ANYTHING)) {
232: allPaths.addAll(new InheritancePath(currentSuperType).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<Type> directSuperTypes = c.getSuperTypes();
252: final List<InheritancePath> copy = new LinkedList<>();
253: copy.addAll(allPaths);
254: final Iterator<InheritancePath> copyPaths = copy.iterator();
255: while (copyPaths.hasNext()) {
256: final InheritancePath copyPath = copyPaths.next();
257: final Iterator<InheritancePath> paths = allPaths.iterator();
258: while (paths.hasNext()) {
259: final InheritancePath path = paths.next();
260: final List<Type> intersection = path.intersect(copyPath);
261: this.gatherResponsibilities(directSuperTypes, intersection, callPriorities, definitiveResponsibilities);
262:
263: }
264: copyPaths.remove();
265: }
266: this.addToCalls(c, definitiveResponsibilities, callPriorities);
267: }
268:
269: /**
270: * Adds all types in definitiveResponsibilities and direct super types of c as list values to the calls map and uses
271: * c as key. Additionally ensures that the order of the elements in the list will be a valid constructor-call-order
272: * when instantiating c.
273: *
274: * @param c
275: * the key to use.
276: * @param definitiveResponsibilities
277: * those classes that c is definitely responsible to call. Every type in this list must also be a key in
278: * callPriorities with a valid value != null;
279: * @param callPriorities
280: * the priorities which are used to determine the call order of the super constructors for c. Will be
281: * empty after a call to this method!
282: */
283: private void addToCalls(final ClassType c,
284: final List<Type> definitiveResponsibilities,
285: final Map<Type, Integer> callPriorities) {
286: final List<Type> callList = new LinkedList<>();
287: if (!definitiveResponsibilities.isEmpty()) {
288: while (!callPriorities.isEmpty()) {
289: final Type max = this.findAndRemoveHighestPathCountType(callPriorities);
290: if (definitiveResponsibilities.contains(max)) {
291: callList.add(max);
292: }
293: }
294: }
295: final Iterator<Type> directSuperTypes = c.getSuperTypes().iterator();
296: while (directSuperTypes.hasNext()) {
297: final Type superType = directSuperTypes.next();
298: if (!superType.toString().equals(ANYTHING)) {
299: callList.add(superType);
300: }
301: }
302: this.getModel().putConstructorCallDependency(c, callList);
303: }
304:
305: /**
306: * Removes the key with the highest integer value as value from callPriorities and returns that key. removes and
307: * returns the first key found if more than one value is at the current maximum. Returns null if callPriorities is
308: * empty.
309: *
310: * @param callPriorities
311: * the map to remove a key from.
312: * @return null if callPriorities is empty. The first key with the highest integer as value found in callPriorities.
313: */
314: private Type findAndRemoveHighestPathCountType(final Map<Type, Integer> callPriorities) {
315: final Iterator<Entry<Type, Integer>> entries = callPriorities.entrySet().iterator();
316: int highestPathCount = 0;
317: Type highestPathCountType = null;
318: while (entries.hasNext()) {
319: final Entry<Type, Integer> entry = entries.next();
320: final int pathCount = entry.getValue();
321: if (pathCount > highestPathCount) {
322: highestPathCount = pathCount;
323: highestPathCountType = entry.getKey();
324: }
325: }
326: callPriorities.remove(highestPathCountType);
327: return highestPathCountType;
328: }
329:
330: /**
331: * Adds all types in intersection to callPriorities and increments the corresponding value for a key by one. Also
332: * adds the first type in intersection to definitiveResponsibilities (no duplicates will be added).
333: *
334: * @param intersection
335: * an intersection of two InheritancePaths.
336: * @param interception
337: * @param callPriorities
338: * a map with call priorities.
339: * @param definitiveResponsibilities
340: * a list with types that have to be instantiated by a certain sub type.
341: */
342: private void gatherResponsibilities(final List<Type> directSuperTypes,
343: final List<Type> intersection,
344: final Map<Type, Integer> callPriorities,
345: final List<Type> definitiveResponsibilities) {
346: final Iterator<Type> commonTypes = intersection.iterator();
347: if (commonTypes.hasNext()) {
348: final Type definitiveOne = commonTypes.next();
349: this.addToPriorities(definitiveOne, callPriorities);
350: if (!definitiveResponsibilities.contains(definitiveOne) && !directSuperTypes.contains(definitiveOne)) {
351: definitiveResponsibilities.add(definitiveOne);
352: }
353: }
354: while (commonTypes.hasNext()) {
355: this.addToPriorities(commonTypes.next(), callPriorities);
356: }
357: }
358:
359: /**
360: * Adds the pair (type,2) to callPriorities if type is not a key of callPriorities. Increments the the value of type
361: * by one if type is a key of callPriorities. The initial value is 2 because it represents the amount of paths a
362: * type has been found in.
363: *
364: * @param type
365: * the key to add/ to find.
366: * @param callPriorities
367: * the map too search in.
368: */
369: private void addToPriorities(final Type type, final Map<Type, Integer> callPriorities) {
370: if (!callPriorities.containsKey(type)) {
371: callPriorities.put(type, 1);
372: }
373: callPriorities.put(type, callPriorities.get(type) + 1);
374: }
375:
376: @Override
377: public void handleGroup(final Group g) throws TaskException {
378: // Nothing to do.
379: }
380:
381: @Override
382: public void handleAttribute(final Attribute a, final ClassType owner) throws TaskException {
383: // Nothing to do.
384: }
385:
386: @Override
387: public void handleConstructorOrOperation(final ConstructorOrOperation coo, final ClassType owner)
388: throws TaskException {
389: // Nothing to do.
390: }
391:
392: @Override
393: public void finalizeTask() throws TaskException {
394: // Nothing to do.
395: }
396:
397: @Override
398: public void beginTask() throws TaskException {
399: // Nothing to do.
400: }
401:
402: }
![[Jenkins]](/jenkins/static/5c0124f8/images/svgs/logo.svg){kind=logo}
