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 protected abstract AbstractObjectStamp copyWith(ResolvedJavaType newType, boolean newExactType, boolean newNonNull, boolean newAlwaysNull);
52
53 @Override
54 protected final AbstractPointerStamp copyWith(boolean newNonNull, boolean newAlwaysNull) {
55 return copyWith(type, exactType, newNonNull, newAlwaysNull);
56 }
57
58 @Override
59 public Stamp unrestricted() {
60 return copyWith(null, false, false, false);
61 }
62
63 @Override
64 public Stamp empty() {
65 return copyWith(null, true, true, false);
66 }
67
68 @Override
69 public Stamp constant(Constant c, MetaAccessProvider meta) {
70 JavaConstant jc = (JavaConstant) c;
71 ResolvedJavaType constType = jc.isNull() ? null : meta.lookupJavaType(jc);
72 return copyWith(constType, jc.isNonNull(), jc.isNonNull(), jc.isNull());
73 }
74
75 @Override
76 public boolean hasValues() {
77 return !exactType || (type != null && (isConcreteType(type)));
78 }
79
80 @Override
81 public JavaKind getStackKind() {
82 return JavaKind.Object;
83 }
84
85 @Override
86 public ResolvedJavaType javaType(MetaAccessProvider metaAccess) {
87 if (type != null) {
88 return type;
89 }
90 return metaAccess.lookupJavaType(Object.class);
91 }
92
93 public ResolvedJavaType type() {
94 return type;
95 }
96
97 public boolean isExactType() {
98 return exactType && type != null;
99 }
100
101 protected void appendString(StringBuilder str) {
102 if (this.isEmpty()) {
103 str.append(" empty");
104 } else {
105 str.append(nonNull() ? "!" : "").append(exactType ? "#" : "").append(' ').append(type == null ? "-" : type.getName()).append(alwaysNull() ? " NULL" : "");
106 }
107 }
108
109 @Override
110 public Stamp meet(Stamp otherStamp) {
111 if (this == otherStamp) {
112 return this;
113 }
114 AbstractObjectStamp other = (AbstractObjectStamp) otherStamp;
115 if (isEmpty()) {
116 return other;
117 } else if (other.isEmpty()) {
118 return this;
119 }
120 ResolvedJavaType meetType;
121 boolean meetExactType;
122 boolean meetNonNull;
123 boolean meetAlwaysNull;
124 if (other.alwaysNull()) {
125 meetType = type();
126 meetExactType = exactType;
127 meetNonNull = false;
128 meetAlwaysNull = alwaysNull();
129 } else if (alwaysNull()) {
130 meetType = other.type();
131 meetExactType = other.exactType;
132 meetNonNull = false;
133 meetAlwaysNull = other.alwaysNull();
134 } else {
135 meetType = meetTypes(type(), other.type());
136 meetExactType = exactType && other.exactType;
137 if (meetExactType && type != null && other.type != null) {
138 // meeting two valid exact types may result in a non-exact type
139 meetExactType = Objects.equals(meetType, type) && Objects.equals(meetType, other.type);
140 }
141 meetNonNull = nonNull() && other.nonNull();
142 meetAlwaysNull = false;
143 }
144
145 if (Objects.equals(meetType, type) && meetExactType == exactType && meetNonNull == nonNull() && meetAlwaysNull == alwaysNull()) {
146 return this;
147 } else if (Objects.equals(meetType, other.type) && meetExactType == other.exactType && meetNonNull == other.nonNull() && meetAlwaysNull == other.alwaysNull()) {
148 return other;
149 } else {
150 return copyWith(meetType, meetExactType, meetNonNull, meetAlwaysNull);
151 }
152 }
153
154 @Override
155 public Stamp join(Stamp otherStamp) {
156 return join0(otherStamp, false);
157 }
158
159 /**
160 * Returns the stamp representing the type of this stamp after a cast to the type represented by
161 * the {@code to} stamp. While this is very similar to a {@link #join} operation, in the case
162 * where both types are not obviously related, the cast operation will prefer the type of the
163 * {@code to} stamp. This is necessary as long as ObjectStamps are not able to accurately
164 * represent intersection types.
165 *
166 * For example when joining the {@link RandomAccess} type with the {@link AbstractList} type,
167 * without intersection types, this would result in the most generic type ({@link Object} ). For
168 * this reason, in some cases a {@code castTo} operation is preferable in order to keep at least
169 * the {@link AbstractList} type.
170 *
171 * @param other the stamp this stamp should be casted to
172 * @return the new improved stamp or {@code null} if this stamp cannot be improved
173 */
174 @Override
175 public Stamp improveWith(Stamp other) {
176 return join0(other, true);
177 }
178
179 private Stamp join0(Stamp otherStamp, boolean improve) {
180 if (this == otherStamp) {
181 return this;
182 }
183 AbstractObjectStamp other = (AbstractObjectStamp) otherStamp;
184 if (isEmpty()) {
185 return this;
186 } else if (other.isEmpty()) {
187 return other;
188 }
189
190 ResolvedJavaType joinType;
191 boolean joinAlwaysNull = alwaysNull() || other.alwaysNull();
192 boolean joinNonNull = nonNull() || other.nonNull();
193 boolean joinExactType = exactType || other.exactType;
194 if (Objects.equals(type, other.type)) {
195 joinType = type;
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 }