stringutils.cpp

/*
 * SPDX-FileCopyrightText: 2015-2017 CSSlayer <wengxt@gmail.com>
 *
 * SPDX-License-Identifier: LGPL-2.1-or-later
 *
 */
#include "stringutils.h"
#include <array>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cstring>
#include <initializer_list>
#include <limits>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
#include <fcitx-utils/fcitxutils_export.h>
#include "charutils.h"
#include "macros.h"

namespace fcitx::stringutils {
namespace details {

std::string
concatPieces(std::initializer_list<std::pair<const char *, std::size_t>> list) {
    std::size_t size = 0;
    for (auto pair : list) {
        size += pair.second;
    }
    std::string result;
    result.reserve(size);
    for (const auto &pair : list) {
        result.append(pair.first, pair.first + pair.second);
    }
    assert(result.size() == size);
    return result;
}

std::string concatPathPieces(
    std::initializer_list<std::pair<const char *, std::size_t>> list) {
    if (!list.size()) {
        return {};
    }

    bool first = true;
    bool firstPieceIsSlash = false;
    std::size_t size = 0;
    for (const auto &pair : list) {
        if (first) {
            if (pair.first[pair.second - 1] == '/') {
                firstPieceIsSlash = true;
            }
            first = false;
        } else {
            size += 1;
        }
        size += pair.second;
    }
    if (list.size() > 1 && firstPieceIsSlash) {
        size -= 1;
    }
    std::string result;
    result.reserve(size);
    first = true;
    for (auto pair : list) {
        if (first) {
            first = false;
        } else if (firstPieceIsSlash) {
            firstPieceIsSlash = false;
        } else {
            result += '/';
        }

        result.append(pair.first, pair.first + pair.second);
    }
    assert(result.size() == size);
    return result;
}
} // namespace details

namespace {

constexpr std::array<char, std::numeric_limits<uint8_t>::max()> escapeMap =
    []() consteval {
        std::array<char, std::numeric_limits<uint8_t>::max()> table{};
        table.fill('\0');
        table['\\'] = '\\';
        table['"'] = '"';
        table['\n'] = 'n';
        table['\f'] = 'f';
        table['\r'] = 'r';
        table['\t'] = 't';
        table['\v'] = 'v';
        return table;
    }();

constexpr std::array<char, std::numeric_limits<uint8_t>::max()> unescapeMap =
    []() consteval {
        std::array<char, std::numeric_limits<uint8_t>::max()> table{};
        table.fill('\0');
        table['\\'] = '\\';
        table['"'] = '"';
        table['n'] = '\n';
        table['f'] = '\f';
        table['r'] = '\r';
        table['t'] = '\t';
        table['v'] = '\v';
        return table;
    }();

} // namespace

FCITXUTILS_DEPRECATED_EXPORT bool startsWith(const std::string &str,
                                             const std::string &prefix) {
    return str.starts_with(prefix);
}

bool startsWith(std::string_view str, std::string_view prefix) {
    return str.starts_with(prefix);
}

FCITXUTILS_DEPRECATED_EXPORT bool endsWith(const std::string &str,
                                           const std::string &suffix) {
    return str.ends_with(suffix);
}

bool endsWith(std::string_view str, std::string_view suffix) {
    return str.ends_with(suffix);
}

inline std::pair<std::string::size_type, std::string::size_type>
trimInplaceImpl(std::string_view str) {
    auto start = str.find_first_not_of(FCITX_WHITESPACE);
    if (start == std::string::npos) {
        return {str.size(), str.size()};
    }

    auto end = str.size();
    while (end > start && charutils::isspace(str[end - 1])) {
        --end;
    }

    return {start, end};
}

FCITXUTILS_DEPRECATED_EXPORT
std::pair<std::string::size_type, std::string::size_type>
trimInplace(const std::string &str) {
    return trimInplaceImpl(str);
}

std::pair<std::string::size_type, std::string::size_type>
trimInplace(std::string_view str) {
    return trimInplaceImpl(str);
}

FCITXUTILS_DEPRECATED_EXPORT
std::string trim(const std::string &str) { return trim(std::string_view(str)); }

std::string trim(std::string_view str) {
    auto pair = trimInplaceImpl(str);
    return {str.begin() + pair.first, str.begin() + pair.second};
}

std::string_view trimView(std::string_view str) {
    auto pair = trimInplace(str);
    return str.substr(pair.first, pair.second - pair.first);
}

FCITXUTILS_DEPRECATED_EXPORT
std::vector<std::string> split(const std::string &str, const std::string &delim,
                               SplitBehavior behavior) {
    return split(std::string_view(str), std::string_view(delim), behavior);
}

std::vector<std::string> split(std::string_view str, std::string_view delim,
                               SplitBehavior behavior) {
    std::vector<std::string> strings;
    std::string::size_type lastPos;
    std::string::size_type pos;
    if (behavior == SplitBehavior::SkipEmpty) {
        lastPos = str.find_first_not_of(delim, 0);
    } else {
        lastPos = 0;
    }
    pos = str.find_first_of(delim, lastPos);

    while (std::string::npos != pos || std::string::npos != lastPos) {
        strings.push_back(std::string(str.substr(lastPos, pos - lastPos)));
        if (behavior == SplitBehavior::SkipEmpty) {
            lastPos = str.find_first_not_of(delim, pos);
        } else {
            if (pos == std::string::npos) {
                break;
            }
            lastPos = pos + 1;
        }
        pos = str.find_first_of(delim, lastPos);
    }

    return strings;
}

FCITXUTILS_DEPRECATED_EXPORT std::vector<std::string>
split(const std::string &str, const std::string &delim) {
    return split(std::string_view(str), std::string_view(delim));
}

std::vector<std::string> split(std::string_view str, std::string_view delim) {
    return split(str, delim, SplitBehavior::SkipEmpty);
}

std::string replaceAll(std::string str, const std::string &before,
                       const std::string &after) {
    if (before.empty()) {
        return str;
    }

    constexpr int MAX_REPLACE_INDICES_NUM = 128;

    size_t pivot = 0;
    std::string newString;
    size_t lastLen = 0;
    size_t indices[MAX_REPLACE_INDICES_NUM];

    size_t newStringPos = 0;
    size_t oldStringPos = 0;

    auto copyAndMoveOn = [&newString, &newStringPos](std::string_view source,
                                                     size_t pos,
                                                     size_t length) {
        if (length == 0) {
            return;
        }
        // Append source[pos..pos+length] to newString.
        newString.replace(newStringPos, length, source, pos, length);
        newStringPos += length;
    };

    do {

        int nIndices = 0;
        while (nIndices < MAX_REPLACE_INDICES_NUM) {
            pivot = str.find(before, pivot);
            if (pivot == std::string::npos) {
                break;
            }

            indices[nIndices++] = pivot;
            pivot += before.size();
        }

        if (nIndices) {
            if (!lastLen) {
                lastLen = str.size() + nIndices * after.size() -
                          nIndices * before.size();
                newString.resize(lastLen);
            } else {
                size_t newLen = lastLen + nIndices * after.size() -
                                nIndices * before.size();
                lastLen = newLen;
                newString.resize(newLen);
            }

            // string s is split as
            // oldStringPos, indices[0], indices[0] + before.size(), indices[1],
            // indices[1] + before.size()
            // .... indices[nIndices - 1], indices[nIndices - 1] + before.size()
            copyAndMoveOn(str, oldStringPos, indices[0] - oldStringPos);
            copyAndMoveOn(after, 0, after.size());

            for (int i = 1; i < nIndices; i++) {
                copyAndMoveOn(str, indices[i - 1] + before.size(),
                              indices[i] - (indices[i - 1] + before.size()));
                copyAndMoveOn(after, 0, after.size());
            }

            oldStringPos = indices[nIndices - 1] + before.size();
        }
    } while (pivot != std::string::npos);

    if (!lastLen) {
        return str;
    }

    copyAndMoveOn(str, oldStringPos, str.size() - oldStringPos);
    newString.resize(newStringPos);

    return newString;
}

#define REHASH(a)                                                              \
    if (ol_minus_1 < sizeof(unsigned int) * CHAR_BIT)                          \
        hashHaystack -= (a) << ol_minus_1;                                     \
    hashHaystack <<= 1

const char *backwardSearch(const char *haystack, size_t l, const char *needle,
                           size_t ol, size_t from) {
    if (ol > l) {
        return nullptr;
    }
    size_t delta = l - ol;
    if (from > l) {
        return nullptr;
    }
    if (from > delta) {
        from = delta;
    }

    const char *end = haystack;
    haystack += from;
    const unsigned int ol_minus_1 = ol - 1;
    const char *n = needle + ol_minus_1;
    const char *h = haystack + ol_minus_1;
    unsigned int hashNeedle = 0;
    unsigned int hashHaystack = 0;
    size_t idx;
    for (idx = 0; idx < ol; ++idx) {
        hashNeedle = ((hashNeedle << 1) + *(n - idx));
        hashHaystack = ((hashHaystack << 1) + *(h - idx));
    }
    hashHaystack -= *haystack;
    while (haystack >= end) {
        hashHaystack += *haystack;
        if (hashHaystack == hashNeedle && memcmp(needle, haystack, ol) == 0) {
            return haystack;
        }
        --haystack;
        REHASH(*(haystack + ol));
    }
    return nullptr;
}

char *backwardSearch(char *haystack, size_t l, const char *needle, size_t ol,
                     size_t from) {
    return const_cast<char *>(backwardSearch(
        static_cast<const char *>(haystack), l, needle, ol, from));
}

size_t backwardSearch(const std::string &haystack, const std::string &needle,
                      size_t from) {
    const auto *cstr = haystack.c_str();
    const auto *result = backwardSearch(cstr, haystack.size(), needle.c_str(),
                                        needle.size(), from);
    if (result) {
        return result - cstr;
    }
    return std::string::npos;
}

enum class UnescapeState { NORMAL, ESCAPE };

bool unescape(std::string &str, bool unescapeQuote) {
    if (str.empty()) {
        return true;
    }

    size_t i = 0;
    size_t j = 0;
    UnescapeState state = UnescapeState::NORMAL;
    do {
        switch (state) {
        case UnescapeState::NORMAL:
            if (str[i] == '\\') {
                state = UnescapeState::ESCAPE;
            } else {
                str[j] = str[i];
                j++;
            }
            break;
        case UnescapeState::ESCAPE:
            if (auto c = unescapeMap[str[i]];
                c && (unescapeQuote || c != '"')) {
                str[j] = c;
                j++;
                state = UnescapeState::NORMAL;
                break;
            }
            // invalid escape sequence
            return false;
        }
    } while (str[i++]);
    str.resize(j - 1);
    return true;
}

std::optional<std::string> unescapeForValue(std::string_view str) {
    // having quote at beginning and end, escape
    if (str.size() >= 2 && str.front() == '"' && str.back() == '"') {
        std::string result;
        auto originLength = str.size();
        auto consumed = consumeMaybeEscapedValue(str, "", &result);
        if (consumed.size() == originLength) {
            return result;
        }
        return std::nullopt;
    }
    return std::string{str};
}

std::string escapeForValue(std::string_view str) {
    std::string value;
    value.reserve(str.size());
    const bool needEscape =
        str.find_first_of("\f\r\t\v \"\\\n") != std::string::npos;
    if (needEscape) {
        value.push_back('"');
    }
    for (char c : str) {
        if (auto escape = escapeMap[static_cast<uint8_t>(c)]) {
            value.push_back('\\');
            value.push_back(escape);
        } else {
            value.push_back(c);
        }
    }
    if (needEscape) {
        value.push_back('"');
    }

    return value;
}

bool consumePrefix(std::string_view &str, std::string_view prefix) {
    if (str.starts_with(prefix)) {
        str = str.substr(prefix.size());
        return true;
    }
    return false;
}

std::string_view consumeMaybeEscapedValue(std::string_view &input,
                                          std::string_view skip,
                                          std::string *output) {
    auto start = input.find_first_not_of(skip);
    if (start == std::string_view::npos) {
        input = std::string_view();
        if (output) {
            output->clear();
        }
        return {};
    }

    input = input.substr(start);
    assert(!input.empty());
    const bool maybeQuoted = input.front() == '"';
    if (maybeQuoted) {
        std::string result;
        UnescapeState state = UnescapeState::NORMAL;
        size_t end = 0;
        for (size_t i = 1; i < input.size(); i++) {
            const char c = input[i];
            switch (state) {
            case UnescapeState::NORMAL:
                if (c == '\\') {
                    state = UnescapeState::ESCAPE;
                } else if (c == '"') {
                    end = i + 1;
                    break;
                } else {
                    result.push_back(c);
                }
                break;
            case UnescapeState::ESCAPE:
                if (auto c = unescapeMap[input[i]]) {
                    result.push_back(c);
                } else {
                    // invalid escape sequence
                    // and treat it as normal character.
                    result.push_back(input[i]);
                }
                state = UnescapeState::NORMAL;
                break;
            }
            if (end) {
                break;
            }
        }
        if (end > 0) {
            auto consumed = input.substr(0, end);
            input = input.substr(end);
            if (output) {
                *output = std::move(result);
            }
            return consumed;
        }
    }
    auto end = input.find_first_of(skip, 1);
    auto consumed = input.substr(0, end);
    input =
        end == std::string_view::npos ? std::string_view() : input.substr(end);
    if (output) {
        *output = std::string(consumed);
    }
    return consumed;
}

} // namespace fcitx::stringutils