objstr.c

/*
 * This file is part of the MicroPython project, http://micropython.org/
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2013, 2014 Damien P. George
 * Copyright (c) 2014-2018 Paul Sokolovsky
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <string.h>
#include <assert.h>

#include "py/unicode.h"
#include "py/objstr.h"
#include "py/objlist.h"
#include "py/runtime.h"
#include "py/stackctrl.h"

#if MICROPY_PY_BUILTINS_STR_OP_MODULO
STATIC mp_obj_t str_modulo_format(mp_obj_t pattern, size_t n_args, const mp_obj_t *args, mp_obj_t dict);
#endif

STATIC mp_obj_t mp_obj_new_bytes_iterator(mp_obj_t str, mp_obj_iter_buf_t *iter_buf);
STATIC NORETURN void bad_implicit_conversion(mp_obj_t self_in);

/******************************************************************************/
/* str                                                                        */

void mp_str_print_quoted(const mp_print_t *print, const byte *str_data, size_t str_len, bool is_bytes) {
    // this escapes characters, but it will be very slow to print (calling print many times)
    bool has_single_quote = false;
    bool has_double_quote = false;
    for (const byte *s = str_data, *top = str_data + str_len; !has_double_quote && s < top; s++) {
        if (*s == '\'') {
            has_single_quote = true;
        } else if (*s == '"') {
            has_double_quote = true;
        }
    }
    int quote_char = '\'';
    if (has_single_quote && !has_double_quote) {
        quote_char = '"';
    }
    mp_printf(print, "%c", quote_char);
    for (const byte *s = str_data, *top = str_data + str_len; s < top; s++) {
        if (*s == quote_char) {
            mp_printf(print, "\\%c", quote_char);
        } else if (*s == '\\') {
            mp_print_str(print, "\\\\");
        } else if (*s >= 0x20 && *s != 0x7f && (!is_bytes || *s < 0x80)) {
            // In strings, anything which is not ascii control character
            // is printed as is, this includes characters in range 0x80-0xff
            // (which can be non-Latin letters, etc.)
            mp_printf(print, "%c", *s);
        } else if (*s == '\n') {
            mp_print_str(print, "\\n");
        } else if (*s == '\r') {
            mp_print_str(print, "\\r");
        } else if (*s == '\t') {
            mp_print_str(print, "\\t");
        } else {
            mp_printf(print, "\\x%02x", *s);
        }
    }
    mp_printf(print, "%c", quote_char);
}

#if MICROPY_PY_UJSON
void mp_str_print_json(const mp_print_t *print, const byte *str_data, size_t str_len) {
    // for JSON spec, see http://www.ietf.org/rfc/rfc4627.txt
    // if we are given a valid utf8-encoded string, we will print it in a JSON-conforming way
    mp_print_str(print, "\"");
    for (const byte *s = str_data, *top = str_data + str_len; s < top; s++) {
        if (*s == '"' || *s == '\\') {
            mp_printf(print, "\\%c", *s);
        } else if (*s >= 32) {
            // this will handle normal and utf-8 encoded chars
            mp_printf(print, "%c", *s);
        } else if (*s == '\n') {
            mp_print_str(print, "\\n");
        } else if (*s == '\r') {
            mp_print_str(print, "\\r");
        } else if (*s == '\t') {
            mp_print_str(print, "\\t");
        } else {
            // this will handle control chars
            mp_printf(print, "\\u%04x", *s);
        }
    }
    mp_print_str(print, "\"");
}
#endif

STATIC void str_print(const mp_print_t *print, mp_obj_t self_in, mp_print_kind_t kind) {
    GET_STR_DATA_LEN(self_in, str_data, str_len);
    #if MICROPY_PY_UJSON
    if (kind == PRINT_JSON) {
        mp_str_print_json(print, str_data, str_len);
        return;
    }
    #endif
    #if !MICROPY_PY_BUILTINS_STR_UNICODE
    bool is_bytes = mp_obj_is_type(self_in, &mp_type_bytes);
    #else
    bool is_bytes = true;
    #endif
    if (kind == PRINT_RAW || (!MICROPY_PY_BUILTINS_STR_UNICODE && kind == PRINT_STR && !is_bytes)) {
        mp_printf(print, "%.*s", str_len, str_data);
    } else {
        if (is_bytes) {
            mp_print_str(print, "b");
        }
        mp_str_print_quoted(print, str_data, str_len, is_bytes);
    }
}

mp_obj_t mp_obj_str_make_new(const mp_obj_type_t *type, size_t n_args, size_t n_kw, const mp_obj_t *args) {
#if MICROPY_CPYTHON_COMPAT
    if (n_kw != 0) {
        mp_arg_error_unimpl_kw();
    }
#endif

    mp_arg_check_num(n_args, n_kw, 0, 3, false);

    switch (n_args) {
        case 0:
            return MP_OBJ_NEW_QSTR(MP_QSTR_);

        case 1: {
            vstr_t vstr;
            mp_print_t print;
            vstr_init_print(&vstr, 16, &print);
            mp_obj_print_helper(&print, args[0], PRINT_STR);
            return mp_obj_new_str_from_vstr(type, &vstr);
        }

        default: // 2 or 3 args
            // TODO: validate 2nd/3rd args
            if (mp_obj_is_type(args[0], &mp_type_bytes)) {
                GET_STR_DATA_LEN(args[0], str_data, str_len);
                GET_STR_HASH(args[0], str_hash);
                if (str_hash == 0) {
                    str_hash = qstr_compute_hash(str_data, str_len);
                }
                #if MICROPY_PY_BUILTINS_STR_UNICODE_CHECK
                if (!utf8_check(str_data, str_len)) {
                    mp_raise_msg(&mp_type_UnicodeError, NULL);
                }
                #endif

                // Check if a qstr with this data already exists
                qstr q = qstr_find_strn((const char*)str_data, str_len);
                if (q != MP_QSTR_NULL) {
                    return MP_OBJ_NEW_QSTR(q);
                }

                mp_obj_str_t *o = MP_OBJ_TO_PTR(mp_obj_new_str_copy(type, NULL, str_len));
                o->data = str_data;
                o->hash = str_hash;
                return MP_OBJ_FROM_PTR(o);
            } else {
                mp_buffer_info_t bufinfo;
                mp_get_buffer_raise(args[0], &bufinfo, MP_BUFFER_READ);
                #if MICROPY_PY_BUILTINS_STR_UNICODE_CHECK
                if (!utf8_check(bufinfo.buf, bufinfo.len)) {
                    mp_raise_msg(&mp_type_UnicodeError, NULL);
                }
                #endif
                return mp_obj_new_str(bufinfo.buf, bufinfo.len);
            }
    }
}

STATIC mp_obj_t bytes_make_new(const mp_obj_type_t *type_in, size_t n_args, size_t n_kw, const mp_obj_t *args) {
    (void)type_in;

    #if MICROPY_CPYTHON_COMPAT
    if (n_kw != 0) {
        mp_arg_error_unimpl_kw();
    }
    #else
    (void)n_kw;
    #endif

    if (n_args == 0) {
        return mp_const_empty_bytes;
    }

    if (mp_obj_is_str(args[0])) {
        if (n_args < 2 || n_args > 3) {
            goto wrong_args;
        }
        GET_STR_DATA_LEN(args[0], str_data, str_len);
        GET_STR_HASH(args[0], str_hash);
        if (str_hash == 0) {
            str_hash = qstr_compute_hash(str_data, str_len);
        }
        mp_obj_str_t *o = MP_OBJ_TO_PTR(mp_obj_new_str_copy(&mp_type_bytes, NULL, str_len));
        o->data = str_data;
        o->hash = str_hash;
        return MP_OBJ_FROM_PTR(o);
    }

    if (n_args > 1) {
        goto wrong_args;
    }

    if (mp_obj_is_small_int(args[0])) {
        mp_int_t len = MP_OBJ_SMALL_INT_VALUE(args[0]);
        if (len < 0) {
            mp_raise_ValueError(NULL);
        }
        vstr_t vstr;
        vstr_init_len(&vstr, len);
        memset(vstr.buf, 0, len);
        return mp_obj_new_str_from_vstr(&mp_type_bytes, &vstr);
    }

    // check if argument has the buffer protocol
    mp_buffer_info_t bufinfo;
    if (mp_get_buffer(args[0], &bufinfo, MP_BUFFER_READ)) {
        return mp_obj_new_bytes(bufinfo.buf, bufinfo.len);
    }

    vstr_t vstr;
    // Try to create array of exact len if initializer len is known
    mp_obj_t len_in = mp_obj_len_maybe(args[0]);
    if (len_in == MP_OBJ_NULL) {
        vstr_init(&vstr, 16);
    } else {
        mp_int_t len = MP_OBJ_SMALL_INT_VALUE(len_in);
        vstr_init(&vstr, len);
    }

    mp_obj_iter_buf_t iter_buf;
    mp_obj_t iterable = mp_getiter(args[0], &iter_buf);
    mp_obj_t item;
    while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
        mp_int_t val = mp_obj_get_int(item);
        #if MICROPY_FULL_CHECKS
        if (val < 0 || val > 255) {
            mp_raise_ValueError("bytes value out of range");
        }
        #endif
        vstr_add_byte(&vstr, val);
    }

    return mp_obj_new_str_from_vstr(&mp_type_bytes, &vstr);

wrong_args:
    mp_raise_TypeError("wrong number of arguments");
}

// like strstr but with specified length and allows \0 bytes
// TODO replace with something more efficient/standard
const byte *find_subbytes(const byte *haystack, size_t hlen, const byte *needle, size_t nlen, int direction) {
    if (hlen >= nlen) {
        size_t str_index, str_index_end;
        if (direction > 0) {
            str_index = 0;
            str_index_end = hlen - nlen;
        } else {
            str_index = hlen - nlen;
            str_index_end = 0;
        }
        for (;;) {
            if (memcmp(&haystack[str_index], needle, nlen) == 0) {
                //found
                return haystack + str_index;
            }
            if (str_index == str_index_end) {
                //not found
                break;
            }
            str_index += direction;
        }
    }
    return NULL;
}

// Note: this function is used to check if an object is a str or bytes, which
// works because both those types use it as their binary_op method.  Revisit
// mp_obj_is_str_or_bytes if this fact changes.
mp_obj_t mp_obj_str_binary_op(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_in) {
    // check for modulo
    if (op == MP_BINARY_OP_MODULO) {
        #if MICROPY_PY_BUILTINS_STR_OP_MODULO
        mp_obj_t *args = &rhs_in;
        size_t n_args = 1;
        mp_obj_t dict = MP_OBJ_NULL;
        if (mp_obj_is_type(rhs_in, &mp_type_tuple)) {
            // TODO: Support tuple subclasses?
            mp_obj_tuple_get(rhs_in, &n_args, &args);
        } else if (mp_obj_is_type(rhs_in, &mp_type_dict)) {
            dict = rhs_in;
        }
        return str_modulo_format(lhs_in, n_args, args, dict);
        #else
        return MP_OBJ_NULL;
        #endif
    }

    // from now on we need lhs type and data, so extract them
    mp_obj_type_t *lhs_type = mp_obj_get_type(lhs_in);
    GET_STR_DATA_LEN(lhs_in, lhs_data, lhs_len);

    // check for multiply
    if (op == MP_BINARY_OP_MULTIPLY) {
        mp_int_t n;
        if (!mp_obj_get_int_maybe(rhs_in, &n)) {
            return MP_OBJ_NULL; // op not supported
        }
        if (n <= 0) {
            if (lhs_type == &mp_type_str) {
                return MP_OBJ_NEW_QSTR(MP_QSTR_); // empty str
            } else {
                return mp_const_empty_bytes;
            }
        }
        vstr_t vstr;
        vstr_init_len(&vstr, lhs_len * n);
        mp_seq_multiply(lhs_data, sizeof(*lhs_data), lhs_len, n, vstr.buf);
        return mp_obj_new_str_from_vstr(lhs_type, &vstr);
    }

    // From now on all operations allow:
    //    - str with str
    //    - bytes with bytes
    //    - bytes with bytearray
    //    - bytes with array.array
    // To do this efficiently we use the buffer protocol to extract the raw
    // data for the rhs, but only if the lhs is a bytes object.
    //
    // NOTE: CPython does not allow comparison between bytes ard array.array
    // (even if the array is of type 'b'), even though it allows addition of
    // such types.  We are not compatible with this (we do allow comparison
    // of bytes with anything that has the buffer protocol).  It would be
    // easy to "fix" this with a bit of extra logic below, but it costs code
    // size and execution time so we don't.

    const byte *rhs_data;
    size_t rhs_len;
    if (lhs_type == mp_obj_get_type(rhs_in)) {
        GET_STR_DATA_LEN(rhs_in, rhs_data_, rhs_len_);
        rhs_data = rhs_data_;
        rhs_len = rhs_len_;
    } else if (lhs_type == &mp_type_bytes) {
        mp_buffer_info_t bufinfo;
        if (!mp_get_buffer(rhs_in, &bufinfo, MP_BUFFER_READ)) {
            return MP_OBJ_NULL; // op not supported
        }
        rhs_data = bufinfo.buf;
        rhs_len = bufinfo.len;
    } else {
        // LHS is str and RHS has an incompatible type
        // (except if operation is EQUAL, but that's handled by mp_obj_equal)
        bad_implicit_conversion(rhs_in);
    }

    switch (op) {
        case MP_BINARY_OP_ADD:
        case MP_BINARY_OP_INPLACE_ADD: {
            if (lhs_len == 0 && mp_obj_get_type(rhs_in) == lhs_type) {
                return rhs_in;
            }
            if (rhs_len == 0) {
                return lhs_in;
            }

            vstr_t vstr;
            vstr_init_len(&vstr, lhs_len + rhs_len);
            memcpy(vstr.buf, lhs_data, lhs_len);
            memcpy(vstr.buf + lhs_len, rhs_data, rhs_len);
            return mp_obj_new_str_from_vstr(lhs_type, &vstr);
        }

        case MP_BINARY_OP_CONTAINS:
            return mp_obj_new_bool(find_subbytes(lhs_data, lhs_len, rhs_data, rhs_len, 1) != NULL);

        //case MP_BINARY_OP_NOT_EQUAL: // This is never passed here
        case MP_BINARY_OP_EQUAL: // This will be passed only for bytes, str is dealt with in mp_obj_equal()
        case MP_BINARY_OP_LESS:
        case MP_BINARY_OP_LESS_EQUAL:
        case MP_BINARY_OP_MORE:
        case MP_BINARY_OP_MORE_EQUAL:
            return mp_obj_new_bool(mp_seq_cmp_bytes(op, lhs_data, lhs_len, rhs_data, rhs_len));

        default:
            return MP_OBJ_NULL; // op not supported
    }
}

#if !MICROPY_PY_BUILTINS_STR_UNICODE
// objstrunicode defines own version
const byte *str_index_to_ptr(const mp_obj_type_t *type, const byte *self_data, size_t self_len,
                             mp_obj_t index, bool is_slice) {
    size_t index_val = mp_get_index(type, self_len, index, is_slice);
    return self_data + index_val;
}
#endif

// This is used for both bytes and 8-bit strings. This is not used for unicode strings.
STATIC mp_obj_t bytes_subscr(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
    mp_obj_type_t *type = mp_obj_get_type(self_in);
    GET_STR_DATA_LEN(self_in, self_data, self_len);
    if (value == MP_OBJ_SENTINEL) {
        // load
#if MICROPY_PY_BUILTINS_SLICE
        if (mp_obj_is_type(index, &mp_type_slice)) {
            mp_bound_slice_t slice;
            if (!mp_seq_get_fast_slice_indexes(self_len, index, &slice)) {
                mp_raise_NotImplementedError("only slices with step=1 (aka None) are supported");
            }
            return mp_obj_new_str_of_type(type, self_data + slice.start, slice.stop - slice.start);
        }
#endif
        size_t index_val = mp_get_index(type, self_len, index, false);
        // If we have unicode enabled the type will always be bytes, so take the short cut.
        if (MICROPY_PY_BUILTINS_STR_UNICODE || type == &mp_type_bytes) {
            return MP_OBJ_NEW_SMALL_INT(self_data[index_val]);
        } else {
            return mp_obj_new_str_via_qstr((char*)&self_data[index_val], 1);
        }
    } else {
        return MP_OBJ_NULL; // op not supported
    }
}

STATIC mp_obj_t str_join(mp_obj_t self_in, mp_obj_t arg) {
    mp_check_self(mp_obj_is_str_or_bytes(self_in));
    const mp_obj_type_t *self_type = mp_obj_get_type(self_in);

    // get separation string
    GET_STR_DATA_LEN(self_in, sep_str, sep_len);

    // process args
    size_t seq_len;
    mp_obj_t *seq_items;

    if (!mp_obj_is_type(arg, &mp_type_list) && !mp_obj_is_type(arg, &mp_type_tuple)) {
        // arg is not a list nor a tuple, try to convert it to a list
        // TODO: Try to optimize?
        arg = mp_type_list.make_new(&mp_type_list, 1, 0, &arg);
    }
    mp_obj_get_array(arg, &seq_len, &seq_items);

    // count required length
    size_t required_len = 0;
    for (size_t i = 0; i < seq_len; i++) {
        if (mp_obj_get_type(seq_items[i]) != self_type) {
            mp_raise_TypeError(
                "join expects a list of str/bytes objects consistent with self object");
        }
        if (i > 0) {
            required_len += sep_len;
        }
        GET_STR_LEN(seq_items[i], l);
        required_len += l;
    }

    // make joined string
    vstr_t vstr;
    vstr_init_len(&vstr, required_len);
    byte *data = (byte*)vstr.buf;
    for (size_t i = 0; i < seq_len; i++) {
        if (i > 0) {
            memcpy(data, sep_str, sep_len);
            data += sep_len;
        }
        GET_STR_DATA_LEN(seq_items[i], s, l);
        memcpy(data, s, l);
        data += l;
    }

    // return joined string
    return mp_obj_new_str_from_vstr(self_type, &vstr);
}
MP_DEFINE_CONST_FUN_OBJ_2(str_join_obj, str_join);

mp_obj_t mp_obj_str_split(size_t n_args, const mp_obj_t *args) {
    const mp_obj_type_t *self_type = mp_obj_get_type(args[0]);
    mp_int_t splits = -1;
    mp_obj_t sep = mp_const_none;
    if (n_args > 1) {
        sep = args[1];
        if (n_args > 2) {
            splits = mp_obj_get_int(args[2]);
        }
    }

    mp_obj_t res = mp_obj_new_list(0, NULL);
    GET_STR_DATA_LEN(args[0], s, len);
    const byte *top = s + len;

    if (sep == mp_const_none) {
        // sep not given, so separate on whitespace

        // Initial whitespace is not counted as split, so we pre-do it
        while (s < top && unichar_isspace(*s)) s++;
        while (s < top && splits != 0) {
            const byte *start = s;
            while (s < top && !unichar_isspace(*s)) s++;
            mp_obj_list_append(res, mp_obj_new_str_of_type(self_type, start, s - start));
            if (s >= top) {
                break;
            }
            while (s < top && unichar_isspace(*s)) s++;
            if (splits > 0) {
                splits--;
            }
        }

        if (s < top) {
            mp_obj_list_append(res, mp_obj_new_str_of_type(self_type, s, top - s));
        }

    } else {
        // sep given
        if (mp_obj_get_type(sep) != self_type) {
            bad_implicit_conversion(sep);
        }

        size_t sep_len;
        const char *sep_str = mp_obj_str_get_data(sep, &sep_len);

        if (sep_len == 0) {
            mp_raise_ValueError("empty separator");
        }

        for (;;) {
            const byte *start = s;
            for (;;) {
                if (splits == 0 || s + sep_len > top) {
                    s = top;
                    break;
                } else if (memcmp(s, sep_str, sep_len) == 0) {
                    break;
                }
                s++;
            }
            mp_obj_list_append(res, mp_obj_new_str_of_type(self_type, start, s - start));
            if (s >= top) {
                break;
            }
            s += sep_len;
            if (splits > 0) {
                splits--;
            }
        }
    }

    return res;
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_split_obj, 1, 3, mp_obj_str_split);

#if MICROPY_PY_BUILTINS_STR_SPLITLINES
STATIC mp_obj_t str_splitlines(size_t n_args, const mp_obj_t *pos_args, mp_map_t *kw_args) {
    enum { ARG_keepends };
    static const mp_arg_t allowed_args[] = {
        { MP_QSTR_keepends, MP_ARG_BOOL, {.u_bool = false} },
    };

    // parse args
    mp_arg_val_t args[MP_ARRAY_SIZE(allowed_args)];
    mp_arg_parse_all(n_args - 1, pos_args + 1, kw_args, MP_ARRAY_SIZE(allowed_args), allowed_args, args);

    const mp_obj_type_t *self_type = mp_obj_get_type(pos_args[0]);
    mp_obj_t res = mp_obj_new_list(0, NULL);

    GET_STR_DATA_LEN(pos_args[0], s, len);
    const byte *top = s + len;

    while (s < top) {
        const byte *start = s;
        size_t match = 0;
        while (s < top) {
            if (*s == '\n') {
                match = 1;
                break;
            } else if (*s == '\r') {
                if (s[1] == '\n') {
                    match = 2;
                } else {
                    match = 1;
                }
                break;
            }
            s++;
        }
        size_t sub_len = s - start;
        if (args[ARG_keepends].u_bool) {
            sub_len += match;
        }
        mp_obj_list_append(res, mp_obj_new_str_of_type(self_type, start, sub_len));
        s += match;
    }

    return res;
}
MP_DEFINE_CONST_FUN_OBJ_KW(str_splitlines_obj, 1, str_splitlines);
#endif

STATIC mp_obj_t str_rsplit(size_t n_args, const mp_obj_t *args) {
    if (n_args < 3) {
        // If we don't have split limit, it doesn't matter from which side
        // we split.
        return mp_obj_str_split(n_args, args);
    }
    const mp_obj_type_t *self_type = mp_obj_get_type(args[0]);
    mp_obj_t sep = args[1];
    GET_STR_DATA_LEN(args[0], s, len);

    mp_int_t splits = mp_obj_get_int(args[2]);
    if (splits < 0) {
        // Negative limit means no limit, so delegate to split().
        return mp_obj_str_split(n_args, args);
    }

    mp_int_t org_splits = splits;
    // Preallocate list to the max expected # of elements, as we
    // will fill it from the end.
    mp_obj_list_t *res = MP_OBJ_TO_PTR(mp_obj_new_list(splits + 1, NULL));
    mp_int_t idx = splits;

    if (sep == mp_const_none) {
        mp_raise_NotImplementedError("rsplit(None,n)");
    } else {
        size_t sep_len;
        const char *sep_str = mp_obj_str_get_data(sep, &sep_len);

        if (sep_len == 0) {
            mp_raise_ValueError("empty separator");
        }

        const byte *beg = s;
        const byte *last = s + len;
        for (;;) {
            s = last - sep_len;
            for (;;) {
                if (splits == 0 || s < beg) {
                    break;
                } else if (memcmp(s, sep_str, sep_len) == 0) {
                    break;
                }
                s--;
            }
            if (s < beg || splits == 0) {
                res->items[idx] = mp_obj_new_str_of_type(self_type, beg, last - beg);
                break;
            }
            res->items[idx--] = mp_obj_new_str_of_type(self_type, s + sep_len, last - s - sep_len);
            last = s;
            splits--;
        }
        if (idx != 0) {
            // We split less parts than split limit, now go cleanup surplus
            size_t used = org_splits + 1 - idx;
            memmove(res->items, &res->items[idx], used * sizeof(mp_obj_t));
            mp_seq_clear(res->items, used, res->alloc, sizeof(*res->items));
            res->len = used;
        }
    }

    return MP_OBJ_FROM_PTR(res);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_rsplit_obj, 1, 3, str_rsplit);

STATIC mp_obj_t str_finder(size_t n_args, const mp_obj_t *args, int direction, bool is_index) {
    const mp_obj_type_t *self_type = mp_obj_get_type(args[0]);
    mp_check_self(mp_obj_is_str_or_bytes(args[0]));

    // check argument type
    if (mp_obj_get_type(args[1]) != self_type) {
        bad_implicit_conversion(args[1]);
    }

    GET_STR_DATA_LEN(args[0], haystack, haystack_len);
    GET_STR_DATA_LEN(args[1], needle, needle_len);

    const byte *start = haystack;
    const byte *end = haystack + haystack_len;
    if (n_args >= 3 && args[2] != mp_const_none) {
        start = str_index_to_ptr(self_type, haystack, haystack_len, args[2], true);
    }
    if (n_args >= 4 && args[3] != mp_const_none) {
        end = str_index_to_ptr(self_type, haystack, haystack_len, args[3], true);
    }

    if (end < start) {
        goto out_error;
    }

    const byte *p = find_subbytes(start, end - start, needle, needle_len, direction);
    if (p == NULL) {
    out_error:
        // not found
        if (is_index) {
            mp_raise_ValueError("substring not found");
        } else {
            return MP_OBJ_NEW_SMALL_INT(-1);
        }
    } else {
        // found
        #if MICROPY_PY_BUILTINS_STR_UNICODE
        if (self_type == &mp_type_str) {
            return MP_OBJ_NEW_SMALL_INT(utf8_ptr_to_index(haystack, p));
        }
        #endif
        return MP_OBJ_NEW_SMALL_INT(p - haystack);
    }
}

STATIC mp_obj_t str_find(size_t n_args, const mp_obj_t *args) {
    return str_finder(n_args, args, 1, false);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_find_obj, 2, 4, str_find);

STATIC mp_obj_t str_rfind(size_t n_args, const mp_obj_t *args) {
    return str_finder(n_args, args, -1, false);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_rfind_obj, 2, 4, str_rfind);

STATIC mp_obj_t str_index(size_t n_args, const mp_obj_t *args) {
    return str_finder(n_args, args, 1, true);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_index_obj, 2, 4, str_index);

STATIC mp_obj_t str_rindex(size_t n_args, const mp_obj_t *args) {
    return str_finder(n_args, args, -1, true);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_rindex_obj, 2, 4, str_rindex);

// TODO: (Much) more variety in args
STATIC mp_obj_t str_startswith(size_t n_args, const mp_obj_t *args) {
    const mp_obj_type_t *self_type = mp_obj_get_type(args[0]);
    GET_STR_DATA_LEN(args[0], str, str_len);
    size_t prefix_len;
    const char *prefix = mp_obj_str_get_data(args[1], &prefix_len);
    const byte *start = str;
    if (n_args > 2) {
        start = str_index_to_ptr(self_type, str, str_len, args[2], true);
    }
    if (prefix_len + (start - str) > str_len) {
        return mp_const_false;
    }
    return mp_obj_new_bool(memcmp(start, prefix, prefix_len) == 0);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_startswith_obj, 2, 3, str_startswith);

STATIC mp_obj_t str_endswith(size_t n_args, const mp_obj_t *args) {
    GET_STR_DATA_LEN(args[0], str, str_len);
    size_t suffix_len;
    const char *suffix = mp_obj_str_get_data(args[1], &suffix_len);
    if (n_args > 2) {
        mp_raise_NotImplementedError("start/end indices");
    }

    if (suffix_len > str_len) {
        return mp_const_false;
    }
    return mp_obj_new_bool(memcmp(str + (str_len - suffix_len), suffix, suffix_len) == 0);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_endswith_obj, 2, 3, str_endswith);

enum { LSTRIP, RSTRIP, STRIP };

STATIC mp_obj_t str_uni_strip(int type, size_t n_args, const mp_obj_t *args) {
    mp_check_self(mp_obj_is_str_or_bytes(args[0]));
    const mp_obj_type_t *self_type = mp_obj_get_type(args[0]);

    const byte *chars_to_del;
    uint chars_to_del_len;
    static const byte whitespace[] = " \t\n\r\v\f";

    if (n_args == 1) {
        chars_to_del = whitespace;
        chars_to_del_len = sizeof(whitespace) - 1;
    } else {
        if (mp_obj_get_type(args[1]) != self_type) {
            bad_implicit_conversion(args[1]);
        }
        GET_STR_DATA_LEN(args[1], s, l);
        chars_to_del = s;
        chars_to_del_len = l;
    }

    GET_STR_DATA_LEN(args[0], orig_str, orig_str_len);

    size_t first_good_char_pos = 0;
    bool first_good_char_pos_set = false;
    size_t last_good_char_pos = 0;
    size_t i = 0;
    int delta = 1;
    if (type == RSTRIP) {
        i = orig_str_len - 1;
        delta = -1;
    }
    for (size_t len = orig_str_len; len > 0; len--) {
        if (find_subbytes(chars_to_del, chars_to_del_len, &orig_str[i], 1, 1) == NULL) {
            if (!first_good_char_pos_set) {
                first_good_char_pos_set = true;
                first_good_char_pos = i;
                if (type == LSTRIP) {
                    last_good_char_pos = orig_str_len - 1;
                    break;
                } else if (type == RSTRIP) {
                    first_good_char_pos = 0;
                    last_good_char_pos = i;
                    break;
                }
            }
            last_good_char_pos = i;
        }
        i += delta;
    }

    if (!first_good_char_pos_set) {
        // string is all whitespace, return ''
        if (self_type == &mp_type_str) {
            return MP_OBJ_NEW_QSTR(MP_QSTR_);
        } else {
            return mp_const_empty_bytes;
        }
    }

    assert(last_good_char_pos >= first_good_char_pos);
    //+1 to accommodate the last character
    size_t stripped_len = last_good_char_pos - first_good_char_pos + 1;
    if (stripped_len == orig_str_len) {
        // If nothing was stripped, don't bother to dup original string
        // TODO: watch out for this case when we'll get to bytearray.strip()
        assert(first_good_char_pos == 0);
        return args[0];
    }
    return mp_obj_new_str_of_type(self_type, orig_str + first_good_char_pos, stripped_len);
}

STATIC mp_obj_t str_strip(size_t n_args, const mp_obj_t *args) {
    return str_uni_strip(STRIP, n_args, args);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_strip_obj, 1, 2, str_strip);

STATIC mp_obj_t str_lstrip(size_t n_args, const mp_obj_t *args) {
    return str_uni_strip(LSTRIP, n_args, args);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_lstrip_obj, 1, 2, str_lstrip);

STATIC mp_obj_t str_rstrip(size_t n_args, const mp_obj_t *args) {
    return str_uni_strip(RSTRIP, n_args, args);
}
MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(str_rstrip_obj, 1, 2, str_rstrip);

#if MICROPY_PY_BUILTINS_STR_CENTER
STATIC mp_obj_t str_center(mp_obj_t str_in, mp_obj_t width_in) {
    GET_STR_DATA_LEN(str_in, str, str_len);
    mp_uint_t width = mp_obj_get_int(width_in);
    if (str_len >= width) {
        return str_in;
    }

    vstr_t vstr;
    vstr_init_len(&vstr, width);
    memset(vstr.buf, ' ', width);
    int left = (width - str_len) / 2;
    memcpy(vstr.buf + left, str, str_len);
    return mp_obj_new_str_from_vstr(mp_obj_get_type(str_in), &vstr);
}
MP_DEFINE_CONST_FUN_OBJ_2(str_center_obj, str_center);
#endif

// Takes an int arg, but only parses unsigned numbers, and only changes
// *num if at least one digit was parsed.
STATIC const char *str_to_int(const char *str, const char *top, int *num) {
    if (str < top && '0' <= *str && *str <= '9') {
        *num = 0;
        do {
            *num = *num * 10 + (*str - '0');
            str++;
        }
        while (str < top && '0' <= *str && *str <= '9');
    }
    return str;
}

STATIC bool isalignment(char ch) {
    return ch && strchr("<>=^", ch) != NULL;
}

STATIC bool istype(char ch) {
    return ch && strchr("bcdeEfFgGnosxX%", ch) != NULL;
}

STATIC bool arg_looks_integer(mp_obj_t arg) {
    return mp_obj_is_type(arg, &mp_type_bool) || mp_obj_is_int(arg);
}

STATIC bool arg_looks_numeric(mp_obj_t arg) {
    return arg_looks_integer(arg)
#if MICROPY_PY_BUILTINS_FLOAT
        || mp_obj_is_float(arg)
#endif
    ;
}

#if MICROPY_PY_BUILTINS_STR_OP_MODULO
STATIC mp_obj_t arg_as_int(mp_obj_t arg) {
#if MICROPY_PY_BUILTINS_FLOAT
    if (mp_obj_is_float(arg)) {
        return mp_obj_new_int_from_float(mp_obj_float_get(arg));
    }
#endif
    return arg;
}
#endif

#if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
STATIC NORETURN void terse_str_format_value_error(void) {
    mp_raise_ValueError("bad format string");
}
#else
// define to nothing to improve coverage
#define terse_str_format_value_error()
#endif

STATIC vstr_t mp_obj_str_format_helper(const char *str, const char *top, int *arg_i, size_t n_args, const mp_obj_t *args, mp_map_t *kwargs) {
    vstr_t vstr;
    mp_print_t print;
    vstr_init_print(&vstr, 16, &print);

    for (; str < top; str++) {
        if (*str == '}') {
            str++;
            if (str < top && *str == '}') {
                vstr_add_byte(&vstr, '}');
                continue;
            }
            if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
                terse_str_format_value_error();
            } else {
                mp_raise_ValueError("single '}' encountered in format string");
            }
        }
        if (*str != '{') {
            vstr_add_byte(&vstr, *str);
            continue;
        }

        str++;
        if (str < top && *str == '{') {
            vstr_add_byte(&vstr, '{');
            continue;
        }

        // replacement_field ::=  "{" [field_name] ["!" conversion] [":" format_spec] "}"

        const char *field_name = NULL;
        const char *field_name_top = NULL;
        char conversion = '\0';
        const char *format_spec = NULL;

        if (str < top && *str != '}' && *str != '!' && *str != ':') {
            field_name = (const char *)str;
            while (str < top && *str != '}' && *str != '!' && *str != ':') {
                ++str;
            }
            field_name_top = (const char *)str;
        }

        // conversion ::=  "r" | "s"

        if (str < top && *str == '!') {
            str++;
            if (str < top && (*str == 'r' || *str == 's')) {
                conversion = *str++;
            } else {
                if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
                    terse_str_format_value_error();
                } else if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_NORMAL) {
                    mp_raise_ValueError("bad conversion specifier");
                } else {
                    if (str >= top) {