001    /* Copyright (c) 2005-2008, Torbjorn Ekman
002     * All rights reserved.
003     *
004     * Redistribution and use in source and binary forms, with or without
005     * modification, are permitted provided that the following conditions are met:
006     *
007     * 1. Redistributions of source code must retain the above copyright notice,
008     * this list of conditions and the following disclaimer.
009     *
010     * 2. Redistributions in binary form must reproduce the above copyright notice,
011     * this list of conditions and the following disclaimer in the documentation
012     * and/or other materials provided with the distribution.
013     *
014     * 3. Neither the name of the copyright holder nor the names of its
015     * contributors may be used to endorse or promote products derived from this
016     * software without specific prior written permission.
017     *
018     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019     * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021     * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
022     * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023     * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024     * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025     * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026     * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027     * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
028     * POSSIBILITY OF SUCH DAMAGE.
029     */
030    
031    aspect GreatestLowerBoundFactory {
032    
033      syn nta TypeDecl TypeVariable.toInterface() {
034        // convert var to interface
035        InterfaceDecl ITj = new InterfaceDecl();
036        ITj.setID("ITj_" + hashCode());
037        // I'm assuming that TypeVariable has no members of it's own.
038        // TODO: would it be enough to add only public members of a bound
039        // that is TypeVariable or ClassDecl and add other (interface)
040        // bounds as superinterfaces to ITj
041        // TODO: Is it really necessary to add public members to the new
042        // interface? Or is an empty interface more than enough since java
043        // has a nominal type system.
044        for (int i = 0; i < getNumTypeBound(); i++) {
045          TypeDecl bound = getTypeBound(i).type();
046          for (int j = 0; j < bound.getNumBodyDecl(); j++) {
047            BodyDecl bd = bound.getBodyDecl(j);
048            if (bd instanceof FieldDeclaration) {
049              FieldDeclaration fd = (FieldDeclaration) bd.treeCopyNoTransform();
050              if (fd.isPublic()) {
051                ITj.addBodyDecl(fd);
052              }
053            } else if (bd instanceof MethodDecl) {
054              MethodDecl md = (MethodDecl) bd;
055              if (md.isPublic()) {
056                ITj.addBodyDecl((BodyDecl) md.treeCopyNoTransform());
057              }
058            }
059          }
060        }
061        return ITj;
062      }
063    
064        public class GLBTypeFactory {
065            // TODO add support for array types.
066            public static TypeDecl glb(final ArrayList typeList) {
067                TypeDecl retType = ((TypeDecl) typeList.get(0)).unknownType();
068                TypeDecl cls = mostSpecificSuperClass(typeList);
069                if (cls != null) {
070                    ArrayList intersectInterfaceList = new ArrayList();
071                    ArrayList allInterfaceList = new ArrayList();
072                    for (Iterator itera = typeList.iterator(); itera.hasNext();) {
073                        TypeDecl typeDecl = (TypeDecl) itera.next();
074                        addInterfaces(intersectInterfaceList, allInterfaceList, typeDecl);
075                    }
076    
077                    // remove all interfaces that are not most specific.
078                    greatestLowerBounds(intersectInterfaceList);
079                    // check for interface compatibility.
080                    if (checkInterfaceCompatibility(allInterfaceList)
081                        && checkClassInterfaceCompatibility(cls, intersectInterfaceList)) {
082                      greatestLowerBounds(typeList);
083                      if (typeList.size() == 1) {
084                        retType = (TypeDecl) typeList.iterator().next();
085                      } else {
086                        retType = retType.lookupGLBType(typeList);
087                      }
088                    }
089                }
090                return retType;
091            }
092    
093            /**
094             * @param intersectInterfaceList
095             * @param allInterfaceList
096             * @param typeDecl
097             */
098            private static void addInterfaces(ArrayList intersectInterfaceList, ArrayList allInterfaceList, TypeDecl typeDecl) {
099                if (typeDecl.isInterfaceDecl()) {
100                    intersectInterfaceList.add((InterfaceDecl) typeDecl);
101                    allInterfaceList.add((InterfaceDecl) typeDecl);
102                } else if (typeDecl instanceof TypeVariable) {
103                    TypeVariable varTD = (TypeVariable) typeDecl;
104                    // add the interfaces created for type variables to
105                    // interface list to be checked for compatibility
106                    intersectInterfaceList.add(varTD.toInterface());
107                    // add the bounds of the type variable that are interfaces.
108                    allInterfaceList.addAll(varTD.implementedInterfaces());
109                } else if (typeDecl instanceof LUBType) {
110                    allInterfaceList.addAll(typeDecl.implementedInterfaces());
111                } else if (typeDecl instanceof GLBType) {
112                    allInterfaceList.addAll(typeDecl.implementedInterfaces());
113                }
114            }
115    
116            /**
117             * See JLS section 4.9 about Intersection Types
118             * <p>
119             * For each <i>T<sub>i</sub></i>, 1 &le; i &le; n, let <i>C<sub>i</sub></i>
120             * be the most specific class or array type such that <i>T<sub>i</sub></i>
121             * &lt;: <i>C<sub>i</sub></i> Then there must be some <i>T<sub>k</sub></i>
122             * &lt;: <i>C<sub>k</sub></i> such that <i>C<sub>k</sub></i> &lt;:
123             * <i>C<sub>i</sub></i> for any <i>i</i>, 1 &le; i &le; n, or a
124             * compile-time error occurs.
125             *
126             * @param types
127             * @return the most specific class that all elements in <i>types</i> are a
128             *         subtype of. Or null if no such class exists.
129             */
130            public final static TypeDecl mostSpecificSuperClass(final ArrayList types) {
131                ArrayList csList = new ArrayList();
132                for (Iterator iter = types.iterator(); iter.hasNext(); ) {
133                  csList.add(mostSpecificSuperClass((TypeDecl) iter.next()));
134                }
135    
136                // find Tk with Ck
137                greatestLowerBounds(csList);
138                if (csList.size() == 1) {
139                    // OK
140                    return (TypeDecl) csList.get(0);
141                } else {
142                    // Ck does not exist.
143                    return null;
144                }
145            }
146    
147            /**
148             * Return most specific superclass of t.
149             *
150             * @param t
151             * @return most specific superclass of t
152             */
153            private final static TypeDecl mostSpecificSuperClass(final TypeDecl t) {
154                HashSet superTypes = new HashSet();
155                addSuperClasses(t, superTypes);
156    
157                if (superTypes.isEmpty()) {
158                    return t.typeObject();
159                }
160    
161                ArrayList result = new ArrayList(superTypes.size());
162                result.addAll(superTypes);
163                greatestLowerBounds(result);
164    
165                if (result.size() == 1) {
166                    return (TypeDecl) result.get(0);
167                } else {
168                    return (TypeDecl) t.typeObject();
169                }
170            }
171    
172            /**
173             * Add the superclasses (<i>C<sub>i</sub></i>) of <i>t</i> to the set
174             * <i>result</i>.
175             * <ul>
176             * <li>If <i>t</i> is a class, then <i>C<sub>i</sub></i> is t itself.</li>
177             * <li>If <i>t</i> is a type variable, then <i>C<sub>i</sub></i> is the
178             * first class encountered in it bounds</li>
179             * <li>It <i>t</i> is an intersection type, then <i>C<sub>i</sub></i>
180             * is class that is a member of the intersection, otherwise it's Object</li>
181             * </ul>
182             *
183             * @param t
184             * @param result
185             */
186            private static final void addSuperClasses(final TypeDecl t, final HashSet result) {
187                if (t == null) {
188                    return;
189                }
190    
191                // class
192                if (t.isClassDecl() && !result.contains(t)) {
193                    result.add((ClassDecl) t);
194                }
195                // type variable, probably called from from 1st if case.
196                else if (t.isTypeVariable()) {
197                    TypeVariable var = (TypeVariable) t;
198                    for (int i = 0; i < var.getNumTypeBound(); i++)
199                        addSuperClasses(var.getTypeBound(i).type(), result);
200                }
201                // intersection type
202                else if (t instanceof LUBType || t instanceof GLBType) {
203                    result.add(t);
204                }
205                // interface
206                else if (t.isInterfaceDecl()) {
207                    result.add((ClassDecl) t.typeObject());
208                }
209    
210            }
211    
212            /**
213             * @param ifaceList
214             */
215            private static boolean checkInterfaceCompatibility(ArrayList ifaceList) {
216                for (int i = 0; i < ifaceList.size(); i++) {
217                    HashSet superISet_i = Constraints
218                            .parameterizedSupertypes((TypeDecl) ifaceList.get(i));
219                    for (Iterator iter1 = superISet_i.iterator(); iter1.hasNext();) {
220                        InterfaceDecl superIface_i = (InterfaceDecl) iter1.next();
221    
222                        if (superIface_i instanceof ParInterfaceDecl) {
223                            ParInterfaceDecl pi = (ParInterfaceDecl) superIface_i;
224                            for (int j = i + 1; j < ifaceList.size(); j++) {
225                                HashSet superISet_j = Constraints
226                                        .parameterizedSupertypes((TypeDecl) ifaceList
227                                                .get(j));
228                                for (Iterator iter2 = superISet_j.iterator(); iter2
229                                        .hasNext();) {
230                                    InterfaceDecl superIface_j = (InterfaceDecl) iter2
231                                            .next();
232                                    if (superIface_j instanceof ParInterfaceDecl) {
233                                        ParInterfaceDecl pj = (ParInterfaceDecl) superIface_j;
234                                        if (pi != pj
235                                                && pi.genericDecl() == pj.genericDecl()
236                                                && !pi.sameArgument(pj)) {
237                                            return false;
238    
239                                        }
240                                    }
241                                }
242                            }
243                        }
244                    }
245                }
246                return true;
247            }
248    
249            /**
250             * @param t
251             * @param cls
252             * @param ifaceList
253             */
254            private static boolean checkClassInterfaceCompatibility(TypeDecl cls,
255                    ArrayList ifaceList) {
256                HashSet implementedInterfaces = cls.implementedInterfaces();
257                for (Iterator iter1 = implementedInterfaces.iterator(); iter1.hasNext();) {
258                    InterfaceDecl impInterface = (InterfaceDecl) iter1.next();
259    
260                    if (impInterface instanceof ParInterfaceDecl) {
261                        ParInterfaceDecl impParIface = (ParInterfaceDecl) impInterface;
262                        for (Iterator iter2 = ifaceList.iterator(); iter2.hasNext();) {
263                            InterfaceDecl iface = (InterfaceDecl) iter2.next();
264    
265                            if (iface instanceof ParInterfaceDecl) {
266                                ParInterfaceDecl parIface = (ParInterfaceDecl) iface;
267                                if (parIface != impParIface
268                                        && parIface.genericDecl() == impParIface
269                                                .genericDecl()
270                                        && !parIface.sameArgument(impParIface)) {
271                                    return false;
272                                }
273                            }
274                        }
275                    }
276                }
277                return true;
278            }
279    
280            /**
281             * Find the greatest lower bound(s).
282             *
283             * @param types
284             */
285            public static final void greatestLowerBounds(ArrayList types) {
286                for (int i = 0; i < types.size(); i++) {
287                    TypeDecl U = (TypeDecl) types.get(i);
288                    for (int j = i + 1; j < types.size(); j++) {
289                        TypeDecl V = (TypeDecl) types.get(j);
290                        if (U == null || V == null) {
291                            continue;
292                        }
293                        if (U.instanceOf(V)) {
294                            types.set(j, null);
295                        } else if (V.instanceOf(U)) {
296                            types.set(i, null);
297                        }
298                    }
299                }
300                // filter null's
301                removeNullValues(types);
302            }
303    
304            /**
305             * Remove null values from the given list
306             *
307             * @param types
308             */
309            public static final void removeNullValues(ArrayList types) {
310                ArrayList filter = new ArrayList(1);
311                filter.add(null);
312                types.removeAll(filter);
313            }
314        }
315    
316    }