001    package AST;
002    
003    import java.util.HashSet;
004    import java.io.File;
005    import java.util.*;
006    import beaver.*;
007    import java.util.ArrayList;
008    import java.util.zip.*;
009    import java.io.*;
010    import java.io.FileNotFoundException;
011    import java.util.Collection;
012    /**
013      * @ast class
014     * 
015     */
016    public class GLBTypeFactory extends java.lang.Object {
017    
018            // TODO add support for array types.
019            public static TypeDecl glb(final ArrayList typeList) {
020                TypeDecl retType = ((TypeDecl) typeList.get(0)).unknownType();
021                TypeDecl cls = mostSpecificSuperClass(typeList);
022                if (cls != null) {
023                    ArrayList intersectInterfaceList = new ArrayList();
024                    ArrayList allInterfaceList = new ArrayList();
025                    for (Iterator itera = typeList.iterator(); itera.hasNext();) {
026                        TypeDecl typeDecl = (TypeDecl) itera.next();
027                        addInterfaces(intersectInterfaceList, allInterfaceList, typeDecl);
028                    }
029    
030                    // remove all interfaces that are not most specific.
031                    greatestLowerBounds(intersectInterfaceList);
032                    // check for interface compatibility.
033                    if (checkInterfaceCompatibility(allInterfaceList)
034                            && checkClassInterfaceCompatibility(cls, intersectInterfaceList)) {
035                        greatestLowerBounds(typeList);
036                        if(typeList.size() == 1) {
037                          retType = (TypeDecl)typeList.iterator().next();
038                        }
039                        else {
040                          retType = retType.lookupGLBType(typeList);
041                        }
042                    }
043                }
044                return retType;
045            }
046    
047    
048    
049            /**
050             * @param intersectInterfaceList
051             * @param allInterfaceList
052             * @param typeDecl
053             */
054            private static void addInterfaces(ArrayList intersectInterfaceList, ArrayList allInterfaceList, TypeDecl typeDecl) {
055                if(typeDecl.isInterfaceDecl()) {
056                    intersectInterfaceList.add((InterfaceDecl)typeDecl);
057                    allInterfaceList.add((InterfaceDecl)typeDecl);
058                }
059                else if (typeDecl instanceof TypeVariable) {
060                    TypeVariable varTD = (TypeVariable)typeDecl;
061                    // add the interfaces created for type variables to
062                    // interface list to be checked for compatibility
063                    intersectInterfaceList.add(varTD.toInterface());
064                    // add the bounds of the type variable that are interfaces.
065                    allInterfaceList.addAll(varTD.implementedInterfaces());
066                }
067                else if (typeDecl instanceof LUBType) {
068                    allInterfaceList.addAll(typeDecl.implementedInterfaces());
069                }
070                else if (typeDecl instanceof GLBType) {
071                    allInterfaceList.addAll(typeDecl.implementedInterfaces());
072                }
073            }
074    
075    
076    
077            /**
078             * See JLS section 4.9 about Intersection Types
079             * <p>
080             * For each <i>T<sub>i</sub></i>, 1 &le; i &le; n, let <i>C<sub>i</sub></i>
081             * be the most specific class or array type such that <i>T<sub>i</sub></i>
082             * &lt;: <i>C<sub>i</sub></i> Then there must be some <i>T<sub>k</sub></i>
083             * &lt;: <i>C<sub>k</sub></i> such that <i>C<sub>k</sub></i> &lt;:
084             * <i>C<sub>i</sub></i> for any <i>i</i>, 1 &le; i &le; n, or a
085             * compile-time error occurs.
086             * 
087             * @param types
088             * @return the most specific class that all elements in <i>types</i> are a
089             *         subtype of. Or null if no such class exists.
090             */
091            public final static TypeDecl mostSpecificSuperClass(final ArrayList types) {
092                ArrayList csList = new ArrayList();
093                for(Iterator iter = types.iterator(); iter.hasNext(); ) {
094                  csList.add(mostSpecificSuperClass((TypeDecl)iter.next()));
095                }
096    
097                // find Tk with Ck
098                greatestLowerBounds(csList);
099                if(csList.size() == 1) {
100                    // OK
101                    return (TypeDecl) csList.get(0);
102                }
103                else {
104                    // Ck does not exist.
105                    return null;
106                }
107            }
108    
109    
110    
111            /**
112             * Return most specific superclass of t.
113             * 
114             * @param t
115             * @return most specific superclass of t
116             */
117            private final static TypeDecl mostSpecificSuperClass(final TypeDecl t) {
118                HashSet superTypes = new HashSet();
119                addSuperClasses(t, superTypes);
120    
121                if (superTypes.isEmpty())
122                    return t.typeObject();
123    
124                ArrayList result = new ArrayList(superTypes.size());
125                result.addAll(superTypes);
126                greatestLowerBounds(result);
127    
128                if (result.size() == 1)
129                    return (TypeDecl) result.get(0);
130                else
131                    return (TypeDecl) t.typeObject();
132            }
133    
134    
135    
136            /**
137             * Add the superclasses (<i>C<sub>i</sub></i>) of <i>t</i> to the set
138             * <i>result</i>.
139             * <ul>
140             * <li>If <i>t</i> is a class, then <i>C<sub>i</sub></i> is t itself.</li>
141             * <li>If <i>t</i> is a type variable, then <i>C<sub>i</sub></i> is the
142             * first class encountered in it bounds</li>
143             * <li>It <i>t</i> is an intersection type, then <i>C<sub>i</sub></i>
144             * is class that is a member of the intersection, otherwise it's Object</li>
145             * </ul>
146             * 
147             * @param t
148             * @param result
149             */
150            private static final void addSuperClasses(final TypeDecl t, final HashSet result) {
151                if (t == null)
152                    return;
153    
154                // class
155                if (t.isClassDecl() && !result.contains(t)) {
156                    result.add((ClassDecl) t);
157                }
158                // type variable, probably called from from 1st if case.
159                else if (t.isTypeVariable()) {
160                    TypeVariable var = (TypeVariable) t;
161                    for (int i = 0; i < var.getNumTypeBound(); i++)
162                        addSuperClasses(var.getTypeBound(i).type(), result);
163                }
164                // intersection type
165                else if (t instanceof LUBType || t instanceof GLBType) {
166                    result.add(t);
167                }
168                // interface
169                else if (t.isInterfaceDecl())
170                    result.add((ClassDecl) t.typeObject());
171    
172            }
173    
174    
175    
176            /**
177             * @param ifaceList
178             */
179            private static boolean checkInterfaceCompatibility(ArrayList ifaceList) {
180                for (int i = 0; i < ifaceList.size(); i++) {
181                    HashSet superISet_i = Constraints
182                            .parameterizedSupertypes((TypeDecl) ifaceList.get(i));
183                    for (Iterator iter1 = superISet_i.iterator(); iter1.hasNext();) {
184                        InterfaceDecl superIface_i = (InterfaceDecl) iter1.next();
185    
186                        if (superIface_i instanceof ParInterfaceDecl) {
187                            ParInterfaceDecl pi = (ParInterfaceDecl) superIface_i;
188                            for (int j = i + 1; j < ifaceList.size(); j++) {
189                                HashSet superISet_j = Constraints
190                                        .parameterizedSupertypes((TypeDecl) ifaceList
191                                                .get(j));
192                                for (Iterator iter2 = superISet_j.iterator(); iter2
193                                        .hasNext();) {
194                                    InterfaceDecl superIface_j = (InterfaceDecl) iter2
195                                            .next();
196                                    if (superIface_j instanceof ParInterfaceDecl) {
197                                        ParInterfaceDecl pj = (ParInterfaceDecl) superIface_j;
198                                        if (pi != pj
199                                                && pi.genericDecl() == pj.genericDecl()
200                                                && !pi.sameArgument(pj)) {
201                                            return false;
202    
203                                        }
204                                    }
205                                }
206                            }
207                        }
208                    }
209                }
210                return true;
211            }
212    
213    
214    
215            /**
216             * @param t
217             * @param cls
218             * @param ifaceList
219             */
220            private static boolean checkClassInterfaceCompatibility(TypeDecl cls,
221                    ArrayList ifaceList) {
222                HashSet implementedInterfaces = cls.implementedInterfaces();
223                for (Iterator iter1 = implementedInterfaces.iterator(); iter1.hasNext();) {
224                    InterfaceDecl impInterface = (InterfaceDecl) iter1.next();
225    
226                    if (impInterface instanceof ParInterfaceDecl) {
227                        ParInterfaceDecl impParIface = (ParInterfaceDecl) impInterface;
228                        for (Iterator iter2 = ifaceList.iterator(); iter2.hasNext();) {
229                            InterfaceDecl iface = (InterfaceDecl) iter2.next();
230    
231                            if (iface instanceof ParInterfaceDecl) {
232                                ParInterfaceDecl parIface = (ParInterfaceDecl) iface;
233                                if (parIface != impParIface
234                                        && parIface.genericDecl() == impParIface
235                                                .genericDecl()
236                                        && !parIface.sameArgument(impParIface)) {
237                                    return false;
238                                }
239                            }
240                        }
241                    }
242                }
243                return true;
244            }
245    
246    
247    
248            /**
249             * Find the greatest lower bound(s).
250             * 
251             * @param types
252             */
253            public static final void greatestLowerBounds(ArrayList types) {
254                for (int i = 0; i < types.size(); i++) {
255                    TypeDecl U = (TypeDecl) types.get(i);
256                    for (int j = i + 1; j < types.size(); j++) {
257                        TypeDecl V = (TypeDecl) types.get(j);
258                        if (U == null || V == null)
259                            continue;
260                        if (U.instanceOf(V))
261                            types.set(j, null);
262                        else if (V.instanceOf(U))
263                            types.set(i, null);
264                    }
265                }
266                // filter null's
267                removeNullValues(types);
268            }
269    
270    
271    
272            /**
273             * Remove null values from the given list
274             * 
275             * @param types
276             */
277            public static final void removeNullValues(ArrayList types) {
278                ArrayList filter = new ArrayList(1);
279                filter.add(null);
280                types.removeAll(filter);
281            }
282    
283    
284    }