#ifndef MYCPP_GC_STR_H
#define MYCPP_GC_STR_H

#include <limits.h>  // CHAR_BIT

#include "mycpp/common.h"  // DISALLOW_COPY_AND_ASSIGN
#include "mycpp/gc_obj.h"  // GC_OBJ
#include "mycpp/hash.h"    // HashFunc

// https://stackoverflow.com/questions/3919995/determining-sprintf-buffer-size-whats-the-standard/11092994#11092994
// Notes:
// - Python 2.7's intobject.c has an erroneous +6
// - This is 13, but len('-2147483648') is 11, which means we only need 12?
// - This formula is valid for octal(), because 2^(3 bits) = 8

const int kIntBufSize = CHAR_BIT * sizeof(int) / 3 + 3;

template <typename T>
class List;

class BigStr {
 public:
  // Don't call this directly.  Call NewStr() instead, which calls this.
  BigStr() {
  }

  char* data() {
    return data_;
  }

  // Call this after writing into buffer created by OverAllocatedStr()
  void MaybeShrink(int str_len);

  BigStr* at(int i);

  int find(BigStr* needle, int start = 0, int end = -1);
  int rfind(BigStr* needle, int start = 0, int end = -1);

  BigStr* slice(int begin);
  BigStr* slice(int begin, int end);

  BigStr* strip();
  // Used for CommandSub in osh/cmd_exec.py
  BigStr* rstrip(BigStr* chars);
  BigStr* rstrip();

  BigStr* lstrip(BigStr* chars);
  BigStr* lstrip();

  BigStr* ljust(int width, BigStr* fillchar);
  BigStr* rjust(int width, BigStr* fillchar);

  // Can take (start, end) so Tokens can be compared without allocation
  bool startswith(BigStr* s);
  bool endswith(BigStr* s);

  BigStr* replace(BigStr* old, BigStr* new_str);
  BigStr* replace(BigStr* old, BigStr* new_str, int count);
  BigStr* join(List<BigStr*>* items);

  List<BigStr*>* split(BigStr* sep);
  List<BigStr*>* split(BigStr* sep, int max_split);
  List<BigStr*>* splitlines(bool keep);

  // TODO: Move unicode functions out of mycpp runtime?  Because we won't match
  // Python exactly
  bool isdigit();
  bool isalpha();
  bool isupper();

  BigStr* upper();
  BigStr* lower();

  // Other options for fast comparison / hashing / string interning:
  // - unique_id_: an index into intern table.  I don't think this works unless
  //   you want to deal with rehashing all strings when the set grows.
  //   - although note that the JVM has -XX:StringTableSize=FIXED, which means
  //   - it can degrade into linked list performance
  // - Hashed strings become GLOBAL_STR().  Never deallocated.
  // - Hashed strings become part of the "large object space", which might be
  //   managed by mark and sweep.  This requires linked list overhead.
  //   (doubly-linked?)
  // - Intern strings at GARBAGE COLLECTION TIME, with
  //   LayoutForwarded::new_location_?  Is this possible?  Does it introduce
  //   too much coupling between strings, hash tables, and GC?

  static constexpr ObjHeader obj_header() {
    return ObjHeader::BigStr();
  }

  unsigned hash(HashFunc h);

  int len_;
  unsigned hash_ : 31;
  unsigned is_hashed_ : 1;
  char data_[1];  // flexible array

 private:
  int internal_find(BigStr* needle, int direction, int start, int end);
  int _strip_left_pos();
  int _strip_right_pos();

  DISALLOW_COPY_AND_ASSIGN(BigStr)
};

constexpr int kStrHeaderSize = offsetof(BigStr, data_);

// Note: for SmallStr, we might copy into the VALUE
inline void BigStr::MaybeShrink(int str_len) {
  len_ = str_len;
  data_[len_] = '\0';  // NUL terminate
}

inline int len(const BigStr* s) {
  return s->len_;
}

BigStr* StrFormat(const char* fmt, ...);
BigStr* StrFormat(BigStr* fmt, ...);

// NOTE: This iterates over bytes.
class StrIter {
 public:
  explicit StrIter(BigStr* s) : s_(s), i_(0), len_(len(s)) {
    // Cheney only: s_ could be moved during iteration.
    // gHeap.PushRoot(reinterpret_cast<RawObject**>(&s_));
  }
  ~StrIter() {
    // gHeap.PopRoot();
  }
  void Next() {
    i_++;
  }
  bool Done() {
    return i_ >= len_;
  }
  BigStr* Value();  // similar to at()

 private:
  BigStr* s_;
  int i_;
  int len_;

  DISALLOW_COPY_AND_ASSIGN(StrIter)
};

extern BigStr* kEmptyString;

// GlobalStr notes:
// - sizeof("foo") == 4, for the NUL terminator.
// - gc_heap_test.cc has a static_assert that GlobalStr matches BigStr.  We
// don't put it here because it triggers -Winvalid-offsetof

template <int N>
class GlobalStr {
  // A template type with the same layout as BigStr with length N-1 (which needs
  // a buffer of size N).  For initializing global constant instances.
 public:
  int len_;
  unsigned hash_ : 31;
  unsigned is_hashed_ : 1;
  const char data_[N];

  DISALLOW_COPY_AND_ASSIGN(GlobalStr)
};

union Str {
 public:
  // Instead of this at the start of every function:
  //   Str* s = nullptr;
  // It will now be:
  //   Str s(nullptr);
  //
  //   StackRoot _root(&s);
  explicit Str(BigStr* big) : big_(big) {
  }

  char* data() {
    return big_->data();
  }

  Str at(int i) {
    return Str(big_->at(i));
  }

  Str upper() {
    return Str(big_->upper());
  }

  uint64_t raw_bytes_;
  BigStr* big_;
  // TODO: add SmallStr, see mycpp/small_str_test.cc
};

inline int len(const Str s) {
  return len(s.big_);
}

// This macro is a workaround for the fact that it's impossible to have a
// a constexpr initializer for char[N].  The "String Literals as Non-Type
// Template Parameters" feature of C++ 20 would have done it, but it's not
// there.
//
// https://old.reddit.com/r/cpp_questions/comments/j0khh6/how_to_constexpr_initialize_class_member_thats/
// https://stackoverflow.com/questions/10422487/how-can-i-initialize-char-arrays-in-a-constructor
//
// TODO: Can we hash values at compile time so they can be in the intern table?

#define GLOBAL_STR(name, val)                                                \
  GcGlobal<GlobalStr<sizeof(val)>> _##name = {                               \
      ObjHeader::Global(TypeTag::BigStr),                                    \
      {.len_ = sizeof(val) - 1, .hash_ = 0, .is_hashed_ = 0, .data_ = val}}; \
  BigStr* name = reinterpret_cast<BigStr*>(&_##name.obj);

// New style for SmallStr compatibility
#define GLOBAL_STR2(name, val)                                               \
  GcGlobal<GlobalStr<sizeof(val)>> _##name = {                               \
      ObjHeader::Global(TypeTag::BigStr),                                    \
      {.len_ = sizeof(val) - 1, .hash_ = 0, .is_hashed_ = 0, .data_ = val}}; \
  Str name(reinterpret_cast<BigStr*>(&_##name.obj));

// Helper function that's consistent with JSON definition of ASCII whitespace,
// e.g.
// {"age": \t 42} is OK
// {"age": \v 42} is NOT OK
inline bool IsAsciiWhitespace(int ch) {
  return ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n';
}

#endif  // MYCPP_GC_STR_H
