blob: 01e942b70c986160e578187663e5f1c8357bc621 [file] [log] [blame]
Stephane Barbarieec0919b2018-09-05 14:14:29 -04001/*
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 */
Stephane Barbariedc5022d2018-11-19 15:21:44 -050016
Stephane Barbarieec0919b2018-09-05 14:14:29 -040017package model
18
19import (
npujar467fe752020-01-16 20:17:45 +053020 "context"
21
serkant.uluderya2ae470f2020-01-21 11:13:09 -080022 "github.com/opencord/voltha-lib-go/v3/pkg/log"
Stephane Barbarieec0919b2018-09-05 14:14:29 -040023)
24
25func revisionsAreEqual(a, b []Revision) bool {
26 // If one is nil, the other must also be nil.
27 if (a == nil) != (b == nil) {
28 return false
29 }
30
31 if len(a) != len(b) {
32 return false
33 }
34
35 for i := range a {
36 if a[i] != b[i] {
37 return false
38 }
39 }
40
41 return true
42}
43
44type changeAnalysis struct {
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040045 KeyMap1 map[string]int
46 KeyMap2 map[string]int
47 AddedKeys map[string]struct{}
48 RemovedKeys map[string]struct{}
49 ChangedKeys map[string]struct{}
Stephane Barbarieec0919b2018-09-05 14:14:29 -040050}
51
52func newChangeAnalysis(lst1, lst2 []Revision, keyName string) *changeAnalysis {
53 changes := &changeAnalysis{}
54
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040055 changes.KeyMap1 = make(map[string]int)
56 changes.KeyMap2 = make(map[string]int)
Stephane Barbarieec0919b2018-09-05 14:14:29 -040057
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040058 changes.AddedKeys = make(map[string]struct{})
59 changes.RemovedKeys = make(map[string]struct{})
60 changes.ChangedKeys = make(map[string]struct{})
Stephane Barbarieec0919b2018-09-05 14:14:29 -040061
62 for i, rev := range lst1 {
63 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040064 changes.KeyMap1[v.String()] = i
Stephane Barbarieec0919b2018-09-05 14:14:29 -040065 }
66 for i, rev := range lst2 {
67 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040068 changes.KeyMap2[v.String()] = i
Stephane Barbarieec0919b2018-09-05 14:14:29 -040069 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050070 for v := range changes.KeyMap2 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040071 if _, ok := changes.KeyMap1[v]; !ok {
72 changes.AddedKeys[v] = struct{}{}
73 }
74 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050075 for v := range changes.KeyMap1 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040076 if _, ok := changes.KeyMap2[v]; !ok {
77 changes.RemovedKeys[v] = struct{}{}
78 }
79 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050080 for v := range changes.KeyMap1 {
Stephane Barbariee16186c2018-09-11 10:46:34 -040081 if _, ok := changes.KeyMap2[v]; ok && lst1[changes.KeyMap1[v]].GetHash() != lst2[changes.KeyMap2[v]].GetHash() {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040082 changes.ChangedKeys[v] = struct{}{}
83 }
84 }
85
86 return changes
87}
88
Stephane Barbariedc5022d2018-11-19 15:21:44 -050089// Merge3Way takes care of combining the revision contents of the same data set
Stephane Barbarieec0919b2018-09-05 14:14:29 -040090func Merge3Way(
npujar467fe752020-01-16 20:17:45 +053091 ctx context.Context,
Stephane Barbarieec0919b2018-09-05 14:14:29 -040092 forkRev, srcRev, dstRev Revision,
93 mergeChildFunc func(Revision) Revision,
Stephane Barbarie694e2b92018-09-07 12:17:36 -040094 dryRun bool) (rev Revision, changes []ChangeTuple) {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040095
Girish Kumarf56a4682020-03-20 20:07:46 +000096 logger.Debugw("3-way-merge-request", log.Fields{"dryRun": dryRun})
Stephane Barbarie260a5632019-02-26 16:12:49 -050097
Stephane Barbarieec0919b2018-09-05 14:14:29 -040098 var configChanged bool
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040099 var revsToDiscard []Revision
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400100
101 if dstRev.GetConfig() == forkRev.GetConfig() {
102 configChanged = dstRev.GetConfig() != srcRev.GetConfig()
103 } else {
104 if dstRev.GetConfig().Hash != srcRev.GetConfig().Hash {
Girish Kumarf56a4682020-03-20 20:07:46 +0000105 logger.Error("config-collision")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400106 }
107 configChanged = true
108 }
109
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500110 //newChildren := reflect.ValueOf(dstRev.GetAllChildren()).Interface().(map[string][]Revision)
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500111 newChildren := make(map[string][]Revision)
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500112 for entryName, childrenEntry := range dstRev.GetAllChildren() {
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500113 //newRev.Children[entryName] = append(newRev.Children[entryName], childrenEntry...)
114 newChildren[entryName] = make([]Revision, len(childrenEntry))
115 copy(newChildren[entryName], childrenEntry)
116 }
117
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400118 childrenFields := ChildrenFields(forkRev.GetData())
119
120 for fieldName, field := range childrenFields {
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500121 forkList := forkRev.GetChildren(fieldName)
122 srcList := srcRev.GetChildren(fieldName)
123 dstList := dstRev.GetChildren(fieldName)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400124
Stephane Barbariee16186c2018-09-11 10:46:34 -0400125 if revisionsAreEqual(dstList, srcList) {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400126 for _, rev := range srcList {
127 mergeChildFunc(rev)
128 }
129 continue
130 }
131
132 if field.Key == "" {
133 if revisionsAreEqual(dstList, forkList) {
134 if !revisionsAreEqual(srcList, forkList) {
Girish Kumarf56a4682020-03-20 20:07:46 +0000135 logger.Error("we should not be here")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400136 } else {
137 for _, rev := range srcList {
138 newChildren[fieldName] = append(newChildren[fieldName], mergeChildFunc(rev))
139 }
140 if field.IsContainer {
Stephane Barbarie694e2b92018-09-07 12:17:36 -0400141 changes = append(
npujar9a30c702019-11-14 17:06:39 +0530142 changes, ChangeTuple{PostListchange,
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400143 NewOperationContext("", nil, fieldName, ""), nil},
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400144 )
145 }
146 }
147 } else {
148 if !revisionsAreEqual(srcList, forkList) {
Girish Kumarf56a4682020-03-20 20:07:46 +0000149 logger.Error("cannot merge - single child node or un-keyed children list has changed")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400150 }
151 }
152 } else {
153 if revisionsAreEqual(dstList, forkList) {
154 src := newChangeAnalysis(forkList, srcList, field.Key)
155
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500156 newList := make([]Revision, len(srcList))
157 copy(newList, srcList)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400158
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500159 for key := range src.AddedKeys {
Stephane Barbariee16186c2018-09-11 10:46:34 -0400160 idx := src.KeyMap2[key]
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400161 newRev := mergeChildFunc(newList[idx])
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400162
Stephane Barbariee16186c2018-09-11 10:46:34 -0400163 // FIXME: newRev may come back as nil... exclude those entries for now
164 if newRev != nil {
165 newList[idx] = newRev
npujar9a30c702019-11-14 17:06:39 +0530166 changes = append(changes, ChangeTuple{PostAdd, newList[idx].GetData(), newRev.GetData()})
Stephane Barbariee16186c2018-09-11 10:46:34 -0400167 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400168 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500169 for key := range src.RemovedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400170 oldRev := forkList[src.KeyMap1[key]]
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400171 revsToDiscard = append(revsToDiscard, oldRev)
npujar9a30c702019-11-14 17:06:39 +0530172 changes = append(changes, ChangeTuple{PostRemove, oldRev.GetData(), nil})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400173 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500174 for key := range src.ChangedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400175 idx := src.KeyMap2[key]
176 newRev := mergeChildFunc(newList[idx])
Stephane Barbariee16186c2018-09-11 10:46:34 -0400177
178 // FIXME: newRev may come back as nil... exclude those entries for now
179 if newRev != nil {
180 newList[idx] = newRev
181 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400182 }
183
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400184 if !dryRun {
185 newChildren[fieldName] = newList
186 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400187 } else {
188 src := newChangeAnalysis(forkList, srcList, field.Key)
189 dst := newChangeAnalysis(forkList, dstList, field.Key)
190
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500191 newList := make([]Revision, len(dstList))
192 copy(newList, dstList)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400193
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500194 for key := range src.AddedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400195 if _, exists := dst.AddedKeys[key]; exists {
196 childDstRev := dstList[dst.KeyMap2[key]]
197 childSrcRev := srcList[src.KeyMap2[key]]
198 if childDstRev.GetHash() == childSrcRev.GetHash() {
199 mergeChildFunc(childDstRev)
200 } else {
Girish Kumarf56a4682020-03-20 20:07:46 +0000201 logger.Error("conflict error - revision has been added is different")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400202 }
203 } else {
204 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
205 newList = append(newList, newRev)
npujar9a30c702019-11-14 17:06:39 +0530206 changes = append(changes, ChangeTuple{PostAdd, srcList[src.KeyMap2[key]], newRev.GetData()})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400207 }
208 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500209 for key := range src.ChangedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400210 if _, removed := dst.RemovedKeys[key]; removed {
Girish Kumarf56a4682020-03-20 20:07:46 +0000211 logger.Error("conflict error - revision has been removed")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400212 } else if _, changed := dst.ChangedKeys[key]; changed {
213 childDstRev := dstList[dst.KeyMap2[key]]
214 childSrcRev := srcList[src.KeyMap2[key]]
215 if childDstRev.GetHash() == childSrcRev.GetHash() {
216 mergeChildFunc(childSrcRev)
217 } else if childDstRev.GetConfig().Hash != childSrcRev.GetConfig().Hash {
Girish Kumarf56a4682020-03-20 20:07:46 +0000218 logger.Error("conflict error - revision has been changed and is different")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400219 } else {
220 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
221 newList[dst.KeyMap2[key]] = newRev
222 }
223 } else {
224 newRev := mergeChildFunc(srcList[src.KeyMap2[key]])
225 newList[dst.KeyMap2[key]] = newRev
226 }
227 }
228
229 // TODO: how do i sort this map in reverse order?
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500230 for key := range src.RemovedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400231 if _, changed := dst.ChangedKeys[key]; changed {
Girish Kumarf56a4682020-03-20 20:07:46 +0000232 logger.Error("conflict error - revision has changed")
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400233 }
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400234 if _, removed := dst.RemovedKeys[key]; !removed {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400235 dstIdx := dst.KeyMap2[key]
236 oldRev := newList[dstIdx]
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400237 revsToDiscard = append(revsToDiscard, oldRev)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400238
239 copy(newList[dstIdx:], newList[dstIdx+1:])
240 newList[len(newList)-1] = nil
241 newList = newList[:len(newList)-1]
242
npujar9a30c702019-11-14 17:06:39 +0530243 changes = append(changes, ChangeTuple{PostRemove, oldRev.GetData(), nil})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400244 }
245 }
246
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400247 if !dryRun {
248 newChildren[fieldName] = newList
249 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400250 }
251 }
252 }
253
Stephane Barbarie260a5632019-02-26 16:12:49 -0500254 if !dryRun && len(newChildren) > 0 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400255 if configChanged {
256 rev = srcRev
257 } else {
258 rev = dstRev
259 }
260
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400261 for _, discarded := range revsToDiscard {
262 discarded.Drop("", true)
263 }
264
Stephane Barbarie260a5632019-02-26 16:12:49 -0500265 // FIXME: Do not discard the latest value for now
266 //dstRev.GetBranch().GetLatest().Drop("", configChanged)
npujar467fe752020-01-16 20:17:45 +0530267 rev = rev.UpdateAllChildren(ctx, newChildren, dstRev.GetBranch())
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400268
269 if configChanged {
npujar9a30c702019-11-14 17:06:39 +0530270 changes = append(changes, ChangeTuple{PostUpdate, dstRev.GetBranch().GetLatest().GetData(), rev.GetData()})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400271 }
272 return rev, changes
Stephane Barbariee16186c2018-09-11 10:46:34 -0400273 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500274
275 return nil, nil
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400276}