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 ≤ i ≤ 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 * <: <i>C<sub>i</sub></i> Then there must be some <i>T<sub>k</sub></i> 122 * <: <i>C<sub>k</sub></i> such that <i>C<sub>k</sub></i> <: 123 * <i>C<sub>i</sub></i> for any <i>i</i>, 1 ≤ i ≤ 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 }