Formula fuzzy search and did you mean

[bayandin]

• Have you followed the guidelines in our Contributing document?
• Have you checked to ensure there aren't other open Pull Requests for the same change?
• Have you added an explanation of what your changes do and why you'd like us to include them?
• Have you written new tests for your changes? Here's an example.
• Have you successfully run brew style with your changes locally?
• Have you successfully run brew typecheck with your changes locally?
• Have you successfully run brew tests with your changes locally?

---

This PR improves brew search command by adding approximately matching formula names (which is useful for mistyped formula names) and adds "Did you mean ..." for mistyped formula names (will be useful for cases like #11526):

Before

$ brew search ripgrip
Error: No formulae or casks found for "ripgrip".

$ brew info ripgrip
Error: No available formula or cask with the name "ripgrip".
==> Searching for a previously deleted formula (in the last month)...
Error: No previously deleted formula found.

$ brew install ripgrip
==> Searching for similarly named formulae...
Error: No similarly named formulae found.
Error: No available formula or cask with the name "ripgrip".
==> Searching for a previously deleted formula (in the last month)...
Error: No previously deleted formula found.
==> Searching taps on GitHub...
Error: No formulae found in taps.

After

$ brew search ripgrip
==> Formulae
ripgrep                                                                                       pipgrip

$ brew info ripgrip
Error: No available formula or cask with the name "ripgrip". Did you mean ripgrep or pipgrip?
==> Searching for a previously deleted formula (in the last month)...
Error: No previously deleted formula found.

$ brew install ripgrip
==> Searching for similarly named formulae...
These similarly named formulae were found:
ripgrep                                                                                       pipgrip
To install one of them, run (for example):
  brew install ripgrep
Error: No available formula or cask with the name "ripgrip". Did you mean ripgrep or pipgrip?
==> Searching for a previously deleted formula (in the last month)...
Error: No previously deleted formula found.
==> Searching taps on GitHub...
Error: No formulae found in taps.

I use did_you_mean gem for it (it bundled with ruby since ruby 2.6 and promoted to default gems in ruby 2.7).
To make it possible to use it I had to remove it from a list of disabled options, here's a test of how it affects performance (I've chosen HOMEBREW_NO_ANALYTICS=1 brew info docker command, please let me know if this is not representative enough):

$ hyperfine --warmup=1 --parameter-list opts "--disable=did_you_mean\,rubyopt","--disable=rubyopt" "HOMEBREW_RUBY_DISABLE_OPTIONS={opts} HOMEBREW_NO_ANALYTICS=1 brew info docker"
Benchmark #1: HOMEBREW_RUBY_DISABLE_OPTIONS=--disable=did_you_mean,rubyopt HOMEBREW_NO_ANALYTICS=1 brew info docker
  Time (mean ± σ):      1.181 s ±  0.023 s    [User: 568.1 ms, System: 594.0 ms]
  Range (min … max):    1.166 s …  1.244 s    10 runs
 
Benchmark #2: HOMEBREW_RUBY_DISABLE_OPTIONS=--disable=rubyopt HOMEBREW_NO_ANALYTICS=1 brew info docker
  Time (mean ± σ):      1.185 s ±  0.011 s    [User: 569.6 ms, System: 595.8 ms]
  Range (min … max):    1.176 s …  1.209 s    10 runs
 
Summary
  'HOMEBREW_RUBY_DISABLE_OPTIONS=--disable=did_you_mean,rubyopt HOMEBREW_NO_ANALYTICS=1 brew info docker' ran
    1.00 ± 0.02 times faster than 'HOMEBREW_RUBY_DISABLE_OPTIONS=--disable=rubyopt HOMEBREW_NO_ANALYTICS=1 brew info docker'

The fuzzy search itself works fast enough and takes ~0.02s per query:

require 'benchmark'
Formula.fuzzy_search("warmup")

n = 100
Benchmark.bm do |x|
  %w[dacker ripgrip ffmpeg alkdsalksdhj aa].each do |query|
    x.report(query) { n.times { Formula.fuzzy_search(query) } }
  end
end

       user     system      total        real
dacker  1.767602   0.004441   1.772043 (  1.775984)
ripgrip  1.991206   0.004591   1.995797 (  1.999828)
ffmpeg  1.797626   0.003832   1.801458 (  1.804969)
alkdsalksdhj  2.952700   0.010327   2.963027 (  2.972564)
aa  0.826834   0.001736   0.828570 (  0.830189)

Things to be sorted out:

• Despite it works in brew (for me), tests can't find did_you_mean gem (need to check if we use different sets of gems for brew and tests). Any suggestions are welcome here 🙂

An error occurred while loading spec_helper.
Hint: Install the `did_you_mean` gem in order to provide suggestions for similarly named files.
Failure/Error: require "did_you_mean"

LoadError:
  cannot load such file -- did_you_mean

ToDo (could be sorted out in the following PRs):

• Add support for casks
• Add support for formula renames/aliases
• Add support for cli commands / add Did you mean for "Error: Unknown command"

[BrewTestBot]

Review period will end on 2021-06-22 at 00:00:00 UTC.

[MikeMcQuaid]

This looks great so far, fantastic work @bayandin!

[MikeMcQuaid]

==> Searching for similarly named formulae...
These similarly named formulae were found:
ripgrep pipgrip
To install one of them, run (for example):
brew install ripgrep
Error: No available formula or cask with the name "ripgrip". Did you mean ripgrep or pipgrip?

Nice! Feels like the output is slightly duplicated, though. Maybe worth removing from the exception message?

    1.00 ± 0.02 times faster than 'HOMEBREW_RUBY_DISABLE_OPTIONS=--disable=rubyopt HOMEBREW_NO_ANALYTICS=1 brew info docker'

This seems fine/worth it 👍🏻

• Despite it works in brew (for me), tests can't find did_you_mean gem (need to check if we use different sets of gems for brew and tests). Any suggestions are welcome here 🙂

May need to adjust the load path and/or requires in spec_helper.rb or tests.rb.

[BrewTestBot]

Review period ended.

[bayandin]

==> Searching for similarly named formulae...
These similarly named formulae were found:
ripgrep pipgrip
To install one of them, run (for example):
brew install ripgrep
Error: No available formula or cask with the name "ripgrip". Did you mean ripgrep or pipgrip?

Nice! Feels like the output is slightly duplicated, though. Maybe worth removing from the exception message?

==> Searching for similarly named formulae...
Error: No similarly named formulae found.
Error: No available formula or cask with the name "ripgrip".

Yep, it looks like now, we have similar duplication. I've removed the second message.

• Despite it works in brew (for me), tests can't find did_you_mean gem (need to check if we use different sets of gems for brew and tests). Any suggestions are welcome here 🙂

May need to adjust the load path and/or requires in spec_helper.rb or tests.rb.

We run tests via bundle exec ... and we have BUNDLE_DISABLE_SHARED_GEMS: "true". It looks like this doesn't allow bundler to pick up existing (not bundled) gems, even if they're bundled with ruby.
I've decided to bundle also did_you_mean gem. It's pure ruby and relatively small:

$ scc --no-cocomo ./Library/Homebrew/vendor/bundle/ruby/2.6.0/gems/did_you_mean-1.5.0/
───────────────────────────────────────────────────────────────────────────────
Language                 Files     Lines   Blanks  Comments     Code Complexity
───────────────────────────────────────────────────────────────────────────────
Ruby                        43      2149      376       247     1526         65
Markdown                     5       811      283         0      528          0
YAML                         5       204       10         0      194          0
Gemfile                      1        10        2         1        7          0
Plain Text                   1        22        4         0       18          0
Rakefile                     1        73       10         0       63          1
Ruby HTML                    1         8        3         0        5          0
gitignore                    1        19        0         0       19          0
───────────────────────────────────────────────────────────────────────────────
Total                       58      3296      688       248     2360         66
───────────────────────────────────────────────────────────────────────────────
Processed 108351 bytes, 0.108 megabytes (SI)
───────────────────────────────────────────────────────────────────────────────

We'll be able to get rid of it when switching to ruby 2.7 in the future.

Alternatively, if we don't want to bundle it, we can use this gem opportunistically (like return [] unless defined?(DidYouMean::SpellChecker))

[MikeMcQuaid]

Makes sense, thanks @bayandin!