src/vm/jit/verify/typeinfo.h

   1 /* src/vm/jit/verify/typeinfo.h - type system used by the type checker
   2
   3    Copyright (C) 1996-2005, 2006, 2007, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23 */
  24
  25 #ifndef _TYPEINFO_H
  26 #define _TYPEINFO_H
  27
  28 /* resolve typedef cycles *****************************************************/
  29
  30 typedef struct typeinfo            typeinfo_t;
  31 typedef struct typeinfo_mergedlist typeinfo_mergedlist_t;
  32 typedef struct typedescriptor      typedescriptor_t;
  33
  34 #include "config.h"
  35 #include "vm/types.h"
  36
  37 #include "vm/global.h"
  38
  39 #include "vmcore/references.h"
  40
  41
  42 /* configuration **************************************************************/
  43
  44 /*
  45  * TYPECHECK_STATISTICS activates gathering statistical information.
  46  * TYPEINFO_DEBUG activates debug checks and debug helpers in typeinfo.c
  47  * TYPECHECK_DEBUG activates debug checks in typecheck.c
  48  * TYPEINFO_DEBUG_TEST activates the typeinfo test at startup.
  49  * TYPECHECK_VERBOSE_IMPORTANT activates important debug messages
  50  * TYPECHECK_VERBOSE activates all debug messages
  51  * TYPEINFO_VERBOSE activates debug prints in typeinfo.c
  52  */
  53 #ifdef ENABLE_VERIFIER
  54 #ifndef NDEBUG
  55 /*#define TYPECHECK_STATISTICS*/
  56 #define TYPEINFO_DEBUG
  57 /*#define TYPEINFO_VERBOSE*/
  58 #define TYPECHECK_DEBUG
  59 /*#define TYPEINFO_DEBUG_TEST*/
  60 /*#define TYPECHECK_VERBOSE*/
  61 /*#define TYPECHECK_VERBOSE_IMPORTANT*/
  62 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
  63 #define TYPECHECK_VERBOSE_OPT
  64 #endif
  65 #endif
  66 #endif
  67
  68 #ifdef TYPECHECK_VERBOSE_OPT
  69 extern bool opt_typecheckverbose;
  70 #endif
  71
  72 /* types **********************************************************************/
  73
  74 /* typecheck_result - return type for boolean and tristate  functions     */
  75 /*                    which may also throw exceptions (typecheck_FAIL).   */
  76
  77 /* NOTE: Use the enum values, not the uppercase #define macros!          */
  78 #define TYPECHECK_MAYBE  0x02
  79 #define TYPECHECK_FAIL   0x04
  80
  81 typedef enum {
  82         typecheck_FALSE = false,
  83         typecheck_TRUE  = true,
  84         typecheck_MAYBE = TYPECHECK_MAYBE,
  85         typecheck_FAIL  = TYPECHECK_FAIL
  86 } typecheck_result;
  87
  88 /* check that typecheck_MAYBE is not ambiguous */
  89 #if TYPECHECK_MAYBE == true
  90 #error "`typecheck_MAYBE` must not be the same as `true`"
  91 #endif
  92 #if TYPECHECK_MAYBE == false
  93 #error "`typecheck_MAYBE` must not be the same as `false`"
  94 #endif
  95
  96 /* check that typecheck_FAIL is not ambiguous */
  97 #if (true & TYPECHECK_FAIL) != 0
  98 #error "`true` must not have bit 0x02 set (conflicts with typecheck_FAIL)"
  99 #endif
 100
 101 /* data structures for the type system ****************************************/
 102
 103 /* The typeinfo structure stores detailed information on address types.
 104  * (stack elements, variables, etc. with type == TYPE_ADR.)
 105  *
 106  * There are two kinds of address types which can be distinguished by
 107  * the value of the typeclass field:
 108  *
 109  * 1) typeclass == NULL: returnAddress type
 110  *                       use TYPEINFO_IS_PRIMITIVE to test for this
 111  *
 112  * 2) typeclass != NULL: reference type
 113  *                       use TYPEINFO_IS_REFERENCE to test for this
 114  *
 115  * Note: For non-address types either there is no typeinfo allocated
 116  * or the fields of the typeinfo struct contain undefined values!
 117  * DO NOT access the typeinfo for non-address types!
 118  *
 119  * CAUTION: The typeinfo structure should be considered opaque outside of
 120  *          typeinfo.[ch]. Please use the macros and functions defined here to
 121  *          access typeinfo structures!
 122  */
 123
 124 /* At all times *exactly one* of the following conditions is true for
 125  * a particular typeinfo struct:
 126  *
 127  * A) typeclass == NULL
 128  *
 129  *        This is a returnAddress type.
 130  *
 131  *        Use TYPEINFO_IS_PRIMITIVE to check for this.
 132  *        Use TYPEINFO_RETURNADDRESS to access the pointer in elementclass.
 133  *        Don't access other fields of the struct.
 134  *
 135  * B) typeclass == pseudo_class_Null
 136  *
 137  *        This is the null-reference type.
 138  *        Use TYPEINFO_IS_NULLTYPE to check for this.
 139  *        Don't access other fields of the struct.
 140  *
 141  * C) typeclass == pseudo_class_New
 142  *
 143  *        This is an 'uninitialized object' type. elementclass can be
 144  *        cast to instruction* and points to the NEW instruction
 145  *        responsible for creating this type.
 146  *
 147  *        Use TYPEINFO_NEWOBJECT_INSTRUCTION to access the pointer in
 148  *        elementclass.
 149  *        Don't access other fields of the struct.
 150  *
 151  * D) typeclass == pseudo_class_Arraystub
 152  *
 153  *        This type is used to represent the result of merging array types
 154  *        with incompatible component types. An arraystub allows no access
 155  *        to its components (since their type is undefined), but it allows
 156  *        operations which act directly on an arbitrary array type (such as
 157  *        requesting the array size).
 158  *
 159  *        NOTE: An array stub does *not* count as an array. It has dimension
 160  *              zero.
 161  *
 162  *        Otherwise like a normal class reference type.
 163  *        Don't access other fields of the struct.
 164  *
 165  * E) typeclass is an array class
 166  *
 167  *        An array reference.
 168  *            elementclass...typeclass of the element type
 169  *            dimension......dimension of the array (>=1)
 170  *            elementtype....element type (ARRAYTYPE_...)
 171  *            merged.........mergedlist of the element type
 172  *
 173  *        Use TYPEINFO_IS_ARRAY to check for this case.
 174  *
 175  *        The elementclass may be one of the following:
 176  *        1) pseudo_class_Arraystub
 177  *        2) an unresolved type
 178  *        3) a loaded interface
 179  *        4) a loaded (non-pseudo-,non-array-)class != (BOOTSTRAP)java.lang.Object
 180  *                Note: `merged` may be used
 181  *        5) (BOOTSTRAP)java.lang.Object
 182  *                Note: `merged` may be used
 183  *
 184  *        For the semantics of the merged field in cases 4) and 5) consult the
 185  *        corresponding descriptions with `elementclass` replaced by `typeclass`.
 186  *
 187  * F) typeclass is an unresolved type (a symbolic class/interface reference)
 188  *
 189  *        The type has not been resolved yet. (Meaning it corresponds to an
 190  *        unloaded class or interface).
 191  *        Don't access other fields of the struct.
 192  *
 193  * G) typeclass is a loaded interface
 194  *
 195  *        An interface reference type.
 196  *        Don't access other fields of the struct.
 197  *
 198  * H) typeclass is a loaded (non-pseudo-,non-array-)class != (BOOTSTRAP)java.lang.Object
 199  *
 200  *        A loaded class type.
 201  *        All classref_or_classinfos in u.merged.list (if any) are
 202  *        loaded subclasses of typeclass (no interfaces, array classes, or
 203  *        unresolved types).
 204  *        Don't access other fields of the struct.
 205  *
 206  * I) typeclass is (BOOTSTRAP)java.lang.Object
 207  *
 208  *        The most general kind of reference type.
 209  *        In this case u.merged.count and u.merged.list
 210  *        are valid and may be non-zero.
 211  *        The classref_or_classinfos in u.merged.list (if any) may be
 212  *        classes, interfaces, pseudo classes or unresolved types.
 213  *        Don't access other fields of the struct.
 214  */
 215
 216 /* The following algorithm is used to determine if the type described
 217  * by this typeinfo struct supports the interface X:  * XXX add MAYBE *
 218  *
 219  *     1) If typeclass is X or a subinterface of X the answer is "yes".
 220  *     2) If typeclass is a (pseudo) class implementing X the answer is "yes".
 221  *     3) If typeclass is not an array and u.merged.count>0
 222  *        and all classes/interfaces in u.merged.list implement X
 223  *        the answer is "yes".
 224  *     4) If none of the above is true the answer is "no".
 225  */
 226
 227 /*
 228  * CAUTION: The typeinfo structure should be considered opaque outside of
 229  *          typeinfo.[ch]. Please use the macros and functions defined here to
 230  *          access typeinfo structures!
 231  */
 232 struct typeinfo {
 233         classref_or_classinfo  typeclass;
 234         classref_or_classinfo  elementclass; /* valid if dimension>0 */ /* various uses! */
 235         typeinfo_mergedlist_t *merged;
 236         u1                     dimension;
 237         u1                     elementtype;  /* valid if dimension>0           */
 238 };
 239
 240 struct typeinfo_mergedlist {
 241         s4                    count;
 242         classref_or_classinfo list[1];       /* variable length!                        */
 243 };
 244
 245 /* a type descriptor stores a basic type and the typeinfo                */
 246 /* this is used for storing the type of a local variable, and for        */
 247 /* storing types in the signature of a method                            */
 248
 249 struct typedescriptor {
 250         typeinfo_t      typeinfo; /* valid if type == TYPE_ADR               */
 251         u1              type;     /* basic type (TYPE_INT, ...)              */
 252 };
 253
 254 /****************************************************************************/
 255 /* MACROS                                                                   */
 256 /****************************************************************************/
 257
 258 /* NOTE: The TYPEINFO macros take typeinfo *structs*, not pointers as
 259  *       arguments.  You have to dereference any pointers.
 260  */
 261
 262 /* typevectors **************************************************************/
 263
 264 #define TYPEVECTOR_SIZE(size)                                           \
 265     ((size) * sizeof(varinfo))
 266
 267 #define DNEW_TYPEVECTOR(size)                                           \
 268     ((varinfo *) DMNEW(uint8_t, TYPEVECTOR_SIZE(size)))
 269
 270 #define DMNEW_TYPEVECTOR(num,size)                                              \
 271     ((void *) DMNEW(uint8_t, (num) * TYPEVECTOR_SIZE(size)))
 272
 273 #define MGET_TYPEVECTOR(array,index,size) \
 274     ((varinfo*) (((u1*)(array)) + TYPEVECTOR_SIZE(size) * (index)))
 275
 276 /* internally used macros ***************************************************/
 277
 278 /* internal, don't use this explicitly! */
 279 #define TYPEINFO_ALLOCMERGED(mergedlist,count)                                  \
 280     do {(mergedlist) = (typeinfo_mergedlist_t *) DMNEW(uint8_t, \
 281             sizeof(typeinfo_mergedlist_t)                       \
 282             + ((count)-1)*sizeof(classinfo*));} while(0)
 283
 284 /* internal, don't use this explicitly! */
 285 #define TYPEINFO_FREEMERGED(mergedlist)
 286
 287 /* internal, don't use this explicitly! */
 288 #define TYPEINFO_FREEMERGED_IF_ANY(mergedlist)
 289
 290 /* macros for type queries **************************************************/
 291
 292 #define TYPEINFO_IS_PRIMITIVE(info)                             \
 293             ((info).typeclass.any == NULL)
 294
 295 #define TYPEINFO_IS_REFERENCE(info)                             \
 296             ((info).typeclass.any != NULL)
 297
 298 #define TYPEINFO_IS_NULLTYPE(info)                              \
 299             ((info).typeclass.cls == pseudo_class_Null)
 300
 301 #define TYPEINFO_IS_NEWOBJECT(info)                             \
 302             ((info).typeclass.cls == pseudo_class_New)
 303
 304 #define TYPEINFO_IS_JAVA_LANG_CLASS(info)                       \
 305             ((info).typeclass.cls == class_java_lang_Class)
 306
 307 /* only use this if TYPEINFO_IS_PRIMITIVE returned true! */
 308 #define TYPEINFO_RETURNADDRESS(info)                            \
 309             ((info).elementclass.any)
 310
 311 /* only use this if TYPEINFO_IS_NEWOBJECT returned true! */
 312 #define TYPEINFO_NEWOBJECT_INSTRUCTION(info)                    \
 313                 ((info).elementclass.any)
 314
 315 /* only use this if TYPEINFO_IS_JAVA_LANG_CLASS returned true! */
 316 #define TYPEINFO_JAVA_LANG_CLASS_CLASSREF(info)                 \
 317                 ((info).elementclass.ref)
 318
 319 /* macros for array type queries ********************************************/
 320
 321 #define TYPEINFO_IS_ARRAY(info)                                 \
 322             ( TYPEINFO_IS_REFERENCE(info)                       \
 323               && ((info).dimension != 0) )
 324
 325 #define TYPEINFO_IS_SIMPLE_ARRAY(info)                          \
 326             ( ((info).dimension == 1) )
 327
 328 #define TYPEINFO_IS_ARRAY_ARRAY(info)                           \
 329             ( ((info).dimension >= 2) )
 330
 331 #define TYPEINFO_IS_PRIMITIVE_ARRAY(info,arraytype)             \
 332             ( TYPEINFO_IS_SIMPLE_ARRAY(info)                    \
 333               && ((info).elementtype == (arraytype)) )
 334
 335 #define TYPEINFO_IS_OBJECT_ARRAY(info)                          \
 336             ( TYPEINFO_IS_SIMPLE_ARRAY(info)                    \
 337               && ((info).elementclass.any != NULL) )
 338
 339 /* assumes that info describes an array type */
 340 #define TYPEINFO_IS_ARRAY_OF_REFS_NOCHECK(info)                 \
 341             ( ((info).elementclass.any != NULL)                 \
 342               || ((info).dimension >= 2) )
 343
 344 #define TYPEINFO_IS_ARRAY_OF_REFS(info)                         \
 345             ( TYPEINFO_IS_ARRAY(info)                           \
 346               && TYPEINFO_IS_ARRAY_OF_REFS_NOCHECK(info) )
 347
 348 #define TYPE_IS_RETURNADDRESS(type,info)                        \
 349             ( ((type)==TYPE_RET)                                \
 350               && TYPEINFO_IS_PRIMITIVE(info) )
 351
 352 #define TYPE_IS_REFERENCE(type,info)                            \
 353             ( ((type)==TYPE_ADR)                                \
 354               && !TYPEINFO_IS_PRIMITIVE(info) )
 355
 356 #define TYPEDESC_IS_RETURNADDRESS(td)                           \
 357             TYPE_IS_RETURNADDRESS((td).type,(td).typeinfo)
 358
 359 #define TYPEDESC_IS_REFERENCE(td)                               \
 360             TYPE_IS_REFERENCE((td).type,(td).typeinfo)
 361
 362 /* queries allowing the null type ********************************************/
 363
 364 #define TYPEINFO_MAYBE_ARRAY(info)                              \
 365     (TYPEINFO_IS_ARRAY(info) || TYPEINFO_IS_NULLTYPE(info))
 366
 367 #define TYPEINFO_MAYBE_PRIMITIVE_ARRAY(info,at)                 \
 368     (TYPEINFO_IS_PRIMITIVE_ARRAY(info,at) || TYPEINFO_IS_NULLTYPE(info))
 369
 370 #define TYPEINFO_MAYBE_ARRAY_OF_REFS(info)                      \
 371     (TYPEINFO_IS_ARRAY_OF_REFS(info) || TYPEINFO_IS_NULLTYPE(info))
 372
 373 /* macros for initializing typeinfo structures ******************************/
 374
 375 #define TYPEINFO_INIT_PRIMITIVE(info)                           \
 376          do {(info).typeclass.any = NULL;                       \
 377              (info).elementclass.any = NULL;                    \
 378              (info).merged = NULL;                              \
 379              (info).dimension = 0;                              \
 380              (info).elementtype = 0;} while(0)
 381
 382 #define TYPEINFO_INIT_RETURNADDRESS(info,adr)                   \
 383          do {(info).typeclass.any = NULL;                       \
 384              (info).elementclass.any = (adr);                   \
 385              (info).merged = NULL;                              \
 386              (info).dimension = 0;                              \
 387              (info).elementtype = 0;} while(0)
 388
 389 #define TYPEINFO_INIT_NON_ARRAY_CLASSINFO(info,cinfo)   \
 390          do {(info).typeclass.cls = (cinfo);            \
 391              (info).elementclass.any = NULL;            \
 392              (info).merged = NULL;                      \
 393              (info).dimension = 0;                      \
 394              (info).elementtype = 0;} while(0)
 395
 396 #define TYPEINFO_INIT_JAVA_LANG_CLASS(info,c)                   \
 397          do {(info).typeclass.any = class_java_lang_Class;      \
 398              (info).elementclass = (c);                         \
 399              (info).merged = NULL;                              \
 400              (info).dimension = 0;                              \
 401              (info).elementtype = 0;} while(0)
 402
 403 #define TYPEINFO_INIT_NULLTYPE(info)                            \
 404             TYPEINFO_INIT_NON_ARRAY_CLASSINFO(info,pseudo_class_Null)
 405
 406 #define TYPEINFO_INIT_NEWOBJECT(info,instr)             \
 407          do {(info).typeclass.cls = pseudo_class_New;   \
 408              (info).elementclass.any = (instr);         \
 409              (info).merged = NULL;                      \
 410              (info).dimension = 0;                      \
 411              (info).elementtype = 0;} while(0)
 412
 413 #define TYPEINFO_INIT_PRIMITIVE_ARRAY(info,arraytype)                   \
 414     typeinfo_init_classinfo(&(info),primitivetype_table[arraytype].arrayclass);
 415
 416 /* macros for copying types (destinition is not checked or freed) ***********/
 417
 418 /* TYPEINFO_COPY makes a shallow copy, the merged pointer is simply copied. */
 419 #define TYPEINFO_COPY(src,dst)                                  \
 420     do {(dst) = (src);} while(0)
 421
 422 /* TYPEINFO_CLONE makes a deep copy, the merged list (if any) is duplicated
 423  * into a newly allocated array.
 424  */
 425 #define TYPEINFO_CLONE(src,dst)                                 \
 426     do {(dst) = (src);                                          \
 427         if ((dst).merged) typeinfo_clone(&(src),&(dst));} while(0)
 428
 429 /****************************************************************************/
 430 /* FUNCTIONS                                                                */
 431 /****************************************************************************/
 432
 433 /* typevector functions *****************************************************/
 434
 435 /* element read-only access */
 436 bool typevector_checktype(varinfo *set,int index,int type);
 437 bool typevector_checkreference(varinfo *set,int index);
 438 bool typevector_checkretaddr(varinfo *set,int index);
 439
 440 /* element write access */
 441 void typevector_store(varinfo *set,int index,int type,typeinfo_t *info);
 442 void typevector_store_retaddr(varinfo *set,int index,typeinfo_t *info);
 443 bool typevector_init_object(varinfo *set,void *ins,classref_or_classinfo initclass,int size);
 444
 445 /* vector functions */
 446 varinfo *typevector_copy(varinfo *src,int size);
 447 void typevector_copy_inplace(varinfo *src,varinfo *dst,int size);
 448 typecheck_result typevector_merge(methodinfo *m,varinfo *dst,varinfo *y,int size);
 449
 450 /* inquiry functions (read-only) ********************************************/
 451
 452 bool typeinfo_is_array(typeinfo_t *info);
 453 bool typeinfo_is_primitive_array(typeinfo_t *info,int arraytype);
 454 bool typeinfo_is_array_of_refs(typeinfo_t *info);
 455
 456 typecheck_result typeinfo_is_assignable(typeinfo_t *value,typeinfo_t *dest);
 457 typecheck_result typeinfo_is_assignable_to_class(typeinfo_t *value,classref_or_classinfo dest);
 458
 459 /* initialization functions *************************************************/
 460
 461 /* RETURN VALUE (bool):
 462  *     true.............ok,
 463  *     false............an exception has been thrown.
 464  *
 465  * RETURN VALUE (int):
 466  *     >= 0.............ok,
 467  *     -1...............an exception has been thrown.
 468  */
 469 void typeinfo_init_classinfo(typeinfo_t *info,classinfo *c);
 470 bool typeinfo_init_class(typeinfo_t *info,classref_or_classinfo c);
 471 bool typeinfo_init_component(typeinfo_t *srcarray,typeinfo_t *dst);
 472
 473 bool typeinfo_init_from_typedesc(typedesc *desc,u1 *type,typeinfo_t *info);
 474 bool typeinfos_init_from_methoddesc(methoddesc *desc,u1 *typebuf,
 475                                    typeinfo_t *infobuf,
 476                                    int buflen,bool twoword,
 477                                    u1 *returntype,typeinfo_t *returntypeinfo);
 478 bool  typedescriptor_init_from_typedesc(typedescriptor_t *td,
 479                                                                             typedesc *desc);
 480 bool  typeinfo_init_varinfo_from_typedesc(varinfo *var,
 481                                                                             typedesc *desc);
 482 int  typedescriptors_init_from_methoddesc(typedescriptor_t *td,
 483                                                                                   methoddesc *desc,
 484                                                                                   int buflen,bool twoword,int startindex,
 485                                                                                   typedescriptor_t *returntype);
 486 bool typeinfo_init_varinfos_from_methoddesc(varinfo *vars,
 487                                                                                   methoddesc *desc,
 488                                                                                   int buflen, int startindex,
 489                                                                                   s4 *map,
 490                                                                                   typedescriptor_t *returntype);
 491
 492 void typeinfo_clone(typeinfo_t *src,typeinfo_t *dest);
 493
 494 /* freeing memory ***********************************************************/
 495
 496 void typeinfo_free(typeinfo_t *info);
 497
 498 /* functions for merging types **********************************************/
 499
 500 typecheck_result typeinfo_merge(methodinfo *m,typeinfo_t *dest,typeinfo_t* y);
 501
 502 /* debugging helpers ********************************************************/
 503
 504 #ifdef TYPEINFO_DEBUG
 505
 506 #include <stdio.h>
 507
 508 void typeinfo_test();
 509 void typeinfo_print_class(FILE *file,classref_or_classinfo c);
 510 void typeinfo_print(FILE *file,typeinfo_t *info,int indent);
 511 void typeinfo_print_short(FILE *file,typeinfo_t *info);
 512 void typeinfo_print_type(FILE *file,int type,typeinfo_t *info);
 513 void typedescriptor_print(FILE *file,typedescriptor_t *td);
 514 void typevector_print(FILE *file,varinfo *vec,int size);
 515
 516 #endif /* TYPEINFO_DEBUG */
 517
 518 #endif /* _TYPEINFO_H */
 519
 520
 521 /*
 522  * These are local overrides for various environment variables in Emacs.
 523  * Please do not remove this and leave it at the end of the file, where
 524  * Emacs will automagically detect them.
 525  * ---------------------------------------------------------------------
 526  * Local variables:
 527  * mode: c
 528  * indent-tabs-mode: t
 529  * c-basic-offset: 4
 530  * tab-width: 4
 531  * End:
 532  */