Fixes bug 844793 - Added a new search interface.

I'm sending this for a first look. It's big, and the commits are not really separated in logical blocks so they won't help the review.