/*
 * Copyright (C) 2012 Apple Inc. All rights reserved.
 * Copyright (C) 2015 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef ShapeCache_h
#define ShapeCache_h

#include "platform/fonts/shaping/ShapeResult.h"
#include "platform/text/TextRun.h"
#include "wtf/Forward.h"
#include "wtf/HashFunctions.h"
#include "wtf/HashSet.h"
#include "wtf/HashTableDeletedValueType.h"
#include "wtf/StringHasher.h"
#include "wtf/WeakPtr.h"

namespace blink {

class Font;
class GlyphBuffer;
class SimpleFontData;

struct ShapeCacheEntry {
  DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();
  ShapeCacheEntry() { m_shapeResult = nullptr; }
  RefPtr<const ShapeResult> m_shapeResult;
};

class ShapeCache {
  USING_FAST_MALLOC(ShapeCache);
  WTF_MAKE_NONCOPYABLE(ShapeCache);

 private:
  // Used to optimize small strings as hash table keys. Avoids malloc'ing an
  // out-of-line StringImpl.
  class SmallStringKey {
    DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();

   public:
    static unsigned capacity() { return s_capacity; }

    SmallStringKey() : m_length(s_emptyValueLength), m_direction(LTR) {}

    SmallStringKey(WTF::HashTableDeletedValueType)
        : m_length(s_deletedValueLength), m_direction(LTR) {}

    template <typename CharacterType>
    SmallStringKey(CharacterType* characters,
                   unsigned short length,
                   TextDirection direction)
        : m_length(length), m_direction(direction) {
      ASSERT(length <= s_capacity);

      StringHasher hasher;

      bool remainder = length & 1;
      length >>= 1;

      unsigned i = 0;
      while (length--) {
        m_characters[i] = characters[i];
        m_characters[i + 1] = characters[i + 1];
        hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
        i += 2;
      }

      if (remainder) {
        m_characters[i] = characters[i];
        hasher.addCharacter(characters[i]);
      }

      m_hash = hasher.hash();
    }

    const UChar* characters() const { return m_characters; }
    unsigned short length() const { return m_length; }
    TextDirection direction() const {
      return static_cast<TextDirection>(m_direction);
    }
    unsigned hash() const { return m_hash; }

    bool isHashTableDeletedValue() const {
      return m_length == s_deletedValueLength;
    }
    bool isHashTableEmptyValue() const {
      return m_length == s_emptyValueLength;
    }

   private:
    static const unsigned s_capacity = 15;
    static const unsigned s_emptyValueLength = s_capacity + 1;
    static const unsigned s_deletedValueLength = s_capacity + 2;

    unsigned m_hash;
    unsigned m_length : 15;
    unsigned m_direction : 1;
    UChar m_characters[s_capacity];
  };

  struct SmallStringKeyHash {
    STATIC_ONLY(SmallStringKeyHash);
    static unsigned hash(const SmallStringKey& key) { return key.hash(); }
    static bool equal(const SmallStringKey& a, const SmallStringKey& b) {
      return a == b;
    }
    // Empty and deleted values have lengths that are not equal to any valid
    // length.
    static const bool safeToCompareToEmptyOrDeleted = true;
  };

  struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
    STATIC_ONLY(SmallStringKeyHashTraits);
    static const bool hasIsEmptyValueFunction = true;
    static bool isEmptyValue(const SmallStringKey& key) {
      return key.isHashTableEmptyValue();
    }
    static const unsigned minimumTableSize = 16;
  };

  friend bool operator==(const SmallStringKey&, const SmallStringKey&);

 public:
  ShapeCache() : m_weakFactory(this), m_version(0) {}

  ShapeCacheEntry* add(const TextRun& run, ShapeCacheEntry entry) {
    if (run.length() > SmallStringKey::capacity())
      return 0;

    return addSlowCase(run, entry);
  }

  void clearIfVersionChanged(unsigned version) {
    if (version != m_version) {
      clear();
      m_version = version;
    }
  }

  void clear() {
    m_singleCharMap.clear();
    m_shortStringMap.clear();
  }

  unsigned size() const {
    return m_singleCharMap.size() + m_shortStringMap.size();
  }

  size_t byteSize() const {
    size_t selfByteSize = 0;
    for (auto cacheEntry : m_singleCharMap) {
      selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
    }
    for (auto cacheEntry : m_shortStringMap) {
      selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
    }
    return selfByteSize;
  }

  WeakPtr<ShapeCache> weakPtr() { return m_weakFactory.createWeakPtr(); }

 private:
  ShapeCacheEntry* addSlowCase(const TextRun& run, ShapeCacheEntry entry) {
    unsigned length = run.length();
    bool isNewEntry;
    ShapeCacheEntry* value;
    if (length == 1) {
      uint32_t key = run[0];
      // All current codepointsin UTF-32 are bewteen 0x0 and 0x10FFFF,
      // as such use bit 32 to indicate direction.
      if (run.direction() == RTL)
        key |= (1u << 31);
      SingleCharMap::AddResult addResult = m_singleCharMap.add(key, entry);
      isNewEntry = addResult.isNewEntry;
      value = &addResult.storedValue->value;
    } else {
      SmallStringKey smallStringKey;
      if (run.is8Bit())
        smallStringKey =
            SmallStringKey(run.characters8(), length, run.direction());
      else
        smallStringKey =
            SmallStringKey(run.characters16(), length, run.direction());

      SmallStringMap::AddResult addResult =
          m_shortStringMap.add(smallStringKey, entry);
      isNewEntry = addResult.isNewEntry;
      value = &addResult.storedValue->value;
    }

    if (!isNewEntry)
      return value;

    if (size() < s_maxSize)
      return value;

    // No need to be fancy: we're just trying to avoid pathological growth.
    m_singleCharMap.clear();
    m_shortStringMap.clear();

    return 0;
  }

  typedef HashMap<SmallStringKey,
                  ShapeCacheEntry,
                  SmallStringKeyHash,
                  SmallStringKeyHashTraits>
      SmallStringMap;
  typedef HashMap<uint32_t,
                  ShapeCacheEntry,
                  DefaultHash<uint32_t>::Hash,
                  WTF::UnsignedWithZeroKeyHashTraits<uint32_t>>
      SingleCharMap;

  // Hard limit to guard against pathological growth. The expected number of
  // cache entries is a lot lower given the average word count for a web page
  // is well below 1,000 and even full length books rarely have over 10,000
  // unique words [1]. 1: http://www.mine-control.com/zack/guttenberg/
  // Our definition of a word is somewhat different from the norm in that we
  // only segment on space. Thus "foo", "foo-", and "foo)" would count as
  // three separate words. Given that 10,000 seems like a reasonable maximum.
  static const unsigned s_maxSize = 10000;

  SingleCharMap m_singleCharMap;
  SmallStringMap m_shortStringMap;
  WeakPtrFactory<ShapeCache> m_weakFactory;
  unsigned m_version;
};

inline bool operator==(const ShapeCache::SmallStringKey& a,
                       const ShapeCache::SmallStringKey& b) {
  if (a.length() != b.length() || a.direction() != b.direction())
    return false;
  return WTF::equal(a.characters(), b.characters(), a.length());
}

}  // namespace blink

#endif  // ShapeCache_h