There was a proof of concept app ages ago that demonstrated how for any seemingly important permission like location, there were ways to get at the very least "good enough" data for it through other sources on/in the phone, even when you only gave it the bare minimum permissions (nothing that prompted for permissions or would show up in the play store).

From most wide to most precise, you have triangulation by cell towers, Wi-fi SSIDs have been pretty thoroughly mapped to location ages ago, and when your phone sees multiple SSIDs at once it can triangulate location even better based on the signal strength of each. GPS is the most accurate, but location can be trimmed down to well within the walls of a building, if not down to the room without it.

Fucking horrible.

Here it is on F-Droid. Doesn't have the location features I thought it did though. That must have been something else.