slamdata/slamengine — pull request #96 by jdegoes (2014-07-04 19:21:54+00:00)
Title: Revamp merging algorithm to preserve structure on both sides

The old merging algorithm was broken. The following invariant must be held at all times:

After a merge is complete, it should be possible to transform either a new left or a new right operation from the left or right schema (respectively) into the unified schema by applying the left or right patch to the op (respectively).

This invariant requires preserving information from both sides. Previously, information was destroyed whenever one side was exhausted of pipeline ops. In the new algorithm, identity projections are synthesized and used to preserve information on the side that has run out of ops.

Note there are two "hacks" in this PR that must be fixed, but the code is substantially more accurate than what's in head.