string.c

Go to the documentation of this file.

/**********************************************************************

  string.c -

  $Author: matz $
  $Date: 2005/10/27 08:19:20 $
  created at: Mon Aug  9 17:12:58 JST 1993

  Copyright (C) 1993-2003 Yukihiro Matsumoto
  Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  Copyright (C) 2000  Information-technology Promotion Agency, Japan

**********************************************************************/

#include "ruby.h"
#include "re.h"

#define BEG(no) regs->beg[no]
#define END(no) regs->end[no]

#include <math.h>
#include <ctype.h>

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

VALUE rb_cString;

#define STR_TMPLOCK FL_USER1
#define STR_ASSOC   FL_USER3
#define STR_NOCAPA  (ELTS_SHARED|STR_ASSOC)

#define RESIZE_CAPA(str,capacity) do {\
    REALLOC_N(RSTRING(str)->ptr, char, (capacity)+1);\
    if (!FL_TEST(str, STR_NOCAPA))\
        RSTRING(str)->aux.capa = (capacity);\
} while (0)

VALUE rb_fs;

static inline void
str_mod_check(s, p, len)
    VALUE s;
    char *p;
    long len;
{
    if (RSTRING(s)->ptr != p || RSTRING(s)->len != len) {
        rb_raise(rb_eRuntimeError, "string modified");
    }
}

static inline void
str_frozen_check(s)
    VALUE s;
{
    if (OBJ_FROZEN(s)) {
        rb_raise(rb_eRuntimeError, "string frozen");
    }
}

static VALUE str_alloc (VALUE);
static VALUE
str_alloc(klass)
    VALUE klass;
{
    NEWOBJ(str, struct RString);
    OBJSETUP(str, klass, T_STRING);

    str->ptr = 0;
    str->len = 0;
    str->aux.capa = 0;

    return (VALUE)str;
}

static VALUE
str_new(klass, ptr, len)
    VALUE klass;
    const char *ptr;
    long len;
{
    VALUE str;

    if (len < 0) {
        rb_raise(rb_eArgError, "negative string size (or size too big)");
    }

    str = str_alloc(klass);
    RSTRING(str)->len = len;
    RSTRING(str)->aux.capa = len;
    RSTRING(str)->ptr = ALLOC_N(char,len+1);
    if (ptr) {
        memcpy(RSTRING(str)->ptr, ptr, len);
    }
    RSTRING(str)->ptr[len] = '\0';
    return str;
}

VALUE
rb_str_new(ptr, len)
    const char *ptr;
    long len;
{
    return str_new(rb_cString, ptr, len);
}

VALUE
rb_str_new2(ptr)
    const char *ptr;
{
    if (!ptr) {
        rb_raise(rb_eArgError, "NULL pointer given");
    }
    return rb_str_new(ptr, strlen(ptr));
}

VALUE
rb_tainted_str_new(ptr, len)
    const char *ptr;
    long len;
{
    VALUE str = rb_str_new(ptr, len);

    OBJ_TAINT(str);
    return str;
}

VALUE
rb_tainted_str_new2(ptr)
    const char *ptr;
{
    VALUE str = rb_str_new2(ptr);

    OBJ_TAINT(str);
    return str;
}

static VALUE
str_new3(klass, str)
    VALUE klass, str;
{
    VALUE str2 = str_alloc(klass);

    RSTRING(str2)->len = RSTRING(str)->len;
    RSTRING(str2)->ptr = RSTRING(str)->ptr;
    RSTRING(str2)->aux.shared = str;
    FL_SET(str2, ELTS_SHARED);
    OBJ_INFECT(str2, str);

    return str2;
}

VALUE
rb_str_new3(str)
    VALUE str;
{
    return str_new3(rb_obj_class(str), str);
}

static VALUE
str_new4(klass, str)
    VALUE klass, str;
{
    VALUE str2 = str_alloc(klass);

    RSTRING(str2)->len = RSTRING(str)->len;
    RSTRING(str2)->ptr = RSTRING(str)->ptr;
    if (FL_TEST(str, ELTS_SHARED)) {
        FL_SET(str2, ELTS_SHARED);
        RSTRING(str2)->aux.shared = RSTRING(str)->aux.shared;
    }
    else {
        FL_SET(str, ELTS_SHARED);
        RSTRING(str)->aux.shared = str2;
    }

    return str2;
}

VALUE
rb_str_new4(orig)
    VALUE orig;
{
    VALUE klass, str;

    if (OBJ_FROZEN(orig)) return orig;
    klass = rb_obj_class(orig);
    if (FL_TEST(orig, ELTS_SHARED) && (str = RSTRING(orig)->aux.shared) && klass == RBASIC(str)->klass) {
        long ofs;
        ofs = RSTRING(str)->len - RSTRING(orig)->len;
        if (ofs > 0) {
            str = str_new3(klass, str);
            RSTRING(str)->ptr += ofs;
            RSTRING(str)->len -= ofs;
        }
    }
    else if (FL_TEST(orig, STR_ASSOC)) {
        str = str_new(klass, RSTRING(orig)->ptr, RSTRING(orig)->len);
    }
    else {
        str = str_new4(klass, orig);
    }
    OBJ_INFECT(str, orig);
    OBJ_FREEZE(str);
    return str;
}

VALUE
rb_str_new5(obj, ptr, len)
    VALUE obj;
    const char *ptr;
    long len;
{
    return str_new(rb_obj_class(obj), ptr, len);
}

#define STR_BUF_MIN_SIZE 128

VALUE
rb_str_buf_new(capa)
    long capa;
{
    VALUE str = str_alloc(rb_cString);

    if (capa < STR_BUF_MIN_SIZE) {
        capa = STR_BUF_MIN_SIZE;
    }
    RSTRING(str)->ptr = 0;
    RSTRING(str)->len = 0;
    RSTRING(str)->aux.capa = capa;
    RSTRING(str)->ptr = ALLOC_N(char, capa+1);
    RSTRING(str)->ptr[0] = '\0';

    return str;
}

VALUE
rb_str_buf_new2(ptr)
    const char *ptr;
{
    VALUE str;
    long len = strlen(ptr);

    str = rb_str_buf_new(len);
    rb_str_buf_cat(str, ptr, len);

    return str;
}

VALUE
rb_str_to_str(str)
    VALUE str;
{
    return rb_convert_type(str, T_STRING, "String", "to_str");
}

static void
rb_str_shared_replace(str, str2)
    VALUE str, str2;
{
    if (str == str2) return;
    rb_str_modify(str);
    if (!FL_TEST(str, ELTS_SHARED)) free(RSTRING(str)->ptr);
    if (NIL_P(str2)) {
        RSTRING(str)->ptr = 0;
        RSTRING(str)->len = 0;
        RSTRING(str)->aux.capa = 0;
        FL_UNSET(str, STR_NOCAPA);
        return;
    }
    RSTRING(str)->ptr = RSTRING(str2)->ptr;
    RSTRING(str)->len = RSTRING(str2)->len;
    FL_UNSET(str, STR_NOCAPA);
    if (FL_TEST(str2, STR_NOCAPA)) {
        FL_SET(str, RBASIC(str2)->flags & STR_NOCAPA);
        RSTRING(str)->aux.shared = RSTRING(str2)->aux.shared;
    }
    else {
        RSTRING(str)->aux.capa = RSTRING(str2)->aux.capa;
    }
    RSTRING(str2)->ptr = 0;     /* abandon str2 */
    RSTRING(str2)->len = 0;
    RSTRING(str2)->aux.capa = 0;
    FL_UNSET(str2, STR_NOCAPA);
    if (OBJ_TAINTED(str2)) OBJ_TAINT(str);
}

static ID id_to_s;

VALUE
rb_obj_as_string(obj)
    VALUE obj;
{
    VALUE str;

    if (TYPE(obj) == T_STRING) {
        return obj;
    }
    str = rb_funcall(obj, id_to_s, 0);
    if (TYPE(str) != T_STRING)
        return rb_any_to_s(obj);
    if (OBJ_TAINTED(obj)) OBJ_TAINT(str);
    return str;
}

static VALUE rb_str_replace (VALUE, VALUE);

VALUE
rb_str_dup(str)
    VALUE str;
{
    VALUE dup = str_alloc(rb_obj_class(str));
    rb_str_replace(dup, str);
    return dup;
}


/*
 *  call-seq:
 *     String.new(str="")   => new_str
 *  
 *  Returns a new string object containing a copy of <i>str</i>.
 */

static VALUE
rb_str_init(argc, argv, str)
    int argc;
    VALUE *argv;
    VALUE str;
{
    VALUE orig;

    if (rb_scan_args(argc, argv, "01", &orig) == 1)
        rb_str_replace(str, orig);
    return str;
}

/*
 *  call-seq:
 *     str.length   => integer
 *  
 *  Returns the length of <i>str</i>.
 */

static VALUE
rb_str_length(str)
    VALUE str;
{
    return LONG2NUM(RSTRING(str)->len);
}

/*
 *  call-seq:
 *     str.empty?   => true or false
 *  
 *  Returns <code>true</code> if <i>str</i> has a length of zero.
 *     
 *     "hello".empty?   #=> false
 *     "".empty?        #=> true
 */

static VALUE
rb_str_empty(str)
    VALUE str;
{
    if (RSTRING(str)->len == 0)
        return Qtrue;
    return Qfalse;
}

/*
 *  call-seq:
 *     str + other_str   => new_str
 *  
 *  Concatenation---Returns a new <code>String</code> containing
 *  <i>other_str</i> concatenated to <i>str</i>.
 *     
 *     "Hello from " + self.to_s   #=> "Hello from main"
 */

VALUE
rb_str_plus(str1, str2)
    VALUE str1, str2;
{
    VALUE str3;

    StringValue(str2);
    str3 = rb_str_new(0, RSTRING(str1)->len+RSTRING(str2)->len);
    memcpy(RSTRING(str3)->ptr, RSTRING(str1)->ptr, RSTRING(str1)->len);
    memcpy(RSTRING(str3)->ptr + RSTRING(str1)->len,
           RSTRING(str2)->ptr, RSTRING(str2)->len);
    RSTRING(str3)->ptr[RSTRING(str3)->len] = '\0';

    if (OBJ_TAINTED(str1) || OBJ_TAINTED(str2))
        OBJ_TAINT(str3);
    return str3;
}

/*
 *  call-seq:
 *     str * integer   => new_str
 *  
 *  Copy---Returns a new <code>String</code> containing <i>integer</i> copies of
 *  the receiver.
 *     
 *     "Ho! " * 3   #=> "Ho! Ho! Ho! "
 */

VALUE
rb_str_times(str, times)
    VALUE str;
    VALUE times;
{
    VALUE str2;
    long i, len;

    len = NUM2LONG(times);
    if (len < 0) {
        rb_raise(rb_eArgError, "negative argument");
    }
    if (len && LONG_MAX/len <  RSTRING(str)->len) {
        rb_raise(rb_eArgError, "argument too big");
    }

    str2 = rb_str_new5(str,0, len *= RSTRING(str)->len);
    for (i = 0; i < len; i += RSTRING(str)->len) {
        memcpy(RSTRING(str2)->ptr + i,
               RSTRING(str)->ptr, RSTRING(str)->len);
    }
    RSTRING(str2)->ptr[RSTRING(str2)->len] = '\0';

    OBJ_INFECT(str2, str);

    return str2;
}

/*
 *  call-seq:
 *     str % arg   => new_str
 *  
 *  Format---Uses <i>str</i> as a format specification, and returns the result
 *  of applying it to <i>arg</i>. If the format specification contains more than
 *  one substitution, then <i>arg</i> must be an <code>Array</code> containing
 *  the values to be substituted. See <code>Kernel::sprintf</code> for details
 *  of the format string.
 *     
 *     "%05d" % 123                       #=> "00123"
 *     "%-5s: %08x" % [ "ID", self.id ]   #=> "ID   : 200e14d6"
 */

static VALUE
rb_str_format(str, arg)
    VALUE str, arg;
{
    VALUE *argv;

    if (TYPE(arg) == T_ARRAY) {
        argv = ALLOCA_N(VALUE, RARRAY(arg)->len + 1);
        argv[0] = str;
        MEMCPY(argv+1, RARRAY(arg)->ptr, VALUE, RARRAY(arg)->len);
        return rb_f_sprintf(RARRAY(arg)->len+1, argv);
    }

    argv = ALLOCA_N(VALUE, 2);
    argv[0] = str;
    argv[1] = arg;
    return rb_f_sprintf(2, argv);
}

static int
str_independent(str)
    VALUE str;
{
    if (FL_TEST(str, STR_TMPLOCK)) {
        rb_raise(rb_eRuntimeError, "can't modify string; temporarily locked");
    }
    if (OBJ_FROZEN(str)) rb_error_frozen("string");
    if (!OBJ_TAINTED(str) && rb_safe_level() >= 4)
        rb_raise(rb_eSecurityError, "Insecure: can't modify string");
    if (!FL_TEST(str, ELTS_SHARED)) return 1;
    return 0;
}

static void
str_make_independent(str)
    VALUE str;
{
    char *ptr;

    ptr = ALLOC_N(char, RSTRING(str)->len+1);
    if (RSTRING(str)->ptr) {
        memcpy(ptr, RSTRING(str)->ptr, RSTRING(str)->len);
    }
    ptr[RSTRING(str)->len] = 0;
    RSTRING(str)->ptr = ptr;
    RSTRING(str)->aux.capa = RSTRING(str)->len;
    FL_UNSET(str, STR_NOCAPA);
}

void
rb_str_modify(str)
    VALUE str;
{
    if (!str_independent(str))
        str_make_independent(str);
}

void
rb_str_associate(str, add)
    VALUE str, add;
{
    if (FL_TEST(str, STR_ASSOC)) {
        /* already associated */
        rb_ary_concat(RSTRING(str)->aux.shared, add);
    }
    else {
        if (FL_TEST(str, ELTS_SHARED)) {
            str_make_independent(str);
        }
        else if (RSTRING(str)->aux.capa != RSTRING(str)->len) {
            RESIZE_CAPA(str, RSTRING(str)->len);
        }
        RSTRING(str)->aux.shared = add;
        FL_SET(str, STR_ASSOC);
    }
}

VALUE
rb_str_associated(str)
    VALUE str;
{
    if (FL_TEST(str, STR_ASSOC)) {
        return RSTRING(str)->aux.shared;
    }
    return Qfalse;
}

static char *null_str = "";

VALUE
rb_string_value(ptr)
    volatile VALUE *ptr;
{
    VALUE s = *ptr;
    if (TYPE(s) != T_STRING) {
        s = rb_str_to_str(s);
        *ptr = s;
    }
    if (!RSTRING(s)->ptr) {
        FL_SET(s, ELTS_SHARED);
        RSTRING(s)->ptr = null_str;
    }
    return s;
}

char *
rb_string_value_ptr(ptr)
    volatile VALUE *ptr;
{
    return RSTRING(rb_string_value(ptr))->ptr;
}

char *
rb_string_value_cstr(ptr)
    volatile VALUE *ptr;
{
    VALUE str = rb_string_value(ptr);
    char *s = RSTRING(str)->ptr;

    if (!s || RSTRING(str)->len != strlen(s)) {
        rb_raise(rb_eArgError, "string contains null byte");
    }
    return s;
}

VALUE
rb_check_string_type(str)
    VALUE str;
{
    str = rb_check_convert_type(str, T_STRING, "String", "to_str");
    if (!NIL_P(str) && !RSTRING(str)->ptr) {
        FL_SET(str, ELTS_SHARED);
        RSTRING(str)->ptr = null_str;
    }
    return str;
}

VALUE
rb_str_substr(str, beg, len)
    VALUE str;
    long beg, len;
{
    VALUE str2;

    if (len < 0) return Qnil;
    if (beg > RSTRING(str)->len) return Qnil;
    if (beg < 0) {
        beg += RSTRING(str)->len;
        if (beg < 0) return Qnil;
    }
    if (beg + len > RSTRING(str)->len) {
        len = RSTRING(str)->len - beg;
    }
    if (len < 0) {
        len = 0;
    }
    if (len == 0) {
        str2 = rb_str_new5(str,0,0);
    }
    else if (len > sizeof(struct RString)/2 &&
        beg + len == RSTRING(str)->len && !FL_TEST(str, STR_ASSOC)) {
        str2 = rb_str_new3(rb_str_new4(str));
        RSTRING(str2)->ptr += RSTRING(str2)->len - len;
        RSTRING(str2)->len = len;
    }
    else {
        str2 = rb_str_new5(str, RSTRING(str)->ptr+beg, len);
    }
    OBJ_INFECT(str2, str);

    return str2;
}

VALUE
rb_str_freeze(str)
    VALUE str;
{
    return rb_obj_freeze(str);
}

VALUE
rb_str_dup_frozen(str)
    VALUE str;
{
    if (FL_TEST(str, ELTS_SHARED) && RSTRING(str)->aux.shared) {
        VALUE shared = RSTRING(str)->aux.shared;
        if (RSTRING(shared)->len == RSTRING(str)->len) {
            OBJ_FREEZE(shared);
            return shared;
        }
    }
    if (OBJ_FROZEN(str)) return str;
    str = rb_str_dup(str);
    OBJ_FREEZE(str);
    return str;
}

VALUE
rb_str_locktmp(str)
    VALUE str;
{
    if (FL_TEST(str, STR_TMPLOCK)) {
        rb_raise(rb_eRuntimeError, "temporal locking already locked string");
    }
    FL_SET(str, STR_TMPLOCK);
    return str;
}

VALUE
rb_str_unlocktmp(str)
    VALUE str;
{
    if (!FL_TEST(str, STR_TMPLOCK)) {
        rb_raise(rb_eRuntimeError, "temporal unlocking already unlocked string");
    }
    FL_UNSET(str, STR_TMPLOCK);
    return str;
}

VALUE
rb_str_resize(str, len)
    VALUE str;
    long len;
{
    if (len < 0) {
        rb_raise(rb_eArgError, "negative string size (or size too big)");
    }

    rb_str_modify(str);
    if (len != RSTRING(str)->len) {
        if (RSTRING(str)->len < len || RSTRING(str)->len - len > 1024) {
            REALLOC_N(RSTRING(str)->ptr, char, len+1);
            if (!FL_TEST(str, STR_NOCAPA)) {
                RSTRING(str)->aux.capa = len;
            }
        }
        RSTRING(str)->len = len;
        RSTRING(str)->ptr[len] = '\0';  /* sentinel */
    }
    return str;
}

VALUE
rb_str_buf_cat(str, ptr, len)
    VALUE str;
    const char *ptr;
    long len;
{
    long capa, total;

    if (len == 0) return str;
    if (len < 0) {
        rb_raise(rb_eArgError, "negative string size (or size too big)");
    }
    rb_str_modify(str);
    if (FL_TEST(str, STR_ASSOC)) {
        FL_UNSET(str, STR_ASSOC);
        capa = RSTRING(str)->aux.capa = RSTRING(str)->len;
    }
    else {
        capa = RSTRING(str)->aux.capa;
    }
    total = RSTRING(str)->len+len;
    if (capa <= total) {
        while (total > capa) {
            capa = (capa + 1) * 2;
        }
        RESIZE_CAPA(str, capa);
    }
    memcpy(RSTRING(str)->ptr + RSTRING(str)->len, ptr, len);
    RSTRING(str)->len = total;
    RSTRING(str)->ptr[total] = '\0'; /* sentinel */

    return str;
}

VALUE
rb_str_buf_cat2(str, ptr)
    VALUE str;
    const char *ptr;
{
    return rb_str_buf_cat(str, ptr, strlen(ptr));
}

VALUE
rb_str_cat(str, ptr, len)
    VALUE str;
    const char *ptr;
    long len;
{
    if (len < 0) {
        rb_raise(rb_eArgError, "negative string size (or size too big)");
    }
    if (FL_TEST(str, STR_ASSOC)) {
        rb_str_modify(str);
        REALLOC_N(RSTRING(str)->ptr, char, RSTRING(str)->len+len);
        memcpy(RSTRING(str)->ptr + RSTRING(str)->len, ptr, len);
        RSTRING(str)->len += len;
        RSTRING(str)->ptr[RSTRING(str)->len] = '\0'; /* sentinel */
        return str;
    }

    return rb_str_buf_cat(str, ptr, len);
}

VALUE
rb_str_cat2(str, ptr)
    VALUE str;
    const char *ptr;
{
    return rb_str_cat(str, ptr, strlen(ptr));
}

VALUE
rb_str_buf_append(str, str2)
    VALUE str, str2;
{
    long capa, len;

    rb_str_modify(str);
    if (FL_TEST(str, STR_ASSOC)) {
        FL_UNSET(str, STR_ASSOC);
        capa = RSTRING(str)->aux.capa = RSTRING(str)->len;
    }
    else {
        capa = RSTRING(str)->aux.capa;
    }
    len = RSTRING(str)->len+RSTRING(str2)->len;
    if (capa <= len) {
        while (len > capa) {
            capa = (capa + 1) * 2;
        }
        RESIZE_CAPA(str, capa);
    }
    memcpy(RSTRING(str)->ptr + RSTRING(str)->len,
           RSTRING(str2)->ptr, RSTRING(str2)->len);
    RSTRING(str)->len += RSTRING(str2)->len;
    RSTRING(str)->ptr[RSTRING(str)->len] = '\0'; /* sentinel */
    OBJ_INFECT(str, str2);

    return str;
}

VALUE
rb_str_append(str, str2)
    VALUE str, str2;
{
    StringValue(str2);
    rb_str_modify(str);
    if (RSTRING(str2)->len > 0) {
        if (FL_TEST(str, STR_ASSOC)) {
            long len = RSTRING(str)->len+RSTRING(str2)->len;
            REALLOC_N(RSTRING(str)->ptr, char, len+1);
            memcpy(RSTRING(str)->ptr + RSTRING(str)->len,
                   RSTRING(str2)->ptr, RSTRING(str2)->len);
            RSTRING(str)->ptr[len] = '\0'; /* sentinel */
            RSTRING(str)->len = len;
        }
        else {
            return rb_str_buf_append(str, str2);
        }
    }
    OBJ_INFECT(str, str2);
    return str;
}


/*
 *  call-seq:
 *     str << fixnum        => str
 *     str.concat(fixnum)   => str
 *     str << obj           => str
 *     str.concat(obj)      => str
 *  
 *  Append---Concatenates the given object to <i>str</i>. If the object is a
 *  <code>Fixnum</code> between 0 and 255, it is converted to a character before
 *  concatenation.
 *     
 *     a = "hello "
 *     a << "world"   #=> "hello world"
 *     a.concat(33)   #=> "hello world!"
 */

VALUE
rb_str_concat(str1, str2)
    VALUE str1, str2;
{
    if (FIXNUM_P(str2)) {
        int i = FIX2INT(str2);
        if (0 <= i && i <= 0xff) { /* byte */
            char c = i;
            return rb_str_cat(str1, &c, 1);
        }
    }
    str1 = rb_str_append(str1, str2);

    return str1;
}

int
rb_str_hash(str)
    VALUE str;
{
    register long len = RSTRING(str)->len;
    register char *p = RSTRING(str)->ptr;
    register int key = 0;

#ifdef HASH_ELFHASH
    register unsigned int g;

    while (len--) {
        key = (key << 4) + *p++;
        if (g = key & 0xF0000000)
            key ^= g >> 24;
        key &= ~g;
    }
#elif HASH_PERL
    while (len--) {
        key += *p++;
        key += (key << 10);
        key ^= (key >> 6);
    }
    key += (key << 3);
    key ^= (key >> 11);
    key += (key << 15);
#else
    while (len--) {
        key = key*65599 + *p;
        p++;
    }
    key = key + (key>>5);
#endif
    return key;
}

/*
 * call-seq:
 *    str.hash   => fixnum
 *
 * Return a hash based on the string's length and content.
 */

static VALUE
rb_str_hash_m(str)
    VALUE str;
{
    int key = rb_str_hash(str);
    return INT2FIX(key);
}

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

int
rb_str_cmp(str1, str2)
    VALUE str1, str2;
{
    long len;
    int retval;

    len = lesser(RSTRING(str1)->len, RSTRING(str2)->len);
    retval = rb_memcmp(RSTRING(str1)->ptr, RSTRING(str2)->ptr, len);
    if (retval == 0) {
        if (RSTRING(str1)->len == RSTRING(str2)->len) return 0;
        if (RSTRING(str1)->len > RSTRING(str2)->len) return 1;
        return -1;
    }
    if (retval > 0) return 1;
    return -1;
}


/*
 *  call-seq:
 *     str == obj   => true or false
 *  
 *  Equality---If <i>obj</i> is not a <code>String</code>, returns
 *  <code>false</code>. Otherwise, returns <code>true</code> if <i>str</i>
 *  <code><=></code> <i>obj</i> returns zero.
 */

static VALUE
rb_str_equal(str1, str2)
    VALUE str1, str2;
{
    if (str1 == str2) return Qtrue;
    if (TYPE(str2) != T_STRING) {
        if (!rb_respond_to(str2, rb_intern("to_str"))) {
            return Qfalse;
        }
        return rb_equal(str2, str1);
    }
    if (RSTRING(str1)->len == RSTRING(str2)->len &&
        rb_str_cmp(str1, str2) == 0) {
        return Qtrue;
    }
    return Qfalse;
}

#define IS_EVSTR(p,e) ((p) < (e) && (*(p) == '$' || *(p) == '@' || *(p) == '{'))

/*
 * call-seq:
 *   str.eql?(other)   => true or false
 *
 * Two strings are equal if the have the same length and content.
 */

static VALUE
rb_str_eql(str1, str2)
    VALUE str1, str2;
{
    if (TYPE(str2) != T_STRING || RSTRING(str1)->len != RSTRING(str2)->len)
        return Qfalse;

    if (memcmp(RSTRING(str1)->ptr, RSTRING(str2)->ptr,
               lesser(RSTRING(str1)->len, RSTRING(str2)->len)) == 0)
        return Qtrue;

    return Qfalse;
}

/*
 *  call-seq:
 *     str <=> other_str   => -1, 0, +1
 *  
 *  Comparison---Returns -1 if <i>other_str</i> is less than, 0 if
 *  <i>other_str</i> is equal to, and +1 if <i>other_str</i> is greater than
 *  <i>str</i>. If the strings are of different lengths, and the strings are
 *  equal when compared up to the shortest length, then the longer string is
 *  considered greater than the shorter one. If the variable <code>$=</code> is
 *  <code>false</code>, the comparison is based on comparing the binary values
 *  of each character in the string. In older versions of Ruby, setting
 *  <code>$=</code> allowed case-insensitive comparisons; this is now deprecated
 *  in favor of using <code>String#casecmp</code>.
 *
 *  <code><=></code> is the basis for the methods <code><</code>,
 *  <code><=</code>, <code>></code>, <code>>=</code>, and <code>between?</code>,
 *  included from module <code>Comparable</code>.  The method
 *  <code>String#==</code> does not use <code>Comparable#==</code>.
 *     
 *     "abcdef" <=> "abcde"     #=> 1
 *     "abcdef" <=> "abcdef"    #=> 0
 *     "abcdef" <=> "abcdefg"   #=> -1
 *     "abcdef" <=> "ABCDEF"    #=> 1
 */

static VALUE
rb_str_cmp_m(str1, str2)
    VALUE str1, str2;
{
    long result;

    if (TYPE(str2) != T_STRING) {
        if (!rb_respond_to(str2, rb_intern("to_str"))) {
            return Qnil;
        }
        else if (!rb_respond_to(str2, rb_intern("<=>"))) {
            return Qnil;
        }
        else {
            VALUE tmp = rb_funcall(str2, rb_intern("<=>"), 1, str1);

            if (NIL_P(tmp)) return Qnil;
            if (!FIXNUM_P(tmp)) {
                return rb_funcall(LONG2FIX(0), '-', 1, tmp);
            }
            result = -FIX2LONG(tmp);
        }
    }
    else {
        result = rb_str_cmp(str1, str2);
    }
    return LONG2NUM(result);
}

/*
 *  call-seq:
 *     str.casecmp(other_str)   => -1, 0, +1
 *  
 *  Case-insensitive version of <code>String#<=></code>.
 *     
 *     "abcdef".casecmp("abcde")     #=> 1
 *     "aBcDeF".casecmp("abcdef")    #=> 0
 *     "abcdef".casecmp("abcdefg")   #=> -1
 *     "abcdef".casecmp("ABCDEF")    #=> 0
 */

static VALUE
rb_str_casecmp(str1, str2)
    VALUE str1, str2;
{
    long len;
    int retval;

    StringValue(str2);
    len = lesser(RSTRING(str1)->len, RSTRING(str2)->len);
    retval = rb_memcicmp(RSTRING(str1)->ptr, RSTRING(str2)->ptr, len);
    if (retval == 0) {
        if (RSTRING(str1)->len == RSTRING(str2)->len) return INT2FIX(0);
        if (RSTRING(str1)->len > RSTRING(str2)->len) return INT2FIX(1);
        return INT2FIX(-1);
    }
    if (retval == 0) return INT2FIX(0);
    if (retval > 0) return INT2FIX(1);
    return INT2FIX(-1);
}

static long
rb_str_index(str, sub, offset)
    VALUE str, sub;
    long offset;
{
    long pos;

    if (offset < 0) {
        offset += RSTRING(str)->len;
        if (offset < 0) return -1;
    }
    if (RSTRING(str)->len - offset < RSTRING(sub)->len) return -1;
    if (RSTRING(sub)->len == 0) return offset;
    pos = rb_memsearch(RSTRING(sub)->ptr, RSTRING(sub)->len,
                       RSTRING(str)->ptr+offset, RSTRING(str)->len-offset);
    if (pos < 0) return pos;
    return pos + offset;
}


/*
 *  call-seq:
 *     str.index(substring [, offset])   => fixnum or nil
 *     str.index(fixnum [, offset])      => fixnum or nil
 *     str.index(regexp [, offset])      => fixnum or nil
 *  
 *  Returns the index of the first occurrence of the given <i>substring</i>,
 *  character (<i>fixnum</i>), or pattern (<i>regexp</i>) in <i>str</i>. Returns
 *  <code>nil</code> if not found. If the second parameter is present, it
 *  specifies the position in the string to begin the search.
 *     
 *     "hello".index('e')             #=> 1
 *     "hello".index('lo')            #=> 3
 *     "hello".index('a')             #=> nil
 *     "hello".index(101)             #=> 1
 *     "hello".index(/[aeiou]/, -3)   #=> 4
 */

static VALUE
rb_str_index_m(argc, argv, str)
    int argc;
    VALUE *argv;
    VALUE str;
{
    VALUE sub;
    VALUE initpos;
    long pos;

    if (rb_scan_args(argc, argv, "11", &sub, &initpos) == 2) {
        pos = NUM2LONG(initpos);
    }
    else {
        pos = 0;
    }
    if (pos < 0) {
        pos += RSTRING(str)->len;
        if (pos < 0) {
            if (TYPE(sub) == T_REGEXP) {
                rb_backref_set(Qnil);
            }
            return Qnil;
        }
    }

    switch (TYPE(sub)) {
      case T_REGEXP:
        pos = rb_reg_adjust_startpos(sub, str, pos, 0);
        pos = rb_reg_search(sub, str, pos, 0);
        break;

      case T_FIXNUM:
      {
          int c = FIX2INT(sub);
          long len = RSTRING(str)->len;
          unsigned char *p = RSTRING(str)->ptr;

          for (;pos<len;pos++) {
              if (p[pos] == c) return LONG2NUM(pos);
          }
          return Qnil;
      }

      default: {
          VALUE tmp;

          tmp = rb_check_string_type(sub);
          if (NIL_P(tmp)) {
              rb_raise(rb_eTypeError, "type mismatch: %s given",
                       rb_obj_classname(sub));
          }
          sub = tmp;
      }
        /* fall through */
      case T_STRING:
        pos = rb_str_index(str, sub, pos);
        break;
    }

    if (pos == -1) return Qnil;
    return LONG2NUM(pos);
}

static long
rb_str_rindex(str, sub, pos)
    VALUE str, sub;
    long pos;
{
    long len = RSTRING(sub)->len;
    char *s, *sbeg, *t;

    /* substring longer than string */
    if (RSTRING(str)->len < len) return -1;
    if (RSTRING(str)->len - pos < len) {
        pos = RSTRING(str)->len - len;
    }
    sbeg = RSTRING(str)->ptr;
    s = RSTRING(str)->ptr + pos;
    t = RSTRING(sub)->ptr;
    if (len) {
        while (sbeg <= s) {
            if (rb_memcmp(s, t, len) == 0) {
                return s - RSTRING(str)->ptr;
            }
            s--;
        }
        return -1;
    }
    else {
        return pos;
    }
}


/*
 *  call-seq:
 *     str.rindex(substring [, fixnum])   => fixnum or nil
 *     str.rindex(fixnum [, fixnum])   => fixnum or nil
 *     str.rindex(regexp [, fixnum])   => fixnum or nil
 *  
 *  Returns the index of the last occurrence of the given <i>substring</i>,
 *  character (<i>fixnum</i>), or pattern (<i>regexp</i>) in <i>str</i>. Returns
 *  <code>nil</code> if not found. If the second parameter is present, it
 *  specifies the position in the string to end the search---characters beyond
 *  this point will not be considered.
 *     
 *     "hello".rindex('e')             #=> 1
 *     "hello".rindex('l')             #=> 3
 *     "hello".rindex('a')             #=> nil
 *     "hello".rindex(101)             #=> 1
 *     "hello".rindex(/[aeiou]/, -2)   #=> 1
 */

static VALUE
rb_str_rindex_m(argc, argv, str)
    int argc;
    VALUE *argv;
    VALUE str;
{
    VALUE sub;
    VALUE position;
    long pos;

    if (rb_scan_args(argc, argv, "11", &sub, &position) == 2) {
        pos = NUM2LONG(position);
        if (pos < 0) {
            pos += RSTRING(str)->len;
            if (pos < 0) {
                if (TYPE(sub) == T_REGEXP) {
                    rb_backref_set(Qnil);
                }
                return Qnil;
            }
        }
        if (pos > RSTRING(str)->len) pos = RSTRING(str)->len;
    }
    else {
        pos = RSTRING(str)->len;
    }

    switch (TYPE(sub)) {
      case T_REGEXP:
        if (RREGEXP(sub)->len) {
            pos = rb_reg_adjust_startpos(sub, str, pos, 1);
            pos = rb_reg_search(sub, str, pos, 1);
        }
        if (pos >= 0) return LONG2NUM(pos);
        break;

      case T_STRING:
        pos = rb_str_rindex(str, sub, pos);
        if (pos >= 0) return LONG2NUM(pos);
        break;

      case T_FIXNUM:
      {
          int c = FIX2INT(sub);
          unsigned char *p = RSTRING(str)->ptr + pos;
          unsigned char *pbeg = RSTRING(str)->ptr;

          if (pos == RSTRING(str)->len) {
              if (pos == 0) return Qnil;
              --p;
          }
          while (pbeg <= p) {
              if (*p == c) return LONG2NUM((char*)p - RSTRING(str)->ptr);
              p--;
          }
          return Qnil;
      }

      default:
        rb_raise(rb_eTypeError, "type mismatch: %s given",
                 rb_obj_classname(sub));
    }
    return Qnil;
}

/*
 *  call-seq:
 *     str =~ obj   => fixnum or nil
 *  
 *  Match---If <i>obj</i> is a <code>Regexp</code>, use it as a pattern to match
 *  against <i>str</i>. If <i>obj</i> is a <code>String</code>, look for it in
 *  <i>str</i> (similar to <code>String#index</code>). Returns the position the
 *  match starts, or <code>nil</code> if there is no match. Otherwise, invokes
 *  <i>obj.=~</i>, passing <i>str</i> as an argument. The default
 *  <code>=~</code> in <code>Object</code> returns <code>false</code>.
 *     
 *     "cat o' 9 tails" =~ '\d'   #=> nil
 *     "cat o' 9 tails" =~ /\d/   #=> 7
 *     "cat o' 9 tails" =~ 9      #=> false
 */

static VALUE
rb_str_match(x, y)
    VALUE x, y;
{
    switch (TYPE(y)) {
      case T_STRING:
        rb_raise(rb_eTypeError, "type mismatch: String given");

      case T_REGEXP:
        return rb_reg_match(y, x);

      default:
        return rb_funcall(y, rb_intern("=~"), 1, x);
    }
}


static VALUE get_pat (VALUE, int);


/*
 *  call-seq:
 *     str.match(pattern)   => matchdata or nil
 *  
 *  Converts <i>pattern</i> to a <code>Regexp</code> (if it isn't already one),
 *  then invokes its <code>match</code> method on <i>str</i>.
 *     
 *     'hello'.match('(.)\1')      #=> #<MatchData:0x401b3d30>
 *     'hello'.match('(.)\1')[0]   #=> "ll"
 *     'hello'.match(/(.)\1/)[0]   #=> "ll"
 *     'hello'.match('xx')         #=> nil
 */

static VALUE
rb_str_match_m(str, re)
    VALUE str, re;
{
    return rb_funcall(get_pat(re, 0), rb_intern("match"), 1, str);
}

static char
succ_char(s)
    char *s;
{
    char c = *s;

    /* numerics */
    if ('0' <= c && c < '9') (*s)++;
    else if (c == '9') {
        *s = '0';
        return '1';
    }
    /* small alphabets */
    else if ('a' <= c && c < 'z') (*s)++;
    else if (c == 'z') {
        return *s = 'a';
    }
    /* capital alphabets */
    else if ('A' <= c && c < 'Z') (*s)++;
    else if (c == 'Z') {
        return *s = 'A';
    }
    return 0;
}


/*
 *  call-seq:
 *     str.succ   => new_str
 *     str.next   => new_str
 *  
 *  Returns the successor to <i>str</i>. The successor is calculated by
 *  incrementing characters starting from the rightmost alphanumeric (or
 *  the rightmost character if there are no alphanumerics) in the
 *  string. Incrementing a digit always results in another digit, and
 *  incrementing a letter results in another letter of the same case.
 *  Incrementing nonalphanumerics uses the underlying character set's
 *  collating sequence.
 *     
 *  If the increment generates a ``carry,'' the character to the left of
 *  it is incremented. This process repeats until there is no carry,
 *  adding an additional character if necessary.
 *     
 *     "abcd".succ        #=> "abce"
 *     "THX1138".succ     #=> "THX1139"
 *     "<<koala>>".succ   #=> "<<koalb>>"
 *     "1999zzz".succ     #=> "2000aaa"
 *     "ZZZ9999".succ     #=> "AAAA0000"
 *     "***".succ         #=> "**+"
 */

static VALUE
rb_str_succ(orig)
    VALUE orig;
{
    VALUE str;
    char *sbeg, *s;
    int c = -1;
    long n = 0;

    str = rb_str_new5(orig, RSTRING(orig)->ptr, RSTRING(orig)->len);
    OBJ_INFECT(str, orig);
    if (RSTRING(str)->len == 0) return str;

    sbeg = RSTRING(str)->ptr; s = sbeg + RSTRING(str)->len - 1;

    while (sbeg <= s) {
        if (ISALNUM(*s)) {
            if ((c = succ_char(s)) == 0) break;
            n = s - sbeg;
        }
        s--;
    }
    if (c == -1) {              /* str contains no alnum */
        sbeg = RSTRING(str)->ptr; s = sbeg + RSTRING(str)->len - 1;
        c = '\001';
        while (sbeg <= s) {
            if ((*s += 1) != 0) break;
            s--;
        }
    }
    if (s < sbeg) {
        RESIZE_CAPA(str, RSTRING(str)->len + 1);
        s = RSTRING(str)->ptr + n;
        memmove(s+1, s, RSTRING(str)->len - n);
        *s = c;
        RSTRING(str)->len += 1;
        RSTRING(str)->ptr[RSTRING(str)->len] = '\0';
    }

    return str;
}


/*
 *  call-seq:
 *     str.succ!   => str
 *     str.next!   => str
 *  
 *  Equivalent to <code>String#succ</code>, but modifies the receiver in
 *  place.
 */

static VALUE
rb_str_succ_bang(str)
    VALUE str;
{
    rb_str_shared_replace(str, rb_str_succ(str));

    return str;
}

VALUE
rb_str_upto(beg, end, excl)
    VALUE beg, end;
    int excl;
{
    VALUE current, after_end;
    ID succ = rb_intern("succ");
    int n;

    StringValue(end);
    n = rb_str_cmp(beg, end);
    if (n > 0 || (excl && n == 0)) return beg;
    after_end = rb_funcall(end, succ, 0, 0);
    current = beg;
    while (!rb_str_equal(current, after_end)) {
        rb_yield(current);
        if (!excl && rb_str_equal(current, end)) break;
        current = rb_funcall(current, succ, 0, 0);
        StringValue(current);
        if (excl && rb_str_equal(current, end)) break;
        StringValue(current);
        if (RSTRING(current)->len > RSTRING(end)->len)
            break;
    }

    return beg;
}


/*
 *  call-seq:
 *     str.upto(other_str) {|s| block }   => str
 *  
 *  Iterates through successive values, starting at <i>str</i> and
 *  ending at <i>other_str</i> inclusive, passing each value in turn to
 *  the block. The <code>String#succ</code> method is used to generate
 *  each value.
 *     
 *     "a8".upto("b6") {|s| print s, ' ' }
 *     for s in "a8".."b6"
 *       print s, ' '
 *     end
 *     
 *  <em>produces:</em>
 *     
 *     a8 a9 b0 b1 b2 b3 b4 b5 b6
 *     a8 a9 b0 b1 b2 b3 b4 b5 b6
 */

static VALUE
rb_str_upto_m(beg, end)
    VALUE beg, end;
{
    return rb_str_upto(beg, end, Qfalse);
}

static VALUE
rb_str_subpat(str, re, nth)
    VALUE str, re;
    int nth;
{
    if (rb_reg_search(re, str, 0, 0) >= 0) {
        return rb_reg_nth_match(nth, rb_backref_get());
    }
    return Qnil;
}

static VALUE
rb_str_aref(str, indx)
    VALUE str;
    VALUE indx;
{
    long idx;

    switch (TYPE(indx)) {
      case T_FIXNUM:
        idx = FIX2LONG(indx);

      num_index:
        if (idx < 0) {
            idx = RSTRING(str)->len + idx;
        }
        if (idx < 0 || RSTRING(str)->len <= idx) {
            return Qnil;
        }
        return INT2FIX(RSTRING(str)->ptr[idx] & 0xff);

      case T_REGEXP:
        return rb_str_subpat(str, indx, 0);

      case T_STRING:
        if (rb_str_index(str, indx, 0) != -1)
            return rb_str_dup(indx);
        return Qnil;

      default:
        /* check if indx is Range */
        {
            long beg, len;
            VALUE tmp;

            switch (rb_range_beg_len(indx, &beg, &len, RSTRING(str)->len, 0)) {
              case Qfalse:
                break;
              case Qnil:
                return Qnil;
              default:
                tmp = rb_str_substr(str, beg, len);
                OBJ_INFECT(tmp, indx);
                return tmp;
            }
        }
        idx = NUM2LONG(indx);
        goto num_index;
    }
    return Qnil;                /* not reached */
}


/*
 *  call-seq:
 *     str[fixnum]                 => fixnum or nil
 *     str[fixnum, fixnum]         => new_str or nil
 *     str[range]                  => new_str or nil
 *     str[regexp]                 => new_str or nil
 *     str[regexp, fixnum]         => new_str or nil
 *     str[other_str]              => new_str or nil
 *     str.slice(fixnum)           => fixnum or nil
 *     str.slice(fixnum, fixnum)   => new_str or nil
 *     str.slice(range)            => new_str or nil
 *     str.slice(regexp)           => new_str or nil
 *     str.slice(regexp, fixnum)   => new_str or nil
 *     str.slice(other_str)        => new_str or nil
 *  
 *  Element Reference---If passed a single <code>Fixnum</code>, returns the code
 *  of the character at that position. If passed two <code>Fixnum</code>
 *  objects, returns a substring starting at the offset given by the first, and
 *  a length given by the second. If given a range, a substring containing
 *  characters at offsets given by the range is returned. In all three cases, if
 *  an offset is negative, it is counted from the end of <i>str</i>. Returns
 *  <code>nil</code> if the initial offset falls outside the string, the length
 *  is negative, or the beginning of the range is greater than the end.
 *     
 *  If a <code>Regexp</code> is supplied, the matching portion of <i>str</i> is
 *  returned. If a numeric parameter follows the regular expression, that
 *  component of the <code>MatchData</code> is returned instead. If a
 *  <code>String</code> is given, that string is returned if it occurs in
 *  <i>str</i>. In both cases, <code>nil</code> is returned if there is no
 *  match.
 *     
 *     a = "hello there"
 *     a[1]                   #=> 101
 *     a[1,3]                 #=> "ell"
 *     a[1..3]                #=> "ell"
 *     a[-3,2]                #=> "er"
 *     a[-4..-2]              #=> "her"
 *     a[12..-1]              #=> nil
 *     a[-2..-4]              #=> ""
 *     a[/[aeiou](.)\1/]      #=> "ell"
 *     a[/[aeiou](.)\1/, 0]   #=> "ell"
 *     a[/[aeiou](.)\1/, 1]   #=> "l"
 *     a[/[aeiou](.)\1/, 2]   #=> nil
 *     a["lo"]                #=> "lo"
 *     a["bye"]               #=> nil
 */

static VALUE
rb_str_aref_m(argc, argv, str)
    int argc;
    VALUE *argv;
    VALUE str;
{
    if (argc == 2) {
        if (TYPE(argv[0]) == T_REGEXP) {
            return rb_str_subpat(str, argv[0], NUM2INT(argv[1]));
        }
        return rb_str_substr(str, NUM2LONG(argv[0]), NUM2LONG(argv[1]));
    }
    if (argc != 1) {
        rb_raise(rb_eArgError, "wrong number of arguments (%d for 1)", argc);
    }
    return rb_str_aref(str, argv[0]);
}

static void
rb_str_splice(str, beg, len, val)
    VALUE str;
    long beg, len;
    VALUE val;
{
    if (len < 0) rb_raise(rb_eIndexError, "negative length %ld", len);

    StringValue(val);
    rb_str_modify(str);

    if (RSTRING(str)->len < beg) {
      out_of_range:
        rb_raise(rb_eIndexError, "index %ld out of string", beg);
    }
    if (beg < 0) {
        if (-beg > RSTRING(str)->len) {
            goto out_of_range;
        }
        beg += RSTRING(str)->len;
    }
    if (RSTRING(str)->len < beg + len) {
        len = RSTRING(str)->len - beg;
    }

    if (len < RSTRIN