BLI: generally improve C++ data structures

The main focus here was to improve the docs significantly. Furthermore,
I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually)
faster, simpler and more customizable. I also rewrote `Stack` to make
it more efficient by avoiding unnecessary copies.

Thanks to everyone who helped with constructive feedback.

Approved by brecht and sybren.

Differential Revision: https://developer.blender.org/D7931

1 files changed, 104 insertions, 25 deletions

diff --git a/source/blender/blenlib/BLI_string_ref.hh b/source/blender/blenlib/BLI_string_ref.hh
index eacc501375a..6a569bee1aa 100644
--- a/source/blender/blenlib/BLI_string_ref.hh
+++ b/source/blender/blenlib/BLI_string_ref.hh
@@ -20,12 +20,26 @@
 /** \file
  * \ingroup bli
  *
- * A StringRef is a pointer to a string somewhere in memory. It should not be used to transfer
- * ownership of that string. When a function gets a StringRef as input, it cannot expect, that
- * the string will still exist after the function ends.
+ * A `BLI::StringRef` references a const char array owned by someone else. It is just a pointer and
+ * a size. Since the memory is not owned, StringRef should not be used to transfer ownership of the
+ * string. The data referenced by a StringRef cannot be mutated through it.
  *
- * There are two types of string references: One that guarantees null termination and one that does
- * not.
+ * A StringRef is NOT null-terminated. This makes it much more powerful within C++, because we can
+ * also cut off parts of the end without creating a copy. When interfacing with C code that expects
+ * null-terminated strings, `BLI::StringRefNull` can be used. It is essentially the same as
+ * StringRef, but with the restriction that the string has to be null-terminated.
+ *
+ * Whenever possible, string parameters should be of type StringRef and the string return type
+ * should be StringRefNull. Don't forget that the StringRefNull does not own the string, so don't
+ * return it when the string exists only in the scope of the function. This convention makes
+ * functions usable in the most contexts.
+ *
+ * BLI::StringRef vs. std::string_view:
+ *   Both types are certainly very similar. The main benefit of using StringRef in Blender is that
+ *   this allows us to add convenience methods at any time. Especially, when doing a lot of string
+ *   manipulation, this helps to keep the code clean. Furthermore, we need StringRefNull anyway,
+ *   because there is a lot of C code that expects null-terminated strings. Once we use C++17,
+ *   implicit conversions to and from string_view can be added.
  */
 
 #include <cstring>
@@ -39,15 +53,16 @@ namespace BLI {
 
 class StringRef;
 
+/**
+ * A common base class for StringRef and StringRefNull. This should never be used in other files.
+ * It only exists to avoid some code duplication.
+ */
 class StringRefBase {
- public:
-  using size_type = size_t;
-
  protected:
   const char *m_data;
-  size_type m_size;
+  uint m_size;
 
-  StringRefBase(const char *data, size_type size) : m_data(data), m_size(size)
+  StringRefBase(const char *data, uint size) : m_data(data), m_size(size)
   {
   }
 
@@ -55,7 +70,7 @@ class StringRefBase {
   /**
    * Return the (byte-)length of the referenced string, without any null-terminator.
    */
-  size_type size() const
+  uint size() const
   {
     return m_size;
   }
@@ -68,17 +83,15 @@ class StringRefBase {
     return m_data;
   }
 
-  char operator[](size_type index) const
-  {
-    BLI_assert(index <= m_size);
-    return m_data[index];
-  }
-
   operator ArrayRef<char>() const
   {
     return ArrayRef<char>(m_data, m_size);
   }
 
+  /**
+   * Implicitely convert to std::string. This is convenient in most cases, but you have to be a bit
+   * careful not to convert to std::string accidentally.
+   */
   operator std::string() const
   {
     return std::string(m_data, m_size);
@@ -94,12 +107,21 @@ class StringRefBase {
     return m_data + m_size;
   }
 
+  /**
+   * Copy the string into a buffer. The buffer has to be one byte larger than the size of the
+   * string, because the copied string will be null-terminated. Only use this when you are
+   * absolutely sure that the buffer is large enough.
+   */
   void unsafe_copy(char *dst) const
   {
     memcpy(dst, m_data, m_size);
     dst[m_size] = '\0';
   }
 
+  /**
+   * Copy the string into a buffer. The copied string will be null-terminated. This invokes
+   * undefined behavior when dst_size is too small. (Should we define the behavior?)
+   */
   void copy(char *dst, uint dst_size) const
   {
     if (m_size < dst_size) {
@@ -111,6 +133,10 @@ class StringRefBase {
     }
   }
 
+  /**
+   * Copy the string into a char array. The copied string will be null-terminated. This invokes
+   * undefined behavior when dst is too small.
+   */
   template<uint N> void copy(char (&dst)[N])
   {
     this->copy(dst, N);
@@ -130,7 +156,7 @@ class StringRefBase {
 };
 
 /**
- * References a null-terminated char array.
+ * References a null-terminated const char array.
  */
 class StringRefNull : public StringRefBase {
 
@@ -139,24 +165,45 @@ class StringRefNull : public StringRefBase {
   {
   }
 
-  StringRefNull(const char *str) : StringRefBase(str, strlen(str))
+  /**
+   * Construct a StringRefNull from a null terminated c-string. The pointer must not point to NULL.
+   */
+  StringRefNull(const char *str) : StringRefBase(str, (uint)strlen(str))
   {
     BLI_assert(str != NULL);
     BLI_assert(m_data[m_size] == '\0');
   }
 
-  StringRefNull(const char *str, size_type size) : StringRefBase(str, size)
+  /**
+   * Construct a StringRefNull from a null terminated c-string. This invokes undefined behavior
+   * when the given size is not the correct size of the string.
+   */
+  StringRefNull(const char *str, uint size) : StringRefBase(str, size)
   {
-    BLI_assert(str[size] == '\0');
+    BLI_assert((uint)strlen(str) == size);
   }
 
+  /**
+   * Reference a std::string. Remember that when the std::string is destructed, the StringRefNull
+   * will point to uninitialized memory.
+   */
   StringRefNull(const std::string &str) : StringRefNull(str.data())
   {
   }
+
+  /**
+   * Get the char at the given index.
+   */
+  char operator[](uint index) const
+  {
+    /* Use '<=' instead of just '<', so that the null character can be accessed as well. */
+    BLI_assert(index <= m_size);
+    return m_data[index];
+  }
 };
 
 /**
- * References a char array. It might not be null terminated.
+ * References a const char array. It might not be null terminated.
  */
 class StringRef : public StringRefBase {
  public:
@@ -164,19 +211,29 @@ class StringRef : public StringRefBase {
   {
   }
 
+  /**
+   * StringRefNull can be converted into StringRef, but not the other way around.
+   */
   StringRef(StringRefNull other) : StringRefBase(other.data(), other.size())
   {
   }
 
-  StringRef(const char *str) : StringRefBase(str, str ? strlen(str) : 0)
+  /**
+   * Create a StringRef from a null-terminated c-string.
+   */
+  StringRef(const char *str) : StringRefBase(str, str ? (uint)strlen(str) : 0)
   {
   }
 
-  StringRef(const char *str, size_type length) : StringRefBase(str, length)
+  StringRef(const char *str, uint length) : StringRefBase(str, length)
   {
   }
 
-  StringRef(const std::string &str) : StringRefBase(str.data(), str.size())
+  /**
+   * Reference a std::string. Remember that when the std::string is destructed, the StringRef
+   * will point to uninitialized memory.
+   */
+  StringRef(const std::string &str) : StringRefBase(str.data(), (uint)str.size())
   {
   }
 
@@ -198,6 +255,15 @@ class StringRef : public StringRefBase {
     BLI_assert(this->startswith(prefix));
     return this->drop_prefix(prefix.size());
   }
+
+  /**
+   * Get the char at the given index.
+   */
+  char operator[](uint index) const
+  {
+    BLI_assert(index < m_size);
+    return m_data[index];
+  }
 };
 
 /* More inline functions
@@ -215,6 +281,10 @@ inline std::ostream &operator<<(std::ostream &stream, StringRefNull ref)
   return stream;
 }
 
+/**
+ * Adding two StringRefs will allocate an std::string. This is not efficient, but convenient in
+ * most cases.
+ */
 inline std::string operator+(StringRef a, StringRef b)
 {
   return std::string(a) + std::string(b);
@@ -233,6 +303,9 @@ inline bool operator!=(StringRef a, StringRef b)
   return !(a == b);
 }
 
+/**
+ * Return true when the string starts with the given prefix.
+ */
 inline bool StringRefBase::startswith(StringRef prefix) const
 {
   if (m_size < prefix.m_size) {
@@ -246,6 +319,9 @@ inline bool StringRefBase::startswith(StringRef prefix) const
   return true;
 }
 
+/**
+ * Return true when the string ends with the given suffix.
+ */
 inline bool StringRefBase::endswith(StringRef suffix) const
 {
   if (m_size < suffix.m_size) {
@@ -260,6 +336,9 @@ inline bool StringRefBase::endswith(StringRef suffix) const
   return true;
 }
 
+/**
+ * Return a new StringRef containing only a substring of the original string.
+ */
 inline StringRef StringRefBase::substr(uint start, uint size) const
 {
   BLI_assert(start + size <= m_size);