Deducing Program Behaviour

With information from inspection available, the isolated observations about operations in a program may now be combined with knowledge about the program's structure to produce deductions about the nature of each operation.

  1. The Deduction Process
    1. Indexes
    2. Building Indexes
    3. Deriving Types from Indexes and Accesses
    4. Converting Usage to Types
    5. Attribute Assignments
    6. Refining Type Deductions
    7. Reference Identification
    8. Aliases
    9. Invocation Target Suitability
    10. Classifying Accessors
    11. Classifying Accesses
  2. Preparing Access Descriptions
    1. Characterising the Accessor
    2. Defining the First Access Method
    3. Redefining the Accessor
    4. Defining the Final Access Method
    5. Identifying Context Information
  3. Preparing Instruction Plans
    1. Original Accessor
    2. First Access Operation
    3. Accessor Nature
    4. Context
    5. Access Tests
    6. Traversing Identified Attributes
    7. Traversing Unidentified Attributes
    8. Final Access Operation
    9. Context Testing
    10. Instruction Details
  4. Deduction Products

The Deduction Process

The deduction process takes observations made during the inspection process and attempts to form deductions about the behaviour of the program primarily in terms of the nature of the attribute accesses, with their corresponding accessors, featuring in the program. Where attributes are used in conjunction with names, accessors are name versions; where attributes are used in conjunction with other expressions, accessors are anonymous.

Indexes

For efficiency, indexes are defined to establish relationships between the following things:

Indexes

From

To

Purpose

access_index

access operation

accessor (name version)

defining types at access locations

access_index_rev

accessor (name version)

access operations

determining whether names are used for accesses; establishing alias information

location_index

accessor (name version)

attribute usage patterns

deducing types for names

attr_class_types
attr_instance_types
attr_module_types

attribute name and assignment state

class, instance, module types

determining types supporting name accesses and assignments

assigned_attrs

attribute usage pattern

attribute assignment locations

determining possibly mutated attributes on types

alias_index

alias (name version)

accesses

determining the identities of aliases (name versions) from initialising name or attribute accesses

alias_index_rev

access

aliases (name versions)

propagating updated information from accesses to aliases

Various collections are also maintained:

Collections

Details

Purpose

reference_assignments

accesses involving assignments

constraining accessor types; adjusting access plans

reference_invocations

accesses involving invocations

converting access types to instantiation or invocation results

The objective of deduction is to combine these indexes to establish new relationships between the different participants of these basic index relationships.

Building Indexes

The building of indexes from inspection data is approximately as follows:

indexesall_attr_accesses(anonymous accesses)init_usage_indexattr_usage(attribute usage)location_index(usage by accessor)all_class_attrsall_instance_attrsall_module attrs(all attributes)init_attr_type_indexesattr_class_typesattr_instance_typesattr_module_types(types by attribute name)attr_accessors(accessors by access)init_accessorsaccess_index(accessor locations by access location)all_attr_access_modifiers(operations/modifiers by access)init_accessesreference_assignments(assignment accesses)reference_invocations(invocation accesses)assigned_attrs(assignment accesses by access)all_aliased_names(accesses by alias)init_aliasesalias_index(access locations by accessor/alias location)

Deriving Types from Indexes and Accesses

The indexes are employed in deduction approximately as follows:

deductionall_attr_accesses(anonymous accesses)record_types_for_attributelocation_index(usage by accessor)record_types_for_usageattr_class_typesattr_instance_typesattr_module_types(types by attribute name)all_initialised_names(types by accessor)access_index(accessor locations by access location)alias_index(access locations by accessor/alias location)accessor_class_typesaccessor_instance_typesaccessor_module_types(types by accessor)provider_class_typesprovider_instance_typesprovider_module_types(provider types by accessor)

Converting Usage to Types

A particularly important operation in the deduction process is that of converting attribute usage information to a set of types supporting such usage. Taking the mapping of attribute names to types, each attribute name provided by a usage observation can be applied, progressively narrowing the set of types available to support the complete attribute usage collection.

usage_to_types(a, b, c)attribute aattribute battribute ctypes by attribute nametype Ptype Qtype Rtype S(a, b, c) needs type Q

The types supporting attribute usage are the attribute providers. Where providers are classes, the affected accessors in the program may also be instances, since instances also support access to attributes of the instantiated class (and its ancestors).

Indexes mapping attributes to types must combine consideration of class and instance attributes in order to correctly identify instance providers. Consider the following example:

instance_providers(a, b, c)attribute aattribute cattribute bcombined attributesattribute C.aattribute C.cattribute (C).bclass Ctype Cinstance of C

To recognise support by instance accessors for the usage pattern concerned, attribute details must be obtained from classes as well as instances. Note that the identified type cannot support such usage purely by providing class or instance attributes alone.

Attribute Assignments

Since attribute access operations may occur as part of assignments, the nature of accesses is recorded during inspection. Combining the indexed information for assignment accesses allows the deducer to determine the most pessimistic effects on the program structure of such assignments.

Taking each attribute usage set employed by accessors involved in assignments, the types are deduced for such accessors, and each individual attribute known to be used in such assignments is then applied to the deduced types, mutating them in such a way that deductions may no longer assume a fixed identity for such attributes when obtained from these types.

assignments(a, b, c)(a, b, c) needs type Qb is assignedattribute Q.b(mutated)type Qattribute Q.aattribute Q.c

Refining Type Deductions

In the context of a specific access, the types may be resolved further:

Reference Identification

The basic information about every accessor and accessed attribute in a program can now be combined to produce specific references to identities consistent with the inspection observations. Several different kinds of accessors and access situations exist:

Aliases

Names initialised using other names or attribute accesses, or using the invocation of either of these things, are known as aliases. Information about aliases originates during inspection when such names are initialised with expression results within the program. During the resolution activity finalising the inspected details, this initialisation information is used to define relationships between aliases and other names and accesses.

During deduction, attribute accesses are investigated and type information computed for both attribute accesses and accessors. The relationships defined between accesses and aliases can then be employed to propagate such deduced information to the aliases and to define appropriate type characteristics for them.

Where aliases are used as the basis of attribute accesses, this propagation refines the previously deduced information about the aliases and may also refine the details of the accesses with which the alias is involved.

Invocation Target Suitability

Having identified accessed attributes, invocation information can be applied in cases where such attributes immediately participate in an invocation, comparing the specified argument details against the parameter details defined for the identified attribute, which must be a callable object for this technique to work. Where arguments do not appear to be suitable - either the number of arguments is incorrect or any keyword argument refer to non-existent parameters - the attribute providing the parameter details can be considered unsuitable for the access.

Classifying Accessors

Each accessor, being a particular version of a name, will have type information associated with it as a consequence of the deduction process. Such information takes the following forms:

This information can be processed in a number of ways to produce the following:

Where many types may be associated with an accessor, identifying the most general types involves eliminating those which are derived from others. Given that descendant types may not remove support for attributes provided by their ancestors, then where an ancestor type has been identified as a possible accessor, it should follow that all of its descendants may also have been identified as possible accessors. Since these descendants should be compatible, identifying them individually is unnecessary: merely specifying that the common ancestor or any descendant could provide an accessor is sufficient.

Defining Guards

A guard is a constraint supported by a run-time test indicating the compliance of an accessor with a particular type. Thus, where a single accessor type has been identified, a guard may be established for an accessor that tests the type of the accessor against a specific type. Where a single general accessor type is identified, a guard is established that tests the accessor against a "common" type: that is, an ancestor type with which other descendant types may comply.

Classifying Accesses

At the point of classifying accesses, information is available about the following:

This information can be processed in a number of ways to produce the following:

Since more than one accessor may be involved, information from all accessors must be combined to determine whether guard information still applies to the access, or whether it is possible for an accessor to be used that has an uncertain type at run-time.

Defining Tests

A test at the access level is a necessary check performed on an accessor before an access to determine whether it belongs to a certain type or group of types.

Where guards applying to accessors apply by extension to an access, it may not be enough to assume that the the attributes exposed by the accessor are the same as those considered acceptable through deduction. Therefore, attributes are obtained for the access using the applicable guard types as accessors. If this set of attributes does not include potentially accessible attributes (perhaps because the guard types are broadly defined and do not support all attribute usage), a test must be generated.

Where a single attribute provider can be identified, a test for a specific type is generated. Where a single general type can be identified as a provider, a test against a "common" type is generated. Tests involving the built-in object are not generated since it is the root of all classes and such tests would merely identify an accessor as a class. In all cases where a single, specific type cannot be tested for, the general attribute validation mechanism must be used instead.

Preparing Access Descriptions

The accumulated deduced knowledge is directed towards producing access descriptions or plans which characterise each access in terms of the following:

Characterising the Accessor

For a given access location, the referenced attribute details established during deduction are used to determine...

Some useful information about the accessor and about the actual provider of the first accessed attribute can be defined:

Class Instance Module
Accessor Class accessor Instance accessor Module accessor
Provider Class provider Instance provider

Depending on which of these criteria are satisfied, some properties of the access operation can be established:

Object-relative accesses merely involve obtaining attributes directly from accessors. Class-relative accesses involve obtaining the class of each accessor and then obtaining an attribute from that class.

Defining the First Access Method

For dynamic or unidentified accessors, the above access properties define the access method on the first attribute in the chain of attributes provided. However, any redefinition of the accessor to a static accessor may influence the first method. For static accessors, the first method is always object-relative since classes and modules do not offer transparent mechanisms to expose the attributes on their own classes.

Static and identified, dynamic accessors should already be known to support the specified attributes. Other accessors require an access method to be used that also checks whether the accessor supports a given attribute.

Redefining the Accessor

With knowledge about the initial accessor, the attributes involved in the access operation are then considered in the context of the accessor. For each attribute name in the chain described for an access, an attempt is made to obtain the details of the attribute of the given name from the accessor, determining whether these details can be used as an accessor to obtain subsequent attribute details.

Where more than one attribute identity is obtained, traversal is terminated: all remaining attributes must be traversed at run-time. If an attribute identified during traversal is static, the first access method changes accordingly.

Defining the Final Access Method

An access can also involve an assignment to the accessed attribute or the invocation of the accessed attribute. Such operations change the nature of the access method used on the final attribute in a chain of attribute names.

Identifying Context Information

Final attribute accesses involving callables need to incorporate context information that can subsequently be used to invoke those callables. Where the nature of an accessed attribute is not known, a simplistic attempt can be made to look up all attributes stored using the attribute name in the program. Otherwise, with knowledge of the attribute, its details can be inspected to determine if context information plays a role in the access.

Context Testing

Of particular interest are the following situations:

Such considerations dictate whether the context information originates from the attribute or from the accessor and whether any run-time test is required to determine this. Thus, for attributes in general:

Accessor

Provider

Attributes

Effect on Context

Remark

Always instances

Always classes

Always methods

Replacement

Permit method calling using the instance as context

Always instances

Always classes

Sometimes methods

Test at run-time

Preserve original context for non-methods

Sometimes instances

Sometimes classes

Sometimes methods

Test at run-time

Preserve original context for non-methods, non-instance accessors

In all other situations, the available context is ignored, with the attribute itself providing any stored context information.

Context Identity

Where the context is ignored, no effort will be made to obtain or retain it in the program for the access operation: it will be unset. Otherwise, the context will be defined as one of the following:

Note that non-static accessors may be computed dynamically and thus need to be stored temporarily for subsequent use.

Preparing Instruction Plans

Instruction plans are sequences of program operations, encoded in a higher-level form than actual program instructions, that describe the steps needed to access attributes. Such sequences are produced from the details provided by individual access plans.

Original Accessor

The expression providing the object from which the first attribute is obtained (or the only attribute if only one is specified) is known as the original accessor. Where this accessor can be identified, the expression describing it in the program can potentially be replaced with a static reference, and subsequent mentions of the accessor can potentially be replaced with such references or names used as expressions.

Access Plan Information

Original Accessor

Static accessor identified

Identified accessor

Named accessor access, not invocation

Indicated name

Named accessor invocation, accessor known to provide the attribute

Indicated name

Named accessor invocation, accessor not known to provide the attribute

Accessor expression

Other accessors

Accessor expression

By using names or static references, the need to store the result of evaluating an accessor expression is eliminated because such labels can be inserted in the instruction sequence as required.

First Access Operation

Although it may be possible to convert accesses into single instructions that obtain attributes directly, many accesses will involve access operations that must consult an accessor object and obtain an attribute from that object, at least for the first attribute in a chain of attributes. This occurs when the access plan indicates the following situations:

Accessor Nature

Attribute assignments involve a single target accessor and potentially many other accessors, depending on how many distinct expressions are evaluated to yield the value to be set in the assignment. Such a target accessor will usually be derived from the evaluation of an expression, and in some cases the expression will be the result of an opaque operation such as the invocation of a function. In such cases, the target accessor is stored in a temporary variable for subsequent use in access operations.

Context

Access Tests

Traversing Identified Attributes

Traversing Unidentified Attributes

Final Access Operation

Context Testing

Instruction Details

The emitted instructions are as follows.

Direct Load

These instructions employ the attribute position for the supplied attribute name.

Instruction

Arguments

Operations

__load_via_class

object, attribute name

Obtain class from object; load attribute from class at position

__load_via_object

object, attribute name

Load attribute from object at position

__get_class_and_load

object, attribute name

Obtain class from object if instance; load attribute from result at position

Direct Store

These instructions employ the attribute position for the supplied attribute name, storing an attribute value.

Instruction

Arguments

Operations

__store_via_class

object, attribute name, value

Obtain class from object; store attribute in class at position

__store_via_object

object, attribute name, value

Store attribute in object at position

Checked Load

These instructions employ the attribute position and code for the supplied attribute name.

Instruction

Arguments

Operations

__check_and_load_via_class

object, attribute name

Obtain class from object; test for attribute and load or raise type error

__check_and_load_via_object

object, attribute name

Test for attribute and load or raise type error

__check_and_load_via_any

object, attribute name

Test for attribute and load or obtain class; test for attribute and load or raise type error

Checked Store

These instructions employ the attribute position and code for the supplied attribute name, storing an attribute value.

Instruction

Arguments

Operations

__check_and_store_via_class

object, attribute name, value

Raise type error

__check_and_store_via_object

object, attribute name, value

Test for attribute and store value or raise type error

__check_and_store_via_any

object, attribute name, value

Test for attribute and store value or raise type error

Testing

These instructions employ the special attribute position and code for the supplied type name.

Instruction

Arguments

Operations

__test_common_instance

object, type

Obtain class from object; test conformance to type

__test_common_object

object, type

Test conformance to type or obtain class from object and test conformance to type

__test_common_type

object, type

Test conformance to type

__test_specific_instance

object, type

Obtain class from object; test equivalence to type

__test_specific_object

object, type

Test equivalence to type or obtain class from object and test equivalence to type

__test_specific_type

object, type

Test equivalence to type

Static Load

These instructions obtain references to static objects, in some cases employing a supplied context.

Instruction

Arguments

Operations

__load_static_ignore

object

Load attribute populated with object, leaving the context unset

__load_static_replace

context, object

Load attribute populated with the context and object

__load_static_test

context, object

Load attribute populated with object; test context compatibility and set the context

Temporary Access

These instructions access temporary values retained to perform the attribute access. The temporary storage index is generated during program translation.

Instruction

Arguments

Operations

__get_context

(temporary)

Load the context stored in the temporary storage

__set_accessor

accessor

Store the accessor temporarily

__set_context

(temporary), context

Store the context in the temporary storage

__set_private_context

context

Store the context temporarily

__set_target_accessor

accessor

Store the assignment accessor temporarily

Context Test

These instructions perform tests on the available context object. The temporary storage index is generated during program translation.

Instruction

Arguments

Operations

__test_context_revert

(temporary), context, attribute

Test compatibility of context; revert temporary to attribute context if incompatible

__test_context_static

(temporary), context, value

Test compatibility of context; set temporary to specified context if compatible

Deduction Products

The deduction process should produce a complete catalogue of accessor and access references that may then be consulted by the translation process needing to know the nature of any operation within the program. Central to the translation process's understanding of references is the attribute access plan for each reference which characterises each access and provides the basis for the formulation of the instruction plan used to replicate it in the final program.