UT_StringHolder.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 * 
 * NAME:        UT_StringHolder.h
 *
 * COMMENTS:    A simple holder for strings which acts like copy on
 *              write, but has special methods for minimizing memory
 *              copies when you know what you are doing.
 *
 *              Has a trivial move constructor.
 *
 *              c_str does not change when it moves.
 *
 * RELATION TO THE STL:
 *
 *              Use UT_StringHolder, UT_WorkBuffer, etc. instead of std::string
 *
 *              Reasoning to not use std::string:
 *
 *              - Performance: The specification prohibits copy-on-write, so we
 *                can’t do a COW implementation, that we often rely on to
 *                minimize allocations. 
 *
 *              - Bugs: It uses internal pointers so is not trivially
 *                relocatable, making arrays of strings expensive to resize.
 *
 *              - Aesthetics: We have too many string types already to manage
 *                in Houdini without making yet another one common.
 *
 *              See also:
 *                https://internal.sidefx.com/wiki/index.php/StringClasses 
 *
 */

// #pragma once

#ifndef __UT_StringHolder_h__
#define __UT_StringHolder_h__

#include "UT_API.h"
#include "UT_Assert.h"
#include "UT_Format.h"
#include "UT_String.h"
#include "UT_Swap.h"
#include "UT_StringUtils.h"

#include <SYS/SYS_AtomicInt.h>
#include <SYS/SYS_Compiler.h>
#include <SYS/SYS_Inline.h>
#include <SYS/SYS_Math.h>
#include <SYS/SYS_Pragma.h>
#include <SYS/SYS_StaticAssert.h>
#include <SYS/SYS_String.h>
#include <SYS/SYS_Types.h>

#include <iosfwd>
#include <string>
#include <utility>

#include <stdint.h>
#include <string.h>

template <typename T> class UT_Array;
class UT_IStream;
class UT_OStream;
class ut_PatternRecord;
class UT_StringHolder;
class UT_StringMMPattern;
class UT_StringRef;
class UT_StringView;
class UT_WorkBuffer;

// Forward declare the UDSL so that we can friend it inside of UT_StringHolder.
namespace UT { inline namespace Literal {
UT_StringHolder operator""_sh(const char *s, std::size_t const length);
} }

/// A string literal with length and compile-time computed hash value.
/// @note This will only be compile-time when used in compile time expressions
/// like template parameters and constexpr variables.
/// @note String literals whose length requires more than 31 bits not supported
/// @see UT_StringRef
class UT_StringLit
{
public:
    constexpr SYS_FORCE_INLINE
    UT_StringLit()
        : myData(nullptr) // These must match UT_StringRef's default ctor
        , myLength(0)
        , myHash(0)
    {
    }

    template <size_t N>
    constexpr SYS_FORCE_INLINE
    UT_StringLit(const char (&str)[N])
        : myData(str)
        , myLength(N-1)
        , myHash(SYSstring_hash(str, myLength, /*allow_nulls*/true))
    {
        SYS_STATIC_ASSERT(N-1 < (((exint)1) << 31));
    }

    SYS_FORCE_INLINE constexpr const char*  data() const
    {
        return myData ? myData : "";
    }
    SYS_FORCE_INLINE constexpr const char*  buffer() const { return data(); }
    SYS_FORCE_INLINE constexpr const char*  c_str() const { return data(); }
    SYS_FORCE_INLINE constexpr operator const char*() const { return data(); }

    SYS_FORCE_INLINE constexpr exint        length() const { return myLength; }

    SYS_FORCE_INLINE constexpr uint32       hash() const { return myHash; }

    SYS_FORCE_INLINE const UT_StringHolder& asHolder() const;
    SYS_FORCE_INLINE const UT_StringRef&    asRef() const;

    SYS_FORCE_INLINE constexpr bool operator==(const UT_StringLit &other) const
    {
        if (myLength != other.myLength || myHash != other.myHash)
            return false;
        // we must check also other.myData for nullptr to avoid gcc error
        if (myData == nullptr || other.myData == nullptr)
            return true;
        return !SYSmemcmp(myData, other.myData, myLength);
    }
    SYS_FORCE_INLINE constexpr bool operator!=(const UT_StringLit &other) const
    {
        return !(*this == other);
    }

    friend SYS_FORCE_INLINE constexpr
    bool operator==(const UT_StringLit &str, const char *other)
    {
        // Treat nullptr as empty strings
        if (other == nullptr)
            return (str.myLength == 0);
        if (str.myData == nullptr)
            return *other == 0;
#if _MSC_VER
        if (__builtin_is_constant_evaluated())
        {
            // compare up to myLength+1 to include terminating nul
            for (int32 i = 0; i < str.myLength + 1; ++i)
            {
                if (str.myData[i] != other[i])
                    return false;
            }
            return true;
        }
        return !strcmp(str.myData, other);
#else
        return !__builtin_strcmp(str.myData, other);
#endif
    }
    friend SYS_FORCE_INLINE constexpr
    bool operator==(const char *other, const UT_StringLit &str)
    {
        return (str == other);
    }
    friend SYS_FORCE_INLINE constexpr
    bool operator!=(const UT_StringLit &str, const char *other)
    {
        return !(str == other);
    }
    friend SYS_FORCE_INLINE constexpr
    bool operator!=(const char *other, const UT_StringLit &str)
    {
        return !(str == other);
    }

private:
    const char* myData;
    int32       myLength;
    uint32      myHash;

    friend class UT_StringRef;
};

// Empty strings must have myData be nullptr, specialize for these
template <>
constexpr SYS_FORCE_INLINE
UT_StringLit::UT_StringLit(const char (&str)[1])
    : myData(nullptr)
    , myLength(0)
    , myHash(0)
{
}

/// A holder for a string, which stores the length and caches the hash value.
/// A UT_StringRef does not necessarily own the string, and it is therefore not
/// safe to e.g. store a UT_StringRef in a container or member variable.
/// @see UT_StringHolder
/// @see UTmakeUnsafeRef
class UT_API UT_StringRef
{
public:
    typedef char value_type;

    enum        StorageMode
    {
        STORE_EXTERNAL,
        STORE_NEW,
        STORE_MALLOC,
        STORE_INLINE
    };

    class UT_API Holder
    {
        Holder() = delete;
    public:
        static Holder *buildFromData(const char *str, exint len, StorageMode storage);
        static Holder *buildInline(const char* str, exint length);
        static Holder *buildInline(exint length);

        const char *c_str() const
        {
            if (myStorageMode == STORE_INLINE)
                return myDataIfInline;
            else
                return myData;
        }

        exint length() const
        {
            return myLength;
        }

        void    incref()
        {
            myRefCount.add(1);
        }

        void    decref()
        {
            if (myRefCount.add(-1) == 0)
                destroy();
        }

        int64           getMemoryUsage(bool inclusive) const;

        bool isUnique() const
        {
            return myRefCount.relaxedLoad() == 1 && myStorageMode != STORE_EXTERNAL;
        }

        char* inlineBufferNC() // used after buildInline(length) to get buffer to write
        {
            return myDataIfInline;
        }

        char* stealAsMalloc()
        {
            if (myStorageMode == STORE_MALLOC && myRefCount.relaxedLoad() == 1)
            {
                myStorageMode = STORE_EXTERNAL; // make destroy not free the data
                return (char*)myData;
            }
            return 0; // steal did not work
        }

    private:
        void destroy();

        SYS_AtomicInt32 myRefCount;
        StorageMode     myStorageMode;
        exint           myLength;

        // This union makes viewing in a debugger much easier.
        union {
            const char *myData;
            char myDataIfInline[sizeof(const char *)];
        };
    };

    SYS_FORCE_INLINE
    UT_StringRef()
        : myData(nullptr)
        , myLength(0)
        , myHash(0)
    {
    }

    /// Will make a shallow reference.
    SYS_FORCE_INLINE
    UT_StringRef(const char *str)
        : UT_StringRef()
    {
        if (str)
            _reference(str, strlen(str));
    }

    /// Will make a shallow reference.
    /// This is NOT a string view, the string must actually null terminate
    SYS_FORCE_INLINE
    UT_StringRef(const char *data, exint length)
        : UT_StringRef()
    {
        _reference(data, length);
    }

    /// Construct from string literal
    SYS_FORCE_INLINE explicit
    UT_StringRef(const UT_StringLit &lit)
        : UT_StringRef(lit.asRef())
    {
    }

    /// This will make a shallow reference to the contents of the string.
    SYS_FORCE_INLINE
    UT_StringRef(const std::string &str)
        : UT_StringRef(str.c_str(), str.length())
    {
    }

    /// This will make a shallow reference to the contents of the string.
    UT_StringRef(const UT_WorkBuffer &str);

    /// This will make a shallow reference to the contents of the string.
    SYS_FORCE_INLINE
    UT_StringRef(const UT_String &str)
        : UT_StringRef(str.buffer(), str.length())
    {
    }

    /// Shares a reference with the source.
    SYS_FORCE_INLINE
    UT_StringRef(const UT_StringRef &s) noexcept
        : myData(s.myData)
        , myLength(s.myLength)
        , myHash(s.myHash)
    {
        incref();
    }

    /// Move constructor. Steals the working data from the original.
    SYS_FORCE_INLINE
    UT_StringRef(UT_StringRef &&s) noexcept
        : myData(s.myData)
        , myLength(s.myLength)
        , myHash(s.myHash)
    {
        s.myData = nullptr;
        s.myLength = 0;
        s.myHash = 0;
    }

    SYS_FORCE_INLINE
    ~UT_StringRef()
    {
        decref();
    }

    /// Special sentinel value support
    /// @{
    enum UT_StringSentinelType { SENTINEL };

    SYS_FORCE_INLINE explicit
    UT_StringRef(UT_StringSentinelType)
        : myData(nullptr)
        , myLength(0)
        , myHash(SENTINEL_HASH)
    {
    }

    /// str==nullptr turns into sentinel, otherwise act like UT_StringRef(str)
    SYS_FORCE_INLINE
    UT_StringRef(UT_StringSentinelType, const char* str)
        : myData(nullptr)
        , myLength(0)
        , myHash(str ? 0 : SENTINEL_HASH)
    {
        if (str)
            _reference(str, strlen(str));
    }

    SYS_FORCE_INLINE
    bool isSentinel() const
    {
        return myHash == SENTINEL_HASH && !myLength;
    }

    SYS_FORCE_INLINE
    void makeSentinel()
    {
        decref();
        myData = nullptr;
        myLength = 0;
        myHash = SENTINEL_HASH;
    }
    /// @}

    /// Returns true this object is the sole owner of the underlying string
    bool isUnique() const
    {
        return !myLength && myDataIfHolder && myDataIfHolder->isUnique();
    }

    /// Shares a reference with the source.
    UT_StringRef &operator=(const UT_StringRef &s)
    {
        s.incref();
        decref();
        myData = s.myData;
        myLength = s.myLength;
        myHash = s.myHash;
        return *this;
    }

    /// Move the contents of about-to-be-destructed string
    /// s to this string.
    SYS_FORCE_INLINE
    UT_StringRef &operator=(UT_StringRef &&s)
    {
        // Can just swap, since s is about to be destructed.
        swap(s);
        return *this;
    }

    bool                operator==(const UT_StringRef &s) const
    { 
        // It is sensible to fast-path this based on myData!
        // If our two pointers are equal, we either are pointing to
        // the same Holder or to the same const char *, so are good
        // to call it equal.
        if (myData == s.myData)
        {
             if (!myData)
                 return myHash == s.myHash; // make sure sentinel != ""
             return true;
        }
        // empty string cannot match non-empty string.
        if (!myData || !s.myData)
            return false;
        // If both strings have cached hashes with different values, the
        // strings cannot be equal.
        if (myHash && s.myHash && myHash != s.myHash)
            return false;
        const exint tl = length();
        return tl == s.length() && SYSmemcmp(c_str(), s.c_str(), tl) == 0;
    }

    bool                operator==(const char *s) const
    { 
        if (!myDataIfChars)
            return (!s || !*s) && !myHash; // make sure sentinel != ""
        // It is sensible to fast-path this based on myData!
        // If our two pointers are equal, we either are pointing to
        // the same Holder or to the same const char *, so are good
        // to call it equal.
        // We don't test for myData being a Holder because it should
        // never alias a const char *.
        if (myDataIfChars == s)
            return true;
        // Avoid comparison with null.
        if (!s)
            return false;
        return ::strcmp(c_str(), s) == 0; 
    }
    bool                operator==(const UT_String &s) const
                            { return operator==(s.buffer()); }

    bool                operator!=(const UT_StringRef &s) const
                            { return !operator==(s); }
    bool                operator!=(const char *s) const
                            { return !operator==(s); }
    bool                operator!=(const UT_String &s) const
                            { return operator!=(s.buffer()); }

    /// Spaceship comparison returns:
    ///  - < 0 if *this < k
    ///  - == 0 if *this == k
    ///  - > 0 if *this > k
    int                 spaceship(const UT_StringRef &k) const
    {
        const exint l = length();
        const exint kl = k.length();
        const exint minlen = SYSmin(l, kl);
        int r = SYSmemcmp(c_str(), k.c_str(), minlen);
        if (r != 0)
            return r;
        else if (kl > minlen)
            return -1;
        else if (l > minlen)
            return 1;
        else
            return 0;
    }

    bool                operator<(const UT_StringRef &k) const
                            { return spaceship(k) < 0; }
    bool                operator<=(const UT_StringRef &k) const
                            { return spaceship(k) <= 0; }
    bool                operator>(const UT_StringRef &k) const
                            { return spaceship(k) > 0; }
    bool                operator>=(const UT_StringRef &k) const
                            { return spaceship(k) >= 0; }
    int                 compare(const UT_StringRef &str,
                                bool ignore_case=false) const
                        {
                            return ignore_case
                                 ? SYSstrcasecmp(c_str(), str.c_str())
                                 : spaceship(str); }
    bool                equal(const UT_StringRef &str,
                                bool ignore_case=false) const
                            { return compare(str, ignore_case) == 0; }

    /// Test whether the string is defined or not
    SYS_FORCE_INLINE
    SYS_SAFE_BOOL       operator bool() const   { return isstring(); }

    /// Imported from UT_String.
    bool        startsWith(const UT_StringView &pfx, bool case_sense=true) const
    {
        return UTstringStartsWith(*this, pfx.data(), case_sense, pfx.length());
    }
    bool        endsWith(const UT_StringView &suffix, bool case_sense=true) const
    {
        return UTstringEndsWith(*this, suffix.data(), case_sense, suffix.length());
    }
    bool        match(const char *pattern, bool case_sensitive=true) const
    { return UT_StringWrap(c_str()).match(pattern, case_sensitive); }

    bool        contains(const char *pattern, bool case_sensitive=true) const
    { return UT_StringWrap(c_str()).contains(pattern, case_sensitive); }
    const char *fcontain(const char *pattern, bool case_sensitive=true) const
    { return UT_StringWrap(c_str()).fcontain(pattern, case_sensitive); }
    const char *findWord(const char *word) const
    { return UT_StringWrap(c_str()).findWord(word); }

    bool multiMatch(const char *pattern, bool case_sensitive,
                        char separator) const
    {
        return UT_StringWrap(c_str()).multiMatch(
                    pattern, case_sensitive, separator);
    }
    bool        multiMatch(const char *pattern, bool case_sensitive = true,
                           const char *separators = ", ",
                           bool *explicitly_excluded = 0,
                           int *match_index = 0,
                           ut_PatternRecord *pattern_record=nullptr) const
    {
        return UT_StringWrap(c_str()).multiMatch(
                    pattern, case_sensitive, separators, explicitly_excluded,
                    match_index, pattern_record);
    }
    bool        multiMatch(const UT_StringMMPattern &pattern,
                           bool *explicitly_excluded = 0,
                           int *match_index = 0,
                           ut_PatternRecord *pattern_record=nullptr) const
    {
        return UT_StringWrap(c_str()).multiMatch(
                    pattern, explicitly_excluded, match_index, pattern_record);
    }

    /// Returns true if the entire string matches the provided regular
    /// expression, false otherwise. See UT_Regex.
    bool         matchRegex(const char *expr) const;

    int          toInt() const
    { return UT_StringWrap(c_str()).toInt(); }
    fpreal       toFloat() const
    { return UT_StringWrap(c_str()).toFloat(); }

    /// Determine if string can be seen as a single floating point number
    bool         isFloat(bool skip_spaces = false, bool loose = false) const
    { return UTstringIsFloat(*this, skip_spaces, loose); }
    /// Determine if string can be seen as a single integer number
    bool         isInteger(bool skip_spaces = false) const
    { return UTstringIsInteger(*this, skip_spaces); }

    SYS_FORCE_INLINE
    operator     const char *() const
                 { return c_str(); }

    SYS_FORCE_INLINE
    const char  *buffer() const
                 { return c_str(); }
    // We are always non-null by definition!
    SYS_FORCE_INLINE
    const char  *nonNullBuffer() const
                 { return c_str(); }

    /// Iterators
    typedef const char *        const_iterator;

    SYS_FORCE_INLINE
    const_iterator begin() const
                 { return c_str(); }
    SYS_FORCE_INLINE
    const_iterator end() const
                 { return begin() + length(); }


    /// Converts the contents of this UT_String to a std::string.  Since
    /// we are never null this is easy
    std::string toStdString() const
    { return std::string(c_str(), length()); }

    SYS_FORCE_INLINE
    void swap( UT_StringRef &other )
    {
        UTswap(myData, other.myData);
        UTswap(myLength, other.myLength);
        UTswap(myHash, other.myHash);
    }

    /// Friend specialization of std::swap() to use UT_StringRef::swap()
    friend void swap(UT_StringRef& a, UT_StringRef& b) { a.swap(b); }

    /// Equivalent to (length() != 0)
    /// Returns false for isSentinel()
    SYS_FORCE_INLINE
    bool isstring() const
        { return myData != nullptr; }

    /// Same as !isstring()
    bool isEmpty() const
         { return myData == nullptr; }

    /// method name that maches std::string
    bool empty() const
         { return myData == nullptr; }

    SYS_FORCE_INLINE
    bool
    hasNonSpace() const
    {
        const char *ptr = c_str();
        for (exint i = 0, n = length(); i < n; ++i)
            if (!SYSisspace(ptr[i]))
                return true;
        return false;
    }

    /// Find the location of the character @c (or -1 if not found)
    SYS_FORCE_INLINE
    exint
    findCharIndex(char c) const
    {
        const char *str = c_str();
        const void *ptr = ::memchr(str, c, length());
        return ptr ? (const char *)ptr - str : -1;
    }

    /// Find the first location of any of the characters in the @c str passed in
    SYS_FORCE_INLINE
    exint
    findCharIndex(const char *str) const
    {
        if (UTisstring(str))
        {
            const char *ptr = c_str();
            const char *found_char = strpbrk(ptr, str);
            if (found_char)
                return found_char - ptr;
        }
        return -1;
    }

    /// Find the location of the character @c (or -1 if not found)
    SYS_FORCE_INLINE
    exint
    findCharIndex(char c, exint start_offset) const
    {
        if (start_offset < length())
        {
            const char *str = c_str();
            const void *ptr = ::memchr(str+start_offset, c,
                                    length()-start_offset);
            if (ptr)
                return (const char *)ptr - str;
        }
        return -1;
    }

    /// Find the first location of any of the characters in the @c str passed in
    SYS_FORCE_INLINE
    exint
    findCharIndex(const char *str, exint start_offset) const
    {
        if (UTisstring(str) && start_offset < length())
        {
            const char *ptr = c_str();
            const char *found_char = strpbrk(ptr+start_offset, str);
            if (found_char)
                return found_char - ptr;
        }
        return -1;
    }

    SYS_FORCE_INLINE
    exint
    lastCharIndex(char c, int occurrence_number = 1) const
    {
        const char *str = c_str();
        exint            n = length();
        const void      *start = SYSmemrchr(str, c, n);
        while (start)
        {
            n = (const char *)start - str;
            occurrence_number--;
            if (occurrence_number <= 0)
                return n;
            start = (n == 0) ? nullptr : SYSmemrchr(str, c, n-1);
        }
        return -1;
    }

    /// Count the number of times the character @c c occurs
    SYS_FORCE_INLINE
    exint
    countChar(char c) const
    {
        return UTstringCountChar(*this, c);
    }

    SYS_FORCE_INLINE
    void clear()
    {
        decref();
        myData = nullptr;
        myLength = 0;
        myHash = 0;
    }

    SYS_FORCE_INLINE
    const char *c_str() const
    { 
        UT_ASSERT_P(!isSentinel());
        if (myLength)
        {
            UT_ASSERT_P(myDataIfChars);
            return myDataIfChars;
        }
        else if (myDataIfHolder)
            return myDataIfHolder->c_str();
        else
        {
#if SYS_IS_GCC_GE(6, 0) && !SYS_IS_GCC_GE(8, 0)
            // We need to do this to fix bad GCC warning:
            // offset outside bounds of constant string
            const char *volatile empty = "";
            return empty;
#else
            return "";
#endif
        }
    }
    SYS_FORCE_INLINE
    const char* data() const
    {
        return c_str();
    }

    exint               length() const
    {
        if (myLength)
            return myLength;
        else if (myDataIfHolder)
            return myDataIfHolder->length();
        else
            return 0;
    }

    unsigned            hash() const
    {
        if (!myHash && myData)
            myHash = hash_string(c_str(), length());
        return myHash;
    }

    /// Make a light weight reference to the source.
    /// Caller must make sure src lives for the duration of this object,
    /// and any objects value copied from this!
    void               reference(const char *src)
    {
        reference(src, src ? strlen(src) : 0);
    }

    /// Fast reference that takes the length of the string.
    /// This is NOT a string view, the string must actually null terminate
    /// at the given length or later functions will be confused.
    void                reference(const char *str, exint length);

    /// old name of method:
    void                fastReferenceWithStrlen(const char *src, exint length)
    {
        reference(src, length);
    }

    int64               getMemoryUsage(bool inclusive) const
    {
        int64 mem = inclusive ? sizeof(*this) : 0;
        if (!myLength && myDataIfHolder)
            mem += myDataIfHolder->getMemoryUsage(true);
        return mem;
    }

    // This hash function does not look for null termination, but
    // instead goes directly for the length.
    SYS_FORCE_INLINE
    static unsigned hash_string(const char *str, exint len)
    {
        return SYSstring_hash(str, len, /*allow_nulls*/true);
    }


    /// Convert the string into a valid C style variable name.
    /// All non-alpha numerics will be converted to _.
    /// If the first letter is a digit, it is prefixed with an _.
    /// If the string is already valid, the string itself is returned.
    /// Note that this does NOT force the name to be non-zero in length.
    /// The safechars parameter is a string containing extra characters
    /// that should be considered safe. These characters are not
    /// converted to underscores.
    SYS_NO_DISCARD_RESULT
    UT_StringRef forceValidVariableName(const char *safechars = nullptr) const;

    /// Convert to lower case.  If the string is already lower case, the string
    /// itself is returned.
    SYS_NO_DISCARD_RESULT
    UT_StringRef toLower() const;
    /// Convert to upper case. If the string is already upper case, the string
    /// itsef is returned.
    SYS_NO_DISCARD_RESULT
    UT_StringRef toUpper() const;

    /// Often people reflexively use this from UT_String days so
    /// this increases code compataibility.
    void         harden(const char *src)
    {
        setHolder(Holder::buildInline(src, src ? strlen(src) : 0));
    }

    // Steals the given string, gaining ownership of it.
    // Will be freed by this when the reference count hits zero.
    void                adoptFromMalloc(const char *str, exint length);
    void                adoptFromNew(const char *str, exint length);

    void                adoptFromString(UT_String &str)
    {
        if (!str.isstring())
        {
            clear();
            return;
        }
        // We want to steal from always deep strings as well.
        // We will erase the data in the source string!
        str.harden();

        adoptFromMalloc(str.myData, strlen(str.myData));

        // Clear after harden in case str refers to us!
        str.myData = 0;
        str.myIsReference = true;
        // Leave always deep as it was.
    }
    void                 adoptFromCharArray(UT_Array<char>& data);

    // Extracts a string from ourself of the given allocation mode.
    // The result can be freed with that allocation mode.
    // Will always clear myself afterwards.  This will return our
    // own string without copying if reference count is 1.
    // Will return 0 for empty strings.
    char                *stealAsMalloc();

    // Tests to see if UT_StringLit's memory layout is the same
    static bool          verifyStringLit();

    /// Does a "smart" string compare which will sort based on numbered names.
    /// That is "text20" is bigger than "text3".  In a strictly alphanumeric
    /// comparison, this would not be the case.
    struct NumberedCompare
    {
        bool operator()(const UT_StringRef &s1, const UT_StringRef &s2) const
        {
            return UT_String::compareNumberedString(s1.c_str(), s2.c_str()) < 0;
        }
    };

    /// Save string to binary stream.
    void         saveBinary(std::ostream &os) const
                    { UT_StringWrap(c_str()).saveBinary(os); }

    /// Save string to ASCII stream. This will add double quotes and escape to
    /// the stream if necessary (empty string or contains spaces).
    void         saveAscii(std::ostream &os) const
                    { UT_StringWrap(c_str()).saveAscii(os); }

private:
    SYS_FORCE_INLINE
    void incref() const
    {
        if (!myLength && myDataIfHolder)
            myDataIfHolder->incref();
    }

    SYS_FORCE_INLINE
    void decref()
    {
        if (!myLength && myDataIfHolder)
            myDataIfHolder->decref();
    }

    // this does not do holder->incref, and holder==nullptr is same as clear()
    void setHolder(Holder* holder)
    {
        decref();
        myDataIfHolder = holder;
        myLength = 0;
        myHash = 0;
    }

    // same as reference() except string is assumed to be empty, used by constructors
    void _reference(const char* str, exint length);

    void harden()
    {
        if (myLength)
        {
            myDataIfHolder = Holder::buildInline(myDataIfChars, myLength);
            myLength = 0;
        }
    }

    // This union makes viewing in a debugger much easier.
    union {
        const void      *myData;
        const char      *myDataIfChars;
        Holder          *myDataIfHolder;
    };
    int                  myLength;
    mutable int          myHash;

    /// This operator saves the string to the stream via the string's
    /// saveAscii() method, protecting any whitespace (by adding quotes),
    /// backslashes or quotes in the string.
    friend UT_API std::ostream  &operator<<(std::ostream &os, const UT_StringRef &d);
    friend UT_API UT_OStream    &operator<<(UT_OStream &os, const UT_StringRef &d);

    // UT_StringHolder needs to be a friend class so that the
    // UT_StringHolder(const UT_StringRef &) constructor can access myHash and
    // myDataIfHolder for the UT_StringRef that is passed in.
    friend class UT_StringHolder;

    static constexpr uint32 SENTINEL_HASH = 0xdeadbeef;
};

SYS_FORCE_INLINE size_t hash_value(const UT_StringRef &str)
{
    return str.hash();
}

/// Equality operators for UT_StringLit with UT_StringRef
/// @{
static SYS_FORCE_INLINE bool
operator==(const UT_StringRef &ref, const UT_StringLit &lit)
{
    return ref.operator==(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator==(const UT_StringLit &lit, const UT_StringRef &ref)
{
    return ref.operator==(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator!=(const UT_StringRef &ref, const UT_StringLit &lit)
{
    return ref.operator!=(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator!=(const UT_StringLit &lit, const UT_StringRef &ref)
{
    return ref.operator!=(lit.asRef());
}
/// @}

/// Equality operators for UT_StringLit with UT_String
/// @{
static SYS_FORCE_INLINE bool
operator==(const UT_String &str, const UT_StringLit &lit)
{
    return str.operator==(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator==(const UT_StringLit &lit, const UT_String &str)
{
    return str.operator==(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator!=(const UT_String &str, const UT_StringLit &lit)
{
    return str.operator!=(lit.asRef());
}
static SYS_FORCE_INLINE bool
operator!=(const UT_StringLit &lit, const UT_String &str)
{
    return str.operator!=(lit.asRef());
}
/// @}


/// A holder for a string, which stores the length and caches the hash value.
/// The lifetime of the string is >= the lifetime of the UT_StringHolder.
class UT_API UT_StringHolder : public UT_StringRef
{
public:
    /// UT_StringHolder can be constructed with UT_StringHolder::REFERENCE to
    /// create a shallow reference to the const char *.
    enum UT_StringReferenceType { REFERENCE };

    SYS_FORCE_INLINE
    UT_StringHolder()
        : UT_StringRef()
    {
    }

    /// Will make a copy of the provided string.
    SYS_FORCE_INLINE
    UT_StringHolder(const char *str)
        : UT_StringHolder(str, str ? strlen(str) : 0)
    {
    }

    /// Will make a shallow reference.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringReferenceType, const char *str)
        : UT_StringRef(str)
    {
    }

    /// Will make a copy of the provided string.
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, exint length)
    {
        myDataIfHolder = Holder::buildInline(data, length);
    }

    // Prohibit accidents when converting from UT_String like:
    //    myStringHolder(buffer, /*deep*/true)
    UT_StringHolder(const char *data, bool bad) = delete;

    // Add back explicit conversions for the length parameter
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, int32 length)
        : UT_StringHolder(data, exint(length)) { }
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, uint32 length)
        : UT_StringHolder(data, exint(length)) { }
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, uint64 length)
        : UT_StringHolder(data, exint(length)) { }
#if defined(MBSD)
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, size_t length)
        : UT_StringHolder(data, exint(length)) { }
    SYS_FORCE_INLINE
    UT_StringHolder(const char *data, ptrdiff_t length)
        : UT_StringHolder(data, exint(length)) { }
#endif

    /// Will make a copy of the provided string.
    SYS_FORCE_INLINE
    UT_StringHolder(const std::string &str)
        : UT_StringHolder(str.c_str(), str.length())
    {
    }

    /// This will make a shallow reference to the contents of the string.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringReferenceType, const std::string &str)
        : UT_StringRef(str)
    {
    }

    /// Will make a copy of the provided string.
    UT_StringHolder(const UT_WorkBuffer &str);

    /// This will make a shallow reference to the contents of the string.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringReferenceType, const UT_WorkBuffer &str)
        : UT_StringRef(str)
    {
    }

    /// Will make a copy of the provided string.
    SYS_FORCE_INLINE
    UT_StringHolder(const UT_String &str)
        : UT_StringHolder(str.buffer(), str.length())
    {
    }

    /// Attempts to steal the string's buffer
    UT_StringHolder(UT_String&& str)
        : UT_StringHolder()
    {
        adoptFromString(str);
    }

    /// This will make a shallow reference to the contents of the string.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringReferenceType, const UT_String &str)
        : UT_StringRef(str)
    {
    }

    /// Will make a copy of the provided string.
    UT_StringHolder(const UT_StringView &sv);

    /// Makes a shallow reference to the contents of the UT_StringRef.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringReferenceType, const UT_StringRef &ref)
        : UT_StringRef(ref)
    {
    }

    /// Makes a deep copy of the provided UT_StringRef.
    /// This constructor is not marked explicit since we often want this
    /// conversion (e.g. when inserting a UT_StringRef into a UT_StringMap, as
    /// with the const char* constructor).
    UT_StringHolder(const UT_StringRef &ref)
        : UT_StringRef(ref)
    {
        harden();
    }

    UT_StringHolder(UT_StringRef&& ref)
        : UT_StringRef(std::move(ref))
    {
        harden();
    }

    /// Construct as a sentinel value
    SYS_FORCE_INLINE explicit
    UT_StringHolder(UT_StringSentinelType sentinel)
        : UT_StringRef(sentinel)
    {
    }

    /// Makes a copy of the provided string.
    SYS_FORCE_INLINE
    UT_StringHolder(const UT_StringHolder &str)
        : UT_StringRef(str)
    {
    }

    /// Move constructor. Steals the working data from the original.
    SYS_FORCE_INLINE
    UT_StringHolder(UT_StringHolder &&a) noexcept
        : UT_StringRef(std::move(a))
    {
    }

    /// Move constructor. Steals the data from the work buffer.
    UT_StringHolder(UT_WorkBuffer &&buf) noexcept;

    /// Makes a bit-wise copy of the string and adjust the reference count.
    SYS_FORCE_INLINE
    UT_StringHolder &operator=(const UT_StringHolder &s)
    {
        UT_StringRef::operator=(s);
        return *this;
    }

    /// Move the contents of about-to-be-destructed string
    /// s to this string.
    SYS_FORCE_INLINE
    UT_StringHolder &operator=(UT_StringHolder &&s)
    {
        UT_StringRef::operator=(std::move(s));
        return *this;
    }

    /// Move the contents buffer into this string holder.
    UT_StringHolder &operator=(UT_WorkBuffer &&buf);

    SYS_FORCE_INLINE
    void swap(UT_StringHolder &other)
    {
        UT_StringRef::swap(other);
    }

    SYS_FORCE_INLINE
    void swap(UT_StringRef &other)
    {
        UT_StringRef::swap(other);
        // harden ourselves like UT_StringHolder::operator=(UT_StringRef&)
        harden();
    }

    /// Friend specialization of std::swap() to use UT_StringHolder::swap()
    /// @{
    friend void swap(UT_StringHolder& a, UT_StringRef& b) { a.swap(b); }
    friend void swap(UT_StringHolder& a, UT_StringHolder& b) { a.swap(b); }
    /// @}

    /// In some functions it's nice to be able to return a const-reference to a
    /// UT_StringHolder.  However, in error cases, you likely want to return an
    /// empty string.  This would mean that you'd have to return a real
    /// UT_StringHolder (not a const reference).  This static lets you return a
    /// reference to an empty string.
    static const UT_StringHolder theEmptyString;

    static const UT_StringHolder theSentinel;
    
    /// Format a string using the same formatting codes as @c UTformat.
    template<typename... Args>
    size_t format(const char *fmt, const Args &...args)
    {
        return format(fmt, {args...});
    }
    size_t format(const char *fmt, std::initializer_list<UT::Format::ArgValue> args);

    /// Format a string using the same formatting codes as @c UTprintf.
    template<typename... Args>
    SYS_DEPRECATED_HDK_REPLACE(19.5, UT_WorkBuffer::sprintf() to avoid string allocations)
    size_t sprintf(const char *fmt, const Args &...args)
    {
        return sprintf(fmt, {args...});
    }
    size_t sprintf(const char *fmt, std::initializer_list<UT::Format::ArgValue> args);

    /// Replaces up to 'count' occurrences of 'find' with 'replacement',
    /// and returns the number of substitutions that occurred.
    /// If 'count' <= 0, all occurrences will be replaced.
    int substitute(const char *find, const char *replacement, exint count = -1)
    {
        UT_String s(buffer());
        exint n = s.substitute(find, replacement, count);
        if (n > 0)
            adoptFromString(s);
        return n;
    }

    /// Strips out all characters found in 'chars'. The string length will be
    /// reduced by the number of characters removed. The number of characters
    /// removed is returned.
    int          strip(const char *chars);

    /// Prepend a string 
    // @{
    void         prepend(const UT_StringRef &prefix);
    // @}

    /// Load string from stream. Use is.eof() to check eof status
    bool load(UT_IStream &is)
    {
        UT_String s;
        if (s.load(is))
        {
            adoptFromString(s);
            return true;
        }
        return false;
    }

    UT_StringHolder &operator+=(const UT_StringRef &src);

    /// A version of trimSpace() that only removes leading and following spaces
    /// from a string, leaving any between words intact.
    bool         trimBoundingSpace();

    /// trimSpace() will remove all space characters (leading and following)
    /// from a string.  If the string consists of multiple words, the words
    /// will be collapsed. To keep a single space between words, pass in true.
    /// The function returns true if space was trimmed.
    bool         trimSpace(bool leave_single_space_between_words = false);

protected:
    friend UT_StringHolder UT::Literal::operator""_sh(
            const char *s, std::size_t const length);
    friend UT_StringHolder operator""_UTsh(
            const char *s, std::size_t const length);
    friend UT_API std::istream  &operator>>(std::istream& is, UT_StringHolder& s);

    /// A marker enum to use this constructor.
    enum UT_StringLiteralType { LITERAL };

    /// Only accepts string literals. Since there's no way to guarantee that
    /// a const char * argument is a string literal, we do this through the
    /// use of user-defined literal and *only* provide this constructor to our
    /// user-defined literal operator.
    SYS_FORCE_INLINE UT_StringHolder(UT_StringLiteralType, const char *str, size_t length)
    {
        if (str && length)
        {
            myDataIfChars = str;
            myLength = length;
            // As of C++14, user defined literals don't support constexpr so
            // this hash computation here is actually done at run-time except
            // for in some cases where the compiler (clang?) is able to
            // optimize this. Therefore, disable this to avoid extraneous hash
            // computation in cases where we just want to use "foo"_sh to avoid
            // heap allocation but never use its hash.
            // Use UT_StringLit if you want to get compile time hashes
#if 0
            myHash = SYSstring_hash_literal(str);
#else
            myHash = 0;
#endif
        }
    }
};

SYS_FORCE_INLINE size_t
hash_value(const UT_StringHolder &str)
{
    return str.hash();
}

/// Convert a UT_StringRef into a UT_StringHolder that is a shallow reference.
SYS_FORCE_INLINE const UT_StringHolder &UTmakeUnsafeRef(const UT_StringRef &ref)
{
    SYS_STATIC_ASSERT(sizeof(UT_StringRef) == sizeof(UT_StringHolder));
    return reinterpret_cast<const UT_StringHolder &>(ref);
}

/// Convert a UT_StringRef into a UT_StringHolder that is a shallow reference,
/// and also precompute the hash.  Use this for string literals
/// that will be used repeatedly in hash tables.
SYS_FORCE_INLINE const UT_StringHolder &UTmakeUnsafeRefHash(const UT_StringRef &ref)
{
    SYS_STATIC_ASSERT(sizeof(UT_StringRef) == sizeof(UT_StringHolder));
    ref.hash();
    return reinterpret_cast<const UT_StringHolder &>(ref);
}

SYS_FORCE_INLINE const UT_StringHolder &
UT_StringLit::asHolder() const
{
    SYS_STATIC_ASSERT(sizeof(UT_StringHolder) == sizeof(*this));
    return reinterpret_cast<const UT_StringHolder &>(*this);
}

SYS_FORCE_INLINE const UT_StringRef &
UT_StringLit::asRef() const
{
    SYS_STATIC_ASSERT(sizeof(UT_StringRef) == sizeof(*this));
    return reinterpret_cast<const UT_StringRef &>(*this);
}

/// A user-defined string literal to construct UT_StringHolder objects.
/// E.g:
/// @code
/// auto lit = "This is my UT_StringHolder literal"_sh;
/// @endcode
namespace UT { inline namespace Literal {
SYS_FORCE_INLINE UT_StringHolder operator""_sh(const char *s, std::size_t const length)
{
    return UT_StringHolder(UT_StringHolder::LITERAL, s, length);
}
} }

/// A user-defined literal in the global namespace. Uglier, but allows the use
/// of UT_StringHolder UDLs in headers. 
SYS_FORCE_INLINE UT_StringHolder operator""_UTsh(const char *s, std::size_t const length)
{
    return UT_StringHolder(UT_StringHolder::LITERAL, s, length);
}


namespace std
{
    template<>
    struct hash<UT_StringRef>
    {
        size_t operator()(const UT_StringRef &s) const
        {
            return s.hash();
        }
    };
    template<>
    struct hash<UT_StringHolder>
    {
        size_t operator()(const UT_StringHolder &s) const
        {
            return s.hash();
        }
    };
}

// For UT::ArraySet.
namespace UT
{
template <typename T>
struct DefaultClearer;

template <>
struct DefaultClearer<UT_StringHolder>
{
    static void clear(UT_StringHolder &v) { v.makeSentinel(); }
    static bool isClear(const UT_StringHolder &v) { return v.isSentinel(); }
    static void clearConstruct(UT_StringHolder *p)
    {
        new ((void *)p) UT_StringHolder(UT_StringRef::SENTINEL);
    }
    static const bool clearNeedsDestruction = false;
};
} // namespace UT

#endif // __UT_StringHolder_h__