merge scribbles

merge.hs

-- reading the code is hard so i tried to imagine what a formalization would look like i was implementing it

-- Notation: big letters = patch sequences, small letters = patches
--
-- In reality operations are freey.
-- We don't evaluate as we go, but instead construct a tree and then have an evaluator for that tree.
-- This way we can decide in which order we will evaluate the patch sequence operations.

(+) : List Patch -> List Patch -> List Patch  -- ignore for now
(-) : List Patch -> List Patch -> List Patch  -- also

merge : Set (List Patch) -> List Patch
merge({X})    := X
merge({X, Y}) := X + Y - merge(fork_point({X, Y}))
-- ... idk about N>2 cases

combine_patches : Set Patch -> Patch
combine_patches({x})    := x
combine_patches({x, y}) := if same_change(x, y) then x else -- idk, something line-based?
-- ... idk about N>2 cases, idk if it even operates on patches or patch sequences?

-- Crisscross merge scenario:

root, init, x, x' : Patch
root = empty
init = insert("original")
x    = replace("original","modified")
x'   = replace("original","modified")

INIT, A, B, C, D : List Patch
INIT = [root, init]

A = [root, init, x]
B = [root, init, x']  -- same patch contents

C = merge({A, B})
  = A + B - merge(fork_point({A, B}))
  = A + B - merge({INIT})
  = A + B - INIT
  = [root, init, x] + [root, init, x'] - [root, init]
  = [root, init, combine_patches({x, x'})]
  = [root, init, xx]  -- let's say that xx is a fresh patch that has the same contents as x or x'

D = -- same thing

E = merge({C, D})
  = C + D - merge(fork_point({C, D}))
  = C + D - merge({A, B})
  
  -- Option 1: Simplify as much as possible, trees resulting in same content are same (path that jj takes now?)
    C + D - merge({A, B})
  = C + D - (A + B - INIT)
  = C + D - A - B + INIT
  = INIT
  = [root, init]

  -- Option 2: Eval in the normal order ("merge resolved first")
    C + D - merge({A, B})
  = C + D - [root, init, xx]
  = [root, init, xx] + [root, init, xx] - [root, init, xx]
  -- Still need to be smart here because if A+A=A then we'll be left over with [].
  -- So we need to count how many of each patch we have, or idk what
  = [root, init, xx]

  -- Option 3: Expand all patch sequences, all parentheses, then eval.
  -- Similar to option 1 but without the 'same content' check
    C + D - merge({A, B})
  = C + D - A - B + INIT
  = [root, init, xx] + [root, init, xx] - [root, init, x] - [root, init, x'] + [root, init]
  -- Option 3a: combine_patches does symbolic cancellation (like what option 1 does with patch sequences)
    [root, init, combine_patches({xx, xx, -x, -x'})]
  = [root, init]
  -- Option 3b: combine_patches refuses to evaluate further and it's like a conflict (good?)
    [root, init, combine_patches({xx, xx, -x, -x'})]
  -- Option 3c: combine_patches (c) never evals so we never lose info about how many same-change patches we have
    [root, init, c({c({x,x'}),c({x,x'}),-x,-x'})]
  = [root, init, c({x,x',x,x',-x,-x'})
  = [root, init, xxxx]  -- let's say combine_patches will result in a fresh patch with the same content as x

  -- Option 4: combine_patches (c) is preserved, eval order is followed
  = C + D - (A + B - INIT)
  = [root, init, c({x,x'})] + [root, init, c({x,x'})] - [root, init, c({x,x'})]
  = [root, init, c({x,x'})]  -- somehow? not sure