<commit_before># Copyright (C) 2001-2004, The Perl Foundation.
# $Id$

=head1 NAME

docs/pdds/pdd08_keys.pod - Indexing Aggregate PMCs

=head1 ABSTRACT

This PDD aims to clear up the confusion regarding the implementation of keyed
access to PMCs in Parrot.

=head1 DESCRIPTION

First, let's define some terminology. An B<aggregate PMC> is one which allows
indexed access to sub-element that it stores or references, by supporting and
implementing the C<_keyed> variants of vtable methods. These variants are
B<indexing> operations, as they act on a specific indexed element of an
aggregate PMC.

Non-aggregates also support C<_keyed> variants of the vtable methods, but they
may 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 sub-elements.

Indexing operations take one or more aggregate-B<key> atoms. At runtime, these
operations will index the key into the aggregate returning a B<value>. Here is
a well-known indexing operation in Perl 6:

    @a[12] = $b;

The key here is the constant integer C<12>, and the aggregate is the
C<PerlArray> C<@a>. In the process of this assignment, Parrot will have to
extract the PMC in element 12 of the array, producing a value. C<$b> is then
assigned to this value.

Now, how does this all get implemented?

=head1 IMPLEMENTATION

=head2 The key structure

The key structure has to have the following features: it must bundle up
multiple keys so that multidimensional aggregates can be indexed; keys may be
specified as integer, string, number or PMC.

Hence, the following structure was produced. First, the individual keys as we
think of them from a language level are each stored in a Key PMC with the key
type encoded in the private flags of the PMC and the value stored in the PMCs
cache.

So, for instance, indexing the multidimensional array C<@foo[$a;12;"hi"]>
produces three PMCs, one with a PMC type, one with an integer type and one
with a string type.

As stated, the key type is encoded in the PMC flags using 8 bits based on the
following scheme:

    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


The C<KEY_register_FLAG> is used to indicate that the C<int_val> component of
the PMC's cache contains the number of a register of the appropriate type that
itself contains the value of the key component.

The next issue is to combine these things into a single key. This is done by
using the C<data> member of the PMC to form a linked list so that each key
points to the next key. A linked list is used so that partial keys can be
easily generated as a multidimensional data structure is traversed.

These definitions, along with declarations of support routines used to
manipulate keys, can be found in F<include/parrot/key.h>

=head2 Aggregate and non-aggregate PMCs

We've already said that what separates the aggregate PMCs from the
non-aggregates is their implementation of the C<_keyed> vtable methods. So it
is Hereby Decreed that the default vtable which everyone inherits from defines
the C<_keyed> forms to throw an exception.

=over 3

=item Todo<commit_msg>[pdd] readability changes<commit_after># Copyright (C) 2001-2004, The Perl Foundation.
# $Id$

=head1 NAME

docs/pdds/pdd08_keys.pod - Indexing Aggregate PMCs

=head1 ABSTRACT

This PDD aims to clear up the confusion regarding the implementation of keyed
access to PMCs in Parrot.

=head1 DESCRIPTION

First, let's define some terminology. An C<aggregate PMC> is one which stores
or references other values as elements.  The aggregate PMC allows indexed
access to element by implementing some of the C<_keyed> variants of VTABLE
functions.  These variants are called C<indexing> operations, as they act on a
specific indexed element of an aggregate PMC.  Examples of a aggregate PMCs
include C<Hash>, C<FixedIntegerArray> and C<ResizablePMCArray>.

Non-aggregates may also support C<_keyed> 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.

Indexing operations take one or more aggregate B<keys>.  At runtime these
operations will index into the B<aggregate> using the C<key> and return a
B<value>.  Here is a well-known indexing operation in Perl 6:

    @a[12] = $b;

The B<key> here is the constant integer C<12>  The aggregate is the
C<Perl6Array> C<@a>.  In the process of this assignment, Parrot will have to
extract the PMC in element 12 of the array, producing a C<value>. C<$b> is then
assigned to this value.

Now, how does this all get implemented?

=head1 IMPLEMENTATION

=head2 The key structure

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.

For this reason the following structure was produced.  Individual keys (e.g. a
single C<Integer> or C<String>) are stored in a C<Key> PMC.  The type of the
key is encoded in the private flags of the PMC as speficied below.   The value
of the C<Key> PMC is stored in the PMC's cache (i.e. C<PMC_pmc_val(key)>,
C<PMC_int_val(key)>).

For example, indexing the multidimensional array C<@foo[$a,12;"hi"]>
produces three PMCs; one with a PMC type, one with an integer type and one with
a string type.

The key type is encoded in the PMC flags using 8 bits based on the following
scheme (from includes/parrot/key.h):

    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


The C<KEY_register_FLAG> is used to indicate that value if the key is in a
register.  In this case, C<PMC_int_val(key)> contains the number of a register
of the appropriate type that contains the value.

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 C<PMC_data(key)>.  The linked list structure allows the
use of partial keys in multidimentional lookups, since the next key can be
generated while the aggregate PMC is being traversed.

These definitions, along with declarations of support routines used to
manipulate keys, can be found in F<include/parrot/key.h>

=head2 Aggregate and non-aggregate PMCs

We've already said that what separates the aggregate PMCs from the
non-aggregates is their implementation of the C<_keyed> vtable methods. So it
is Hereby Decreed that the default vtable which everyone inherits from defines
the C<_keyed> forms to throw an exception.

=over 3

=item Todo
{'fraction_non_alphanumeric': 0.04513432835820896, 'fraction_numerical': 0.008955223880597015, 'mean_word_length': 3.286591606960082, 'pattern_counts': {'":': 0, '<': 50, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4487373', 'n_tokens_mistral': 2457, 'n_tokens_neox': 2313, 'n_words': 1099}