Implementation golang/term#15 demo of use/benefit fortio/terminal@77eee7b

Change https://go.dev/cl/603957 mentions this issue: x/term: expose History() AddToHistory() and NewHistory() so users of the library can save and restore the history.

I don't know if this is a good proposal or not, but if you add History() it should return iter.Seq[string].

I don't know if this is a good proposal or not, but if you add History() it should return iter.Seq[string].

Thanks for looking. If you look at the code you'll see it creates a copy while holding the lock. An iterator wouldn't be helpful as the copy (snapshot) is needed.

Hey Laurent!

I was about to push for review my patches for almost the same thing, hence would rather not waste everyone's time again and join you here.

I also did a terminal.PopHistory(), which I used when the user was just hitting Enter to clear the screen a bit. I think your terminal.ReplaceLatest() wouldn't cover this use case, of skipping the last command entirely from history, correct?

And what would you think is the best approach to achieve that? A modification to ReplaceLatest() (e.g. return a *string and nil means pop it), or the following that I already did in my patch?

// Pop the last element from the history.
func (s *stRingBuffer) Pop() (string, bool) {
	if s.size == 0 {
		return "", false
	}
	value := s.entries[s.head]
	s.head--
	if s.head < 0 {
		s.head += s.max
	}
	if s.size > 0 {
		s.size--
	}
	return value, true
}
func (t *Terminal) PopHistory() (string, bool) {
	t.lock.Lock()
	defer t.lock.Unlock()

	return t.history.Pop()
}

Or I guess also using AutoHistory(false) and then adding just the non-empty lines to history would work too...

Would you care to include this too, or you'd rather prefer that I'll push a PR after the current code is merged?

Cheers,
-Dragos

Thanks, yes I ended up mostly turning auto history off for real cases and adding depending on conditions, the on behavior is for backward compatibility with current behavior. I was using replace until I hit writing a "history" (and !nn repeat) which shifts the history by one making auto not useable, maybe for minimalism I should remove replace?

Edit: I wouldn't mind replacing Replace by Pop btw if that works better

I was buying though your explanation for what ReplaceLatest() could be useful 😉. Yet one could achieve a similar effect also without, since you're also implementing AddToHistory().

So the question probably is: would AutoHistory(true) really be used beyond backwards-compatibility? If yes, then ReplaceLatest() and Pop() would be useful and worth adding (yet also of limited use, because next someone would want access to other entries, not just the last).

IMHO the usage pattern of these APIs is:

• first users let AutoHistory(true) as default or are oblivious to its existence;
• more advanced users which want more control will set AutoHistory(false);
  • then AddToHistory() would be enough for most scenarios;
  • for the rest you have already built a way to get-all, (modify), clear, set-back-all; so I'd say it's not worth adding more complexity for eventual efficiency savings.

tl;dr - I'm thinking neither ReplaceLatest() and Pop() might be significant additions. There are many ways to get to the same end state. I'd go with the simplest.

And remember that once an API is added, there will always be some using it forever, along with all it's undocumented or unintended side-effects 😛.

So I use replace in the example but it's true I just set auto to false instead in my real code. I can drop it from the proposal.

I just want to say though that I wanted to avoid people clearing the whole history and re-adding to change last entry as even with a relatively small 99 entry slice it'd be wasteful

lastly there is one other reason for replace which is to let users use up arrow and find the last bad entry and correct it

ping, anyone?

It's unclear why we bothered with a limited, circular buffer. What if we made the state an unbounded slice that is directly exposed in the struct, like History []string, and then implementations can maintain it however they like, including occasionally cutting it back. Then all those methods aren't needed.

I don't understand the sync.Mutex in the struct, though, so I'm not sure how it would work exactly.

Another option would be to let the user pass in a History interface with some set of methods and implement it however it wants. I still am not sure what the locking rules need to be.

It's unclear why we bothered with a limited, circular buffer. What if we made the state an unbounded slice that is directly exposed in the struct, like History []string, and then implementations can maintain it however they like, including occasionally cutting it back. Then all those methods aren't needed.

Having a limited history is somewhat a reasonable thing for a cli, so as to not grow unbounded (or be manageable) - also changing that is a breaking change for callers (vs it being 100 currently automatically)

I don't understand the sync.Mutex in the struct, though, so I'm not sure how it would work exactly.

You mean Terminal.lock? (like in https://github.com/golang/term/pull/15/files#diff-76dcb3ff0bf98acc001558927365f8a3b7f0d2253580a49dc5973dfa398372c7R825)

It's not a new thing and it makes the terminal thread safe, per the comment

	// lock protects the terminal and the state in this object from
	// concurrent processing of a key press and a Write() call.
	lock sync.Mutex

ie terminal handles \r wrapping and refreshing the prompt concurrently with output

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

This seems like a lot of API to recreate a limited set of operations that could instead be expressed explicitly directly on a slice.

My understanding (correct me if I'm wrong) is that we couldn't expose the history slice directly because of concurrency concerns, but it seems like we could have a simple get/put API like:

// History returns a copy of the command history.
// (Which order are the strings in?)
func (*Terminal) History() []string

// SetHistory sets the terminal command history.
// (Do we copy it or take ownership? Copying is safer, but often a waste.)
func (*Terminal) SetHistory([]string)

For the history capacity, we could either add a method specifically for setting that, or make it an argument to SetHistory, or do something more implicit like using the capacity of the slice passed to SetHistory (that feels too implicit to me).

A slice api would be less efficient than the current circular buffer. You could argue maybe it doesn’t matter for human scale timing/history - but adding 3 apis (get/set/size) vs the 4 proposed doesn’t seem significantly better tradeoff?

I agree that copying back and forth to a slice is a bit unfortunate. However, I don't think comparing simply the number of methods is the right way to measure the trade-off. The 4 proposed methods are really not very general, whereas a get/set slice API lets the caller implement whatever modifications they want.

Here's an exploration of what this might look like if we expose it as a real deque API. The is certainly more API surface, but it's a standard data structure with a standard API that provides a lot of generality without the cost of copying to/from a slice:

func (t *Terminal) History() *History

// History is a bounded deque of strings.
//
// The most recent entry is numbered 0, and called the "head".
// The least recent entry is called the tail.
type History struct { ... }

// Push pushes a new head element.
// If Len() == Cap(), this also deletes the tail.
func (h *History) Push(s string)
// Pop pops the head element, or panics if the deque is empty.
func (h *History) Pop() string
// Len returns the number of elements.
func (h *History) Len() int
// Cap returns the maximum number of elements.
func (h *History) Cap() int
// SetCap changes the maximum number of elements that can be stored in the deque.
// If the new cap is < Len(), it deletes elements from the tail.
func (h *History) SetCap(cap int)
// All iterates over all elements in the deque, starting with the head element.
func (h *History) All() iter.Seq[string]
// Get returns the i'th entry, where 0 refers to the head element.
func (h *History) Get(i int) string
// Set sets the i'th entry. It panics if i >= Len().
func (h *History) Set(i int, s string)

Ideally that would look more like

import "container/deque"
func (t *Terminal) History() *deque.Bounded[string]

Sure, I don't disagree. Though the fact that it's bounded is a little odd for a general-purpose deque.

I do think if we add a deque type here, it should use method names similar to those used by container/list. For my own generic deque, I have

func (d *Deque[T]) All() iter.Seq2[int, T]
func (d *Deque[T]) At(n int) (t T, ok bool)
func (d *Deque[T]) Back() (t T, ok bool)
func (d *Deque[T]) Cap() int
func (d *Deque[T]) Clip()
func (d *Deque[T]) Front() (v T, ok bool)
func (d *Deque[T]) Grow(n int)
func (d *Deque[T]) Len() int
func (d *Deque[T]) PushBack(v T)
func (d *Deque[T]) PushBackSeq(seq iter.Seq[T])
func (d *Deque[T]) PushBackSlice(s []T)
func (d *Deque[T]) PushFront(v T)
func (d *Deque[T]) RemoveBack() (t T, ok bool)
func (d *Deque[T]) RemoveFront() (t T, ok bool)
func (d *Deque[T]) Reverse() iter.Seq2[int, T]
func (d *Deque[T]) Slice() []T
func (d *Deque[T]) String() string
func (d *Deque[T]) Swap(i, j int)

which mirrors container/list

func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v any, mark *Element) *Element
func (l *List) InsertBefore(v any, mark *Element) *Element
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) PushBack(v any) *Element
func (l *List) PushBackList(other *List)
func (l *List) PushFront(v any) *Element
func (l *List) PushFrontList(other *List)
func (l *List) Remove(e *Element) any

I think x/term can just have:

type Terminal struct{
    // If set, terminal uses this to store history for key up/down events.
    // If left unset, a default implementation is used (current ring buffer).
    History History
}

type History interface{
    // adds a new line into the history
    Add(string)

    // retrieves a line from history
    // 0 should be the most recent entry
    // ok = false when out of range
    At(idx int) (string, ok)
}

This is sufficient to support the needs of x/term (adding, key up/down).
Any additional manipulation can be done by extra methods on the type implementing the interface.

I think x/term can just have:

type Terminal struct{
// If set, terminal uses this to store history for key up/down events.
// If left unset, a default implementation is used (current ring buffer).
History History
}

type History interface{
// adds a new line into the history
Add(string)

// retrieves a line from history
// 0 should be the most recent entry
// ok = false when out of range
At(idx int) (string, ok)

}

This is sufficient to support the needs of x/term (adding, key up/down). Any additional manipulation can be done by extra methods on the type implementing the interface.

I like this but with the method name PushBack(string) instead of Add(string). A quick search on pkg.go.dev for deque finds lots of existing deque implementations that can be used as is with the method name PushBack.

That would probably be wrong though: history generally wants to start from the most recent entry, while At(0) on a dequeue should be the oldest entry
unless you want to mandate support for negative indices, or an extra Len() every time.

Are we maybe over-engineering this a bit? As a user of this API, I for one, primarily want to save and recover the history.

Secondarily, since the terminal is an interface with a human, we just want some basic way to fix the history a bit. If this secondary target is too much, we'll probably just be happy with the primary one and we'll manage on our side.

So I'd suggest progress over perfection, considering also how old this issue is.

If we make an interface, we'd still need a backward compatible implementation for it

As a reminder the diff of the proposed API is really straightforward, simple and small and has been doing the job needed for many months: https://github.com/golang/term/pull/15/files

I use it (because I need it) in grol's repl, fortio/terminal etc

That would probably be wrong though: history generally wants to start from the most recent entry, while At(0) on a dequeue should be the oldest entry unless you want to mandate support for negative indices, or an extra Len() every time.

Huh? People would be supplying their own deques/ring buffers, and those would have their own Back methods which would return the newest entry. Why would it be different than any other ring buffer? You could have a PushFront method instead if you wanted At(0) to be the newest thing, but that seems weird to me.

The implementation would just be the existing one: https://cs.opensource.google/go/x/term/+/refs/tags/v0.30.0:terminal.go;l=907-945

The api proposed at the top of the issue seems to overfit to whatever you wanted to do.

Not lining up with the semantics of a dequeue is exactly why the names shouldn't come from dequeue.
An interface should be defined to for how it's used, for history, that is to add, and to retrieve, starting from the most recent entry.

Yes so to for instance just change that hard coded 100, one would need to wholesale replace the otherwise fine implementation

ditto to intercept Add when one doesn't need to add

I assume Add() would be the current (unexposed) NthPreviousEntry()

This being said, any way to not have to maintain a fork would be progress

But what about the locking/thread safety?

But what about the locking/thread safety?

Good point. I was thinking about how Terminal could lock additions to History, but you'd also need a way to lock reading History, which is why a simple slice is probably the best API here, since the lock wouldn't be a problem.

If the lock is over the entire history then instead of a field you could have

func (*Terminal) SetHistory(History)
func (*Terminal) WithHistory(func(History))

where WithHistory without a call to SetHistory would expose the default behavior as a History