Обобщение 3-way merge
Допустим, у нас есть функция 3-way merge, которая из трех версий O[rigin], A, B однозначно1 делает версию C
Как нетривиально2 обобщить эту функцию на такие случаи:
1. есть R1 (предок) и 3 головы (Ra:R1, Rb:R1, Rc:R1)
2. есть R1 (предок), Ra:R1, Rb:R1, и две головы (Rx:[Rb,Ra] и Rc:R1)
Как-то так. Мне главное чтоб сохранилось свойство консистентности, т.е. чтобы "в итоге" все, получив все наборы ревизий, пришли без дополнительных коммуникаций к одинаковому исходу.
Т.е. чтобы если ПОСЛЕ мержа примера (1) участники узнали что кто-то вбросил голову Ry:[Ra,Rb] то оно смержилось в то же самое, во что смержится пример (2)
В терминах git/hg: мне надо чтобы после того как все один раз push --force, дождались когда пушнут все остальные и pull - автомерж выдал одинаковый результат
В качестве дополнительной инфы у ревизии есть автор, все ревизии от одного автора упорядочены по времени "до/после", но время ревизий двух разных авторов сравнивать нельзя. Т.е. vector clock.
--
1. т.е. merge(O,A,B) === merge(O,B,A), что достигнуто, например, лексикографическим упорядочиванием A, B по хэшу от их содержимого.
НО мерж не коммутативен, т.е. m(A,m(B,C))!=m(m(A,B),C)
2. решению задачи удовлетворяет тривиальная функция которая всегда возвращает null, но это, очевидно, не то)
UPD: предложили посмотреть http://en.wikipedia.org/wiki/C3_linearization , http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory , смотрю
UPD2: да, я знаю про Operational Transformation и Commutative Replicated Data Types, это скорее второе.
Как нетривиально2 обобщить эту функцию на такие случаи:
1. есть R1 (предок) и 3 головы (Ra:R1, Rb:R1, Rc:R1)
2. есть R1 (предок), Ra:R1, Rb:R1, и две головы (Rx:[Rb,Ra] и Rc:R1)
Как-то так. Мне главное чтоб сохранилось свойство консистентности, т.е. чтобы "в итоге" все, получив все наборы ревизий, пришли без дополнительных коммуникаций к одинаковому исходу.
Т.е. чтобы если ПОСЛЕ мержа примера (1) участники узнали что кто-то вбросил голову Ry:[Ra,Rb] то оно смержилось в то же самое, во что смержится пример (2)
В терминах git/hg: мне надо чтобы после того как все один раз push --force, дождались когда пушнут все остальные и pull - автомерж выдал одинаковый результат
В качестве дополнительной инфы у ревизии есть автор, все ревизии от одного автора упорядочены по времени "до/после", но время ревизий двух разных авторов сравнивать нельзя. Т.е. vector clock.
--
1. т.е. merge(O,A,B) === merge(O,B,A), что достигнуто, например, лексикографическим упорядочиванием A, B по хэшу от их содержимого.
НО мерж не коммутативен, т.е. m(A,m(B,C))!=m(m(A,B),C)
2. решению задачи удовлетворяет тривиальная функция которая всегда возвращает null, но это, очевидно, не то)
UPD: предложили посмотреть http://en.wikipedia.org/wiki/C3_linearization , http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory , смотрю
UPD2: да, я знаю про Operational Transformation и Commutative Replicated Data Types, это скорее второе.