It's small wonder you didn't realize the tool is called "the silver searcher" just because the binary is named after the chemical symbol for silver ("Ag"), nor that it has been discussed here - it's been a while, and I'm not sure if it ever made it to the front page (but ack might have, and ag might have made an appearance) - apparently it's been four-five years(there's been some reposts): https://news.ycombinator.com/item?id=3835901

As for the package, you might want to try "apt-file":

  sudo apt install apt-file
  apt-file update 
  apt-file find bin/ag

It makes finding some of the less search-friendly packages a little easier, if you know the binary or config file name. I think it'll also work as a poor man's "provides", but I haven't tried:

  apt-file find /etc/alternatives/mail

As for something like everything, there was a "spree" of tools that tried to provide something similar, but I'm not sure of their current state -- I tried looking for some a while back and got the impression they were all more or less abandoned (with the notable exception of locate/mlocate and the similar apropos/mandb for man pages).

It would appear mlocate is most like everything, in that it only index on name/path, not contents.

Of the few I found only "tracker" seemed to be around:

https://wiki.gnome.org/Projects/Tracker

Other than unity's "dash" that is:

https://help.ubuntu.com/16.10/ubuntu-help/unity-dash-files.h...

Finally, there's "recoll":

http://www.lesbonscomptes.com/recoll/