paul@109 | 1 | Data Structures
|
paul@109 | 2 | ===============
|
paul@109 | 3 |
|
paul@109 | 4 | The fundamental "value type" is a pair of references: one pointing to the
|
paul@109 | 5 | referenced object represented by the interchangeable value; one referring to
|
paul@109 | 6 | the context of the referenced object, typically the object through which the
|
paul@109 | 7 | referenced object was acquired as an attribute.
|
paul@109 | 8 |
|
paul@109 | 9 | Value Layout
|
paul@109 | 10 | ------------
|
paul@109 | 11 |
|
paul@109 | 12 | 0 1
|
paul@109 | 13 | object context
|
paul@109 | 14 | reference reference
|
paul@109 | 15 |
|
paul@185 | 16 | Such values are used as the stored representations of attributes (of classes,
|
paul@185 | 17 | instances, modules, and other objects supporting attribute-like entities) as
|
paul@185 | 18 | well as the stored values associated with names in functions and methods.
|
paul@185 | 19 |
|
paul@185 | 20 | Stored Values and Contexts
|
paul@185 | 21 | --------------------------
|
paul@185 | 22 |
|
paul@185 | 23 | In a program image, generated attribute data will employ values, and these
|
paul@185 | 24 | values will generally have the following context definitions according to the
|
paul@185 | 25 | type of the referenced objects:
|
paul@185 | 26 |
|
paul@185 | 27 | Referenced Object Type Context
|
paul@185 | 28 | ---------------------- -------
|
paul@185 | 29 |
|
paul@185 | 30 | Function None
|
paul@185 | 31 |
|
paul@185 | 32 | Method Parent object (class)
|
paul@185 | 33 |
|
paul@185 | 34 | Class None
|
paul@185 | 35 |
|
paul@185 | 36 | Value and Context Transformations
|
paul@185 | 37 | ---------------------------------
|
paul@109 | 38 |
|
paul@109 | 39 | Values are acquired through name lookups and attribute access, yielding
|
paul@109 | 40 | the appropriate object reference together with a context reference as
|
paul@109 | 41 | indicated in the following table:
|
paul@109 | 42 |
|
paul@109 | 43 | Type of Access Context Notes
|
paul@109 | 44 | -------------- ------- -----
|
paul@109 | 45 |
|
paul@109 | 46 | Local name Preserved Functions provide no context
|
paul@109 | 47 |
|
paul@109 | 48 | Global name Preserved Modules provide no context
|
paul@109 | 49 |
|
paul@109 | 50 | Class-originating Accessor Class accessor preserves the stored
|
paul@109 | 51 | attribute -or- context; instance accessor overrides
|
paul@109 | 52 | Preserved the stored context if it is null or
|
paul@109 | 53 | belongs to the instance's class
|
paul@109 | 54 | hierarchy
|
paul@109 | 55 |
|
paul@109 | 56 | Instance-originating Preserved Methods retain their original context
|
paul@109 | 57 | attribute
|
paul@109 | 58 |
|
paul@109 | 59 | There may be some scope for simplifying the above, to the detriment of Python
|
paul@109 | 60 | compatibility, since the unbound vs. bound methods situation can be confusing.
|
paul@109 | 61 |
|
paul@119 | 62 | Acquiring Values
|
paul@119 | 63 | ----------------
|
paul@109 | 64 |
|
paul@109 | 65 | According to the table describing value acquisition, different instructions
|
paul@109 | 66 | must implement different operations when acquiring values:
|
paul@109 | 67 |
|
paul@109 | 68 | Instruction Purpose Context Operations
|
paul@109 | 69 | ----------- ------- ------------------
|
paul@109 | 70 |
|
paul@109 | 71 | LoadConst Load class, function, Combine null context with loaded
|
paul@109 | 72 | module, constant object
|
paul@109 | 73 |
|
paul@109 | 74 | LoadAddress Load attribute from Classes, functions and modules
|
paul@119 | 75 | known object cause the loaded attribute to be
|
paul@186 | 76 | (typically classes and retrieved unchanged; whereas
|
paul@186 | 77 | modules) constants (representing instances)
|
paul@109 | 78 | cause the constant to override the
|
paul@109 | 79 | attribute's own context (since all
|
paul@109 | 80 | attributes should belong to the
|
paul@109 | 81 | constant's class hierarchy)
|
paul@109 | 82 |
|
paul@186 | 83 | LoadAddressContext Load attribute Override loaded context with a
|
paul@186 | 84 | from known object predetermined object (provided
|
paul@186 | 85 | (typically classes) that the object and context are
|
paul@186 | 86 | for an instance compatible, which can be tested at
|
paul@123 | 87 | compile-time)
|
paul@119 | 88 |
|
paul@186 | 89 | LoadAttr Load attribute from Contexts are preserved (since only
|
paul@186 | 90 | instance values stored on instances can be
|
paul@186 | 91 | accessed in this way, and their
|
paul@186 | 92 | contexts would never be overridden
|
paul@186 | 93 | upon access
|
paul@109 | 94 |
|
paul@186 | 95 | LoadAttrIndex Load attribute from Classes, functions and modules as
|
paul@186 | 96 | object (can be the unknown object accessor cause
|
paul@186 | 97 | classes, modules, the loaded attribute to be
|
paul@186 | 98 | instances...) retrieved unchanged; instances
|
paul@186 | 99 | cause the LoadAttr rules to apply
|
paul@186 | 100 | (class compatibility applies)
|
paul@109 | 101 |
|
paul@119 | 102 | A certain amount of run-time testing might be required for both LoadAttr and
|
paul@119 | 103 | LoadAttrIndex instructions. However, with certain restrictions in place around
|
paul@119 | 104 | class attributes, some simplifications are possible:
|
paul@119 | 105 |
|
paul@119 | 106 | * Since only class-originating attributes may cause context overriding, and
|
paul@119 | 107 | since class attributes may only be defined within class definitions, the
|
paul@119 | 108 | attributes whose context may be modified should be known at compile-time.
|
paul@123 | 109 | (These will be those attributes whose context agrees with their parent
|
paul@123 | 110 | class.)
|
paul@119 | 111 |
|
paul@119 | 112 | * By recording a special context value for attributes whose context can be
|
paul@119 | 113 | overridden, this value can be tested efficiently at run-time where the
|
paul@123 | 114 | appropriate conditions are satisfied. (This special context value or
|
paul@123 | 115 | indicator will be present in the object table record for the attribute.)
|
paul@119 | 116 |
|
paul@119 | 117 | * It should be possible to move the instance compatibility condition testing
|
paul@119 | 118 | to compile-time by testing the compatibility of the origin of an attribute
|
paul@123 | 119 | with the class on which it is stored. However, some compatibility testing
|
paul@123 | 120 | will still be required if invoking methods via classes, since the instance
|
paul@123 | 121 | will be specified in the argument list instead of being presented in an
|
paul@123 | 122 | attribute lookup instruction.
|
paul@119 | 123 |
|
paul@119 | 124 | Storing Values
|
paul@119 | 125 | --------------
|
paul@119 | 126 |
|
paul@119 | 127 | According to the table describing value acquisition, different instructions
|
paul@119 | 128 | must implement different operations when acquiring values:
|
paul@119 | 129 |
|
paul@119 | 130 | Instruction Purpose Context Operations
|
paul@119 | 131 | ----------- ------- ------------------
|
paul@119 | 132 |
|
paul@119 | 133 | StoreAddress Store attribute in a Preserve context; note that no
|
paul@119 | 134 | known object test for class attribute
|
paul@119 | 135 | assignment should be necessary
|
paul@119 | 136 | since this instruction should only
|
paul@119 | 137 | be generated for module globals
|
paul@119 | 138 |
|
paul@119 | 139 | StoreAttr Store attribute in an Preserve context; note that no
|
paul@119 | 140 | instance test for class attribute
|
paul@119 | 141 | assignment should be necessary
|
paul@119 | 142 | since this instruction should only
|
paul@119 | 143 | be generated for self accesses
|
paul@119 | 144 |
|
paul@119 | 145 | StoreAttrIndex Store attribute in an Preserve context; since the index
|
paul@119 | 146 | unknown object lookup could yield a class
|
paul@119 | 147 | attribute, a test of the nature of
|
paul@119 | 148 | the nature of the structure is
|
paul@119 | 149 | necessary in order to prevent
|
paul@119 | 150 | assignments to classes
|
paul@109 | 151 |
|
paul@186 | 152 | Note that contexts are never changed in the stored value: they are preserved.
|
paul@186 | 153 |
|
paul@109 | 154 | Objects
|
paul@109 | 155 | -------
|
paul@109 | 156 |
|
paul@109 | 157 | Since classes, functions and instances are all "objects", each must support
|
paul@109 | 158 | certain features and operations in the same way.
|
paul@109 | 159 |
|
paul@109 | 160 | The __class__ Attribute
|
paul@109 | 161 | -----------------------
|
paul@109 | 162 |
|
paul@109 | 163 | All objects support the __class__ attribute:
|
paul@109 | 164 |
|
paul@109 | 165 | Class: refers to the type class (type.__class__ also refers to the type class)
|
paul@109 | 166 | Function: refers to the function class
|
paul@109 | 167 | Instance: refers to the class instantiated to make the object
|
paul@109 | 168 |
|
paul@109 | 169 | Invocation
|
paul@109 | 170 | ----------
|
paul@109 | 171 |
|
paul@109 | 172 | The following actions need to be supported:
|
paul@109 | 173 |
|
paul@109 | 174 | Class: create instance, call __init__ with instance, return object
|
paul@109 | 175 | Function: call function body, return result
|
paul@109 | 176 | Instance: call __call__ method, return result
|
paul@109 | 177 |
|
paul@109 | 178 | Structure Layout
|
paul@109 | 179 | ----------------
|
paul@109 | 180 |
|
paul@109 | 181 | A suitable structure layout might be something like this:
|
paul@109 | 182 |
|
paul@134 | 183 | Identifier Identifier Address Details Type Object ...
|
paul@109 | 184 |
|
paul@134 | 185 | 0 1 2 3 4 5 6
|
paul@134 | 186 | classcode attrcode invocation invocation __class__ attribute ...
|
paul@134 | 187 | reference #args, reference reference
|
paul@137 | 188 | defaults
|
paul@137 | 189 | reference
|
paul@109 | 190 |
|
paul@109 | 191 | Here, the classcode refers to the attribute lookup table for the object. Since
|
paul@109 | 192 | classes and instances share the same classcode, they might resemble the
|
paul@109 | 193 | following:
|
paul@109 | 194 |
|
paul@109 | 195 | Class C:
|
paul@109 | 196 |
|
paul@134 | 197 | 0 1 2 3 4 5 6
|
paul@134 | 198 | code for C attrcode __new__ __new__ class type attribute ...
|
paul@134 | 199 | for C reference #args, reference reference
|
paul@137 | 200 | defaults
|
paul@137 | 201 | reference
|
paul@109 | 202 |
|
paul@109 | 203 | Instance of C:
|
paul@109 | 204 |
|
paul@134 | 205 | 0 1 2 3 4 5 6
|
paul@134 | 206 | code for C attrcode C.__call__ C.__call__ class C attribute ...
|
paul@134 | 207 | for C reference #args, reference reference
|
paul@137 | 208 | (if exists) defaults
|
paul@137 | 209 | reference
|
paul@109 | 210 |
|
paul@109 | 211 | The __new__ reference would lead to code consisting of the following
|
paul@109 | 212 | instructions:
|
paul@109 | 213 |
|
paul@109 | 214 | create instance for C
|
paul@109 | 215 | call C.__init__(instance, ...)
|
paul@109 | 216 | return instance
|
paul@109 | 217 |
|
paul@109 | 218 | If C has a __call__ attribute, the invocation "slot" of C instances would
|
paul@182 | 219 | refer to the same thing as C.__call__. This "slot" has to be prepared when
|
paul@184 | 220 | creating instances, either by modifying the sequence of instructions used in,
|
paul@184 | 221 | amongst other places, the instantiator function, or by generating a template
|
paul@184 | 222 | instance whose details are copied when new instances are created.
|
paul@109 | 223 |
|
paul@109 | 224 | For functions, the same general layout applies:
|
paul@109 | 225 |
|
paul@109 | 226 | Function f:
|
paul@109 | 227 |
|
paul@134 | 228 | 0 1 2 3 4 5 6
|
paul@134 | 229 | code for attrcode code code class attribute ...
|
paul@134 | 230 | function for reference #args, function (default)
|
paul@137 | 231 | function defaults reference reference
|
paul@137 | 232 | reference
|
paul@109 | 233 |
|
paul@109 | 234 | Here, the code reference would lead to code for the function. Note that the
|
paul@109 | 235 | function locals are completely distinct from this structure and are not
|
paul@109 | 236 | comparable to attributes. Instead, attributes are reserved for default
|
paul@109 | 237 | parameter values.
|
paul@109 | 238 |
|
paul@109 | 239 | For modules, there is no meaningful invocation reference:
|
paul@109 | 240 |
|
paul@109 | 241 | Module m:
|
paul@109 | 242 |
|
paul@134 | 243 | 0 1 2 3 4 5 6
|
paul@134 | 244 | code for m attrcode (unused) (unused) module type attribute ...
|
paul@134 | 245 | for m reference (global)
|
paul@134 | 246 | reference
|
paul@109 | 247 |
|
paul@109 | 248 | Both classes and modules have code in their definitions, but this would be
|
paul@109 | 249 | generated in order and not referenced externally.
|
paul@109 | 250 |
|
paul@109 | 251 | Invocation Operation
|
paul@109 | 252 | --------------------
|
paul@109 | 253 |
|
paul@109 | 254 | Consequently, regardless of the object an invocation is always done as
|
paul@109 | 255 | follows:
|
paul@109 | 256 |
|
paul@109 | 257 | get invocation reference (at object+1)
|
paul@109 | 258 | jump to reference
|
paul@109 | 259 |
|
paul@109 | 260 | Additional preparation is necessary before the above code: positional
|
paul@109 | 261 | arguments must be saved to the parameter stack, and keyword arguments must be
|
paul@109 | 262 | resolved and saved to the appropriate position in the parameter stack.
|
paul@109 | 263 |
|
paul@109 | 264 | Attribute Operations
|
paul@109 | 265 | --------------------
|
paul@109 | 266 |
|
paul@109 | 267 | Attribute access needs to go through the attribute lookup table. Some
|
paul@109 | 268 | optimisations are possible and are described in the appropriate section.
|
paul@109 | 269 |
|
paul@109 | 270 | One important aspect of attribute access is the appropriate setting of the
|
paul@109 | 271 | context in the acquired attribute value. From the table describing the
|
paul@109 | 272 | acquisition of values, it is clear that the principal exception is that where
|
paul@109 | 273 | a class-originating attribute is accessed on an instance. Consequently, the
|
paul@109 | 274 | following algorithm could be employed once an attribute has been located:
|
paul@109 | 275 |
|
paul@109 | 276 | 1. If the attribute's context is a special value, indicating that it should
|
paul@109 | 277 | be replaced upon instance access, then proceed to the next step;
|
paul@109 | 278 | otherwise, acquire both the context and the object as they are.
|
paul@109 | 279 |
|
paul@109 | 280 | 2. If the accessor is an instance, use that as the value's context, acquiring
|
paul@109 | 281 | only the object from the attribute.
|
paul@109 | 282 |
|
paul@109 | 283 | Where accesses can be determined ahead of time (as discussed in the
|
paul@109 | 284 | optimisations section), the above algorithm may not necessarily be employed in
|
paul@109 | 285 | the generated code for some accesses.
|
paul@134 | 286 |
|
paul@134 | 287 | Instance/Class Compatibility
|
paul@134 | 288 | ----------------------------
|
paul@134 | 289 |
|
paul@134 | 290 | Although it would be possible to have a data structure mapping classes to
|
paul@134 | 291 | compatible classes, which in the case of context (or self argument)
|
paul@134 | 292 | suitability in invocations would involve a mapping from a class to itself plus
|
paul@134 | 293 | its descendants, the need to retain the key to such a data structure for each
|
paul@134 | 294 | class might introduce a noticeable overhead. Such a structure would
|
paul@134 | 295 | effectively be a matrix with each dimension indexed using the same sequence of
|
paul@134 | 296 | codes for each of the classes in a program.
|
paul@134 | 297 |
|
paul@181 | 298 | The current solution is to insert descendants as special attributes into the
|
paul@181 | 299 | object/attribute lookup table. This requires an extra key to be retained,
|
paul@181 | 300 | since each class must provide its own attribute code such that upon an
|
paul@181 | 301 | instance/class compatibility test, the code may be obtained and used in the
|
paul@181 | 302 | object table.
|