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 }
--- EOF ---