paul@810 | 1 | = Deducing Program Behaviour = |
paul@810 | 2 | |
paul@861 | 3 | With information from [[../Inspection|inspection]] available, the isolated |
paul@861 | 4 | observations about operations in a program may now be combined with knowledge |
paul@861 | 5 | about the program's structure to produce deductions about the nature of each |
paul@861 | 6 | operation. |
paul@810 | 7 | |
paul@810 | 8 | <<TableOfContents(2,3)>> |
paul@810 | 9 | |
paul@810 | 10 | == The Deduction Process == |
paul@810 | 11 | |
paul@861 | 12 | The deduction process takes observations made during the |
paul@861 | 13 | [[../Inspection|inspection process]] and attempts to form deductions about the |
paul@861 | 14 | behaviour of the program primarily in terms of the nature of the attribute |
paul@861 | 15 | '''accesses''', with their corresponding '''accessors''', featuring in the |
paul@861 | 16 | program. Where attributes are used in conjunction with names, accessors are |
paul@861 | 17 | name versions; where attributes are used in conjunction with other |
paul@861 | 18 | expressions, accessors are '''anonymous'''. |
paul@810 | 19 | |
paul@810 | 20 | === Indexes === |
paul@810 | 21 | |
paul@861 | 22 | For efficiency, indexes are defined to establish relationships between the |
paul@861 | 23 | following things: |
paul@810 | 24 | |
paul@810 | 25 | {{{#!table |
paul@810 | 26 | '''Indexes''' || '''Details''' |
paul@810 | 27 | == |
paul@861 | 28 | `access_index` || Which accessors (name versions) are involved with access |
paul@861 | 29 | .. operations |
paul@810 | 30 | == |
paul@861 | 31 | `location_index` || Which attribute usage patterns are supported by accessors |
paul@861 | 32 | .. (name versions) |
paul@810 | 33 | == |
paul@810 | 34 | `attr_class_types`<<BR>>`attr_instance_types`<<BR>>`attr_module_types` |
paul@810 | 35 | || Which types support which attribute names |
paul@810 | 36 | == |
paul@810 | 37 | `assigned_attrs` |
paul@810 | 38 | || Which usage patterns involve attribute assignment |
paul@810 | 39 | == |
paul@810 | 40 | `reference_assignments` |
paul@810 | 41 | || Which accesses involve assignments |
paul@810 | 42 | == |
paul@810 | 43 | `reference_invocations` |
paul@810 | 44 | || Which accesses involve invocations |
paul@810 | 45 | == |
paul@810 | 46 | `alias_index` |
paul@810 | 47 | || Which names are aliases for other names, accesses or invocations |
paul@810 | 48 | }}} |
paul@810 | 49 | |
paul@861 | 50 | The objective of deduction is to combine these indexes to establish new |
paul@861 | 51 | relationships between the different participants of these basic index |
paul@861 | 52 | relationships. |
paul@810 | 53 | |
paul@810 | 54 | === Building Indexes === |
paul@810 | 55 | |
paul@810 | 56 | The building of indexes from inspection data is approximately as follows: |
paul@810 | 57 | |
paul@810 | 58 | {{{#!graphviz |
paul@810 | 59 | //format=svg |
paul@810 | 60 | //transform=notugly |
paul@810 | 61 | digraph indexes { |
paul@810 | 62 | node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Indexes"]; |
paul@810 | 63 | edge [tooltip="Indexes"]; |
paul@810 | 64 | rankdir=LR; |
paul@810 | 65 | |
paul@810 | 66 | all_attr_accesses [label="all_attr_accesses\n(anonymous accesses)"]; |
paul@810 | 67 | attr_usage [label="attr_usage\n(attribute usage)"]; |
paul@810 | 68 | location_index [label="location_index\n(usage by accessor)"]; |
paul@810 | 69 | |
paul@810 | 70 | all_attrs [label="all_class_attrs | all_instance_attrs | all_module attrs | (all attributes)",shape=record]; |
paul@810 | 71 | attr_types [label="attr_class_types | attr_instance_types | attr_module_types | (types by attribute name)",shape=record]; |
paul@810 | 72 | |
paul@810 | 73 | attr_accessors [label="attr_accessors\n(accessors by access)"]; |
paul@810 | 74 | access_index [label="access_index\n(accessor locations by access location)"]; |
paul@810 | 75 | |
paul@810 | 76 | all_attr_access_modifiers [label="all_attr_access_modifiers\n(operations/modifiers by access)"]; |
paul@810 | 77 | reference_assignments [label="reference_assignments\n(assignment accesses)"]; |
paul@810 | 78 | reference_invocations [label="reference_invocations\n(invocation accesses)"]; |
paul@810 | 79 | assigned_attrs [label="assigned_attrs\n(assignment accesses by access)"]; |
paul@810 | 80 | |
paul@810 | 81 | all_aliased_names [label="all_aliased_names\n(accesses by alias)"]; |
paul@810 | 82 | alias_index [label="alias_index\n(access locations by accessor/alias location)"]; |
paul@810 | 83 | |
paul@810 | 84 | init_usage_index [label="init_usage_index",shape=ellipse]; |
paul@810 | 85 | init_attr_type_indexes [label="init_attr_type_indexes",shape=ellipse]; |
paul@810 | 86 | init_accessors [label="init_accessors",shape=ellipse]; |
paul@810 | 87 | init_accesses [label="init_accesses",shape=ellipse]; |
paul@810 | 88 | init_aliases [label="init_aliases",shape=ellipse]; |
paul@810 | 89 | |
paul@810 | 90 | all_attr_accesses -> init_usage_index; |
paul@810 | 91 | attr_usage -> init_usage_index; |
paul@810 | 92 | init_usage_index -> location_index; |
paul@810 | 93 | |
paul@810 | 94 | all_attrs -> init_attr_type_indexes -> attr_types; |
paul@810 | 95 | |
paul@810 | 96 | attr_accessors -> init_accessors -> access_index; |
paul@810 | 97 | |
paul@810 | 98 | all_attr_access_modifiers -> init_accesses; |
paul@810 | 99 | init_accesses -> reference_assignments; |
paul@810 | 100 | init_accesses -> reference_invocations; |
paul@810 | 101 | init_accesses -> assigned_attrs; |
paul@810 | 102 | |
paul@810 | 103 | all_aliased_names -> init_aliases -> alias_index; |
paul@810 | 104 | } |
paul@810 | 105 | }}} |
paul@810 | 106 | |
paul@810 | 107 | === Deriving Types from Indexes and Accesses === |
paul@810 | 108 | |
paul@810 | 109 | The indexes are employed in deduction approximately as follows: |
paul@810 | 110 | |
paul@810 | 111 | {{{#!graphviz |
paul@810 | 112 | //format=svg |
paul@810 | 113 | //transform=notugly |
paul@810 | 114 | digraph deduction { |
paul@810 | 115 | node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Deduction"]; |
paul@810 | 116 | edge [tooltip="Deduction"]; |
paul@810 | 117 | rankdir=LR; |
paul@810 | 118 | |
paul@810 | 119 | all_attr_accesses [label="all_attr_accesses\n(anonymous accesses)"]; |
paul@810 | 120 | location_index [label="location_index\n(usage by accessor)"]; |
paul@810 | 121 | |
paul@810 | 122 | attr_types [label="attr_class_types | attr_instance_types | attr_module_types | (types by attribute name)",shape=record]; |
paul@810 | 123 | |
paul@810 | 124 | all_initialised_names [label="all_initialised_names\n(types by accessor)"]; |
paul@810 | 125 | |
paul@810 | 126 | access_index [label="access_index\n(accessor locations by access location)"]; |
paul@810 | 127 | |
paul@810 | 128 | alias_index [label="alias_index\n(access locations by accessor/alias location)"]; |
paul@810 | 129 | |
paul@810 | 130 | record_types_for_usage [label="record_types_for_usage",shape=ellipse]; |
paul@810 | 131 | record_types_for_attribute [label="record_types_for_attribute",shape=ellipse]; |
paul@810 | 132 | |
paul@810 | 133 | accessor_types [label="accessor_class_types | accessor_instance_types | accessor_module_types | (types by accessor)",shape=record]; |
paul@810 | 134 | provider_types [label="provider_class_types | provider_instance_types | provider_module_types | (provider types by accessor)",shape=record]; |
paul@810 | 135 | |
paul@810 | 136 | location_index -> record_types_for_usage; |
paul@810 | 137 | attr_types -> record_types_for_usage; |
paul@810 | 138 | all_initialised_names -> record_types_for_usage; |
paul@810 | 139 | access_index -> record_types_for_usage; |
paul@810 | 140 | alias_index -> record_types_for_usage; |
paul@810 | 141 | |
paul@810 | 142 | record_types_for_usage -> provider_types; |
paul@810 | 143 | record_types_for_usage -> accessor_types; |
paul@810 | 144 | |
paul@810 | 145 | attr_types -> record_types_for_attribute; |
paul@810 | 146 | all_attr_accesses -> record_types_for_attribute; |
paul@810 | 147 | |
paul@810 | 148 | record_types_for_attribute -> provider_types; |
paul@810 | 149 | record_types_for_attribute -> accessor_types; |
paul@810 | 150 | } |
paul@810 | 151 | }}} |
paul@810 | 152 | |
paul@810 | 153 | === Converting Usage to Types === |
paul@810 | 154 | |
paul@861 | 155 | A particularly important operation in the deduction process is that of |
paul@861 | 156 | converting attribute usage information to a set of types supporting such |
paul@861 | 157 | usage. Taking the mapping of attribute names to types, each attribute name |
paul@861 | 158 | provided by a usage observation can be applied, progressively narrowing the |
paul@861 | 159 | set of types available to support the complete attribute usage collection. |
paul@810 | 160 | |
paul@810 | 161 | {{{#!graphviz |
paul@810 | 162 | //format=svg |
paul@810 | 163 | //transform=notugly |
paul@810 | 164 | digraph usage_to_types { |
paul@810 | 165 | node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Usage to types"]; |
paul@810 | 166 | edge [tooltip="Usage to types"]; |
paul@810 | 167 | rankdir=LR; |
paul@810 | 168 | |
paul@810 | 169 | usage [label="(a, b, c)",style=filled,fillcolor=darkorange]; |
paul@810 | 170 | |
paul@810 | 171 | subgraph { |
paul@810 | 172 | rank=same; |
paul@810 | 173 | attr_a [label="attribute a",style=filled,fillcolor=gold]; |
paul@810 | 174 | attr_b [label="attribute b",style=filled,fillcolor=gold]; |
paul@810 | 175 | attr_c [label="attribute c",style=filled,fillcolor=gold]; |
paul@810 | 176 | } |
paul@810 | 177 | |
paul@810 | 178 | index [label="types by attribute name",shape=ellipse]; |
paul@810 | 179 | |
paul@810 | 180 | subgraph { |
paul@810 | 181 | rank=same; |
paul@810 | 182 | type_P [label="type P"]; |
paul@810 | 183 | type_Q [label="type Q",style=filled,fillcolor=gold]; |
paul@810 | 184 | type_R [label="type R"]; |
paul@810 | 185 | type_S [label="type S"]; |
paul@810 | 186 | } |
paul@810 | 187 | |
paul@810 | 188 | deduction [label="(a, b, c) needs type Q",style=filled,fillcolor=darkorange]; |
paul@810 | 189 | |
paul@810 | 190 | usage -> attr_a; |
paul@810 | 191 | usage -> attr_b; |
paul@810 | 192 | usage -> attr_c; |
paul@810 | 193 | |
paul@810 | 194 | attr_a -> attr_b -> attr_c [style=dashed,dir=none]; |
paul@810 | 195 | attr_a -> index -> type_P [style=dashed,dir=none]; |
paul@810 | 196 | type_P -> type_Q -> type_R -> type_S [style=dashed,dir=none]; |
paul@810 | 197 | |
paul@810 | 198 | attr_a -> type_P; |
paul@810 | 199 | attr_a -> type_Q; |
paul@810 | 200 | attr_b -> type_Q; |
paul@810 | 201 | attr_b -> type_R; |
paul@810 | 202 | attr_c -> type_Q; |
paul@810 | 203 | attr_c -> type_S; |
paul@810 | 204 | |
paul@810 | 205 | type_Q -> deduction; |
paul@810 | 206 | } |
paul@810 | 207 | }}} |
paul@810 | 208 | |
paul@861 | 209 | The types supporting attribute usage are the attribute '''providers'''. Where |
paul@861 | 210 | providers are classes, the affected accessors in the program may also be |
paul@861 | 211 | instances, since instances also support access to attributes of the |
paul@861 | 212 | instantiated class (and its ancestors). |
paul@810 | 213 | |
paul@861 | 214 | Indexes mapping attributes to types must combine consideration of class and |
paul@861 | 215 | instance attributes in order to correctly identify instance providers. |
paul@861 | 216 | Consider the following example: |
paul@810 | 217 | |
paul@810 | 218 | {{{#!graphviz |
paul@810 | 219 | //format=svg |
paul@810 | 220 | //transform=notugly |
paul@810 | 221 | digraph instance_providers { |
paul@810 | 222 | node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Instance providers"]; |
paul@810 | 223 | edge [tooltip="Instance providers"]; |
paul@810 | 224 | rankdir=LR; |
paul@810 | 225 | |
paul@810 | 226 | usage [label="(a, b, c)",style=filled,fillcolor=darkorange]; |
paul@810 | 227 | |
paul@810 | 228 | subgraph { |
paul@810 | 229 | rank=same; |
paul@810 | 230 | combined [label="combined attributes",shape=ellipse]; |
paul@810 | 231 | attr_a [label="attribute a",style=filled,fillcolor=gold]; |
paul@810 | 232 | attr_c [label="attribute c",style=filled,fillcolor=gold]; |
paul@810 | 233 | attr_b [label="attribute b",style=filled,fillcolor=gold]; |
paul@810 | 234 | } |
paul@810 | 235 | |
paul@810 | 236 | subgraph { |
paul@810 | 237 | rank=same; |
paul@810 | 238 | class_C [label="class C"]; |
paul@810 | 239 | attr_Ca [label="attribute C.a",style=filled,fillcolor=gold]; |
paul@810 | 240 | attr_Cc [label="attribute C.c",style=filled,fillcolor=gold]; |
paul@810 | 241 | instance_C [label="instance of C"]; |
paul@810 | 242 | attr_Ib [label="attribute (C).b",style=filled,fillcolor=gold]; |
paul@810 | 243 | } |
paul@810 | 244 | |
paul@810 | 245 | type_C [label="type C",style=filled,fillcolor=darkorange]; |
paul@810 | 246 | |
paul@810 | 247 | combined -> attr_a -> attr_c -> attr_b [style=dashed,dir=none]; |
paul@810 | 248 | class_C -> attr_Ca -> attr_Cc [style=dashed,dir=none]; |
paul@810 | 249 | instance_C -> attr_Ib [style=dashed,dir=none]; |
paul@810 | 250 | |
paul@810 | 251 | usage -> attr_a -> attr_Ca; |
paul@810 | 252 | usage -> attr_b -> attr_Ib; |
paul@810 | 253 | usage -> attr_c -> attr_Cc; |
paul@810 | 254 | |
paul@810 | 255 | attr_Ca -> type_C; |
paul@810 | 256 | attr_Cc -> type_C; |
paul@810 | 257 | attr_Ib -> type_C; |
paul@810 | 258 | } |
paul@810 | 259 | }}} |
paul@810 | 260 | |
paul@861 | 261 | To recognise support by instance accessors for the usage pattern concerned, |
paul@861 | 262 | attribute details must be obtained from classes as well as instances. Note |
paul@861 | 263 | that the identified type cannot support such usage purely by providing class |
paul@861 | 264 | or instance attributes alone. |
paul@810 | 265 | |
paul@810 | 266 | === Attribute Assignments === |
paul@810 | 267 | |
paul@861 | 268 | Since attribute access operations may occur as part of assignments, the nature |
paul@861 | 269 | of accesses is recorded during inspection. Combining the indexed information |
paul@861 | 270 | for assignment accesses allows the deducer to determine the most pessimistic |
paul@861 | 271 | effects on the program structure of such assignments. |
paul@810 | 272 | |
paul@861 | 273 | Taking each attribute usage set employed by accessors involved in assignments, |
paul@861 | 274 | the types are deduced for such accessors, and each individual attribute known |
paul@861 | 275 | to be used in such assignments is then applied to the deduced types, |
paul@861 | 276 | '''mutating''' them in such a way that deductions may no longer assume a fixed |
paul@861 | 277 | identity for such attributes when obtained from these types. |
paul@810 | 278 | |
paul@810 | 279 | {{{#!graphviz |
paul@810 | 280 | //format=svg |
paul@810 | 281 | //transform=notugly |
paul@810 | 282 | digraph assignments { |
paul@810 | 283 | node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Attribute assignments"]; |
paul@810 | 284 | edge [tooltip="Attribute assignments"]; |
paul@810 | 285 | rankdir=LR; |
paul@810 | 286 | |
paul@810 | 287 | subgraph { |
paul@810 | 288 | rank=same; |
paul@810 | 289 | usage [label="(a, b, c)",style=filled,fillcolor=darkorange]; |
paul@810 | 290 | assigned [label="b is assigned",style=filled,fillcolor=darkorange]; |
paul@810 | 291 | } |
paul@810 | 292 | |
paul@810 | 293 | deduction [label="(a, b, c) needs type Q",style=filled,fillcolor=gold]; |
paul@810 | 294 | |
paul@810 | 295 | subgraph { |
paul@810 | 296 | rank=same; |
paul@810 | 297 | type_Q [label="type Q",style=filled,fillcolor=gold]; |
paul@810 | 298 | attr_Qa [label="attribute Q.a"]; |
paul@810 | 299 | attr_Qb [label="attribute Q.b\n(mutated)",style=filled,fillcolor=darkorange]; |
paul@810 | 300 | attr_Qc [label="attribute Q.c"]; |
paul@810 | 301 | } |
paul@810 | 302 | |
paul@810 | 303 | type_Q -> attr_Qa -> attr_Qb -> attr_Qc [style=dashed,dir=none]; |
paul@810 | 304 | usage -> deduction -> type_Q; |
paul@810 | 305 | assigned -> attr_Qb; |
paul@810 | 306 | } |
paul@810 | 307 | }}} |
paul@810 | 308 | |
paul@810 | 309 | === Refining Type Deductions === |
paul@810 | 310 | |
paul@810 | 311 | In the context of a specific access, the types may be resolved further: |
paul@810 | 312 | |
paul@861 | 313 | * Any name whose initialisation could be determined during inspection can be |
paul@861 | 314 | associated with its initialised type |
paul@861 | 315 | * Any name referring to a constant object can be associated with the type of |
paul@861 | 316 | that object |
paul@861 | 317 | * Usage of `self` in methods can result in only compatible class and instance |
paul@861 | 318 | types being retained from the types obtained from usage deductions |
paul@810 | 319 | |
paul@810 | 320 | === Reference Identification === |
paul@810 | 321 | |
paul@861 | 322 | The basic information about every accessor and accessed attribute in a program |
paul@861 | 323 | can now be combined to produce specific '''references''' to identities |
paul@861 | 324 | consistent with the inspection observations. Several different kinds of |
paul@861 | 325 | accessors and access situations exist: |
paul@810 | 326 | |
paul@810 | 327 | * Name-based accesses involving attribute usage |
paul@810 | 328 | * Aliases to names, possibly accompanied by accesses |
paul@810 | 329 | * Anonymous accesses involving individual attributes |
paul@810 | 330 | * Constant or previously-identified names, possibly accompanied by accesses |
paul@810 | 331 | |
paul@810 | 332 | === Aliases === |
paul@810 | 333 | |
paul@861 | 334 | Names initialised using other names or attribute accesses, or using the |
paul@861 | 335 | invocation of either of these things, are known as '''aliases'''. Information |
paul@861 | 336 | about aliases originates during inspection when such names are initialised |
paul@861 | 337 | with expression results within the program. During the resolution activity |
paul@861 | 338 | finalising the inspected details, this initialisation information is used to |
paul@861 | 339 | define relationships between aliases and other names and accesses. |
paul@810 | 340 | |
paul@861 | 341 | During deduction, attribute accesses are investigated and type information |
paul@861 | 342 | computed for both attribute accesses and accessors. The relationships defined |
paul@861 | 343 | between accesses and aliases can then be employed to propagate such deduced |
paul@861 | 344 | information to the aliases and to define appropriate type characteristics for |
paul@861 | 345 | them. |
paul@810 | 346 | |
paul@861 | 347 | Where aliases are used as the basis of attribute accesses, this propagation |
paul@861 | 348 | refines the previously deduced information about the aliases and may also |
paul@861 | 349 | refine the details of the accesses with which the alias is involved. |
paul@810 | 350 | |
paul@810 | 351 | === Invocation Target Suitability === |
paul@810 | 352 | |
paul@861 | 353 | Having identified accessed attributes, invocation information can be applied |
paul@861 | 354 | in cases where such attributes immediately participate in an invocation, |
paul@861 | 355 | comparing the specified argument details against the parameter details defined |
paul@861 | 356 | for the identified attribute, which must be a callable object for this |
paul@861 | 357 | technique to work. Where arguments do not appear to be suitable - either the |
paul@861 | 358 | number of arguments is incorrect or any keyword argument refer to non-existent |
paul@861 | 359 | parameters - the attribute providing the parameter details can be considered |
paul@861 | 360 | unsuitable for the access. |
paul@810 | 361 | |
paul@810 | 362 | === Classifying Accessors === |
paul@810 | 363 | |
paul@861 | 364 | Each accessor, being a particular version of a name, will have type |
paul@861 | 365 | information associated with it as a consequence of the deduction process. Such |
paul@861 | 366 | information takes the following forms: |
paul@810 | 367 | |
paul@861 | 368 | * Provider types, indicating which types may provide the attributes used by |
paul@861 | 369 | the accessor |
paul@810 | 370 | * Accessor types, indicating which types will actually appear as the accessor |
paul@810 | 371 | |
paul@810 | 372 | This information can be processed in a number of ways to produce the following: |
paul@810 | 373 | |
paul@861 | 374 | * All types (from all kinds of type) of providers able to provide attributes |
paul@861 | 375 | via the accessor |
paul@861 | 376 | * All types (from all kinds of type) of accessors compatible with the |
paul@861 | 377 | accessor |
paul@810 | 378 | * The most general types of accessors compatible with the accessor |
paul@810 | 379 | |
paul@861 | 380 | Where many types may be associated with an accessor, identifying the most |
paul@861 | 381 | general types involves eliminating those which are derived from others. Given |
paul@861 | 382 | that descendant types may not remove support for attributes provided by their |
paul@861 | 383 | ancestors, then where an ancestor type has been identified as a possible |
paul@861 | 384 | accessor, it should follow that all of its descendants may also have been |
paul@861 | 385 | identified as possible accessors. Since these descendants should be |
paul@861 | 386 | compatible, identifying them individually is unnecessary: merely specifying |
paul@861 | 387 | that the common ancestor or ''any'' descendant could provide an accessor is |
paul@861 | 388 | sufficient. |
paul@810 | 389 | |
paul@810 | 390 | ==== Defining Guards ==== |
paul@810 | 391 | |
paul@861 | 392 | A '''guard''' is a constraint supported by a run-time test indicating the |
paul@861 | 393 | compliance of an accessor with a particular type. Thus, where a single |
paul@861 | 394 | accessor type has been identified, a guard may be established for an accessor |
paul@861 | 395 | that tests the type of the accessor against a specific type. Where a single |
paul@861 | 396 | ''general'' accessor type is identified, a guard is established that tests the |
paul@861 | 397 | accessor against a "common" type: that is, an ancestor type with which other |
paul@861 | 398 | descendant types may comply. |
paul@810 | 399 | |
paul@810 | 400 | === Classifying Accesses === |
paul@810 | 401 | |
paul@861 | 402 | At the point of classifying accesses, information is available about the |
paul@861 | 403 | following: |
paul@810 | 404 | |
paul@810 | 405 | * The accessors potentially involved in each access |
paul@861 | 406 | * The types of accessors and the types providing attributes via those |
paul@861 | 407 | accessors |
paul@810 | 408 | * Any guards applying to the accessors |
paul@861 | 409 | * Whether an access is constrained by certain program characteristics and is |
paul@861 | 410 | thus guaranteed to be as deduced |
paul@810 | 411 | * The possible attributes referenced by the access |
paul@810 | 412 | |
paul@861 | 413 | This information can be processed in a number of ways to produce the |
paul@861 | 414 | following: |
paul@810 | 415 | |
paul@810 | 416 | * The types of accessors, both general and specific, applying to each access |
paul@861 | 417 | * The attributes that can be provided by each access, consolidating existing |
paul@861 | 418 | referenced attribute details |
paul@810 | 419 | * The general types providing the attributes |
paul@810 | 420 | |
paul@861 | 421 | Since more than one accessor may be involved, information from all accessors |
paul@861 | 422 | must be combined to determine whether guard information still applies to the |
paul@861 | 423 | access, or whether it is possible for an accessor to be used that has an |
paul@861 | 424 | uncertain type at run-time. |
paul@810 | 425 | |
paul@810 | 426 | ==== Defining Tests ==== |
paul@810 | 427 | |
paul@861 | 428 | A '''test''' at the access level is a necessary check performed on an accessor |
paul@861 | 429 | before an access to determine whether it belongs to a certain type or group of |
paul@861 | 430 | types. |
paul@810 | 431 | |
paul@861 | 432 | Where guards applying to accessors apply by extension to an access, it may not |
paul@861 | 433 | be enough to assume that the the attributes exposed by the accessor are the |
paul@861 | 434 | same as those considered acceptable through deduction. Therefore, attributes |
paul@861 | 435 | are obtained for the access using the applicable guard types as accessors. If |
paul@861 | 436 | this set of attributes does not include potentially accessible attributes |
paul@861 | 437 | (perhaps because the guard types are broadly defined and do not support all |
paul@861 | 438 | attribute usage), a test must be generated. |
paul@810 | 439 | |
paul@861 | 440 | Where a single attribute provider can be identified, a test for a specific |
paul@861 | 441 | type is generated. Where a single general type can be identified as a |
paul@861 | 442 | provider, a test against a "common" type is generated. Tests involving the |
paul@861 | 443 | built-in `object` are not generated since it is the root of all classes and |
paul@861 | 444 | such tests would merely identify an accessor as a class. In all cases where a |
paul@861 | 445 | single, specific type cannot be tested for, the general attribute validation |
paul@861 | 446 | mechanism must be used instead. |
paul@810 | 447 | |
paul@810 | 448 | == Preparing Access Descriptions == |
paul@810 | 449 | |
paul@861 | 450 | The accumulated deduced knowledge is directed towards producing access |
paul@861 | 451 | descriptions or plans which characterise each access in terms of the |
paul@861 | 452 | following: |
paul@810 | 453 | |
paul@861 | 454 | * The initial accessor, being the starting object for attribute accesses, |
paul@861 | 455 | unless a static accessor has been identified |
paul@810 | 456 | * Details of any test required on the initial accessor |
paul@810 | 457 | * Details of any type employed by the test |
paul@810 | 458 | * Any identified static accessor (to be used as the initial accessor) |
paul@861 | 459 | * Attributes needing to be traversed from the accessor that yield unambiguous |
paul@861 | 460 | objects |
paul@810 | 461 | * Access modes for each of the unambiguously-traversed attributes |
paul@861 | 462 | * Remaining attributes needing to be tested and traversed (after having |
paul@861 | 463 | traversed the above attributes) |
paul@810 | 464 | * Details of the context |
paul@810 | 465 | * Any test to apply to the context (to ensure its validity) |
paul@810 | 466 | * The method of obtaining the first attribute |
paul@810 | 467 | * The method of obtaining the final attribute |
paul@810 | 468 | * Any identified static final attribute |
paul@810 | 469 | * The kinds of objects providing the final attribute |
paul@810 | 470 | |
paul@810 | 471 | === Characterising the Accessor === |
paul@810 | 472 | |
paul@861 | 473 | For a given access location, the referenced attribute details established |
paul@861 | 474 | during deduction are used to determine... |
paul@810 | 475 | |
paul@861 | 476 | * Whether the initial accessor is static, originating from a constant access |
paul@861 | 477 | or involving an identifiable static object |
paul@810 | 478 | * Whether the initial accessor is dynamic but has a known, deduced identity |
paul@810 | 479 | |
paul@861 | 480 | Some useful information about the accessor and about the actual provider of |
paul@861 | 481 | the first accessed attribute can be defined: |
paul@810 | 482 | |
paul@810 | 483 | || || '''Class''' || '''Instance''' || '''Module''' || |
paul@810 | 484 | || '''Accessor''' || Class accessor || Instance accessor || Module accessor || |
paul@810 | 485 | || '''Provider''' || Class provider || Instance provider || || |
paul@810 | 486 | |
paul@861 | 487 | Depending on which of these criteria are satisfied, some properties of the |
paul@861 | 488 | access operation can be established: |
paul@810 | 489 | |
paul@861 | 490 | * Object-relative accesses occur with class accessors or module accessors or |
paul@861 | 491 | when attributes are provided by instances |
paul@861 | 492 | * Class-relative accesses occur with instance accessors when attributes are |
paul@861 | 493 | provided by classes |
paul@810 | 494 | |
paul@861 | 495 | Object-relative accesses merely involve obtaining attributes directly from |
paul@861 | 496 | accessors. Class-relative accesses involve obtaining the class of each |
paul@861 | 497 | accessor and then obtaining an attribute from that class. |
paul@810 | 498 | |
paul@810 | 499 | === Defining the First Access Method === |
paul@810 | 500 | |
paul@861 | 501 | For dynamic or unidentified accessors, the above access properties define the |
paul@861 | 502 | access method on the first attribute in the chain of attributes provided. |
paul@861 | 503 | However, any redefinition of the accessor to a static accessor may influence |
paul@861 | 504 | the first method. For static accessors, the first method is always |
paul@861 | 505 | object-relative since classes and modules do not offer transparent mechanisms |
paul@861 | 506 | to expose the attributes on their own classes. |
paul@810 | 507 | |
paul@861 | 508 | Static and identified, dynamic accessors should already be known to support |
paul@861 | 509 | the specified attributes. Other accessors require an access method to be used |
paul@861 | 510 | that also checks whether the accessor supports a given attribute. |
paul@810 | 511 | |
paul@810 | 512 | === Redefining the Accessor === |
paul@810 | 513 | |
paul@861 | 514 | With knowledge about the initial accessor, the attributes involved in the |
paul@861 | 515 | access operation are then considered in the context of the accessor. For each |
paul@861 | 516 | attribute name in the chain described for an access, an attempt is made to |
paul@861 | 517 | obtain the details of the attribute of the given name from the accessor, |
paul@861 | 518 | determining whether these details can be used as an accessor to obtain |
paul@861 | 519 | subsequent attribute details. |
paul@810 | 520 | |
paul@861 | 521 | Where more than one attribute identity is obtained, traversal is terminated: |
paul@861 | 522 | all remaining attributes must be traversed at run-time. If an attribute |
paul@861 | 523 | identified during traversal is static, the first access method changes |
paul@861 | 524 | accordingly. |
paul@810 | 525 | |
paul@810 | 526 | === Defining the Final Access Method === |
paul@810 | 527 | |
paul@861 | 528 | An access can also involve an assignment to the accessed attribute or the |
paul@861 | 529 | invocation of the accessed attribute. Such operations change the nature of the |
paul@861 | 530 | access method used on the final attribute in a chain of attribute names. |
paul@810 | 531 | |
paul@810 | 532 | === Identifying Context Information === |
paul@810 | 533 | |
paul@861 | 534 | Final attribute accesses involving callables need to yield context information |
paul@861 | 535 | that can subsequently be used to invoke those callables. Where the nature of |
paul@861 | 536 | an accessed attribute is not known, a simplistic attempt can be made to look |
paul@861 | 537 | up all attributes stored using the attribute name in the program. |
paul@810 | 538 | |
paul@810 | 539 | Of particular interest are the following situations: |
paul@810 | 540 | |
paul@861 | 541 | * Where class attributes are being accessed via instances, whether the |
paul@861 | 542 | attributes are all methods that can be bound upon access |
paul@861 | 543 | * Where class attributes may be accessed via instances, whether any |
paul@861 | 544 | attributes could be methods |
paul@810 | 545 | |
paul@861 | 546 | Such considerations dictate whether the context information originates from |
paul@861 | 547 | the attribute or from the accessor and whether any run-time test is required |
paul@861 | 548 | to determine this. |
paul@810 | 549 | |
paul@810 | 550 | == Preparing Instruction Plans == |
paul@810 | 551 | |
paul@861 | 552 | Instruction plans are sequences of program operations, encoded in a |
paul@861 | 553 | higher-level form than actual program instructions, that describe the steps |
paul@861 | 554 | needed to access attributes. Such sequences are produced from the details |
paul@861 | 555 | provided by individual access plans. |
paul@810 | 556 | |
paul@810 | 557 | === Original Accessor === |
paul@810 | 558 | |
paul@861 | 559 | The expression providing the object from which the first attribute is obtained |
paul@861 | 560 | (or the only attribute if only one is specified) is known as the original |
paul@861 | 561 | accessor. Where this accessor can be identified, the expression describing it |
paul@861 | 562 | in the program can potentially be replaced with a static reference, and |
paul@861 | 563 | subsequent mentions of the accessor can potentially be replaced with such |
paul@861 | 564 | references or names used as expressions. |
paul@810 | 565 | |
paul@810 | 566 | || '''Access Plan Information''' || '''Original Accessor''' || |
paul@810 | 567 | || Static accessor identified || Identified accessor || |
paul@810 | 568 | || Named accessor access, not invocation || Indicated name || |
paul@810 | 569 | || Named accessor invocation, accessor known to provide the attribute || Indicated name || |
paul@810 | 570 | || Named accessor invocation, accessor not known to provide the attribute || Accessor expression || |
paul@810 | 571 | || Other accessors || Accessor expression || |
paul@810 | 572 | |
paul@861 | 573 | By using names or static references, the need to store the result of |
paul@861 | 574 | evaluating an accessor expression is eliminated because such labels can be |
paul@861 | 575 | inserted in the instruction sequence as required. |
paul@810 | 576 | |
paul@810 | 577 | === First Access Operation === |
paul@810 | 578 | |
paul@861 | 579 | Although it may be possible to convert accesses into single instructions that |
paul@861 | 580 | obtain attributes directly, many accesses will involve access operations that |
paul@861 | 581 | must consult an accessor object and obtain an attribute from that object, at |
paul@861 | 582 | least for the first attribute in a chain of attributes. This occurs when the |
paul@861 | 583 | access plan indicates the following situations: |
paul@810 | 584 | |
paul@861 | 585 | * Final method is an access (meaning that an attribute cannot be directly |
paul@861 | 586 | obtained) |
paul@861 | 587 | * Final method is an assignment (requiring the object whose attribute will be |
paul@861 | 588 | updated) |
paul@810 | 589 | * Attributes (identified or otherwise) need traversing |
paul@810 | 590 | |
paul@810 | 591 | === Accessor Nature === |
paul@810 | 592 | |
paul@861 | 593 | Attribute assignments involve a single '''target accessor''' and potentially |
paul@861 | 594 | many other accessors, depending on how many distinct expressions are evaluated |
paul@861 | 595 | to yield the value to be set in the assignment. Such a target accessor will |
paul@861 | 596 | usually be derived from the evaluation of an expression, and in some cases the |
paul@861 | 597 | expression will be the result of an opaque operation such as the invocation of |
paul@861 | 598 | a function. In such cases, the target accessor is stored in a temporary |
paul@861 | 599 | variable for subsequent use in access operations. |
paul@810 | 600 | |
paul@810 | 601 | === Context === |
paul@810 | 602 | |
paul@810 | 603 | === Access Tests === |
paul@810 | 604 | |
paul@810 | 605 | === Traversing Identified Attributes === |
paul@810 | 606 | |
paul@810 | 607 | === Traversing Unidentified Attributes === |
paul@810 | 608 | |
paul@810 | 609 | === Final Access Operation === |
paul@810 | 610 | |
paul@810 | 611 | === Context Testing === |
paul@810 | 612 | |
paul@810 | 613 | == Deduction Products == |
paul@810 | 614 | |
paul@861 | 615 | The deduction process should produce a complete catalogue of accessor and |
paul@861 | 616 | access references that may then be consulted by the |
paul@861 | 617 | [[../Translation|translation]] process needing to know the nature of any |
paul@861 | 618 | operation within the program. Central to the translation process's |
paul@861 | 619 | understanding of references is the '''attribute access plan''' for each |
paul@861 | 620 | reference which characterises each access and provides the basis for the |
paul@861 | 621 | formulation of the '''instruction plan''' used to replicate it in the final |
paul@861 | 622 | program. |