Probably the same as a normal text undo. You store the "actions" the user performs against the document on a stack. Each action is a replacement of one text str

Probably the same as a normal text undo. You store the "actions" the user performs against the document on a stack. Each action is a replacement of one text string in the document with another (where strings can be zero-length and can start and end at any point). Actions can "do" and "undo" themselves against the document trivially. Then to save space, you compress adjacent actions into single actions (e.g. add('a', 0) and add('b', 1) compress to add("ab", 0)).