Lichen

Annotated docs/wiki/Deduction

862:0c3887bb6ff8
2019-01-17 Paul Boddie Expanded various sections and formatted the text in various places.
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@862 12
The deduction process takes observations made during the [[../Inspection|
paul@862 13
inspection process]] and attempts to form deductions about the behaviour of
paul@862 14
the program primarily in terms of the nature of the attribute '''accesses''',
paul@862 15
with their corresponding '''accessors''', featuring in the program. Where
paul@862 16
attributes are used in conjunction with names, accessors are name versions;
paul@862 17
where attributes are used in conjunction with other expressions, accessors are
paul@862 18
'''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@862 26
'''Indexes''' || '''From''' || '''To''' || '''Purpose'''
paul@862 27
==
paul@862 28
`access_index`
paul@862 29
|| access operation
paul@862 30
|| accessor (name version)
paul@862 31
|| defining types at access locations
paul@810 32
==
paul@862 33
`access_index_rev`
paul@862 34
|| accessor (name version)
paul@862 35
|| access operations
paul@862 36
|| determining whether names are used for accesses; establishing alias
paul@862 37
.. information
paul@810 38
==
paul@862 39
`location_index`
paul@862 40
|| accessor (name version)
paul@862 41
|| attribute usage patterns
paul@862 42
|| deducing types for names
paul@810 43
==
paul@810 44
`attr_class_types`<<BR>>`attr_instance_types`<<BR>>`attr_module_types`
paul@862 45
|| attribute name and assignment state
paul@862 46
|| class, instance, module types
paul@862 47
|| determining types supporting name accesses and assignments
paul@810 48
==
paul@810 49
`assigned_attrs`
paul@862 50
|| attribute usage pattern
paul@862 51
|| attribute assignment locations
paul@862 52
|| determining possibly mutated attributes on types
paul@862 53
==
paul@862 54
`alias_index`
paul@862 55
|| alias (name version)
paul@862 56
|| accesses
paul@862 57
|| determining the identities of aliases (name versions) from initialising
paul@862 58
.. name or attribute accesses
paul@862 59
==
paul@862 60
`alias_index_rev`
paul@862 61
|| access
paul@862 62
|| aliases (name versions)
paul@862 63
|| propagating updated information from accesses to aliases
paul@862 64
}}}
paul@862 65
paul@862 66
Various collections are also maintained:
paul@862 67
paul@862 68
{{{#!table
paul@862 69
'''Collections''' || '''Details''' || '''Purpose'''
paul@810 70
==
paul@810 71
`reference_assignments`
paul@862 72
|| accesses involving assignments
paul@862 73
|| constraining accessor types; adjusting access plans
paul@810 74
==
paul@810 75
`reference_invocations`
paul@862 76
|| accesses involving invocations
paul@862 77
|| converting access types to instantiation or invocation results
paul@810 78
}}}
paul@810 79
paul@861 80
The objective of deduction is to combine these indexes to establish new
paul@861 81
relationships between the different participants of these basic index
paul@861 82
relationships.
paul@810 83
paul@810 84
=== Building Indexes ===
paul@810 85
paul@810 86
The building of indexes from inspection data is approximately as follows:
paul@810 87
paul@810 88
{{{#!graphviz
paul@810 89
//format=svg
paul@810 90
//transform=notugly
paul@810 91
digraph indexes {
paul@810 92
  node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Indexes"];
paul@810 93
  edge [tooltip="Indexes"];
paul@810 94
  rankdir=LR;
paul@810 95
paul@810 96
  all_attr_accesses [label="all_attr_accesses\n(anonymous accesses)"];
paul@810 97
  attr_usage [label="attr_usage\n(attribute usage)"];
paul@810 98
  location_index [label="location_index\n(usage by accessor)"];
paul@810 99
paul@810 100
  all_attrs [label="all_class_attrs | all_instance_attrs | all_module attrs | (all attributes)",shape=record];
paul@810 101
  attr_types [label="attr_class_types | attr_instance_types | attr_module_types | (types by attribute name)",shape=record];
paul@810 102
paul@810 103
  attr_accessors [label="attr_accessors\n(accessors by access)"];
paul@810 104
  access_index [label="access_index\n(accessor locations by access location)"];
paul@810 105
paul@810 106
  all_attr_access_modifiers [label="all_attr_access_modifiers\n(operations/modifiers by access)"];
paul@810 107
  reference_assignments [label="reference_assignments\n(assignment accesses)"];
paul@810 108
  reference_invocations [label="reference_invocations\n(invocation accesses)"];
paul@810 109
  assigned_attrs [label="assigned_attrs\n(assignment accesses by access)"];
paul@810 110
paul@810 111
  all_aliased_names [label="all_aliased_names\n(accesses by alias)"];
paul@810 112
  alias_index [label="alias_index\n(access locations by accessor/alias location)"];
paul@810 113
paul@810 114
  init_usage_index [label="init_usage_index",shape=ellipse];
paul@810 115
  init_attr_type_indexes [label="init_attr_type_indexes",shape=ellipse];
paul@810 116
  init_accessors [label="init_accessors",shape=ellipse];
paul@810 117
  init_accesses [label="init_accesses",shape=ellipse];
paul@810 118
  init_aliases [label="init_aliases",shape=ellipse];
paul@810 119
paul@810 120
  all_attr_accesses -> init_usage_index;
paul@810 121
  attr_usage -> init_usage_index;
paul@810 122
  init_usage_index -> location_index;
paul@810 123
paul@810 124
  all_attrs -> init_attr_type_indexes -> attr_types;
paul@810 125
paul@810 126
  attr_accessors -> init_accessors -> access_index;
paul@810 127
paul@810 128
  all_attr_access_modifiers -> init_accesses;
paul@810 129
  init_accesses -> reference_assignments;
paul@810 130
  init_accesses -> reference_invocations;
paul@810 131
  init_accesses -> assigned_attrs;
paul@810 132
paul@810 133
  all_aliased_names -> init_aliases -> alias_index;
paul@810 134
}
paul@810 135
}}}
paul@810 136
paul@810 137
=== Deriving Types from Indexes and Accesses ===
paul@810 138
paul@810 139
The indexes are employed in deduction approximately as follows:
paul@810 140
paul@810 141
{{{#!graphviz
paul@810 142
//format=svg
paul@810 143
//transform=notugly
paul@810 144
digraph deduction {
paul@810 145
  node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Deduction"];
paul@810 146
  edge [tooltip="Deduction"];
paul@810 147
  rankdir=LR;
paul@810 148
paul@810 149
  all_attr_accesses [label="all_attr_accesses\n(anonymous accesses)"];
paul@810 150
  location_index [label="location_index\n(usage by accessor)"];
paul@810 151
paul@810 152
  attr_types [label="attr_class_types | attr_instance_types | attr_module_types | (types by attribute name)",shape=record];
paul@810 153
paul@810 154
  all_initialised_names [label="all_initialised_names\n(types by accessor)"];
paul@810 155
paul@810 156
  access_index [label="access_index\n(accessor locations by access location)"];
paul@810 157
paul@810 158
  alias_index [label="alias_index\n(access locations by accessor/alias location)"];
paul@810 159
paul@810 160
  record_types_for_usage [label="record_types_for_usage",shape=ellipse];
paul@810 161
  record_types_for_attribute [label="record_types_for_attribute",shape=ellipse];
paul@810 162
paul@810 163
  accessor_types [label="accessor_class_types | accessor_instance_types | accessor_module_types | (types by accessor)",shape=record];
paul@810 164
  provider_types [label="provider_class_types | provider_instance_types | provider_module_types | (provider types by accessor)",shape=record];
paul@810 165
paul@810 166
  location_index -> record_types_for_usage;
paul@810 167
  attr_types -> record_types_for_usage;
paul@810 168
  all_initialised_names -> record_types_for_usage;
paul@810 169
  access_index -> record_types_for_usage;
paul@810 170
  alias_index -> record_types_for_usage; 
paul@810 171
paul@810 172
  record_types_for_usage -> provider_types;
paul@810 173
  record_types_for_usage -> accessor_types;
paul@810 174
paul@810 175
  attr_types -> record_types_for_attribute;
paul@810 176
  all_attr_accesses -> record_types_for_attribute;
paul@810 177
paul@810 178
  record_types_for_attribute -> provider_types;
paul@810 179
  record_types_for_attribute -> accessor_types;
paul@810 180
}
paul@810 181
}}}
paul@810 182
paul@810 183
=== Converting Usage to Types ===
paul@810 184
paul@861 185
A particularly important operation in the deduction process is that of
paul@861 186
converting attribute usage information to a set of types supporting such
paul@861 187
usage. Taking the mapping of attribute names to types, each attribute name
paul@861 188
provided by a usage observation can be applied, progressively narrowing the
paul@861 189
set of types available to support the complete attribute usage collection.
paul@810 190
paul@810 191
{{{#!graphviz
paul@810 192
//format=svg
paul@810 193
//transform=notugly
paul@810 194
digraph usage_to_types {
paul@810 195
  node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Usage to types"];
paul@810 196
  edge [tooltip="Usage to types"];
paul@810 197
  rankdir=LR;
paul@810 198
paul@810 199
  usage [label="(a, b, c)",style=filled,fillcolor=darkorange];
paul@810 200
paul@810 201
  subgraph {
paul@810 202
    rank=same;
paul@810 203
    attr_a [label="attribute a",style=filled,fillcolor=gold];
paul@810 204
    attr_b [label="attribute b",style=filled,fillcolor=gold];
paul@810 205
    attr_c [label="attribute c",style=filled,fillcolor=gold];
paul@810 206
  }
paul@810 207
paul@810 208
  index [label="types by attribute name",shape=ellipse];
paul@810 209
paul@810 210
  subgraph {
paul@810 211
    rank=same;
paul@810 212
    type_P [label="type P"];
paul@810 213
    type_Q [label="type Q",style=filled,fillcolor=gold];
paul@810 214
    type_R [label="type R"];
paul@810 215
    type_S [label="type S"];
paul@810 216
  }
paul@810 217
paul@810 218
  deduction [label="(a, b, c) needs type Q",style=filled,fillcolor=darkorange];
paul@810 219
paul@810 220
  usage -> attr_a;
paul@810 221
  usage -> attr_b;
paul@810 222
  usage -> attr_c;
paul@810 223
paul@810 224
  attr_a -> attr_b -> attr_c [style=dashed,dir=none];
paul@810 225
  attr_a -> index -> type_P [style=dashed,dir=none];
paul@810 226
  type_P -> type_Q -> type_R -> type_S [style=dashed,dir=none];
paul@810 227
paul@810 228
  attr_a -> type_P;
paul@810 229
  attr_a -> type_Q;
paul@810 230
  attr_b -> type_Q;
paul@810 231
  attr_b -> type_R;
paul@810 232
  attr_c -> type_Q;
paul@810 233
  attr_c -> type_S;
paul@810 234
paul@810 235
  type_Q -> deduction;
paul@810 236
}
paul@810 237
}}}
paul@810 238
paul@861 239
The types supporting attribute usage are the attribute '''providers'''. Where
paul@861 240
providers are classes, the affected accessors in the program may also be
paul@861 241
instances, since instances also support access to attributes of the
paul@861 242
instantiated class (and its ancestors).
paul@810 243
paul@861 244
Indexes mapping attributes to types must combine consideration of class and
paul@861 245
instance attributes in order to correctly identify instance providers.
paul@861 246
Consider the following example:
paul@810 247
paul@810 248
{{{#!graphviz
paul@810 249
//format=svg
paul@810 250
//transform=notugly
paul@810 251
digraph instance_providers {
paul@810 252
  node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Instance providers"];
paul@810 253
  edge [tooltip="Instance providers"];
paul@810 254
  rankdir=LR;
paul@810 255
paul@810 256
  usage [label="(a, b, c)",style=filled,fillcolor=darkorange];
paul@810 257
paul@810 258
  subgraph {
paul@810 259
    rank=same;
paul@810 260
    combined [label="combined attributes",shape=ellipse];
paul@810 261
    attr_a [label="attribute a",style=filled,fillcolor=gold];
paul@810 262
    attr_c [label="attribute c",style=filled,fillcolor=gold];
paul@810 263
    attr_b [label="attribute b",style=filled,fillcolor=gold];
paul@810 264
  }
paul@810 265
paul@810 266
  subgraph {
paul@810 267
    rank=same;
paul@810 268
    class_C [label="class C"];
paul@810 269
    attr_Ca [label="attribute C.a",style=filled,fillcolor=gold];
paul@810 270
    attr_Cc [label="attribute C.c",style=filled,fillcolor=gold];
paul@810 271
    instance_C [label="instance of C"];
paul@810 272
    attr_Ib [label="attribute (C).b",style=filled,fillcolor=gold];
paul@810 273
  }
paul@810 274
paul@810 275
  type_C [label="type C",style=filled,fillcolor=darkorange];
paul@810 276
paul@810 277
  combined -> attr_a -> attr_c -> attr_b [style=dashed,dir=none];
paul@810 278
  class_C -> attr_Ca -> attr_Cc [style=dashed,dir=none];
paul@810 279
  instance_C -> attr_Ib [style=dashed,dir=none];
paul@810 280
paul@810 281
  usage -> attr_a -> attr_Ca;
paul@810 282
  usage -> attr_b -> attr_Ib;
paul@810 283
  usage -> attr_c -> attr_Cc;
paul@810 284
paul@810 285
  attr_Ca -> type_C;
paul@810 286
  attr_Cc -> type_C;
paul@810 287
  attr_Ib -> type_C;
paul@810 288
}
paul@810 289
}}}
paul@810 290
paul@861 291
To recognise support by instance accessors for the usage pattern concerned,
paul@861 292
attribute details must be obtained from classes as well as instances. Note
paul@861 293
that the identified type cannot support such usage purely by providing class
paul@861 294
or instance attributes alone.
paul@810 295
paul@810 296
=== Attribute Assignments ===
paul@810 297
paul@861 298
Since attribute access operations may occur as part of assignments, the nature
paul@861 299
of accesses is recorded during inspection. Combining the indexed information
paul@861 300
for assignment accesses allows the deducer to determine the most pessimistic
paul@861 301
effects on the program structure of such assignments.
paul@810 302
paul@861 303
Taking each attribute usage set employed by accessors involved in assignments,
paul@861 304
the types are deduced for such accessors, and each individual attribute known
paul@861 305
to be used in such assignments is then applied to the deduced types,
paul@861 306
'''mutating''' them in such a way that deductions may no longer assume a fixed
paul@861 307
identity for such attributes when obtained from these types.
paul@810 308
paul@810 309
{{{#!graphviz
paul@810 310
//format=svg
paul@810 311
//transform=notugly
paul@810 312
digraph assignments {
paul@810 313
  node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Attribute assignments"];
paul@810 314
  edge [tooltip="Attribute assignments"];
paul@810 315
  rankdir=LR;
paul@810 316
paul@810 317
  subgraph {
paul@810 318
    rank=same;
paul@810 319
    usage [label="(a, b, c)",style=filled,fillcolor=darkorange];
paul@810 320
    assigned [label="b is assigned",style=filled,fillcolor=darkorange];
paul@810 321
  }
paul@810 322
paul@810 323
  deduction [label="(a, b, c) needs type Q",style=filled,fillcolor=gold];
paul@810 324
paul@810 325
  subgraph {
paul@810 326
    rank=same;
paul@810 327
    type_Q [label="type Q",style=filled,fillcolor=gold];
paul@810 328
    attr_Qa [label="attribute Q.a"];
paul@810 329
    attr_Qb [label="attribute Q.b\n(mutated)",style=filled,fillcolor=darkorange];
paul@810 330
    attr_Qc [label="attribute Q.c"];
paul@810 331
  }
paul@810 332
paul@810 333
  type_Q -> attr_Qa -> attr_Qb -> attr_Qc [style=dashed,dir=none];
paul@810 334
  usage -> deduction -> type_Q;
paul@810 335
  assigned -> attr_Qb;
paul@810 336
}
paul@810 337
}}}
paul@810 338
paul@810 339
=== Refining Type Deductions ===
paul@810 340
paul@810 341
In the context of a specific access, the types may be resolved further:
paul@810 342
paul@861 343
 * Any name whose initialisation could be determined during inspection can be
paul@861 344
   associated with its initialised type
paul@862 345
paul@861 346
 * Any name referring to a constant object can be associated with the type of
paul@861 347
   that object
paul@862 348
paul@861 349
 * Usage of `self` in methods can result in only compatible class and instance
paul@861 350
   types being retained from the types obtained from usage deductions
paul@810 351
paul@810 352
=== Reference Identification ===
paul@810 353
paul@861 354
The basic information about every accessor and accessed attribute in a program
paul@861 355
can now be combined to produce specific '''references''' to identities
paul@861 356
consistent with the inspection observations. Several different kinds of
paul@861 357
accessors and access situations exist:
paul@810 358
paul@810 359
 * Name-based accesses involving attribute usage
paul@862 360
paul@810 361
 * Aliases to names, possibly accompanied by accesses
paul@862 362
paul@810 363
 * Anonymous accesses involving individual attributes
paul@862 364
paul@810 365
 * Constant or previously-identified names, possibly accompanied by accesses
paul@810 366
paul@810 367
=== Aliases ===
paul@810 368
paul@861 369
Names initialised using other names or attribute accesses, or using the
paul@861 370
invocation of either of these things, are known as '''aliases'''. Information
paul@861 371
about aliases originates during inspection when such names are initialised
paul@861 372
with expression results within the program. During the resolution activity
paul@861 373
finalising the inspected details, this initialisation information is used to
paul@861 374
define relationships between aliases and other names and accesses.
paul@810 375
paul@861 376
During deduction, attribute accesses are investigated and type information
paul@861 377
computed for both attribute accesses and accessors. The relationships defined
paul@861 378
between accesses and aliases can then be employed to propagate such deduced
paul@861 379
information to the aliases and to define appropriate type characteristics for
paul@861 380
them.
paul@810 381
paul@861 382
Where aliases are used as the basis of attribute accesses, this propagation
paul@861 383
refines the previously deduced information about the aliases and may also
paul@861 384
refine the details of the accesses with which the alias is involved.
paul@810 385
paul@810 386
=== Invocation Target Suitability ===
paul@810 387
paul@861 388
Having identified accessed attributes, invocation information can be applied
paul@861 389
in cases where such attributes immediately participate in an invocation,
paul@861 390
comparing the specified argument details against the parameter details defined
paul@861 391
for the identified attribute, which must be a callable object for this
paul@861 392
technique to work. Where arguments do not appear to be suitable - either the
paul@861 393
number of arguments is incorrect or any keyword argument refer to non-existent
paul@861 394
parameters - the attribute providing the parameter details can be considered
paul@861 395
unsuitable for the access.
paul@810 396
paul@810 397
=== Classifying Accessors ===
paul@810 398
paul@861 399
Each accessor, being a particular version of a name, will have type
paul@861 400
information associated with it as a consequence of the deduction process. Such
paul@861 401
information takes the following forms:
paul@810 402
paul@861 403
 * Provider types, indicating which types may provide the attributes used by
paul@861 404
   the accessor
paul@862 405
paul@810 406
 * Accessor types, indicating which types will actually appear as the accessor
paul@810 407
paul@862 408
This information can be processed in a number of ways to produce the
paul@862 409
following:
paul@810 410
paul@861 411
 * All types (from all kinds of type) of providers able to provide attributes
paul@861 412
   via the accessor
paul@862 413
paul@861 414
 * All types (from all kinds of type) of accessors compatible with the
paul@861 415
   accessor
paul@862 416
paul@810 417
 * The most general types of accessors compatible with the accessor
paul@810 418
paul@861 419
Where many types may be associated with an accessor, identifying the most
paul@861 420
general types involves eliminating those which are derived from others. Given
paul@861 421
that descendant types may not remove support for attributes provided by their
paul@861 422
ancestors, then where an ancestor type has been identified as a possible
paul@861 423
accessor, it should follow that all of its descendants may also have been
paul@861 424
identified as possible accessors. Since these descendants should be
paul@861 425
compatible, identifying them individually is unnecessary: merely specifying
paul@861 426
that the common ancestor or ''any'' descendant could provide an accessor is
paul@861 427
sufficient.
paul@810 428
paul@810 429
==== Defining Guards ====
paul@810 430
paul@861 431
A '''guard''' is a constraint supported by a run-time test indicating the
paul@861 432
compliance of an accessor with a particular type. Thus, where a single
paul@861 433
accessor type has been identified, a guard may be established for an accessor
paul@861 434
that tests the type of the accessor against a specific type. Where a single
paul@861 435
''general'' accessor type is identified, a guard is established that tests the
paul@861 436
accessor against a "common" type: that is, an ancestor type with which other
paul@861 437
descendant types may comply.
paul@810 438
paul@810 439
=== Classifying Accesses ===
paul@810 440
paul@861 441
At the point of classifying accesses, information is available about the
paul@861 442
following:
paul@810 443
paul@810 444
 * The accessors potentially involved in each access
paul@862 445
paul@861 446
 * The types of accessors and the types providing attributes via those
paul@861 447
   accessors
paul@862 448
paul@810 449
 * Any guards applying to the accessors
paul@862 450
paul@861 451
 * Whether an access is constrained by certain program characteristics and is
paul@861 452
   thus guaranteed to be as deduced
paul@862 453
paul@810 454
 * The possible attributes referenced by the access
paul@810 455
paul@861 456
This information can be processed in a number of ways to produce the
paul@861 457
following:
paul@810 458
paul@810 459
 * The types of accessors, both general and specific, applying to each access
paul@862 460
paul@861 461
 * The attributes that can be provided by each access, consolidating existing
paul@861 462
   referenced attribute details
paul@862 463
paul@810 464
 * The general types providing the attributes
paul@810 465
paul@861 466
Since more than one accessor may be involved, information from all accessors
paul@861 467
must be combined to determine whether guard information still applies to the
paul@861 468
access, or whether it is possible for an accessor to be used that has an
paul@861 469
uncertain type at run-time.
paul@810 470
paul@810 471
==== Defining Tests ====
paul@810 472
paul@861 473
A '''test''' at the access level is a necessary check performed on an accessor
paul@861 474
before an access to determine whether it belongs to a certain type or group of
paul@861 475
types.
paul@810 476
paul@861 477
Where guards applying to accessors apply by extension to an access, it may not
paul@861 478
be enough to assume that the the attributes exposed by the accessor are the
paul@861 479
same as those considered acceptable through deduction. Therefore, attributes
paul@861 480
are obtained for the access using the applicable guard types as accessors. If
paul@861 481
this set of attributes does not include potentially accessible attributes
paul@861 482
(perhaps because the guard types are broadly defined and do not support all
paul@861 483
attribute usage), a test must be generated.
paul@810 484
paul@861 485
Where a single attribute provider can be identified, a test for a specific
paul@861 486
type is generated. Where a single general type can be identified as a
paul@861 487
provider, a test against a "common" type is generated. Tests involving the
paul@861 488
built-in `object` are not generated since it is the root of all classes and
paul@861 489
such tests would merely identify an accessor as a class. In all cases where a
paul@861 490
single, specific type cannot be tested for, the general attribute validation
paul@861 491
mechanism must be used instead.
paul@810 492
paul@810 493
== Preparing Access Descriptions ==
paul@810 494
paul@861 495
The accumulated deduced knowledge is directed towards producing access
paul@861 496
descriptions or plans which characterise each access in terms of the
paul@861 497
following:
paul@810 498
paul@861 499
 * The initial accessor, being the starting object for attribute accesses,
paul@861 500
   unless a static accessor has been identified
paul@810 501
 * Details of any test required on the initial accessor
paul@810 502
 * Details of any type employed by the test
paul@810 503
 * Any identified static accessor (to be used as the initial accessor)
paul@862 504
 * Attributes needing to be traversed from the accessor that yield
paul@862 505
   unambiguous objects
paul@810 506
 * Access modes for each of the unambiguously-traversed attributes
paul@861 507
 * Remaining attributes needing to be tested and traversed (after having
paul@861 508
   traversed the above attributes)
paul@810 509
 * Details of the context
paul@810 510
 * Any test to apply to the context (to ensure its validity)
paul@810 511
 * The method of obtaining the first attribute
paul@810 512
 * The method of obtaining the final attribute
paul@810 513
 * Any identified static final attribute
paul@810 514
 * The kinds of objects providing the final attribute
paul@810 515
paul@810 516
=== Characterising the Accessor ===
paul@810 517
paul@861 518
For a given access location, the referenced attribute details established
paul@861 519
during deduction are used to determine...
paul@810 520
paul@861 521
 * Whether the initial accessor is static, originating from a constant access
paul@861 522
   or involving an identifiable static object
paul@862 523
paul@810 524
 * Whether the initial accessor is dynamic but has a known, deduced identity
paul@810 525
paul@861 526
Some useful information about the accessor and about the actual provider of
paul@861 527
the first accessed attribute can be defined:
paul@810 528
paul@810 529
|| || '''Class''' || '''Instance''' || '''Module''' ||
paul@810 530
|| '''Accessor''' || Class accessor || Instance accessor || Module accessor ||
paul@810 531
|| '''Provider''' || Class provider || Instance provider || ||
paul@810 532
paul@861 533
Depending on which of these criteria are satisfied, some properties of the
paul@861 534
access operation can be established:
paul@810 535
paul@861 536
 * Object-relative accesses occur with class accessors or module accessors or
paul@861 537
   when attributes are provided by instances
paul@862 538
paul@861 539
 * Class-relative accesses occur with instance accessors when attributes are
paul@861 540
   provided by classes
paul@810 541
paul@861 542
Object-relative accesses merely involve obtaining attributes directly from
paul@861 543
accessors. Class-relative accesses involve obtaining the class of each
paul@861 544
accessor and then obtaining an attribute from that class.
paul@810 545
paul@810 546
=== Defining the First Access Method ===
paul@810 547
paul@861 548
For dynamic or unidentified accessors, the above access properties define the
paul@861 549
access method on the first attribute in the chain of attributes provided.
paul@861 550
However, any redefinition of the accessor to a static accessor may influence
paul@861 551
the first method. For static accessors, the first method is always
paul@861 552
object-relative since classes and modules do not offer transparent mechanisms
paul@861 553
to expose the attributes on their own classes.
paul@810 554
paul@861 555
Static and identified, dynamic accessors should already be known to support
paul@861 556
the specified attributes. Other accessors require an access method to be used
paul@861 557
that also checks whether the accessor supports a given attribute.
paul@810 558
paul@810 559
=== Redefining the Accessor ===
paul@810 560
paul@861 561
With knowledge about the initial accessor, the attributes involved in the
paul@861 562
access operation are then considered in the context of the accessor. For each
paul@861 563
attribute name in the chain described for an access, an attempt is made to
paul@861 564
obtain the details of the attribute of the given name from the accessor,
paul@861 565
determining whether these details can be used as an accessor to obtain
paul@861 566
subsequent attribute details.
paul@810 567
paul@861 568
Where more than one attribute identity is obtained, traversal is terminated:
paul@861 569
all remaining attributes must be traversed at run-time. If an attribute
paul@861 570
identified during traversal is static, the first access method changes
paul@861 571
accordingly.
paul@810 572
paul@810 573
=== Defining the Final Access Method ===
paul@810 574
paul@861 575
An access can also involve an assignment to the accessed attribute or the
paul@861 576
invocation of the accessed attribute. Such operations change the nature of the
paul@861 577
access method used on the final attribute in a chain of attribute names.
paul@810 578
paul@810 579
=== Identifying Context Information ===
paul@810 580
paul@862 581
Final attribute accesses involving callables need to incorporate context
paul@862 582
information that can subsequently be used to invoke those callables. Where the
paul@862 583
nature of an accessed attribute is not known, a simplistic attempt can be made
paul@862 584
to look up all attributes stored using the attribute name in the program.
paul@862 585
Otherwise, with knowledge of the attribute, its details can be inspected to
paul@862 586
determine if context information plays a role in the access.
paul@862 587
paul@862 588
==== Context Testing ====
paul@810 589
paul@810 590
Of particular interest are the following situations:
paul@810 591
paul@861 592
 * Where class attributes are being accessed via instances, whether the
paul@862 593
   attributes are all methods that are bound to the instances
paul@862 594
paul@862 595
 * Where class attributes ''may'' be accessed via instances, whether any
paul@862 596
   attributes ''could be'' methods
paul@810 597
paul@861 598
Such considerations dictate whether the context information originates from
paul@861 599
the attribute or from the accessor and whether any run-time test is required
paul@862 600
to determine this. Thus, for attributes in general:
paul@862 601
paul@862 602
{{{#!table
paul@862 603
'''Accessor''' || '''Provider''' || '''Attributes'''
paul@862 604
|| '''Effect on Context''' || '''Remark'''
paul@862 605
==
paul@862 606
Always instances || Always classes || Always methods
paul@862 607
|| Replacement
paul@862 608
|| Permit method calling using the instance as context
paul@862 609
==
paul@862 610
Always instances || Always classes || Sometimes methods
paul@862 611
|| Test at run-time
paul@862 612
|| Preserve original context for non-methods
paul@862 613
==
paul@862 614
Sometimes instances || Sometimes classes || Sometimes methods
paul@862 615
|| Test at run-time
paul@862 616
|| Preserve original context for non-methods, non-instance accessors
paul@862 617
}}}
paul@862 618
paul@862 619
In all other situations, the available context is ignored, with the attribute
paul@862 620
itself providing any stored context information.
paul@862 621
paul@862 622
==== Context Identity ====
paul@862 623
paul@862 624
Where the context is ignored, no effort will be made to obtain or retain it in
paul@862 625
the program for the access operation: it will be unset. Otherwise, the context
paul@862 626
will be defined as one of the following:
paul@862 627
paul@862 628
 * The "base" or static accessor where this is also the accessor for the final
paul@862 629
   access
paul@862 630
paul@862 631
 * The original (or initial) accessor where this is also the accessor for the
paul@862 632
   final access
paul@862 633
paul@862 634
 * The final accessor, having been identified through attribute traversal
paul@862 635
paul@862 636
Note that non-static accessors may be computed dynamically and thus need to be
paul@862 637
stored temporarily for subsequent use. 
paul@810 638
paul@810 639
== Preparing Instruction Plans ==
paul@810 640
paul@861 641
Instruction plans are sequences of program operations, encoded in a
paul@861 642
higher-level form than actual program instructions, that describe the steps
paul@861 643
needed to access attributes. Such sequences are produced from the details
paul@861 644
provided by individual access plans.
paul@810 645
paul@810 646
=== Original Accessor ===
paul@810 647
paul@861 648
The expression providing the object from which the first attribute is obtained
paul@861 649
(or the only attribute if only one is specified) is known as the original
paul@861 650
accessor. Where this accessor can be identified, the expression describing it
paul@861 651
in the program can potentially be replaced with a static reference, and
paul@861 652
subsequent mentions of the accessor can potentially be replaced with such
paul@861 653
references or names used as expressions.
paul@810 654
paul@862 655
{{{#!table
paul@862 656
'''Access Plan Information''' || '''Original Accessor'''
paul@862 657
==
paul@862 658
Static accessor identified
paul@862 659
|| Identified accessor
paul@862 660
==
paul@862 661
Named accessor access, not invocation
paul@862 662
|| Indicated name
paul@862 663
==
paul@862 664
Named accessor invocation, accessor known to provide the attribute
paul@862 665
|| Indicated name
paul@862 666
==
paul@862 667
Named accessor invocation, accessor not known to provide the attribute
paul@862 668
|| Accessor expression
paul@862 669
==
paul@862 670
Other accessors
paul@862 671
|| Accessor expression
paul@862 672
}}}
paul@810 673
paul@861 674
By using names or static references, the need to store the result of
paul@861 675
evaluating an accessor expression is eliminated because such labels can be
paul@861 676
inserted in the instruction sequence as required.
paul@810 677
paul@810 678
=== First Access Operation ===
paul@810 679
paul@861 680
Although it may be possible to convert accesses into single instructions that
paul@861 681
obtain attributes directly, many accesses will involve access operations that
paul@861 682
must consult an accessor object and obtain an attribute from that object, at
paul@861 683
least for the first attribute in a chain of attributes. This occurs when the
paul@861 684
access plan indicates the following situations:
paul@810 685
paul@861 686
 * Final method is an access (meaning that an attribute cannot be directly
paul@861 687
   obtained)
paul@862 688
paul@861 689
 * Final method is an assignment (requiring the object whose attribute will be
paul@861 690
   updated)
paul@862 691
paul@810 692
 * Attributes (identified or otherwise) need traversing
paul@810 693
paul@810 694
=== Accessor Nature ===
paul@810 695
paul@861 696
Attribute assignments involve a single '''target accessor''' and potentially
paul@861 697
many other accessors, depending on how many distinct expressions are evaluated
paul@861 698
to yield the value to be set in the assignment. Such a target accessor will
paul@861 699
usually be derived from the evaluation of an expression, and in some cases the
paul@861 700
expression will be the result of an opaque operation such as the invocation of
paul@861 701
a function. In such cases, the target accessor is stored in a temporary
paul@861 702
variable for subsequent use in access operations.
paul@810 703
paul@810 704
=== Context ===
paul@810 705
paul@810 706
=== Access Tests ===
paul@810 707
paul@810 708
=== Traversing Identified Attributes ===
paul@810 709
paul@810 710
=== Traversing Unidentified Attributes ===
paul@810 711
paul@810 712
=== Final Access Operation ===
paul@810 713
paul@810 714
=== Context Testing ===
paul@810 715
paul@862 716
=== Instruction Details ===
paul@862 717
paul@862 718
The emitted instructions are as follows.
paul@862 719
paul@862 720
==== Direct Load ====
paul@862 721
paul@862 722
These instructions employ the attribute position for the supplied attribute
paul@862 723
name.
paul@862 724
paul@862 725
{{{#!table
paul@862 726
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 727
==
paul@862 728
`__load_via_class` || object, attribute name
paul@862 729
|| Obtain class from object; load attribute from class at position
paul@862 730
==
paul@862 731
`__load_via_object` || object, attribute name
paul@862 732
|| Load attribute from object at position
paul@862 733
==
paul@862 734
`__get_class_and_load` || object, attribute name
paul@862 735
|| Obtain class from object if instance; load attribute from result at
paul@862 736
.. position
paul@862 737
}}}
paul@862 738
paul@862 739
==== Direct Store ====
paul@862 740
paul@862 741
These instructions employ the attribute position for the supplied attribute
paul@862 742
name, storing an attribute value.
paul@862 743
paul@862 744
{{{#!table
paul@862 745
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 746
==
paul@862 747
`__store_via_class` || object, attribute name, value
paul@862 748
|| Obtain class from object; store attribute in class at position
paul@862 749
==
paul@862 750
`__store_via_object` || object, attribute name, value
paul@862 751
|| Store attribute in object at position
paul@862 752
}}}
paul@862 753
paul@862 754
==== Checked Load ====
paul@862 755
paul@862 756
These instructions employ the attribute position and code for the supplied
paul@862 757
attribute name.
paul@862 758
paul@862 759
{{{#!table
paul@862 760
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 761
==
paul@862 762
`__check_and_load_via_class` || object, attribute name
paul@862 763
|| Obtain class from object; test for attribute and load or raise type error
paul@862 764
==
paul@862 765
`__check_and_load_via_object` || object, attribute name
paul@862 766
|| Test for attribute and load or raise type error
paul@862 767
==
paul@862 768
`__check_and_load_via_any` || object, attribute name
paul@862 769
|| Test for attribute and load or obtain class; test for attribute and load or
paul@862 770
.. raise type error
paul@862 771
}}}
paul@862 772
paul@862 773
==== Checked Store ====
paul@862 774
paul@862 775
These instructions employ the attribute position and code for the supplied
paul@862 776
attribute name, storing an attribute value.
paul@862 777
paul@862 778
{{{#!table
paul@862 779
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 780
==
paul@862 781
`__check_and_store_via_class` || object, attribute name, value
paul@862 782
|| Raise type error
paul@862 783
==
paul@862 784
`__check_and_store_via_object` || object, attribute name, value
paul@862 785
|| Test for attribute and store value or raise type error
paul@862 786
==
paul@862 787
`__check_and_store_via_any` || object, attribute name, value
paul@862 788
|| Test for attribute and store value or raise type error
paul@862 789
}}}
paul@862 790
paul@862 791
==== Testing ====
paul@862 792
paul@862 793
These instructions employ the special attribute position and code for the
paul@862 794
supplied type name.
paul@862 795
paul@862 796
{{{#!table
paul@862 797
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 798
==
paul@862 799
`__test_common_instance` || object, type
paul@862 800
|| Obtain class from object; test conformance to type
paul@862 801
==
paul@862 802
`__test_common_object` || object, type
paul@862 803
|| Test conformance to type or obtain class from object and test conformance
paul@862 804
.. to type
paul@862 805
==
paul@862 806
`__test_common_type` || object, type
paul@862 807
|| Test conformance to type
paul@862 808
==
paul@862 809
`__test_specific_instance` || object, type
paul@862 810
|| Obtain class from object; test equivalence to type
paul@862 811
==
paul@862 812
`__test_specific_object` || object, type
paul@862 813
|| Test equivalence to type or obtain class from object and test equivalence
paul@862 814
.. to type
paul@862 815
==
paul@862 816
`__test_specific_type` || object, type
paul@862 817
|| Test equivalence to type
paul@862 818
}}}
paul@862 819
paul@862 820
==== Static Load ====
paul@862 821
paul@862 822
These instructions obtain references to static objects, in some cases
paul@862 823
employing a supplied context.
paul@862 824
paul@862 825
{{{#!table
paul@862 826
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 827
==
paul@862 828
`__load_static_ignore` || object
paul@862 829
|| Load attribute populated with object, leaving the context unset
paul@862 830
==
paul@862 831
`__load_static_replace` || context, object
paul@862 832
|| Load attribute populated with the context and object
paul@862 833
==
paul@862 834
`__load_static_test` || context, object
paul@862 835
|| Load attribute populated with object; test context compatibility and set
paul@862 836
.. the context
paul@862 837
}}}
paul@862 838
paul@862 839
==== Temporary Access ====
paul@862 840
paul@862 841
These instructions access temporary values retained to perform the attribute
paul@862 842
access. The temporary storage index is generated during program translation.
paul@862 843
paul@862 844
{{{#!table
paul@862 845
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 846
==
paul@862 847
`__get_context` || (temporary)
paul@862 848
|| Load the context stored in the temporary storage
paul@862 849
==
paul@862 850
`__set_accessor` || accessor
paul@862 851
|| Store the accessor temporarily
paul@862 852
==
paul@862 853
`__set_context` || (temporary), context
paul@862 854
|| Store the context in the temporary storage
paul@862 855
==
paul@862 856
`__set_private_context` || context
paul@862 857
|| Store the context temporarily
paul@862 858
==
paul@862 859
`__set_target_accessor` || accessor
paul@862 860
|| Store the assignment accessor temporarily
paul@862 861
}}}
paul@862 862
paul@862 863
==== Context Test ====
paul@862 864
paul@862 865
These instructions perform tests on the available context object. The
paul@862 866
temporary storage index is generated during program translation.
paul@862 867
paul@862 868
{{{#!table
paul@862 869
'''Instruction''' || '''Arguments''' || '''Operations'''
paul@862 870
==
paul@862 871
`__test_context_revert` || (temporary), context, attribute
paul@862 872
|| Test compatibility of context; revert temporary to attribute context if
paul@862 873
.. incompatible
paul@862 874
==
paul@862 875
`__test_context_static` || (temporary), context, value
paul@862 876
|| Test compatibility of context; set temporary to specified context if
paul@862 877
.. compatible
paul@862 878
}}}
paul@862 879
paul@810 880
== Deduction Products ==
paul@810 881
paul@861 882
The deduction process should produce a complete catalogue of accessor and
paul@862 883
access references that may then be consulted by the [[../Translation|
paul@862 884
translation]] process needing to know the nature of any operation within the
paul@862 885
program. Central to the translation process's understanding of references is
paul@862 886
the '''attribute access plan''' for each reference which characterises each
paul@862 887
access and provides the basis for the formulation of the '''instruction
paul@862 888
plan''' used to replicate it in the final program.