Repository: junegunn/fzf (go)

Issue:
[Feature Request] Action to remove/pop entries in the list
### Checklist

- [x] I have read through the manual page (`man fzf`)
- [x] I have searched through the existing issues
- [x] For bug reports, I have checked if the bug is reproducible in the latest version of fzf

### Output of `fzf --version`

0.57.0 (0476a65)

### OS

- [x] Linux
- [ ] macOS
- [x] Windows
- [ ] Etc.

### Shell

- [x] bash
- [x] zsh
- [ ] fish

### Problem / Steps to reproduce

I have encounter the use case in which I would like to remove 1 or more items in the list displayed in fzf.

For simplicity take the following example:

```bash
printf 'top\nmiddle\nbottom' | fzf --bind 'ctrl-a:execute(operation that makes "bottom" invalid for selection)'
```

Where the options `top`, `middle` and `bottom` are all valid options. However if you press `ctrl-a` to run some extra processing, then the `bottom` option stops being valid and should not be selected anymore.

My current solution for this is to add a reload action and filtering out the invalid option(s). However depending on the case reloading and filtering could be expensive/slow or add a lot of extra complexity. My assumption is that removing/filtering out options in fzf is probably faster and easier as the search already does that when fuzzy matching to narrow options.

The proposed feature is to include a `pop` action (name used for example) that could be used to remove items from the list.

- Without arguments (`pop`) e.g. `--bind 'ctrl-a:execute(foo {1})+pop+execute(something {+f})`
  - When multiple entries are selected, they all get removed from the list.
  - When there is no selection (e.g. --no-multi), currently focused item is removed.
  - Template values (`{1}`, `{n}`, `{+f}`, etc.) should remain unchanged from the start of the --bind flag until the last action in the same --bind flag even if a `pop` action was used.
- With arguments (`pop(N)`) e.g. `--bind 'ctrl-a:execute(foo {1})+pop(5)+execute(something {+f})`
  - Argument `N` represents a number, range of numbers `1..2` or space separated list `1 2 3 4..6` that represent the index of the entries to remove.
  - Templates that represent indexes are valid `{n}` and `{+n}`

This is just a high level description of how the feature could work but it is open for discussion if the feature is considered.

Thanks.

Pull request description:
Add 'exclude' action for excluding current/selected items from the result
Close #4185 

## Summary

Add `exclude` action to make the current item or the selected items excluded from the result.

## Discussion / Issues

* `exclude` "excludes" the selected items (`--multi`) at once if there's any, instead of excluding the "current" item on the cursor. Is this acceptable, or should we have a separate action? i.e. `exclude-current` + `exclude-selected`. I prefer the current implementation.
* The total item count does not decrease on `exclude`. I think this has a value of indicating that some items are excluded, as opposed to the list being fully "reloaded."
* To avoid the overhead of locking, we copy the exclusion list before passing it to the matcher. This is fine for small lists. But it does have performance problem if the exclusion list becomes excessively large.
  ```sh
  # But realistically, who would do this?
  seq 10000000 | fzf --sync --multi --bind start:select-all+exclude
  ```


Patch:
diff --git a/man/man1/fzf.1 b/man/man1/fzf.1
index ba3abaa5..74d0c05d 100644
--- a/man/man1/fzf.1
+++ b/man/man1/fzf.1
@@ -1601,6 +1601,7 @@ A key or an event can be bound to one or more of the following actions.
     \fBdown\fR                         \fIctrl\-j  ctrl\-n  down\fR
     \fBenable\-search\fR                (enable search functionality)
     \fBend\-of\-line\fR                  \fIctrl\-e  end\fR
+    \fBexclude\fR                      (exclude the current item or the selected items from the result)
     \fBexecute(...)\fR                 (see below for the details)
     \fBexecute\-silent(...)\fR          (see below for the details)
     \fBfirst\fR                        (move to the first match; same as \fBpos(1)\fR)
diff --git a/src/core.go b/src/core.go
index 8f4a6d84..08d9e868 100644
--- a/src/core.go
+++ b/src/core.go
@@ -198,10 +198,26 @@ func Run(opts *Options) (int, error) {
 	inputRevision := revision{}
 	snapshotRevision := revision{}
 	patternCache := make(map[string]*Pattern)
+	denyMutex := sync.Mutex{}
+	denylist := make(map[int32]struct{})
+	clearDenylist := func() {
+		denyMutex.Lock()
+		if len(denylist) > 0 {
+			patternCache = make(map[string]*Pattern)
+		}
+		denylist = make(map[int32]struct{})
+		denyMutex.Unlock()
+	}
 	patternBuilder := func(runes []rune) *Pattern {
+		denyMutex.Lock()
+		denylistCopy := make(map[int32]struct{})
+		for k, v := range denylist {
+			denylistCopy[k] = v
+		}
+		denyMutex.Unlock()
 		return BuildPattern(cache, patternCache,
 			opts.Fuzzy, opts.FuzzyAlgo, opts.Extended, opts.Case, opts.Normalize, forward, withPos,
-			opts.Filter == nil, nth, opts.Delimiter, inputRevision, runes)
+			opts.Filter == nil, nth, opts.Delimiter, inputRevision, runes, denylistCopy)
 	}
 	matcher := NewMatcher(cache, patternBuilder, sort, opts.Tac, eventBox, inputRevision)
 
@@ -301,6 +317,9 @@ func Run(opts *Options) (int, error) {
 	var snapshot []*Chunk
 	var count int
 	restart := func(command commandSpec, environ []string) {
+		if !useSnapshot {
+			clearDenylist()
+		}
 		reading = true
 		chunkList.Clear()
 		itemIndex = 0
@@ -347,7 +366,8 @@ func Run(opts *Options) (int, error) {
 					} else {
 						reading = reading && evt == EvtReadNew
 					}
-					if useSnapshot && evt == EvtReadFin {
+					if useSnapshot && evt == EvtReadFin { // reload-sync
+						clearDenylist()
 						useSnapshot = false
 					}
 					if !useSnapshot {
@@ -378,9 +398,21 @@ func Run(opts *Options) (int, error) {
 						command = val.command
 						environ = val.environ
 						changed = val.changed
+						bump := false
+						if len(val.denylist) > 0 && val.revision.compatible(inputRevision) {
+							denyMutex.Lock()
+							for _, itemIndex := range val.denylist {
+								denylist[itemIndex] = struct{}{}
+							}
+							denyMutex.Unlock()
+							bump = true
+						}
 						if val.nth != nil {
 							// Change nth and clear caches
 							nth = *val.nth
+							bump = true
+						}
+						if bump {
 							patternCache = make(map[string]*Pattern)
 							cache.Clear()
 							inputRevision.bumpMinor()
diff --git a/src/options.go b/src/options.go
index 2b310612..4a6c3b2b 100644
--- a/src/options.go
+++ b/src/options.go
@@ -1603,6 +1603,8 @@ func parseActionList(masked string, original string, prevActions []*action, putA
 			}
 		case "bell":
 			appendAction(actBell)
+		case "exclude":
+			appendAction(actExclude)
 		default:
 			t := isExecuteAction(specLower)
 			if t == actIgnore {
diff --git a/src/pattern.go b/src/pattern.go
index 8919ad87..93640cb6 100644
--- a/src/pattern.go
+++ b/src/pattern.go
@@ -63,6 +63,7 @@ type Pattern struct {
 	revision      revision
 	procFun       map[termType]algo.Algo
 	cache         *ChunkCache
+	denylist      map[int32]struct{}
 }
 
 var _splitRegex *regexp.Regexp
@@ -73,7 +74,7 @@ func init() {
 
 // BuildPattern builds Pattern object from the given arguments
 func BuildPattern(cache *ChunkCache, patternCache map[string]*Pattern, fuzzy bool, fuzzyAlgo algo.Algo, extended bool, caseMode Case, normalize bool, forward bool,
-	withPos bool, cacheable bool, nth []Range, delimiter Delimiter, revision revision, runes []rune) *Pattern {
+	withPos bool, cacheable bool, nth []Range, delimiter Delimiter, revision revision, runes []rune, denylist map[int32]struct{}) *Pattern {
 
 	var asString string
 	if extended {
@@ -144,6 +145,7 @@ func BuildPattern(cache *ChunkCache, patternCache map[string]*Pattern, fuzzy boo
 		revision:      revision,
 		delimiter:     delimiter,
 		cache:         cache,
+		denylist:      denylist,
 		procFun:       make(map[termType]algo.Algo)}
 
 	ptr.cacheKey = ptr.buildCacheKey()
@@ -243,6 +245,9 @@ func parseTerms(fuzzy bool, caseMode Case, normalize bool, str string) []termSet
 
 // IsEmpty returns true if the pattern is effectively empty
 func (p *Pattern) IsEmpty() bool {
+	if len(p.denylist) > 0 {
+		return false
+	}
 	if !p.extended {
 		return len(p.text) == 0
 	}
@@ -296,14 +301,38 @@ func (p *Pattern) Match(chunk *Chunk, slab *util.Slab) []Result {
 func (p *Pattern) matchChunk(chunk *Chunk, space []Result, slab *util.Slab) []Result {
 	matches := []Result{}
 
+	if len(p.denylist) == 0 {
+		// Huge code duplication for minimizing unnecessary map lookups
+		if space == nil {
+			for idx := 0; idx < chunk.count; idx++ {
+				if match, _, _ := p.MatchItem(&chunk.items[idx], p.withPos, slab); match != nil {
+					matches = append(matches, *match)
+				}
+			}
+		} else {
+			for _, result := range space {
+				if match, _, _ := p.MatchItem(result.item, p.withPos, slab); match != nil {
+					matches = append(matches, *match)
+				}
+			}
+		}
+		return matches
+	}
+
 	if space == nil {
 		for idx := 0; idx < chunk.count; idx++ {
+			if _, prs := p.denylist[chunk.items[idx].Index()]; prs {
+				continue
+			}
 			if match, _, _ := p.MatchItem(&chunk.items[idx], p.withPos, slab); match != nil {
 				matches = append(matches, *match)
 			}
 		}
 	} else {
 		for _, result := range space {
+			if _, prs := p.denylist[result.item.Index()]; prs {
+				continue
+			}
 			if match, _, _ := p.MatchItem(result.item, p.withPos, slab); match != nil {
 				matches = append(matches, *match)
 			}
diff --git a/src/terminal.go b/src/terminal.go
index 9a06ad61..60ddaa71 100644
--- a/src/terminal.go
+++ b/src/terminal.go
@@ -584,6 +584,7 @@ const (
 	actShowHeader
 	actHideHeader
 	actBell
+	actExclude
 )
 
 func (a actionType) Name() string {
@@ -621,12 +622,14 @@ type placeholderFlags struct {
 }
 
 type searchRequest struct {
-	sort    bool
-	sync    bool
-	nth     *[]Range
-	command *commandSpec
-	environ []string
-	changed bool
+	sort     bool
+	sync     bool
+	nth      *[]Range
+	command  *commandSpec
+	environ  []string
+	changed  bool
+	denylist []int32
+	revision revision
 }
 
 type previewRequest struct {
@@ -4751,6 +4754,7 @@ func (t *Terminal) Loop() error {
 		changed := false
 		beof := false
 		queryChanged := false
+		denylist := []int32{}
 
 		// Special handling of --sync. Activate the interface on the second tick.
 		if loopIndex == 1 && t.deferActivation() {
@@ -4907,6 +4911,21 @@ func (t *Terminal) Loop() error {
 				}
 			case actBell:
 				t.tui.Bell()
+			case actExclude:
+				if len(t.selected) > 0 {
+					for _, item := range t.sortSelected() {
+						denylist = append(denylist, item.item.Index())
+					}
+					// Clear selected items
+					t.selected = make(map[int32]selectedItem)
+					t.version++
+				} else {
+					item := t.currentItem()
+					if item != nil {
+						denylist = append(denylist, item.Index())
+					}
+				}
+				changed = true
 			case actExecute, actExecuteSilent:
 				t.executeCommand(a.a, false, a.t == actExecuteSilent, false, false, "")
 			case actExecuteMulti:
@@ -6016,7 +6035,7 @@ func (t *Terminal) Loop() error {
 		reload := changed || newCommand != nil
 		var reloadRequest *searchRequest
 		if reload {
-			reloadRequest = &searchRequest{sort: t.sort, sync: reloadSync, nth: newNth, command: newCommand, environ: t.environ(), changed: changed}
+			reloadRequest = &searchRequest{sort: t.sort, sync: reloadSync, nth: newNth, command: newCommand, environ: t.environ(), changed: changed, denylist: denylist, revision: t.merger.Revision()}
 		}
 		t.mutex.Unlock() // Must be unlocked before touching reqBox
 


Test patch:
diff --git a/src/pattern_test.go b/src/pattern_test.go
index 24b17744..8e566263 100644
--- a/src/pattern_test.go
+++ b/src/pattern_test.go
@@ -68,7 +68,7 @@ func buildPattern(fuzzy bool, fuzzyAlgo algo.Algo, extended bool, caseMode Case,
 	withPos bool, cacheable bool, nth []Range, delimiter Delimiter, runes []rune) *Pattern {
 	return BuildPattern(NewChunkCache(), make(map[string]*Pattern),
 		fuzzy, fuzzyAlgo, extended, caseMode, normalize, forward,
-		withPos, cacheable, nth, delimiter, revision{}, runes)
+		withPos, cacheable, nth, delimiter, revision{}, runes, nil)
 }
 
 func TestExact(t *testing.T) {
diff --git a/test/test_core.rb b/test/test_core.rb
index e15ab8ee..4eee51b2 100644
--- a/test/test_core.rb
+++ b/test/test_core.rb
@@ -1666,6 +1666,30 @@ class TestCore < TestInteractive
     end
   end
 
+  def test_exclude
+    tmux.send_keys %(seq 1000 | #{FZF} --multi --bind 'a:exclude,b:reload(seq 1000),c:reload-sync(seq 1000)'), :Enter
+
+    tmux.until { |lines| assert_equal 1000, lines.match_count }
+    tmux.until { |lines| assert_includes lines, '> 1' }
+    tmux.send_keys :a
+    tmux.until { |lines| assert_includes lines, '> 2' }
+    tmux.until { |lines| assert_equal 999, lines.match_count }
+    tmux.send_keys :Up, :BTab, :BTab, :BTab, :a
+    tmux.until { |lines| assert_equal 996, lines.match_count }
+    tmux.until { |lines| assert_includes lines, '> 9' }
+    tmux.send_keys :b
+    tmux.until { |lines| assert_equal 1000, lines.match_count }
+    tmux.until { |lines| assert_includes lines, '> 5' }
+    tmux.send_keys :Tab, :Tab, :Tab, :a
+    tmux.until { |lines| assert_equal 997, lines.match_count }
+    tmux.until { |lines| assert_includes lines, '> 2' }
+    tmux.send_keys :c
+    tmux.until { |lines| assert_equal 1000, lines.match_count }
+    tmux.until { |lines| assert_includes lines, '> 2' }
+
+    # TODO: We should also check the behavior of 'exclude' during reloads
+  end
+
   def test_accept_nth
     tmux.send_keys %((echo "foo  bar  baz"; echo "bar baz  foo") | #{FZF} --multi --accept-nth 2,2 --sync --bind start:select-all+accept > #{tempname}), :Enter
     wait do