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 */
23package org.graalvm.compiler.core.common.type;
24
25import java.util.AbstractList;
26import java.util.Objects;
27import java.util.RandomAccess;
28
29import jdk.vm.ci.meta.Constant;
30import jdk.vm.ci.meta.JavaConstant;
31import jdk.vm.ci.meta.JavaKind;
32import jdk.vm.ci.meta.MetaAccessProvider;
33import jdk.vm.ci.meta.ResolvedJavaType;
34
35/**
36 * Type describing all pointers to Java objects.
37 */
38public 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}
339