blob: 752d025055e3cc485b5774449a1289f4250a1f92 [file] [log] [blame]
Scott Baker2c1c4822019-10-16 11:02:41 -07001/*
2 * Copyright 2018-present Open Networking Foundation
3
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7
8 * http://www.apache.org/licenses/LICENSE-2.0
9
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package model
18
19import (
Scott Bakere73f91e2019-10-17 12:58:11 -070020 "github.com/opencord/voltha-lib-go/pkg/log"
Scott Baker2c1c4822019-10-16 11:02:41 -070021)
22
23func revisionsAreEqual(a, b []Revision) bool {
24 // If one is nil, the other must also be nil.
25 if (a == nil) != (b == nil) {
26 return false
27 }
28
29 if len(a) != len(b) {
30 return false
31 }
32
33 for i := range a {
34 if a[i] != b[i] {
35 return false
36 }
37 }
38
39 return true
40}
41
42type changeAnalysis struct {
43 KeyMap1 map[string]int
44 KeyMap2 map[string]int
45 AddedKeys map[string]struct{}
46 RemovedKeys map[string]struct{}
47 ChangedKeys map[string]struct{}
48}
49
50func newChangeAnalysis(lst1, lst2 []Revision, keyName string) *changeAnalysis {
51 changes := &changeAnalysis{}
52
53 changes.KeyMap1 = make(map[string]int)
54 changes.KeyMap2 = make(map[string]int)
55
56 changes.AddedKeys = make(map[string]struct{})
57 changes.RemovedKeys = make(map[string]struct{})
58 changes.ChangedKeys = make(map[string]struct{})
59
60 for i, rev := range lst1 {
61 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
62 changes.KeyMap1[v.String()] = i
63 }
64 for i, rev := range lst2 {
65 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
66 changes.KeyMap2[v.String()] = i
67 }
68 for v := range changes.KeyMap2 {
69 if _, ok := changes.KeyMap1[v]; !ok {
70 changes.AddedKeys[v] = struct{}{}
71 }
72 }
73 for v := range changes.KeyMap1 {
74 if _, ok := changes.KeyMap2[v]; !ok {
75 changes.RemovedKeys[v] = struct{}{}
76 }
77 }
78 for v := range changes.KeyMap1 {
79 if _, ok := changes.KeyMap2[v]; ok && lst1[changes.KeyMap1[v]].GetHash() != lst2[changes.KeyMap2[v]].GetHash() {
80 changes.ChangedKeys[v] = struct{}{}
81 }
82 }
83
84 return changes
85}
86
87// Merge3Way takes care of combining the revision contents of the same data set
88func Merge3Way(
89 forkRev, srcRev, dstRev Revision,
90 mergeChildFunc func(Revision) Revision,
91 dryRun bool) (rev Revision, changes []ChangeTuple) {
92
93 log.Debugw("3-way-merge-request", log.Fields{"dryRun": dryRun})
94
95 var configChanged bool
96 var revsToDiscard []Revision
97
98 if dstRev.GetConfig() == forkRev.GetConfig() {
99 configChanged = dstRev.GetConfig() != srcRev.GetConfig()
100 } else {
101 if dstRev.GetConfig().Hash != srcRev.GetConfig().Hash {
102 log.Error("config-collision")
103 }
104 configChanged = true
105 }
106
107 //newChildren := reflect.ValueOf(dstRev.GetAllChildren()).Interface().(map[string][]Revision)
108 newChildren := make(map[string][]Revision)
109 for entryName, childrenEntry := range dstRev.GetAllChildren() {
110 //newRev.Children[entryName] = append(newRev.Children[entryName], childrenEntry...)
111 newChildren[entryName] = make([]Revision, len(childrenEntry))
112 copy(newChildren[entryName], childrenEntry)
113 }
114
115 childrenFields := ChildrenFields(forkRev.GetData())
116
117 for fieldName, field := range childrenFields {
118 forkList := forkRev.GetChildren(fieldName)
119 srcList := srcRev.GetChildren(fieldName)
120 dstList := dstRev.GetChildren(fieldName)
121
122 if revisionsAreEqual(dstList, srcList) {
123 for _, rev := range srcList {
124 mergeChildFunc(rev)
125 }
126 continue
127 }
128
129 if field.Key == "" {
130 if revisionsAreEqual(dstList, forkList) {
131 if !revisionsAreEqual(srcList, forkList) {
132 log.Error("we should not be here")
133 } else {
134 for _, rev := range srcList {
135 newChildren[fieldName] = append(newChildren[fieldName], mergeChildFunc(rev))
136 }
137 if field.IsContainer {
138 changes = append(
139 changes, ChangeTuple{POST_LISTCHANGE,
140 NewOperationContext("", nil, fieldName, ""), nil},
141 )
142 }
143 }
144 } else {
145 if !revisionsAreEqual(srcList, forkList) {
146 log.Error("cannot merge - single child node or un-keyed children list has changed")
147 }
148 }
149 } else {
150 if revisionsAreEqual(dstList, forkList) {
151 src := newChangeAnalysis(forkList, srcList, field.Key)
152
153 newList := make([]Revision, len(srcList))
154 copy(newList, srcList)
155
156 for key := range src.AddedKeys {
157 idx := src.KeyMap2[key]
158 newRev := mergeChildFunc(newList[idx])
159
160 // FIXME: newRev may come back as nil... exclude those entries for now
161 if newRev != nil {
162 newList[idx] = newRev
163 changes = append(changes, ChangeTuple{POST_ADD, newList[idx].GetData(), newRev.GetData()})
164 }
165 }
166 for key := range src.RemovedKeys {
167 oldRev := forkList[src.KeyMap1[key]]
168 revsToDiscard = append(revsToDiscard, oldRev)
169 changes = append(changes, ChangeTuple{POST_REMOVE, oldRev.GetData(), nil})
170 }
171 for key := range src.ChangedKeys {
172 idx := src.KeyMap2[key]
173 newRev := mergeChildFunc(newList[idx])
174
175 // FIXME: newRev may come back as nil... exclude those entries for now
176 if newRev != nil {
177 newList[idx] = newRev
178 }
179 }
180
181 if !dryRun {
182 newChildren[fieldName] = newList
183 }
184 } else {
185 src := newChangeAnalysis(forkList, srcList, field.Key)
186 dst := newChangeAnalysis(forkList, dstList, field.Key)
187
188 newList := make([]Revision, len(dstList))
189 copy(newList, dstList)
190
191 for key := range src.AddedKeys {
192 if _, exists := dst.AddedKeys[key]; exists {
193 childDstRev := dstList[dst.KeyMap2[key]]
194 childSrcRev := srcList[src.KeyMap2[key]]
195 if childDstRev.GetHash() == childSrcRev.GetHash() {
196 mergeChildFunc(childDstRev)
197 } else {
198 log.Error("conflict error - revision has been added is different")
199 }
200 } else {
201 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
202 newList = append(newList, newRev)
203 changes = append(changes, ChangeTuple{POST_ADD, srcList[src.KeyMap2[key]], newRev.GetData()})
204 }
205 }
206 for key := range src.ChangedKeys {
207 if _, removed := dst.RemovedKeys[key]; removed {
208 log.Error("conflict error - revision has been removed")
209 } else if _, changed := dst.ChangedKeys[key]; changed {
210 childDstRev := dstList[dst.KeyMap2[key]]
211 childSrcRev := srcList[src.KeyMap2[key]]
212 if childDstRev.GetHash() == childSrcRev.GetHash() {
213 mergeChildFunc(childSrcRev)
214 } else if childDstRev.GetConfig().Hash != childSrcRev.GetConfig().Hash {
215 log.Error("conflict error - revision has been changed and is different")
216 } else {
217 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
218 newList[dst.KeyMap2[key]] = newRev
219 }
220 } else {
221 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
222 newList[dst.KeyMap2[key]] = newRev
223 }
224 }
225
226 // TODO: how do i sort this map in reverse order?
227 for key := range src.RemovedKeys {
228 if _, changed := dst.ChangedKeys[key]; changed {
229 log.Error("conflict error - revision has changed")
230 }
231 if _, removed := dst.RemovedKeys[key]; !removed {
232 dstIdx := dst.KeyMap2[key]
233 oldRev := newList[dstIdx]
234 revsToDiscard = append(revsToDiscard, oldRev)
235
236 copy(newList[dstIdx:], newList[dstIdx+1:])
237 newList[len(newList)-1] = nil
238 newList = newList[:len(newList)-1]
239
240 changes = append(changes, ChangeTuple{POST_REMOVE, oldRev.GetData(), nil})
241 }
242 }
243
244 if !dryRun {
245 newChildren[fieldName] = newList
246 }
247 }
248 }
249 }
250
251 if !dryRun && len(newChildren) > 0 {
252 if configChanged {
253 rev = srcRev
254 } else {
255 rev = dstRev
256 }
257
258 for _, discarded := range revsToDiscard {
259 discarded.Drop("", true)
260 }
261
262 // FIXME: Do not discard the latest value for now
263 //dstRev.GetBranch().GetLatest().Drop("", configChanged)
264 rev = rev.UpdateAllChildren(newChildren, dstRev.GetBranch())
265
266 if configChanged {
267 changes = append(changes, ChangeTuple{POST_UPDATE, dstRev.GetBranch().GetLatest().GetData(), rev.GetData()})
268 }
269 return rev, changes
270 }
271
272 return nil, nil
273}