Regex expected exception message

Aims to solve #1263. Also gives some basic test coverage for `ExceptionMessage` constraint.