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