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