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