src/Structures.h
author David Anderson <dvander@alliedmods.net>
Sat Nov 17 18:41:01 2012 -0800 (2012-11-17)
changeset 195 c1ba166f3fc4
parent 164 3bf7c007883d
child 234 26e3035cdffc
permissions -rw-r--r--
Massive SemA/BC refactoring to support better type systems. Read on for more.

The previous compiler had a simple pipeline, best outlined as:
(1) Parsing and name binding -> AST
(2) Storage allocation -> AST
(3) Semantic Analysis (SemA) -> AST
(4) Bytecode Compilation (BC) -> Code

This pipeline, unfortunately, had two problems. First, name binding cannot be performed in one pass if we wish to have multi-file support in the form of modules. Name binding must be two-pass.

Second, because SemA was only capable of annotating AST nodes with a single type, most coercion work had to be duplicated in the BC phase, as coercion was not explicit in the SemA output. This made introducing new type rules extremely difficult, and all but precluded concepts like operator overloading (or overloading at all).

This patch rewrites most of Keima's backend. Of interest are the following changes:
(1) CompileContext has been refactored around future multi-file support.
(2) Parsing no longer performs any name binding.
(3) The grammar for type-and-name has been changed from:
(Label | Identifier)? Identifier
to:
Type? Identifier
where:
Type ::= OldType | NewType
OldType ::= Label
NewType ::= Identifier (. NewType)*


Although we do not implement the full production for Type yet, this
distinction is important. A type identifier is now affixed to the AST
as an Expression (right now, always a NameProxy), so it can fully
participate in name binding.

(4) Immediately after parsing, the AST goes through a NamePopulation phase.
This phase creates Scope objects for every scope which declares a name,
and if those names are declaring types or functions, a Symbol is created
and entered into the scope. Symbols entirely replace the old BoundName
classes.

(5) After NamePopulation comes NameBinding. This phase performs three steps:
(a) Links Scope objects together, to form a tree.
(b) Binds any free name to an existing name in the scope chain.
(c) Creates and registers any Symbols for names which have not yet been
added to the scope (for example, local variables).

In accordance, all "allocation" and "binding" concepts have been removed
from Scopes, which are now lightweight container classes.

(6) SemA now generates bytecode for each statement in the AST. Expression
compilation is performed via a separate mechanism called HIR (High-level
Intermediate Representation). To analyze an expression, SemA will walk
the AST, and produce a HIR object for each node. HIR is typed, and SemA
may insert coercion nodes, or even expand an AST node into multiple HIR
nodes. The result of evaluating an expression in SemA is therefore the
the root of a HIR tree, which SemA then sends to the HIRTranslator, which
performs bytecode generation.

As before, SemA still performs full semantic analysis. However, not it
also produces each function's bytecode.

This split allows us to decompose potentially complex semantics into
a more fine-grained, AST-like structure, which can have very simple
code-generation logic. For example, (1.0 + 5) might look like:

HAdd(HFloat(1.0), HConvert(HInteger(5), <Float>))

As part of this decomposition, many opcodes have been removed. Rather than
using typed jumps, we now expand jumps into longer tests. For example:
jge.f <label>
becomes:
ge.f
cvt.f2b
jt <label>

This simplifies the pipeline, and JITs should be able to melt the added
work away.

HIR is not used at a statement level, and HIR does not have any concept
of control-flow.

(7) The old BytecodeCompiler has been removed, as its work is now split
between SemA and HIRTranslator.


In addition, some minor refactorings have taken place:

(1) Opcodes.tbl no longer hardcodes numbers (aaah).
(2) Type has been split into smaller, typed structs.
(3) BytecodeEmitter no longer relies on Pools or RootScopes.
(4) SemA is now responsible for variable/storage allocation.
(5) Native table are now global, rather than per-module. As such, native
declarations now result in a Native object (which still requires a
CALLNATIVE opcode), which is an index into the global table. Natives
must be bound globally. This is in preparation for module support.
(6) Publics are no longer tracked, but rather registered via a global
callback upon module load. This callback can be set by embedders. This
is in preparation for multi-file support.
(7) The BytecodeEmitter now performs Symbol allocations itself, and it
also generates Code objects itself, which removes a good deal of
complexity.

Finally, a test harness has been added. This harness is a python script which finds *.test files, recursively, in the tests folder. For each file it runs the corresponding .sp. The contents of the .test file must match stdout+stderr.
dvander@146
     1
/* vim: set ts=4 sw=4 tw=99 et:
dvander@85
     2
 *
dvander@85
     3
 * Copyright (C) 2012 David Anderson
dvander@85
     4
 *
dvander@146
     5
 * This file is part of SourcePawn.
dvander@85
     6
 *
dvander@146
     7
 * SourcePawn is free software: you can redistribute it and/or modify it under
dvander@85
     8
 * the terms of the GNU General Public License as published by the Free
dvander@85
     9
 * Software Foundation, either version 3 of the License, or (at your option)
dvander@85
    10
 * any later version.
dvander@85
    11
 * 
dvander@146
    12
 * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@85
    13
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@85
    14
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@85
    15
 *
dvander@85
    16
 * You should have received a copy of the GNU General Public License along with
dvander@146
    17
 * SourcePawn. If not, see http://www.gnu.org/licenses/.
dvander@85
    18
 */
dvander@85
    19
#ifndef _include_jc_structure_h_
dvander@85
    20
#define _include_jc_structure_h_
dvander@85
    21
dvander@85
    22
#include "Objects.h"
dvander@85
    23
#include "Handles.h"
dvander@85
    24
#include "Vector.h"
dvander@147
    25
#include "Heap.h"
dvander@85
    26
dvander@85
    27
namespace ke {
dvander@85
    28
dvander@85
    29
class Type;
dvander@85
    30
class String;
dvander@85
    31
class FixedArray;
dvander@195
    32
class StructType;
dvander@85
    33
dvander@85
    34
// When describing composite structures, the GC must be able to trace interior
dvander@85
    35
// references to Objects. To make this possible, maps that describe composite
dvander@85
    36
// structures must provide a list of offsets into their objects that are
dvander@85
    37
// traceable. StructureBufferBuilder assists with this.
dvander@85
    38
class StructureBufferBuilder
dvander@85
    39
{
dvander@85
    40
  public:
dvander@85
    41
    StructureBufferBuilder();
dvander@85
    42
dvander@85
    43
    bool add(Handle<Type> type, unsigned *offset);
dvander@85
    44
dvander@85
    45
    unsigned structureSize() const {
dvander@85
    46
        return size_;
dvander@85
    47
    }
dvander@85
    48
    unsigned traceableOffsetCount() const {
dvander@85
    49
        return offsets_.length();
dvander@85
    50
    }
dvander@147
    51
    const unsigned *offsets() const {
dvander@85
    52
        return offsets_.buffer();
dvander@85
    53
    }
dvander@85
    54
dvander@85
    55
  private:
dvander@85
    56
    Vector<unsigned> offsets_;
dvander@85
    57
    unsigned size_;
dvander@85
    58
};
dvander@85
    59
dvander@146
    60
// Represents a property descriptor for a structure field.
dvander@146
    61
class Descriptor : public Object
dvander@146
    62
{
dvander@146
    63
    // The name of the field.
dvander@146
    64
    Barriered<String> name_;
dvander@146
    65
dvander@146
    66
    // The type of the field.
dvander@146
    67
    Barriered<Type> type_;
dvander@146
    68
dvander@146
    69
    // The offset into an object at which this field can be accessed.
dvander@146
    70
    unsigned offset_;
dvander@146
    71
dvander@146
    72
  public:
dvander@195
    73
    static Descriptor *New(Zone *zone, Handle<String> name, Handle<Type> type);
dvander@146
    74
dvander@146
    75
    String *name() {
dvander@146
    76
        return name_;
dvander@146
    77
    }
dvander@146
    78
    Type *type() {
dvander@146
    79
        return type_;
dvander@146
    80
    }
dvander@146
    81
    unsigned offset() {
dvander@195
    82
        assert(offset_ != unsigned(-1));
dvander@146
    83
        return offset_;
dvander@146
    84
    }
dvander@195
    85
    void setOffset(unsigned offset) {
dvander@195
    86
        assert(offset_ == unsigned(-1));
dvander@195
    87
        offset_ = offset;
dvander@195
    88
    }
dvander@146
    89
dvander@146
    90
    // Begin GC descriptor.
dvander@146
    91
    static inline size_t offsetOfName() {
dvander@146
    92
        return OFFSETOF(Descriptor, name_);
dvander@146
    93
    }
dvander@146
    94
    static inline size_t offsetOfType() {
dvander@146
    95
        return OFFSETOF(Descriptor, type_);
dvander@146
    96
    }
dvander@146
    97
    // End GC descriptor.
dvander@146
    98
    
dvander@146
    99
    static inline Descriptor *cast(Object *obj) {
dvander@146
   100
        assert(!obj || obj->is(MapKind_Descriptor));
dvander@146
   101
        return reinterpret_cast<Descriptor *>(obj);
dvander@146
   102
    }
dvander@146
   103
};
dvander@146
   104
dvander@147
   105
class StructMap : public Map
dvander@147
   106
{
dvander@147
   107
    unsigned structureSize_;
dvander@147
   108
    unsigned traceOffsetCount_;
dvander@195
   109
    Barriered<StructType> type_;
dvander@147
   110
dvander@153
   111
    // List of descriptors which must be allocated upon initialization.
dvander@153
   112
    Barriered<FixedArray> composed_;
dvander@153
   113
dvander@147
   114
  public:
dvander@195
   115
    static StructMap *New(Zone *zone, const StructureBufferBuilder &builder, Handle<StructType> type);
dvander@147
   116
dvander@147
   117
    unsigned structureSize() {
dvander@147
   118
        return structureSize_;
dvander@147
   119
    }
dvander@147
   120
    unsigned traceOffsetCount() {
dvander@147
   121
        return traceOffsetCount_;
dvander@147
   122
    }
dvander@147
   123
    const unsigned *traceOffsets() {
dvander@147
   124
        return reinterpret_cast<unsigned *>(this + 1);
dvander@147
   125
    }
dvander@161
   126
    size_t objSize() {
dvander@161
   127
        return sizeof(StructMap) + sizeof(unsigned) * traceOffsetCount();
dvander@147
   128
    }
dvander@195
   129
    StructType *type() {
dvander@147
   130
        return type_;
dvander@147
   131
    }
dvander@153
   132
    FixedArray *composed() {
dvander@153
   133
        return composed_;
dvander@153
   134
    }
dvander@153
   135
dvander@195
   136
    void setType(StructType *type) {
dvander@147
   137
        assert(!type_);
dvander@147
   138
        type_ = type;
dvander@147
   139
    }
dvander@147
   140
dvander@147
   141
    // Begin GC descriptors.
dvander@147
   142
    static inline size_t offsetOfType() {
dvander@147
   143
        return OFFSETOF(StructMap, type_);
dvander@147
   144
    }
dvander@153
   145
    static inline size_t offsetOfComposed() {
dvander@153
   146
        return OFFSETOF(StructMap, composed_);
dvander@153
   147
    }
dvander@147
   148
    // End GC descriptors.
dvander@147
   149
dvander@147
   150
    static inline StructMap *cast(Object *obj) {
dvander@147
   151
        assert(!obj || obj->is(MapKind_MetaStruct));
dvander@147
   152
        return reinterpret_cast<StructMap *>(obj);
dvander@147
   153
    }
dvander@147
   154
};
dvander@147
   155
dvander@147
   156
class Struct : public Object
dvander@147
   157
{
dvander@147
   158
  public:
dvander@147
   159
    static Struct *New(Zone *zone, Handle<StructMap> map, Heap::Tenure tenure = Heap::Tenure_Default);
dvander@147
   160
dvander@161
   161
    size_t objSize() {
dvander@161
   162
        return sizeof(Struct) + map()->structureSize();
dvander@147
   163
    }
dvander@147
   164
    StructMap *map() {
dvander@147
   165
        return StructMap::cast(Object::map());
dvander@147
   166
    }
dvander@147
   167
dvander@164
   168
    void *ref(Descriptor *desc) {
dvander@164
   169
        return reinterpret_cast<Address>(this) + offsetOfSlotOffset(desc->offset());
dvander@164
   170
    }
dvander@164
   171
dvander@152
   172
    // This must NOT be used with any Object * type!
dvander@152
   173
    template <typename T> T get(Descriptor *desc) {
dvander@164
   174
        return *reinterpret_cast<T *>(ref(desc));
dvander@152
   175
    }
dvander@152
   176
dvander@152
   177
    template <typename T> void set(Descriptor *desc, const T &t) {
dvander@164
   178
        *reinterpret_cast<T *>(ref(desc)) = t;
dvander@152
   179
    }
dvander@152
   180
dvander@152
   181
    void set(Zone *zone, Descriptor *desc, Object *obj) {
dvander@152
   182
        // :TODO: write barrier
dvander@152
   183
        *reinterpret_cast<Object **>(
dvander@152
   184
            reinterpret_cast<Address>(this) +
dvander@152
   185
            offsetOfSlotOffset(desc->offset())) = obj;
dvander@152
   186
    }
dvander@152
   187
dvander@147
   188
    static inline size_t offsetOfSlotOffset(unsigned offset) {
dvander@147
   189
        return sizeof(Struct) + offset;
dvander@147
   190
    }
dvander@147
   191
dvander@147
   192
    static inline Struct *cast(Object *obj) {
dvander@147
   193
        assert(!obj || obj->is(MapKind_Struct));
dvander@147
   194
        return reinterpret_cast<Struct *>(obj);
dvander@147
   195
    }
dvander@147
   196
};
dvander@147
   197
dvander@85
   198
}
dvander@85
   199
dvander@85
   200
#endif // _include_jc_structure_h_
dvander@146
   201