#1763 History recall off by 1 on full history stack

[Matthew Halverson]

Using version 5.0.3 on windows (gp503-win64-mingw.zip, using wgnuplot.exe), it seems that the ability to recall a history command by number does not quite work when the history stack is full.

To demonstrate this, run the following commands

set history size 4
plot [1:2][1:4] 1
plot [1:2][1:4] 2
plot [1:2][1:4] 3
history

This will set the history stack to 4 and then preceed to fill it up. The result of that final command is to print the current history stack which looks like

    1  plot [1:2][1:4] 1
    2  plot [1:2][1:4] 2
    3  plot [1:2][1:4] 3
    4  history

Now, issuing the command history !2 should repeat the plot command that draws a line at y=2. Instead we get the line at y=3. It seems that when the history stack is full, the new command is first added to the stack pushing all the previous entries back by one, and then the command is recalled by number. This means that the command for y=2 is now at item 1 and the command for y=3 is now at item 2, so the wrong command is recalled.

This does not occur when the history stack is not full. For example, run the following commands (first setting a smaller size and then a larger one in order to flush the stack to a known state)

set history size 4
plot [1:2][1:4] 1
plot [1:2][1:4] 2
plot [1:2][1:4] 3
set history size 8
history

This will give us a history stack holding up to 8 items and with the following populated

    1  plot [1:2][1:4] 1
    2  plot [1:2][1:4] 2
    3  plot [1:2][1:4] 3
    4  set history size 8
    5  history

In this case, history !2 draws the line at y=2 as expected. Thus the off by one behavior only occurs when the history stack is full.

Additionally, while playing with the history size in order to come up with a good example to demonstrate this, I have had gnuplot (using the wgnuplot.exe executable) crash a couple of times on me with a few variations of set history size <number> and set history <number>. Unfortunately, I have been unable to come up with a test case that reliably causes this crash, so I'm not sure if the cause can be easily determined.

Again, this only occurs when the history stack is full. If there is room open in it, nothing like this occurs. Looking at the source code, it looks like different systems may implement the history mechanism differently, so it is also possible that this does not occur on all systems.

[Matthew Halverson]

A related issue occurs because the item number 1 gets pushed off the history stack.

Run

set history size 4
a=1;plot [1:2][1:4] 1
a=2;plot [1:2][1:4] 2
a=3;plot [1:2][1:4] 3
history

This populates the history stack and prints

    1  a=1;plot [1:2][1:4] 1
    2  a=2;plot [1:2][1:4] 2
    3  a=3;plot [1:2][1:4] 3
    4  history

Now, the command history !"a=1" results in the message not in history, because item 1 was pushed off the history stack by this command referencing it before it could be ran.

Running history !1 works without an error, but actually grabs item 2 as previously described.

[Matthew Halverson]

I've been trying to think of how this issue could be fixed and although I can think of three possible approaches, all of them introduce new issues. It may be that effectively referencing an item in a full history stack by number (or by string in the case of the first item) is simply untenable.

Approach 1

Changing the order of the processing so the command is ran before putting it on the history stack (it seems that the opposisite is currently done) could work. Then a command like history !2 will correctly grab item 2 on the stack instead of item 3 like it does now.

The problem is that when I type history to see the history stack, it would be printed and then this command would be added. This means that when I want to access the item which said it was item 2, it would now be item 1. Thus pretty much the same problem occurs, but the mistake is moved to the printed results instead of the command referencing command. It may be that this can be fixed by the history detecting if it is full and subtracting one from every number if it is. Then the command that said it was number 2 could be accessed as number 2. This means that item 1 (which would now say it is item 0) would have to be skipped (it will end up pushed off the stack before I can access it anyways) and the stack would always show one empty slot (in our example of 4 items we would list an item 1 [really 2], item 2 [really 3], and item 3 [really 4]). This would also allow me to access item 1 (as printed) because it does not get pushed off the stack before it is accessed. This means that history !"some string" would work with the first item as well.

Approach 2

It may be possible to have the referencing process determine if the stack is full and subtract one from it in that case. Thus when I run history !2 on a full stack it actually grabs item 1 (which would have been item 2 before this command was added to the stack) but if the stack is not full then it would grab item 2. For this to work, we must be able to determine if the stack was full before the new command was added (which would shift all the numbers) or if the new command was the one that filled it up (which would not shift the numbers this time, but the next command would).

Here we have the problem with item 1 being unaccessible because it gets pushed off the stack. Thus the command history !1 would be meaningless.

Approach 3

It may be possible to increase the size of the stack by one if it is full before running the new command and then adjust back. Thus if we have a stack size of 4 and it is full, running a new command would increase the size to 5, run the new command, and then adjust it back to 4.

This is probably too difficult to implement, and I think has the same problems as approach 1 when printing the current history stack.

[Bastian Märkisch]

Another possibility: do not add history commands to the history.

[Matthew Halverson]

Actually that is probably best (why did I come up with so complicated solutions, when this is obvious in hindsight?).

One possible problem with that, however. When I type history !2 it doesn't add history !2 to the history. Instead it adds what that resolves to (and actually violates the suppress duplicates option too), so there may be some more checking needed with that (I don't know if the add method sees the history command or what the history command resolves to). But, if we avoid adding whatever that resolves to into the history, that would completely solve the problem.

[Bastian Märkisch]

That might not be as trivial as I first thought. The new input is added to the history immediately before parsing. While that could be changed with a little effort, it is also not clear to me what to do if there are more commands than just a single history on the command line. Any thoughts?

[Bastian Märkisch]

The attached patch tests for the first command on the line being history. If that's the case, the line is not appended to the history.

[Ethan Merritt]

Hi Bastian.
I'd like to see this patch applied. But first he handling of leading blank space needs a fix. I think the tests for NUL and blank need to test line[start+i] rather than line[i] but I'm not sure that is the complete fix.

[Bastian Märkisch]

Fixed and applied to CVS for 5.1. Should it also go to 5.0?

[Ethan Merritt]

Wait a minute. Going back to your original description...
"set history size 4" actually does something visible on your gnuplot?
For me it has no immediate effect whatsover. It only changes how many lines will be saved to a file when you exit the program. That matches what the documentation says.

gnuplot> set history size 4
gnuplot> plot [1:2][1:4] 1
gnuplot> plot [1:2][1:4] 2
gnuplot> plot [1:2][1:4] 3
gnuplot> history
    1   set term qt 5 close
    2   plot sin(x)
[... snip ...]
  501   set history size 4
  502   plot [1:2][1:4] 1
  503   plot [1:2][1:4] 2
  504   plot [1:2][1:4] 3
  505   history

So I don't understand what problem you are seeing. Are you just saying that the numbers saved to a file do not necessarily match the numbers you saw in a previous session? IMHO that's not a bug. There is no guarantee that item #23 bears any relationship to what it was in a session from a month ago.

[Matthew Halverson]

On the windows version (with both wgnuplot.exe and gnuplot.exe) it limits how many items are in the history stack entirely (in the current session), so yes it does something visible.

For example,

set history size 3
print "a"
print "b"
print "c"
print "d"
history

results in

1 print "b"
2 print "c"
3 print "d"

keeping only the last 3 items. Continuing to run commands and then running history will never show more than 3 items with that setting. Thus it effects the number of items available in the current session, and not just the number saved when you exit.

I don't expect the numbers to match between sessions, but they should match within the current session. I thought that this behavior was correct, but now that I look at the description again, and based on what you are saying, this is the real bug.

From what you are saying, and looking at the documentation again, there is a bug, but not necessarily the one I originally described (although that arises as a consequence). This is effecting the current season, when its effect should only arise upon exiting. That is causing the bug I described as this limit is being hard enforced in the current session. If it was only effecting what was saved upon exiting (as it is supposed to), it would fix this behavior.

---

Note that the setting only has an effect upon issuing a new command besides history, however. For example, if I do

set history size 4
history

with a history containing many more than 4 items, I will see many more than 4 items listed. But if I then do

print "a"
history

I will now only see 4 items listed. Again, the size is cut down within the current session, but it only takes effect if a command other than history is ran. I don't know if this will be helpful in tracking down where the problem is or not.

[Ethan Merritt]

Weird. I was not aware that "history" acted so differently on different platforms.
This is not a part of the program I have ever looked at.

I do see that some of the code checks for
#if defined(HAVE_LIBREADLINE) && defined(GNUPLOT_HISTORY)

Are you using libreadline? What is the first line of compile options reported by "show version long"?

[Matthew Halverson]

I am using the precompiled windows binaries (I have only had marginal luck compiling from source under windows).

On wgnuplot.exe, show version long produces

        G N U P L O T
        Version 5.0 patchlevel 3    last modified 2016-02-21 

        Copyright (C) 1986-1993, 1998, 2004, 2007-2016
        Thomas Williams, Colin Kelley and many others

        gnuplot home:     http://www.gnuplot.info
        faq, bugs, etc:   type "help FAQ"
        immediate help:   type "help"  (plot window: hit 'h')
Compile options:
+READLINE  -LIBREADLINE  +HISTORY  
-BACKWARDS_COMPATIBILITY  +BINARY_DATA  
+LIBCERF  +GD_PNG  +GD_JPEG  +GD_TTF  +GD_GIF  +ANIMATION  
-USE_CWDRC  +USE_MOUSE  +HIDDEN3D_QUADTREE  
+DATASTRINGS  +HISTOGRAMS  +OBJECTS  +STRINGVARS  +MACROS  +THIN_SPLINES  +IMAGE  +USER_LINETYPES +STATS +EXTERNAL_FUNCTIONS 
MAX_PARALLEL_AXES=7

GNUPLOT_PS_DIR     = "share/PostScript"
HELPFILE           = "C:\gnuplot\5.0\bin\wgnuplot.chm"
MENUNAME           = "C:\gnuplot\5.0\bin\wgnuplot.mnu"
libcaca version    : 0.99.beta19pre

and on gnuplot.exe, it produces the same except for the MENUNAME line near the bottom is not present.

If I am reading those correctly, it doesn't use libreadline on windows.

[Ethan Merritt]

Ugh. I've just built a copy configure --with-readline=builtin and indeed history is rather broken. The history numbering changes on every command, which makes it pretty much useless. As I say, I have not looked at this part of the program before so I am not familiar with the code, but it looks like some significant revision is needed to make it match the readline-based version and behave as documented.

If nothing else, it looks to me that the entire block of code starting at line 98 in history.c is counter-productive and should be removed. It renumbers the history on every command, which is crazy.

So...

diff -urp gnuplot50/src/history.c test50/src/history.c
--- gnuplot50/src/history.c     2013-12-16 16:49:52.000000000 -0800
+++ test50/src/history.c        2016-03-30 11:26:45.000000000 -0700
@@ -95,7 +95,11 @@ add_history(char *line)
        entry = entry->prev;
     }                          /* end of not-storing duplicated entries */

-#ifdef GNUPLOT_HISTORY
+#if (0)
+    /* This code block breaks "history !<number>" because it renumbers the  */
+    /* entries before retrieving the requested number.  Also it potentially */
+    /* truncates the list on every command contrary to the documentattion.  */
+
     /* limit size of history list to "gnuplot_history_size" */
     if (gnuplot_history_size != -1) {
        while ((hist_count >= gnuplot_history_size) && (first_entry != NULL)) {

Work-around: Always use "set history -1"

[Bastian Märkisch]

Seems like I am resposible for that piece of code. Actually that was one of my first contributions like 11 years back... The rationale of it was to limit the in-memory size of the history. But the commit comment didn't even say so.

I think that this can be removed more completely. Patch is attached.

[Ethan Merritt]

Please go ahead and apply that cleanup to both 5.0 and 5.1

I think I have encountered unexpected loss of a previous command after the "don't save history commands" change but I have not been able to reproduce it on demand. It seems that sometimes the very last command in a session is not saved. But as I say I can't reliably reproduce this.

[Ethan Merritt]

A regression caused this bug to reappear, but now it's fixed again.