1 /* 2 * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.core.common.type; 24 25 import java.util.AbstractList; 26 import java.util.Objects; 27 import java.util.RandomAccess; 28 29 import jdk.vm.ci.meta.Constant; 30 import jdk.vm.ci.meta.JavaConstant; 31 import jdk.vm.ci.meta.JavaKind; 32 import jdk.vm.ci.meta.MetaAccessProvider; 33 import jdk.vm.ci.meta.ResolvedJavaType; 34 35 /** 36 * Type describing all pointers to Java objects. 37 */ 38 public abstract class AbstractObjectStamp extends AbstractPointerStamp { 39 40 private final ResolvedJavaType type; 41 private final boolean exactType; 42 43 protected AbstractObjectStamp(ResolvedJavaType type, boolean exactType, boolean nonNull, boolean alwaysNull) { 44 super(nonNull, alwaysNull); 45 this.type = type; 46 this.exactType = exactType; 47 } 48 49 protected abstract AbstractObjectStamp copyWith(ResolvedJavaType newType, boolean newExactType, boolean newNonNull, boolean newAlwaysNull); 50 51 @Override 52 protected final AbstractPointerStamp copyWith(boolean newNonNull, boolean newAlwaysNull) { 53 return copyWith(type, exactType, newNonNull, newAlwaysNull); 54 } 55 56 @Override 57 public Stamp unrestricted() { 58 return copyWith(null, false, false, false); 59 } 60 61 @Override 62 public Stamp empty() { 63 return copyWith(null, true, true, false); 64 } 65 66 @Override 67 public Stamp constant(Constant c, MetaAccessProvider meta) { 68 JavaConstant jc = (JavaConstant) c; 69 ResolvedJavaType constType = jc.isNull() ? null : meta.lookupJavaType(jc); 70 return copyWith(constType, jc.isNonNull(), jc.isNonNull(), jc.isNull()); 71 } 72 73 @Override 74 public boolean hasValues() { 75 return !exactType || (type != null && (isConcreteType(type))); 76 } 77 78 @Override 79 public JavaKind getStackKind() { 80 return JavaKind.Object; 81 } 82 83 @Override 84 public ResolvedJavaType javaType(MetaAccessProvider metaAccess) { 85 if (type != null) { 86 return type; 87 } 88 return metaAccess.lookupJavaType(Object.class); 89 } 90 91 public ResolvedJavaType type() { 92 return type; 93 } 94 95 public boolean isExactType() { 96 return exactType && type != null; 97 } 98 99 protected void appendString(StringBuilder str) { 100 if (this.isEmpty()) { 101 str.append(" empty"); 102 } else { 103 str.append(nonNull() ? "!" : "").append(exactType ? "#" : "").append(' ').append(type == null ? "-" : type.getName()).append(alwaysNull() ? " NULL" : ""); 104 } 105 } 106 107 @Override 108 public Stamp meet(Stamp otherStamp) { 109 if (this == otherStamp) { 110 return this; 111 } 112 AbstractObjectStamp other = (AbstractObjectStamp) otherStamp; 113 if (isEmpty()) { 114 return other; 115 } else if (other.isEmpty()) { 116 return this; 117 } 118 ResolvedJavaType meetType; 119 boolean meetExactType; 120 boolean meetNonNull; 121 boolean meetAlwaysNull; 122 if (other.alwaysNull()) { 123 meetType = type(); 124 meetExactType = exactType; 125 meetNonNull = false; 126 meetAlwaysNull = alwaysNull(); 127 } else if (alwaysNull()) { 128 meetType = other.type(); 129 meetExactType = other.exactType; 130 meetNonNull = false; 131 meetAlwaysNull = other.alwaysNull(); 132 } else { 133 meetType = meetTypes(type(), other.type()); 134 meetExactType = exactType && other.exactType; 135 if (meetExactType && type != null && other.type != null) { 136 // meeting two valid exact types may result in a non-exact type 137 meetExactType = Objects.equals(meetType, type) && Objects.equals(meetType, other.type); 138 } 139 meetNonNull = nonNull() && other.nonNull(); 140 meetAlwaysNull = false; 141 } 142 143 if (Objects.equals(meetType, type) && meetExactType == exactType && meetNonNull == nonNull() && meetAlwaysNull == alwaysNull()) { 144 return this; 145 } else if (Objects.equals(meetType, other.type) && meetExactType == other.exactType && meetNonNull == other.nonNull() && meetAlwaysNull == other.alwaysNull()) { 146 return other; 147 } else { 148 return copyWith(meetType, meetExactType, meetNonNull, meetAlwaysNull); 149 } 150 } 151 152 @Override 153 public Stamp join(Stamp otherStamp) { 154 return join0(otherStamp, false); 155 } 156 157 /** 158 * Returns the stamp representing the type of this stamp after a cast to the type represented by 159 * the {@code to} stamp. While this is very similar to a {@link #join} operation, in the case 160 * where both types are not obviously related, the cast operation will prefer the type of the 161 * {@code to} stamp. This is necessary as long as ObjectStamps are not able to accurately 162 * represent intersection types. 163 * 164 * For example when joining the {@link RandomAccess} type with the {@link AbstractList} type, 165 * without intersection types, this would result in the most generic type ({@link Object} ). For 166 * this reason, in some cases a {@code castTo} operation is preferable in order to keep at least 167 * the {@link AbstractList} type. 168 * 169 * @param other the stamp this stamp should be casted to 170 * @return the new improved stamp or {@code null} if this stamp cannot be improved 171 */ 172 @Override 173 public Stamp improveWith(Stamp other) { 174 return join0(other, true); 175 } 176 177 private Stamp join0(Stamp otherStamp, boolean improve) { 178 if (this == otherStamp) { 179 return this; 180 } 181 AbstractObjectStamp other = (AbstractObjectStamp) otherStamp; 182 if (isEmpty()) { 183 return this; 184 } else if (other.isEmpty()) { 185 return other; 186 } 187 188 ResolvedJavaType joinType; 189 boolean joinAlwaysNull = alwaysNull() || other.alwaysNull(); 190 boolean joinNonNull = nonNull() || other.nonNull(); 191 boolean joinExactType = exactType || other.exactType; 192 if (Objects.equals(type, other.type)) { 193 joinType = type; 194 } else if (type == null && other.type == null) { 195 joinType = null; 196 } else if (type == null) { 197 joinType = other.type; 198 } else if (other.type == null) { 199 joinType = type; 200 } else { 201 // both types are != null and different 202 if (type.isAssignableFrom(other.type)) { 203 joinType = other.type; 204 if (exactType) { 205 joinAlwaysNull = true; 206 } 207 } else if (other.type.isAssignableFrom(type)) { 208 joinType = type; 209 if (other.exactType) { 210 joinAlwaysNull = true; 211 } 212 } else { 213 if (improve) { 214 joinType = type; 215 joinExactType = exactType; 216 } else { 217 joinType = null; 218 } 219 220 if (joinExactType || (!isInterfaceOrArrayOfInterface(type) && !isInterfaceOrArrayOfInterface(other.type))) { 221 joinAlwaysNull = true; 222 } 223 } 224 } 225 if (joinAlwaysNull) { 226 joinType = null; 227 joinExactType = false; 228 } 229 if (joinExactType && joinType == null) { 230 return empty(); 231 } 232 if (joinAlwaysNull && joinNonNull) { 233 return empty(); 234 } else if (joinExactType && !isConcreteType(joinType)) { 235 return empty(); 236 } 237 if (Objects.equals(joinType, type) && joinExactType == exactType && joinNonNull == nonNull() && joinAlwaysNull == alwaysNull()) { 238 return this; 239 } else if (Objects.equals(joinType, other.type) && joinExactType == other.exactType && joinNonNull == other.nonNull() && joinAlwaysNull == other.alwaysNull()) { 240 return other; 241 } else { 242 return copyWith(joinType, joinExactType, joinNonNull, joinAlwaysNull); 243 } 244 } 245 246 private static boolean isInterfaceOrArrayOfInterface(ResolvedJavaType t) { 247 return t.isInterface() || (t.isArray() && t.getElementalType().isInterface()); 248 } 249 250 public static boolean isConcreteType(ResolvedJavaType type) { 251 return !(type.isAbstract() && !type.isArray()); 252 } 253 254 private static ResolvedJavaType meetTypes(ResolvedJavaType a, ResolvedJavaType b) { 255 if (Objects.equals(a, b)) { 256 return a; 257 } else if (a == null || b == null) { 258 return null; 259 } else { 260 // The `meetTypes` operation must be commutative. One way to achieve this is to totally 261 // order the types and always call `meetOrderedNonNullTypes` in the same order. We 262 // establish the order by first comparing the hash-codes for performance reasons, and 263 // then comparing the internal names of the types. 264 int hashA = a.getName().hashCode(); 265 int hashB = b.getName().hashCode(); 266 if (hashA < hashB) { 267 return meetOrderedNonNullTypes(a, b); 268 } else if (hashB < hashA) { 269 return meetOrderedNonNullTypes(b, a); 270 } else { 271 int diff = a.getName().compareTo(b.getName()); 272 if (diff <= 0) { 273 return meetOrderedNonNullTypes(a, b); 274 } else { 275 return meetOrderedNonNullTypes(b, a); 276 } 277 } 278 } 279 } 280 281 private static ResolvedJavaType meetOrderedNonNullTypes(ResolvedJavaType a, ResolvedJavaType b) { 282 ResolvedJavaType result = a.findLeastCommonAncestor(b); 283 if (result.isJavaLangObject() && a.isInterface() && b.isInterface()) { 284 // Both types are incompatible interfaces => search for first possible common 285 // ancestor match among super interfaces. 286 ResolvedJavaType[] interfacesA = a.getInterfaces(); 287 ResolvedJavaType[] interfacesB = b.getInterfaces(); 288 for (int i = 0; i < interfacesA.length; ++i) { 289 ResolvedJavaType interface1 = interfacesA[i]; 290 for (int j = 0; j < interfacesB.length; ++j) { 291 ResolvedJavaType interface2 = interfacesB[j]; 292 ResolvedJavaType leastCommon = meetTypes(interface1, interface2); 293 if (leastCommon.isInterface()) { 294 return leastCommon; 295 } 296 } 297 } 298 } 299 return result; 300 } 301 302 @Override 303 public int hashCode() { 304 final int prime = 31; 305 int result = 1; 306 result = prime * result + super.hashCode(); 307 result = prime * result + (exactType ? 1231 : 1237); 308 result = prime * result + ((type == null || type.isJavaLangObject()) ? 0 : type.hashCode()); 309 return result; 310 } 311 312 @Override 313 public boolean equals(Object obj) { 314 if (this == obj) { 315 return true; 316 } 317 if (obj == null || getClass() != obj.getClass()) { 318 return false; 319 } 320 AbstractObjectStamp other = (AbstractObjectStamp) obj; 321 if (exactType != other.exactType) { 322 return false; 323 } 324 // null == java.lang.Object 325 if (type == null) { 326 if (other.type != null && !other.type.isJavaLangObject()) { 327 return false; 328 } 329 } else if (other.type == null) { 330 if (type != null && !type.isJavaLangObject()) { 331 return false; 332 } 333 } else if (!type.equals(other.type)) { 334 return false; 335 } 336 return super.equals(other); 337 } 338 }