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