blob: c59dda434a4f6a10904b89d941c264c01a59afca [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 (
20 "github.com/opencord/voltha-go/common/log"
Stephane Barbarieec0919b2018-09-05 14:14:29 -040021)
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 {
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040043 KeyMap1 map[string]int
44 KeyMap2 map[string]int
45 AddedKeys map[string]struct{}
46 RemovedKeys map[string]struct{}
47 ChangedKeys map[string]struct{}
Stephane Barbarieec0919b2018-09-05 14:14:29 -040048}
49
50func newChangeAnalysis(lst1, lst2 []Revision, keyName string) *changeAnalysis {
51 changes := &changeAnalysis{}
52
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040053 changes.KeyMap1 = make(map[string]int)
54 changes.KeyMap2 = make(map[string]int)
Stephane Barbarieec0919b2018-09-05 14:14:29 -040055
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040056 changes.AddedKeys = make(map[string]struct{})
57 changes.RemovedKeys = make(map[string]struct{})
58 changes.ChangedKeys = make(map[string]struct{})
Stephane Barbarieec0919b2018-09-05 14:14:29 -040059
60 for i, rev := range lst1 {
61 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040062 changes.KeyMap1[v.String()] = i
Stephane Barbarieec0919b2018-09-05 14:14:29 -040063 }
64 for i, rev := range lst2 {
65 _, v := GetAttributeValue(rev.GetData(), keyName, 0)
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040066 changes.KeyMap2[v.String()] = i
Stephane Barbarieec0919b2018-09-05 14:14:29 -040067 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050068 for v := range changes.KeyMap2 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040069 if _, ok := changes.KeyMap1[v]; !ok {
70 changes.AddedKeys[v] = struct{}{}
71 }
72 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050073 for v := range changes.KeyMap1 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040074 if _, ok := changes.KeyMap2[v]; !ok {
75 changes.RemovedKeys[v] = struct{}{}
76 }
77 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -050078 for v := range changes.KeyMap1 {
Stephane Barbariee16186c2018-09-11 10:46:34 -040079 if _, ok := changes.KeyMap2[v]; ok && lst1[changes.KeyMap1[v]].GetHash() != lst2[changes.KeyMap2[v]].GetHash() {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040080 changes.ChangedKeys[v] = struct{}{}
81 }
82 }
83
84 return changes
85}
86
Stephane Barbariedc5022d2018-11-19 15:21:44 -050087// Merge3Way takes care of combining the revision contents of the same data set
Stephane Barbarieec0919b2018-09-05 14:14:29 -040088func Merge3Way(
89 forkRev, srcRev, dstRev Revision,
90 mergeChildFunc func(Revision) Revision,
Stephane Barbarie694e2b92018-09-07 12:17:36 -040091 dryRun bool) (rev Revision, changes []ChangeTuple) {
Stephane Barbarieec0919b2018-09-05 14:14:29 -040092
Stephane Barbarie260a5632019-02-26 16:12:49 -050093 log.Debugw("3-way-merge-request", log.Fields{"dryRun": dryRun})
94
Stephane Barbarieec0919b2018-09-05 14:14:29 -040095 var configChanged bool
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -040096 var revsToDiscard []Revision
Stephane Barbarieec0919b2018-09-05 14:14:29 -040097
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
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500107 //newChildren := reflect.ValueOf(dstRev.GetAllChildren()).Interface().(map[string][]Revision)
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500108 newChildren := make(map[string][]Revision)
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500109 for entryName, childrenEntry := range dstRev.GetAllChildren() {
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500110 //newRev.Children[entryName] = append(newRev.Children[entryName], childrenEntry...)
111 newChildren[entryName] = make([]Revision, len(childrenEntry))
112 copy(newChildren[entryName], childrenEntry)
113 }
114
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400115 childrenFields := ChildrenFields(forkRev.GetData())
116
117 for fieldName, field := range childrenFields {
Stephane Barbarie3cb01222019-01-16 17:15:56 -0500118 forkList := forkRev.GetChildren(fieldName)
119 srcList := srcRev.GetChildren(fieldName)
120 dstList := dstRev.GetChildren(fieldName)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400121
Stephane Barbariee16186c2018-09-11 10:46:34 -0400122 if revisionsAreEqual(dstList, srcList) {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400123 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 {
Stephane Barbarie694e2b92018-09-07 12:17:36 -0400138 changes = append(
139 changes, ChangeTuple{POST_LISTCHANGE,
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400140 NewOperationContext("", nil, fieldName, ""), nil},
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400141 )
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
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500153 newList := make([]Revision, len(srcList))
154 copy(newList, srcList)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400155
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500156 for key := range src.AddedKeys {
Stephane Barbariee16186c2018-09-11 10:46:34 -0400157 idx := src.KeyMap2[key]
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400158 newRev := mergeChildFunc(newList[idx])
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400159
Stephane Barbariee16186c2018-09-11 10:46:34 -0400160 // FIXME: newRev may come back as nil... exclude those entries for now
161 if newRev != nil {
162 newList[idx] = newRev
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400163 changes = append(changes, ChangeTuple{POST_ADD, newList[idx].GetData(), newRev.GetData()})
Stephane Barbariee16186c2018-09-11 10:46:34 -0400164 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400165 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500166 for key := range src.RemovedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400167 oldRev := forkList[src.KeyMap1[key]]
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400168 revsToDiscard = append(revsToDiscard, oldRev)
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400169 changes = append(changes, ChangeTuple{POST_REMOVE, oldRev.GetData(), nil})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400170 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500171 for key := range src.ChangedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400172 idx := src.KeyMap2[key]
173 newRev := mergeChildFunc(newList[idx])
Stephane Barbariee16186c2018-09-11 10:46:34 -0400174
175 // FIXME: newRev may come back as nil... exclude those entries for now
176 if newRev != nil {
177 newList[idx] = newRev
178 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400179 }
180
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400181 if !dryRun {
182 newChildren[fieldName] = newList
183 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400184 } else {
185 src := newChangeAnalysis(forkList, srcList, field.Key)
186 dst := newChangeAnalysis(forkList, dstList, field.Key)
187
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500188 newList := make([]Revision, len(dstList))
189 copy(newList, dstList)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400190
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500191 for key := range src.AddedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400192 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)
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400203 changes = append(changes, ChangeTuple{POST_ADD, srcList[src.KeyMap2[key]], newRev.GetData()})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400204 }
205 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500206 for key := range src.ChangedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400207 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?
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500227 for key := range src.RemovedKeys {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400228 if _, changed := dst.ChangedKeys[key]; changed {
229 log.Error("conflict error - revision has changed")
230 }
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400231 if _, removed := dst.RemovedKeys[key]; !removed {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400232 dstIdx := dst.KeyMap2[key]
233 oldRev := newList[dstIdx]
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400234 revsToDiscard = append(revsToDiscard, oldRev)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400235
236 copy(newList[dstIdx:], newList[dstIdx+1:])
237 newList[len(newList)-1] = nil
238 newList = newList[:len(newList)-1]
239
Stephane Barbarie8c48b5c2018-10-02 09:45:17 -0400240 changes = append(changes, ChangeTuple{POST_REMOVE, oldRev.GetData(), nil})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400241 }
242 }
243
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400244 if !dryRun {
245 newChildren[fieldName] = newList
246 }
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400247 }
248 }
249 }
250
Stephane Barbarie260a5632019-02-26 16:12:49 -0500251 if !dryRun && len(newChildren) > 0 {
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400252 if configChanged {
253 rev = srcRev
254 } else {
255 rev = dstRev
256 }
257
Stephane Barbarie88fbe7f2018-09-25 12:25:23 -0400258 for _, discarded := range revsToDiscard {
259 discarded.Drop("", true)
260 }
261
Stephane Barbarie260a5632019-02-26 16:12:49 -0500262 // FIXME: Do not discard the latest value for now
263 //dstRev.GetBranch().GetLatest().Drop("", configChanged)
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400264 rev = rev.UpdateAllChildren(newChildren, dstRev.GetBranch())
265
266 if configChanged {
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500267 changes = append(changes, ChangeTuple{POST_UPDATE, dstRev.GetBranch().GetLatest().GetData(), rev.GetData()})
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400268 }
269 return rev, changes
Stephane Barbariee16186c2018-09-11 10:46:34 -0400270 }
Stephane Barbariedc5022d2018-11-19 15:21:44 -0500271
272 return nil, nil
Stephane Barbarieec0919b2018-09-05 14:14:29 -0400273}