Completion Chat November 2019

Back to Shell Autocompletion

Notes from discussion:

Philosophy / Problem

• I think there are two different problems: one for "legacy" code, and another if you're going to make the user rewrite the flag parser in a different language
  • symbolic execution probably makes sense to try to extract completion from legacy C code.
    • although it's possible that some information necessary for completion doesn't exist in the code
  • But if I was to design some subset of sh or Oil to allow "dual purpose" flag parsers and completion functions, then maybe some easier algorithm is possible. Or it would be more like an API than an algorithm
• my view (Andy) is that if you want to be general you should support a language that's closer to what the original program is written in, not a declarative language
• I wanted Oil to obey some basic invariants like "there should be some suffix of the suggested completion that will NOT result in a syntax error" :)
  • although I guess that doesn't quite cover it, because grep myfile.c doesn't result in a syntax error, but it's not a good completion IMO
• opt-in vs. opt-out -- browsers have you opt OUT by backspace, shells generally have you opt in with TAB
  • I think suggestions should be automatic, but modifying the user's buffer should be opt in (unlike chrome)
• http://tenex.opost.com/hbook.html -- talks about a completion system in the OS. esc for completion and ? to display options.
  • I think moving completion into the binary itself, using an API provided by the shell, can accomplish something similar

Observations About Existing Systems

• fish tries to complete filenames for the pattern arg to grep, which is incorrect
  • For example you can see here it doesn't know anything about the command structure, only flags: https://github.com/fish-shell/fish-shell/blob/master/share/completions/grep.fish
  • bash-completion doesn't appear to know that either
  • however zsh does know that the first arg to grep isn't a file
• ls | grep and ls | wc -l make sense because the second commands read from stdin, but ls | ls doesn't. But none of bash/zsh/fish understand that.

API

I think it can be as simple as an API to throw exceptions for command errors, e.g. consider:

grep --no-filename
grep --max-count
grep --max-count=

These all result in syntax errors, and some of them are different. Right now most commands aren't consistent about how they report errors.

But the "carrot" is if they are consistent and use an Oil API, then they will completion for free, and it will be correct.

---

Of course you also need to display completions when there are no syntax errors, like

grep pattern file1.c <TAB>

should complete another file, even though the prefix is a valid command

only the command knows

1. if an flag takes an argument
2. If so, what kind of argument it is

So the syntax error can include a completion type, like

raise SyntaxError('FILE', 'file expected')
raise SyntaxError('HOST', 'host expected')

raise SyntaxError('arg expected')  # a command arg, not flag arg

You could implement such a parser/API in any language but I would start with Oil. I guess you could do it in sh with global variables since it doesn't have rich return values/exceptions.

That is another instance of the problem where the sh language isn't expressive enough to express basic things about its problem domain.

---

• the success case is a problem, you might have to force the user to return a "completion hint" as well as parsed options, e.g.

def Parse(argv):
  # maybe raise syntax error
  return opts, CompletionHint('FILE')  # success, but could be more args

IR Approach

And I mentioned there also another approach that's more like information retrieval -- parse all the successful commands from history, and complete based on that. That eliminates some of the "boiling the ocean" problem, and can also be used for ranking.

i.e. bash on Ubuntu will complete something 500 commands by default from an empty state (and it's slow). but obviously it would be better if it ranks it by the commands you actually use.

I think that's pretty powerful but I haven't explored it yet

I think if you were to really evaluate it from an HCI perspective, it would basically force you to do ranking, because it would be such a big win

bash does no ranking / priority but I think fish does some. zsh doesn't appear to either