asherkin@263: /* vim: set ts=4 sw=4 tw=99 et:
asherkin@263:  *
asherkin@263:  * Copyright (C) 2012 David Anderson
asherkin@263:  *
asherkin@263:  * This file is part of SourcePawn.
asherkin@263:  *
asherkin@263:  * SourcePawn is free software: you can redistribute it and/or modify it under
asherkin@263:  * the terms of the GNU General Public License as published by the Free
asherkin@263:  * Software Foundation, either version 3 of the License, or (at your option)
asherkin@263:  * any later version.
asherkin@263:  * 
asherkin@263:  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
asherkin@263:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
asherkin@263:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
asherkin@263:  *
asherkin@263:  * You should have received a copy of the GNU General Public License along with
asherkin@263:  * SourcePawn. If not, see http://www.gnu.org/licenses/.
asherkin@263:  */
asherkin@263: #include <string.h>
asherkin@263: #include "Array.h"
asherkin@263: #include "FixedArray.h"
asherkin@263: #include "Heap.h"
asherkin@263: #include "Zone.h"
asherkin@263: #include "Structures.h"
asherkin@263: #include "Heap-inl.h"
asherkin@263: 
asherkin@263: using namespace ke;
asherkin@263: 
asherkin@263: ArrayMap *
asherkin@263: ArrayMap::New(Zone *zone, Handle<ArrayType> type)
asherkin@263: {
asherkin@263:     Local<Map> obj(zone, zone->allocateMap(MapKind_Array, sizeof(ArrayMap), MapKind_MetaArray));
asherkin@263:     if (!obj)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     Local<ArrayMap> map(zone, ArrayMap::cast(obj));
asherkin@263:     map->type_ = type;
asherkin@263:     return map;
asherkin@263: }
asherkin@263: 
asherkin@263: ArrayMap *
asherkin@263: ArrayMap::NewDependent(Zone *zone, Handle<ArrayType> type)
asherkin@263: {
asherkin@263:     Local<Map> obj(zone, zone->allocateMap(MapKind_DependentArray, sizeof(ArrayMap), MapKind_MetaArray));
asherkin@263:     if (!obj)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     Local<ArrayMap> map(zone, ArrayMap::cast(obj));
asherkin@263:     map->type_ = type;
asherkin@263:     return map;
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewRaw(Zone *zone, Handle<ArrayMap> map, unsigned nelements, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     assert(!map->type()->isFixedLength() || nelements == map->type()->fixedLength());
asherkin@263: 
asherkin@263:     if (nelements > (INT_MAX / SizeForElement(map->type()))) {
asherkin@263:         zone->reportError(Message_ArraySizeTooBig);
asherkin@263:         return NULL;
asherkin@263:     }
asherkin@263: 
asherkin@263:     size_t bytes = sizeof(Array);
asherkin@263:     if (map->type()->hasInlineElements())
asherkin@263:         bytes += SizeForElement(map->type()) * nelements;
asherkin@263: 
asherkin@263:     Local<Array> array(zone, Array::cast(zone->allocate(map, bytes, tenure)));
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     array->length_ = 0;
asherkin@263:     array->elements_ = NULL;
asherkin@263: 
asherkin@263:     if (map->type()->hasInlineElements()) {
asherkin@263:         // This must be a fixed array containing no traceables.
asherkin@263:         assert(nelements > 0);
asherkin@263:         assert(map->type()->isFixedLength());
asherkin@263:         assert(!map->type()->contained()->isTraceable());
asherkin@263: 
asherkin@263:         // Compute an interior |elements_| pointer, such that if elements_
asherkin@263:         // is accessed like a FixedArray, we reach the appropriate vector.
asherkin@263:         array->elements_ = Address((Array *)array + 1) - ByteArray::offsetToElements();
asherkin@263:         array->length_ = nelements;
asherkin@263:         memset(array->bytes(), 0, SizeForElement(map->type()) * nelements);
asherkin@263:         return array;
asherkin@263:     }
asherkin@263: 
asherkin@263:     // If there is nothing to allocate, we don't bother creating elements yet.
asherkin@263:     if (!nelements)
asherkin@263:         return array;
asherkin@263: 
asherkin@263:     if (!map->type()->contained()->isTraceable()) {
asherkin@263:         size_t nbytes = SizeForElement(map->type()) * nelements;
asherkin@263:         Local<ByteArray> elements(zone, ByteArray::New(zone, nbytes, tenure));
asherkin@263:         if (!elements)
asherkin@263:             return NULL;
asherkin@263: 
asherkin@263:         array->updateLengthAndElements(zone, nelements, elements);
asherkin@263:         return array;
asherkin@263:     }
asherkin@263: 
asherkin@263:     Local<FixedArray> elements(zone, FixedArray::New(zone, nelements, tenure));
asherkin@263:     if (!elements)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     array->updateLengthAndElements(zone, nelements, elements);
asherkin@263: 
asherkin@263:     // If this is an array of structs, we're required to allocate those structs now.
asherkin@263:     if (map->type()->contained()->isStruct()) {
asherkin@263:         Local<StructType> childType(zone, StructType::cast(map->type()->contained()));
asherkin@263:         Local<StructMap> childMap(zone, childType->newMap());
asherkin@263:         Local<Struct> child(zone);
asherkin@263:         for (unsigned i = 0; i < nelements; i++) {
asherkin@263:             child = Struct::New(zone, childMap, tenure);
asherkin@263:             if (!child)
asherkin@263:                 return NULL;
asherkin@263: 
asherkin@263:             elements->set(zone, i, child);
asherkin@263:         }
asherkin@263:     }
asherkin@263: 
asherkin@263:     return array;
asherkin@263: }
asherkin@263: 
asherkin@263: static Array *
asherkin@263: ConstructSizedArray(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH],
asherkin@263:                     unsigned level, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     Local<Array> array(zone, Array::NewRaw(zone, map, dims[level], tenure));
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     if (map->type()->contained()->isArray()) {
asherkin@263:         Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
asherkin@263:         Local<ArrayMap> childMap(zone, childType->newMap());
asherkin@263:         Local<Array> child(zone);
asherkin@263: 
asherkin@263:         for (unsigned i = 0; i < unsigned(dims[level]); i++) {
asherkin@263:             child = ConstructSizedArray(zone, childMap, dims, level + 1, tenure);
asherkin@263:             if (!child)
asherkin@263:                 return NULL;
asherkin@263: 
asherkin@263:             array->writeObject(zone, i, child);
asherkin@263:         }
asherkin@263:     }
asherkin@263: 
asherkin@263:     return array;
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewSized(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH], Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     for (size_t i = 0; i < map->type()->levels(); i++) {
asherkin@263:         if (dims[i] < 0) {
asherkin@263:             zone->reportError(Message_InvalidDimensionSize, dims[i], i);
asherkin@263:             return NULL;
asherkin@263:         }
asherkin@263:     }
asherkin@263: 
asherkin@263:     return ConstructSizedArray(zone, map, dims, 0, tenure);
asherkin@263: }
asherkin@263: 
asherkin@263: static Array *
asherkin@263: ConstructFixedArray(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     unsigned length = map->type()->fixedLength();
asherkin@263:     Local<Array> array(zone, Array::NewRaw(zone, map, length, tenure));
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     if (map->type()->contained()->isArray()) {
asherkin@263:         Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
asherkin@263:         Local<ArrayMap> childMap(zone, childType->newMap());
asherkin@263:         Local<Array> child(zone);
asherkin@263: 
asherkin@263:         if (childMap->type()->isFixedLength()) {
asherkin@263:             for (unsigned i = 0; i < length; i++) {
asherkin@263:                 child = ConstructFixedArray(zone, childMap, tenure);
asherkin@263:                 if (!child)
asherkin@263:                     return NULL;
asherkin@263: 
asherkin@263:                 array->writeObject(zone, i, child);
asherkin@263:             }
asherkin@263:         } else {
asherkin@263:             for (unsigned i = 0; i < length; i++) {
asherkin@263:                 child = Array::NewRaw(zone, childMap, 0, tenure);
asherkin@263:                 if (!child)
asherkin@263:                     return NULL;
asherkin@263: 
asherkin@263:                 array->writeObject(zone, i, child);
asherkin@263:             }
asherkin@263:         }
asherkin@263:     }
asherkin@263: 
asherkin@263:     return array;
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewFixed(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     return ConstructFixedArray(zone, map, tenure);
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewString(Zone *zone, Handle<ArrayMap> map, char *buffer, size_t length, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     assert(map->type()->isCharArray());
asherkin@263: 
asherkin@263:     Local<Array> array(zone);
asherkin@263:     
asherkin@263:     if (map->type()->isFixedLength())
asherkin@263:         array = Array::NewFixed(zone, map, tenure);
asherkin@263:     else
asherkin@263:         array = Array::New1D(zone, map, length + 1, tenure);
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     assert(array->length() >= length + 1);
asherkin@263:     memcpy(array->chars(), buffer, length + 1);
asherkin@263:     return array;
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::New1D(Zone *zone, Handle<ArrayMap> map, uint32 elements, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     assert(map->type()->levels());
asherkin@263:     return Array::NewRaw(zone, map, elements, tenure);
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewEmpty(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     assert(!map->type()->isFixedLength());
asherkin@263: 
asherkin@263:     return Array::NewRaw(zone, map, 0, tenure);
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::NewExternal(Zone *zone, Handle<ArrayMap> map, void *buffer, unsigned length,
asherkin@263:                    Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     Local<Array> array(zone, Array::cast(zone->allocate(map, sizeof(Array), tenure)));
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     array->length_ = length;
asherkin@263:     array->elements_ = Address(buffer) - ByteArray::offsetToElements();
asherkin@263:     return array;
asherkin@263: }
asherkin@263: 
asherkin@263: static bool
asherkin@263: CopyArrayElements(Zone *zone, Handle<Type> contained, Handle<Array> dest, Handle<Array> source)
asherkin@263: {
asherkin@263:     if (contained->isTraceable()) {
asherkin@263:         if (contained->isStruct()) {
asherkin@263:             assert(dest->type()->contained() == contained);
asherkin@263:             assert(source->length() == dest->length());
asherkin@263: 
asherkin@263:             Local<Struct> left(zone);
asherkin@263:             Local<Struct> right(zone);
asherkin@263:             for (unsigned i = 0; i < source->length(); i++) {
asherkin@263:                 left = Struct::cast(dest->readObject(i));
asherkin@263:                 right = Struct::cast(source->readObject(i));
asherkin@263:                 if (!Struct::Copy(zone, left, right))
asherkin@263:                     return false;
asherkin@263:             }
asherkin@263:         } else if (contained->isArray() && ArrayType::cast(contained)->isFixedLength()) {
asherkin@263:             assert(ArrayType::cast(source->type())->fixedLength() ==
asherkin@263:                    ArrayType::cast(contained)->fixedLength());
asherkin@263: 
asherkin@263:             Local<Array> left(zone);
asherkin@263:             Local<Array> right(zone);
asherkin@263:             for (unsigned i = 0; i < source->length(); i++) {
asherkin@263:                 left = Array::cast(dest->readObject(i));
asherkin@263:                 right = Array::cast(source->readObject(i));
asherkin@263:                 if (!Array::ShallowCopy(zone, left, right))
asherkin@263:                     return false;
asherkin@263:             }
asherkin@263:         } else {
asherkin@263:             assert(dest->length() == source->length());
asherkin@263:             for (unsigned i = 0; i < source->length(); i++)
asherkin@263:                 dest->writeObject(zone, i, source->readObject(i));
asherkin@263:         }
asherkin@263:     } else {
asherkin@263:         assert(contained->pod() == dest->type()->contained()->pod());
asherkin@263:         assert(contained->pod() == PrimitiveType_Char
asherkin@263:                ? source->length() <= dest->length()
asherkin@263:                : source->length() == dest->length());
asherkin@263:     
asherkin@263:         assert(dest->length());
asherkin@263:         memcpy(dest->bytes(), source->bytes(), source->length() * Array::SizeForElement(dest->type()));
asherkin@263:     }
asherkin@263:     return true;
asherkin@263: }
asherkin@263: 
asherkin@263: // Shallow copy an array. Fixed slots in the destination are copied from
asherkin@263: // the source, but otherwise, references are assigned.
asherkin@263: bool
asherkin@263: Array::ShallowCopy(Zone *zone, Handle<Array> dest, Handle<Array> source)
asherkin@263: {
asherkin@263:     Local<Type> contained(zone, dest->type()->contained());
asherkin@263: 
asherkin@263:     return CopyArrayElements(zone, contained, dest, source);
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: Array::DeepCopy(Zone *zone, Handle<Array> source, Heap::Tenure tenure)
asherkin@263: {
asherkin@263:     Local<ArrayMap> map(zone, ArrayMap::cast(source->map()));
asherkin@263: 
asherkin@263:     Local<Array> dest(zone, Array::NewRaw(zone, map, source->length(), tenure));
asherkin@263:     if (!dest)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     Local<Type> contained(zone, source->type()->contained());
asherkin@263:     if (contained->isArray()) {
asherkin@263:         assert(false);
asherkin@263:         Local<Array> sub(zone);
asherkin@263:         for (size_t i = 0; i < source->length(); i++) {
asherkin@263:             sub = Array::cast(source->readObject(i));
asherkin@263:             sub = DeepCopy(zone, sub, tenure);
asherkin@263:             if (!sub)
asherkin@263:                 return NULL;
asherkin@263:             dest->writeObject(zone, i, sub);
asherkin@263:         }
asherkin@263:     } else {
asherkin@263:         if (!CopyArrayElements(zone, contained, dest, source))
asherkin@263:             return NULL;
asherkin@263:     }
asherkin@263: 
asherkin@263:     return dest;
asherkin@263: }
asherkin@263: 
asherkin@263: Array *
asherkin@263: DependentArray::New(Zone *zone, Handle<Array> source, Handle<ArrayMap> map, unsigned index)
asherkin@263: {
asherkin@263:     Local<ArrayType> sourcetype(zone, source->type());
asherkin@263: 
asherkin@263:     // Right now we only support char arrays, to avoid nasty deep cloning
asherkin@263:     // and to maybe cut off this feature as far as we can.
asherkin@263:     assert(sourcetype->isCharArray());
asherkin@263:     assert(map->type()->isCharArray());
asherkin@263: 
asherkin@263:     // We allow taking 0-length dependent strings. It's safe because any reads
asherkin@263:     // or writes will fail.
asherkin@263:     assert(index <= source->length());
asherkin@263: 
asherkin@263:     unsigned newlen = source->length() - index;
asherkin@263:     unsigned eltsize = SizeForElement(sourcetype);
asherkin@263:     
asherkin@263:     if (!sourcetype->isFixedLength()) {
asherkin@263:         // Simple case, just copy the array.
asherkin@263:         Local<ArrayMap> map(zone, sourcetype->newMap());
asherkin@263:         
asherkin@263:         Local<Array> dest(zone, Array::NewRaw(zone, map, newlen, Heap::Tenure_Default));
asherkin@263:         if (!dest)
asherkin@263:             return NULL;
asherkin@263: 
asherkin@263:         memcpy(dest->bytes(),
asherkin@263:                (Address)source->bytes() + (index * eltsize),
asherkin@263:                newlen * eltsize);
asherkin@263:         return dest;
asherkin@263:     }
asherkin@263: 
asherkin@263:     Local<DependentArray> array(zone, DependentArray::cast(zone->allocate(map, sizeof(DependentArray), Heap::Tenure_Default)));
asherkin@263:     if (!array)
asherkin@263:         return NULL;
asherkin@263: 
asherkin@263:     // :GC: This is currently not safe for moving GC! Although we will mark
asherkin@263:     // the object owning the interior pointer, the interior pointer could be
asherkin@263:     // moved later. We will eventually need some way of dealing with this.
asherkin@263:     Address elements = Address(source->bytes()) + (index * eltsize);
asherkin@263: 
asherkin@263:     array->root_ = source;
asherkin@263:     array->length_ = newlen;
asherkin@263:     array->elements_ = elements - ByteArray::offsetToElements();
asherkin@263:     return array;
asherkin@263: }