proposal: x/term: expose history

[ldemailly]

Proposal Details

--- Newer "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

---

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.

[earthboundkid]

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.

[seankhliao]

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.

[vingarzan]

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.

[ldemailly]

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

[earthboundkid]

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.

[seankhliao]

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.

[ldemailly]

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?

[earthboundkid]

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.

[jimmyfrasche]

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

[ldemailly]

Any conclusion?

[earthboundkid]

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

You would have to trust users not to accidentally use the History they pass in after a call to SetHistory. Seems prone to accidental misuse due to not reading the docs.

I favor this API:

// History returns a copy of the command history.
// History is arranged with oldest commands first and most recent commands last.
func (*Terminal) History() []string

// SetHistory sets the terminal command history, replacing any existing history.
// History should arranged with oldest commands first and most recent commands last.
// If the history is longer than the current HistoryCap, it will be truncated to more recent items.
func (*Terminal) SetHistory([]string)

func (*Terminal) HistoryCap() int
func (*Terminal) SetHistoryCap(int)

[aclements]

What are the actual use cases for a history API? So far I've seen the following (sorry if I missed any already mentioned):

• Resize history
• Replace most recent command in history
• Remove the most recent entry (and/or disable adding it in the first place)
• Save and restore history

[ldemailly]

Yes

• Allow save and restore of history
• Decide if the last user entry is good to keep in history permanently or not (allow typos to be edited with up arrow yet also not keep typos or empty lines etc... past the most recent entry)
• Configure the max number of entries

[aclements]

Thanks.

We're leaning toward the interface-based approach (thanks @rsc here and @seankhliao here). That's a very minimal API, while allowing consumers that need more flexibility with their history to do anything they need to.

I think that just leaves the question of concurrency. The lock @ldemailly mentioned protects ReadLine vs Write. The history doesn't need to synchronize with Write, just ReadLine, so I don't think it needs locking. We just need to specify that it's not safe to call ReadLine and methods on History concurrently.

[ldemailly]

I think it could work, hopefully without issue with current historyIndex (starting at -1 marker value) and historyPending internal state - should I update the changelist/make a new one or is someone else doing that ?

[ldemailly]

The diff is pretty trivial, let me see if I can reimplement the rest of the functionality and if it works

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

(it is mildly annoying to have to reimplement that circular buffer but...)

[ldemailly]

I have to say too it seems quite unlikely someone can provide a correct implementation without looking at the code

[ldemailly]

See above PRs... Having Add() not really Add to implement former explicit AutoHistory is (a bit/quite) awkward.
So is copy-pasting the implementation of the ring buffer.

Also it's not quite working like before, will look with fresher eyes tmr/later Edit: got it working.

[ldemailly]

Got it working - it was because the History interface got out of sync with the internal one needed for the extra methods (UnconditionallyAdd() and Replace()) and ditto for carrying the AutoHistory flag into new copies.

I also had to t.lock.Unlock() before calling History.Add() so debug statements in there didn't hang

Short version: golang/term#20 works (for me)

[earthboundkid]

I maintain that Add(string) should be PushFront(string) so that you can use existing deque implementations and any potential future standard library implementations.

[ldemailly]

I maintain that Add(string) should be PushFront(string) so that you can use existing deque implementations

You can't quite use an existing implementation anyway if you need to conditionally add to the history (like I do) so the interface might as well be specific and need an adapter to the concrete type. If anything maybe Add/At are too broad names.

I'd love to move forward though I think it creates complexity for callers vs exposing what one would reasonably need/expect to be available without reinventing or copy-pasta'ing their own implementation - as in get this approved and merged and tagged so I don't need to maintain a fork of x/term anymore

ps: see the added uglyness around unlock'ing and function wrappers in case of panic in the History in latest of the PR

[aclements]

We could expose the internal ring-based history as an exported, concrete type (with a very minimal API), which would make it easy to wrap with another History implementation that makes a small behavior change. Does that sound like a reasonable compromise?

[seankhliao]

I don't think it's worth exposing the current ring implementation, it's not all that much code anyway (30 lines of code).

[ldemailly]

ok so "accepted" with api (and code more or less) from https://github.com/golang/term/pull/20/files ?

[ldemailly]

I updated the original description - ptal / update

[seankhliao]

nothing is accepted yet.

[ldemailly]

yeah thus question mark and asking for edit/updates (I should have put "acceptable?" instead I guess- ESL here)