Remove Vector returning split functions, use range adaptor

Do not allocate temporary vectors to store splitted data, use the
'split' range adaptor along with transform(unescape) to provide the
same feature with less allocations.

7 files changed, 97 insertions, 115 deletions

diff --git a/src/commands.cc b/src/commands.cc
index 8ae74c7c..8ee19c49 100644
--- a/src/commands.cc
+++ b/src/commands.cc
@@ -932,8 +932,8 @@ void define_command(const ParametersParser& parser, Context& context, const Shel
                                                           ShellManager::Flags::WaitForStdout,
                                                           shell_context).first;
             CandidateList candidates;
-            for (auto& str : split(output, '\n', 0))
-                candidates.push_back(std::move(str));
+            for (auto&& candidate : output | split<StringView>('\n'))
+                candidates.push_back(candidate.str());
 
             return Completions{ 0_byte, pos_in_token, std::move(candidates) };
         };
@@ -1579,7 +1579,7 @@ void context_wrap(const ParametersParser& parser, Context& context, Func func)
                 context_wrap_for_buffer(*buffer);
         }
         else
-            for (auto& name : split(*bufnames, ','))
+            for (auto&& name : *bufnames | split<StringView>(','))
                 context_wrap_for_buffer(BufferManager::instance().get_buffer(name));
         return;
     }
diff --git a/src/constexpr_utils.hh b/src/constexpr_utils.hh
index f1d3ce81..b0d5643f 100644
--- a/src/constexpr_utils.hh
+++ b/src/constexpr_utils.hh
@@ -5,6 +5,8 @@
 #include <initializer_list>
 #include <stddef.h>
 
+#include "array_view.hh"
+
 namespace Kakoune
 {
 
@@ -16,6 +18,9 @@ struct Array
     constexpr const T* begin() const { return m_data; }
     constexpr const T* end() const { return m_data+N; }
 
+    constexpr operator ArrayView<T>() { return {m_data, N}; }
+    constexpr operator ConstArrayView<T>() const { return {m_data, N}; }
+
     T m_data[N];
 };
 
diff --git a/src/normal.cc b/src/normal.cc
index a92eb257..0b3d8645 100644
--- a/src/normal.cc
+++ b/src/normal.cc
@@ -1185,9 +1185,13 @@ void select_object(Context& context, NormalParams params)
                     if (event != PromptEvent::Validate)
                         return;
 
-                    Vector<String> params = split(cmdline, ',', '\\');
-                    if (params.size() != 2 or params[0].empty() or params[1].empty())
-                        throw runtime_error{"desc parsing failed, expected <open>,<close>"};
+                    struct error : runtime_error { error(size_t) : runtime_error{"desc parsing failed, expected <open>,<close>"} {} };
+
+                    auto params = cmdline | split<StringView>(',', '\\') |
+                        transform(unescape<',', '\\'>) | static_gather<error, 2>();
+
+                    if (params[0].empty() or params[1].empty())
+                        throw error{0};
 
                     select_and_set_last<mode>(
                         context, std::bind(select_surrounding, _1, _2,
diff --git a/src/option_types.hh b/src/option_types.hh
index 219fcc69..0c3fc3e3 100644
--- a/src/option_types.hh
+++ b/src/option_types.hh
@@ -84,7 +84,8 @@ template<typename T, MemoryDomain domain>
 void option_from_string(StringView str, Vector<T, domain>& opt)
 {
     opt.clear();
-    for (auto& elem : split(str, list_separator, '\\'))
+    for (auto&& elem : str | split<StringView>(list_separator, '\\')
+                           | transform(unescape<list_separator, '\\'>))
     {
         T opt_elem;
         option_from_string(elem, opt_elem);
@@ -130,16 +131,18 @@ template<typename Key, typename Value, MemoryDomain domain>
 bool option_add(HashMap<Key, Value, domain>& opt, StringView str)
 {
     bool changed = false;
-    for (auto& elem : split(str, list_separator, '\\'))
+    for (auto&& elem : str | split<StringView>(list_separator, '\\')
+                           | transform(unescape<list_separator, '\\'>))
     {
-        Vector<String> pair_str = split(elem, '=', '\\');
-        if (pair_str.size() != 2)
-            throw runtime_error("map option expects key=value");
-        Key key;
-        Value value;
-        option_from_string(pair_str[0], key);
-        option_from_string(pair_str[1], value);
-        opt.insert({ std::move(key), std::move(value) });
+        struct error : runtime_error { error(size_t) : runtime_error{"map option expects key=value"} {} };
+        auto key_value = elem | split<StringView>('=', '\\')
+                              | transform(unescape<'=', '\\'>)
+                              | static_gather<error, 2>();
+
+        HashItem<Key, Value> item;
+        option_from_string(key_value[0], item.key);
+        option_from_string(key_value[1], item.value);
+        opt.insert(std::move(item));
         changed = true;
     }
     return changed;
@@ -200,11 +203,16 @@ String option_to_string(const std::tuple<Types...>& opt)
 template<typename... Types>
 void option_from_string(StringView str, std::tuple<Types...>& opt)
 {
-    auto elems = split(str, tuple_separator, '\\');
-    if (elems.size() != sizeof...(Types))
-        throw runtime_error(elems.size() < sizeof...(Types) ?
-                              "not enough elements in tuple"
-                            : "too many elements in tuple");
+    struct error : runtime_error
+    {
+        error(size_t i) : runtime_error{i < sizeof...(Types) ?
+                                          "not enough elements in tuple"
+                                        : "too many elements in tuple"} {}
+    };
+    auto elems = str | split<StringView>(tuple_separator, '\\')
+                     | transform(unescape<tuple_separator, '\\'>)
+                     | static_gather<error, sizeof...(Types)>();
+
     TupleOptionDetail<sizeof...(Types)-1, Types...>::from_string(elems, opt);
 }
 
@@ -246,9 +254,9 @@ inline void option_update(WorstMatch, const Context&)
 template<typename EffectiveType, typename LineType, typename ColumnType>
 inline void option_from_string(StringView str, LineAndColumn<EffectiveType, LineType, ColumnType>& opt)
 {
-    auto vals = split(str, ',');
-    if (vals.size() != 2)
-        throw runtime_error("expected <line>,<column>");
+    struct error : runtime_error { error(size_t) : runtime_error{"expected <line>,<column>"} {} };
+    auto vals = str | split<StringView>(',')
+                    | static_gather<error, 2>();
     opt.line = str_to_int(vals[0]);
     opt.column = str_to_int(vals[1]);
 }
diff --git a/src/ranges.hh b/src/ranges.hh
index 599396dc..9a4b1c8e 100644
--- a/src/ranges.hh
+++ b/src/ranges.hh
@@ -161,7 +161,8 @@ inline auto transform(Transform t)
     });
 }
 
-template<typename Range, typename Separator = ValueOf<Range>,
+template<typename Range, bool escape = false,
+         typename Element = ValueOf<Range>,
          typename ValueTypeParam = void>
 struct SplitView
 {
@@ -172,11 +173,15 @@ struct SplitView
 
     struct Iterator : std::iterator<std::forward_iterator_tag, ValueType>
     {
-        Iterator(RangeIt pos, RangeIt end, char separator)
-         : pos(pos), sep(pos), end(end), separator(separator)
+        Iterator(RangeIt pos, RangeIt end, Element separator, Element escaper)
+         : pos(pos), sep(pos), end(end), separator(separator), escaper(escaper)
         {
-            while (sep != end and *sep != separator)
+            bool escaped = false;
+            while (sep != end and (escaped or *sep != separator))
+            {
+                escaped = escape and *sep == escaper;
                 ++sep;
+            }
         }
 
         Iterator& operator++() { advance(); return *this; }
@@ -197,32 +202,45 @@ struct SplitView
             }
 
             pos = sep+1;
+            bool escaped = escape and *sep == escaper;
             for (sep = pos; sep != end; ++sep)
             {
-                if (*sep == separator)
+                if (not escaped and *sep == separator)
                     break;
+                escaped = escape and not escaped and *sep == escaper;
             }
         }
 
         RangeIt pos;
         RangeIt sep;
         RangeIt end;
-        Separator separator;
+        Element separator;
+        Element escaper;
     };
 
-    Iterator begin() const { return {std::begin(m_range), std::end(m_range), m_separator}; }
-    Iterator end()   const { return {std::end(m_range), std::end(m_range), m_separator}; }
+    Iterator begin() const { return {std::begin(m_range), std::end(m_range), m_separator, m_escaper}; }
+    Iterator end()   const { return {std::end(m_range), std::end(m_range), m_separator, m_escaper}; }
 
     Range m_range;
-    Separator m_separator;
+    Element m_separator;
+    Element m_escaper;
 };
 
-template<typename ValueType = void, typename Separator>
-auto split(Separator separator)
+template<typename ValueType = void, typename Element>
+auto split(Element separator)
 {
     return make_view_factory([s = std::move(separator)](auto&& range) {
         using Range = decltype(range);
-        return SplitView<decay_range<Range>, Separator, ValueType>{std::forward<Range>(range), std::move(s)};
+        return SplitView<decay_range<Range>, false, Element, ValueType>{std::forward<Range>(range), std::move(s), {}};
+    });
+}
+
+template<typename ValueType = void, typename Element>
+auto split(Element separator, Element escaper)
+{
+    return make_view_factory([s = std::move(separator), e = std::move(escaper)](auto&& range) {
+        using Range = decltype(range);
+        return SplitView<decay_range<Range>, true, Element, ValueType>{std::forward<Range>(range), std::move(s), std::move(e)};
     });
 }
 
@@ -340,20 +358,37 @@ auto gather()
 }
 
 template<typename ExceptionType, size_t... Indexes>
-auto elements()
+auto elements(bool exact_size = false)
 {
-    return make_view_factory([] (auto&& range) {
+    return make_view_factory([=] (auto&& range) {
         using std::begin; using std::end;
-        auto elem = [it = begin(range), end = end(range), i = 0u](size_t index) mutable {
-            for (; i < index; ++i, ++it)
-                if (it == end) throw ExceptionType{i};
+        auto it = begin(range), end_it = end(range);
+        size_t i = 0;
+        auto elem = [&](size_t index) {
+            for (; i < index; ++i)
+                if (++it == end_it) throw ExceptionType{i};
             return *it;
         };
         // Note that initializer lists elements are guaranteed to be sequenced
-        return Array<std::decay_t<decltype(*begin(range))>, sizeof...(Indexes)>{{elem(Indexes)...}};
+        Array<std::decay_t<decltype(*begin(range))>, sizeof...(Indexes)> res{{elem(Indexes)...}};
+        if (exact_size and ++it != end_it)
+            throw ExceptionType{++i};
+        return res;
     });
 }
 
+template<typename ExceptionType, size_t... Indexes>
+auto static_gather_impl(std::index_sequence<Indexes...>)
+{
+    return elements<ExceptionType, Indexes...>(true);
+}
+
+template<typename ExceptionType, size_t size>
+auto static_gather()
+{
+    return static_gather_impl<ExceptionType>(std::make_index_sequence<size>());
+}
+
 }
 
 #endif // ranges_hh_INCLUDED
diff --git a/src/string_utils.cc b/src/string_utils.cc
index 06e0eb7c..55c7562e 100644
--- a/src/string_utils.cc
+++ b/src/string_utils.cc
@@ -7,60 +7,6 @@
 namespace Kakoune
 {
 
-Vector<String> split(StringView str, char separator, char escape)
-{
-    Vector<String> res;
-    auto it = str.begin();
-    auto start = it;
-    while (it != str.end())
-    {
-        res.emplace_back();
-        String& element = res.back();
-        while (it != str.end())
-        {
-            auto c = *it;
-            if (c == escape and it + 1 != str.end() and *(it+1) == separator)
-            {
-                element += StringView{start, it+1};
-                element.back() = separator;
-                it += 2;
-                start = it;
-            }
-            else if (c == separator)
-            {
-                element += StringView{start, it};
-                ++it;
-                start = it;
-                break;
-            }
-            else
-                ++it;
-        }
-    }
-    if (start != str.end())
-        res.back() += StringView{start, str.end()};
-    return res;
-}
-
-Vector<StringView> split(StringView str, char separator)
-{
-    Vector<StringView> res;
-    if (str.empty())
-        return res;
-
-    auto beg = str.begin();
-    for (auto it = beg; it != str.end(); ++it)
-    {
-        if (*it == separator)
-        {
-            res.emplace_back(beg, it);
-            beg = it + 1;
-        }
-    }
-    res.emplace_back(beg, str.end());
-    return res;
-}
-
 StringView trim_whitespaces(StringView str)
 {
     auto beg = str.begin(), end = str.end();
@@ -390,22 +336,6 @@ UnitTest test_string{[]()
 {
     kak_assert(String("youpi ") + "matin" == "youpi matin");
 
-    Vector<String> splited = split("youpi:matin::tchou\\:kanaky:hihi\\:", ':', '\\');
-    kak_assert(splited[0] == "youpi");
-    kak_assert(splited[1] == "matin");
-    kak_assert(splited[2] == "");
-    kak_assert(splited[3] == "tchou:kanaky");
-    kak_assert(splited[4] == "hihi:");
-
-    Vector<StringView> splitedview = split("youpi:matin::tchou\\:kanaky:hihi\\:", ':');
-    kak_assert(splitedview[0] == "youpi");
-    kak_assert(splitedview[1] == "matin");
-    kak_assert(splitedview[2] == "");
-    kak_assert(splitedview[3] == "tchou\\");
-    kak_assert(splitedview[4] == "kanaky");
-    kak_assert(splitedview[5] == "hihi\\");
-    kak_assert(splitedview[6] == "");
-
     Vector<StringView> wrapped = wrap_lines("wrap this paragraph\n respecting whitespaces and much_too_long_words", 16);
     kak_assert(wrapped.size() == 6);
     kak_assert(wrapped[0] == "wrap this");
diff --git a/src/string_utils.hh b/src/string_utils.hh
index 7263c6f6..f1796f7c 100644
--- a/src/string_utils.hh
+++ b/src/string_utils.hh
@@ -8,14 +8,14 @@
 namespace Kakoune
 {
 
-Vector<String> split(StringView str, char separator, char escape);
-Vector<StringView> split(StringView str, char separator);
-
 StringView trim_whitespaces(StringView str);
 
 String escape(StringView str, StringView characters, char escape);
 String unescape(StringView str, StringView characters, char escape);
 
+template<char character, char escape>
+String unescape(StringView str) { return unescape(str, character, escape); }
+
 String indent(StringView str, StringView indent = "    ");
 
 String replace(StringView str, StringView substr, StringView replacement);