Ensure predicates are applied during matching

(Replacement for #995, which I temporarily reverted from master)