jumplist: browser-style (or 'tagstack') navigation #11530

Traditionally, when navigating to a specific location from the middle of
the jumplist results in shifting the current location to the bottom of
the list and adding the new location after it.  This behavior is not
desireable to all users--see, for example
https://vi.stackexchange.com/questions/18344/how-to-change-jumplist-behavior.

Here, another jumplist behavior is introduced.  When jumpoptions (a new
option set added here) includes stack, the jumplist behaves like the
tagstack or like history in a web browser.  That is, when navigating to
a location from the middle of the jumplist

    2 first
    1 second
    0 third <-- current location
    1 fourth
    2 fifth

to a new location the locations after the current location in the jump
list are discarded

    2 first
    1 second
    0 third
            <-- current location

The result is that when moving forward from that location, the new
location will be appended to the jumplist:

    3 first
    2 second
    1 third
    0 new

If the new location is the same

  new == second

as some previous (but not immediately prior) entry in the jumplist,

    2 first
    1 second
    0 third <-- current location
    1 fourth
    2 fifth

both occurrences preserved

    3 first
    2 second
    1 third
    0 second (new)

when moving forward from that location.

It would be desireable to go farther and, when the new location is the
same as the location that is currently next in the jumplist,

    new == fourth

make the result of navigating to the new location by jumping (e.g. 50gg)
be the same as moving forward in the jumplist

    2 first
    1 second
    0 third
    1 new <-- current location
    2 fifth

and simply increment the jumplist index.  That change is NOT part of
this patch because it would require passing the new cursor location to
the function (setpcmark) from all of its callees.  That in turn would
require those callees to know *before* calling what the new cursor
location is, which do they do not currently.

9 files changed, 205 insertions, 3 deletions

diff --git a/runtime/doc/motion.txt b/runtime/doc/motion.txt
index 07ff4cf030..3947e583b7 100644
--- a/runtime/doc/motion.txt
+++ b/runtime/doc/motion.txt
@@ -1083,6 +1083,60 @@ When you split a window, the jumplist will be copied to the new window.
 If you have included the ' item in the 'shada' option the jumplist will be
 stored in the ShaDa file and restored when starting Vim.
 
+							*jumplist-stack*
+When jumpoptions includes "stack", the jumplist behaves like the history in a
+web browser and like the tag stack.  When jumping to a new location from the
+middle of the jumplist, the locations after the current position will be
+discarded.
+
+This behavior corresponds to the following situation in a web browser.
+Navigate to first.com, second.com, third.com, fourth.com and then fifth.com.
+Then navigate backwards twice so that third.com is displayed.  At that point,
+the history is:
+- first.com
+- second.com
+- third.com <--
+- fourth.com
+- fifth.com
+
+Finally, navigate to a different webpage, new.com.  The history is
+- first.com
+- second.com
+- third.com
+- new.com <--
+
+When the jumpoptions includes "stack", this is the behavior of neovim as well.
+That is, given a jumplist like the following in which CTRL-O has been used to
+move back three times to location X
+
+ jump line  col file/text
+   2  1260    8 src/nvim/mark.c         <-- location X-2
+   1   685    0 src/nvim/option_defs.h  <-- location X-1
+>  0   462   36 src/nvim/option_defs.h  <-- location X
+   1   479   39 src/nvim/option_defs.h
+   2   213    2 src/nvim/mark.c
+   3   181    0 src/nvim/mark.c
+
+jumping to location Y results in the locations after the current locations being
+removed:
+
+ jump line  col file/text
+   3  1260    8 src/nvim/mark.c
+   2   685    0 src/nvim/option_defs.h
+   1   462   36 src/nvim/option_defs.h  <-- location X
+> 
+
+Then, when yet another location Z is jumped to, the new location Y appears
+directly after location X in the jumplist and location X remains in the same
+position relative to the locations (X-1, X-2, etc., ...) that had been before it
+prior to the original jump from X to Y:
+
+ jump line  col file/text
+   4  1260    8 src/nvim/mark.c         <-- location X-2
+   3   685    0 src/nvim/option_defs.h  <-- location X-1
+   2   462   36 src/nvim/option_defs.h  <-- location X
+   1   100    0 src/nvim/option_defs.h  <-- location Y
+> 
 
 CHANGE LIST JUMPS			*changelist* *change-list-jumps* *E664*
 
diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt
index 95265fa153..4b8740c5d2 100644
--- a/runtime/doc/options.txt
+++ b/runtime/doc/options.txt
@@ -3457,6 +3457,17 @@ A jump table for the options with a short description can be found at |Q_op|.
 	Unprintable and zero-width Unicode characters are displayed as <xxxx>.
 	There is no option to specify these characters.
 
+						*'jumpoptions'* *'jop'*
+'jumpoptions' 'jop'	string	(default "")
+			global
+	List of words that change the behavior of the |jumplist|.
+	  stack         Make the jumplist behave like the tagstack or like a
+	                web browser.  Relative location of entries in the
+			jumplist is preserved at the cost of discarding
+			subsequent entries when navigating backwards in the
+			jumplist and then jumping to a location.
+			|jumplist-stack|
+
 			*'joinspaces'* *'js'* *'nojoinspaces'* *'nojs'*
 'joinspaces' 'js'	boolean	(default on)
 			global
diff --git a/runtime/doc/quickref.txt b/runtime/doc/quickref.txt
index dfa7218bdf..224f14a18b 100644
--- a/runtime/doc/quickref.txt
+++ b/runtime/doc/quickref.txt
@@ -743,6 +743,7 @@ Short explanation of each option:		*option-list*
 'iskeyword'	  'isk'     characters included in keywords
 'isprint'	  'isp'     printable characters
 'joinspaces'	  'js'	    two spaces after a period with a join command
+'jumpoptions'	  'jop'     specifies how jumping is done
 'keymap'	  'kmp'     name of a keyboard mapping
 'keymodel'	  'km'	    enable starting/stopping selection with keys
 'keywordprg'	  'kp'	    program to use for the "K" command
diff --git a/runtime/doc/vim_diff.txt b/runtime/doc/vim_diff.txt
index 9c106077ab..64b5830575 100644
--- a/runtime/doc/vim_diff.txt
+++ b/runtime/doc/vim_diff.txt
@@ -336,6 +336,11 @@ Macro/|recording| behavior
 Motion:
   The |jumplist| avoids useless/phantom jumps.
 
+  When the new option |jumpoptions| includes 'stack', the jumplist behaves
+  like the tagstack or history in a web browser--jumping from the middle of
+  the jumplist discards the locations after the jumped-from position
+  (|jumplist-stack|).
+
 Normal commands:
   |Q| is the same as |gQ|
 
diff --git a/src/nvim/mark.c b/src/nvim/mark.c
index e5070f23ff..93bc497cf0 100644
--- a/src/nvim/mark.c
+++ b/src/nvim/mark.c
@@ -178,6 +178,16 @@ void setpcmark(void)
     curwin->w_pcmark.lnum = 1;
   }
 
+  if (jop_flags & JOP_STACK) {
+    // If we're somewhere in the middle of the jumplist discard everything
+    // after the current index.
+    if (curwin->w_jumplistidx < curwin->w_jumplistlen - 1) {
+      // Discard the rest of the jumplist by cutting the length down to
+      // contain nothing beyond the current index.
+      curwin->w_jumplistlen = curwin->w_jumplistidx + 1;
+    }
+  }
+
   /* If jumplist is full: remove oldest entry */
   if (++curwin->w_jumplistlen > JUMPLISTSIZE) {
     curwin->w_jumplistlen = JUMPLISTSIZE;
@@ -1204,7 +1214,20 @@ void cleanup_jumplist(win_T *wp, bool checktail)
         break;
       }
     }
-    if (i >= wp->w_jumplistlen) {  // no duplicate
+    bool mustfree;
+    if (i >= wp->w_jumplistlen) {  // not duplicate
+      mustfree = false;
+    } else if (i > from + 1) {  // non-adjacent duplicate
+      // When the jump options include "stack", duplicates are only removed from
+      // the jumplist when they are adjacent.
+      mustfree = !(jop_flags & JOP_STACK);
+    } else {  // adjacent duplicate
+      mustfree = true;
+    }
+
+    if (mustfree) {
+      xfree(wp->w_jumplist[from].fname);
+    } else {
       if (to != from) {
         // Not using wp->w_jumplist[to++] = wp->w_jumplist[from] because
         // this way valgrind complains about overlapping source and destination
@@ -1212,8 +1235,6 @@ void cleanup_jumplist(win_T *wp, bool checktail)
         wp->w_jumplist[to] = wp->w_jumplist[from];
       }
       to++;
-    } else {
-      xfree(wp->w_jumplist[from].fname);
     }
   }
   if (wp->w_jumplistidx == wp->w_jumplistlen) {
diff --git a/src/nvim/option.c b/src/nvim/option.c
index 68ab310329..e48ed201e8 100644
--- a/src/nvim/option.c
+++ b/src/nvim/option.c
@@ -2184,6 +2184,7 @@ static void didset_options(void)
   (void)opt_strings_flags(p_tc, p_tc_values, &tc_flags, false);
   (void)opt_strings_flags(p_ve, p_ve_values, &ve_flags, true);
   (void)opt_strings_flags(p_wop, p_wop_values, &wop_flags, true);
+  (void)opt_strings_flags(p_jop, p_jop_values, &jop_flags, true);
   (void)spell_check_msm();
   (void)spell_check_sps();
   (void)compile_cap_prog(curwin->w_s);
@@ -2632,6 +2633,10 @@ did_set_string_option(
     if (strcmp((char *)(*varp), HIGHLIGHT_INIT) != 0) {
       errmsg = e_unsupportedoption;
     }
+  } else if (varp == &p_jop) {  // 'jumpoptions'
+    if (opt_strings_flags(p_jop, p_jop_values, &jop_flags, true) != OK) {
+      errmsg = e_invarg;
+    }
   } else if (gvarp == &p_nf) {  // 'nrformats'
     if (check_opt_strings(*varp, p_nf_values, true) != OK) {
       errmsg = e_invarg;
diff --git a/src/nvim/option_defs.h b/src/nvim/option_defs.h
index c6e3f71016..4f9f32794b 100644
--- a/src/nvim/option_defs.h
+++ b/src/nvim/option_defs.h
@@ -473,6 +473,12 @@ EXTERN char_u   *p_isf;         // 'isfname'
 EXTERN char_u   *p_isi;         // 'isident'
 EXTERN char_u   *p_isp;         // 'isprint'
 EXTERN int p_js;                // 'joinspaces'
+EXTERN char_u *p_jop;           // 'jumpooptions'
+EXTERN unsigned jop_flags;
+#ifdef IN_OPTION_C
+static char *(p_jop_values[]) = { "stack", NULL };
+#endif
+#define JOP_STACK               0x01
 EXTERN char_u   *p_kp;          // 'keywordprg'
 EXTERN char_u   *p_km;          // 'keymodel'
 EXTERN char_u   *p_langmap;     // 'langmap'
diff --git a/src/nvim/options.lua b/src/nvim/options.lua
index 1e7105219f..93bfc1c0b1 100644
--- a/src/nvim/options.lua
+++ b/src/nvim/options.lua
@@ -1300,6 +1300,14 @@ return {
       defaults={if_true={vi=true}}
     },
     {
+      full_name='jumpoptions', abbreviation='jop',
+      type='string', list='onecomma', scope={'global'},
+      deny_duplicates=true,
+      varname='p_jop',
+      vim=true,
+      defaults={if_true={vim=''}}
+    },
+    {
       full_name='keymap', abbreviation='kmp',
       type='string', scope={'buffer'},
       normal_fname_chars=true,
diff --git a/test/functional/normal/jump_spec.lua b/test/functional/normal/jump_spec.lua
index 5bed541752..d53b5f7415 100644
--- a/test/functional/normal/jump_spec.lua
+++ b/test/functional/normal/jump_spec.lua
@@ -5,6 +5,7 @@ local command = helpers.command
 local eq = helpers.eq
 local funcs = helpers.funcs
 local feed = helpers.feed
+local redir_exec = helpers.redir_exec
 local write_file = helpers.write_file
 
 describe('jumplist', function()
@@ -46,3 +47,93 @@ describe('jumplist', function()
     eq(buf1, funcs.bufnr('%'))
   end)
 end)
+
+describe('jumpoptions=stack behaves like browser history', function()
+  before_each(function()
+    clear()
+    feed(':clearjumps<cr>')
+
+    -- Add lines so that we have locations to jump to.
+    for i = 1,101,1
+    do
+        feed('iLine ' .. i .. '<cr><esc>')
+    end
+
+    -- Jump around to add some locations to the jump list.
+    feed('0gg')
+    feed('10gg')
+    feed('20gg')
+    feed('30gg')
+    feed('40gg')
+    feed('50gg')
+
+    feed(':set jumpoptions=stack<cr>')
+  end)
+
+  after_each(function()
+      feed('set jumpoptions=')
+  end)
+
+  it('discards the tail when navigating from the middle', function()
+    feed('<C-O>')
+    feed('<C-O>')
+
+    eq(   '\n'
+       .. ' jump line  col file/text\n'
+       .. '   4   102    0 \n'
+       .. '   3     1    0 Line 1\n'
+       .. '   2    10    0 Line 10\n'
+       .. '   1    20    0 Line 20\n'
+       .. '>  0    30    0 Line 30\n'
+       .. '   1    40    0 Line 40\n'
+       .. '   2    50    0 Line 50',
+       redir_exec('jumps'))
+
+    feed('90gg')
+
+    eq(   '\n'
+       .. ' jump line  col file/text\n'
+       .. '   5   102    0 \n'
+       .. '   4     1    0 Line 1\n'
+       .. '   3    10    0 Line 10\n'
+       .. '   2    20    0 Line 20\n'
+       .. '   1    30    0 Line 30\n'
+       .. '>',
+       redir_exec('jumps'))
+  end)
+
+  it('does not add the same location twice adjacently', function()
+    feed('60gg')
+    feed('60gg')
+
+    eq(   '\n'
+       .. ' jump line  col file/text\n'
+       .. '   7   102    0 \n'
+       .. '   6     1    0 Line 1\n'
+       .. '   5    10    0 Line 10\n'
+       .. '   4    20    0 Line 20\n'
+       .. '   3    30    0 Line 30\n'
+       .. '   2    40    0 Line 40\n'
+       .. '   1    50    0 Line 50\n'
+       .. '>',
+       redir_exec('jumps'))
+  end)
+
+  it('does add the same location twice nonadjacently', function()
+    feed('10gg')
+    feed('20gg')
+
+    eq(   '\n'
+       .. ' jump line  col file/text\n'
+       .. '   8   102    0 \n'
+       .. '   7     1    0 Line 1\n'
+       .. '   6    10    0 Line 10\n'
+       .. '   5    20    0 Line 20\n'
+       .. '   4    30    0 Line 30\n'
+       .. '   3    40    0 Line 40\n'
+       .. '   2    50    0 Line 50\n'
+       .. '   1    10    0 Line 10\n'
+       .. '>',
+       redir_exec('jumps'))
+  end)
+end)