1 /********************************************************************** 2 * Copyright (c) 2008, 2014 Technical University Berlin, Germany and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * Stephan Herrmann - Initial API and implementation 13 **********************************************************************/ 14 package org.eclipse.jdt.internal.compiler.util; 15 16 import java.util.Arrays; 17 import java.util.Comparator; 18 19 import org.eclipse.jdt.internal.compiler.lookup.InferenceVariable; 20 import org.eclipse.jdt.internal.compiler.lookup.MethodBinding; 21 import org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding; 22 import org.eclipse.jdt.internal.compiler.lookup.TypeBinding; 23 import org.eclipse.jdt.internal.compiler.lookup.TypeIds; 24 25 /** 26 * Sorting utilities. 27 * Originally developed for the <a href="http://www.eclipse.org/objectteams">Object Teams project</a>. 28 */ 29 public class Sorting { 30 31 /** 32 * Topological sort for types 33 * Guarantee: supertypes come before subtypes. 34 */ sortTypes(ReferenceBinding[] types)35 public static ReferenceBinding[] sortTypes(ReferenceBinding[] types) { 36 int len = types.length; 37 38 ReferenceBinding[] unsorted = new ReferenceBinding[len]; 39 ReferenceBinding[] sorted = new ReferenceBinding[len]; 40 System.arraycopy(types, 0, unsorted, 0, len); 41 42 int o = 0; 43 for(int i=0; i<len; i++) 44 o = sort(unsorted, i, sorted, o); 45 46 return sorted; 47 } 48 // Transfer input[i] and all its supers into output[o] ff. sort(ReferenceBinding[] input, int i, ReferenceBinding[] output, int o)49 private static int sort(ReferenceBinding[] input, int i, 50 ReferenceBinding[] output, int o) 51 { 52 if (input[i] == null) 53 return o; 54 55 ReferenceBinding superclass = input[i].superclass(); 56 o = sortSuper(superclass, input, output, o); 57 58 ReferenceBinding[] superInterfaces = input[i].superInterfaces(); 59 for (int j=0; j<superInterfaces.length; j++) { 60 o = sortSuper(superInterfaces[j], input, output, o); 61 } 62 63 // done with supers, now input[i] can safely be transferred: 64 output[o++] = input[i]; 65 input[i] = null; 66 67 return o; 68 } 69 // if superclass is within the set of types to sort, 70 // transfer it and all its supers to output[o] ff. sortSuper(ReferenceBinding superclass, ReferenceBinding[] input, ReferenceBinding[] output, int o)71 private static int sortSuper(ReferenceBinding superclass, 72 ReferenceBinding[] input, 73 ReferenceBinding[] output, int o) 74 { 75 if (superclass.id != TypeIds.T_JavaLangObject) { 76 // search superclass within input: 77 int j = 0; 78 for(j=0; j<input.length; j++) 79 if (TypeBinding.equalsEquals(input[j], superclass)) 80 break; 81 if (j < input.length) 82 // depth first traversal: 83 o = sort(input, j, output, o); 84 // otherwise assume super was already transferred. 85 } 86 return o; 87 } concreteFirst(MethodBinding[] methods, int length)88 public static MethodBinding[] concreteFirst(MethodBinding[] methods, int length) { 89 if (length == 0 || (length > 0 && !methods[0].isAbstract())) 90 return methods; 91 MethodBinding[] copy = new MethodBinding[length]; 92 int idx = 0; 93 for (int i=0; i<length; i++) 94 if (!methods[i].isAbstract()) 95 copy[idx++] = methods[i]; 96 for (int i=0; i<length; i++) 97 if (methods[i].isAbstract()) 98 copy[idx++] = methods[i]; 99 return copy; 100 } abstractFirst(MethodBinding[] methods, int length)101 public static MethodBinding[] abstractFirst(MethodBinding[] methods, int length) { 102 if (length == 0 || (length > 0 && methods[0].isAbstract())) 103 return methods; 104 MethodBinding[] copy = new MethodBinding[length]; 105 int idx = 0; 106 for (int i=0; i<length; i++) 107 if (methods[i].isAbstract()) 108 copy[idx++] = methods[i]; 109 for (int i=0; i<length; i++) 110 if (!methods[i].isAbstract()) 111 copy[idx++] = methods[i]; 112 return copy; 113 } 114 115 /** Sort inference variables by rank. */ sortInferenceVariables(InferenceVariable[] variables)116 public static void sortInferenceVariables(InferenceVariable[] variables) { 117 Arrays.sort(variables, new Comparator<InferenceVariable>() { 118 @Override 119 public int compare(InferenceVariable iv1, InferenceVariable iv2) { 120 return iv1.rank - iv2.rank; 121 } 122 }); 123 } 124 } 125