utf8.hpp

// Copyright (C) 2022 by Camden Mannett.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#pragma once
 
#include "arg_router/utility/utf8/double_width.hpp"
#include "arg_router/utility/utf8/grapheme_cluster_break.hpp"
#include "arg_router/utility/utf8/line_break.hpp"
#include "arg_router/utility/utf8/whitespace.hpp"
#include "arg_router/utility/utf8/zero_width.hpp"
 
#include <string_view>
 
namespace arg_router::utility::utf8
{
namespace detail
{
template <std::size_t N>
[[nodiscard]] constexpr std::optional<code_point::range> find_range(
    const std::array<code_point::range, N>& table,
    code_point::type cp) noexcept
{
    auto first = table.begin();
 
    auto len = N;
    while (len > 0) {
        const auto step = len / 2;
        auto halfway = first + step;
 
        if (cp < halfway->first()) {
            len = step;
        } else if (cp <= halfway->last()) {
            return *halfway;
        } else {
            first = ++halfway;
            len -= step + 1;
        }
    }
 
    return {};
}
}  // namespace detail
 
class iterator
{
public:
    using difference_type = std::string_view::difference_type;
    using value_type = std::string_view;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::forward_iterator_tag;
 
    class range_t
    {
    public:
        friend class iterator;
 
        [[nodiscard]] constexpr iterator begin() noexcept { return iterator{str_}; }
 
        [[nodiscard]] constexpr static iterator end() noexcept { return iterator{}; }
 
    private:
        constexpr explicit range_t(std::string_view str) noexcept : str_{str} {}
 
        std::string_view str_;
    };
 
    [[nodiscard]] constexpr static range_t range(std::string_view str) noexcept
    {
        return range_t{str};
    }
 
    constexpr iterator() noexcept : current_{0}, trailing_window_{} {}
 
    constexpr explicit iterator(std::string_view str) noexcept :
        current_{0}, str_{str}, trailing_window_{}
    {
        fill_trailing_window();
        update_current();
    }
 
    [[nodiscard]] constexpr bool operator==(iterator other) const noexcept
    {
        // If they are both empty, then they are considered both end iterators and therefore equal
        if (str_.empty() && other.str_.empty()) {
            return true;
        }
        return (str_.data() == other.str_.data()) && (str_.size() == other.str_.size());
    }
 
    [[nodiscard]] constexpr bool operator!=(iterator other) const noexcept
    {
        return !(*this == other);
    }
 
    [[nodiscard]] constexpr value_type operator*() const noexcept
    {
        return str_.substr(0, current_);
    }
 
    constexpr iterator& operator++() noexcept
    {
        // Remove the leading cluster
        str_.remove_prefix(current_);
 
        // Find the end of the new one
        update_current();
 
        return *this;
    }
 
    constexpr iterator operator++(int) noexcept
    {
        auto result = *this;
 
        ++(*this);
        return result;
    }
 
private:
    constexpr static auto trailing_window_size = std::size_t{AR_UTF8_TRAILING_WINDOW_SIZE};
 
    [[nodiscard]] constexpr static grapheme_cluster_break_class extract_class(
        code_point::type cp) noexcept
    {
        auto result = grapheme_cluster_break_class::any;
        const auto range = detail::find_range(grapheme_cluster_break_table, cp);
        if (range) {
            result = static_cast<grapheme_cluster_break_class>(range->meta());
        }
 
        return result;
    }
 
    [[nodiscard]] constexpr bool should_break(grapheme_cluster_break_class next_class) noexcept
    {
        for (auto rule : no_break_rules::grapheme_cluster<trailing_window_size>) {
            if (rule(trailing_window_, next_class)) {
                return false;
            }
        }
 
        return true;
    }
 
    constexpr void fill_trailing_window() noexcept
    {
        // array::fill(..) is only constexpr in C++20
        for (auto& p : trailing_window_) {
            p = grapheme_cluster_break_class::any;
        }
    }
 
    constexpr void rotate_trailing_window() noexcept
    {
        // Right rotate the window, std::rotate isn't constexpr in C++17
        auto it = trailing_window_.rbegin();
        while (true) {
            auto prev = it++;
            if (it == trailing_window_.rend()) {
                break;
            }
            *prev = *it;
        }
    }
 
    constexpr void update_current() noexcept
    {
        current_ = 0;
        if (str_.empty()) {
            return;
        }
 
        // Iterate over each code point and its neighbour, pass their break classes into the rule
        // checker
        for (auto it = code_point::iterator{str_}; it != code_point::iterator{}; ++it) {
            current_ += code_point::size(*it);
 
            // If this code point is malformed, then just skip it
            const auto this_cp = code_point::decode(*it);
            if (!this_cp) {
                continue;
            }
 
            rotate_trailing_window();
            trailing_window_.front() = extract_class(*this_cp);
 
            // If there is a following code point, use it to update the next_break_class
            auto next_break_class = grapheme_cluster_break_class::any;
            {
                auto next_it = it;
                ++next_it;
                if (next_it != code_point::iterator{}) {
                    const auto next_cp = code_point::decode(*next_it);
                    if (next_cp) {
                        next_break_class = extract_class(*next_cp);
                    }
                }
            }
 
            if (should_break(next_break_class)) {
                break;
            }
        }
    }
 
    std::size_t current_;
    std::string_view str_;
    std::array<grapheme_cluster_break_class, trailing_window_size> trailing_window_;
};
 
[[nodiscard]] inline constexpr std::size_t count(std::string_view str) noexcept
{
    return std::distance(iterator(str), iterator());
}
 
[[nodiscard]] inline constexpr bool is_whitespace(std::string_view str) noexcept
{
    const auto cp = code_point::decode(str);
    if (!cp) {
        return false;
    }
 
    return !!detail::find_range(whitespace_table, *cp);
}
 
[[nodiscard]] inline constexpr bool contains_whitespace(std::string_view str) noexcept
{
    for (auto cp : code_point::iterator::range(str)) {
        if (is_whitespace(cp)) {
            return true;
        }
    }
 
    return false;
}
 
[[nodiscard]] inline constexpr std::size_t terminal_width(std::string_view str) noexcept
{
    auto width = std::size_t{0};
    for (auto cp_str : code_point::iterator::range(str)) {
        const auto cp = code_point::decode(cp_str);
        if (!cp) {
            continue;
        }
 
        if (detail::find_range(double_width_table, *cp)) {
            width += 2;
        } else if (!detail::find_range(zero_width_table, *cp)) {
            width += 1;
        }
    }
 
    return width;
}
 
class line_iterator
{
public:
    using difference_type = std::string_view::difference_type;
    using value_type = std::string_view;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::forward_iterator_tag;
 
    constexpr line_iterator() noexcept : max_columns_{0}, line_break_byte_{0}, trailing_window_{} {}
 
    constexpr explicit line_iterator(std::string_view str, std::size_t max_columns) noexcept :
        str_{str}, max_columns_{max_columns}, line_break_byte_{0}, trailing_window_{}
    {
        if (max_columns_ == 0) {
            str_ = std::string_view{};
        }
 
        fill_trailing_window();
        consume();
    }
 
    [[nodiscard]] constexpr std::size_t max_columns() const noexcept { return max_columns_; }
 
    [[nodiscard]] constexpr bool operator==(line_iterator other) const noexcept
    {
        // If they are both empty, then they are considered both end iterators and therefore equal
        if (str_.empty() && other.str_.empty()) {
            return true;
        }
        return (str_.data() == other.str_.data()) && (str_.size() == other.str_.size()) &&
               (max_columns_ == other.max_columns_) && (line_break_byte_ == other.line_break_byte_);
    }
 
    [[nodiscard]] constexpr bool operator!=(line_iterator other) const noexcept
    {
        return !(*this == other);
    }
 
    [[nodiscard]] constexpr value_type operator*() const noexcept
    {
        return str_.substr(0, line_break_byte_);
    }
 
    constexpr line_iterator& operator++() noexcept
    {
        consume();
        return *this;
    }
 
    constexpr line_iterator operator++(int) noexcept
    {
        auto result = *this;
 
        ++(*this);
        return result;
    }
 
private:
    constexpr static auto trailing_window_size = std::size_t{AR_UTF8_TRAILING_WINDOW_SIZE};
 
    [[nodiscard]] constexpr static line_break_class extract_class(code_point::type cp) noexcept
    {
        auto result = line_break_class::any;
        const auto range = detail::find_range(line_break_table, cp);
        if (range) {
            result = static_cast<line_break_class>(range->meta());
        }
 
        return result;
    }
 
    [[nodiscard]] constexpr bool should_break(line_break_class next_class) noexcept
    {
        for (auto rule : no_break_rules::line_break<trailing_window_size>) {
            if (rule(trailing_window_, next_class)) {
                return false;
            }
        }
 
        return true;
    }
 
    constexpr void fill_trailing_window() noexcept
    {
        // array::fill(..) is only constexpr in C++20
        for (auto& p : trailing_window_) {
            p = line_break_class::any;
        }
    }
 
    constexpr void rotate_trailing_window() noexcept
    {
        // Right rotate the window, std::rotate isn't constexpr in C++17
        auto it = trailing_window_.rbegin();
        while (true) {
            auto prev = it++;
            if (it == trailing_window_.rend()) {
                break;
            }
            *prev = *it;
        }
    }
 
    constexpr void consume() noexcept
    {
        if (str_.empty()) {
            return;
        }
 
        // Start by consuming the previous line
        if (line_break_byte_ != 0) {
            str_.remove_prefix(line_break_byte_);
            line_break_byte_ = 0;
 
            // Consuming any leading whitespace
            auto bytes = std::size_t{0};
            for (auto cp : code_point::iterator::range(str_)) {
                if (!is_whitespace(cp)) {
                    break;
                }
                bytes += code_point::size(cp);
            }
            str_.remove_prefix(bytes);
 
            if (str_.empty()) {
                return;
            }
        }
 
        // Iterate over the code points until you reach or exceed the column limit, setting the
        // break markers at each whitespace code point
        auto column = std::size_t{0};
        auto bytes = std::size_t{0};
        auto line_break_column = std::size_t{0};
        auto line_break_byte = std::size_t{0};
        for (auto it = code_point::iterator{str_}; it != code_point::iterator{}; ++it) {
            // Have we exceeded the terminal width?
            column += terminal_width(*it);
            if (column > max_columns_) {
                if (line_break_column == 0) {
                    // Oh dear, the line has no whitespace in it to break on, so force break on the
                    // last code point
                    line_break_byte_ = bytes;
                } else {
                    line_break_byte_ = line_break_byte;
                }
                return;
            }
 
            bytes += code_point::size(*it);
 
            // If this code point is malformed, then just skip it
            const auto this_cp = code_point::decode(*it);
            if (!this_cp) {
                continue;
            }
 
            rotate_trailing_window();
            trailing_window_.front() = extract_class(*this_cp);
 
            // If there is a following code point, use it to update the next_break_class
            auto next_break_class = line_break_class::any;
            {
                auto next_it = it;
                ++next_it;
                if (next_it != code_point::iterator{}) {
                    const auto next_cp = code_point::decode(*next_it);
                    if (next_cp) {
                        next_break_class = extract_class(*next_cp);
                    }
                }
            }
 
            if (should_break(next_break_class)) {
                line_break_column = column;
                line_break_byte = bytes;
            }
        }
 
        // We haven't hit the max column, so consume the whole string
        line_break_byte_ = str_.size();
    }
 
    std::string_view str_;
    std::size_t max_columns_;
    std::size_t line_break_byte_;
    std::array<line_break_class, trailing_window_size> trailing_window_;
};
}  // namespace arg_router::utility::utf8