Repository: junegunn/fzf (language: 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.


Discussion / hints:
While I agree that this can be useful, it's not trivial to implement. fzf maintains the items as a list of fixed-sized immutable chunks for better performance. Removing something in an immutable chunk affects the core premises of counting, matching, caching, etc. Adding a flag to each item would be another option to implement it, but it's also not without a cost (e.g. increased memory footprint, extra locking).

I'll leave this open and think about it over time.

While not ideal, there can be several strategies to deal with such situations. `transform` is one option.

```sh
(echo yes; echo no) | fzf --bind 'ctrl-a:transform:
  if [[ {} = yes ]]; then
    printf "execute:echo %s; read" {}
  else
    printf "change-header:ctrl-a not allowed for %s" {}
  fi
'
```
I see, would changing the strategy from removing from the list to permanently hiding (until a reaload happens) be more feasible? I imagine there is some logic to hide entries that is already working with the fuzzy matching algorithm. The list would remain the same and be immutable but certain indexes can be marked to remain hidden and unselectable.

Also, thanks for the `transform` suggestion. I'll see if I can apply it in the meanwhile.
Yes, that approach would be better. We still have to guard against concurrent accesses to the "deny list", either by locking on each access during search or copying the full list before search. Assuming that the deny list doesn't grow too large, copying would be preferable.

Fix patch:
diff --git a/man/man1/fzf.1 b/man/man1/fzf.1
index ba3abaa510f..74d0c05d4d4 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 8f4a6d84b07..08d9e868937 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 2b310612d01..4a6c3b2b1cb 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 8919ad876b5..93640cb69af 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 9a06ad615ef..60ddaa71e04 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 24b17744616..8e566263470 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 e15ab8eee01..4eee51b2781 100644
--- a/test/test_core.rb
+++ b/test/test_core.rb
@@ -1666,6 +1666,30 @@ def test_abort_action_chain
     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