Modifier canonicalization

[kpreid]

The current situation is that Blocks have an arbitrary list of Modifiers, and there a couple special cases such that if a Modifier::Rotate is being added, it is combined with an existing one if present. However there are some, and will be more, cases where other modifiers too should be put in a consistent order, so that

• operations and other game rules can match blocks without failing because of arbitrary variation in representations, and
• there is a low chance of unbounded storage leaks due to adding modifiers.

The scheme I have in mind for this is:

• Modifiers have a method to map them to a finite set of kinds.
• Each pair of kinds may or may not be considered commutative, i.e. able to be swapped in the modifier list without changing the results.
• A kind might be non-commutative with itself but able to be collapsed into a single instance of itself (e.g. rotations, attribute-setting), which serves a similar purpose

Then, a sketch of an algorithm for canonicalizing a modifier list:

1. Find runs of commutative modifiers; count each run as unordered, that is, they can be thought of as neither before nor after each other.
2. If two adjacent runs have modifiers that are collapsible, collapse them, leaving only one modifier of that type in the pair of runs.
3. Check if the runs are now commutative and bundle them into a larger run if so.
4. Repeat from step 2 until nothing changes.
5. Within each run, sort the modifiers into some canonical order (e.g. Rotate shall always come before Inventory, or vice versa).

Once we have this algorithm, it should be applied at appropriate times by user editing and Operations, but not automatically by all mutations of Blocks.