<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Parrot - [DRAFT] PDD 8: PMC Keys</title>
<link rel="stylesheet" type="text/css"
href="../../../../resources/parrot.css"
media="all">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<body>
<div id="wrapper">
<div id="header">
<a href="http://www.parrot.org">
<img border=0 src="../../../../resources/parrot_logo.png" id="logo" alt="parrot">
</a>
</div> <!-- "header" -->
<div id="divider"></div>
<div id="mainbody">
<div id="breadcrumb">
<a href="../../../../html/index.html">Home</a> » <a href="../../../../html/pdds.html">Parrot Design Documents (PDDs)</a> » [DRAFT] PDD 8: PMC Keys
</div>
<h1><a name="[DRAFT]_PDD_8:_PMC_Keys"
>[DRAFT] PDD 8: PMC Keys</a></h1>
<h2><a name="Abstract"
>Abstract</a></h2>
<p>This PDD aims to clear up the confusion regarding the implementation of keyed access to PMCs in Parrot.</p>
<h2><a name="Description"
>Description</a></h2>
<p>First,
let's define some terminology.
An <code>aggregate PMC</code> is one which stores or references other values as elements.
The aggregate PMC allows indexed access to element by implementing some of the <code>_keyed</code> variants of VTABLE functions.
These variants are called <code>indexing</code> operations,
as they act on a specific indexed element of an aggregate PMC.
Examples of a aggregate PMCs include <code>Hash</code>,
<code>FixedIntegerArray</code> and <code>ResizablePMCArray</code>.</p>
<p>Non-aggregates may also support <code>_keyed</code> variants of the VTABLE functions,
but they not do anything particularly clever.
For instance,
PMC types implementing Perl references will merely pass the index on to the referent.
These aren't aggregates because they don't directly store or reference elements.</p>
<p>Indexing operations take one or more aggregate <b>keys</b>.
At runtime these operations will index into the <b>aggregate</b> using the <code>key</code> and return a <b>value</b>.
Here is a well-known indexing operation in Perl 6:</p>
<pre> @a[12] = $b;</pre>
<p>The <b>key</b> here is the constant integer <code>12</code> The aggregate is the <code>Perl6Array</code> <code>@a</code>. In the process of this assignment, Parrot will have to extract the PMC in element 12 of the array, producing a <code>value</code>. <code>$b</code> is then assigned to this value.</p>
<p>Now, how does this all get implemented?</p>
<h2><a name="Implementation"
>Implementation</a></h2>
<h3><a name="The_key_structure"
>The key structure</a></h3>
<p>The key structure must bundle multiple keys. This is to allow indexing into multidimensional aggregate PMCs. These keys may be specified as integer, string, number or PMC.</p>
<p>For this reason the following structure was produced. Individual keys (e.g. a single <code>Integer</code> or <code>String</code>) are stored in a <code>Key</code> PMC. The type of the key is encoded in the private flags of the PMC as specified below. The value of the <code>Key</code> PMC is stored in the PMC's data structure internally and can be accessed using the appropriate get_* VTABLE functions.</p>
<p>For example, indexing the multidimensional array <code>@foo[$a,12;"hi"]</code> produces three PMCs; one with a PMC type, one with an integer type and one with a string type.</p>
<p>The key type is encoded in the PMC flags using 8 bits based on the following scheme (from includes/parrot/key.h):</p>
<pre> typedef enum {
KEY_integer_FLAG = PObj_private0_FLAG,
KEY_number_FLAG = PObj_private1_FLAG,
KEY_hash_iterator_FLAGS = PObj_private0_FLAG | PObj_private1_FLAG,
KEY_string_FLAG = PObj_private2_FLAG,
KEY_pmc_FLAG = PObj_private3_FLAG,
KEY_register_FLAG = PObj_private4_FLAG,
KEY_start_slice_FLAG = PObj_private5_FLAG,
KEY_end_slice_FLAG = PObj_private6_FLAG,
KEY_inf_slice_FLAG = PObj_private7_FLAG,
KEY_type_FLAGS = KEY_integer_FLAG |
KEY_number_FLAG |
KEY_string_FLAG |
KEY_pmc_FLAG |
KEY_register_FLAG |
KEY_hash_iterator_FLAGS
} KEY_flags</pre>
<p>The <code>KEY_register_FLAG</code> is used to indicate that value if the key is in a register. In this case, the Key PMC's data contains the integer number of the appropriate register in the current context.</p>
<p>Parrot must also have a way to combine multiple keys into a key that can be treated as a single unit. This is done by forming a singly linked list such that each key points at the next. Within a single Key PMC, the pointer to the next key is stored in <code>PMC_data(key)</code>. The linked list structure allows the use of partial keys in multidimensional lookups, since the next key can be generated while the aggregate PMC is being traversed.</p>
<p>These definitions, along with declarations of support routines used to manipulate keys, can be found in <em>include/parrot/key.h</em></p>
<h3><a name="Aggregate_and_non-aggregate_PMCs"
>Aggregate and non-aggregate PMCs</a></h3>
<p>We've already said that what separates the aggregate PMCs from the non-aggregates is their implementation of the <code>_keyed</code> vtable methods. So it is Hereby Decreed that the default vtable which everyone inherits from defines the <code>_keyed</code> forms to throw an exception.</p>
<dl>
<dt><a name="Todo"
>Todo</a></dt>
Need discussion on whether <code>EXCEPTION_OUT_OF_BOUNDS</code> is a good exception for this, or whether something else should be used. It's really a compiler screw-up, since code which indexes a non-aggregate shouldn't be generated.</dl>
<h3><a name="_keyed_vtable_methods"
><code>_keyed</code> vtable methods</a></h3>
<p>So what of these magical <code>_keyed</code> vtable methods? They are generated when you add the <code>keyed</code> tag to the appropriate entry in <em>src/vtable.tbl</em>. They are constructed by following <b>every</b> <code>PMC</code> argument with a second <code>PMC</code> argument which acts as the key for that argument; the name of the second <code>PMC</code> argument is formed by adding <code>_key</code> onto the end of the first <code>PMC</code> argument.</p>
<p>The reason why every PMC argument has an associated key is twofold. Firstly, it means that</p>
<pre> @a[$b] = $c</pre>
<p>and</p>
<pre> $a = @b[$c]</pre>
<p>use the same vtable method, reducing the multiplicity of methods. Secondly, a three-argument <code>assign</code> as suggested by the code above would be ambiguous - the code above uses 3 PMCs in different ways.</p>
<p>Also, operations which take an aggregate key for one of their arguments should take aggregate keys for <b>all</b> of their arguments. This is to avoid the following:</p>
<pre> void foo_keyed_i(PMC* x, PMC* x_key, INT a)
void foo_keyed_n(PMC* x, PMC* x_key, NUM a)
void foo_keyed_p(PMC* x, PMC* x_key, PMC a)
void foo_keyed_p_keyed(PMC* x, PMC* x_key, PMC* a, PMC* a_key)</pre>
<p>These are all replaced with the single entry</p>
<pre> void foo_keyed(PMC* x, PMC* a_key, PMC* a, PMC* a_key)</pre>
<p>(Think how much worse it gets when there are three or more PMCs in an entry...)</p>
<p>Yes. This means that you may need to turn some things into <code>PMC</code>s that you didn't want to. Since the alternative is mega pollution and duplication in the vtable table, and since the majority of things that you'll deal with in a real world situation are expected to be <code>PMC</code>s anyway, this shouldn't be too much of a problem.</p>
<p>So, if you have a PMC in a <code>_keyed</code> method which you don't want to index, pass in <code>NULL</code> instead of a real key. Code implementing these methods should understand <code>PMC* foo, PMC* NULL</code> as meaning the entirety of <code>foo</code> in some sense; this is trivial to understand if <code>foo</code> is non-aggregate, and implementation-defined if <code>foo</code> is aggregate. If you remember that a key PMC is really a linked list, you'll notice that after traversing down through the list, you'll reach a <code>NULL</code> which again means the entirety of whatever object you traversed to.</p>
<p>Similarly, non-<code>_keyed</code> methods on aggregates are implementation defined; for instance, a <code>set_integer</code> on a <code>PerlArray</code> may be understood as setting <code>@array.length</code>.</p>
<p>Historically, we first implemented keys as two separate keyed methods per applicable method - <code>..._index</code> and <code>..._index_s</code> for integer and string indexing respectively. However, this didn't give us the flexibility and scalability that key structures give us.</p>
<h3><a name="Input_to_the_assembler"
>Input to the assembler</a></h3>
<p>There are several different valid specifications of an aggregate key to the assembler. These are:</p>
<pre> op arg, P1[1234] # Constant integer key
op arg, P1[I1] # Integer key
op arg, P1[12.34] # Constant number key - handled as constant key
op arg, P1["foo"] # Constant string key - handled as constant key
op arg, P1[I1;I2] # Multi-level key - handled as constant key
op arg, P1[P1] # Register key</pre>
<p>(Rationale: fits programmer's expectation, easier to understand at a glance than <code>op P1, P2, P3</code>. Also, is <code>op P1, P2, P3</code> the same as <code>op P1[P2], P3</code> or <code>op P1, P2[P3]</code>, or are these three separate PMCs?)</p>
<p>In all there are four types of key. The first two are integer keys and constant integer keys which are optimisations for the common case of single level integer keys.</p>
<p>The other two are constant keys, which can handle any combination of constants and registers with any number of levels; and register keys which are represented by a single PMC register that is assumed to contain a PMC of the Key class.</p>
<h3><a name="What_the_assembler_did_next"
>What the assembler did next</a></h3>
<p>When the assembler sees an aggregate key, it "detaches" the key to form a separate argument. It then decides on the type of key. For integer keys (both constant and register) the data is encoded in the same way as an ordinary integer argument. For register keys the data is encoded as for an ordinary PMC register argument, while for constant keys a key constant is generated that encodes the list of constants and registers that make up the key and an appropriate index into the constant table is encoded as the argument.</p>
<p>Next it selects the appropriate op. Register keys have the signature <code>k</code> and constant keys have the signature <code>kc</code>. Integer register and constant keys are encoded as <code>ki</code> and <code>kic</code> respectively.</p>
<pre> set $P1["hi"], 1234
</pre>
<p>finds an op named <code>set_p_kc_i</code>. On the other hand,</p>
<pre> set $P1[$P1], 1234
</pre>
<p>produces an op named <code>set_p_k_i</code>. Likewise, this:</p>
<pre> set $P1[1], 1234
</pre>
<p>produces an op named <code>set_p_kic</code>, and this:</p>
<pre> set $P1[$I1], 1234
</pre>
<p>produces an op named <code>set_p_ki</code>.</p>
<h3><a name="Bytecode_representation"
>Bytecode representation</a></h3>
<p>The bytecode representation of these keys are as follows: constant keys are treated just like another constant, and are an index into the packfile's constant table.</p>
<p>Each key in that constant table consists of one word specifying its length in terms of number of keys. For instance, <code>["hi"]</code> has length 1; <code>["hi";P1;S1;123]</code> has length 4. Next, each key is specified using two words. The first word is a type specifier:</p>
<pre> 1 - Integer constant
2 - Number constant
4 - String constant
7 - Integer register
8 - Number register
9 - PMC register
10 - String register</pre>
<p>and the second word is either a value (for integer constants), a register number (for registers) or an index into the appropriate constant table.</p>
<p>The type values shown above are actually the <code>PARROT_ARG_*</code> values taken from <em>include/parrot/op.h</em>.</p>
<h2><a name="Version"
>Version</a></h2>
<h3><a name="Current"
>Current</a></h3>
<pre> Maintainer: Simon Cozens <simon@netthink.co.uk>
Class: Internals
PDD Number: 8
Version: 1.3
Status: Developing
Last Modified: 25 August, 2002
PDD Format: 1
Language: English</pre>
<h3><a name="History"
>History</a></h3>
<dl>
<dt><a name="Sun_Aug_25_11:14:43_GMT_2002_:_Version_1.3"
>Sun Aug 25 11:14:43 GMT 2002 : Version 1.3</a></dt>
Updated to reflect Dan's decision to change keys to use PMCs instead of a custom data structure. Also corrects documentation of multi-level keys and how they are compiled and work. tom@compton.nu.
<dt><a name="Thu_Apr_25_18:30:36_UTC_2002_:_Version_1.2"
>Thu Apr 25 18:30:36 UTC 2002 : Version 1.2</a></dt>
Renamed <code>KEY_PAIR</code> to <code>KEY_ATOM</code>, updated to reflect changeover to linked list. - steve@fink.com
<dt><a name="Fri_Mar_8_18:47:34_GMT_2002_:_Version_1.1"
>Fri Mar 8 18:47:34 GMT 2002 : Version 1.1</a></dt>
updated to reflect Dan's comments that non-aggregates also support <code>_keyed</code> variant vtable methods.</dl>
<h2><a name="References"
>References</a></h2>
<p>To come.</p>
</div> <!-- "mainbody" -->
<div id="divider"></div>
<div id="footer">
Copyright © 2002-2009, Parrot Foundation.
</div>
</div> <!-- "wrapper" -->
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
cd14cddf3b3ceaf1193157472227757a
>
files
>
136
