LUCENE-3041, its become apparent that using a Visitor / Walker isn't right for caching the rewrites of Querys. Although we still intend to introduce the Query / Walker for advanced query transformations, rewriting still serves a purpose for very specific implementation detail writing. As such, it can be very expensive. So I think we should introduce first class support for rewrite caching. I also feel the key is to make the caching as transparent as possible, to reduce the strain on Query implementors.
The TermState idea gave me the idea of maybe making a RewriteState / RewriteCache / RewriteInterceptor, which would be consulted for rewritten Querys. It would then maintain an internal cache that it would check. If a value wasn't found, it'd then call Query#rewrite, and cache the result.
By having this external rewrite source, people could 'pre' rewrite Querys if they were particularly expensive but also common.