Трехсторонняя разность и слияние для замыкающих структур данных - PullRequest
Новая
       43

Трехсторонняя разность и слияние для замыкающих структур данных

0 голосов
/ 18 февраля 2020

Я нашел отличную библиотеку juji / editscript , которая позволяет анализировать и исправлять любые вложенные структуры данных clojure. Кроме того, я хочу реализовать функцию (diff3 a o b), где o является общим предком как a, так и b.

Простым решением является объединение правок из двух разностей.

Входные данные: 

(def o {:a 1 :b 2})
(def a {:a 1 :b 2 :c 3})
(def b {:a 1 :b 2 :d 4})

Различия (правки сценариев): 

(editscript.core/diff o a)
; => [[[:c] :+ 3]]

(editscript.core/diff o b)
; => [[[:d] :+ 4]]

Объединение (объединение ) editscripts: 

(editscript.edit/combine
  (editscript.core/diff o a)
  (editscript.core/diff o b))
; => [[[:c] :+ 3] 
      [[:d] :+ 4]]

Исправления: 

(editscript.core/patch 
  o
  (editscript.edit/combine
    (editscript.core/diff o a)
    (editscript.core/diff o b)))
; => {:a 1, :b 2, :c 3, :d 4}

Но я застрял с обнаружением конфликтов, когда одновременные обновления происходят в одном и том же месте в a и b: 

(def o {:a {:b 1}})
(def a {:a nil})
(def b {:a {:b 2}})

(editscript.edit/combine
  (editscript.core/diff o a)
  (editscript.core/diff o b))
; => [[[:a] :r nil] 
;     [[:a :b] :r 2]]

(editscript.core/patch 
  o
  (editscript.edit/combine
    (editscript.core/diff o a)
    (editscript.core/diff o b))) 
; throws exception

Существуют ли какие-либо известные решения или алгоритмы итерации по этим правкам и нахождения конфликтующих узлов?

...