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

/*

 *  This file is part of the KDE libraries

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

 *  Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.

 *  Copyright (C) 2007 Cameron Zwarich (cwzwarich@uwaterloo.ca)

 *

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

 *  modify it under the terms of the GNU Library 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

 *  Library General Public License for more details.

 *

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

 *  along with this library; see the file COPYING.LIB.  If not, write to

 *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

 *  Boston, MA 02110-1301, USA.

 *

 */

#include "config.h"

#include "ustring.h"

#include "JSLock.h"

#include "collector.h"

#include "dtoa.h"

#include "function.h"

#include "identifier.h"

#include "operations.h"

#include <assert.h>

#include <ctype.h>

#include <float.h>

#include <limits.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <wtf/Vector.h>

#if HAVE(STRING_H)

#include <string.h>

#endif

#if HAVE(STRINGS_H)

#include <strings.h>

#endif

#if PLATFORM(SYMBIAN)

#define INT_MIN KMinTInt

#define LONG_MIN KMinTInt

#endif

using std::max;

using std::min;

namespace KJS {

extern const double NaN;

extern const double Inf;

static inline const size_t overflowIndicator() { return std::numeric_limits<size_t>::max(); }

static inline const size_t maxUChars() { return std::numeric_limits<size_t>::max() / sizeof(UChar); }

static inline UChar* allocChars(size_t length)

{

    ASSERT(length);

    if (length > maxUChars())

        return 0;

    return static_cast<UChar*>(fastMalloc(sizeof(UChar) * length));

}

static inline UChar* reallocChars(UChar* buffer, size_t length)

{

    ASSERT(length);

    if (length > maxUChars())

        return 0;

    return static_cast<UChar*>(fastRealloc(buffer, sizeof(UChar) * length));

}

// we'd rather not do shared substring append for small strings, since

// this runs too much risk of a tiny initial string holding down a

// huge buffer. This is also tuned to match the extra cost size, so we

// don't ever share a buffer that wouldn't be over the extra cost

// threshold already.

// FIXME: this should be size_t but that would cause warnings until we

// fix UString sizes to be size_t instad of int

static const int minShareSize = Collector::minExtraCostSize / sizeof(UChar);

COMPILE_ASSERT(sizeof(UChar) == 2, uchar_is_2_bytes)

CString::CString(const char *c)

{

  length = strlen(c);

  data = new char[length+1];

  memcpy(data, c, length + 1);

}

CString::CString(const char *c, size_t len)

{

  length = len;

  data = new char[len+1];

  memcpy(data, c, len);

  data[len] = 0;

}

CString::CString(const CString &b)

{

  length = b.length;

  if (b.data) {

    data = new char[length+1];

    memcpy(data, b.data, length + 1);

  }

  else

    data = 0;

}

CString::~CString()

{

  delete [] data;

}

CString &CString::append(const CString &t)

{

  char *n;

  n = new char[length+t.length+1];

  if (length)

    memcpy(n, data, length);

  if (t.length)

    memcpy(n+length, t.data, t.length);

  length += t.length;

  n[length] = 0;

  delete [] data;

  data = n;

  return *this;

}

CString &CString::operator=(const char *c)

{

  if (data)

    delete [] data;

  length = strlen(c);

  data = new char[length+1];

  memcpy(data, c, length + 1);

  return *this;

}

CString &CString::operator=(const CString &str)

{

  if (this == &str)

    return *this;

  if (data)

    delete [] data;

  length = str.length;

  if (str.data) {

    data = new char[length + 1];

    memcpy(data, str.data, length + 1);

  }

  else

    data = 0;

  return *this;

}

bool operator==(const CString& c1, const CString& c2)

{

  size_t len = c1.size();

  return len == c2.size() && (len == 0 || memcmp(c1.c_str(), c2.c_str(), len) == 0);

}

// Hack here to avoid a global with a constructor; point to an unsigned short instead of a UChar.

static unsigned short almostUChar;

UString::Rep UString::Rep::null = { 0, 0, 1, 0, 0, &UString::Rep::null, 0, 0, 0, 0, 0 };

UString::Rep UString::Rep::empty = { 0, 0, 1, 0, 0, &UString::Rep::empty, reinterpret_cast<UChar*>(&almostUChar), 0, 0, 0, 0 };

const int normalStatBufferSize = 4096;

static char *statBuffer = 0;

static int statBufferSize = 0;

PassRefPtr<UString::Rep> UString::Rep::createCopying(const UChar *d, int l)

{

  ASSERT(JSLock::lockCount() > 0);

  int sizeInBytes = l * sizeof(UChar);

  UChar *copyD = static_cast<UChar *>(fastMalloc(sizeInBytes));

  memcpy(copyD, d, sizeInBytes);

  return create(copyD, l);

}

PassRefPtr<UString::Rep> UString::Rep::create(UChar *d, int l)

{

  ASSERT(JSLock::lockCount() > 0);

  Rep* r = new Rep;

  r->offset = 0;

  r->len = l;

  r->rc = 1;

  r->_hash = 0;

  r->isIdentifier = 0;

  r->baseString = r;

  r->buf = d;

  r->usedCapacity = l;

  r->capacity = l;

  r->usedPreCapacity = 0;

  r->preCapacity = 0;

  // steal the single reference this Rep was created with

  return adoptRef(r);

}

PassRefPtr<UString::Rep> UString::Rep::create(PassRefPtr<Rep> base, int offset, int length)

{

  ASSERT(JSLock::lockCount() > 0);

  ASSERT(base);

  int baseOffset = base->offset;

  base = base->baseString;

  assert(-(offset + baseOffset) <= base->usedPreCapacity);

  assert(offset + baseOffset + length <= base->usedCapacity);

  Rep *r = new Rep;

  r->offset = baseOffset + offset;

  r->len = length;

  r->rc = 1;

  r->_hash = 0;

  r->isIdentifier = 0;

  r->baseString = base.releaseRef();

  r->buf = 0;

  r->usedCapacity = 0;

  r->capacity = 0;

  r->usedPreCapacity = 0;

  r->preCapacity = 0;

  // steal the single reference this Rep was created with

  return adoptRef(r);

}

EXPORT

void UString::Rep::destroy()

{

  ASSERT(JSLock::lockCount() > 0);

  if (isIdentifier)

    Identifier::remove(this);

  if (baseString != this) {

    baseString->deref();

  } else {

    fastFree(buf);

  }

  delete this;

}

// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's

// or anything like that.

const unsigned PHI = 0x9e3779b9U;

// Paul Hsieh's SuperFastHash

// http://www.azillionmonkeys.com/qed/hash.html

unsigned UString::Rep::computeHash(const UChar *s, int len)

{

  unsigned l = len;

  uint32_t hash = PHI;

  uint32_t tmp;

  int rem = l & 1;

  l >>= 1;

  // Main loop

  for (; l > 0; l--) {

    hash += s[0].uc;

    tmp = (s[1].uc << 11) ^ hash;

    hash = (hash << 16) ^ tmp;

    s += 2;

    hash += hash >> 11;

  }

  // Handle end case

  if (rem) {

    hash += s[0].uc;

    hash ^= hash << 11;

    hash += hash >> 17;

  }

  // Force "avalanching" of final 127 bits

  hash ^= hash << 3;

  hash += hash >> 5;

  hash ^= hash << 2;

  hash += hash >> 15;

  hash ^= hash << 10;

  // this avoids ever returning a hash code of 0, since that is used to

  // signal "hash not computed yet", using a value that is likely to be

  // effectively the same as 0 when the low bits are masked

  if (hash == 0)

    hash = 0x80000000;

  return hash;

}

// Paul Hsieh's SuperFastHash

// http://www.azillionmonkeys.com/qed/hash.html

unsigned UString::Rep::computeHash(const char *s)

{

  // This hash is designed to work on 16-bit chunks at a time. But since the normal case

  // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they

  // were 16-bit chunks, which should give matching results

  uint32_t hash = PHI;

  uint32_t tmp;

  size_t l = strlen(s);

  size_t rem = l & 1;

  l >>= 1;

  // Main loop

  for (; l > 0; l--) {

    hash += (unsigned char)s[0];

    tmp = ((unsigned char)s[1] << 11) ^ hash;

    hash = (hash << 16) ^ tmp;

    s += 2;

    hash += hash >> 11;

  }

  // Handle end case

  if (rem) {

    hash += (unsigned char)s[0];

    hash ^= hash << 11;

    hash += hash >> 17;

  }

  // Force "avalanching" of final 127 bits

  hash ^= hash << 3;

  hash += hash >> 5;

  hash ^= hash << 2;

  hash += hash >> 15;

  hash ^= hash << 10;

  // this avoids ever returning a hash code of 0, since that is used to

  // signal "hash not computed yet", using a value that is likely to be

  // effectively the same as 0 when the low bits are masked

  if (hash == 0)

    hash = 0x80000000;

  return hash;

}

// put these early so they can be inlined

inline size_t UString::expandedSize(size_t size, size_t otherSize) const

{

    // Do the size calculation in two parts, returning overflowIndicator if

    // we overflow the maximum value that we can handle.

    if (size > maxUChars())

        return overflowIndicator();

    size_t expandedSize = ((size + 10) / 10 * 11) + 1;

    if (maxUChars() - expandedSize < otherSize)

        return overflowIndicator();

    return expandedSize + otherSize;

}

inline int UString::usedCapacity() const

{

  return m_rep->baseString->usedCapacity;

}

inline int UString::usedPreCapacity() const

{

  return m_rep->baseString->usedPreCapacity;

}

void UString::expandCapacity(int requiredLength)

{

  Rep* r = m_rep->baseString;

  if (requiredLength > r->capacity) {

    size_t newCapacity = expandedSize(requiredLength, r->preCapacity);

    UChar* oldBuf = r->buf;

    r->buf = reallocChars(r->buf, newCapacity);

    if (!r->buf) {

        r->buf = oldBuf;

        m_rep = &Rep::null;

        return;

    }

    r->capacity = newCapacity - r->preCapacity;

  }

  if (requiredLength > r->usedCapacity) {

    r->usedCapacity = requiredLength;

  }

}

void UString::expandPreCapacity(int requiredPreCap)

{

  Rep* r = m_rep->baseString;

  if (requiredPreCap > r->preCapacity) {

    size_t newCapacity = expandedSize(requiredPreCap, r->capacity);

    int delta = newCapacity - r->capacity - r->preCapacity;

    UChar* newBuf = allocChars(newCapacity);

    if (!newBuf) {

        m_rep = &Rep::null;

        return;

    }

    memcpy(newBuf + delta, r->buf, (r->capacity + r->preCapacity) * sizeof(UChar));

    fastFree(r->buf);

    r->buf = newBuf;

    r->preCapacity = newCapacity - r->capacity;

  }

  if (requiredPreCap > r->usedPreCapacity) {

    r->usedPreCapacity = requiredPreCap;

  }

}

#if PLATFORM(SYMBIAN)

EXPORT

UString::UString()

  : m_rep(&Rep::null)

{

}

#endif

EXPORT

UString::UString(const char *c)

{

  if (!c) {

    m_rep = &Rep::null;

    return;

  }

  size_t length = strlen(c);

  if (length == 0) {

    m_rep = &Rep::empty;

    return;

  }

  UChar *d = allocChars(length);

  if (!d)

      m_rep = &Rep::null;

  else {

      for (size_t i = 0; i < length; i++)

          d[i].uc = c[i];

      m_rep = Rep::create(d, static_cast<int>(length));

  }

}

EXPORT

UString::UString(const UChar *c, int length)

{

  if (length == 0)

    m_rep = &Rep::empty;

  else

    m_rep = Rep::createCopying(c, length);

}

UString::UString(UChar *c, int length, bool copy)

{

  if (length == 0)

    m_rep = &Rep::empty;

  else if (copy)

    m_rep = Rep::createCopying(c, length);

  else

    m_rep = Rep::create(c, length);

}

EXPORT

UString::UString(const UString &a, const UString &b)

{

  int aSize = a.size();

  int aOffset = a.m_rep->offset;

  int bSize = b.size();

  int bOffset = b.m_rep->offset;

  int length = aSize + bSize;

  // possible cases:

  if (aSize == 0) {

    // a is empty

    m_rep = b.m_rep;

  } else if (bSize == 0) {

    // b is empty

    m_rep = a.m_rep;

  } else if (aOffset + aSize == a.usedCapacity() && aSize >= minShareSize && 4 * aSize >= bSize &&

             (-bOffset != b.usedPreCapacity() || aSize >= bSize)) {

    // - a reaches the end of its buffer so it qualifies for shared append

    // - also, it's at least a quarter the length of b - appending to a much shorter

    //   string does more harm than good

    // - however, if b qualifies for prepend and is longer than a, we'd rather prepend

    UString x(a);

    x.expandCapacity(aOffset + length);

    if (a.data() && x.data()) {

        memcpy(const_cast<UChar *>(a.data() + aSize), b.data(), bSize * sizeof(UChar));

        m_rep = Rep::create(a.m_rep, 0, length);

    } else

        m_rep = &Rep::null;

  } else if (-bOffset == b.usedPreCapacity() && bSize >= minShareSize && 4 * bSize >= aSize) {

    // - b reaches the beginning of its buffer so it qualifies for shared prepend

    // - also, it's at least a quarter the length of a - prepending to a much shorter

    //   string does more harm than good

    UString y(b);

    y.expandPreCapacity(-bOffset + aSize);

    if (b.data() && y.data()) {

        memcpy(const_cast<UChar *>(b.data() - aSize), a.data(), aSize * sizeof(UChar));

        m_rep = Rep::create(b.m_rep, -aSize, length);

    } else

        m_rep = &Rep::null;

  } else {

    // a does not qualify for append, and b does not qualify for prepend, gotta make a whole new string

    size_t newCapacity = expandedSize(length, 0);

    UChar* d = allocChars(newCapacity);

    if (!d)

        m_rep = &Rep::null;

    else {

        memcpy(d, a.data(), aSize * sizeof(UChar));

        memcpy(d + aSize, b.data(), bSize * sizeof(UChar));

        m_rep = Rep::create(d, length);

        m_rep->capacity = newCapacity;

    }

  }

}