de.dhbwstuttgart.typeinference.unify

Class Unify

java.lang.Object

de.dhbwstuttgart.typeinference.unify.Unify

public class Unify
extends java.lang.Object

Implementierung des Unifizierungsalgorithmus

Version:

$Date: 2013/05/22 22:23:50 $

Author:

Martin Pl�micke, Thomas Ott

Field Summary

Fields

Modifier and Type	Field and Description
protected static SectionLogger	inferencelog

Constructor Summary

Constructors

Constructor and Description
Unify()

Method Summary

Modifier and Type	Method and Description
private static void	adapt(Menge<Pair> H, Pair PFC, RefType TA1, RefType TA2, FC_TTO fc_tto) Implementiert die adapt Regel des sub_unify
private static void	adaptExt(Menge<Pair> H, Pair PFC, RefType TA1, RefType TA2, FC_TTO fc_tto) Implementiert die adaptExt Regel des sub_unify
private static void	adaptSup(Menge<Pair> H, Pair PFC, RefType TA1, RefType TA2, FC_TTO fc_tto) Implementiert die adaptSup Regel des sub_unify
static Menge<RefType>	allGreater(RefType ty, Menge<Pair> FC)
static Menge<RefType>	allSmaller(RefType ty, Menge<Pair> FC)
private static Menge<ObjectType>	CaptureConversion(Menge<ObjectType> TVec, FC_TTO fc_tto) Implementiert die CaptureConversion.
private static Type	CaptureConversion(Type T, FC_TTO fc_tto) Erzeugt die CaptureConversion von einem Typ.
private static java.util.Hashtable<JavaClassName,Type>	CaptureConversionHashtable(java.util.Hashtable<JavaClassName,Type> ht, FC_TTO fc_tto)
private static Menge<Menge<Pair>>	cartProductPair(Menge<Menge<Pair>> vec) Überladung der Funktion cartProductPair, damit der Programmierer beim ersten Aufruf nicht den 2.
private static Menge<Menge<Pair>>	cartProductPair(Menge<Menge<Pair>> vec, int index) Erzeugt das Kartesische Product von mehreren Mengeen von Paaren.
private static Menge<Menge<Type>>	cartProductType(Menge<Menge<Type>> vec) Überladung der Funktion cartProductType, damit der Programmierer beim ersten Aufruf nicht den 2.
private static Menge<Menge<Type>>	cartProductType(Menge<Menge<Type>> vec, int index) Erzeugt das Kartesische Product von mehreren Mengeen von Typen.
static Menge<Menge<Pair>>	copyMengeMengePair(Menge<Menge<Pair>> vp)
private static Menge<ObjectType>	copyMengeObjectType(Menge<ObjectType> vec) Kopiert einen Menge.
static Menge<Pair>	copyMengePair(Menge<Pair> vp)
private static Menge<Type>	copyMengeType(Menge<? extends Type> vec) Kopiert einen Menge.
private static boolean	DelFreshWildcardTypeVar(Type T) Gibt True zurück, wenn T eine FreshWildcard ist, oder im Falle eines RefTypes oder WildcardTypes eine FreshWildcard enthält.
private static Menge<Menge<Pair>>	generateSetOfSetOfPair(Type TA1, Menge<? extends Type> otherPairTypes) Diese Methode generiert einen Menge> wobei immer der übergebene TA1 vorne steht, und jeder Typ aus otherPairTypes hinten.
private static Menge<ObjectType>	greater(ObjectType T, FC_TTO fc_tto) Erzeugt alle Typen die greater sind als T.
private static Menge<ObjectType>	greater0(ObjectType T, FC_TTO fc_tto) greater0 Schritt von greater.
private static Menge<ObjectType>	greater1(ObjectType T, FC_TTO fc_tto) greater1 Schritt von greater.
private static Menge<ObjectType>	greater2(Menge<ObjectType> greater1Erg, FC_TTO fc_tto) greater2 Schritt von greater
private static Menge<ObjectType>	greater3(Menge<ObjectType> greater2Erg, FC_TTO fc_tto) greater3 Schritt von greater
private static Menge<Type>	greaterArg(Type T, FC_TTO fc_tto) greaterArg Schritt von greater Für den Argumenttype FunN<...> werden keine ?
static boolean	hasSolvedForm(Menge<Pair> E)
static Menge<Menge<Pair>>	instanceSmaller(Pair P, FC_TTO fc_tto)
static Pair	isInFC(RefType R1, RefType R2, Menge<Pair> FC)
private static Pair	isInFClinks(RefType RT1, RefType RT2, Menge<Pair> FC)
static Pair	isInFCrechtsUnify(RefType RT1, RefType RT2, FC_TTO fc_tto)
static boolean	isRealSubClass(java.lang.String Basis, java.lang.String Mutter, FC_TTO fc_tto)
static boolean	isRXSimilarRY(RefType RFC, RefType RY, boolean allowTPH)
static boolean	isTVinRefType(TypePlaceholder TV, RefType RT)
static java.util.Hashtable	match(RefType FCtype, RefType tomatch, java.util.Hashtable<JavaClassName,Type> ht)
static java.util.Hashtable<JavaClassName,Type>	MengePair2SubstHashtableMengePair(Menge<Pair> v)
static int	pi(int n, java.lang.String C, java.lang.String D, Menge tto)
static void	printMenge(java.lang.String strMenge, Menge<Pair> E, int nDebug)
static void	printMengeUnifier(java.lang.String strMenge, Menge<Menge<Pair>> Uni, int nDebug)
private static void	reduce1(Menge<Pair> H, RefType TA1, RefType TA2, Menge TTO) Implementiert die reduce1 Regel des sub_unify
private static void	reduce2(Menge<Pair> H, RefType TA1, RefType TA2, Menge TTO) Implementiert die reduce2 Regel des sub_unify
private static void	reduceEq(Menge<Pair> H, RefType TA1, RefType TA2, Menge TTO) Implementiert die reduceEq Regel des sub_unify Da in reduce2 unnötigerweise pi verwendet wird (siehe Kommentar in reduce2), kann reduceEq einfach an reduce2 deligieren.
private static void	reduceExt(Menge<Pair> H, RefType TA1, RefType TA2, Menge TTO) Implementiert die reduceExt Regel des sub_unify
private static void	reduceSup(Menge<Pair> H, RefType TA1, RefType TA2, Menge TTO) Implementiert die reduceSup Regel des sub_unify
static Menge<Menge<java.lang.Integer>>	schnitt(Menge<Menge<TypePlaceholder>> vars) Bildet Schnittmengen der Mengen von Typeplaceholders Rueckgabe ist die Menge der Menge von Indizies die Schnittmengen sind.
(package private) static Menge<java.lang.Integer>	schnitt1(Menge<TypePlaceholder> var, Menge<Menge<TypePlaceholder>> vars, Menge<java.lang.Integer> indexe) PL 2014-10-25 schnitt1 checkt ob die Typeplaceholders aus in den Elemeneten aus vars enthalten sind Rückgabe ist die Menge der Indizies von vars der Schnittmengen mit var nicht leer sind.
private static Menge<ObjectType>	smaller(ObjectType T, FC_TTO fc_tto) Erzeugt alle Typen die smaller sind als T.
private static Menge<ObjectType>	smaller0(ObjectType T, FC_TTO fc_tto) smaller0 Schritt von smaller
private static Menge<ObjectType>	smaller1(Type T, FC_TTO fc_tto) smaller1 Schritt von smaller
private static Menge<ObjectType>	smaller2(Menge<ObjectType> smaller1Erg, FC_TTO fc_tto) smaller2 Schritt von smaller
private static Menge<ObjectType>	smaller3(Menge<ObjectType> smaller12Erg, FC_TTO fc_tto) smaller3 Schritt von smaller
private static Menge<ObjectType>	smaller4(Menge<ObjectType> smallerErg) smaller4 Schritt von smaller
private static Menge<Type>	smallerArg(Type T, FC_TTO fc_tto) smallerArg Schritt von smaller
static Menge<Pair>	sub_unify(Menge<Pair> E, FC_TTO fc_tto)
static Menge<Pair>	sub_unify(Menge<Pair> E, FC_TTO fc_tto, boolean useSubst)
static boolean	Subst(Pair P, int nTypnrInPair, TypePlaceholder a, Type o, boolean bMitVorbedingung)
static void	SubstHashtable(RefType typterm, java.util.Hashtable<JavaClassName,Type> ht)
static Menge<Pair>	SubstHashtable2MengePair(java.util.Hashtable<JavaClassName,Type> ht)
static void	SubstHashtableGeneric(RefType typterm, java.util.Hashtable<JavaClassName,Type> ht)
private static void	testUnifyErg(Menge<Menge<Pair>> unifyErgs, RefType test) Diese Methode wird verwendet, um Zuordnungen z.B.
static MUB	unify_Mub(Type ty1, Type ty2, FC_TTO fc_tto)
static Menge<Menge<Pair>>	unify(Menge<Pair> E, FC_TTO fc_tto) Einstieg in die Unifizierung mit Wildcards
static Menge<Menge<Pair>>	unify(Type ty1, Type ty2, FC_TTO fc_tto) Unifiziert ein Pair mit den Elementen ty1 und ty2 -> (ty1 < ty2)
static Menge<Menge<Pair>>	unifyFiltered(Menge<Pair> E, FC_TTO fc_tto, boolean filter)
static Menge<Menge<Pair>>	unifyWC(Pair P, FC_TTO fc_tto) Einstieg in die Unifizierung mit Wildcards
static Menge<Menge<Pair>>	unifyWC(Type ty1, Type ty2, FC_TTO fc_tto) Einstieg in die Unifizierung mit Wildcards
static void	varSubst(RefType typterm, java.util.Hashtable<JavaClassName,Type> ht)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

inferencelog

protected static SectionLogger inferencelog

Constructor Detail

Unify

public Unify()

Method Detail

unify

public static Menge<Menge<Pair>> unify(Type ty1,
                                       Type ty2,
                                       FC_TTO fc_tto)

Unifiziert ein Pair mit den Elementen ty1 und ty2 -> (ty1 < ty2)

Parameters:

ty1 -

ty2 -

fc_tto -

Returns:

unifyWC

public static Menge<Menge<Pair>> unifyWC(Type ty1,
                                         Type ty2,
                                         FC_TTO fc_tto)

Einstieg in die Unifizierung mit Wildcards

Parameters:

ty1 - - Typ 1 der Unifizierung

ty2 - - Typ 2 der Unifizierung

fc_tto - - Hilfsklasse mit FC

Returns:

Menge> - Ergebnispaare

unifyWC

public static Menge<Menge<Pair>> unifyWC(Pair P,
                                         FC_TTO fc_tto)

Einstieg in die Unifizierung mit Wildcards

Parameters:

P - - Paar das unifiziert werden soll.

fc_tto - - Hilfsklasse mit FC

Returns:

Menge> - Ergebnispaare

unify

public static Menge<Menge<Pair>> unify(Menge<Pair> E,
                                       FC_TTO fc_tto)

Einstieg in die Unifizierung mit Wildcards

Parameters:

E - - Menge von Paaren die unifiziert werden sollen

fc_tto - - Hilfsklasse mit FC

Returns:

Menge> - Ergebnispaare Entweder alle Elemente in solved Form [A =. type, B =. type2, ...] oder alle Elemente in der Form [A <. B, C <. D, ..., E in Typ A ...> werden keine ? extends-, ? super-Typen erzeugt

unifyFiltered

public static Menge<Menge<Pair>> unifyFiltered(Menge<Pair> E,
                                               FC_TTO fc_tto,
                                               boolean filter)

schnitt1

static Menge<java.lang.Integer> schnitt1(Menge<TypePlaceholder> var,
                                         Menge<Menge<TypePlaceholder>> vars,
                                         Menge<java.lang.Integer> indexe)

PL 2014-10-25 schnitt1 checkt ob die Typeplaceholders aus in den Elemeneten aus vars enthalten sind Rückgabe ist die Menge der Indizies von vars der Schnittmengen mit var nicht leer sind.

Parameters:

var -

vars -

indexe -

Returns:

schnitt

public static Menge<Menge<java.lang.Integer>> schnitt(Menge<Menge<TypePlaceholder>> vars)

Bildet Schnittmengen der Mengen von Typeplaceholders Rueckgabe ist die Menge der Menge von Indizies die Schnittmengen sind.

Parameters:

vars -

Returns:

testUnifyErg

private static void testUnifyErg(Menge<Menge<Pair>> unifyErgs,
                                 RefType test)

Diese Methode wird verwendet, um Zuordnungen z.B. TPH a = Integer aus der Ergebnismenge zu entfernen, wenn im Typ in den die eingesetzt werden sollen kein TPH a vorhanden ist. Beispiel: unifyERgs = [[a = Integer, b = Number ]], test = Menge In diesm fall wird b = Number aus dem Menge entfernt. Durch das Entfernen entstehen evtl. Identische Mengeen, diese werden auch gelöscht.

Parameters:

unifyErgs - - Ergebnisse des Unify, die geprüft werden sollen.

test - - RefType gegen den geprüft werden soll.

generateSetOfSetOfPair

private static Menge<Menge<Pair>> generateSetOfSetOfPair(Type TA1,
                                                         Menge<? extends Type> otherPairTypes)

Diese Methode generiert einen Menge> wobei immer der übergebene TA1 vorne steht, und jeder Typ aus otherPairTypes hinten. Beispiel: otherPairTypes = [Integer, Number, Menge], TA1 = TPH a. return: [[TPH a = Integer],[TPH a = Number],[TPH a = Menge]]

Parameters:

TA1 - - Der Typ der immer vorne steht

otherPairTypes - - Die anderen Typen

Returns:

- Ein Menge> der alle Paare enthält.

unify_Mub

public static MUB unify_Mub(Type ty1,
                            Type ty2,
                            FC_TTO fc_tto)
                     throws CTypeReconstructionException

Throws:

CTypeReconstructionException

match

public static java.util.Hashtable match(RefType FCtype,
                                        RefType tomatch,
                                        java.util.Hashtable<JavaClassName,Type> ht)
                                 throws MatchException

Throws:

MatchException

sub_unify

public static Menge<Pair> sub_unify(Menge<Pair> E,
                                    FC_TTO fc_tto)

sub_unify

public static Menge<Pair> sub_unify(Menge<Pair> E,
                                    FC_TTO fc_tto,
                                    boolean useSubst)

reduce1

private static void reduce1(Menge<Pair> H,
                            RefType TA1,
                            RefType TA2,
                            Menge TTO)
                     throws SCException

Implementiert die reduce1 Regel des sub_unify

Throws:

SCException

reduceExt

private static void reduceExt(Menge<Pair> H,
                              RefType TA1,
                              RefType TA2,
                              Menge TTO)
                       throws SCException

Implementiert die reduceExt Regel des sub_unify

Throws:

SCException

reduceSup

private static void reduceSup(Menge<Pair> H,
                              RefType TA1,
                              RefType TA2,
                              Menge TTO)
                       throws SCException

Implementiert die reduceSup Regel des sub_unify

Throws:

SCException

reduceEq

private static void reduceEq(Menge<Pair> H,
                             RefType TA1,
                             RefType TA2,
                             Menge TTO)
                      throws SCException

Implementiert die reduceEq Regel des sub_unify Da in reduce2 unnötigerweise pi verwendet wird (siehe Kommentar in reduce2), kann reduceEq einfach an reduce2 deligieren.

Throws:

SCException

reduce2

private static void reduce2(Menge<Pair> H,
                            RefType TA1,
                            RefType TA2,
                            Menge TTO)
                     throws SCException

Implementiert die reduce2 Regel des sub_unify

Throws:

SCException

adapt

private static void adapt(Menge<Pair> H,
                          Pair PFC,
                          RefType TA1,
                          RefType TA2,
                          FC_TTO fc_tto)

Implementiert die adapt Regel des sub_unify

adaptExt

private static void adaptExt(Menge<Pair> H,
                             Pair PFC,
                             RefType TA1,
                             RefType TA2,
                             FC_TTO fc_tto)

Implementiert die adaptExt Regel des sub_unify

adaptSup

private static void adaptSup(Menge<Pair> H,
                             Pair PFC,
                             RefType TA1,
                             RefType TA2,
                             FC_TTO fc_tto)

Implementiert die adaptSup Regel des sub_unify

CaptureConversionHashtable

private static java.util.Hashtable<JavaClassName,Type> CaptureConversionHashtable(java.util.Hashtable<JavaClassName,Type> ht,
                                                                                  FC_TTO fc_tto)

isInFClinks

private static Pair isInFClinks(RefType RT1,
                                RefType RT2,
                                Menge<Pair> FC)

isRXSimilarRY

public static boolean isRXSimilarRY(RefType RFC,
                                    RefType RY,
                                    boolean allowTPH)

SubstHashtable2MengePair

public static Menge<Pair> SubstHashtable2MengePair(java.util.Hashtable<JavaClassName,Type> ht)

MengePair2SubstHashtableMengePair

public static java.util.Hashtable<JavaClassName,Type> MengePair2SubstHashtableMengePair(Menge<Pair> v)

copyMengePair

public static Menge<Pair> copyMengePair(Menge<Pair> vp)

copyMengeMengePair

public static Menge<Menge<Pair>> copyMengeMengePair(Menge<Menge<Pair>> vp)

instanceSmaller

public static Menge<Menge<Pair>> instanceSmaller(Pair P,
                                                 FC_TTO fc_tto)

allSmaller

public static Menge<RefType> allSmaller(RefType ty,
                                        Menge<Pair> FC)

allGreater

public static Menge<RefType> allGreater(RefType ty,
                                        Menge<Pair> FC)

isInFC

public static Pair isInFC(RefType R1,
                          RefType R2,
                          Menge<Pair> FC)

isInFCrechtsUnify

public static Pair isInFCrechtsUnify(RefType RT1,
                                     RefType RT2,
                                     FC_TTO fc_tto)

isTVinRefType

public static boolean isTVinRefType(TypePlaceholder TV,
                                    RefType RT)

Subst

public static boolean Subst(Pair P,
                            int nTypnrInPair,
                            TypePlaceholder a,
                            Type o,
                            boolean bMitVorbedingung)

SubstHashtableGeneric

public static void SubstHashtableGeneric(RefType typterm,
                                         java.util.Hashtable<JavaClassName,Type> ht)

SubstHashtable

public static void SubstHashtable(RefType typterm,
                                  java.util.Hashtable<JavaClassName,Type> ht)

isRealSubClass

public static boolean isRealSubClass(java.lang.String Basis,
                                     java.lang.String Mutter,
                                     FC_TTO fc_tto)

pi

public static int pi(int n,
                     java.lang.String C,
                     java.lang.String D,
                     Menge tto)
              throws SCException

Throws:

SCException

printMengeUnifier

public static void printMengeUnifier(java.lang.String strMenge,
                                     Menge<Menge<Pair>> Uni,
                                     int nDebug)

printMenge

public static void printMenge(java.lang.String strMenge,
                              Menge<Pair> E,
                              int nDebug)

hasSolvedForm

public static boolean hasSolvedForm(Menge<Pair> E)

varSubst

public static void varSubst(RefType typterm,
                            java.util.Hashtable<JavaClassName,Type> ht)

CaptureConversion

private static Menge<ObjectType> CaptureConversion(Menge<ObjectType> TVec,
                                                   FC_TTO fc_tto)

Implementiert die CaptureConversion. Wendet diese auf jeden Typ im Menge TVec an. Rückgabe ist ein ErgebnisMenge

CaptureConversion

private static Type CaptureConversion(Type T,
                                      FC_TTO fc_tto)

Erzeugt die CaptureConversion von einem Typ.

Parameters:

T - - Übergebener Typ, von welchem die CaptureConversion gemacht werden soll.

fc_tto - - Hilfsklasse.

Returns:

- CC(T)

greater

private static Menge<ObjectType> greater(ObjectType T,
                                         FC_TTO fc_tto)

Erzeugt alle Typen die greater sind als T. Gibt diese zurück. Für den Argumenttype FunN<...> in Typ A ...> werden keine ? extends-, ? super-Typen erzeugt

greater0

private static Menge<ObjectType> greater0(ObjectType T,
                                          FC_TTO fc_tto)

greater0 Schritt von greater.

greater1

private static Menge<ObjectType> greater1(ObjectType T,
                                          FC_TTO fc_tto)

greater1 Schritt von greater. Für den Argumenttype FunN<...> in Typ A ...> werden keine ? extends-, ? super-Typen erzeugt

cartProductType

private static Menge<Menge<Type>> cartProductType(Menge<Menge<Type>> vec)

Überladung der Funktion cartProductType, damit der Programmierer beim ersten Aufruf nicht den 2. Parameter welcher für die rekursion erforderlich ist mit übergeben muss.

cartProductType

private static Menge<Menge<Type>> cartProductType(Menge<Menge<Type>> vec,
                                                  int index)

Erzeugt das Kartesische Product von mehreren Mengeen von Typen. Für den Startaufruf ist der index = 0. Danach ruft sich cartProductType rekursiv auf.

cartProductPair

private static Menge<Menge<Pair>> cartProductPair(Menge<Menge<Pair>> vec)

Überladung der Funktion cartProductPair, damit der Programmierer beim ersten Aufruf nicht den 2. Parameter welcher für die rekursion erforderlich ist mit übergeben muss.

cartProductPair

private static Menge<Menge<Pair>> cartProductPair(Menge<Menge<Pair>> vec,
                                                  int index)

Erzeugt das Kartesische Product von mehreren Mengeen von Paaren. Für den Startaufruf ist der index = 0. Danach ruft sich cartProductPair rekursiv auf.

copyMengeType

private static Menge<Type> copyMengeType(Menge<? extends Type> vec)

Kopiert einen Menge. Es ist eine Deep Copy, da die Elemente auch kopiert werden.

copyMengeObjectType

private static Menge<ObjectType> copyMengeObjectType(Menge<ObjectType> vec)

Kopiert einen Menge. Es ist eine Deep Copy, da die Elemente auch kopiert werden. noetig wegen Type-Erasure

greaterArg

private static Menge<Type> greaterArg(Type T,
                                      FC_TTO fc_tto)

greaterArg Schritt von greater Für den Argumenttype FunN<...> werden keine ? extends-, ? super-Typen erzeugt

greater2

private static Menge<ObjectType> greater2(Menge<ObjectType> greater1Erg,
                                          FC_TTO fc_tto)

greater2 Schritt von greater

greater3

private static Menge<ObjectType> greater3(Menge<ObjectType> greater2Erg,
                                          FC_TTO fc_tto)

greater3 Schritt von greater

smaller

private static Menge<ObjectType> smaller(ObjectType T,
                                         FC_TTO fc_tto)

Erzeugt alle Typen die smaller sind als T. Gibt diese zurück.

smaller0

private static Menge<ObjectType> smaller0(ObjectType T,
                                          FC_TTO fc_tto)

smaller0 Schritt von smaller

smaller1

private static Menge<ObjectType> smaller1(Type T,
                                          FC_TTO fc_tto)

smaller1 Schritt von smaller

smallerArg

private static Menge<Type> smallerArg(Type T,
                                      FC_TTO fc_tto)

smallerArg Schritt von smaller

smaller2

private static Menge<ObjectType> smaller2(Menge<ObjectType> smaller1Erg,
                                          FC_TTO fc_tto)

smaller2 Schritt von smaller

smaller3

private static Menge<ObjectType> smaller3(Menge<ObjectType> smaller12Erg,
                                          FC_TTO fc_tto)

smaller3 Schritt von smaller

smaller4

private static Menge<ObjectType> smaller4(Menge<ObjectType> smallerErg)

smaller4 Schritt von smaller

DelFreshWildcardTypeVar

private static boolean DelFreshWildcardTypeVar(Type T)

Gibt True zurück, wenn T eine FreshWildcard ist, oder im Falle eines RefTypes oder WildcardTypes eine FreshWildcard enthält.