# HG changeset patch # User David Anderson # Date 1356743631 28800 # Node ID 7721042bdb67a6fd8ad08859c0ddbc3c1a99e80e # Parent f9c4371d59d49001bc21193054abf5d9bbabb63e Implement dependent char arrays. diff -r f9c4371d59d4 -r 7721042bdb67 src/Array.cpp --- a/src/Array.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Array.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -39,6 +39,18 @@ } ArrayMap * +ArrayMap::NewDependent(Zone *zone, Handle type) +{ + Local obj(zone, zone->allocateMap(MapKind_DependentArray, sizeof(ArrayMap), MapKind_MetaArray)); + if (!obj) + return NULL; + + Local map(zone, ArrayMap::cast(obj)); + map->type_ = type; + return map; +} + +ArrayMap * ArrayMap::Attach(Zone *zone, Handle type) { if (type->newMap()) @@ -339,3 +351,49 @@ return dest; } + +Array * +DependentArray::New(Zone *zone, Handle source, Handle map, unsigned index) +{ + Local sourcetype(zone, source->type()); + + // Right now we only support char arrays, to avoid nasty deep cloning + // and to maybe cut off this feature as far as we can. + assert(sourcetype->isCharArray()); + assert(map->type()->isCharArray()); + + // We allow taking 0-length dependent strings. It's safe because any reads + // or writes will fail. + assert(index <= source->length()); + + unsigned newlen = source->length() - index; + unsigned eltsize = SizeForElement(sourcetype); + + if (!sourcetype->isFixedLength()) { + // Simple case, just copy the array. + Local map(zone, sourcetype->newMap()); + + Local dest(zone, Array::NewRaw(zone, map, newlen, Heap::Tenure_Default)); + if (!dest) + return NULL; + + memcpy(dest->bytes(), + (Address)source->bytes() + (index * eltsize), + newlen * eltsize); + return dest; + } + + Local array(zone, DependentArray::cast(zone->allocate(map, sizeof(DependentArray), Heap::Tenure_Default))); + if (!array) + return NULL; + + // :GC: This is currently not safe for moving GC! Although we will mark + // the object owning the interior pointer, the interior pointer could be + // moved later. We will eventually need some way of dealing with this. + Address elements = Address(source->bytes()) + (index * eltsize); + + array->root_ = source; + array->length_ = newlen; + array->elements_ = elements - ByteArray::offsetToElements(); + return array; +} diff -r f9c4371d59d4 -r 7721042bdb67 src/Array.h --- a/src/Array.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Array.h Fri Dec 28 17:13:51 2012 -0800 @@ -32,6 +32,7 @@ { friend class ArrayMap; + protected: // Note: we do not write barrier |elements_|, since it can be set to // arbitrary pointers. uint32 length_; @@ -40,7 +41,7 @@ Object *objelements_; }; - private: + protected: void updateLengthAndElements(Zone *zone, unsigned length, Object *array) { length_ = length; write(zone, &objelements_, array); @@ -134,19 +135,50 @@ // End GC Descriptor. static Array *cast(Object *obj) { - assert(!obj || obj->is(MapKind_Array)); + assert(!obj || + obj->is(MapKind_Array) || + obj->is(MapKind_DependentArray)); return reinterpret_cast(obj); } }; +class DependentArray : public Array +{ + Barriered root_; + + public: + static Array *New(Zone *zone, Handle source, Handle map, unsigned index); + + // GC Descriptor. + static inline size_t offsetOfRoot() { + return offsetof(DependentArray, root_); + } + // End GC Descriptor. + + static DependentArray *cast(Object *obj) { + assert(!obj || obj->is(MapKind_DependentArray)); + return reinterpret_cast(obj); + } +}; + class ArrayMap : public Map { Barriered type_; public: + // The way array maps work is kind of clownshoes. In the future, these + // should be created immediately (or lazily) on the Type directly, and not + // manually created via ::Attach. :TODO: do this when we begin caching + // array types. static ArrayMap *New(Zone *zone, Handle type); static ArrayMap *Attach(Zone *zone, Handle type); + // DependentArray maps are never attached, and are just free-floating, + // rooted ultimately by the bytecode. A :TODO: that we might need to + // cache these, or attach them somewhere saner like ArrayType, which + // itself will eventually be cached. + static ArrayMap *NewDependent(Zone *zone, Handle type); + ArrayType *type() { return type_; } @@ -169,6 +201,7 @@ assert(!type()->contained()->isTraceable()); assert(type()->hasInlineElements() || type()->isExternalArray() || + is(MapKind_DependentArray) || !length() || ByteArray::cast((Object *)elements_)); diff -r f9c4371d59d4 -r 7721042bdb67 src/Interpreter.cpp --- a/src/Interpreter.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Interpreter.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -986,6 +986,26 @@ break; } +case OP_DEPARRAY: +{ + Local map(zone, ArrayMap::cast(top.fp->code()->object(READ_UINT32(top.pc)))); + Local array(zone, Array::cast(top.sp[-2].obj)); + int index = top.sp[-1].i32; + + // We allow taking 0-length dependent arrays. + if (index < 0 || unsigned(index) > array->length()) { + zone->reportError(Message_ArrayIndexOutOfBounds, index, array->length()); + goto error; + } + + top.sp[-2].obj = DependentArray::New(zone, array, map, index); + if (!top.sp[-2].obj) + goto error; + + top.sp--; + break; +} + default: assert(false); return false; diff -r f9c4371d59d4 -r 7721042bdb67 src/ObjectVisitor.h --- a/src/ObjectVisitor.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/ObjectVisitor.h Fri Dec 28 17:13:51 2012 -0800 @@ -148,6 +148,11 @@ return array->objSize(map); } + size_t iterateDependentArray(Object *array) { + visitField(array, DependentArray::offsetOfRoot()); + return sizeof(DependentArray); + } + size_t iterateBox(Box *obj) { visitField(obj, Box::offsetOfType()); if (obj->type()->isTraceable()) @@ -248,7 +253,10 @@ return iterateString(obj); case MapKind_Array: - return Align(iterateArray(Array::cast(obj), ArrayMap::cast(map)), kObjectAlignment); + return iterateArray(Array::cast(obj), ArrayMap::cast(map)); + + case MapKind_DependentArray: + return iterateDependentArray(obj); case MapKind_Box: return iterateBox(Box::cast(obj)); @@ -340,7 +348,10 @@ return sizeof(Native); case MapKind_Array: - return Align(Array::cast(obj)->objSize(ArrayMap::cast(map)), kObjectAlignment); + return Array::cast(obj)->objSize(ArrayMap::cast(map)); + + case MapKind_DependentArray: + return sizeof(DependentArray), kObjectAlignment; case MapKind_Box: return sizeof(Box); diff -r f9c4371d59d4 -r 7721042bdb67 src/Objects.h --- a/src/Objects.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Objects.h Fri Dec 28 17:13:51 2012 -0800 @@ -60,6 +60,7 @@ // These do not have canonical maps. MapKind_Array, + MapKind_DependentArray, MapKind_Struct, // These represent special Map subclasses that require special tracing. diff -r f9c4371d59d4 -r 7721042bdb67 src/Opcodes.cpp --- a/src/Opcodes.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Opcodes.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -210,6 +210,7 @@ case OP_PUBLIC: case OP_LEAVELOOP: case OP_DUPARRAY: + case OP_DEPARRAY: break; case OP_ENTERLOOP: diff -r f9c4371d59d4 -r 7721042bdb67 src/Opcodes.tbl --- a/src/Opcodes.tbl Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Opcodes.tbl Fri Dec 28 17:13:51 2012 -0800 @@ -259,4 +259,10 @@ // // If the second byte to ENTERLOOP is 0, then no LIFO region is needed. OPDEF(OP_ENTERLOOP, "enterloop", 2, 0, 0) -OPDEF(OP_LEAVELOOP, "leaveloop", 1, 0, 0) \ No newline at end of file +OPDEF(OP_LEAVELOOP, "leaveloop", 1, 0, 0) + +// Create a new dependent array. The type to use is encoded as an index. +// index = POP() +// base = POP() +// PUSH(array) +OPDEF(OP_DEPARRAY, "deparray", 5, 2, 1) \ No newline at end of file diff -r f9c4371d59d4 -r 7721042bdb67 src/TypeManager.cpp --- a/src/TypeManager.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/TypeManager.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -2,19 +2,19 @@ * * Copyright (C) 2012 David Anderson * - * This file is part of JITCraft. + * This file is part of SourcePawn. * - * JITCraft is free software: you can redistribute it and/or modify it under + * SourcePawn is free software: you can redistribute it and/or modify it under * the terms of the GNU General Public License as published by the Free * Software Foundation, either version 3 of the License, or (at your option) * any later version. * - * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY + * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. * * You should have received a copy of the GNU General Public License along with - * JITCraft. If not, see http://www.gnu.org/licenses/. + * SourcePawn. If not, see http://www.gnu.org/licenses/. */ #include #include "Types.h" diff -r f9c4371d59d4 -r 7721042bdb67 src/Types.h --- a/src/Types.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/Types.h Fri Dec 28 17:13:51 2012 -0800 @@ -297,6 +297,12 @@ return temp; } + bool isDynamic() { + return elements_ == DYNAMIC_ARRAY_SIZE; + } + bool isExtensible() { + return isDynamic() && !(quals_ & TypeQual_Const); + } Type *contained() { return contained_; } @@ -435,6 +441,10 @@ assert(isNative()); return variadicNative_; } + void setVariadic() { + assert(isNative()); + variadicNative_ = true; + } void setReturnType(Handle returnType) { assert(!returnType_); returnType_ = returnType; diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/AST.h --- a/src/compiler/AST.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/AST.h Fri Dec 28 17:13:51 2012 -0800 @@ -708,12 +708,14 @@ { StatementList *statements_; Scope *scope_; + TokenKind type_; public: - BlockStatement(const SourcePosition &pos, StatementList *statements) + BlockStatement(const SourcePosition &pos, StatementList *statements, TokenKind kind) : Statement(pos), statements_(statements), - scope_(NULL) + scope_(NULL), + type_(kind) { } @@ -728,6 +730,9 @@ void setScope(Scope *scope) { scope_ = scope; } + TokenKind type() const { + return type_; + } }; typedef PoolList ParameterList; diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/BytecodeEmitter.h --- a/src/compiler/BytecodeEmitter.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/BytecodeEmitter.h Fri Dec 28 17:13:51 2012 -0800 @@ -494,6 +494,13 @@ writeObject(map); markOop(1); } + void deparray(ArrayMap *map) { + recordOops(); + ensure(OP_DEPARRAY_LENGTH); + writeOp(OP_DEPARRAY); + writeObject(map); + markOop(1); + } void savelifo(unsigned slot) { ensure(OP_SAVELIFO_LENGTH); writeOp(OP_SAVELIFO); diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/HIR.cpp --- a/src/compiler/HIR.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/HIR.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -52,6 +52,7 @@ void visitIndex(HIndex *index); void visitPostIncDec(HPostIncDec *hir); void visitToRef(HToRef *hir); + void visitNewDependentArray(HNewDependentArray *hir); private: Zone *zone_; @@ -438,6 +439,10 @@ unary->in()->accept(this); switch (unary->token()) { + case TOK_TILDE: + __ bitnot(); + break; + case TOK_MINUS: if (unary->type()->isFloat()) __ neg_f(); @@ -474,6 +479,27 @@ } void +HIRTranslator::visitNewDependentArray(HNewDependentArray *hir) +{ + hir->base()->accept(this); + hir->index()->accept(this); + + Local type(zone_, ArrayType::cast(hir->type())); + + // Attach an actual map to the dependent type, in case it's a new + // type. + if (!ArrayMap::Attach(zone_, type)) + return; + + // The dependent map is used for the opcode, but is not attached. + Local map(zone_, ArrayMap::NewDependent(zone_, type)); + if (!map) + return; + + __ deparray(map); +} + +void ke::EmitHIR(Zone *zone, BytecodeEmitter &emitter, HIR *hir) { HIRTranslator translator(zone, emitter); diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/HIR.h --- a/src/compiler/HIR.h Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/HIR.h Fri Dec 28 17:13:51 2012 -0800 @@ -34,6 +34,7 @@ _(Array) \ _(Store) \ _(ToRef) \ + _(NewDependentArray) \ /* Special LValue types */ \ _(Index) \ _(Local) \ @@ -306,6 +307,13 @@ void load(BytecodeEmitter &emitter_); bool ref(BytecodeEmitter &emitter_); + HIR *base() const { + return left_; + } + HIR *index() const { + return right_; + } + private: HIR *left_; HIR *right_; @@ -515,6 +523,30 @@ HIR *in_; }; +class HNewDependentArray : public HIR +{ + public: + HNewDependentArray(AstNode *node, Type *type, HIR *base, HIR *index) + : HIR(node, type), + base_(base), + index_(index) + { + } + + DEFINE_HIR(NewDependentArray); + + HIR *base() const { + return base_; + } + HIR *index() const { + return index_; + } + + private: + HIR *base_; + HIR *index_; +}; + #undef DEFINE_HIR void EmitHIR(Zone *zone, BytecodeEmitter &emitter, HIR *hir); diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/NameBinding.cpp --- a/src/compiler/NameBinding.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/NameBinding.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -335,12 +335,26 @@ node->setScope(env.scope()); } void visitBlockStatement(BlockStatement *node) { - SymbolEnv env(&env_); + if (node->type() == TOK_NEW) { + // Don't create a symbol environment for this block, since it + // was created solely to house multiple variable decls. + for (size_t i = 0; i < node->statements()->length(); i++) + node->statements()->at(i)->accept(this); + } else { + assert(node->type() == TOK_LBRACE); + + SymbolEnv env(&env_); - for (size_t i = 0; i < node->statements()->length(); i++) - node->statements()->at(i)->accept(this); + for (size_t i = 0; i < node->statements()->length(); i++) + node->statements()->at(i)->accept(this); + + if (node->type() == TOK_NEW) { + assert(!env.scope()); + return; + } - node->setScope(env.scope()); + node->setScope(env.scope()); + } } void visitIntegerLiteral(IntegerLiteral *node) { } @@ -856,6 +870,9 @@ fun->setReturnType(type); } + if (sig.variadic()) + fun->setVariadic(); + Local params(zone_, FixedArray::New(zone_, sig.parameters()->length(), Heap::Tenure_Old)); if (!params) return false; diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/Parser.cpp --- a/src/compiler/Parser.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/Parser.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -920,7 +920,7 @@ } // Create a fake-o block with no scope to create a statement list. - return new (pool_) BlockStatement(decl->pos(), statements); + return new (pool_) BlockStatement(decl->pos(), statements, TOK_NEW); } Statement * @@ -970,7 +970,7 @@ return NULL; } - BlockStatement *block = new (pool_) BlockStatement(pos, statements); + BlockStatement *block = new (pool_) BlockStatement(pos, statements, TOK_LBRACE); return block; } diff -r f9c4371d59d4 -r 7721042bdb67 src/compiler/SemanticAnalysis.cpp --- a/src/compiler/SemanticAnalysis.cpp Thu Dec 27 21:07:03 2012 -0800 +++ b/src/compiler/SemanticAnalysis.cpp Fri Dec 28 17:13:51 2012 -0800 @@ -694,13 +694,66 @@ } else { Local actual(zone_, fun->parameterAt(i)); - if (expression->isIndexExpression()) { - // Temporarily disabled. - assert(!actual->isArray()); + + if (expression->isIndexExpression() && arg->isIndex()) { + // If the expression is the form x[y], and this produced a + // normal array indexing operation, then we apply some + // special rules. + if (actual->isReference()) { + // Disabled, since this doesn't have easily definable or + // sensible semantics with SP2 arrays, but we don't want + // to silently break SP1 semantics. cc_.reportError(expression->pos(), Message_CannotComputeIndexRef); return; } + + // As a special rule to account for SP1 semantics, we allow x[y] + // to automatically compute a sliced, read-only array view if + // the desired type is an array of one more dimension than x[y] + // would return. + // + // As an additional restriction, this is only allowed for + // one-level char arrays, to minimize potential issues until + // we determine whether more compatibility is needed. + // + // Internally, for sanity, the dependent array operation does + // not necessarily create a dependent array. For extensible + // arrays, we instead create a duplicate arrary of just the + // sliced portion, rather than deal with the complexity of the + // source array being resized. + // + // Note that we don't really know whether a dependent array + // will be dependent at compile-time, so the dependent type's + // just inherits from the source. + if (actual->isArray()) { + HIndex *index = arg->toIndex(); + Local basetype(zone_, ArrayType::cast(index->base()->type())); + Local atype(zone_, ArrayType::cast(actual)); + + if (atype->isCharArray() && basetype->isCharArray()) { + // There is no possible way this will type check, so + // it's safe to just try something completely + // different. + Local slicetype(zone_); + if (basetype->isFixedLength()) { + // If the base type is fixed length, we need to + // compute a new dynamic array type based on the + // fixed array's contents and qualifiers. + Local contained(zone_, basetype->contained()); + slicetype = zone_->types()->newArray(contained, ArrayType::DYNAMIC_ARRAY_SIZE); + if (!slicetype) + return; + slicetype = zone_->types()->qualify(slicetype, basetype->quals()); + if (!slicetype) + return; + } else { + slicetype = basetype; + } + arg = new (pool_) HNewDependentArray(expression, slicetype, index->base(), index->index()); + given = arg->type(); + } + } } if (actual->isReference()) { @@ -830,10 +883,17 @@ Type * SemanticAnalysis::coercionType(TokenKind token, HIR *left, HIR *right) { - Handle l = left->type(); - Handle r = right->type(); + Local l(zone_, left->type()); + Local r(zone_, right->type()); - if (token >= TOK_PLUS && token <= TOK_SLASH) { + if (l->isPod()) + l = l->unqualified(); + if (r->isPod()) + r = r->unqualified(); + + if ((token >= TOK_PLUS && token <= TOK_SLASH) || + (token >= TOK_EQUALS && token <= TOK_GE)) + { // We allow: [float|int32] + [float|int32] if (l->isFloat() && r->isInt32()) return l; @@ -841,6 +901,11 @@ return r; if (l->isInt32() && r->isInt32()) return l; + + if (l->isChar() && r->isInt32()) + return r; + if (l->isInt32() && r->isChar()) + return l; } // :TODO: remove @@ -1097,23 +1162,36 @@ return; switch (node->token()) { + case TOK_TILDE: + { + if (!hir->type()->isInt32() && !hir->type()->isEnum()) { + char name[255]; + cc_.reportError(node->pos(), Message_InvalidUnaryType, + "~", + GetTypeName(hir->type(), name, sizeof(name))); + } + Local type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32)); + hir_ = new (pool_) HUnary(node, hir->type(), TOK_TILDE, hir); + return; + } + case TOK_MINUS: { - if (hir->type()->isInt32() || hir->type()->isEnum()) { - Local type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32)); - hir_ = new (pool_) HUnary(node, type, TOK_MINUS, hir); - return; - } - if (hir->type()->isFloat()) { - hir_ = new (pool_) HUnary(node, hir->type(), TOK_MINUS, hir); - return; - } + if (hir->type()->isInt32() || hir->type()->isEnum()) { + Local type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32)); + hir_ = new (pool_) HUnary(node, type, TOK_MINUS, hir); + return; + } + if (hir->type()->isFloat()) { + hir_ = new (pool_) HUnary(node, hir->type(), TOK_MINUS, hir); + return; + } - char name[255]; - cc_.reportError(node->pos(), Message_InvalidUnaryType, - "-", - GetTypeName(hir->type(), name, sizeof(name))); - break; + char name[255]; + cc_.reportError(node->pos(), Message_InvalidUnaryType, + "-", + GetTypeName(hir->type(), name, sizeof(name))); + break; } default: @@ -1195,8 +1273,13 @@ BinaryExpression *bin = expr->toBinaryExpression(); if (token == TOK_AND || token == TOK_OR) { - assert(false); - //visitForLogicTest(expr, trueBranch, falseBranch, fallthrough); + Label next; + if (token == TOK_AND) + visitForTest(bin->left(), &next, falseBranch, &next); + else + visitForTest(bin->left(), trueBranch, &next, &next); + __ bind(&next); + visitForTest(bin->right(), trueBranch, falseBranch, fallthrough); return; } diff -r f9c4371d59d4 -r 7721042bdb67 tests/basic/dependent-strings.out --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/basic/dependent-strings.out Fri Dec 28 17:13:51 2012 -0800 @@ -0,0 +1,2 @@ +Pab +ake diff -r f9c4371d59d4 -r 7721042bdb67 tests/basic/dependent-strings.sp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/basic/dependent-strings.sp Fri Dec 28 17:13:51 2012 -0800 @@ -0,0 +1,17 @@ +native PrintString(const char:text[]); + +f(char:str[]) +{ + str[0] = 80; +} + +public main() +{ + new char:fixed[100] = "crab\n"; + new char:dynamo[] = "cake\n"; + f(fixed[1]); + f(dynamo[1]); + PrintString(fixed[1]); + PrintString(dynamo[1]); +} +