docs/pdds/draft/pdd08_keys.pod

   1 # Copyright (C) 2001-2010, Parrot Foundation.
   2 # $Id$
   3
   4 =head1 [DRAFT] PDD 8: PMC Keys
   5
   6 =head2 Abstract
   7
   8 This PDD aims to clear up the confusion regarding the implementation of keyed
   9 access to PMCs in Parrot.
  10
  11 =head2 Version
  12
  13 $Revision$
  14
  15 =head2 Description
  16
  17 First, let's define some terminology. An C<aggregate PMC> is one which stores
  18 or references other values as elements.  The aggregate PMC allows indexed
  19 access to element by implementing some of the C<_keyed> variants of VTABLE
  20 functions.  These variants are called C<indexing> operations, as they act on a
  21 specific indexed element of an aggregate PMC.  Examples of a aggregate PMCs
  22 include C<Hash>, C<FixedIntegerArray> and C<ResizablePMCArray>.
  23
  24 Non-aggregates may also support C<_keyed> variants of the VTABLE functions,
  25 but they not do anything particularly clever.  For instance, PMC types
  26 implementing Perl references will merely pass the index on to the referent.
  27 These aren't aggregates because they don't directly store or reference
  28 elements.
  29
  30 Indexing operations take one or more aggregate B<keys>.  At runtime these
  31 operations will index into the B<aggregate> using the C<key> and return a
  32 B<value>.  Here is a well-known indexing operation in Perl 6:
  33
  34     @a[12] = $b;
  35
  36 The B<key> here is the constant integer C<12>  The aggregate is the
  37 C<Perl6Array> C<@a>.  In the process of this assignment, Parrot will have to
  38 extract the PMC in element 12 of the array, producing a C<value>.
  39 C<$b> is then assigned to this value.
  40
  41 Now, how does this all get implemented?
  42
  43 =head2 Implementation
  44
  45 =head3 The key structure
  46
  47 The key structure must bundle multiple keys.  This is to allow indexing into
  48 multidimensional aggregate PMCs.  These keys may be specified as integer,
  49 string, number or PMC.
  50
  51 For this reason the following structure was produced.  Individual keys (e.g. a
  52 single C<Integer> or C<String>) are stored in a C<Key> PMC.  The type of the
  53 key is encoded in the private flags of the PMC as specified below.   The value
  54 of the C<Key> PMC is stored in the PMC's data structure internally and can be
  55 accessed using the appropriate get_* VTABLE functions.
  56
  57 For example, indexing the multidimensional array C<@foo[$a,12;"hi"]>
  58 produces three PMCs; one with a PMC type, one with an integer type
  59 and one with a string type.
  60
  61 The key type is encoded in the PMC flags using 8 bits based on the following
  62 scheme (from includes/parrot/key.h):
  63
  64     typedef enum {
  65         KEY_integer_FLAG        = PObj_private0_FLAG,
  66         KEY_number_FLAG         = PObj_private1_FLAG,
  67         KEY_hash_iterator_FLAGS = PObj_private0_FLAG | PObj_private1_FLAG,
  68         KEY_string_FLAG         = PObj_private2_FLAG,
  69         KEY_pmc_FLAG            = PObj_private3_FLAG,
  70         KEY_register_FLAG       = PObj_private4_FLAG,
  71
  72         KEY_type_FLAGS          = KEY_integer_FLAG   |
  73                                   KEY_number_FLAG    |
  74                                   KEY_string_FLAG    |
  75                                   KEY_pmc_FLAG       |
  76                                   KEY_register_FLA G |
  77                                   KEY_hash_iterator_FLAGS
  78     } KEY_flags
  79
  80
  81 The C<KEY_register_FLAG> is used to indicate that value if the key is in a
  82 register.  In this case, the Key PMC's data contains the integer number of the
  83 appropriate register in the current context.
  84
  85 Parrot must also have a way to combine multiple keys into a key that can be
  86 treated as a single unit.  This is done by forming a singly linked list such
  87 that each key points at the next.  Within a single Key PMC, the pointer to the
  88 next key is stored in C<PMC_data(key)>.  The linked list structure allows the
  89 use of partial keys in multidimensional lookups, since the next key can be
  90 generated while the aggregate PMC is being traversed.
  91
  92 These definitions, along with declarations of support routines used to
  93 manipulate keys, can be found in F<include/parrot/key.h>
  94
  95 =head3 Aggregate and non-aggregate PMCs
  96
  97 We've already said that what separates the aggregate PMCs from the
  98 non-aggregates is their implementation of the C<_keyed> vtable functions. So
  99 it is Hereby Decreed that the default vtable which everyone inherits from
 100 defines the C<_keyed> forms to throw an exception.
 101
 102 =over 3
 103
 104 =item Todo
 105
 106 Need discussion on whether C<EXCEPTION_OUT_OF_BOUNDS> is a good exception for
 107 this, or whether something else should be used. It's really a compiler
 108 screw-up, since code which indexes a non-aggregate shouldn't be generated.
 109
 110 =back
 111
 112 =head3 C<_keyed> vtable functions
 113
 114 So what of these magical C<_keyed> vtable functions? They are generated when
 115 you add the C<keyed> tag to the appropriate entry in F<src/vtable.tbl>. They
 116 are constructed by following B<every> C<PMC> argument with a second C<PMC>
 117 argument which acts as the key for that argument; the name of the second
 118 C<PMC> argument is formed by adding C<_key> onto the end of the first C<PMC>
 119 argument.
 120
 121 The reason why every PMC argument has an associated key is twofold. Firstly,
 122 it means that
 123
 124     @a[$b] = $c
 125
 126 and
 127
 128     $a = @b[$c]
 129
 130 use the same vtable function, reducing the multiplicity of methods. Secondly,
 131 a three-argument C<assign> as suggested by the code above would be ambiguous -
 132 the code above uses 3 PMCs in different ways.
 133
 134 Also, operations which take an aggregate key for one of their arguments should
 135 take aggregate keys for B<all> of their arguments. This is to avoid the
 136 following:
 137
 138     void foo_keyed_i(PMC* x, PMC* x_key, INT a)
 139     void foo_keyed_n(PMC* x, PMC* x_key, NUM a)
 140     void foo_keyed_p(PMC* x, PMC* x_key, PMC a)
 141     void foo_keyed_p_keyed(PMC* x, PMC* x_key, PMC* a, PMC* a_key)
 142
 143 These are all replaced with the single entry
 144
 145     void foo_keyed(PMC* x, PMC* a_key, PMC* a, PMC* a_key)
 146
 147 (Think how much worse it gets when there are three or more PMCs in an
 148 entry...)
 149
 150 Yes. This means that you may need to turn some things into C<PMC>s that you
 151 didn't want to. Since the alternative is mega pollution and duplication in the
 152 vtable table, and since the majority of things that you'll deal with in a real
 153 world situation are expected to be C<PMC>s anyway, this shouldn't be too much
 154 of a problem.
 155
 156 So, if you have a PMC in a C<_keyed> method which you don't want to index,
 157 pass in C<NULL> instead of a real key. Code implementing these methods should
 158 understand C<PMC* foo, PMC* NULL> as meaning the entirety of C<foo> in some
 159 sense; this is trivial to understand if C<foo> is non-aggregate, and
 160 implementation-defined if C<foo> is aggregate. If you remember that a key PMC
 161 is really a linked list, you'll notice that after traversing down through the
 162 list, you'll reach a C<NULL> which again means the entirety of whatever object
 163 you traversed to.
 164
 165 Similarly, non-C<_keyed> methods on aggregates are implementation defined; for
 166 instance, a C<set_integer> on a C<PerlArray> may be understood as setting
 167 C<@array.length>.
 168
 169 Historically, we first implemented keys as two separate keyed methods per
 170 applicable method - C<..._index> and C<..._index_s> for integer and string
 171 indexing respectively. However, this didn't give us the flexibility and
 172 scalability that key structures give us.
 173
 174 =head3 Input to the assembler
 175
 176 There are several different valid specifications of an aggregate key to the
 177 assembler. These are:
 178
 179     op arg, P1[1234]  # Constant integer key
 180     op arg, P1[I1]    # Integer key
 181
 182     op arg, P1[12.34] # Constant number key - handled as constant key
 183     op arg, P1["foo"] # Constant string key - handled as constant key
 184     op arg, P1[I1;I2] # Multi-level key - handled as constant key
 185
 186     op arg, P1[P1]    # Register key
 187
 188 (Rationale: fits programmer's expectation, easier to understand at a glance
 189 than C<op P1, P2, P3>. Also, is C<op P1, P2, P3> the same as C<op P1[P2], P3>
 190 or C<op P1, P2[P3]>, or are these three separate PMCs?)
 191
 192 In all there are four types of key. The first two are integer keys and
 193 constant integer keys which are optimisations for the common case of single
 194 level integer keys.
 195
 196 The other two are constant keys, which can handle any combination of constants
 197 and registers with any number of levels; and register keys which are
 198 represented by a single PMC register that is assumed to  contain a PMC of the
 199 Key class.
 200
 201 =head3 What the assembler did next
 202
 203 When the assembler sees an aggregate key, it "detaches" the key to form a
 204 separate argument. It then decides on the type of key. For  integer keys (both
 205 constant and register) the data is encoded in the same way as an ordinary
 206 integer argument. For register keys the data is encoded as for an ordinary PMC
 207 register argument, while for constant keys a key constant is generated that
 208 encodes the list of constants and registers that make up the key and an
 209 appropriate index into the constant table is encoded as the argument.
 210
 211 Next it selects the appropriate op. Register keys have the signature C<k> and
 212 constant keys have the signature C<kc>. Integer register and constant keys are
 213 encoded as C<ki> and C<kic> respectively.
 214
 215 =begin PIR_FRAGMENT
 216
 217     set $P1["hi"], 1234
 218
 219 =end PIR_FRAGMENT
 220
 221 finds an op named C<set_p_kc_i>. On the other hand,
 222
 223 =begin PIR_FRAGMENT
 224
 225     set $P1[$P1], 1234
 226
 227 =end PIR_FRAGMENT
 228
 229 produces an op named C<set_p_k_i>. Likewise, this:
 230
 231 =begin PIR_FRAGMENT
 232
 233     set $P1[1], 1234
 234
 235 =end PIR_FRAGMENT
 236
 237 produces an op named C<set_p_kic>, and this:
 238
 239 =begin PIR_FRAGMENT
 240
 241     set $P1[$I1], 1234
 242
 243 =end PIR_FRAGMENT
 244
 245 produces an op named C<set_p_ki>.
 246
 247 =head3 Bytecode representation
 248
 249 The bytecode representation of these keys are as follows: constant keys are
 250 treated just like another constant, and are an index into the packfile's
 251 constant table.
 252
 253 Each key in that constant table consists of one word specifying its length in
 254 terms of number of keys. For instance, C<["hi"]> has length 1;
 255 C<["hi";P1;S1;123]> has length 4. Next, each key is specified using two words.
 256 The first word is a type specifier:
 257
 258     1 - Integer constant
 259     2 - Number constant
 260     4 - String constant
 261     7 - Integer register
 262     8 - Number register
 263     9 - PMC register
 264    10 - String register
 265
 266 and the second word is either a value (for integer constants), a register
 267 number (for registers) or an index into the appropriate constant table.
 268
 269 The type values shown above are actually the C<PARROT_ARG_*> values taken from
 270 F<include/parrot/op.h>.
 271
 272 =head2 References
 273
 274 None.
 275
 276 =cut
 277
 278 __END__
 279 Local Variables:
 280   fill-column:78
 281 End:
 282 vim: expandtab shiftwidth=4: