Queries should be immutable

[RutledgePaulV]

Mutability can produce unexpected behavior, etc. It's easier to reason about if each method on a query object always returns an immutable representation.

Since we're already dealing with trees I'm curious if we could use persistent data structures to achieve this and avoid copying. (but the overall trees will be small so copying wouldn't be the worst thing in the world).