src/Array.cpp
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 247 7721042bdb67
child 263 ba85a47ee414
permissions -rw-r--r--
Initial implementation of module imports.
     1 /* vim: set ts=4 sw=4 tw=99 et:
     2  *
     3  * Copyright (C) 2012 David Anderson
     4  *
     5  * This file is part of SourcePawn.
     6  *
     7  * SourcePawn is free software: you can redistribute it and/or modify it under
     8  * the terms of the GNU General Public License as published by the Free
     9  * Software Foundation, either version 3 of the License, or (at your option)
    10  * any later version.
    11  * 
    12  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
    13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along with
    17  * SourcePawn. If not, see http://www.gnu.org/licenses/.
    18  */
    19 #include <string.h>
    20 #include "Array.h"
    21 #include "FixedArray.h"
    22 #include "Heap.h"
    23 #include "Zone.h"
    24 #include "Structures.h"
    25 #include "Heap-inl.h"
    26 
    27 using namespace ke;
    28 
    29 ArrayMap *
    30 ArrayMap::New(Zone *zone, Handle<ArrayType> type)
    31 {
    32     Local<Map> obj(zone, zone->allocateMap(MapKind_Array, sizeof(ArrayMap), MapKind_MetaArray));
    33     if (!obj)
    34         return NULL;
    35 
    36     Local<ArrayMap> map(zone, ArrayMap::cast(obj));
    37     map->type_ = type;
    38     return map;
    39 }
    40 
    41 ArrayMap *
    42 ArrayMap::NewDependent(Zone *zone, Handle<ArrayType> type)
    43 {
    44     Local<Map> obj(zone, zone->allocateMap(MapKind_DependentArray, sizeof(ArrayMap), MapKind_MetaArray));
    45     if (!obj)
    46         return NULL;
    47 
    48     Local<ArrayMap> map(zone, ArrayMap::cast(obj));
    49     map->type_ = type;
    50     return map;
    51 }
    52 
    53 Array *
    54 Array::NewRaw(Zone *zone, Handle<ArrayMap> map, unsigned nelements, Heap::Tenure tenure)
    55 {
    56     assert(!map->type()->isFixedLength() || nelements == map->type()->fixedLength());
    57 
    58     if (nelements > (INT_MAX / SizeForElement(map->type()))) {
    59         zone->reportError(Message_ArraySizeTooBig);
    60         return NULL;
    61     }
    62 
    63     size_t bytes = sizeof(Array);
    64     if (map->type()->hasInlineElements())
    65         bytes += SizeForElement(map->type()) * nelements;
    66 
    67     Local<Array> array(zone, Array::cast(zone->allocate(map, bytes, tenure)));
    68     if (!array)
    69         return NULL;
    70 
    71     array->length_ = 0;
    72     array->elements_ = NULL;
    73 
    74     if (map->type()->hasInlineElements()) {
    75         // This must be a fixed array containing no traceables.
    76         assert(nelements > 0);
    77         assert(map->type()->isFixedLength());
    78         assert(!map->type()->contained()->isTraceable());
    79 
    80         // Compute an interior |elements_| pointer, such that if elements_
    81         // is accessed like a FixedArray, we reach the appropriate vector.
    82         array->elements_ = Address((Array *)array + 1) - ByteArray::offsetToElements();
    83         array->length_ = nelements;
    84         memset(array->bytes(), 0, SizeForElement(map->type()) * nelements);
    85         return array;
    86     }
    87 
    88     // If there is nothing to allocate, we don't bother creating elements yet.
    89     if (!nelements)
    90         return array;
    91 
    92     if (!map->type()->contained()->isTraceable()) {
    93         size_t nbytes = SizeForElement(map->type()) * nelements;
    94         Local<ByteArray> elements(zone, ByteArray::New(zone, nbytes, tenure));
    95         if (!elements)
    96             return NULL;
    97 
    98         array->updateLengthAndElements(zone, nelements, elements);
    99         return array;
   100     }
   101 
   102     Local<FixedArray> elements(zone, FixedArray::New(zone, nelements, tenure));
   103     if (!elements)
   104         return NULL;
   105 
   106     array->updateLengthAndElements(zone, nelements, elements);
   107 
   108     // If this is an array of structs, we're required to allocate those structs now.
   109     if (map->type()->contained()->isStruct()) {
   110         Local<StructType> childType(zone, StructType::cast(map->type()->contained()));
   111         Local<StructMap> childMap(zone, childType->newMap());
   112         Local<Struct> child(zone);
   113         for (unsigned i = 0; i < nelements; i++) {
   114             child = Struct::New(zone, childMap, tenure);
   115             if (!child)
   116                 return NULL;
   117 
   118             elements->set(zone, i, child);
   119         }
   120     }
   121 
   122     return array;
   123 }
   124 
   125 static Array *
   126 ConstructSizedArray(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH],
   127                     unsigned level, Heap::Tenure tenure)
   128 {
   129     Local<Array> array(zone, Array::NewRaw(zone, map, dims[level], tenure));
   130     if (!array)
   131         return NULL;
   132 
   133     if (map->type()->contained()->isArray()) {
   134         Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
   135         Local<ArrayMap> childMap(zone, childType->newMap());
   136         Local<Array> child(zone);
   137 
   138         for (unsigned i = 0; i < unsigned(dims[level]); i++) {
   139             child = ConstructSizedArray(zone, childMap, dims, level + 1, tenure);
   140             if (!child)
   141                 return NULL;
   142 
   143             array->writeObject(zone, i, child);
   144         }
   145     }
   146 
   147     return array;
   148 }
   149 
   150 Array *
   151 Array::NewSized(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH], Heap::Tenure tenure)
   152 {
   153     for (size_t i = 0; i < map->type()->levels(); i++) {
   154         if (dims[i] < 0) {
   155             zone->reportError(Message_InvalidDimensionSize, dims[i], i);
   156             return NULL;
   157         }
   158     }
   159 
   160     return ConstructSizedArray(zone, map, dims, 0, tenure);
   161 }
   162 
   163 static Array *
   164 ConstructFixedArray(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
   165 {
   166     unsigned length = map->type()->fixedLength();
   167     Local<Array> array(zone, Array::NewRaw(zone, map, length, tenure));
   168     if (!array)
   169         return NULL;
   170 
   171     if (map->type()->contained()->isArray()) {
   172         Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
   173         Local<ArrayMap> childMap(zone, childType->newMap());
   174         Local<Array> child(zone);
   175 
   176         if (childMap->type()->isFixedLength()) {
   177             for (unsigned i = 0; i < length; i++) {
   178                 child = ConstructFixedArray(zone, childMap, tenure);
   179                 if (!child)
   180                     return NULL;
   181 
   182                 array->writeObject(zone, i, child);
   183             }
   184         } else {
   185             for (unsigned i = 0; i < length; i++) {
   186                 child = Array::NewRaw(zone, childMap, 0, tenure);
   187                 if (!child)
   188                     return NULL;
   189 
   190                 array->writeObject(zone, i, child);
   191             }
   192         }
   193     }
   194 
   195     return array;
   196 }
   197 
   198 Array *
   199 Array::NewFixed(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
   200 {
   201     return ConstructFixedArray(zone, map, tenure);
   202 }
   203 
   204 Array *
   205 Array::NewString(Zone *zone, Handle<ArrayMap> map, char *buffer, size_t length, Heap::Tenure tenure)
   206 {
   207     assert(map->type()->isCharArray());
   208 
   209     Local<Array> array(zone);
   210     
   211     if (map->type()->isFixedLength())
   212         array = Array::NewFixed(zone, map, tenure);
   213     else
   214         array = Array::New1D(zone, map, length + 1, tenure);
   215     if (!array)
   216         return NULL;
   217 
   218     assert(array->length() >= length + 1);
   219     memcpy(array->chars(), buffer, length + 1);
   220     return array;
   221 }
   222 
   223 Array *
   224 Array::New1D(Zone *zone, Handle<ArrayMap> map, uint32 elements, Heap::Tenure tenure)
   225 {
   226     assert(map->type()->levels());
   227     return Array::NewRaw(zone, map, elements, tenure);
   228 }
   229 
   230 Array *
   231 Array::NewEmpty(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
   232 {
   233     assert(!map->type()->isFixedLength());
   234 
   235     return Array::NewRaw(zone, map, 0, tenure);
   236 }
   237 
   238 Array *
   239 Array::NewExternal(Zone *zone, Handle<ArrayMap> map, void *buffer, unsigned length,
   240                    Heap::Tenure tenure)
   241 {
   242     Local<Array> array(zone, Array::cast(zone->allocate(map, sizeof(Array), tenure)));
   243     if (!array)
   244         return NULL;
   245 
   246     array->length_ = length;
   247     array->elements_ = Address(buffer) - ByteArray::offsetToElements();
   248     return array;
   249 }
   250 
   251 static bool
   252 CopyArrayElements(Zone *zone, Handle<Type> contained, Handle<Array> dest, Handle<Array> source)
   253 {
   254     if (contained->isTraceable()) {
   255         if (contained->isStruct()) {
   256             assert(dest->type()->contained() == contained);
   257             assert(source->length() == dest->length());
   258 
   259             Local<Struct> left(zone);
   260             Local<Struct> right(zone);
   261             for (unsigned i = 0; i < source->length(); i++) {
   262                 left = Struct::cast(dest->readObject(i));
   263                 right = Struct::cast(source->readObject(i));
   264                 if (!Struct::Copy(zone, left, right))
   265                     return false;
   266             }
   267         } else if (contained->isArray() && ArrayType::cast(contained)->isFixedLength()) {
   268             assert(ArrayType::cast(source->type())->fixedLength() ==
   269                    ArrayType::cast(contained)->fixedLength());
   270 
   271             Local<Array> left(zone);
   272             Local<Array> right(zone);
   273             for (unsigned i = 0; i < source->length(); i++) {
   274                 left = Array::cast(dest->readObject(i));
   275                 right = Array::cast(source->readObject(i));
   276                 if (!Array::ShallowCopy(zone, left, right))
   277                     return false;
   278             }
   279         } else {
   280             assert(dest->length() == source->length());
   281             for (unsigned i = 0; i < source->length(); i++)
   282                 dest->writeObject(zone, i, source->readObject(i));
   283         }
   284     } else {
   285         assert(contained->pod() == dest->type()->contained()->pod());
   286         assert(contained->pod() == PrimitiveType_Char
   287                ? source->length() <= dest->length()
   288                : source->length() == dest->length());
   289     
   290         assert(dest->length());
   291         memcpy(dest->bytes(), source->bytes(), source->length() * Array::SizeForElement(dest->type()));
   292     }
   293     return true;
   294 }
   295 
   296 // Shallow copy an array. Fixed slots in the destination are copied from
   297 // the source, but otherwise, references are assigned.
   298 bool
   299 Array::ShallowCopy(Zone *zone, Handle<Array> dest, Handle<Array> source)
   300 {
   301     Local<Type> contained(zone, dest->type()->contained());
   302 
   303     return CopyArrayElements(zone, contained, dest, source);
   304 }
   305 
   306 Array *
   307 Array::DeepCopy(Zone *zone, Handle<Array> source, Heap::Tenure tenure)
   308 {
   309     Local<ArrayMap> map(zone, ArrayMap::cast(source->map()));
   310 
   311     Local<Array> dest(zone, Array::NewRaw(zone, map, source->length(), tenure));
   312     if (!dest)
   313         return NULL;
   314 
   315     Local<Type> contained(zone, source->type()->contained());
   316     if (contained->isArray()) {
   317         assert(false);
   318         Local<Array> sub(zone);
   319         for (size_t i = 0; i < source->length(); i++) {
   320             sub = Array::cast(source->readObject(i));
   321             sub = DeepCopy(zone, sub, tenure);
   322             if (!sub)
   323                 return NULL;
   324             dest->writeObject(zone, i, sub);
   325         }
   326     } else {
   327         if (!CopyArrayElements(zone, contained, dest, source))
   328             return NULL;
   329     }
   330 
   331     return dest;
   332 }
   333 
   334 Array *
   335 DependentArray::New(Zone *zone, Handle<Array> source, Handle<ArrayMap> map, unsigned index)
   336 {
   337     Local<ArrayType> sourcetype(zone, source->type());
   338 
   339     // Right now we only support char arrays, to avoid nasty deep cloning
   340     // and to maybe cut off this feature as far as we can.
   341     assert(sourcetype->isCharArray());
   342     assert(map->type()->isCharArray());
   343 
   344     // We allow taking 0-length dependent strings. It's safe because any reads
   345     // or writes will fail.
   346     assert(index <= source->length());
   347 
   348     unsigned newlen = source->length() - index;
   349     unsigned eltsize = SizeForElement(sourcetype);
   350     
   351     if (!sourcetype->isFixedLength()) {
   352         // Simple case, just copy the array.
   353         Local<ArrayMap> map(zone, sourcetype->newMap());
   354         
   355         Local<Array> dest(zone, Array::NewRaw(zone, map, newlen, Heap::Tenure_Default));
   356         if (!dest)
   357             return NULL;
   358 
   359         memcpy(dest->bytes(),
   360                (Address)source->bytes() + (index * eltsize),
   361                newlen * eltsize);
   362         return dest;
   363     }
   364 
   365     Local<DependentArray> array(zone, DependentArray::cast(zone->allocate(map, sizeof(DependentArray), Heap::Tenure_Default)));
   366     if (!array)
   367         return NULL;
   368 
   369     // :GC: This is currently not safe for moving GC! Although we will mark
   370     // the object owning the interior pointer, the interior pointer could be
   371     // moved later. We will eventually need some way of dealing with this.
   372     Address elements = Address(source->bytes()) + (index * eltsize);
   373 
   374     array->root_ = source;
   375     array->length_ = newlen;
   376     array->elements_ = elements - ByteArray::offsetToElements();
   377     return array;
   378 }