Add support for using C++17 string_view or a fallback

Define a `cm::string_view` type implemented via C++17 `std::string_view`
when available.  Provide a fallback implementation for C++11 and C++14
compilers.

The fallback implementation was written by reading documentation of the
standard spec.  We have no dedicated tests for it, but it will be
covered by tests of its clients later.

4 files changed, 521 insertions, 0 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index 9aebfa7..4bf2e73 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -375,6 +375,8 @@ set(SRCS
   cmXMLWriter.h
   cmake.cxx
   cmake.h
+  cm_string_view.cxx
+  cm_string_view.hxx
 
   cmCommand.cxx
   cmCommand.h
diff --git a/Source/cm_string_view.cxx b/Source/cm_string_view.cxx
new file mode 100644
index 0000000..61fa80e
--- /dev/null
+++ b/Source/cm_string_view.cxx
@@ -0,0 +1,301 @@
+/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
+   file Copyright.txt or https://cmake.org/licensing for details.  */
+
+#include "cm_string_view.hxx"
+
+#ifndef CMake_HAVE_CXX_STRING_VIEW
+
+#  include "cm_kwiml.h"
+
+#  include <algorithm>
+#  include <ostream>
+#  include <stdexcept>
+
+namespace cm {
+
+string_view::const_reference string_view::at(size_type pos) const
+{
+  if (pos >= size_) {
+    throw std::out_of_range("Index out of range in string_view::at");
+  }
+  return data_[pos];
+}
+
+string_view::size_type string_view::copy(char* dest, size_type count,
+                                         size_type pos) const
+{
+  if (pos > size_) {
+    throw std::out_of_range("Index out of range in string_view::copy");
+  }
+  size_type const rcount = std::min(count, size_ - pos);
+  traits_type::copy(dest, data_ + pos, rcount);
+  return rcount;
+}
+
+string_view string_view::substr(size_type pos, size_type count) const
+{
+  if (pos > size_) {
+    throw std::out_of_range("Index out of range in string_view::substr");
+  }
+  size_type const rcount = std::min(count, size_ - pos);
+  return string_view(data_ + pos, rcount);
+}
+
+int string_view::compare(string_view v) const noexcept
+{
+  size_type const rlen = std::min(size_, v.size_);
+  int c = traits_type::compare(data_, v.data_, rlen);
+  if (c == 0) {
+    if (size_ < v.size_) {
+      c = -1;
+    } else if (size_ > v.size_) {
+      c = 1;
+    }
+  }
+  return c;
+}
+
+int string_view::compare(size_type pos1, size_type count1, string_view v) const
+{
+  return substr(pos1, count1).compare(v);
+}
+
+int string_view::compare(size_type pos1, size_type count1, string_view v,
+                         size_type pos2, size_type count2) const
+{
+  return substr(pos1, count1).compare(v.substr(pos2, count2));
+}
+
+int string_view::compare(const char* s) const
+{
+  return compare(string_view(s));
+}
+
+int string_view::compare(size_type pos1, size_type count1, const char* s) const
+{
+  return substr(pos1, count1).compare(string_view(s));
+}
+
+int string_view::compare(size_type pos1, size_type count1, const char* s,
+                         size_type count2) const
+{
+  return substr(pos1, count1).compare(string_view(s, count2));
+}
+
+string_view::size_type string_view::find(string_view v, size_type pos) const
+  noexcept
+{
+  for (; pos + v.size_ <= size_; ++pos) {
+    if (std::char_traits<char>::compare(data_ + pos, v.data_, v.size_) == 0) {
+      return pos;
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::find(char c, size_type pos) const noexcept
+{
+  return find(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::find(const char* s, size_type pos,
+                                         size_type count) const
+{
+  return find(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::find(const char* s, size_type pos) const
+{
+  return find(string_view(s), pos);
+}
+
+string_view::size_type string_view::rfind(string_view v, size_type pos) const
+  noexcept
+{
+  if (size_ >= v.size_) {
+    for (pos = std::min(pos, size_ - v.size_) + 1; pos > 0;) {
+      --pos;
+      if (std::char_traits<char>::compare(data_ + pos, v.data_, v.size_) ==
+          0) {
+        return pos;
+      }
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::rfind(char c, size_type pos) const noexcept
+{
+  return rfind(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::rfind(const char* s, size_type pos,
+                                          size_type count) const
+{
+  return rfind(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::rfind(const char* s, size_type pos) const
+{
+  return rfind(string_view(s), pos);
+}
+
+string_view::size_type string_view::find_first_of(string_view v,
+                                                  size_type pos) const noexcept
+{
+  for (; pos < size_; ++pos) {
+    if (traits_type::find(v.data_, v.size_, data_[pos])) {
+      return pos;
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::find_first_of(char c, size_type pos) const
+  noexcept
+{
+  return find_first_of(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::find_first_of(const char* s, size_type pos,
+                                                  size_type count) const
+{
+  return find_first_of(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::find_first_of(const char* s,
+                                                  size_type pos) const
+{
+  return find_first_of(string_view(s), pos);
+}
+
+string_view::size_type string_view::find_last_of(string_view v,
+                                                 size_type pos) const noexcept
+{
+  if (size_ > 0) {
+    for (pos = std::min(pos, size_ - 1) + 1; pos > 0;) {
+      --pos;
+      if (traits_type::find(v.data_, v.size_, data_[pos])) {
+        return pos;
+      }
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::find_last_of(char c, size_type pos) const
+  noexcept
+{
+  return find_last_of(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::find_last_of(const char* s, size_type pos,
+                                                 size_type count) const
+{
+  return find_last_of(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::find_last_of(const char* s,
+                                                 size_type pos) const
+{
+  return find_last_of(string_view(s), pos);
+}
+
+string_view::size_type string_view::find_first_not_of(string_view v,
+                                                      size_type pos) const
+  noexcept
+{
+  for (; pos < size_; ++pos) {
+    if (!traits_type::find(v.data_, v.size_, data_[pos])) {
+      return pos;
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::find_first_not_of(char c,
+                                                      size_type pos) const
+  noexcept
+{
+  return find_first_not_of(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::find_first_not_of(const char* s,
+                                                      size_type pos,
+                                                      size_type count) const
+{
+  return find_first_not_of(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::find_first_not_of(const char* s,
+                                                      size_type pos) const
+{
+  return find_first_not_of(string_view(s), pos);
+}
+
+string_view::size_type string_view::find_last_not_of(string_view v,
+                                                     size_type pos) const
+  noexcept
+{
+  if (size_ > 0) {
+    for (pos = std::min(pos, size_ - 1) + 1; pos > 0;) {
+      --pos;
+      if (!traits_type::find(v.data_, v.size_, data_[pos])) {
+        return pos;
+      }
+    }
+  }
+  return npos;
+}
+
+string_view::size_type string_view::find_last_not_of(char c,
+                                                     size_type pos) const
+  noexcept
+{
+  return find_last_not_of(string_view(&c, 1), pos);
+}
+
+string_view::size_type string_view::find_last_not_of(const char* s,
+                                                     size_type pos,
+                                                     size_type count) const
+{
+  return find_last_not_of(string_view(s, count), pos);
+}
+
+string_view::size_type string_view::find_last_not_of(const char* s,
+                                                     size_type pos) const
+{
+  return find_last_not_of(string_view(s), pos);
+}
+
+std::ostream& operator<<(std::ostream& o, string_view v)
+{
+  return o.write(v.data(), v.size());
+}
+
+std::string& operator+=(std::string& s, string_view v)
+{
+  s.append(v.data(), v.size());
+  return s;
+}
+}
+
+std::hash<cm::string_view>::result_type std::hash<cm::string_view>::operator()(
+  argument_type const& s) const noexcept
+{
+  // FNV-1a hash.
+  static KWIML_INT_uint64_t const fnv_offset_basis = 0xcbf29ce484222325;
+  static KWIML_INT_uint64_t const fnv_prime = 0x100000001b3;
+  KWIML_INT_uint64_t h = fnv_offset_basis;
+  for (char const& c : s) {
+    h = h ^ KWIML_INT_uint64_t(KWIML_INT_uint8_t(c));
+    h = h * fnv_prime;
+  }
+  return result_type(h);
+}
+#else
+// Avoid empty translation unit.
+void cm_string_view_cxx()
+{
+}
+#endif
diff --git a/Source/cm_string_view.hxx b/Source/cm_string_view.hxx
new file mode 100644
index 0000000..d368ed8
--- /dev/null
+++ b/Source/cm_string_view.hxx
@@ -0,0 +1,217 @@
+/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
+   file Copyright.txt or https://cmake.org/licensing for details.  */
+#ifndef cm_string_view_hxx
+#define cm_string_view_hxx
+
+#include "cmConfigure.h" // IWYU pragma: keep
+
+#if __cplusplus >= 201703L || defined(_MSVC_LANG) && _MSVC_LANG >= 201703L
+#  define CMake_HAVE_CXX_STRING_VIEW
+#endif
+
+#ifdef CMake_HAVE_CXX_STRING_VIEW
+#  include <string_view>
+namespace cm {
+using std::string_view;
+}
+#else
+#  include <cstddef>
+#  include <functional>
+#  include <iosfwd>
+#  include <iterator>
+#  include <string>
+
+namespace cm {
+
+class string_view
+{
+public:
+  using traits_type = std::string::traits_type;
+  using value_type = char;
+  using pointer = char*;
+  using const_pointer = const char*;
+  using reference = char&;
+  using const_reference = char const&;
+  using const_iterator = const char*;
+  using iterator = const_iterator;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using reverse_iterator = const_reverse_iterator;
+  using size_type = std::string::size_type;
+  using difference_type = std::string::difference_type;
+
+  static size_type const npos = static_cast<size_type>(-1);
+
+  string_view() noexcept = default;
+  string_view(string_view const&) noexcept = default;
+
+  string_view(const char* s, size_t count) noexcept
+    : data_(s)
+    , size_(count)
+  {
+  }
+
+  string_view(const char* s) noexcept
+    : data_(s)
+    , size_(traits_type::length(s))
+  {
+  }
+
+  // C++17 does not define this constructor.  Instead it defines
+  // a conversion operator on std::string to create a string_view.
+  // Since this implementation is used in C++11, std::string does
+  // not have that conversion.
+  string_view(std::string const& s) noexcept
+    : data_(s.data())
+    , size_(s.size())
+  {
+  }
+
+  // C++17 does not define this conversion.  Instead it defines
+  // a constructor on std::string that can take a string_view.
+  // Since this implementation is used in C++11, std::string does
+  // not have that constructor.
+  explicit operator std::string() const { return std::string(data_, size_); }
+
+  string_view& operator=(string_view const&) = default;
+
+  const_iterator begin() const noexcept { return data_; }
+  const_iterator end() const noexcept { return data_ + size_; }
+  const_iterator cbegin() const noexcept { return begin(); }
+  const_iterator cend() const noexcept { return end(); }
+
+  const_reverse_iterator rbegin() const noexcept
+  {
+    return const_reverse_iterator(end());
+  }
+  const_reverse_iterator rend() const noexcept
+  {
+    return const_reverse_iterator(begin());
+  }
+  const_reverse_iterator crbegin() const noexcept { return rbegin(); }
+  const_reverse_iterator crend() const noexcept { return rend(); }
+
+  const_reference operator[](size_type pos) const noexcept
+  {
+    return data_[pos];
+  }
+  const_reference at(size_type pos) const;
+  const_reference front() const noexcept { return data_[0]; }
+  const_reference back() const noexcept { return data_[size_ - 1]; }
+  const_pointer data() const noexcept { return data_; }
+
+  size_type size() const noexcept { return size_; }
+  size_type length() const noexcept { return size_; }
+  size_type max_size() const noexcept { return npos - 1; }
+  bool empty() const noexcept { return size_ == 0; }
+
+  void remove_prefix(size_type n) noexcept
+  {
+    data_ += n;
+    size_ -= n;
+  }
+  void remove_suffix(size_type n) noexcept { size_ -= n; }
+  void swap(string_view& v) noexcept
+  {
+    string_view tmp = v;
+    v = *this;
+    *this = tmp;
+  }
+
+  size_type copy(char* dest, size_type count, size_type pos = 0) const;
+  string_view substr(size_type pos = 0, size_type count = npos) const;
+
+  int compare(string_view v) const noexcept;
+  int compare(size_type pos1, size_type count1, string_view v) const;
+  int compare(size_type pos1, size_type count1, string_view v, size_type pos2,
+              size_type count2) const;
+  int compare(const char* s) const;
+  int compare(size_type pos1, size_type count1, const char* s) const;
+  int compare(size_type pos1, size_type count1, const char* s,
+              size_type count2) const;
+
+  size_type find(string_view v, size_type pos = 0) const noexcept;
+  size_type find(char c, size_type pos = 0) const noexcept;
+  size_type find(const char* s, size_type pos, size_type count) const;
+  size_type find(const char* s, size_type pos = 0) const;
+
+  size_type rfind(string_view v, size_type pos = npos) const noexcept;
+  size_type rfind(char c, size_type pos = npos) const noexcept;
+  size_type rfind(const char* s, size_type pos, size_type count) const;
+  size_type rfind(const char* s, size_type pos = npos) const;
+
+  size_type find_first_of(string_view v, size_type pos = 0) const noexcept;
+  size_type find_first_of(char c, size_type pos = 0) const noexcept;
+  size_type find_first_of(const char* s, size_type pos, size_type count) const;
+  size_type find_first_of(const char* s, size_type pos = 0) const;
+
+  size_type find_last_of(string_view v, size_type pos = npos) const noexcept;
+  size_type find_last_of(char c, size_type pos = npos) const noexcept;
+  size_type find_last_of(const char* s, size_type pos, size_type count) const;
+  size_type find_last_of(const char* s, size_type pos = npos) const;
+
+  size_type find_first_not_of(string_view v, size_type pos = 0) const noexcept;
+  size_type find_first_not_of(char c, size_type pos = 0) const noexcept;
+  size_type find_first_not_of(const char* s, size_type pos,
+                              size_type count) const;
+  size_type find_first_not_of(const char* s, size_type pos = 0) const;
+
+  size_type find_last_not_of(string_view v, size_type pos = npos) const
+    noexcept;
+  size_type find_last_not_of(char c, size_type pos = npos) const noexcept;
+  size_type find_last_not_of(const char* s, size_type pos,
+                             size_type count) const;
+  size_type find_last_not_of(const char* s, size_type pos = npos) const;
+
+private:
+  const char* data_ = nullptr;
+  size_type size_ = 0;
+};
+
+std::ostream& operator<<(std::ostream& o, string_view v);
+
+std::string& operator+=(std::string& s, string_view v);
+
+inline bool operator==(string_view l, string_view r) noexcept
+{
+  return l.compare(r) == 0;
+}
+
+inline bool operator!=(string_view l, string_view r) noexcept
+{
+  return l.compare(r) != 0;
+}
+
+inline bool operator<(string_view l, string_view r) noexcept
+{
+  return l.compare(r) < 0;
+}
+
+inline bool operator<=(string_view l, string_view r) noexcept
+{
+  return l.compare(r) <= 0;
+}
+
+inline bool operator>(string_view l, string_view r) noexcept
+{
+  return l.compare(r) > 0;
+}
+
+inline bool operator>=(string_view l, string_view r) noexcept
+{
+  return l.compare(r) >= 0;
+}
+}
+
+namespace std {
+
+template <>
+struct hash<cm::string_view>
+{
+  typedef cm::string_view argument_type;
+  typedef size_t result_type;
+  result_type operator()(argument_type const& s) const noexcept;
+};
+}
+
+#endif
+#endif
diff --git a/bootstrap b/bootstrap
index 6710d1a..dcc3a83 100755
--- a/bootstrap
+++ b/bootstrap
@@ -430,6 +430,7 @@ CMAKE_CXX_SOURCES="\
   cmake  \
   cmakemain \
   cmcmd  \
+  cm_string_view \
 "
 
 if ${cmake_system_mingw}; then