Versioned provides take 2

New version of !14 (closed)

I think the behaviour might match the old one now, but please review (and feel free to fix any mistakes I have made.)

Thanks!