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 retrieved unchanged; whereas
77 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 Override loaded context with a
84 predetermined object (provided
85 that the object and context are
86 compatible, which can be tested at
87 compile-time)
88
89 LoadAttr Load attribute from Attributes with null contexts or
90 instance contexts compatible with the
91 instance cause loaded attributes
92 to combine the instance as context
93 with the object from the
94 attribute; other attributes have
95 their context preserved
96
97 LoadAttrIndex Load attribute from Functions and modules as unknown
98 object the unknown object accessor cause
99 the loaded attribute to be
100 retrieved unchanged; classes and
101 instances cause the LoadAttr rules
102 to apply (class compatibility
103 applies)
104
105 A certain amount of run-time testing might be required for both LoadAttr and
106 LoadAttrIndex instructions. However, with certain restrictions in place around
107 class attributes, some simplifications are possible:
108
109 * Since only class-originating attributes may cause context overriding, and
110 since class attributes may only be defined within class definitions, the
111 attributes whose context may be modified should be known at compile-time.
112 (These will be those attributes whose context agrees with their parent
113 class.)
114
115 * By recording a special context value for attributes whose context can be
116 overridden, this value can be tested efficiently at run-time where the
117 appropriate conditions are satisfied. (This special context value or
118 indicator will be present in the object table record for the attribute.)
119
120 * It should be possible to move the instance compatibility condition testing
121 to compile-time by testing the compatibility of the origin of an attribute
122 with the class on which it is stored. However, some compatibility testing
123 will still be required if invoking methods via classes, since the instance
124 will be specified in the argument list instead of being presented in an
125 attribute lookup instruction.
126
127 Storing Values
128 --------------
129
130 According to the table describing value acquisition, different instructions
131 must implement different operations when acquiring values:
132
133 Instruction Purpose Context Operations
134 ----------- ------- ------------------
135
136 StoreAddress Store attribute in a Preserve context; note that no
137 known object test for class attribute
138 assignment should be necessary
139 since this instruction should only
140 be generated for module globals
141
142 StoreAttr Store attribute in an Preserve context; note that no
143 instance test for class attribute
144 assignment should be necessary
145 since this instruction should only
146 be generated for self accesses
147
148 StoreAttrIndex Store attribute in an Preserve context; since the index
149 unknown object lookup could yield a class
150 attribute, a test of the nature of
151 the nature of the structure is
152 necessary in order to prevent
153 assignments to classes
154
155 Objects
156 -------
157
158 Since classes, functions and instances are all "objects", each must support
159 certain features and operations in the same way.
160
161 The __class__ Attribute
162 -----------------------
163
164 All objects support the __class__ attribute:
165
166 Class: refers to the type class (type.__class__ also refers to the type class)
167 Function: refers to the function class
168 Instance: refers to the class instantiated to make the object
169
170 Invocation
171 ----------
172
173 The following actions need to be supported:
174
175 Class: create instance, call __init__ with instance, return object
176 Function: call function body, return result
177 Instance: call __call__ method, return result
178
179 Structure Layout
180 ----------------
181
182 A suitable structure layout might be something like this:
183
184 Identifier Identifier Address Details Type Object ...
185
186 0 1 2 3 4 5 6
187 classcode attrcode invocation invocation __class__ attribute ...
188 reference #args, reference reference
189 defaults
190 reference
191
192 Here, the classcode refers to the attribute lookup table for the object. Since
193 classes and instances share the same classcode, they might resemble the
194 following:
195
196 Class C:
197
198 0 1 2 3 4 5 6
199 code for C attrcode __new__ __new__ class type attribute ...
200 for C reference #args, reference reference
201 defaults
202 reference
203
204 Instance of C:
205
206 0 1 2 3 4 5 6
207 code for C attrcode C.__call__ C.__call__ class C attribute ...
208 for C reference #args, reference reference
209 (if exists) defaults
210 reference
211
212 The __new__ reference would lead to code consisting of the following
213 instructions:
214
215 create instance for C
216 call C.__init__(instance, ...)
217 return instance
218
219 If C has a __call__ attribute, the invocation "slot" of C instances would
220 refer to the same thing as C.__call__. This "slot" has to be prepared when
221 creating instances, either by modifying the sequence of instructions used in,
222 amongst other places, the instantiator function, or by generating a template
223 instance whose details are copied when new instances are created.
224
225 For functions, the same general layout applies:
226
227 Function f:
228
229 0 1 2 3 4 5 6
230 code for attrcode code code class attribute ...
231 function for reference #args, function (default)
232 function defaults reference reference
233 reference
234
235 Here, the code reference would lead to code for the function. Note that the
236 function locals are completely distinct from this structure and are not
237 comparable to attributes. Instead, attributes are reserved for default
238 parameter values.
239
240 For modules, there is no meaningful invocation reference:
241
242 Module m:
243
244 0 1 2 3 4 5 6
245 code for m attrcode (unused) (unused) module type attribute ...
246 for m reference (global)
247 reference
248
249 Both classes and modules have code in their definitions, but this would be
250 generated in order and not referenced externally.
251
252 Invocation Operation
253 --------------------
254
255 Consequently, regardless of the object an invocation is always done as
256 follows:
257
258 get invocation reference (at object+1)
259 jump to reference
260
261 Additional preparation is necessary before the above code: positional
262 arguments must be saved to the parameter stack, and keyword arguments must be
263 resolved and saved to the appropriate position in the parameter stack.
264
265 Attribute Operations
266 --------------------
267
268 Attribute access needs to go through the attribute lookup table. Some
269 optimisations are possible and are described in the appropriate section.
270
271 One important aspect of attribute access is the appropriate setting of the
272 context in the acquired attribute value. From the table describing the
273 acquisition of values, it is clear that the principal exception is that where
274 a class-originating attribute is accessed on an instance. Consequently, the
275 following algorithm could be employed once an attribute has been located:
276
277 1. If the attribute's context is a special value, indicating that it should
278 be replaced upon instance access, then proceed to the next step;
279 otherwise, acquire both the context and the object as they are.
280
281 2. If the accessor is an instance, use that as the value's context, acquiring
282 only the object from the attribute.
283
284 Where accesses can be determined ahead of time (as discussed in the
285 optimisations section), the above algorithm may not necessarily be employed in
286 the generated code for some accesses.
287
288 Instance/Class Compatibility
289 ----------------------------
290
291 Although it would be possible to have a data structure mapping classes to
292 compatible classes, which in the case of context (or self argument)
293 suitability in invocations would involve a mapping from a class to itself plus
294 its descendants, the need to retain the key to such a data structure for each
295 class might introduce a noticeable overhead. Such a structure would
296 effectively be a matrix with each dimension indexed using the same sequence of
297 codes for each of the classes in a program.
298
299 The current solution is to insert descendants as special attributes into the
300 object/attribute lookup table. This requires an extra key to be retained,
301 since each class must provide its own attribute code such that upon an
302 instance/class compatibility test, the code may be obtained and used in the
303 object table.