org.eclipse.jdt.core/compiler/org/eclipse/objectteams/otdt/internal/core/compiler/util/Sorting.java - objectteams/org.eclipse.objectteams - Git at Google

 /**********************************************************************
  * This file is part of "Object Teams Development Tooling"-Software
  *
  * Copyright 20038 Technical University Berlin, Germany.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
  * which accompanies this distribution, and is available at
  * https://www.eclipse.org/legal/epl-2.0/
  *
  * SPDX-License-Identifier: EPL-2.0
  * $Id: Sorting.java 23417 2010-02-03 20:13:55Z stephan $
  *
  * Please visit http://www.eclipse.org/objectteams for updates and contact.
  *
  * Contributors:
  * Technical University Berlin - Initial API and implementation
  **********************************************************************/
 package org.eclipse.objectteams.otdt.internal.core.compiler.util;

 import java.util.Arrays;
 import java.util.Comparator;

 import org.eclipse.jdt.internal.compiler.ast.TypeDeclaration;
 import org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding;
 import org.eclipse.jdt.internal.compiler.lookup.SourceTypeBinding;
 import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
 import org.eclipse.jdt.internal.compiler.lookup.TypeIds;
 import org.eclipse.objectteams.otdt.core.exceptions.InternalCompilerError;
 import org.eclipse.objectteams.otdt.internal.core.compiler.model.RoleModel;

 /**
  * Sorting utilities.
  *
  * @author stephan
  * @since 1.2.1
  */
 public class Sorting {

 	/**
 	 * Topological sort for member types with depth first search.
 	 * Guarantee: supertypes come before subtypes.
 	 */
 	public static void sortMemberTypes(SourceTypeBinding enclosing) {
 		int len = enclosing.memberTypes.length;

 		ReferenceBinding[] unsorted = new ReferenceBinding[len];
 		ReferenceBinding[] sorted = new ReferenceBinding[len];
 		System.arraycopy(enclosing.memberTypes, 0, unsorted, 0, len);

 		int o = 0;
 		for(int i=0; i<len; i++)
 			o = sort(enclosing, unsorted, i, sorted, o);

 		enclosing.memberTypes = sorted;
 	}
 	// Transfer input[i] and all its supers into output[o] ff.
 	private static int sort(ReferenceBinding enclosing,
 							ReferenceBinding[] input, int i,
 							ReferenceBinding[] output, int o)
 	{
 		if (input[i] == null)
 			return o;

 		ReferenceBinding superclass = input[i].superclass();
 		o = sortSuper(enclosing, superclass, input, output, o);

 		for (ReferenceBinding superIfc : input[i].superInterfaces())
 			o = sortSuper(enclosing, superIfc, input, output, o);

 		// done with supers, now input[i] can safely be transferred:
 		output[o++] = input[i];
 		input[i] = null;

 		return o;
 	}
 	// if superclass is within the set of member types to sort,
 	// transfer it and all its supers to output[o] ff.
 	private static int sortSuper(ReferenceBinding enclosing,
 						  		 ReferenceBinding superclass,
 						  		 ReferenceBinding[] input,
 						  		 ReferenceBinding[] output, int o)
 	{
 		if (   superclass != null // inspecting super of Confined?
 			&& superclass.id != TypeIds.T_JavaLangObject
 			&& TypeBinding.equalsEquals(superclass.enclosingType(), enclosing)) // is super within scope?
 		{
 			// search superclass within input:
 			int j = 0;
 			for(j=0; j<input.length; j++)
 				if (TypeBinding.equalsEquals(input[j], superclass))
 					break;
 			if (j < input.length)
 				// depth first traversal:
 				o = sort(enclosing, input, j, output, o);
 			// otherwise assume super was already transferred.
 		}
 		return o;
 	}

 	// --- similar for role models:

 	public static RoleModel[] sortRoles(RoleModel[] unsorted) {
 		int len = unsorted.length;

 		RoleModel[] sorted = new RoleModel[len];
 		int o = 0;
 		for(int i=0; i<len; i++)
 			o = sort(unsorted, i, sorted, o);
 		// also consider the base hierarchy, but for roles bound to
 		// the same base keep the existing order.
 		Arrays.sort(sorted, new Comparator<RoleModel>() {
 			@Override
 			public int compare(RoleModel o1, RoleModel o2) {
 				ReferenceBinding b1 = o1.getBaseTypeBinding();
 				ReferenceBinding b2 = o2.getBaseTypeBinding();
 				if (TypeBinding.equalsEquals(b1, b2))
 					return 0;
 				if (b1 != null && b1.id != TypeIds.T_JavaLangObject) {
 					if (b2 == null || b2.id == TypeIds.T_JavaLangObject)
 						return 1;
 					if (b1.isCompatibleWith(b2))
 						return 1;
 					if (b2.isCompatibleWith(b1))
 						return -1;
 				} else {
 					if (b2 != null && b2.id != TypeIds.T_JavaLangObject)
 						return -1;
 				}
 				return 0;
 			}
 		});

 		return sorted;
 	}

 	// Transfer input[i] and all its supers into output[o] ff.
 	private static int sort(RoleModel[] input, int i,
 							RoleModel[] output, int o)
 	{
 		if (input[i] == null || input[i].getBinding() == null)
 			return o;

 		ReferenceBinding inBinding = input[i].getBinding();
 		ReferenceBinding superclass = inBinding.superclass();
 		o = sortSuper(superclass, input, output, o);

 		for (ReferenceBinding superIfc : inBinding.superInterfaces())
 			o = sortSuper(superIfc, input, output, o);

 		// done with supers, now input[i] can safely be transferred:
 		output[o++] = input[i];
 		input[i] = null;

 		return o;
 	}
 	// if superclass is within the set of member types to sort,
 	// transfer it and all its supers to output[o] ff.
 	private static int sortSuper(ReferenceBinding superclass,
 						  		 RoleModel[] input,
 						  		 RoleModel[] output, int o)
 	{
 		if (   superclass != null // inspecting super of Confined?
 			&& superclass.id != TypeIds.T_JavaLangObject) // is super within scope?
 		{
 			boolean inScope = false;
 			for (RoleModel rm : input)
 				if (rm != null && TypeBinding.equalsEquals(rm.getBinding(), superclass)) {
 					inScope = true;
 					break;
 				}
 			if (inScope) {

 				// search superclass within input:
 				int j = 0;
 				for(j=0; j<input.length; j++)
 					if (input[j] != null && TypeBinding.equalsEquals(input[j].getBinding(), superclass))
 						break;
 				if (j < input.length)
 					// depth first traversal:
 					o = sort(input, j, output, o);
 				// otherwise assume super was already transferred.
 			}
 		}
 		return o;
 	}

 	/** Apply the sorting from member type bindings to their ASTs, too. */
 	public static void sortMemberTypes(TypeDeclaration typeDeclaration) {
 		if (typeDeclaration.memberTypes == null) return;
 		ReferenceBinding[] bindings = typeDeclaration.binding.memberTypes;
 		TypeDeclaration[] unsorted = typeDeclaration.memberTypes;
 		TypeDeclaration[] newMembers = new TypeDeclaration[unsorted.length];
 		int l = 0;
 		allMembers: for (int i=0; i<bindings.length; i++) {
 			ReferenceBinding current = bindings[i];
 			if (current.isBinaryBinding())
 				continue; // no AST: phantom or reused rofi
 			// find corresponding AST
 			for (int j=0; j<unsorted.length; j++) {
 				if (TypeBinding.equalsEquals(unsorted[j].binding, current)) {
 					newMembers[l++] = unsorted[j];
 					continue allMembers;
 				}
 			}
 			throw new InternalCompilerError("Unmatched member type "+String.valueOf(current.readableName())); //$NON-NLS-1$
 		}
 		if (l<newMembers.length)
 			throw new InternalCompilerError("Not all member types matched: "+l); //$NON-NLS-1$
 		typeDeclaration.memberTypes = newMembers;
 	}
 }
	/**********************************************************************
	* This file is part of "Object Teams Development Tooling"-Software
	*
	* Copyright 20038 Technical University Berlin, Germany.
	*
	* This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License 2.0
	* which accompanies this distribution, and is available at
	* https://www.eclipse.org/legal/epl-2.0/
	*
	* SPDX-License-Identifier: EPL-2.0
	* $Id: Sorting.java 23417 2010-02-03 20:13:55Z stephan $
	*
	* Please visit http://www.eclipse.org/objectteams for updates and contact.
	*
	* Contributors:
	* Technical University Berlin - Initial API and implementation
	**********************************************************************/
	package org.eclipse.objectteams.otdt.internal.core.compiler.util;

	import java.util.Arrays;
	import java.util.Comparator;

	import org.eclipse.jdt.internal.compiler.ast.TypeDeclaration;
	import org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding;
	import org.eclipse.jdt.internal.compiler.lookup.SourceTypeBinding;
	import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
	import org.eclipse.jdt.internal.compiler.lookup.TypeIds;
	import org.eclipse.objectteams.otdt.core.exceptions.InternalCompilerError;
	import org.eclipse.objectteams.otdt.internal.core.compiler.model.RoleModel;

	/**
	* Sorting utilities.
	*
	* @author stephan
	* @since 1.2.1
	*/
	public class Sorting {

	/**
	* Topological sort for member types with depth first search.
	* Guarantee: supertypes come before subtypes.
	*/
	public static void sortMemberTypes(SourceTypeBinding enclosing) {
	int len = enclosing.memberTypes.length;

	ReferenceBinding[] unsorted = new ReferenceBinding[len];
	ReferenceBinding[] sorted = new ReferenceBinding[len];
	System.arraycopy(enclosing.memberTypes, 0, unsorted, 0, len);

	int o = 0;
	for(int i=0; i<len; i++)
	o = sort(enclosing, unsorted, i, sorted, o);

	enclosing.memberTypes = sorted;
	}
	// Transfer input[i] and all its supers into output[o] ff.
	private static int sort(ReferenceBinding enclosing,
	ReferenceBinding[] input, int i,
	ReferenceBinding[] output, int o)
	{
	if (input[i] == null)
	return o;

	ReferenceBinding superclass = input[i].superclass();
	o = sortSuper(enclosing, superclass, input, output, o);

	for (ReferenceBinding superIfc : input[i].superInterfaces())
	o = sortSuper(enclosing, superIfc, input, output, o);

	// done with supers, now input[i] can safely be transferred:
	output[o++] = input[i];
	input[i] = null;

	return o;
	}
	// if superclass is within the set of member types to sort,
	// transfer it and all its supers to output[o] ff.
	private static int sortSuper(ReferenceBinding enclosing,
	ReferenceBinding superclass,
	ReferenceBinding[] input,
	ReferenceBinding[] output, int o)
	{
	if ( superclass != null // inspecting super of Confined?
	&& superclass.id != TypeIds.T_JavaLangObject
	&& TypeBinding.equalsEquals(superclass.enclosingType(), enclosing)) // is super within scope?
	{
	// search superclass within input:
	int j = 0;
	for(j=0; j<input.length; j++)
	if (TypeBinding.equalsEquals(input[j], superclass))
	break;
	if (j < input.length)
	// depth first traversal:
	o = sort(enclosing, input, j, output, o);
	// otherwise assume super was already transferred.
	}
	return o;
	}

	// --- similar for role models:

	public static RoleModel[] sortRoles(RoleModel[] unsorted) {
	int len = unsorted.length;

	RoleModel[] sorted = new RoleModel[len];
	int o = 0;
	for(int i=0; i<len; i++)
	o = sort(unsorted, i, sorted, o);
	// also consider the base hierarchy, but for roles bound to
	// the same base keep the existing order.
	Arrays.sort(sorted, new Comparator<RoleModel>() {
	@Override
	public int compare(RoleModel o1, RoleModel o2) {
	ReferenceBinding b1 = o1.getBaseTypeBinding();
	ReferenceBinding b2 = o2.getBaseTypeBinding();
	if (TypeBinding.equalsEquals(b1, b2))
	return 0;
	if (b1 != null && b1.id != TypeIds.T_JavaLangObject) {
	if (b2 == null \|\| b2.id == TypeIds.T_JavaLangObject)
	return 1;
	if (b1.isCompatibleWith(b2))
	return 1;
	if (b2.isCompatibleWith(b1))
	return -1;
	} else {
	if (b2 != null && b2.id != TypeIds.T_JavaLangObject)
	return -1;
	}
	return 0;
	}
	});

	return sorted;
	}

	// Transfer input[i] and all its supers into output[o] ff.
	private static int sort(RoleModel[] input, int i,
	RoleModel[] output, int o)
	{
	if (input[i] == null \|\| input[i].getBinding() == null)
	return o;

	ReferenceBinding inBinding = input[i].getBinding();
	ReferenceBinding superclass = inBinding.superclass();
	o = sortSuper(superclass, input, output, o);

	for (ReferenceBinding superIfc : inBinding.superInterfaces())
	o = sortSuper(superIfc, input, output, o);

	// done with supers, now input[i] can safely be transferred:
	output[o++] = input[i];
	input[i] = null;

	return o;
	}
	// if superclass is within the set of member types to sort,
	// transfer it and all its supers to output[o] ff.
	private static int sortSuper(ReferenceBinding superclass,
	RoleModel[] input,
	RoleModel[] output, int o)
	{
	if ( superclass != null // inspecting super of Confined?
	&& superclass.id != TypeIds.T_JavaLangObject) // is super within scope?
	{
	boolean inScope = false;
	for (RoleModel rm : input)
	if (rm != null && TypeBinding.equalsEquals(rm.getBinding(), superclass)) {
	inScope = true;
	break;
	}
	if (inScope) {

	// search superclass within input:
	int j = 0;
	for(j=0; j<input.length; j++)
	if (input[j] != null && TypeBinding.equalsEquals(input[j].getBinding(), superclass))
	break;
	if (j < input.length)
	// depth first traversal:
	o = sort(input, j, output, o);
	// otherwise assume super was already transferred.
	}
	}
	return o;
	}

	/** Apply the sorting from member type bindings to their ASTs, too. */
	public static void sortMemberTypes(TypeDeclaration typeDeclaration) {
	if (typeDeclaration.memberTypes == null) return;
	ReferenceBinding[] bindings = typeDeclaration.binding.memberTypes;
	TypeDeclaration[] unsorted = typeDeclaration.memberTypes;
	TypeDeclaration[] newMembers = new TypeDeclaration[unsorted.length];
	int l = 0;
	allMembers: for (int i=0; i<bindings.length; i++) {
	ReferenceBinding current = bindings[i];
	if (current.isBinaryBinding())
	continue; // no AST: phantom or reused rofi
	// find corresponding AST
	for (int j=0; j<unsorted.length; j++) {
	if (TypeBinding.equalsEquals(unsorted[j].binding, current)) {
	newMembers[l++] = unsorted[j];
	continue allMembers;
	}
	}
	throw new InternalCompilerError("Unmatched member type "+String.valueOf(current.readableName())); //$NON-NLS-1$
	}
	if (l<newMembers.length)
	throw new InternalCompilerError("Not all member types matched: "+l); //$NON-NLS-1$
	typeDeclaration.memberTypes = newMembers;
	}
	}