1(**************************************************************************) 2(* *) 3(* OCaml *) 4(* *) 5(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *) 6(* *) 7(* Copyright 1996 Institut National de Recherche en Informatique et *) 8(* en Automatique. *) 9(* *) 10(* All rights reserved. This file is distributed under the terms of *) 11(* the GNU Lesser General Public License version 2.1, with the *) 12(* special exception on linking described in the file LICENSE. *) 13(* *) 14(**************************************************************************) 15 16(** {0 Representation of types and declarations} *) 17 18(** [Types] defines the representation of types and declarations (that is, the 19 content of module signatures). 20 21 CMI files are made of marshalled types. 22*) 23 24(** Asttypes exposes basic definitions shared both by Parsetree and Types. *) 25open Asttypes 26 27(** Type expressions for the core language. 28 29 The [type_desc] variant defines all the possible type expressions one can 30 find in OCaml. [type_expr] wraps this with some annotations. 31 32 The [level] field tracks the level of polymorphism associated to a type, 33 guiding the generalization algorithm. 34 Put shortly, when referring to a type in a given environment, both the type 35 and the environment have a level. If the type has an higher level, then it 36 can be considered fully polymorphic (type variables will be printed as 37 ['a]), otherwise it'll be weakly polymorphic, or non generalized (type 38 variables printed as ['_a]). 39 See [http://okmij.org/ftp/ML/generalization.html] for more information. 40 41 Note about [type_declaration]: one should not make the confusion between 42 [type_expr] and [type_declaration]. 43 44 [type_declaration] refers specifically to the [type] construct in OCaml 45 language, where you create and name a new type or type alias. 46 47 [type_expr] is used when you refer to existing types, e.g. when annotating 48 the expected type of a value. 49 50 Also, as the type system of OCaml is generative, a [type_declaration] can 51 have the side-effect of introducing a new type constructor, different from 52 all other known types. 53 Whereas [type_expr] is a pure construct which allows referring to existing 54 types. 55 56 Note on mutability: TBD. 57 *) 58type type_expr = 59 { mutable desc: type_desc; 60 mutable level: int; 61 id: int } 62 63and type_desc = 64 | Tvar of string option 65 (** [Tvar (Some "a")] ==> ['a] or ['_a] 66 [Tvar None] ==> [_] *) 67 68 | Tarrow of arg_label * type_expr * type_expr * commutable 69 (** [Tarrow (Nolabel, e1, e2, c)] ==> [e1 -> e2] 70 [Tarrow (Labelled "l", e1, e2, c)] ==> [l:e1 -> e2] 71 [Tarrow (Optional "l", e1, e2, c)] ==> [?l:e1 -> e2] 72 73 See [commutable] for the last argument. *) 74 75 | Ttuple of type_expr list 76 (** [Ttuple [t1;...;tn]] ==> [(t1 * ... * tn)] *) 77 78 | Tconstr of Path.t * type_expr list * abbrev_memo ref 79 (** [Tconstr (`A.B.t', [t1;...;tn], _)] ==> [(t1,...,tn) A.B.t] 80 The last parameter keep tracks of known expansions, see [abbrev_memo]. *) 81 82 | Tobject of type_expr * (Path.t * type_expr list) option ref 83 (** [Tobject (`f1:t1;...;fn: tn', `None')] ==> [< f1: t1; ...; fn: tn >] 84 f1, fn are represented as a linked list of types using Tfield and Tnil 85 constructors. 86 87 [Tobject (_, `Some (`A.ct', [t1;...;tn]')] ==> [(t1, ..., tn) A.ct]. 88 where A.ct is the type of some class. 89 90 There are also special cases for so-called "class-types", cf. [Typeclass] 91 and [Ctype.set_object_name]: 92 93 [Tobject (Tfield(_,_,...(Tfield(_,_,rv)...), 94 Some(`A.#ct`, [rv;t1;...;tn])] 95 ==> [(t1, ..., tn) #A.ct] 96 [Tobject (_, Some(`A.#ct`, [Tnil;t1;...;tn])] ==> [(t1, ..., tn) A.ct] 97 98 where [rv] is the hidden row variable. 99 *) 100 101 | Tfield of string * field_kind * type_expr * type_expr 102 (** [Tfield ("foo", Fpresent, t, ts)] ==> [<...; foo : t; ts>] *) 103 104 | Tnil 105 (** [Tnil] ==> [<...; >] *) 106 107 | Tlink of type_expr 108 (** Indirection used by unification engine. *) 109 110 | Tsubst of type_expr (* for copying *) 111 (** [Tsubst] is used temporarily to store information in low-level 112 functions manipulating representation of types, such as 113 instantiation or copy. 114 This constructor should not appear outside of these cases. *) 115 116 | Tvariant of row_desc 117 (** Representation of polymorphic variants, see [row_desc]. *) 118 119 | Tunivar of string option 120 (** Occurrence of a type variable introduced by a 121 forall quantifier / [Tpoly]. *) 122 123 | Tpoly of type_expr * type_expr list 124 (** [Tpoly (ty,tyl)] ==> ['a1... 'an. ty], 125 where 'a1 ... 'an are names given to types in tyl 126 and occurences of those types in ty. *) 127 128 | Tpackage of Path.t * Longident.t list * type_expr list 129 (** Type of a first-class module (a.k.a package). *) 130 131(** [ `X | `Y ] (row_closed = true) 132 [< `X | `Y ] (row_closed = true) 133 [> `X | `Y ] (row_closed = false) 134 [< `X | `Y > `X ] (row_closed = true) 135 136 type t = [> `X ] as 'a (row_more = Tvar a) 137 type t = private [> `X ] (row_more = Tconstr (t#row, [], ref Mnil) 138 139 And for: 140 141 let f = function `X -> `X -> | `Y -> `X 142 143 the type of "f" will be a [Tarrow] whose lhs will (basically) be: 144 145 Tvariant { row_fields = [("X", _)]; 146 row_more = 147 Tvariant { row_fields = [("Y", _)]; 148 row_more = 149 Tvariant { row_fields = []; 150 row_more = _; 151 _ }; 152 _ }; 153 _ 154 } 155 156*) 157and row_desc = 158 { row_fields: (label * row_field) list; 159 row_more: type_expr; 160 row_bound: unit; (* kept for compatibility *) 161 row_closed: bool; 162 row_fixed: bool; 163 row_name: (Path.t * type_expr list) option } 164 165and row_field = 166 Rpresent of type_expr option 167 | Reither of bool * type_expr list * bool * row_field option ref 168 (* 1st true denotes a constant constructor *) 169 (* 2nd true denotes a tag in a pattern matching, and 170 is erased later *) 171 | Rabsent 172 173(** [abbrev_memo] allows one to keep track of different expansions of a type 174 alias. This is done for performance purposes. 175 176 For instance, when defining [type 'a pair = 'a * 'a], when one refers to an 177 ['a pair], it is just a shortcut for the ['a * 'a] type. 178 This expansion will be stored in the [abbrev_memo] of the corresponding 179 [Tconstr] node. 180 181 In practice, [abbrev_memo] behaves like list of expansions with a mutable 182 tail. 183 184 Note on marshalling: [abbrev_memo] must not appear in saved types. 185 [Btype], with [cleanup_abbrev] and [memo], takes care of tracking and 186 removing abbreviations. 187*) 188and abbrev_memo = 189 | Mnil (** No known abbrevation *) 190 191 | Mcons of private_flag * Path.t * type_expr * type_expr * abbrev_memo 192 (** Found one abbreviation. 193 A valid abbreviation should be at least as visible and reachable by the 194 same path. 195 The first expression is the abbreviation and the second the expansion. *) 196 197 | Mlink of abbrev_memo ref 198 (** Abbreviations can be found after this indirection *) 199 200and field_kind = 201 Fvar of field_kind option ref 202 | Fpresent 203 | Fabsent 204 205(** [commutable] is a flag appended to every arrow type. 206 207 When typing an application, if the type of the functional is 208 known, its type is instantiated with [Cok] arrows, otherwise as 209 [Clink (ref Cunknown)]. 210 211 When the type is not known, the application will be used to infer 212 the actual type. This is fragile in presence of labels where 213 there is no principal type. 214 215 Two incompatible applications relying on [Cunknown] arrows will 216 trigger an error. 217 218 let f g = 219 g ~a:() ~b:(); 220 g ~b:() ~a:(); 221 222 Error: This function is applied to arguments 223 in an order different from other calls. 224 This is only allowed when the real type is known. 225*) 226and commutable = 227 Cok 228 | Cunknown 229 | Clink of commutable ref 230 231module TypeOps : sig 232 type t = type_expr 233 val compare : t -> t -> int 234 val equal : t -> t -> bool 235 val hash : t -> int 236end 237 238(* Maps of methods and instance variables *) 239 240module Meths : Map.S with type key = string 241module Vars : Map.S with type key = string 242 243(* Value descriptions *) 244 245type value_description = 246 { val_type: type_expr; (* Type of the value *) 247 val_kind: value_kind; 248 val_loc: Location.t; 249 val_attributes: Parsetree.attributes; 250 } 251 252and value_kind = 253 Val_reg (* Regular value *) 254 | Val_prim of Primitive.description (* Primitive *) 255 | Val_ivar of mutable_flag * string (* Instance variable (mutable ?) *) 256 | Val_self of (Ident.t * type_expr) Meths.t ref * 257 (Ident.t * mutable_flag * virtual_flag * type_expr) Vars.t ref * 258 string * type_expr 259 (* Self *) 260 | Val_anc of (string * Ident.t) list * string 261 (* Ancestor *) 262 | Val_unbound (* Unbound variable *) 263 264(* Variance *) 265 266module Variance : sig 267 type t 268 type f = May_pos | May_neg | May_weak | Inj | Pos | Neg | Inv 269 val null : t (* no occurence *) 270 val full : t (* strictly invariant *) 271 val covariant : t (* strictly covariant *) 272 val may_inv : t (* maybe invariant *) 273 val union : t -> t -> t 274 val inter : t -> t -> t 275 val subset : t -> t -> bool 276 val set : f -> bool -> t -> t 277 val mem : f -> t -> bool 278 val conjugate : t -> t (* exchange positive and negative *) 279 val get_upper : t -> bool * bool (* may_pos, may_neg *) 280 val get_lower : t -> bool * bool * bool * bool (* pos, neg, inv, inj *) 281end 282 283(* Type definitions *) 284 285type type_declaration = 286 { type_params: type_expr list; 287 type_arity: int; 288 type_kind: type_kind; 289 type_private: private_flag; 290 type_manifest: type_expr option; 291 type_variance: Variance.t list; 292 (* covariant, contravariant, weakly contravariant, injective *) 293 type_newtype_level: (int * int) option; 294 (* definition level * expansion level *) 295 type_loc: Location.t; 296 type_attributes: Parsetree.attributes; 297 type_immediate: bool; (* true iff type should not be a pointer *) 298 type_unboxed: unboxed_status; 299 } 300 301and type_kind = 302 Type_abstract 303 | Type_record of label_declaration list * record_representation 304 | Type_variant of constructor_declaration list 305 | Type_open 306 307and record_representation = 308 Record_regular (* All fields are boxed / tagged *) 309 | Record_float (* All fields are floats *) 310 | Record_unboxed of bool (* Unboxed single-field record, inlined or not *) 311 | Record_inlined of int (* Inlined record *) 312 | Record_extension (* Inlined record under extension *) 313 314and label_declaration = 315 { 316 ld_id: Ident.t; 317 ld_mutable: mutable_flag; 318 ld_type: type_expr; 319 ld_loc: Location.t; 320 ld_attributes: Parsetree.attributes; 321 } 322 323and constructor_declaration = 324 { 325 cd_id: Ident.t; 326 cd_args: constructor_arguments; 327 cd_res: type_expr option; 328 cd_loc: Location.t; 329 cd_attributes: Parsetree.attributes; 330 } 331 332and constructor_arguments = 333 | Cstr_tuple of type_expr list 334 | Cstr_record of label_declaration list 335 336and unboxed_status = private 337 (* This type must be private in order to ensure perfect sharing of the 338 four possible values. Otherwise, ocamlc.byte and ocamlc.opt produce 339 different executables. *) 340 { 341 unboxed: bool; 342 default: bool; (* True for unannotated unboxable types. *) 343 } 344 345val unboxed_false_default_false : unboxed_status 346val unboxed_false_default_true : unboxed_status 347val unboxed_true_default_false : unboxed_status 348val unboxed_true_default_true : unboxed_status 349 350type extension_constructor = 351 { 352 ext_type_path: Path.t; 353 ext_type_params: type_expr list; 354 ext_args: constructor_arguments; 355 ext_ret_type: type_expr option; 356 ext_private: private_flag; 357 ext_loc: Location.t; 358 ext_attributes: Parsetree.attributes; 359 } 360 361and type_transparence = 362 Type_public (* unrestricted expansion *) 363 | Type_new (* "new" type *) 364 | Type_private (* private type *) 365 366(* Type expressions for the class language *) 367 368module Concr : Set.S with type elt = string 369 370type class_type = 371 Cty_constr of Path.t * type_expr list * class_type 372 | Cty_signature of class_signature 373 | Cty_arrow of arg_label * type_expr * class_type 374 375and class_signature = 376 { csig_self: type_expr; 377 csig_vars: 378 (Asttypes.mutable_flag * Asttypes.virtual_flag * type_expr) Vars.t; 379 csig_concr: Concr.t; 380 csig_inher: (Path.t * type_expr list) list } 381 382type class_declaration = 383 { cty_params: type_expr list; 384 mutable cty_type: class_type; 385 cty_path: Path.t; 386 cty_new: type_expr option; 387 cty_variance: Variance.t list; 388 cty_loc: Location.t; 389 cty_attributes: Parsetree.attributes; 390 } 391 392type class_type_declaration = 393 { clty_params: type_expr list; 394 clty_type: class_type; 395 clty_path: Path.t; 396 clty_variance: Variance.t list; 397 clty_loc: Location.t; 398 clty_attributes: Parsetree.attributes; 399 } 400 401(* Type expressions for the module language *) 402 403type module_type = 404 Mty_ident of Path.t 405 | Mty_signature of signature 406 | Mty_functor of Ident.t * module_type option * module_type 407 | Mty_alias of alias_presence * Path.t 408 409and alias_presence = 410 | Mta_present 411 | Mta_absent 412 413and signature = signature_item list 414 415and signature_item = 416 Sig_value of Ident.t * value_description 417 | Sig_type of Ident.t * type_declaration * rec_status 418 | Sig_typext of Ident.t * extension_constructor * ext_status 419 | Sig_module of Ident.t * module_declaration * rec_status 420 | Sig_modtype of Ident.t * modtype_declaration 421 | Sig_class of Ident.t * class_declaration * rec_status 422 | Sig_class_type of Ident.t * class_type_declaration * rec_status 423 424and module_declaration = 425 { 426 md_type: module_type; 427 md_attributes: Parsetree.attributes; 428 md_loc: Location.t; 429 } 430 431and modtype_declaration = 432 { 433 mtd_type: module_type option; (* None: abstract *) 434 mtd_attributes: Parsetree.attributes; 435 mtd_loc: Location.t; 436 } 437 438and rec_status = 439 Trec_not (* first in a nonrecursive group *) 440 | Trec_first (* first in a recursive group *) 441 | Trec_next (* not first in a recursive/nonrecursive group *) 442 443and ext_status = 444 Text_first (* first constructor in an extension *) 445 | Text_next (* not first constructor in an extension *) 446 | Text_exception 447 448 449(* Constructor and record label descriptions inserted held in typing 450 environments *) 451 452type constructor_description = 453 { cstr_name: string; (* Constructor name *) 454 cstr_res: type_expr; (* Type of the result *) 455 cstr_existentials: type_expr list; (* list of existentials *) 456 cstr_args: type_expr list; (* Type of the arguments *) 457 cstr_arity: int; (* Number of arguments *) 458 cstr_tag: constructor_tag; (* Tag for heap blocks *) 459 cstr_consts: int; (* Number of constant constructors *) 460 cstr_nonconsts: int; (* Number of non-const constructors *) 461 cstr_normal: int; (* Number of non generalized constrs *) 462 cstr_generalized: bool; (* Constrained return type? *) 463 cstr_private: private_flag; (* Read-only constructor? *) 464 cstr_loc: Location.t; 465 cstr_attributes: Parsetree.attributes; 466 cstr_inlined: type_declaration option; 467 } 468 469and constructor_tag = 470 Cstr_constant of int (* Constant constructor (an int) *) 471 | Cstr_block of int (* Regular constructor (a block) *) 472 | Cstr_unboxed (* Constructor of an unboxed type *) 473 | Cstr_extension of Path.t * bool (* Extension constructor 474 true if a constant false if a block*) 475 476type label_description = 477 { lbl_name: string; (* Short name *) 478 lbl_res: type_expr; (* Type of the result *) 479 lbl_arg: type_expr; (* Type of the argument *) 480 lbl_mut: mutable_flag; (* Is this a mutable field? *) 481 lbl_pos: int; (* Position in block *) 482 lbl_all: label_description array; (* All the labels in this type *) 483 lbl_repres: record_representation; (* Representation for this record *) 484 lbl_private: private_flag; (* Read-only field? *) 485 lbl_loc: Location.t; 486 lbl_attributes: Parsetree.attributes; 487 } 488