src/vm/jit/verify/typeinfo.h

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