strCat.hh

Go to the documentation of this file.

#ifndef STRCAT_H
#define STRCAT_H

#include "string_view.hh"
#include <climits>
#include <cstring>
#include <limits>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>

// strCat and strAppend()
//
// Inspired by google's absl::StrCat (similar interface, different implementation).
// See https://abseil.io/blog/20171023-cppcon-strcat
// and https://github.com/abseil/abseil-cpp/blob/master/absl/strings/str_cat.h


// --- Public interface ---

// Concatenate a bunch of 'printable' objects.
//
// Conceptually each object is converted to a string, all those strings are
// concatenated, and that result is returned.
//
// For example:
//      auto s = strCat("foobar", s, ' ', 123);
// is equivalent to
//      auto s = "foobar" + s + ' ' + std::to_string(123);
//
// The former executes faster than the latter because (among other things) it
// immediately creates a result of the correct size instead of (re)allocating
// all intermediate strings. Also it doesn't create temporary string objects
// for the integer conversions.
template<typename... Ts>
std::string strCat(Ts&& ...ts);


// Apppend a bunch of 'printable' objects to an exiting string.
//
// Can be used to optimize
//     s += strCat(a, b, c);
// to
//     strAppend(s, a, b, c);
//
// This latter will immediately construct the result in 's' instead of first
// formatting to a temporary string followed by appending that temporary to 's'.
//
// There's one limitation though: it's not allowed to append a string to
// itself, not even parts of the string (strCat() doesn't have this
// limitation). So the following is invalid:
//     strAppend(s, s); // INVALID, append s to itself
//
//     string_view v = s;
//     v.substr(10, 20);
//     strAppend(s, v); // INVALID, append part of s to itself
template<typename... Ts>
void strAppend(std::string& result, Ts&& ...ts);


// Format an integer as a fixed-width hexadecimal value and insert it into
// a strCat() or strAppend() sequence.
// - If the value is small, leading zeros are printed.
// - If the value is too big, it gets truncated. Only the rightmost characters
//   are kept.
//
// For example:
//    s = strCat("The value is: 0x", hex_string<4>(value), '.');


// Insert 'n' spaces into a strCat() or strAppend() sequence.
//
// For example:
//    s = strCat("The result is ", spaces(30 - item.size()), item);
//
// This can be more efficient than creating a temporary string containing 'n'
// spaces, like this
//    s = strCat("The result is ", std::string(30 - item.size(), ' '), item);


// --- Implementation details ---

namespace strCatImpl {

// ConcatUnit
// These implement various mechanisms to concatentate an object to a string.
// All these classes implement:
//
// - size_t size() const;
//     Returns the (exact) size in characters of the formatted object.
//
// - char* copy(char* dst) const;
//     Copy the formatted object to 'dst', returns an updated pointer.
template<typename T> struct ConcatUnit;


// Helper for types which are formatted via a temporary string object
struct ConcatViaString
{
        ConcatViaString(std::string s_)
                : s(std::move(s_))
        {
        }

        size_t size() const
        {
                return s.size();
        }

        char* copy(char* dst) const
        {
                auto sz = s.size();
                memcpy(dst, s.data(), sz);
                return dst + sz;
        }

private:
        std::string s;
};

#if 0
// Dingux doesn't have std::to_string() ???

// Helper for types which are printed via std::to_string(),
// e.g. floating point types.
template<typename T>
struct ConcatToString : ConcatViaString
{
        ConcatToString(T t)
                : ConcatViaString(std::to_string(t))
        {
        }
};
#endif

// The default (slow) implementation uses 'operator<<(ostream&, T)'
template<typename T>
struct ConcatUnit : ConcatViaString
{
        ConcatUnit(const T& t)
                : ConcatViaString([&](){
                        std::ostringstream os;
                        os << t;
                        return os.str();
                }())
        {
        }
};


// ConcatUnit<string_view>:
//   store the string view (copies the view, not the string)
template<> struct ConcatUnit<string_view>
{
        ConcatUnit(const string_view v_)
                : v(v_)
        {
        }

        size_t size() const
        {
                return v.size();
        }

        char* copy(char* dst) const
        {
                auto sz = v.size();
                memcpy(dst, v.data(), sz);
                return dst + sz;
        }

private:
        string_view v;
};


// ConcatUnit<char>:
//   store single char (length is constant 1)
template<> struct ConcatUnit<char>
{
        ConcatUnit(char c_)
                : c(c_)
        {
        }

        size_t size() const
        {
                return 1;
        }

        char* copy(char* dst) const
        {
                *dst = c;
                return dst + 1;
        }

private:
        char c;
};


// ConcatUnit<bool>:
//   store bool (length is constant 1)
template<> struct ConcatUnit<bool>
{
        ConcatUnit(bool b_)
                : b(b_)
        {
        }

        size_t size() const
        {
                return 1;
        }

        char* copy(char* dst) const
        {
                *dst = b ? '1' : '0';
                return dst + 1;
        }

private:
        bool b;
};


// Helper classes/functions for fast integer -> string conversion.

// Returns a fast type that is wide enough to hold the absolute value for
// values of the given type.
//
// On x86 32-bit operations are faster than e.g. 16-bit operations.
// So this function returns a 32-bit type unless 64-bit are needed.
//
// 'long' is special because it's either 32-bit (windows) or 64-bit (Linux).
template<typename T> struct FastUnsignedImpl { using type = unsigned; };
template<> struct FastUnsignedImpl<              long> { using type = unsigned long;      };
template<> struct FastUnsignedImpl<unsigned      long> { using type = unsigned long;      };
template<> struct FastUnsignedImpl<         long long> { using type = unsigned long long; };
template<> struct FastUnsignedImpl<unsigned long long> { using type = unsigned long long; };
template<typename T> using FastUnsigned = typename FastUnsignedImpl<T>::type;

// Helper function to take the absolute value of a signed or unsigned type.
//
// This does the equivalent of
//    unsigned u = (t < 0) ? -t : t;
// But it avoids compiler warnings on 't < 0' and '-t' when t is unsigned.
template<bool IS_SIGNED> struct AbsHelper;

template<> struct AbsHelper<true>
{
        template<typename T>
        inline FastUnsigned<T> operator()(T t) const
        {
                return (t < 0) ? -t : t;
        }
};

template<> struct AbsHelper<false>
{
        template<typename T>
        inline FastUnsigned<T> operator()(T t) const
        {
                return t;
        }
};

// Helper function to print a minus sign in front of negative values.
//
// Does the equivalent of
//   if (t < 0) *--p = '-';
// but
// - Is guaranteed to be optimized away for unsigned types.
// - Doesn't generate compiler warnings for unsigned types.
template<bool IS_SIGNED> struct PutSignHelper;

template<> struct PutSignHelper<true>
{
        template<typename T>
        inline void operator()(T t, char*& p) const
        {
                if (t < 0) *--p = '-';
        }
};

template<> struct PutSignHelper<false>
{
        template<typename T>
        inline void operator()(T /*t*/, char*& /*p*/) const
        {
                // nothing
        }
};

// Optimized integer printing.
//
// Prints the value to an internal buffer. The formatted characters are
// generated from back to front. This means the final result is not aligned
// with the start of this internal buffer.
//
// Next to the internal buffer we also store the size (in characters) of the
// result. This size can be used to calculate the start position in the buffer.
template<typename T> struct ConcatIntegral
{
        static const bool IS_SIGNED = std::numeric_limits<T>::is_signed;
        static const size_t BUF_SIZE = 1 + std::numeric_limits<T>::digits10 + IS_SIGNED;

        ConcatIntegral(T t)
        {
                char* p = this->end();
                auto a = AbsHelper<IS_SIGNED>()(t);

                do {
                        *--p = static_cast<char>('0' + (a % 10));
                        a /= 10;
                } while (a);

                PutSignHelper<IS_SIGNED>()(t, p);
                this->sz = static_cast<unsigned char>(this->end() - p);
        }

        size_t size() const
        {
                return sz;
        }

        char* copy(char* dst) const
        {
                memcpy(dst, begin(), sz);
                return dst + sz;
        }

        operator std::string() const
        {
                return std::string(begin(), this->size());
        }

private:
        const char* begin() const
        {
                return &buf[BUF_SIZE] - sz;
        }

        char* end()
        {
                return &buf[BUF_SIZE];
        }

private:
        char buf[BUF_SIZE];
        unsigned char sz;
};


// Format an integral as a hexadecimal value with a fixed number of characters.
// This fixed width means it either adds leading zeros or truncates the result
// (it keeps the rightmost digits).
template<size_t N, typename T> struct ConcatFixedWidthHexIntegral
{
        ConcatFixedWidthHexIntegral(T t_)
                : t(t_)
        {
        }

        size_t size() const
        {
                return N;
        }

        char* copy(char* dst) const
        {
                char* p = dst + N;
                auto u = static_cast<FastUnsigned<T>>(t);

                for (size_t i = 0; i < N; ++i) {
                        auto d = u & 15;
                        *--p = (d < 10) ? static_cast<char>(d + '0')
                                        : static_cast<char>(d - 10 + 'a');
                        u >>= 4;
                }

                return dst + N;
        }

private:
        T t;
};


// Prints a number of spaces (without constructing a temporary string).
struct ConcatSpaces
{
        ConcatSpaces(size_t n_)
                : n(n_)
        {
        }

        size_t size() const
        {
                return n;
        }

        char* copy(char* dst) const
        {
                memset(dst, ' ', n);
                return dst + n;
        }

private:
        size_t n;
};


// Create a 'ConcatUnit<T>' wrapper object for a given 'T' value.

// Generic version: use the corresponding ConcatUnit<T> class. This can be
// a specialized version for 'T', or the generic (slow) version which uses
// operator<<(ostream&, T).
template<typename T>
inline auto makeConcatUnit(const T& t)
{
        return ConcatUnit<T>(t);
}

// Overloads for various cases (strings, integers, floats, ...).
inline auto makeConcatUnit(const std::string& s)
{
        return ConcatUnit<string_view>(s);
}

inline auto makeConcatUnit(const char* s)
{
        return ConcatUnit<string_view>(s);
}

inline auto makeConcatUnit(char* s)
{
        return ConcatUnit<string_view>(s);
}

// Note: no ConcatIntegral<char> because that is printed as a single character
inline auto makeConcatUnit(signed char c)
{
        return ConcatIntegral<signed char>(c);
}

inline auto makeConcatUnit(unsigned char c)
{
        return ConcatIntegral<unsigned char>(c);
}

inline auto makeConcatUnit(short s)
{
        return ConcatIntegral<short>(s);
}

inline auto makeConcatUnit(unsigned short s)
{
        return ConcatIntegral<unsigned short>(s);
}

inline auto makeConcatUnit(int i)
{
        return ConcatIntegral<int>(i);
}

inline auto makeConcatUnit(unsigned u)
{
        return ConcatIntegral<unsigned>(u);
}

inline auto makeConcatUnit(long l)
{
        return ConcatIntegral<long>(l);
}

inline auto makeConcatUnit(unsigned long l)
{
        return ConcatIntegral<unsigned long>(l);
}

inline auto makeConcatUnit(long long l)
{
        return ConcatIntegral<long long>(l);
}

inline auto makeConcatUnit(unsigned long long l)
{
        return ConcatIntegral<unsigned long long>(l);
}

#if 0
// Converting float->string via std::to_string() might be faster than via
// std::stringstream. Though the former doesn't seem to work on Dingux??
//
// But for openMSX this isn't critical, so we can live with the default
// (slower?) version.

inline auto makeConcatUnit(float f)
{
        return ConcatToString<float>(f);
}

inline auto makeConcatUnit(double d)
{
        return ConcatToString<double>(d);
}

inline auto makeConcatUnit(long double d)
{
        return ConcatToString<long double>(d);
}
#endif

template<size_t N, typename T>
inline auto makeConcatUnit(const ConcatFixedWidthHexIntegral<N, T>& t)
{
        return t;
}

inline auto makeConcatUnit(const ConcatSpaces& t)
{
        return t;
}


// Calculate the total size for a bunch (a tuple) of ConcatUnit<T> objects.
// That is, calculate the sum of calling the size() method on each ConcatUnit.
template<typename Tuple, size_t... Is>
size_t calcTotalSizeHelper(const Tuple& t, std::index_sequence<Is...>)
{
        // TODO implementation can be simplified by using c++17 fold expressions
        size_t total = 0;
        auto l = { ((total += std::get<Is>(t).size()) , 0)... };
        (void)l;
        return total;
}

template<typename... Ts>
size_t calcTotalSize(const std::tuple<Ts...>& t)
{
        return calcTotalSizeHelper(t, std::index_sequence_for<Ts...>{});
}


// Copy each ConcatUnit<T> in the given tuple to the final result.
template<typename Tuple, size_t... Is>
void copyUnitsHelper(char* dst, const Tuple& t, std::index_sequence<Is...>)
{
        auto l = { ((dst = std::get<Is>(t).copy(dst)) , 0)... };
        (void)l;
}

template<typename... Ts>
void copyUnits(char* dst, const std::tuple<Ts...>& t)
{
        copyUnitsHelper(dst, t, std::index_sequence_for<Ts...>{});
}

// Fast integral -> string conversion. (Standalone version, result is not part
// of a larger string).
template<typename T>
inline std::string to_string(T x)
{
        return ConcatIntegral<T>(x);
}

} // namespace strCatImpl


// Generic version
template<typename... Ts>
std::string strCat(Ts&& ...ts)
{
        // Strategy:
        // - For each parameter (of any type) we create a ConcatUnit object.
        // - We sum the results of callings size() on all those objects.
        // - We allocate a string of that total size.
        // - We copy() each ConcatUnit into that string.

        auto t = std::make_tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
        auto size = strCatImpl::calcTotalSize(t);
        // Ideally we want an uninitialized string with given size, but that's not
        // yet possible. Though see the following proposal (for c++20):
        //   www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1072r0.html
        std::string result(size, ' ');
        char* dst = &result[0]; // C++17 result.data()
        strCatImpl::copyUnits(dst, t);
        return result;
}

// Optimized strCat() for the case that the 1st parameter is a temporary
// (rvalue) string. In that case we can append to that temporary.
template<typename... Ts>
std::string strCat(std::string&& first, Ts&& ...ts)
{
        strAppend(first, std::forward<Ts>(ts)...);
        return std::move(first);
}

// Degenerate case
inline std::string strCat()
{
        return std::string();
}

// Extra overloads. These don't change and/or extend the above functionality,
// but in some cases they might improve performance a bit (see notes above
// about uninitialized string resize). With these overloads strCat()/strAppend()
// should never be less efficient than a sequence of + or += string-operations.
inline std::string strCat(const std::string& x) { return x; }
inline std::string strCat(std::string&&      x) { return std::move(x); }
inline std::string strCat(const char*        x) { return std::string(x); }
inline std::string strCat(char               x) { return std::string(1, x); }
inline std::string strCat(string_view         x) { return std::string(x.data(), x.size()); }

inline std::string strCat(signed char        x) { return strCatImpl::to_string(x); }
inline std::string strCat(unsigned char      x) { return strCatImpl::to_string(x); }
inline std::string strCat(short              x) { return strCatImpl::to_string(x); }
inline std::string strCat(unsigned short     x) { return strCatImpl::to_string(x); }
inline std::string strCat(int                x) { return strCatImpl::to_string(x); }
inline std::string strCat(unsigned           x) { return strCatImpl::to_string(x); }
inline std::string strCat(long               x) { return strCatImpl::to_string(x); }
inline std::string strCat(unsigned long      x) { return strCatImpl::to_string(x); }
inline std::string strCat(long long          x) { return strCatImpl::to_string(x); }
inline std::string strCat(unsigned long long x) { return strCatImpl::to_string(x); }

inline std::string strCat(const std::string& x, const std::string& y) { return x + y; }
inline std::string strCat(const char*        x, const std::string& y) { return x + y; }
inline std::string strCat(char               x, const std::string& y) { return x + y; }
inline std::string strCat(const std::string& x, const char*        y) { return x + y; }
inline std::string strCat(const std::string& x, char               y) { return x + y; }
inline std::string strCat(std::string&&      x, const std::string& y) { return x + y; }
inline std::string strCat(const std::string& x, std::string&&      y) { return x + y; }
inline std::string strCat(std::string&&      x, std::string&&      y) { return x + y; }
inline std::string strCat(const char*        x, std::string&&      y) { return x + y; }
inline std::string strCat(char               x, std::string&&      y) { return x + y; }
inline std::string strCat(std::string&&      x, const char*        y) { return x + y; }
inline std::string strCat(std::string&&      x, char               y) { return x + y; }


// Generic version
template<typename... Ts>
void strAppend(std::string& result, Ts&& ...ts)
{
        // Implementation strategy is similar to strCat(). Main difference is
        // that we now extend an existing string instead of creating a new one.

        auto t = std::make_tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
        auto extraSize = strCatImpl::calcTotalSize(t);
        auto oldSize = result.size();
        result.append(extraSize, ' '); // see note in strCat() about uninitialized string
        char* dst = &result[oldSize];
        strCatImpl::copyUnits(dst, t);
}

// Degenerate case
inline void strAppend(std::string& /*x*/)
{
        // nothing
}

// Extra overloads, see strCat().
inline void strAppend(std::string& x, const std::string& y) { x += y; }
inline void strAppend(std::string& x, const char*        y) { x += y; }
inline void strAppend(std::string& x, string_view         y) { x.append(y.data(), y.size()); }


template<size_t N, typename T>
inline strCatImpl::ConcatFixedWidthHexIntegral<N, T> hex_string(T t)
{
        return {t};
}

inline strCatImpl::ConcatSpaces spaces(size_t n)
{
        return {n};
}

#endif