shada: Initial support for merging history

Currently only merges history when reading ShaDa file. No tests yet.

4 files changed, 564 insertions, 41 deletions

diff --git a/src/nvim/ex_getln.c b/src/nvim/ex_getln.c
index 1347feb857..38f84f2e7f 100644
--- a/src/nvim/ex_getln.c
+++ b/src/nvim/ex_getln.c
@@ -4274,8 +4274,7 @@ in_history (
     int type,
     char_u *str,
     int move_to_front,              /* Move the entry to the front if it exists */
-    int sep,
-    int writing                    /* ignore entries read from viminfo */
+    int sep
 )
 {
   int i;
@@ -4293,7 +4292,6 @@ in_history (
      * well. */
     p = history[type][i].hisstr;
     if (STRCMP(str, p) == 0
-        && !(writing && history[type][i].viminfo)
         && (type != HIST_SEARCH || sep == p[STRLEN(p) + 1])) {
       if (!move_to_front)
         return TRUE;
@@ -4313,7 +4311,6 @@ in_history (
       last_i = i;
     }
     history[type][i].hisnum = ++hisnum[type];
-    history[type][i].viminfo = FALSE;
     history[type][i].hisstr = str;
     history[type][i].timestamp = os_time();
     history[type][i].additional_elements = NULL;
@@ -4386,7 +4383,7 @@ add_to_history (
     }
     last_maptick = -1;
   }
-  if (!in_history(histype, new_entry, TRUE, sep, FALSE)) {
+  if (!in_history(histype, new_entry, TRUE, sep)) {
     if (++hisidx[histype] == hislen)
       hisidx[histype] = 0;
     hisptr = &history[histype][hisidx[histype]];
@@ -4400,7 +4397,6 @@ add_to_history (
     hisptr->hisstr[len + 1] = sep;
 
     hisptr->hisnum = ++hisnum[histype];
-    hisptr->viminfo = FALSE;
     if (histype == HIST_SEARCH && in_map)
       last_maptick = maptick;
   }
@@ -4768,6 +4764,32 @@ void ex_history(exarg_T *eap)
   }
 }
 
+/// Translate a history type number to the associated character
+int hist_type2char(int type)
+  FUNC_ATTR_CONST
+{
+  switch (type) {
+    case HIST_CMD: {
+      return ':';
+    }
+    case HIST_SEARCH: {
+      return '/';
+    }
+    case HIST_EXPR: {
+      return '=';
+    }
+    case HIST_INPUT: {
+      return '@';
+    }
+    case HIST_DEBUG: {
+      return '>';
+    }
+    default: {
+      assert(false);
+    }
+  }
+}
+
 /*
  * Write a character at the current cursor+offset position.
  * It is directly written into the command buffer block.
@@ -5078,7 +5100,7 @@ char_u *script_get(exarg_T *eap, char_u *cmd)
 ///
 /// @return Pointer used in next iteration or NULL to indicate that iteration 
 ///         was finished.
-const void *hist_iter(const void *const iter, const size_t history_type,
+const void *hist_iter(const void *const iter, const uint8_t history_type,
                       const bool zero, histentry_T *const hist)
   FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ARG(4)
 {
@@ -5121,3 +5143,22 @@ const void *hist_iter(const void *const iter, const size_t history_type,
   hiter++;
   return (const void *) ((hiter > hend) ? hstart : hiter);
 }
+
+/// Get array of history items
+///
+/// @param[in]   history_type  Type of the history to get array for.
+/// @param[out]  new_hisidx    Location where last index in the new array should 
+///                            be saved.
+/// @param[out]  new_hisnum    Location where last history number in the new 
+///                            history should be saved.
+///
+/// @return Pointer to the array or NULL.
+histentry_T *hist_get_array(const uint8_t history_type, int **const new_hisidx,
+                            int **const new_hisnum)
+  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL
+{
+  init_history();
+  *new_hisidx = &(hisidx[history_type]);
+  *new_hisnum = &(hisnum[history_type]);
+  return history[history_type];
+}
diff --git a/src/nvim/ex_getln.h b/src/nvim/ex_getln.h
index 9c7a688e7e..738e515f21 100644
--- a/src/nvim/ex_getln.h
+++ b/src/nvim/ex_getln.h
@@ -38,7 +38,6 @@ typedef char_u *(*CompleteListItemGetter)(expand_T *, int);
 /// History entry definition
 typedef struct hist_entry {
   int hisnum;           ///< Entry identifier number.
-  bool viminfo;         ///< If true, indicates that entry comes from viminfo.
   char_u *hisstr;       ///< Actual entry, separator char after the NUL.
   Timestamp timestamp;  ///< Time when entry was added.
   Array *additional_elements;  ///< Additional entries from ShaDa file.
diff --git a/src/nvim/lib/ringbuf.h b/src/nvim/lib/ringbuf.h
new file mode 100644
index 0000000000..f86d656deb
--- /dev/null
+++ b/src/nvim/lib/ringbuf.h
@@ -0,0 +1,281 @@
+/// Macros-based ring buffer implementation.
+///
+/// Supported functions:
+///
+/// - new: allocates new ring buffer.
+/// - dealloc: free ring buffer itself.
+/// - free: free ring buffer and all its elements.
+/// - push: adds element to the end of the buffer.
+/// - length: get buffer length.
+/// - size: size of the ring buffer.
+/// - idx: get element at given index.
+/// - idx_p: get pointer to the element at given index.
+/// - insert: insert element at given position.
+/// - remove: remove element from given position.
+#ifndef NVIM_LIB_RINGBUF_H
+#define NVIM_LIB_RINGBUF_H
+
+#include <string.h>
+#include <assert.h>
+#include <stdint.h>
+
+#include "nvim/memory.h"
+#include "nvim/func_attr.h"
+
+#define _RINGBUF_LENGTH(rb) \
+    ((rb)->first == NULL ? 0 \
+     : ((rb)->next == (rb)->first) ? (size_t) ((rb)->buf_end - (rb)->buf) + 1 \
+     : ((rb)->next > (rb)->first) ? (size_t) ((rb)->next - (rb)->first) \
+     : (size_t) ((rb)->next - (rb)->buf + (rb)->buf_end - (rb)->first + 1))
+
+#define _RINGBUF_NEXT(rb, var) \
+    ((var) == (rb)->buf_end ? (rb)->buf : (var) + 1)
+#define _RINGBUF_PREV(rb, var) \
+    ((var) == (rb)->buf ? (rb)->buf_end : (var) - 1)
+
+/// Iterate over all ringbuf values
+///
+/// @param  rb       Ring buffer to iterate over.
+/// @param  RBType   Type of the ring buffer element.
+/// @param  varname  Variable name.
+#define RINGBUF_FORALL(rb, RBType, varname) \
+    size_t varname##_length_fa_ = _RINGBUF_LENGTH(rb); \
+    for (RBType *varname = ((rb)->first == NULL ? (rb)->next : (rb)->first); \
+         varname##_length_fa_; \
+         (varname = _RINGBUF_NEXT(rb, varname)), \
+         varname##_length_fa_--)
+
+/// Iterate over all ringbuf values, from end to the beginning
+///
+/// Unlike previous RINGBUF_FORALL uses already defined variable, in place of
+/// defining variable in the cycle body.
+///
+/// @param  rb       Ring buffer to iterate over.
+/// @param  RBType   Type of the ring buffer element.
+/// @param  varname  Variable name.
+#define RINGBUF_ITER_BACK(rb, RBType, varname) \
+    size_t varname##_length_ib_ = _RINGBUF_LENGTH(rb); \
+    for (varname = ((rb)->next == (rb)->buf ? (rb)->buf_end : (rb)->next - 1); \
+         varname##_length_ib_; \
+         (varname = _RINGBUF_PREV(rb, varname)), \
+         varname##_length_ib_--)
+
+/// Define a ring buffer structure
+///
+/// @param TypeName    Ring buffer type name. Actual type name will be 
+///                    `{TypeName}RingBuffer`.
+/// @param RBType      Type of the single ring buffer element.
+#define RINGBUF_TYPEDEF(TypeName, RBType)                                      \
+typedef struct {                                                               \
+  RBType *buf;                                                                 \
+  RBType *next;                                                                \
+  RBType *first;                                                               \
+  RBType *buf_end;                                                             \
+} TypeName##RingBuffer;
+
+/// Initialize a new ring buffer
+///
+/// @param TypeName    Ring buffer type name. Actual type name will be 
+///                    `{TypeName}RingBuffer`.
+/// @param funcprefix  Prefix for all ring buffer functions. Function name will 
+///                    look like `{funcprefix}_rb_{function_name}`.
+/// @param RBType      Type of the single ring buffer element.
+/// @param rbfree      Function used to free ring buffer element. May be 
+///                    a macros like `#define RBFREE(item)` (to skip freeing).
+///
+///                    Intended function signature: `void *rbfree(RBType *)`;
+#define RINGBUF_INIT(TypeName, funcprefix, RBType, rbfree)                     \
+                                                                               \
+                                                                               \
+static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size)      \
+  REAL_FATTR_WARN_UNUSED_RESULT;                                               \
+static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size)      \
+{                                                                              \
+  assert(size != 0);                                                           \
+  RBType *buf = xmalloc(size * sizeof(RBType));                                \
+  return (TypeName##RingBuffer) {                                              \
+    .buf = buf,                                                                \
+    .next = buf,                                                               \
+    .first = NULL,                                                             \
+    .buf_end = buf + size - 1,                                                 \
+  };                                                                           \
+}                                                                              \
+                                                                               \
+static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb)        \
+  REAL_FATTR_UNUSED;                                                           \
+static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb)        \
+{                                                                              \
+  if (rb == NULL) {                                                            \
+    return;                                                                    \
+  }                                                                            \
+  RINGBUF_FORALL(rb, RBType, rbitem) {                                         \
+    rbfree(rbitem);                                                            \
+  }                                                                            \
+  xfree(rb->buf);                                                              \
+}                                                                              \
+                                                                               \
+static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb)     \
+  REAL_FATTR_UNUSED;                                                           \
+static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb)     \
+{                                                                              \
+  xfree(rb->buf);                                                              \
+}                                                                              \
+                                                                               \
+static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb,        \
+                                        RBType item)                           \
+  REAL_FATTR_NONNULL_ARG(1);                                                   \
+static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb,        \
+                                        RBType item)                           \
+{                                                                              \
+  if (rb->next == rb->first) {                                                 \
+    rbfree(rb->first);                                                         \
+    rb->first = _RINGBUF_NEXT(rb, rb->first);                                  \
+  } else if (rb->first == NULL) {                                              \
+    rb->first = rb->next;                                                      \
+  }                                                                            \
+  *rb->next = item;                                                            \
+  rb->next = _RINGBUF_NEXT(rb, rb->next);                                      \
+}                                                                              \
+                                                                               \
+static inline ptrdiff_t funcprefix##_rb_find_idx(                              \
+    const TypeName##RingBuffer *const rb, const RBType *const item_p)          \
+  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED;                    \
+static inline ptrdiff_t funcprefix##_rb_find_idx(                              \
+    const TypeName##RingBuffer *const rb, const RBType *const item_p)          \
+{                                                                              \
+  assert(rb->buf <= item_p);                                                   \
+  assert(rb->buf_end >= item_p);                                               \
+  if (rb->first == NULL) {                                                     \
+    return -1;                                                                 \
+  } else if (item_p >= rb->first) {                                            \
+    return item_p - rb->first;                                                 \
+  } else {                                                                     \
+    return item_p - rb->buf + rb->buf_end - rb->first + 1;                     \
+  }                                                                            \
+}                                                                              \
+                                                                               \
+static inline size_t funcprefix##_rb_size(                                     \
+    const TypeName##RingBuffer *const rb)                                      \
+  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE;                                      \
+static inline size_t funcprefix##_rb_size(                                     \
+    const TypeName##RingBuffer *const rb)                                      \
+{                                                                              \
+  return (size_t) (rb->buf_end - rb->buf) + 1;                                 \
+}                                                                              \
+                                                                               \
+static inline size_t funcprefix##_rb_length(                                   \
+    const TypeName##RingBuffer *const rb)                                      \
+  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE;                                      \
+static inline size_t funcprefix##_rb_length(                                   \
+    const TypeName##RingBuffer *const rb)                                      \
+{                                                                              \
+  return _RINGBUF_LENGTH(rb);                                                  \
+}                                                                              \
+                                                                               \
+static inline RBType *funcprefix##_rb_idx_p(                                   \
+    const TypeName##RingBuffer *const rb, const size_t idx)                    \
+  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE;                                      \
+static inline RBType *funcprefix##_rb_idx_p(                                   \
+    const TypeName##RingBuffer *const rb, const size_t idx)                    \
+{                                                                              \
+  assert(idx <= funcprefix##_rb_size(rb));                                     \
+  assert(idx <= funcprefix##_rb_length(rb));                                   \
+  if (rb->first + idx > rb->buf_end) {                                         \
+    return rb->buf + ((rb->first + idx) - (rb->buf_end + 1));                  \
+  } else {                                                                     \
+    return rb->first + idx;                                                    \
+  }                                                                            \
+}                                                                              \
+                                                                               \
+static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \
+                                         const size_t idx)                     \
+  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED;                    \
+static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \
+                                         const size_t idx)                     \
+{                                                                              \
+  return *funcprefix##_rb_idx_p(rb, idx);                                      \
+}                                                                              \
+                                                                               \
+static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb,      \
+                                          const size_t idx,                    \
+                                          RBType item)                         \
+  REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED;                                 \
+static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb,      \
+                                          const size_t idx,                    \
+                                          RBType item)                         \
+{                                                                              \
+  assert(idx <= funcprefix##_rb_size(rb));                                     \
+  assert(idx <= funcprefix##_rb_length(rb));                                   \
+  const size_t length = funcprefix##_rb_length(rb);                            \
+  if (idx == length) {                                                         \
+    funcprefix##_rb_push(rb, item);                                            \
+    return;                                                                    \
+  }                                                                            \
+  RBType *const insertpos = funcprefix##_rb_idx_p(rb, idx);                    \
+  if (insertpos == rb->next) {                                                 \
+    funcprefix##_rb_push(rb, item);                                            \
+    return;                                                                    \
+  }                                                                            \
+  if (length == funcprefix##_rb_size(rb)) {                                    \
+    rbfree(rb->first);                                                         \
+  }                                                                            \
+  if (insertpos < rb->next) {                                                  \
+    memmove(insertpos + 1, insertpos,                                          \
+            (size_t) ((uintptr_t) rb->next - (uintptr_t) insertpos));          \
+  } else {                                                                     \
+    assert(insertpos > rb->first);                                             \
+    assert(rb->next <= rb->first);                                             \
+    memmove(rb->buf + 1, rb->buf,                                              \
+            (size_t) ((uintptr_t) rb->next - (uintptr_t) rb->buf));            \
+    *rb->buf = *rb->buf_end;                                                   \
+    memmove(insertpos + 1, insertpos,                                          \
+            (size_t) ((uintptr_t) (rb->buf_end + 1) - (uintptr_t) insertpos)); \
+  }                                                                            \
+  *insertpos = item;                                                           \
+  if (length == funcprefix##_rb_size(rb)) {                                    \
+    rb->first = _RINGBUF_NEXT(rb, rb->first);                                  \
+  }                                                                            \
+  rb->next = _RINGBUF_NEXT(rb, rb->next);                                      \
+}                                                                              \
+                                                                               \
+static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb,      \
+                                          const size_t idx)                    \
+  REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED;                                 \
+static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb,      \
+                                          const size_t idx)                    \
+{                                                                              \
+  assert(idx < funcprefix##_rb_size(rb));                                      \
+  assert(idx < funcprefix##_rb_length(rb));                                    \
+  RBType *const rmpos = funcprefix##_rb_idx_p(rb, idx);                        \
+  rbfree(rmpos);                                                               \
+  if (rmpos == rb->next - 1) {                                                 \
+    rb->next--;                                                                \
+    if (rb->first == rb->next) {                                               \
+      rb->first = NULL;                                                        \
+      rb->next = rb->buf;                                                      \
+    }                                                                          \
+  } else if (rmpos == rb->first) {                                             \
+    rb->first = _RINGBUF_NEXT(rb, rb->first);                                  \
+    if (rb->first == rb->next) {                                               \
+      rb->first = NULL;                                                        \
+      rb->next = rb->buf;                                                      \
+    }                                                                          \
+  } else if (rb->first < rb->next || rb->next == rb->buf) {                    \
+    assert(rmpos > rb->first);                                                 \
+    assert(rmpos <= _RINGBUF_PREV(rb, rb->next));                              \
+    memmove(rb->first + 1, rb->first,                                          \
+            (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first));             \
+    rb->first = _RINGBUF_NEXT(rb, rb->first);                                  \
+  } else if (rmpos < rb->next) {                                               \
+    memmove(rmpos, rmpos + 1,                                                  \
+            (size_t) ((uintptr_t) rb->next - (uintptr_t) rmpos));              \
+    rb->next = _RINGBUF_PREV(rb, rb->next);                                    \
+  } else {                                                                     \
+    assert(rb->first < rb->buf_end);                                           \
+    memmove(rb->first + 1, rb->first,                                          \
+            (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first));             \
+    rb->first = _RINGBUF_NEXT(rb, rb->first);                                  \
+  }                                                                            \
+}
+
+#endif  // NVIM_LIB_RINGBUF_H
diff --git a/src/nvim/shada.c b/src/nvim/shada.c
index 6a729597db..de2e89736f 100644
--- a/src/nvim/shada.c
+++ b/src/nvim/shada.c
@@ -42,6 +42,7 @@
 #include "nvim/eval_defs.h"
 #include "nvim/version.h"
 #include "nvim/path.h"
+#include "nvim/lib/ringbuf.h"
 
 #define buflist_nr2name(...) ((char *) buflist_nr2name(__VA_ARGS__))
 #define copy_option_part(src, dest, ...) \
@@ -140,6 +141,8 @@ typedef struct {
     struct history_item {
       uint8_t histtype;
       char *string;
+      char sep;
+      bool canfree;
       Array *additional_elements;
     } history_item;
     struct reg {
@@ -168,10 +171,22 @@ typedef struct {
   } data;
 } ShadaEntry;
 
+RINGBUF_TYPEDEF(HM, ShadaEntry)
+
+typedef struct {
+  HMRingBuffer hmrb;
+  bool do_merge;
+  const void *iter;
+  ShadaEntry last_hist_entry;
+  uint8_t history_type;
+} HistoryMergerState;
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "shada.c.generated.h"
 #endif
 
+RINGBUF_INIT(HM, hm, ShadaEntry, shada_free_shada_entry)
+
 /// Msgpack callback for writing to FILE*
 static int msgpack_fbuffer_write(void *data, const char *buf, size_t len)
 {
@@ -227,6 +242,93 @@ int shada_read_file(const char *const file, const int flags)
   return OK;
 }
 
+/// Wrapper for hist_iter() function which produces ShadaEntry values
+///
+/// @warning Zeroes original items in process.
+static const void *shada_hist_iter(const void *const iter,
+                                   const uint8_t history_type,
+                                   const bool zero,
+                                   ShadaEntry *const hist)
+  FUNC_ATTR_NONNULL_ARG(4) FUNC_ATTR_WARN_UNUSED_RESULT
+{
+  histentry_T hist_he;
+  const void *const ret = hist_iter(iter, history_type, zero, &hist_he);
+  if (hist_he.hisstr == NULL) {
+    *hist = (ShadaEntry) { .type = kSDItemMissing };
+  } else {
+    *hist = (ShadaEntry) {
+      .type = kSDItemHistoryEntry,
+      .timestamp = hist_he.timestamp,
+      .data = {
+        .history_item = {
+          .histtype = history_type,
+          .string = (char *) hist_he.hisstr,
+          .sep = (char) (history_type == HIST_SEARCH
+                        ? (char) hist_he.hisstr[STRLEN(hist_he.hisstr) + 1]
+                        : 0),
+          .additional_elements = hist_he.additional_elements,
+          .canfree = zero,
+        }
+      }
+    };
+  }
+  return ret;
+}
+
+/// Insert history entry
+///
+/// Inserts history entry at the end of the ring buffer (may insert earlier 
+/// according to the timestamp). If entry was already in the ring buffer 
+/// existing entry will be removed unless it has greater timestamp.
+///
+/// Before the new entry entries from the current NeoVim history will be 
+/// inserted unless `do_iter` argument is false.
+///
+/// @param[in,out]  hms_p    Ring buffer and associated structures.
+/// @param[in]      entry    Inserted entry.
+/// @param[in]      do_iter  Determines whether NeoVim own history should be 
+///                          used.
+static void insert_history_entry(HistoryMergerState *const hms_p,
+                                 const ShadaEntry entry,
+                                 const bool no_iter)
+{
+  HMRingBuffer *const rb = &(hms_p->hmrb);
+  RINGBUF_FORALL(rb, ShadaEntry, cur_entry) {
+    if (STRCMP(cur_entry->data.history_item.string,
+               entry.data.history_item.string) == 0) {
+      if (entry.timestamp > cur_entry->timestamp) {
+        hm_rb_remove(rb, (size_t) hm_rb_find_idx(rb, cur_entry));
+      } else {
+        return;
+      }
+    }
+  }
+  if (!no_iter) {
+    if (hms_p->iter == NULL) {
+      if (hms_p->last_hist_entry.type != kSDItemMissing
+          && hms_p->last_hist_entry.timestamp < entry.timestamp) {
+        insert_history_entry(hms_p, hms_p->last_hist_entry, false);
+        hms_p->last_hist_entry.type = kSDItemMissing;
+      }
+    } else {
+      while (hms_p->iter != NULL
+            && hms_p->last_hist_entry.type != kSDItemMissing
+            && hms_p->last_hist_entry.timestamp < entry.timestamp) {
+        insert_history_entry(hms_p, hms_p->last_hist_entry, false);
+        hms_p->iter = shada_hist_iter(hms_p->iter, hms_p->history_type, true,
+                                      &(hms_p->last_hist_entry));
+      }
+    }
+  }
+  ShadaEntry *insert_after;
+  RINGBUF_ITER_BACK(rb, ShadaEntry, insert_after) {
+    if (insert_after->timestamp <= entry.timestamp) {
+      break;
+    }
+  }
+  hm_rb_insert(rb, (size_t) (hm_rb_find_idx(rb, insert_after) + 1), entry);
+}
+
 /// Read data from ShaDa file
 ///
 /// @param[in]  fp     File to read from.
@@ -234,6 +336,15 @@ int shada_read_file(const char *const file, const int flags)
 static void shada_read(FILE *const fp, const int flags)
   FUNC_ATTR_NONNULL_ALL
 {
+  HistoryMergerState hms[HIST_COUNT];
+  if (flags & kShaDaWantInfo && p_hi) {
+    for (uint8_t i = 0; i < HIST_COUNT; i++) {
+      hms[i].hmrb = hm_rb_new((size_t) p_hi);
+      hms[i].do_merge = true;
+      hms[i].iter = shada_hist_iter(NULL, i, true, &(hms[i].last_hist_entry));
+      hms[i].history_type = i;
+    }
+  }
   ShadaEntry cur_entry;
   buf_T *local_mark_prev_buf = NULL;
   char *local_mark_prev_fname = NULL;
@@ -290,12 +401,17 @@ static void shada_read(FILE *const fp, const int flags)
         break;
       }
       case kSDItemHistoryEntry: {
-        if (!(flags & kShaDaWantInfo)) {
+        if (!(flags & kShaDaWantInfo && p_hi)) {
           shada_free_shada_entry(&cur_entry);
           break;
         }
-        // FIXME
-        shada_free_shada_entry(&cur_entry);
+        if (cur_entry.data.history_item.histtype >= HIST_COUNT) {
+          shada_free_shada_entry(&cur_entry);
+          break;
+        }
+        insert_history_entry(hms + cur_entry.data.history_item.histtype,
+                             cur_entry, true);
+        // Do not free shada entry: its allocated memory was saved above.
         break;
       }
       case kSDItemRegister: {
@@ -353,6 +469,7 @@ static void shada_read(FILE *const fp, const int flags)
             .additional_data = cur_entry.data.filemark.additional_data,
           },
         }, !(flags & kShaDaForceit));
+        // Do not free shada entry: its allocated memory was saved above.
         break;
       }
       case kSDItemJump: {
@@ -407,6 +524,43 @@ static void shada_read(FILE *const fp, const int flags)
       }
     }
   }
+  // Warning: shada_hist_iter returns ShadaEntry elements which use strings from 
+  //          original history list. This means that once such entry is removed 
+  //          from the history NeoVim array will no longer be valid. To reduce 
+  //          amount of memory allocations ShaDa file reader allocates enough 
+  //          memory for the history string itself and separator character which 
+  //          may be assigned right away.
+  if (flags & kShaDaWantInfo && p_hi) {
+    for (uint8_t i = 0; i < HIST_COUNT; i++) {
+      if (hms[i].last_hist_entry.type != kSDItemMissing) {
+        insert_history_entry(&(hms[i]), hms[i].last_hist_entry, false);
+      }
+      while (hms[i].iter != NULL
+            && hms[i].last_hist_entry.type != kSDItemMissing) {
+        hms[i].iter = shada_hist_iter(hms[i].iter, hms[i].history_type, true,
+                                      &(hms[i].last_hist_entry));
+        insert_history_entry(&(hms[i]), hms[i].last_hist_entry, false);
+      }
+      clr_history(i);
+      int *new_hisidx;
+      int *new_hisnum;
+      histentry_T *hist = hist_get_array(i, &new_hisidx, &new_hisnum);
+      if (hist != NULL) {
+        histentry_T *const hist_init = hist;
+        RINGBUF_FORALL(&(hms[i].hmrb), ShadaEntry, cur_entry) {
+          hist->timestamp = cur_entry->timestamp;
+          hist->hisnum = (int) (hist - hist_init) + 1;
+          hist->hisstr = (char_u *) cur_entry->data.history_item.string;
+          hist->additional_elements =
+              cur_entry->data.history_item.additional_elements;
+          hist++;
+        }
+        *new_hisnum = (int) hm_rb_length(&(hms[i].hmrb));
+        *new_hisidx = *new_hisnum - 1;
+      }
+      hm_rb_dealloc(&(hms[i].hmrb));
+    }
+  }
   xfree(local_mark_prev_fname);
   FOR_ALL_BUFFERS(buf) {
     fmarks_check_names(buf);
@@ -491,7 +645,9 @@ static void shada_pack_entry(msgpack_packer *const packer,
       break;
     }
     case kSDItemHistoryEntry: {
-      const size_t arr_size = 2 + (
+      const bool is_hist_search =
+          entry.data.history_item.histtype == HIST_SEARCH;
+      const size_t arr_size = 2 + (size_t) is_hist_search + (
           entry.data.history_item.additional_elements == NULL
           ? 0
           : entry.data.history_item.additional_elements->size);
@@ -499,7 +655,10 @@ static void shada_pack_entry(msgpack_packer *const packer,
       msgpack_pack_uint8(spacker, entry.data.history_item.histtype);
       msgpack_rpc_from_string(cstr_as_string(entry.data.history_item.string),
                               spacker);
-      for (size_t i = 0; i < arr_size - 2; i++) {
+      if (is_hist_search) {
+        msgpack_pack_uint8(spacker, (uint8_t) entry.data.history_item.sep);
+      }
+      for (size_t i = 0; i < arr_size - 2 - (size_t) is_hist_search; i++) {
         msgpack_rpc_from_object(
             entry.data.history_item.additional_elements->items[i], spacker);
       }
@@ -798,26 +957,35 @@ static void shada_write(FILE *const newfp, FILE *const oldfp)
   // FIXME No merging currently
 
   // 4. History
-  const void *hist_iters[HIST_COUNT] = {NULL, NULL, NULL, NULL, NULL};
+  HistoryMergerState hms[HIST_COUNT];
   for (uint8_t i = 0; i < HIST_COUNT; i++) {
-    do {
-      histentry_T cur_hist;
-      hist_iters[i] = hist_iter(hist_iters[i], i, false, &cur_hist);
-      if (cur_hist.hisstr == NULL) {
-        break;
-      }
-      shada_pack_entry(packer, (ShadaEntry) {
-        .type = kSDItemHistoryEntry,
-        .timestamp = cur_hist.timestamp,
-        .data = {
-          .history_item = {
-            .histtype = i,
-            .string = (char *) cur_hist.hisstr,
-            .additional_elements = cur_hist.additional_elements,
+    long num_saved = get_viminfo_parameter(hist_type2char(i));
+    if (num_saved == -1) {
+      num_saved = p_hi;
+    }
+    if (num_saved > 0) {
+      HistoryMergerState *hms_p = &(hms[i]);
+      hms_p->hmrb = hm_rb_new((size_t) num_saved);
+      hms_p->do_merge = false;
+      hms_p->iter = shada_hist_iter(NULL, i, false, &(hms[i].last_hist_entry));
+      hms_p->history_type = i;
+      if (hms_p->last_hist_entry.type != kSDItemMissing) {
+        hm_rb_push(&(hms_p->hmrb), hms_p->last_hist_entry);
+        while (hms_p->iter != NULL) {
+          hms_p->iter = shada_hist_iter(hms_p->iter, hms_p->history_type, false,
+                                        &(hms_p->last_hist_entry));
+          if (hms_p->last_hist_entry.type != kSDItemMissing) {
+            hm_rb_push(&(hms_p->hmrb), hms_p->last_hist_entry);
+          } else {
+            break;
           }
         }
-      }, max_kbyte);
-    } while (hist_iters[i] != NULL);
+      }
+      RINGBUF_FORALL(&(hms_p->hmrb), ShadaEntry, cur_entry) {
+        shada_pack_entry(packer, *cur_entry, max_kbyte);
+      }
+      hm_rb_dealloc(&hms_p->hmrb);
+    }
   }
 
   // 5. Search patterns
@@ -1042,11 +1210,13 @@ static void shada_free_shada_entry(ShadaEntry *const entry)
       break;
     }
     case kSDItemHistoryEntry: {
-      if (entry->data.history_item.additional_elements != NULL) {
-        api_free_array(*entry->data.history_item.additional_elements);
-        xfree(entry->data.history_item.additional_elements);
+      if (entry->data.history_item.canfree) {
+        if (entry->data.history_item.additional_elements != NULL) {
+          api_free_array(*entry->data.history_item.additional_elements);
+          xfree(entry->data.history_item.additional_elements);
+        }
+        xfree(entry->data.history_item.string);
       }
-      xfree(entry->data.history_item.string);
       break;
     }
     case kSDItemVariable: {
@@ -1656,7 +1826,8 @@ shada_read_next_item_start:
       entry->data.history_item = (struct history_item) {
         .histtype = 0,
         .string = NULL,
-        .additional_elements = NULL
+        .sep = 0,
+        .additional_elements = NULL,
       };
       if (unpacked.data.via.array.size < 2) {
         emsgn("Error while reading ShaDa file: "
@@ -1683,16 +1854,47 @@ shada_read_next_item_start:
       }
       entry->data.history_item.histtype =
           (uint8_t) unpacked.data.via.array.ptr[0].via.u64;
-      entry->data.history_item.string =
-          xmemdupz(unpacked.data.via.array.ptr[1].via.bin.ptr,
-                   unpacked.data.via.array.ptr[1].via.bin.size);
-      if (unpacked.data.via.array.size > 2) {
+      const bool is_hist_search =
+          entry->data.history_item.histtype == HIST_SEARCH;
+      if (is_hist_search) {
+        if (unpacked.data.via.array.size < 3) {
+          emsgn("Error while reading ShaDa file: "
+                "search history entry at position %" PRId64 " "
+                "does not have separator character",
+                (int64_t) initial_fpos);
+          goto shada_read_next_item_error;
+        }
+        if (unpacked.data.via.array.ptr[2].type
+            != MSGPACK_OBJECT_POSITIVE_INTEGER) {
+          emsgn("Error while reading ShaDa file: "
+                "search history entry at position %" PRId64 " "
+                "has wrong history separator type",
+                (int64_t) initial_fpos);
+          goto shada_read_next_item_error;
+        }
+        entry->data.history_item.sep =
+            (char) unpacked.data.via.array.ptr[2].via.u64;
+      }
+      const size_t strsize = (
+          unpacked.data.via.array.ptr[1].via.bin.size
+          + 1 // Zero byte
+          + 1 // Separator character
+      );
+      entry->data.history_item.string = xmalloc(strsize);
+      memcpy(entry->data.history_item.string,
+             unpacked.data.via.array.ptr[1].via.bin.ptr,
+             unpacked.data.via.array.ptr[1].via.bin.size);
+      entry->data.history_item.string[strsize - 2] = 0;
+      entry->data.history_item.string[strsize - 1] =
+          entry->data.history_item.sep;
+      if (unpacked.data.via.array.size > (size_t) (2 + is_hist_search)) {
         msgpack_object obj = {
           .type = MSGPACK_OBJECT_ARRAY,
           .via = {
             .array = {
-              .size = unpacked.data.via.array.size - 2,
-              .ptr = unpacked.data.via.array.ptr + 2,
+              .size = (unpacked.data.via.array.size
+                       - (uint32_t) (2 + is_hist_search)),
+              .ptr = unpacked.data.via.array.ptr + (2 + is_hist_search),
             }
           }
         };