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 }