src/vm/jit/verify/typeinfo.h

   1 /* typeinfo.h - type system used by the type checker
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Edwin Steiner
  28
  29    $Id: typeinfo.h 1735 2004-12-07 14:33:27Z twisti $
  30
  31 */
  32
  33
  34 #ifndef _TYPEINFO_H
  35 #define _TYPEINFO_H
  36
  37 #include "vm/global.h"
  38
  39 /* resolve typedef cycles *****************************************************/
  40
  41 typedef struct typeinfo typeinfo;
  42 typedef struct typeinfo_mergedlist typeinfo_mergedlist;
  43 typedef struct typedescriptor typedescriptor;
  44 typedef struct typevector typevector;
  45 typedef struct typeinfo_retaddr_set typeinfo_retaddr_set;
  46
  47 /* data structures for the type system ****************************************/
  48
  49 /* The typeinfo structure stores detailed information on address types.
  50  * (stack elements, variables, etc. with type == TYPE_ADR.)
  51  *
  52  * There are two kinds of address types which can are distinguished by
  53  * the value of the typeclass field:
  54  *
  55  * 1) typeclass == NULL: returnAddress type
  56  *                       use TYPEINFO_IS_PRIMITIVE to test for this
  57  *
  58  * 2) typeclass != NULL: reference type
  59  *                       use TYPEINFO_IS_REFERENCE to test for this
  60  *
  61  * Note: For non-address types either there is no typeinfo allocated
  62  * or the fields of the typeinfo struct contain undefined values!
  63  *
  64  * CAUTION: The typeinfo structure should be considered opaque outside of
  65  *          typeinfo.[ch]. Please use the macros and functions defined here to
  66  *          access typeinfo structures!
  67  */
  68
  69 /* At all times *exactly one* of the following conditions is true for
  70  * a particular typeinfo struct:
  71  *
  72  * A) typeclass == NULL
  73  *
  74  *        This is a returnAddress type. The interpretation of the
  75  *        elementclass field depends on wether this typeinfo describes
  76  *        a stack slot or a local variable:
  77  *
  78  *        stack slot: elementclass is a pointer to a
  79  *            typeinfo_retaddr_set which contains a return target for
  80  *            every vector in the current set of local variable vectors.
  81  *        local variable: elementclass is the return target (when cast
  82  *            to basicblock *)
  83  *
  84  *        Use TYPEINFO_IS_PRIMITIVE to check for this.
  85  *        Use TYPEINFO_RETURNADDRESS to access the pointer in elementclass.
  86  *        Don't access other fields of the struct.
  87  *
  88  * B) typeclass == pseudo_class_Null
  89  *
  90  *        This is the null-reference type. Use TYPEINFO_IS_NULLTYPE to check for this.
  91  *        Don't access other fields of the struct.
  92  *
  93  * C) typeclass == pseudo_class_New
  94  *
  95  *        This is a 'uninitialized object' type. elementclass can be
  96  *        cast to instruction* and points to the NEW instruction
  97  *        responsible for creating this type.
  98  *
  99  *        Use TYPEINFO_NEWOBJECT_INSTRUCTION to access the pointer in
 100  *        elementclass.
 101  *        Don't access other fields of the struct.
 102  *
 103  * D) typeclass == pseudo_class_Arraystub
 104  *
 105  *        See global.h for a describes of pseudo_class_Arraystub.
 106  *        Otherwise like a normal class reference type.
 107  *        Don't access other fields of the struct.
 108  *
 109  * E) typeclass is an array class
 110  *
 111  *        An array reference.
 112  *            elementclass...typeclass of the element type
 113  *            dimension......dimension of the array (>=1)
 114  *            elementtype....element type (ARRAYTYPE_...)
 115  *            merged.........mergedlist of the element type
 116  *
 117  * F) typeclass is an interface
 118  *
 119  *        An interface reference type.
 120  *        Don't access other fields of the struct.
 121  *
 122  * G) typeclass is a (non-pseudo-,non-array-)class != java.lang.Object
 123  *
 124  *        A class reference type.
 125  *        All classinfos in u.merged.list (if any) are
 126  *        subclasses of typeclass (no interfaces or array classes).
 127  *        Don't access other fields of the struct.
 128  *
 129  * H) typeclass is java.lang.Object
 130  *
 131  *        The most general kind of reference type.
 132  *        In this case u.merged.count and u.merged.list
 133  *        are valid and may be non-zero.
 134  *        The classinfos in u.merged.list (if any) may be
 135  *        classes, interfaces and pseudo classes.
 136  *        Don't access other fields of the struct.
 137  */
 138
 139 /* The following algorithm is used to determine if the type described
 140  * by this typeinfo struct supports the interface X:
 141  *
 142  *     1) If typeclass is X or a subinterface of X the answer is "yes".
 143  *     2) If typeclass is a (pseudo) class implementing X the answer is "yes".
 144  *     3) If typeclass is not an array and u.merged.count>0
 145  *        and all classes/interfaces in u.merged.list implement X
 146  *        the answer is "yes".
 147  *     4) If none of the above is true the answer is "no".
 148  */
 149
 150 /*
 151  * CAUTION: The typeinfo structure should be considered opaque outside of
 152  *          typeinfo.[ch]. Please use the macros and functions defined here to
 153  *          access typeinfo structures!
 154  */
 155 struct typeinfo {
 156         classinfo           *typeclass;
 157         classinfo           *elementclass; /* valid if dimension>0 */ /* various uses! */
 158         typeinfo_mergedlist *merged;
 159         u1                   dimension;
 160         u1                   elementtype;  /* valid if dimension>0 */
 161 };
 162
 163 struct typeinfo_mergedlist {
 164         s4         count;
 165         classinfo *list[1];       /* variable length!                        */
 166 };
 167
 168 struct typeinfo_retaddr_set {
 169         typeinfo_retaddr_set *alt;  /* next alternative in set               */
 170         void                 *addr; /* return address                        */
 171 };
 172
 173 struct typedescriptor {
 174         typeinfo        info;     /* valid if type == TYPE_ADR               */
 175         u1              type;     /* basic type (TYPE_INT, ...)              */
 176 };
 177
 178 /* typevectors are used to store the types of local variables */
 179
 180 struct typevector {
 181         typevector      *alt;     /* next alternative in typevector set */
 182         int              k;       /* for lining up with the stack set   */
 183         typedescriptor   td[1];   /* variable length!                   */
 184 };
 185
 186 /****************************************************************************/
 187 /* MACROS                                                                   */
 188 /****************************************************************************/
 189
 190 /* NOTE: The TYPEINFO macros take typeinfo *structs*, not pointers as
 191  *       arguments.  You have to dereference any pointers.
 192  */
 193
 194 /* typevectors **************************************************************/
 195
 196 #define TYPEVECTOR_SIZE(size)                                           \
 197     ((sizeof(typevector) - sizeof(typedescriptor))      \
 198      + (size)*sizeof(typedescriptor))
 199
 200 #define DNEW_TYPEVECTOR(size)                                           \
 201     ((typevector*)dump_alloc(TYPEVECTOR_SIZE(size)))
 202
 203 #define DMNEW_TYPEVECTOR(num,size)                                              \
 204     ((void*)dump_alloc((num) * TYPEVECTOR_SIZE(size)))
 205
 206 #define MGET_TYPEVECTOR(array,index,size) \
 207     ((typevector*) (((u1*)(array)) + TYPEVECTOR_SIZE(size) * (index)))
 208
 209 #define COPY_TYPEVECTORSET(src,dst,size)                                                \
 210     do {memcpy(dst,src,TYPEVECTOR_SIZE(size));                                  \
 211         dst->k = 0;                                             \
 212         if ((src)->alt) {                                                                               \
 213                 (dst)->alt = typevectorset_copy((src)->alt,1,size);     \
 214         }} while(0)
 215
 216 /* internally used macros ***************************************************/
 217
 218 /* internal, don't use this explicitly! */
 219 #define TYPEINFO_ALLOCMERGED(mergedlist,count)                  \
 220     do {(mergedlist) = (typeinfo_mergedlist*)dump_alloc(        \
 221             sizeof(typeinfo_mergedlist)                         \
 222             + ((count)-1)*sizeof(classinfo*));} while(0)
 223
 224 /* internal, don't use this explicitly! */
 225 #define TYPEINFO_FREEMERGED(mergedlist)
 226
 227 /* internal, don't use this explicitly! */
 228 #define TYPEINFO_FREEMERGED_IF_ANY(mergedlist)
 229
 230 /* macros for type queries **************************************************/
 231
 232 #define TYPEINFO_IS_PRIMITIVE(info)                             \
 233             ((info).typeclass == NULL)
 234
 235 #define TYPEINFO_IS_REFERENCE(info)                             \
 236             ((info).typeclass != NULL)
 237
 238 #define TYPEINFO_IS_NULLTYPE(info)                              \
 239             ((info).typeclass == pseudo_class_Null)
 240
 241 #define TYPEINFO_IS_NEWOBJECT(info)                             \
 242             ((info).typeclass == pseudo_class_New)
 243
 244 /* only use this if TYPEINFO_IS_PRIMITIVE returned true! */
 245 #define TYPEINFO_RETURNADDRESS(info)                            \
 246             ((void *)(info).elementclass)
 247
 248 /* only use this if TYPEINFO_IS_NEWOBJECT returned true! */
 249 #define TYPEINFO_NEWOBJECT_INSTRUCTION(info)                    \
 250             ((void *)(info).elementclass)
 251
 252 /* macros for array type queries ********************************************/
 253
 254 #define TYPEINFO_IS_ARRAY(info)                                 \
 255             ( TYPEINFO_IS_REFERENCE(info)                       \
 256               && ((info).dimension != 0) )
 257
 258 #define TYPEINFO_IS_SIMPLE_ARRAY(info)                          \
 259             ( ((info).dimension == 1) )
 260
 261 #define TYPEINFO_IS_ARRAY_ARRAY(info)                           \
 262             ( ((info).dimension >= 2) )
 263
 264 #define TYPEINFO_IS_PRIMITIVE_ARRAY(info,arraytype)             \
 265             ( TYPEINFO_IS_SIMPLE_ARRAY(info)                    \
 266               && ((info).elementtype == (arraytype)) )
 267
 268 #define TYPEINFO_IS_OBJECT_ARRAY(info)                          \
 269             ( TYPEINFO_IS_SIMPLE_ARRAY(info)                    \
 270               && ((info).elementclass != NULL) )
 271
 272 /* assumes that info describes an array type */
 273 #define TYPEINFO_IS_ARRAY_OF_REFS_NOCHECK(info)                 \
 274             ( ((info).elementclass != NULL)                     \
 275               || ((info).dimension >= 2) )
 276
 277 #define TYPEINFO_IS_ARRAY_OF_REFS(info)                         \
 278             ( TYPEINFO_IS_ARRAY(info)                           \
 279               && TYPEINFO_IS_ARRAY_OF_REFS_NOCHECK(info) )
 280
 281 #define TYPE_IS_RETURNADDRESS(type,info)                        \
 282             ( ((type)==TYPE_ADDRESS)                            \
 283               && TYPEINFO_IS_PRIMITIVE(info) )
 284
 285 #define TYPE_IS_REFERENCE(type,info)                            \
 286             ( ((type)==TYPE_ADDRESS)                            \
 287               && !TYPEINFO_IS_PRIMITIVE(info) )
 288
 289 #define TYPEDESC_IS_RETURNADDRESS(td)                           \
 290             TYPE_IS_RETURNADDRESS((td).type,(td).info)
 291
 292 #define TYPEDESC_IS_REFERENCE(td)                               \
 293             TYPE_IS_REFERENCE((td).type,(td).info)
 294
 295 /* queries allowing the null type ********************************************/
 296
 297 #define TYPEINFO_MAYBE_ARRAY(info)                              \
 298     (TYPEINFO_IS_ARRAY(info) || TYPEINFO_IS_NULLTYPE(info))
 299
 300 #define TYPEINFO_MAYBE_PRIMITIVE_ARRAY(info,at)                 \
 301     (TYPEINFO_IS_PRIMITIVE_ARRAY(info,at) || TYPEINFO_IS_NULLTYPE(info))
 302
 303 #define TYPEINFO_MAYBE_ARRAY_OF_REFS(info)                      \
 304     (TYPEINFO_IS_ARRAY_OF_REFS(info) || TYPEINFO_IS_NULLTYPE(info))
 305
 306 /* macros for initializing typeinfo structures ******************************/
 307
 308 #define TYPEINFO_INIT_PRIMITIVE(info)                           \
 309          do {(info).typeclass = NULL;                           \
 310              (info).elementclass = NULL;                        \
 311              (info).merged = NULL;                              \
 312              (info).dimension = 0;                              \
 313              (info).elementtype = 0;} while(0)
 314
 315 #define TYPEINFO_INIT_RETURNADDRESS(info,adr)                   \
 316          do {(info).typeclass = NULL;                           \
 317              (info).elementclass = (classinfo*) (adr);          \
 318              (info).merged = NULL;                              \
 319              (info).dimension = 0;                              \
 320              (info).elementtype = 0;} while(0)
 321
 322 #define TYPEINFO_INIT_NON_ARRAY_CLASSINFO(info,cinfo)   \
 323          do {(info).typeclass = (cinfo);                \
 324              (info).elementclass = NULL;                \
 325              (info).merged = NULL;                      \
 326              (info).dimension = 0;                      \
 327              (info).elementtype = 0;} while(0)
 328
 329 #define TYPEINFO_INIT_NULLTYPE(info)                            \
 330             TYPEINFO_INIT_CLASSINFO(info,pseudo_class_Null)
 331
 332 #define TYPEINFO_INIT_NEWOBJECT(info,instr)             \
 333          do {(info).typeclass = pseudo_class_New;       \
 334              (info).elementclass = (classinfo*) (instr);\
 335              (info).merged = NULL;                      \
 336              (info).dimension = 0;                      \
 337              (info).elementtype = 0;} while(0)
 338
 339 #define TYPEINFO_INIT_PRIMITIVE_ARRAY(info,arraytype)                   \
 340     TYPEINFO_INIT_CLASSINFO(info,primitivetype_table[arraytype].arrayclass);
 341
 342 #define TYPEINFO_INIT_CLASSINFO(info,cls)                               \
 343         do {if (((info).typeclass = (cls))->vftbl->arraydesc) {         \
 344                 if ((cls)->vftbl->arraydesc->elementvftbl)              \
 345                     (info).elementclass = (cls)->vftbl->arraydesc->elementvftbl->class; \
 346                 else                                                    \
 347                     (info).elementclass = NULL;                         \
 348                 (info).dimension = (cls)->vftbl->arraydesc->dimension;  \
 349                 (info).elementtype = (cls)->vftbl->arraydesc->elementtype; \
 350             }                                                           \
 351             else {                                                      \
 352                 (info).elementclass = NULL;                             \
 353                 (info).dimension = 0;                                   \
 354                 (info).elementtype = 0;                                 \
 355             }                                                           \
 356             (info).merged = NULL;} while(0)
 357
 358 #define TYPEINFO_INIT_FROM_FIELDINFO(info,fi)                   \
 359             typeinfo_init_from_descriptor(&(info),              \
 360                 (fi)->descriptor->text,utf_end((fi)->descriptor));
 361
 362 /* macros for copying types (destinition is not checked or freed) ***********/
 363
 364 /* TYPEINFO_COPY makes a shallow copy, the merged pointer is simply copied. */
 365 #define TYPEINFO_COPY(src,dst)                                  \
 366     do {(dst) = (src);} while(0)
 367
 368 /* TYPEINFO_CLONE makes a deep copy, the merged list (if any) is duplicated
 369  * into a newly allocated array.
 370  */
 371 #define TYPEINFO_CLONE(src,dst)                                 \
 372     do {(dst) = (src);                                          \
 373         if ((dst).merged) typeinfo_clone(&(src),&(dst));} while(0)
 374
 375 /****************************************************************************/
 376 /* FUNCTIONS                                                                */
 377 /****************************************************************************/
 378
 379 /* typevector functions *****************************************************/
 380
 381 /* element read-only access */
 382 bool typevectorset_checktype(typevector *set,int index,int type);
 383 bool typevectorset_checkreference(typevector *set,int index);
 384 bool typevectorset_checkretaddr(typevector *set,int index);
 385 int typevectorset_copymergedtype(typevector *set,int index,typeinfo *dst);
 386 typeinfo *typevectorset_mergedtypeinfo(typevector *set,int index,typeinfo *temp);
 387 int typevectorset_mergedtype(typevector *set,int index,typeinfo *temp,typeinfo **result);
 388
 389 /* element write access */
 390 void typevectorset_store(typevector *set,int index,int type,typeinfo *info);
 391 void typevectorset_store_retaddr(typevector *set,int index,typeinfo *info);
 392 void typevectorset_store_twoword(typevector *set,int index,int type);
 393 void typevectorset_init_object(typevector *set,void *ins,classinfo *initclass,int size);
 394
 395 /* vector functions */
 396 bool typevector_separable_from(typevector *a,typevector *b,int size);
 397 bool typevector_merge(typevector *dst,typevector *y,int size);
 398
 399 /* vector set functions */
 400 typevector *typevectorset_copy(typevector *src,int k,int size);
 401 bool typevectorset_separable_with(typevector *set,typevector *add,int size);
 402 bool typevectorset_collapse(typevector *dst,int size);
 403 void typevectorset_add(typevector *dst,typevector *v,int size);
 404 typevector *typevectorset_select(typevector **set,int retindex,void *retaddr);
 405
 406 /* inquiry functions (read-only) ********************************************/
 407
 408 bool typeinfo_is_array(typeinfo *info);
 409 bool typeinfo_is_primitive_array(typeinfo *info,int arraytype);
 410 bool typeinfo_is_array_of_refs(typeinfo *info);
 411
 412 bool typeinfo_implements_interface(typeinfo *info,classinfo *interf);
 413 bool typeinfo_is_assignable(typeinfo *value,typeinfo *dest);
 414 bool typeinfo_is_assignable_to_classinfo(typeinfo *value,classinfo *dest);
 415
 416 /* initialization functions *************************************************/
 417
 418 void typeinfo_init_from_descriptor(typeinfo *info,char *utf_ptr,char *end_ptr);
 419 void typeinfo_init_component(typeinfo *srcarray,typeinfo *dst);
 420
 421 int  typeinfo_count_method_args(utf *d,bool twoword); /* this not included */
 422 void typeinfo_init_from_method_args(utf *desc,u1 *typebuf,
 423                                     typeinfo *infobuf,
 424                                     int buflen,bool twoword,
 425                                     int *returntype,typeinfo *returntypeinfo);
 426 int  typedescriptors_init_from_method_args(typedescriptor *td,
 427                                                                                    utf *desc,
 428                                                                                    int buflen,bool twoword,
 429                                                                                    typedescriptor *returntype);
 430
 431 void typeinfo_clone(typeinfo *src,typeinfo *dest);
 432
 433 /* functions for the type system ********************************************/
 434
 435 void typeinfo_free(typeinfo *info);
 436
 437 bool typeinfo_merge(typeinfo *dest,typeinfo* y);
 438
 439 /* debugging helpers ********************************************************/
 440
 441 #ifdef TYPEINFO_DEBUG
 442
 443 #include <stdio.h>
 444
 445 void typeinfo_test();
 446 void typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc);
 447 void typeinfo_print(FILE *file,typeinfo *info,int indent);
 448 void typeinfo_print_short(FILE *file,typeinfo *info);
 449 void typeinfo_print_type(FILE *file,int type,typeinfo *info);
 450 void typeinfo_print_stacktype(FILE *file,int type,typeinfo *info);
 451 void typedescriptor_print(FILE *file,typedescriptor *td);
 452 void typevector_print(FILE *file,typevector *vec,int size);
 453 void typevectorset_print(FILE *file,typevector *set,int size);
 454
 455 #endif /* TYPEINFO_DEBUG */
 456
 457 #endif /* _TYPEINFO_H */
 458
 459
 460 /*
 461  * These are local overrides for various environment variables in Emacs.
 462  * Please do not remove this and leave it at the end of the file, where
 463  * Emacs will automagically detect them.
 464  * ---------------------------------------------------------------------
 465  * Local variables:
 466  * mode: c
 467  * indent-tabs-mode: t
 468  * c-basic-offset: 4
 469  * tab-width: 4
 470  * End:
 471  */