#include <ctype.h>

#include <limits.h>

#include <stddef.h>

#include <stdlib.h>

#include <string.h>

#include "mruby.h"

#include "mruby/array.h"

#include "mruby/class.h"

#include "mruby/range.h"

#include "mruby/string.h"

#include "re.h"

#define STR_EMBED_P(s) ((s)->flags & MRB_STR_EMBED)

#define STR_SET_EMBED_FLAG(s) ((s)->flags |= MRB_STR_EMBED)

#define STR_UNSET_EMBED_FLAG(s) ((s)->flags &= ~(MRB_STR_EMBED|MRB_STR_EMBED_LEN_MASK))

#define STR_SET_EMBED_LEN(s, n) do {\

mrb_int tmp_n = (n);\

s->flags &= ~MRB_STR_EMBED_LEN_MASK;\

s->flags |= (tmp_n) << MRB_STR_EMBED_LEN_SHIFT;\

} while (0)

#define STR_SET_LEN(s, n) do {\

if (STR_EMBED_P(s)) {\

STR_SET_EMBED_LEN((s),(n));\

} else {\

s->as.heap.len = (n);\

}\

} while (0)

#define RSTRING_EMBED_LEN(s) \

(mrb_int)((RSTRING(s)->flags & MRB_STR_EMBED_LEN_MASK) >> MRB_STR_EMBED_LEN_SHIFT)

#define STR_EMBED_LEN(s)\

(mrb_int)(((s)->flags & MRB_STR_EMBED_LEN_MASK) >> MRB_STR_EMBED_LEN_SHIFT)

#define STR_PTR(s) ((STR_EMBED_P(s)) ? (s)->as.ary : (s)->as.heap.ptr)

#define STR_LEN(s) ((STR_EMBED_P(s)) ? STR_EMBED_LEN(s) : (s)->as.heap.len)

const char mrb_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";

typedef struct mrb_shared_string {

} mrb_shared_string;

#define STR_SHARED_P(s) ((s)->flags & MRB_STR_SHARED)

#define STR_SET_SHARED_FLAG(s) ((s)->flags |= MRB_STR_SHARED)

#define STR_UNSET_SHARED_FLAG(s) ((s)->flags &= ~MRB_STR_SHARED)

static mrb_value str_replace(mrb_state *mrb, struct RString *s1, struct RString *s2);

static mrb_value mrb_str_subseq(mrb_state *mrb, mrb_value str, mrb_int beg, mrb_int len);

mrb_str_strlen(mrb_state *mrb, struct RString *s)

{

mrb_int i, max = STR_LEN(s);

char *p = STR_PTR(s);

if (!p) return 0;

for (i=0; i<max; i++) {

if (p[i] == '\0') {

mrb_raise(mrb, E_ARGUMENT_ERROR, "string contains null byte");

}

}

return max;

}

#define RESIZE_CAPA(s,capacity) do {\

if (STR_EMBED_P(s)) {\

if (RSTRING_EMBED_LEN_MAX < (capacity)) {\

char *const tmp = (char *)mrb_malloc(mrb, (capacity)+1);\

const mrb_int len = STR_EMBED_LEN(s);\

memcpy(tmp, s->as.ary, len);\

STR_UNSET_EMBED_FLAG(s);\

s->as.heap.ptr = tmp;\

s->as.heap.len = len;\

s->as.heap.aux.capa = (capacity);\

}\

} else {\

s->as.heap.ptr = (char *)mrb_realloc(mrb, STR_PTR(s), (capacity)+1);\

s->as.heap.aux.capa = capacity;\

}\

} while(0)

static void

str_decref(mrb_state *mrb, mrb_shared_string *shared)

{

shared->refcnt--;

if (shared->refcnt == 0) {

if (!shared->nofree) {

mrb_free(mrb, shared->ptr);

}

mrb_free(mrb, shared);

}

}

mrb_str_modify(mrb_state *mrb, struct RString *s)

{

if (STR_SHARED_P(s)) {

mrb_shared_string *shared = s->as.heap.aux.shared;

if (shared->refcnt == 1 && s->as.heap.ptr == shared->ptr) {

s->as.heap.ptr = shared->ptr;

s->as.heap.aux.capa = shared->len;

STR_PTR(s)[s->as.heap.len] = '\0';

mrb_free(mrb, shared);

}

else {

char *ptr, *p;

mrb_int len;

p = STR_PTR(s);

len = s->as.heap.len;

ptr = (char *)mrb_malloc(mrb, (size_t)len + 1);

if (p) {

memcpy(ptr, p, len);

}

ptr[len] = '\0';

s->as.heap.ptr = ptr;

s->as.heap.aux.capa = len;

str_decref(mrb, shared);

}

STR_UNSET_SHARED_FLAG(s);

return;

}

if (s->flags & MRB_STR_NOFREE) {

char *p = STR_PTR(s);

s->as.heap.ptr = (char *)mrb_malloc(mrb, (size_t)s->as.heap.len+1);

if (p) {

memcpy(STR_PTR(s), p, s->as.heap.len);

}

STR_PTR(s)[s->as.heap.len] = '\0';

s->as.heap.aux.capa = s->as.heap.len;

s->flags &= ~MRB_STR_NOFREE;

return;

}

}

mrb_str_resize(mrb_state *mrb, mrb_value str, mrb_int len)

{

int slen;

struct RString *s = mrb_str_ptr(str);

mrb_str_modify(mrb, s);

slen = STR_LEN(s);

if (len != slen) {

if (slen < len || slen - len > 256) {

RESIZE_CAPA(s, len);

}

STR_SET_LEN(s, len);

STR_PTR(s)[len] = '\0'; /* sentinel */

}

return str;

}

#define mrb_obj_alloc_string(mrb) ((struct RString*)mrb_obj_alloc((mrb), MRB_TT_STRING, (mrb)->string_class))

mrb_str_offset(mrb_state *mrb, mrb_value str, int pos)

{

return pos;

}

static struct RString*

str_new(mrb_state *mrb, const char *p, mrb_int len)

{

struct RString *s;

s = mrb_obj_alloc_string(mrb);

if (len < RSTRING_EMBED_LEN_MAX) {

STR_SET_EMBED_FLAG(s);

STR_SET_EMBED_LEN(s,len);

if (p) {

memcpy(s->as.ary, p, len);

}

} else {

s->as.heap.len = len;

s->as.heap.aux.capa = len;

s->as.heap.ptr = (char *)mrb_malloc(mrb, (size_t)len+1);

if (p) {

memcpy(s->as.heap.ptr, p, len);

}

}

STR_PTR(s)[len] = '\0';

return s;

}

static void

str_with_class(mrb_state *mrb, struct RString *s, mrb_value obj)

{

s->c = mrb_str_ptr(obj)->c;

}

static mrb_value

mrb_str_new_empty(mrb_state *mrb, mrb_value str)

{

struct RString *s = str_new(mrb, 0, 0);

str_with_class(mrb, s, str);

return mrb_obj_value(s);

}

#ifndef MRB_STR_BUF_MIN_SIZE

# define MRB_STR_BUF_MIN_SIZE 128

mrb_str_buf_new(mrb_state *mrb, mrb_int capa)

{

struct RString *s;

s = mrb_obj_alloc_string(mrb);

if (capa < MRB_STR_BUF_MIN_SIZE) {

capa = MRB_STR_BUF_MIN_SIZE;

}

s->as.heap.len = 0;

s->as.heap.aux.capa = capa;

s->as.heap.ptr = (char *)mrb_malloc(mrb, capa+1);

STR_PTR(s)[0] = '\0';

return mrb_obj_value(s);

}

static void

str_buf_cat(mrb_state *mrb, struct RString *s, const char *ptr, size_t len)

{

mrb_int capa;

mrb_int total;

ptrdiff_t off = -1;

mrb_str_modify(mrb, s);

if (ptr >= STR_PTR(s) && ptr <= STR_PTR(s) + STR_LEN(s)) {

off = ptr - STR_PTR(s);

}

if (len == 0) return;

if (STR_EMBED_P(s))

capa = RSTRING_EMBED_LEN_MAX;

else

capa = s->as.heap.aux.capa;

if (STR_LEN(s) >= MRB_INT_MAX - (mrb_int)len) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "string sizes too big");

}

total = STR_LEN(s)+len;

if (capa <= total) {

while (total > capa) {

if (capa + 1 >= MRB_INT_MAX / 2) {

capa = (total + 4095) / 4096;

break;

}

capa = (capa + 1) * 2;

}

RESIZE_CAPA(s, capa);

}

if (off != -1) {

ptr = STR_PTR(s) + off;

}

memcpy(STR_PTR(s) + STR_LEN(s), ptr, len);

STR_SET_LEN(s, total);

STR_PTR(s)[total] = '\0'; /* sentinel */

}

mrb_str_buf_cat(mrb_state *mrb, mrb_value str, const char *ptr, size_t len)

{

if (len == 0) return str;

str_buf_cat(mrb, mrb_str_ptr(str), ptr, len);

return str;

}

mrb_str_new(mrb_state *mrb, const char *p, size_t len)

{

struct RString *s;

if ((mrb_int)len < 0) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "negative string size (or size too big)");

}

s = str_new(mrb, p, len);

return mrb_obj_value(s);

}

mrb_str_new_cstr(mrb_state *mrb, const char *p)

{

struct RString *s;

size_t len;

if (p) {

len = strlen(p);

if ((mrb_int)len < 0) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "argument too big");

}

}

else {

len = 0;

}

s = str_new(mrb, p, len);

return mrb_obj_value(s);

}

mrb_str_new_static(mrb_state *mrb, const char *p, size_t len)

{

struct RString *s;

if ((mrb_int)len < 0) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "negative string size (or size too big)");

}

s = mrb_obj_alloc_string(mrb);

s->as.heap.len = len;

s->as.heap.aux.capa = 0; /* nofree */

s->as.heap.ptr = (char *)p;

s->flags = MRB_STR_NOFREE;

return mrb_obj_value(s);

}

mrb_gc_free_str(mrb_state *mrb, struct RString *str)

{

if (STR_EMBED_P(str))

/* no code */;

else if (STR_SHARED_P(str))

str_decref(mrb, str->as.heap.aux.shared);

else if ((str->flags & MRB_STR_NOFREE) == 0)

mrb_free(mrb, str->as.heap.ptr);

}

char *

mrb_str_to_cstr(mrb_state *mrb, mrb_value str0)

{

struct RString *s;

if (!mrb_string_p(str0)) {

mrb_raise(mrb, E_TYPE_ERROR, "expected String");

}

s = str_new(mrb, RSTRING_PTR(str0), RSTRING_LEN(str0));

if ((strlen(STR_PTR(s)) ^ STR_LEN(s)) != 0) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "string contains null byte");

}

return STR_PTR(s);

}

static void

str_make_shared(mrb_state *mrb, struct RString *s)

{

if (!STR_SHARED_P(s)) {

mrb_shared_string *shared = (mrb_shared_string *)mrb_malloc(mrb, sizeof(mrb_shared_string));

shared->refcnt = 1;

if (STR_EMBED_P(s)) {

const mrb_int len = STR_EMBED_LEN(s);

char *const tmp = (char *)mrb_malloc(mrb, len+1);

memcpy(tmp, s->as.ary, len);

tmp[len] = '\0';

STR_UNSET_EMBED_FLAG(s);

s->as.heap.ptr = tmp;

s->as.heap.len = len;

shared->nofree = FALSE;

shared->ptr = s->as.heap.ptr;

}

else if (s->flags & MRB_STR_NOFREE) {

shared->nofree = TRUE;

shared->ptr = STR_PTR(s);

s->flags &= ~MRB_STR_NOFREE;

}

else {

shared->nofree = FALSE;

if (s->as.heap.aux.capa > s->as.heap.len) {

s->as.heap.ptr = shared->ptr = (char *)mrb_realloc(mrb, STR_PTR(s), s->as.heap.len+1);

}

else {

shared->ptr = STR_PTR(s);

}

}

shared->len = s->as.heap.len;

s->as.heap.aux.shared = shared;

STR_SET_SHARED_FLAG(s);

}

}

const char*

mrb_str_body(mrb_value str, int *len_p)

{

struct RString *s = mrb_str_ptr(str);

*len_p = STR_LEN(s);

return STR_PTR(s);

}

mrb_str_concat(mrb_state *mrb, mrb_value self, mrb_value other)

{

struct RString *s1 = mrb_str_ptr(self), *s2;

mrb_int len;

mrb_str_modify(mrb, s1);

if (!mrb_string_p(other)) {

other = mrb_str_to_str(mrb, other);

}

s2 = mrb_str_ptr(other);

len = STR_LEN(s1) + STR_LEN(s2);

if (RSTRING_CAPA(self) < len) {

RESIZE_CAPA(s1, len);

}

memcpy(STR_PTR(s1)+STR_LEN(s1), STR_PTR(s2), STR_LEN(s2));

STR_SET_LEN(s1, len);

STR_PTR(s1)[len] = '\0';

}

mrb_str_plus(mrb_state *mrb, mrb_value a, mrb_value b)

{

struct RString *s = mrb_str_ptr(a);

struct RString *s2 = mrb_str_ptr(b);

struct RString *t;

t = str_new(mrb, 0, STR_LEN(s) + STR_LEN(s2));

memcpy(STR_PTR(t), STR_PTR(s), STR_LEN(s));

memcpy(STR_PTR(t) + STR_LEN(s), STR_PTR(s2), STR_LEN(s2));

return mrb_obj_value(t);

}

static mrb_value

mrb_str_plus_m(mrb_state *mrb, mrb_value self)

{

mrb_value str;

mrb_get_args(mrb, "S", &str);

return mrb_str_plus(mrb, self, str);

}

static mrb_value

mrb_str_bytesize(mrb_state *mrb, mrb_value self)

{

struct RString *s = mrb_str_ptr(self);

return mrb_fixnum_value(STR_LEN(s));

}

mrb_str_size(mrb_state *mrb, mrb_value self)

{

struct RString *s = mrb_str_ptr(self);

return mrb_fixnum_value(STR_LEN(s));

}

static mrb_value

mrb_str_times(mrb_state *mrb, mrb_value self)

{

mrb_int n,len,times;

struct RString *str2;

char *p;

mrb_get_args(mrb, "i", &times);

if (times < 0) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "negative argument");

}

if (times && MRB_INT_MAX / times < RSTRING_LEN(self)) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "argument too big");

}

len = RSTRING_LEN(self)*times;

str2 = str_new(mrb, 0, len);

str_with_class(mrb, str2, self);

p = STR_PTR(str2);

if (len > 0) {

n = RSTRING_LEN(self);

memcpy(p, RSTRING_PTR(self), n);

while (n <= len/2) {

memcpy(p + n, p, n);

n *= 2;

}

memcpy(p + n, p, len-n);

}

p[STR_LEN(str2)] = '\0';

return mrb_obj_value(str2);

}

#define lesser(a,b) (((a)>(b))?(b):(a))

mrb_str_cmp(mrb_state *mrb, mrb_value str1, mrb_value str2)

{

mrb_int len;

mrb_int retval;

struct RString *s1 = mrb_str_ptr(str1);

struct RString *s2 = mrb_str_ptr(str2);

len = lesser(STR_LEN(s1), STR_LEN(s2));

retval = memcmp(STR_PTR(s1), STR_PTR(s2), len);

if (retval == 0) {

if (STR_LEN(s1) == STR_LEN(s2)) return 0;

if (STR_LEN(s1) > STR_LEN(s2)) return 1;

return -1;

}

if (retval > 0) return 1;

return -1;

}

static mrb_value

mrb_str_cmp_m(mrb_state *mrb, mrb_value str1)

{

mrb_value str2;

mrb_int result;

mrb_get_args(mrb, "o", &str2);

if (!mrb_string_p(str2)) {

if (!mrb_respond_to(mrb, str2, mrb_intern_lit(mrb, "to_s"))) {

return mrb_nil_value();

}

else if (!mrb_respond_to(mrb, str2, mrb_intern_lit(mrb, "<=>"))) {

return mrb_nil_value();

}

else {

mrb_value tmp = mrb_funcall(mrb, str2, "<=>", 1, str1);

if (mrb_nil_p(tmp)) return mrb_nil_value();

if (!mrb_fixnum(tmp)) {

return mrb_funcall(mrb, mrb_fixnum_value(0), "-", 1, tmp);

}

result = -mrb_fixnum(tmp);

}

}

else {

result = mrb_str_cmp(mrb, str1, str2);

}

return mrb_fixnum_value(result);

}

static mrb_bool

str_eql(mrb_state *mrb, const mrb_value str1, const mrb_value str2)

{

const mrb_int len = RSTRING_LEN(str1);

if (len != RSTRING_LEN(str2)) return FALSE;

if (memcmp(RSTRING_PTR(str1), RSTRING_PTR(str2), (size_t)len) == 0)

return TRUE;

return FALSE;

}

mrb_str_equal(mrb_state *mrb, mrb_value str1, mrb_value str2)

{

if (mrb_obj_equal(mrb, str1, str2)) return TRUE;

if (!mrb_string_p(str2)) {

if (mrb_nil_p(str2)) return FALSE;

if (!mrb_respond_to(mrb, str2, mrb_intern_lit(mrb, "to_str"))) {

return FALSE;

}

str2 = mrb_funcall(mrb, str2, "to_str", 0);

return mrb_equal(mrb, str2, str1);

}

return str_eql(mrb, str1, str2);

}

static mrb_value

mrb_str_equal_m(mrb_state *mrb, mrb_value str1)

{

mrb_value str2;

mrb_bool equal_p;

mrb_get_args(mrb, "o", &str2);

equal_p = mrb_str_equal(mrb, str1, str2);

return mrb_bool_value(equal_p);

}

mrb_str_to_str(mrb_state *mrb, mrb_value str)

{

mrb_value s;

if (!mrb_string_p(str)) {

s = mrb_check_convert_type(mrb, str, MRB_TT_STRING, "String", "to_str");

if (mrb_nil_p(s)) {

s = mrb_convert_type(mrb, str, MRB_TT_STRING, "String", "to_s");

}

return s;

}

return str;

}

char *

mrb_string_value_ptr(mrb_state *mrb, mrb_value ptr)

{

mrb_value str = mrb_str_to_str(mrb, ptr);

return RSTRING_PTR(str);

}

static mrb_value

noregexp(mrb_state *mrb, mrb_value self)

{

mrb_raise(mrb, E_NOTIMP_ERROR, "Regexp class not implemented");

return mrb_nil_value();

}

static void

regexp_check(mrb_state *mrb, mrb_value obj)

{

if (!memcmp(mrb_obj_classname(mrb, obj), REGEXP_CLASS, sizeof(REGEXP_CLASS) - 1)) {

noregexp(mrb, obj);

}

}

static inline mrb_int

mrb_memsearch_qs(const unsigned char *xs, mrb_int m, const unsigned char *ys, mrb_int n)

{

const unsigned char *x = xs, *xe = xs + m;

const unsigned char *y = ys;

int i, qstable[256];

/* Preprocessing */

for (i = 0; i < 256; ++i)

qstable[i] = m + 1;

for (; x < xe; ++x)

qstable[*x] = xe - x;

/* Searching */

for (; y + m <= ys + n; y += *(qstable + y[m])) {

if (*xs == *y && memcmp(xs, y, m) == 0)

return y - ys;

}

return -1;

}

static mrb_int

mrb_memsearch(const void *x0, mrb_int m, const void *y0, mrb_int n)

{

const unsigned char *x = (const unsigned char *)x0, *y = (const unsigned char *)y0;

if (m > n) return -1;

else if (m == n) {

return memcmp(x0, y0, m) == 0 ? 0 : -1;

}

else if (m < 1) {

return 0;

}

else if (m == 1) {

const unsigned char *ys = y, *ye = ys + n;

for (; y < ye; ++y) {

if (*x == *y)

return y - ys;

}

return -1;

}

return mrb_memsearch_qs((const unsigned char *)x0, m, (const unsigned char *)y0, n);

}

static mrb_int

mrb_str_index(mrb_state *mrb, mrb_value str, mrb_value sub, mrb_int offset)

{

mrb_int pos;

char *s, *sptr;

mrb_int len, slen;

len = RSTRING_LEN(str);

slen = RSTRING_LEN(sub);

if (offset < 0) {

offset += len;

if (offset < 0) return -1;

}

if (len - offset < slen) return -1;

s = RSTRING_PTR(str);

if (offset) {

s += offset;

}

if (slen == 0) return offset;

/* need proceed one character at a time */

sptr = RSTRING_PTR(sub);

slen = RSTRING_LEN(sub);

len = RSTRING_LEN(str) - offset;

pos = mrb_memsearch(sptr, slen, s, len);

if (pos < 0) return pos;

return pos + offset;

}

mrb_str_dup(mrb_state *mrb, mrb_value str)

{

/* should return shared string */

struct RString *s = mrb_str_ptr(str);

return mrb_str_new(mrb, STR_PTR(s), STR_LEN(s));

}

static mrb_value

mrb_str_aref(mrb_state *mrb, mrb_value str, mrb_value indx)

{

mrb_int idx;

regexp_check(mrb, indx);

switch (mrb_type(indx)) {

case MRB_TT_FIXNUM:

idx = mrb_fixnum(indx);

num_index:

str = mrb_str_substr(mrb, str, idx, 1);

if (!mrb_nil_p(str) && RSTRING_LEN(str) == 0) return mrb_nil_value();

return str;

case MRB_TT_STRING:

if (mrb_str_index(mrb, str, indx, 0) != -1)

return mrb_str_dup(mrb, indx);

return mrb_nil_value();

case MRB_TT_RANGE:

/* check if indx is Range */

{

mrb_int beg, len;

len = RSTRING_LEN(str);

if (mrb_range_beg_len(mrb, indx, &beg, &len, len)) {

return mrb_str_subseq(mrb, str, beg, len);

}

else {

return mrb_nil_value();

}

}

default:

idx = mrb_fixnum(indx);

goto num_index;

}

return mrb_nil_value(); /* not reached */

}

static mrb_value

mrb_str_aref_m(mrb_state *mrb, mrb_value str)

{

mrb_value a1, a2;

int argc;

argc = mrb_get_args(mrb, "o|o", &a1, &a2);

if (argc == 2) {

regexp_check(mrb, a1);

return mrb_str_substr(mrb, str, mrb_fixnum(a1), mrb_fixnum(a2));

}

if (argc != 1) {

mrb_raisef(mrb, E_ARGUMENT_ERROR, "wrong number of arguments (%S for 1)", mrb_fixnum_value(argc));

}

return mrb_str_aref(mrb, str, a1);

}

static mrb_value

mrb_str_capitalize_bang(mrb_state *mrb, mrb_value str)

{

char *p, *pend;

int modify = 0;

struct RString *s = mrb_str_ptr(str);

mrb_str_modify(mrb, s);

if (STR_LEN(s) == 0 || !STR_PTR(s)) return mrb_nil_value();

p = STR_PTR(s); pend = STR_PTR(s) + STR_LEN(s);

if (ISLOWER(*p)) {

*p = TOUPPER(*p);

modify = 1;

}

while (++p < pend) {

if (ISUPPER(*p)) {

*p = TOLOWER(*p);

modify = 1;

}

}

if (modify) return str;

return mrb_nil_value();

}

static mrb_value

mrb_str_capitalize(mrb_state *mrb, mrb_value self)

{

mrb_value str;

str = mrb_str_dup(mrb, self);

mrb_str_capitalize_bang(mrb, str);

return str;

}

static mrb_value

mrb_str_chomp_bang(mrb_state *mrb, mrb_value str)

{

mrb_value rs;

mrb_int newline;

char *p, *pp;

mrb_int rslen;

mrb_int len;

struct RString *s = mrb_str_ptr(str);

mrb_str_modify(mrb, s);

len = STR_LEN(s);

if (mrb_get_args(mrb, "|S", &rs) == 0) {

if (len == 0) return mrb_nil_value();

smart_chomp:

if (STR_PTR(s)[len-1] == '\n') {

STR_SET_LEN(s, STR_LEN(s) - 1);

if (STR_LEN(s) > 0 &&

STR_PTR(s)[STR_LEN(s)-1] == '\r') {

STR_SET_LEN(s, STR_LEN(s) - 1);

}

}

else if (STR_PTR(s)[len-1] == '\r') {

STR_SET_LEN(s, STR_LEN(s) - 1);

}