I was thinking the other day, wouldn't it be easyish and optimal to specify/calculate all the data that is used to generate a fragment, store the information in a tree, and invalidate the parents when a node changes.

This would only invalidate data that needs to be invalidated, and it doesn't sound too hard to implement... Does it exist anywhere? What are downsides I haven't thought of?