LibLine: Handle history across multiple concurrent sessions better

- Store history entries as (timestamp)::(entry)\n\n
- Merge the entries together when saving to avoid loss of history
  entries

To ideally make having two concurrently open shells
(or `js` repls or whatever) not overwrite each others' history entries.

5 files changed, 88 insertions, 18 deletions

diff --git a/Applications/Debugger/main.cpp b/Applications/Debugger/main.cpp
index 09128bacdd..4feef9c4db 100644
--- a/Applications/Debugger/main.cpp
+++ b/Applications/Debugger/main.cpp
@@ -269,7 +269,7 @@ int main(int argc, char** argv)
             Optional<Debug::DebugSession::DebugDecision> decision;
 
             if (command.is_empty() && !editor->history().is_empty()) {
-                command = editor->history().last();
+                command = editor->history().last().entry;
             }
             if (command == "cont") {
                 decision = Debug::DebugSession::DebugDecision::Continue;
@@ -300,7 +300,7 @@ int main(int argc, char** argv)
 
             if (success && !command.is_empty()) {
                 // Don't add repeated commands to history
-                if (editor->history().is_empty() || editor->history().last() != command)
+                if (editor->history().is_empty() || editor->history().last().entry != command)
                     editor->add_to_history(command);
             }
             if (!success) {
diff --git a/Libraries/LibLine/Editor.cpp b/Libraries/LibLine/Editor.cpp
index 7ed04b93c4..0ac1fe100c 100644
--- a/Libraries/LibLine/Editor.cpp
+++ b/Libraries/LibLine/Editor.cpp
@@ -212,13 +212,15 @@ void Editor::add_to_history(const String& line)
     String histcontrol = getenv("HISTCONTROL");
     auto ignoredups = histcontrol == "ignoredups" || histcontrol == "ignoreboth";
     auto ignorespace = histcontrol == "ignorespace" || histcontrol == "ignoreboth";
-    if (ignoredups && !m_history.is_empty() && line == m_history.last())
+    if (ignoredups && !m_history.is_empty() && line == m_history.last().entry)
         return;
     if (ignorespace && line.starts_with(' '))
         return;
     if ((m_history.size() + 1) > m_history_capacity)
         m_history.take_first();
-    m_history.append(line);
+    struct timeval tv;
+    gettimeofday(&tv, nullptr);
+    m_history.append({ line, tv.tv_sec });
 }
 
 bool Editor::load_history(const String& path)
@@ -226,22 +228,86 @@ bool Editor::load_history(const String& path)
     auto history_file = Core::File::construct(path);
     if (!history_file->open(Core::IODevice::ReadOnly))
         return false;
-    while (history_file->can_read_line()) {
-        add_to_history(history_file->read_line());
+    auto data = history_file->read_all();
+    auto hist = StringView { data.data(), data.size() };
+    for (auto& str : hist.split_view("\n\n")) {
+        auto it = str.find_first_of("::").value_or(0);
+        auto time = str.substring_view(0, it).to_uint<time_t>().value_or(0);
+        auto string = str.substring_view(it == 0 ? it : it + 2);
+        m_history.append({ string, time });
     }
     return true;
 }
 
+template<typename It0, typename It1, typename OutputT, typename MapperT, typename LessThan>
+static void merge(It0&& begin0, const It0& end0, It1&& begin1, const It1& end1, OutputT& output, MapperT left_mapper, LessThan less_than)
+{
+    for (;;) {
+        if (begin0 == end0 && begin1 == end1)
+            return;
+
+        if (begin0 == end0) {
+            auto&& right = *begin1;
+            if (output.last().entry != right.entry)
+                output.append(right);
+            ++begin1;
+            continue;
+        }
+
+        auto&& left = left_mapper(*begin0);
+        if (left.entry.is_whitespace()) {
+            ++begin0;
+            continue;
+        }
+        if (begin1 == end1) {
+            if (output.last().entry != left.entry)
+                output.append(left);
+            ++begin0;
+            continue;
+        }
+
+        auto&& right = *begin1;
+        if (less_than(left, right)) {
+            if (output.last().entry != left.entry)
+                output.append(left);
+            ++begin0;
+        } else {
+            if (output.last().entry != right.entry)
+                output.append(right);
+            ++begin1;
+            if (right.entry == left.entry)
+                ++begin0;
+        }
+    }
+}
+
 bool Editor::save_history(const String& path)
 {
+    Vector<HistoryEntry> final_history { { "", 0 } };
+    {
+        auto file_or_error = Core::File::open(path, Core::IODevice::ReadWrite, 0600);
+        if (file_or_error.is_error())
+            return false;
+        auto file = file_or_error.release_value();
+        merge(
+            file->line_begin(), file->line_end(), m_history.begin(), m_history.end(), final_history,
+            [](StringView str) {
+                auto it = str.find_first_of("::").value_or(0);
+                auto time = str.substring_view(0, it).to_uint<time_t>().value_or(0);
+                auto string = str.substring_view(it == 0 ? it : it + 2);
+                return HistoryEntry { string, time };
+            },
+            [](const HistoryEntry& left, const HistoryEntry& right) { return left.timestamp < right.timestamp; });
+    }
+
     auto file_or_error = Core::File::open(path, Core::IODevice::WriteOnly, 0600);
     if (file_or_error.is_error())
         return false;
-    auto& file = *file_or_error.value();
-    for (const auto& line : m_history) {
-        file.write(line);
-        file.write("\n");
-    }
+    auto file = file_or_error.release_value();
+    final_history.take_first();
+    for (const auto& entry : final_history)
+        file->write(String::formatted("{}::{}\n\n", entry.timestamp, entry.entry));
+
     return true;
 }
 
@@ -1002,7 +1068,7 @@ bool Editor::search(const StringView& phrase, bool allow_empty, bool from_beginn
         size_t search_offset = m_search_offset;
         for (size_t i = m_history_cursor; i > 0; --i) {
             auto& entry = m_history[i - 1];
-            auto contains = from_beginning ? entry.starts_with(phrase) : entry.contains(phrase);
+            auto contains = from_beginning ? entry.entry.starts_with(phrase) : entry.entry.contains(phrase);
             if (contains) {
                 last_matching_offset = i - 1;
                 if (search_offset == 0) {
@@ -1022,7 +1088,7 @@ bool Editor::search(const StringView& phrase, bool allow_empty, bool from_beginn
     if (found) {
         m_buffer.clear();
         m_cursor = 0;
-        insert(m_history[last_matching_offset]);
+        insert(m_history[last_matching_offset].entry);
         // Always needed, as we have cleared the buffer above.
         m_refresh_needed = true;
     }
diff --git a/Libraries/LibLine/Editor.h b/Libraries/LibLine/Editor.h
index 65655043e9..407b3fd9fa 100644
--- a/Libraries/LibLine/Editor.h
+++ b/Libraries/LibLine/Editor.h
@@ -154,7 +154,7 @@ public:
     void add_to_history(const String& line);
     bool load_history(const String& path);
     bool save_history(const String& path);
-    const Vector<String>& history() const { return m_history; }
+    const auto& history() const { return m_history; }
 
     void register_key_input_callback(const KeyBinding&);
     void register_key_input_callback(Vector<Key> keys, Function<bool(Editor&)> callback) { m_callback_machine.register_key_input_callback(move(keys), move(callback)); }
@@ -451,9 +451,13 @@ private:
     bool m_was_resized { false };
 
     // FIXME: This should be something more take_first()-friendly.
-    Vector<String> m_history;
+    struct HistoryEntry {
+        String entry;
+        time_t timestamp;
+    };
+    Vector<HistoryEntry> m_history;
     size_t m_history_cursor { 0 };
-    size_t m_history_capacity { 100 };
+    size_t m_history_capacity { 1024 };
 
     enum class InputState {
         Free,
diff --git a/Libraries/LibLine/InternalFunctions.cpp b/Libraries/LibLine/InternalFunctions.cpp
index 09bc97a9c2..6cb80671f8 100644
--- a/Libraries/LibLine/InternalFunctions.cpp
+++ b/Libraries/LibLine/InternalFunctions.cpp
@@ -425,7 +425,7 @@ void Editor::insert_last_words()
 {
     if (!m_history.is_empty()) {
         // FIXME: This isn't quite right: if the last arg was `"foo bar"` or `foo\ bar` (but not `foo\\ bar`), we should insert that whole arg as last token.
-        if (auto last_words = m_history.last().split_view(' '); !last_words.is_empty())
+        if (auto last_words = m_history.last().entry.split_view(' '); !last_words.is_empty())
             insert(last_words.last());
     }
 }
diff --git a/Shell/Builtin.cpp b/Shell/Builtin.cpp
index fb3791695e..d3a48b5089 100644
--- a/Shell/Builtin.cpp
+++ b/Shell/Builtin.cpp
@@ -463,7 +463,7 @@ int Shell::builtin_disown(int argc, const char** argv)
 int Shell::builtin_history(int, const char**)
 {
     for (size_t i = 0; i < m_editor->history().size(); ++i) {
-        printf("%6zu  %s\n", i, m_editor->history()[i].characters());
+        printf("%6zu  %s\n", i, m_editor->history()[i].entry.characters());
     }
     return 0;
 }