x/term: support pluggable history

[ldemailly]

Proposal Details

--- Accepted proposal:

// A History provides a (possibly bounded) queue of input lines read by [ReadLine].
type History interface {
	// Add adds a new, most recent entry to the history.
	// It is allowed to drop any entry, including
	// the entry being added (e.g.,, if it's a whitespace-only entry),
	// the least-recent entry (e.g., to keep the history bounded),
	// or any other entry.
	Add(entry string)

	// Len returns the number of entries in the history.
	Len() int

	// At returns an entry from the history.
	// Index 0 is the most-recently added entry and
	// index Len()-1 is the least-recently added entry.
	// If index is < 0 or >= Len(), it panics.
	At(index int) string
}

type Terminal struct {
        ...

        // History records and retrieves lines of input read by [ReadLine].
        //
        // It is not safe to call ReadLine concurrently with any methods on History.
        // 
        // [NewTerminal] sets this to an implementation that records the last 100 lines of input.
        History History
}

copied from #68780 (comment)

--- Was "Interface" Proposal:

https://github.com/golang/term/pull/20/files

// The History interface provides a way to replace the default automatic
// 100 slots ringbuffer implementation.
type History interface {
	// Add will be called by Terminal to add a new line into the history.
	// An implementation may decide to not add every lines by ignoring calls
	// to this function (from Terminal.ReadLine) and to only add validated
	// entries out of band.
	Add(entry string)

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

// In terminal:

	// History allows to replace the default implementation of the history
	// which contains previously entered commands so that they can be
	// accessed with the up and down keys.
	// It's not safe to call ReadLine and methods on History concurrently.
	History History

---

And even earlier "direct" proposal for reference:

x/term is very nice, it includes a 100 slot history ring buffer, unfortunately entirely private

https://github.com/golang/term/blob/master/terminal.go#L89

it would be nice to let people

// History returns a slice of strings containing the history of entered commands so far.
func (t *Terminal) History() []string {

and

// AddToHistory populates history.
func (t *Terminal) AddToHistory(commands ...string) {

and resize

// NewHistory resets the history to one of a given capacity.
func (t *Terminal) NewHistory(capacity int) {

and allow replacement of last command in history (for instance to replace invalid by validated or canonical variant)

// ReplaceLatest replaces the most recent history entry with the given string.
// Enables to add invalid commands to the history for editing purpose and
// replace them with the corrected version. Returns the replaced entry.
func (t *Terminal) ReplaceLatest(entry string) string {

and control whether lines are automatically added to history (defaults remains true)

// AutoHistory sets whether lines are automatically added to the history
// before being returned by ReadLine() or not. Defaults to true.
func (t *Terminal) AutoHistory(onOff bool) {

if acceptable I'd be happy to make a PR edit: made a PR

[ldemailly]

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

[gopherbot]

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.

[earthboundkid]

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

[ldemailly]

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.

[vingarzan]

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

[ldemailly]

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

[vingarzan]

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 😛.

[ldemailly]

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

[ldemailly]

ping, anyone?

[rsc]

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.

[ldemailly]

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

[rsc]

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

[aclements]

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).

[ldemailly]

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?

[aclements]

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)

[jimmyfrasche]

Ideally that would look more like

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

[aclements]

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

[earthboundkid]

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

[seankhliao]

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.

[ldemailly]

in short I would vote for the minimal/surgical version, 1 interface, 2 methods in the current description; 2nd choice being adding Len but not using it, and that most recent only if that's the only way to get this approved

[earthboundkid]

My preference would be that At returns "" for index out of range.

[aclements]

I personally am against changing the working code, including the signature - I was ok renaming NthPreviousEntry to At as that was risk free and mechanical

The concerns of a one-time internal (and fairly minor) refactoring should not outweigh the concerns of designing an exported API. Implementation is fleeting. API is forever.

[aclements]

My preference would be that At returns "" for index out of range.

For what reason?

My argument for panicking is that, while History isn't quite a general purpose sequence container API, it's certainly inspired by this. And in a general sequence container, At(int) T should panic for an out-of-bounds index for the same reason all built-in sequences (slice, array, string) do.

[ldemailly]

The concerns of a one-time internal (and fairly minor) refactoring should not outweigh the concerns of designing an exported API. Implementation is fleeting. API is forever.

It's a bit like "in theory, there is no difference between theory and practice, but in practice, there is"
So in theory I agree, in practice for this specific case, I disagree that adding Len() and a panic'ing At with new signature is a good practical choice, including because of my earlier point

adding (even theoretically im)possible panic() for code that has the terminal in raw mode

eg what made the need for https://go-review.googlesource.com/c/term/+/408754

I will also repeat I believe it's not possible to use (implement) that API without looking at the current code - which is probably a smell of sort - so I wouldn't be very adamant on designing the most beautiful abstract API for this.

Yet... anything that lets the CL move forward... not sure what the decision process is here...

[earthboundkid]

At(int) T should panic for an out-of-bounds index for the same reason all built-in sequences (slice, array, string) do.

OTOH, map doesn't panic because it's more convenient to just return a sensible default.

Here's a survey of some results for deque on pkg.go.dev:

• github.com/gammazero/deque At(int) T panics out of range
• github.com/liyue201/gostl/ds/deque At(int) T panics out of range
• github.com/oleiade/lane/v2 No At-like method
• github.com/ef-ds/deque/v2 No At-like method
• github.com/edwingeng/deque/v2 Peek(int) T panics out of range
• github.com/tebeka/deque (not generic) Get(int) (any, error)
• github.com/earthboundkid/deque/v2 At(int) (T, bool) (mine)

It looks like a single value form that panics is the more common way to do it.

[ardnew]

@ldemailly yeesh, a PR from 3 years ago — the time frame aligns exactly with work I was doing on a readline/ANSI seq package for TinyGo.

During development/test, I faintly recall swapping in packages from x/term to compare against my own implementations. This is probably how I ran into it. That, and I probably had a lot of time on my hands during COVID.

[ldemailly]

@earthboundkid thanks for having taken the time to look at dequeues impls/apis - this being said whichever is more common isn't really (imo) a deciding factor (in particular because someone replacing History wouldn't just plug the same/std dequeue as what's already there). It does show value, bool or value, err isn't unheard off though (vs value + panic).

@ardnew thanks for the reply - do you have an opinion on whether NthPreviousEntry() (called At() here) should panic?

[ardnew]

@ldemailly My knee-jerk expectation is that it should panic — that bounds checking should occur prior to access (consistent with built-in containers, as @aclements mentioned).

Assuming the alternative is to add a returned errror/bool:

• Omitting error/bool from the signature doesn't prevent an implementation from adding error handling,
• and so requiring it only adds constraint; it adds baggage to the call semantics of a rather discrete operation.

In my humble opinion, error handling should be a concern of the consumer here, not the interface.

[ldemailly]

Agreed in general, yet your CL/PR removed (some cases of(*)) panic and replaced them with returning false

*: eg calling NthPreviousEntry(-200) was panicking before your PR and not anymore after - yet ok just doing -1 was returning garbage before yet not panic unless near the end of the buffer

The consumer being... the terminal... in the implementation I did add unlock and defer relock in case of panic just to be safe but... having to replace

	entry, ok := t.historyAt(t.historyIndex + 1)
	if !ok {
		return "", false
	}

by

                 idx := t.historyIndex + 1
                 if idx >= t.historyLen() {
                     return "", false
                 }
                 entry = t.historyAt(idx)

is odd (and calls into question whether unlocking mid way and doing it twice is safe and efficient (probably not... probably will need a single replacement for making 2 calls to the api while unlocked)

EDIT: I can put the 2 calls in historyAt() with unchanged signature so it's fine. not my favorite but I am wore down on accepting this :)

[ardnew]

Agreed in general, yet your CL/PR removed (some cases of(*)) panic and replaced them with returning false

Indeed, I am 100% recommending the opposite of what I did in the PR 😄

[aclements]

Sounds like the consensus is to panic.

[ldemailly]

by some definition of consensus sure… I would say more like beaten into submission for the sake of forward progress

[aclements]

@ldemailly , we're trying to work together here. The proposal process exists to ensure changes and additions to Go are durable and consistent through the review and consensus of the community and software design experts. It's not perfect, but it does typically achieve that goal. Please leave your snark at the door.

[ldemailly]

There is no snark just that I hear the input and feedback but I don't think my points are heard - yet I would like this to get approved so I can work with whichever proposal is deemed acceptable. (also I happen to be an expert too, including on software engineering and consequences of introducing things like panic or code maintenance and am as far I know one of the people who try to use and update and maintain this package more rather than roll my own so I do find the whole thing a bit negative)

[vingarzan]

Being in the same position of just wanting to help and provide patches like @ldemailly, I don't think that was snarky at all. As a user willing to contribute patches, I would appreciate a bit more empathy for old change requests.

I don't see either the point of a panic, especially as Len() and At() are different methods and there is no lock in-between calling them (or?). So then I must always wrap then such calls in recover, if there is a possibility that At() might panic due to concurrent changes in the history?

Of course, would appreciate your thoughts if I'm wrong here...

[aclements]

So then I must always wrap then such calls in recover, if there is a possibility that At() might panic due to concurrent changes in the history?

My understanding is that a History can only be changed by x/term during a call to ReadLine, and we propose specifying that methods on History must not be called concurrently with ReadLine. So I don't think there's any danger of concurrency here. Thus you should no more have to worry about recovering panics from At than you would when accessing a slice. Concurrent changes would also cause problems with other use patterns that expect a consistent view of the history, like calling At multiple times with different indexes.

[aclements]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— aclements for the proposal review group

The proposal is to add the following API to the golang.org/x/term package:

// A History provides a (possibly bounded) queue of input lines read by [ReadLine].
type History interface {
	// Add adds a new, most recent entry to the history.
	// It is allowed to drop any entry, including
	// the entry being added (e.g.,, if it's a whitespace-only entry),
	// the least-recent entry (e.g., to keep the history bounded),
	// or any other entry.
	Add(entry string)

	// Len returns the number of entries in the history.
	Len() int

	// At returns an entry from the history.
	// Index 0 is the most-recently added entry and
	// index Len()-1 is the least-recently added entry.
	// If index is < 0 or >= Len(), it panics.
	At(index int) string
}

type Terminal struct {
        ...

        // History records and retrieves lines of input read by [ReadLine].
        //
        // It is not safe to call ReadLine concurrently with any methods on History.
        // 
        // [NewTerminal] sets this to an implementation that records the last 100 lines of input.
        History History
}

[ldemailly]

Thanks. I will update the CL and test panic and Out use cases in History to make sure the upcoming code handles it all.

[vingarzan]

So then I must always wrap then such calls in recover, if there is a possibility that At() might panic due to concurrent changes in the history?

My understanding is that a History can only be changed by x/term during a call to ReadLine, and we propose specifying that methods on History must not be called concurrently with ReadLine. So I don't think there's any danger of concurrency here. Thus you should no more have to worry about recovering panics from At than you would when accessing a slice. Concurrent changes would also cause problems with other use patterns that expect a consistent view of the history, like calling At multiple times with different indexes.

OK, I get it now that there are documented preconditions on how to use the API safely. But I for one would've preferred to have it more robust, if some users might make mistakes in using it. You are the maintainers, I am the user and yeah, I might be "holding it wrong" 😅, but I would prefer not to have to build a "bumper" around it. Of course, a good API is part of that, so your help is greatly appreciated!

Anyway, Thank You, for both the explanation and getting it through! I for one just wanted convergence, to be able to drop my (similar) fork 🎉

And also Thank You to @ldemailly - your proposal covered use-cases that I haven't initially thought about, but now find very useful!

[ldemailly]

golang/term#20 (https://go-review.googlesource.com/c/term/+/659835) has been updated (as well as fortio/terminal#85 which uses/tests it)

[gopherbot]

Change https://go.dev/cl/659835 mentions this issue: term: support pluggable history