// -*- c-basic-offset: 2 -*-

/*

 *  This file is part of the KDE libraries

 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)

 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.

 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)

 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)

 *

 *  This library is free software; you can redistribute it and/or

 *  modify it under the terms of the GNU Lesser General Public

 *  License as published by the Free Software Foundation; either

 *  version 2 of the License, or (at your option) any later version.

 *

 *  This library 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

 *  Lesser General Public License for more details.

 *

 *  You should have received a copy of the GNU Lesser General Public

 *  License along with this library; if not, write to the Free Software

 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

 *

 */

#include "config.h"

#include "array_object.h"

#include "array_object.lut.h"

#include "error_object.h"

#include "lookup.h"

#include "operations.h"

#include "PropertyNameArray.h"

#include <wtf/HashSet.h>

#include <stdio.h>

#if PLATFORM(SYMBIAN)

#include <Browser_platform_variant.hrh>

#endif  // PLATFORM(SYMBIAN)

using namespace KJS;

// ------------------------------ ArrayInstance -----------------------------

const unsigned sparseArrayCutoff = 10000;

const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};

static inline JSValue** allocateStorage(size_t capacity)

{

  if (capacity == 0)

      return 0;

  // store capacity in extra space before the beginning of the storage array to save space

  JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 1, sizeof(JSValue *))) + 1;

  storage[-1] = reinterpret_cast<JSValue*>(capacity);

  return storage;

}

static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)

{

  if (!storage) {

    storage =  allocateStorage(newCapacity);

    return;

  }

  // store capacity in extra space before the beginning of the storage array to save space

  storage = static_cast<JSValue**>(fastRealloc(storage - 1, (newCapacity + 1) * sizeof (JSValue*))) + 1;

  storage[-1] = reinterpret_cast<JSValue*>(newCapacity);

}

static inline void freeStorage(JSValue** storage)

{

  if (storage)

    fastFree(storage - 1);

}

ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)

  : JSObject(proto)

  , length(initialLength)

  , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)

  , storage(allocateStorage(storageLength))

{

  Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));

}

ArrayInstance::ArrayInstance(JSObject *proto, const List &list)

  : JSObject(proto)

  , length(list.size())

  , storageLength(length)

  , storage(allocateStorage(storageLength))

{

  ListIterator it = list.begin();

  unsigned l = length;

  for (unsigned i = 0; i < l; ++i) {

    storage[i] = it++;

  }

  // When the array is created non-empty its cells are filled so it's really no worse than

  // a property map. Therefore don't report extra memory cost.

}

ArrayInstance::~ArrayInstance()

{

  freeStorage(storage);

}

JSValue* ArrayInstance::getItem(unsigned i) const

{

    if (i >= length)

        return jsUndefined();

    JSValue* val = (i < storageLength) ?

                            storage[i] :

                            getDirect(Identifier::from(i));

    return val ? val : jsUndefined();

}

JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)

{

  return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);

}

bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)

{

  if (propertyName == exec->propertyNames().length) {

    slot.setCustom(this, lengthGetter);

    return true;

  }

  bool ok;

  unsigned index = propertyName.toArrayIndex(&ok);

  if (ok) {

    if (index >= length)

      return false;

    if (index < storageLength) {

      JSValue *v = storage[index];

      if (!v)

        return false;

      slot.setValueSlot(this, &storage[index]);

      return true;

    }

  }

  return JSObject::getOwnPropertySlot(exec, propertyName, slot);

}

bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)

{

  if (index > MAX_ARRAY_INDEX)

    return getOwnPropertySlot(exec, Identifier::from(index), slot);

  if (index >= length)

    return false;

  if (index < storageLength) {

    JSValue *v = storage[index];

    if (!v)

      return false;

    slot.setValueSlot(this, &storage[index]);

    return true;

  }

  return JSObject::getOwnPropertySlot(exec, index, slot);

}

// Special implementation of [[Put]] - see ECMA 15.4.5.1

void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)

{

  if (propertyName == exec->propertyNames().length) {

    unsigned int newLen = value->toUInt32(exec);

    if (value->toNumber(exec) != double(newLen)) {

      throwError(exec, RangeError, "Invalid array length.");

      return;

    }

    setLength(newLen, exec);

    return;

  }

  bool ok;

  unsigned index = propertyName.toArrayIndex(&ok);

  if (ok) {

    put(exec, index, value, attr);

    return;

  }

  JSObject::put(exec, propertyName, value, attr);

}

void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)

{

  //0xFFFF FFFF is a bit weird --- it should be treated as a non-array index, even when

  //it's a string

  if (index > MAX_ARRAY_INDEX) {

    put(exec, Identifier::from(index), value, attr);

    return;

  }

  if (index < sparseArrayCutoff && index >= storageLength) {

    resizeStorage(index + 1);

  }

  if (index >= length) {

    length = index + 1;

  }

  if (index < storageLength) {

    storage[index] = value;

    return;

  }

  assert(index >= sparseArrayCutoff);

  JSObject::put(exec, Identifier::from(index), value, attr);

}

bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)

{

  if (propertyName == exec->propertyNames().length)

    return false;

  bool ok;

  uint32_t index = propertyName.toArrayIndex(&ok);

  if (ok) {

    if (index >= length)

      return true;

    if (index < storageLength) {

      storage[index] = 0;

      return true;

    }

  }

  return JSObject::deleteProperty(exec, propertyName);

}

bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)

{

  if (index > MAX_ARRAY_INDEX)

    return deleteProperty(exec, Identifier::from(index));

  if (index >= length)

    return true;

  if (index < storageLength) {

    storage[index] = 0;

    return true;

  }

  return JSObject::deleteProperty(exec, Identifier::from(index));

}

void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)

{

  // avoid fetching this every time through the loop

  JSValue* undefined = jsUndefined();

  for (unsigned i = 0; i < storageLength; ++i) {

    JSValue* value = storage[i];

    if (value && value != undefined)

      propertyNames.add(Identifier::from(i));

  }

  JSObject::getPropertyNames(exec, propertyNames);

}

void ArrayInstance::resizeStorage(unsigned newLength)

{

    if (newLength < storageLength) {

      memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));

    }

    size_t cap = capacity();

    if (newLength > cap) {

      unsigned newCapacity;

      if (newLength > sparseArrayCutoff) {

        newCapacity = newLength;

      } else {

        newCapacity = (newLength * 3 + 1) / 2;

        if (newCapacity > sparseArrayCutoff) {

          newCapacity = sparseArrayCutoff;

        }

      }

      reallocateStorage(storage, newCapacity);

      memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));

    }

    storageLength = newLength;

}

void ArrayInstance::setLength(unsigned newLength, ExecState *exec)

{

  if (newLength <= storageLength) {

    resizeStorage(newLength);

  }

  if (newLength < length) {

    PropertyNameArray sparseProperties;

    _prop.getSparseArrayPropertyNames(sparseProperties);

    PropertyNameArrayIterator end = sparseProperties.end();

    for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {

      Identifier name = *it;

      bool ok;

      unsigned index = name.toArrayIndex(&ok);

      if (ok && index > newLength)

        deleteProperty(exec, name);

    }

  }

  length = newLength;

}

void ArrayInstance::mark()

{

  if(checkStackDepthTooDeep())

  {

  	return;

  }

  JSObject::mark();

  unsigned l = storageLength;

  for (unsigned i = 0; i < l; ++i) {

    JSValue *imp = storage[i];

    if (imp && !imp->marked())

      imp->mark();

  }

}

static ExecState* execForCompareByStringForQSort = 0;

static int compareByStringForQSort(const void *a, const void *b)

{

    ExecState *exec = execForCompareByStringForQSort;

    JSValue *va = *(JSValue **)a;

    JSValue *vb = *(JSValue **)b;

    if (va->isUndefined()) {

        return vb->isUndefined() ? 0 : 1;

    }

    if (vb->isUndefined()) {

        return -1;

    }

    return compare(va->toString(exec), vb->toString(exec));

}

void ArrayInstance::sort(ExecState* exec)

{

    size_t lengthNotIncludingUndefined = compactForSorting();

    ExecState* oldExec = execForCompareByStringForQSort;

    execForCompareByStringForQSort = exec;

#if HAVE(MERGESORT)

    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.

    // however, becuase it requires extra copies of the storage buffer, don't use it for very

    // large arrays

    // FIXME: for sorting by string value, the fastest thing would actually be to convert all the

    // values to string once up front, and then use a radix sort. That would be O(N) rather than

    // O(N log N).

    if (lengthNotIncludingUndefined < sparseArrayCutoff) {

        JSValue** storageCopy = allocateStorage(capacity());

        memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));

        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);

        freeStorage(storage);

        storage = storageCopy;

        execForCompareByStringForQSort = oldExec;

        return;

    }

#endif

    qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);

    execForCompareByStringForQSort = oldExec;

}

struct CompareWithCompareFunctionArguments {

    CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)

        : exec(e)

        , compareFunction(cf)

        , globalObject(e->dynamicInterpreter()->globalObject())

    {

        arguments.append(jsUndefined());

        arguments.append(jsUndefined());

    }

    ExecState *exec;

    JSObject *compareFunction;

    List arguments;

    JSObject *globalObject;

};

static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;

static int compareWithCompareFunctionForQSort(const void *a, const void *b)

{

    CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;

    JSValue *va = *(JSValue **)a;

    JSValue *vb = *(JSValue **)b;

#if PLATFORM(SYMBIAN) 

    //If both the objects are same then no need to compare. 

    //return 0 from compare function meaning objects are equal.     

    if (va == vb) 

        return 0; 

#endif 

    if (va->isUndefined()) {

        return vb->isUndefined() ? 0 : 1;

    }

    if (vb->isUndefined()) {

        return -1;

    }

    args->arguments.clear();

    args->arguments.append(va);

    args->arguments.append(vb);

    double compareResult = args->compareFunction->call

        (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);

    return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;

}

void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)

{

    size_t lengthNotIncludingUndefined = compactForSorting();

    CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;

    CompareWithCompareFunctionArguments args(exec, compareFunction);

    compareWithCompareFunctionArguments = &args;

#if HAVE(MERGESORT)

    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.

    // however, becuase it requires extra copies of the storage buffer, don't use it for very

    // large arrays

    // FIXME: a tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even

    // better job of minimizing compares

    if (lengthNotIncludingUndefined < sparseArrayCutoff) {

        JSValue** storageCopy = allocateStorage(capacity());

        memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));

        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);

        freeStorage(storage);

        storage = storageCopy;

        compareWithCompareFunctionArguments = oldArgs;

        return;

    }

#endif

    qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);

    compareWithCompareFunctionArguments = oldArgs;

}

unsigned ArrayInstance::compactForSorting()

{

    JSValue *undefined = jsUndefined();

    unsigned o = 0;

    for (unsigned i = 0; i != storageLength; ++i) {

        JSValue *v = storage[i];

        if (v && v != undefined) {

            if (o != i)

                storage[o] = v;

            o++;

        }

    }

    PropertyNameArray sparseProperties;

    _prop.getSparseArrayPropertyNames(sparseProperties);

    unsigned newLength = o + sparseProperties.size();

    if (newLength > storageLength)

        resizeStorage(newLength);

    PropertyNameArrayIterator end = sparseProperties.end();

    for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {

        Identifier name = *it;

        storage[o] = getDirect(name);

        _prop.remove(name);

        o++;

    }

    if (newLength != storageLength)

        memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));

    return o;

}

// ------------------------------ ArrayPrototype ----------------------------

const ClassInfo ArrayPrototype::info = {"Array", &ArrayInstance::info, &arrayTable, 0};

/* Source for array_object.lut.h

@begin arrayTable 16

  toString       ArrayProtoFunc::ToString       DontEnum|Function 0

  toLocaleString ArrayProtoFunc::ToLocaleString DontEnum|Function 0

  concat         ArrayProtoFunc::Concat         DontEnum|Function 1

  join           ArrayProtoFunc::Join           DontEnum|Function 1

  pop            ArrayProtoFunc::Pop            DontEnum|Function 0

  push           ArrayProtoFunc::Push           DontEnum|Function 1

  reverse        ArrayProtoFunc::Reverse        DontEnum|Function 0

  shift          ArrayProtoFunc::Shift          DontEnum|Function 0

  slice          ArrayProtoFunc::Slice          DontEnum|Function 2

  sort           ArrayProtoFunc::Sort           DontEnum|Function 1

  splice         ArrayProtoFunc::Splice         DontEnum|Function 2

  unshift        ArrayProtoFunc::UnShift        DontEnum|Function 1

  every          ArrayProtoFunc::Every          DontEnum|Function 1

  forEach        ArrayProtoFunc::ForEach        DontEnum|Function 1

  some           ArrayProtoFunc::Some           DontEnum|Function 1

  indexOf        ArrayProtoFunc::IndexOf        DontEnum|Function 1

  lastIndexOf    ArrayProtoFunc::LastIndexOf    DontEnum|Function 1

  filter         ArrayProtoFunc::Filter         DontEnum|Function 1

  map            ArrayProtoFunc::Map            DontEnum|Function 1

@end

*/

// ECMA 15.4.4

ArrayPrototype::ArrayPrototype(ExecState*, ObjectPrototype* objProto)

  : ArrayInstance(objProto, 0)

{

}

bool ArrayPrototype::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)

{

  return getStaticFunctionSlot<ArrayProtoFunc, ArrayInstance>(exec, &arrayTable, this, propertyName, slot);

}

// ------------------------------ ArrayProtoFunc ----------------------------

ArrayProtoFunc::ArrayProtoFunc(ExecState* exec, int i, int len, const Identifier& name)

  : InternalFunctionImp(static_cast<FunctionPrototype*>

                        (exec->lexicalInterpreter()->builtinFunctionPrototype()), name)

  , id(i)

{

  put(exec, exec->propertyNames().length, jsNumber(len), DontDelete | ReadOnly | DontEnum);

}

static JSValue *getProperty(ExecState *exec, JSObject *obj, unsigned index)

{