1package deb 2 3import ( 4 "bytes" 5 "encoding/json" 6 "sort" 7 8 "github.com/AlekSi/pointer" 9 "github.com/ugorji/go/codec" 10) 11 12// PackageRefList is a list of keys of packages, this is basis for snapshot 13// and similar stuff 14// 15// Refs are sorted in lexicographical order 16type PackageRefList struct { 17 // List of package keys 18 Refs [][]byte 19} 20 21// Verify interface 22var ( 23 _ sort.Interface = &PackageRefList{} 24) 25 26// NewPackageRefList creates empty PackageRefList 27func NewPackageRefList() *PackageRefList { 28 return &PackageRefList{} 29} 30 31// NewPackageRefListFromPackageList creates PackageRefList from PackageList 32func NewPackageRefListFromPackageList(list *PackageList) *PackageRefList { 33 reflist := &PackageRefList{} 34 reflist.Refs = make([][]byte, list.Len()) 35 36 i := 0 37 for _, p := range list.packages { 38 reflist.Refs[i] = p.Key("") 39 i++ 40 } 41 42 sort.Sort(reflist) 43 44 return reflist 45} 46 47// Len returns number of refs 48func (l *PackageRefList) Len() int { 49 return len(l.Refs) 50} 51 52// Swap swaps two refs 53func (l *PackageRefList) Swap(i, j int) { 54 l.Refs[i], l.Refs[j] = l.Refs[j], l.Refs[i] 55} 56 57// Compare compares two refs in lexographical order 58func (l *PackageRefList) Less(i, j int) bool { 59 return bytes.Compare(l.Refs[i], l.Refs[j]) < 0 60} 61 62// Encode does msgpack encoding of PackageRefList 63func (l *PackageRefList) Encode() []byte { 64 var buf bytes.Buffer 65 66 encoder := codec.NewEncoder(&buf, &codec.MsgpackHandle{}) 67 encoder.Encode(l) 68 69 return buf.Bytes() 70} 71 72// Decode decodes msgpack representation into PackageRefLit 73func (l *PackageRefList) Decode(input []byte) error { 74 decoder := codec.NewDecoderBytes(input, &codec.MsgpackHandle{}) 75 return decoder.Decode(l) 76} 77 78// ForEach calls handler for each package ref in list 79func (l *PackageRefList) ForEach(handler func([]byte) error) error { 80 var err error 81 for _, p := range l.Refs { 82 err = handler(p) 83 if err != nil { 84 return err 85 } 86 } 87 return err 88} 89 90// Has checks whether package is part of reflist 91func (l *PackageRefList) Has(p *Package) bool { 92 key := p.Key("") 93 94 i := sort.Search(len(l.Refs), func(j int) bool { return bytes.Compare(l.Refs[j], key) >= 0 }) 95 return i < len(l.Refs) && bytes.Equal(l.Refs[i], key) 96} 97 98// Strings builds list of strings with package keys 99func (l *PackageRefList) Strings() []string { 100 if l == nil { 101 return []string{} 102 } 103 104 result := make([]string, l.Len()) 105 106 for i := 0; i < l.Len(); i++ { 107 result[i] = string(l.Refs[i]) 108 } 109 110 return result 111} 112 113// Subtract returns all packages in l that are not in r 114func (l *PackageRefList) Subtract(r *PackageRefList) *PackageRefList { 115 result := &PackageRefList{Refs: make([][]byte, 0, 128)} 116 117 // pointer to left and right reflists 118 il, ir := 0, 0 119 // length of reflists 120 ll, lr := l.Len(), r.Len() 121 122 for il < ll || ir < lr { 123 if il == ll { 124 // left list exhausted, we got the result 125 break 126 } 127 if ir == lr { 128 // right list exhausted, append what is left to result 129 result.Refs = append(result.Refs, l.Refs[il:]...) 130 break 131 } 132 133 rel := bytes.Compare(l.Refs[il], r.Refs[ir]) 134 if rel == 0 { 135 // r contains entry from l, so we skip it 136 il++ 137 ir++ 138 } else if rel < 0 { 139 // item il is not in r, append 140 result.Refs = append(result.Refs, l.Refs[il]) 141 il++ 142 } else { 143 // skip over to next item in r 144 ir++ 145 } 146 } 147 148 return result 149} 150 151// PackageDiff is a difference between two packages in a list. 152// 153// If left & right are present, difference is in package version 154// If left is nil, package is present only in right 155// If right is nil, package is present only in left 156type PackageDiff struct { 157 Left, Right *Package 158} 159 160// Check interface 161var ( 162 _ json.Marshaler = PackageDiff{} 163) 164 165// MarshalJSON implements json.Marshaler interface 166func (d PackageDiff) MarshalJSON() ([]byte, error) { 167 serialized := struct { 168 Left, Right *string 169 }{} 170 171 if d.Left != nil { 172 serialized.Left = pointer.ToString(string(d.Left.Key(""))) 173 } 174 if d.Right != nil { 175 serialized.Right = pointer.ToString(string(d.Right.Key(""))) 176 } 177 178 return json.Marshal(serialized) 179} 180 181// PackageDiffs is a list of PackageDiff records 182type PackageDiffs []PackageDiff 183 184// Diff calculates difference between two reflists 185func (l *PackageRefList) Diff(r *PackageRefList, packageCollection *PackageCollection) (result PackageDiffs, err error) { 186 result = make(PackageDiffs, 0, 128) 187 188 // pointer to left and right reflists 189 il, ir := 0, 0 190 // length of reflists 191 ll, lr := l.Len(), r.Len() 192 // cached loaded packages on the left & right 193 pl, pr := (*Package)(nil), (*Package)(nil) 194 195 // until we reached end of both lists 196 for il < ll || ir < lr { 197 // if we've exhausted left list, pull the rest from the right 198 if il == ll { 199 pr, err = packageCollection.ByKey(r.Refs[ir]) 200 if err != nil { 201 return nil, err 202 } 203 result = append(result, PackageDiff{Left: nil, Right: pr}) 204 ir++ 205 continue 206 } 207 // if we've exhausted right list, pull the rest from the left 208 if ir == lr { 209 pl, err = packageCollection.ByKey(l.Refs[il]) 210 if err != nil { 211 return nil, err 212 } 213 result = append(result, PackageDiff{Left: pl, Right: nil}) 214 il++ 215 continue 216 } 217 218 // refs on both sides are present, load them 219 rl, rr := l.Refs[il], r.Refs[ir] 220 // compare refs 221 rel := bytes.Compare(rl, rr) 222 223 if rel == 0 { 224 // refs are identical, so are packages, advance pointer 225 il++ 226 ir++ 227 pl, pr = nil, nil 228 } else { 229 // load pl & pr if they haven't been loaded before 230 if pl == nil { 231 pl, err = packageCollection.ByKey(rl) 232 if err != nil { 233 return nil, err 234 } 235 } 236 237 if pr == nil { 238 pr, err = packageCollection.ByKey(rr) 239 if err != nil { 240 return nil, err 241 } 242 } 243 244 // otherwise pl or pr is missing on one of the sides 245 if rel < 0 { 246 // compaction: +(,A) -(B,) --> !(A,B) 247 if len(result) > 0 && result[len(result)-1].Left == nil && result[len(result)-1].Right.Name == pl.Name && 248 result[len(result)-1].Right.Architecture == pl.Architecture { 249 result[len(result)-1] = PackageDiff{Left: pl, Right: result[len(result)-1].Right} 250 } else { 251 result = append(result, PackageDiff{Left: pl, Right: nil}) 252 } 253 il++ 254 pl = nil 255 } else { 256 // compaction: -(A,) +(,B) --> !(A,B) 257 if len(result) > 0 && result[len(result)-1].Right == nil && result[len(result)-1].Left.Name == pr.Name && 258 result[len(result)-1].Left.Architecture == pr.Architecture { 259 result[len(result)-1] = PackageDiff{Left: result[len(result)-1].Left, Right: pr} 260 } else { 261 result = append(result, PackageDiff{Left: nil, Right: pr}) 262 } 263 ir++ 264 pr = nil 265 } 266 } 267 } 268 269 return 270} 271 272// Merge merges reflist r into current reflist. If overrideMatching, merge 273// replaces matching packages (by architecture/name) with reference from r. 274// If ignoreConflicting is set, all packages are preserved, otherwise conflicting 275// packages are overwritten with packages from "right" snapshot. 276func (l *PackageRefList) Merge(r *PackageRefList, overrideMatching, ignoreConflicting bool) (result *PackageRefList) { 277 var overriddenArch, overridenName []byte 278 279 // pointer to left and right reflists 280 il, ir := 0, 0 281 // length of reflists 282 ll, lr := l.Len(), r.Len() 283 284 result = &PackageRefList{} 285 result.Refs = make([][]byte, 0, ll+lr) 286 287 // until we reached end of both lists 288 for il < ll || ir < lr { 289 // if we've exhausted left list, pull the rest from the right 290 if il == ll { 291 result.Refs = append(result.Refs, r.Refs[ir:]...) 292 break 293 } 294 // if we've exhausted right list, pull the rest from the left 295 if ir == lr { 296 result.Refs = append(result.Refs, l.Refs[il:]...) 297 break 298 } 299 300 // refs on both sides are present, load them 301 rl, rr := l.Refs[il], r.Refs[ir] 302 // compare refs 303 rel := bytes.Compare(rl, rr) 304 305 if rel == 0 { 306 // refs are identical, so are packages, advance pointer 307 result.Refs = append(result.Refs, l.Refs[il]) 308 il++ 309 ir++ 310 overridenName = nil 311 overriddenArch = nil 312 } else { 313 partsL := bytes.Split(rl, []byte(" ")) 314 archL, nameL, versionL := partsL[0][1:], partsL[1], partsL[2] 315 316 partsR := bytes.Split(rr, []byte(" ")) 317 archR, nameR, versionR := partsR[0][1:], partsR[1], partsR[2] 318 319 if !ignoreConflicting && bytes.Equal(archL, archR) && bytes.Equal(nameL, nameR) && bytes.Equal(versionL, versionR) { 320 // conflicting duplicates with same arch, name, version, but different file hash 321 result.Refs = append(result.Refs, r.Refs[ir]) 322 il++ 323 ir++ 324 overridenName = nil 325 overriddenArch = nil 326 continue 327 } 328 329 if overrideMatching { 330 if bytes.Equal(archL, overriddenArch) && bytes.Equal(nameL, overridenName) { 331 // this package has already been overridden on the right 332 il++ 333 continue 334 } 335 336 if bytes.Equal(archL, archR) && bytes.Equal(nameL, nameR) { 337 // override with package from the right 338 result.Refs = append(result.Refs, r.Refs[ir]) 339 il++ 340 ir++ 341 overriddenArch = archL 342 overridenName = nameL 343 continue 344 } 345 } 346 347 // otherwise append smallest of two 348 if rel < 0 { 349 result.Refs = append(result.Refs, l.Refs[il]) 350 il++ 351 } else { 352 result.Refs = append(result.Refs, r.Refs[ir]) 353 ir++ 354 overridenName = nil 355 overriddenArch = nil 356 } 357 } 358 } 359 360 return 361} 362 363// FilterLatestRefs takes in a reflist with potentially multiples of the same 364// packages and reduces it to only the latest of each package. The operations 365// are done in-place. This implements a "latest wins" approach which can be used 366// while merging two or more snapshots together. 367func (l *PackageRefList) FilterLatestRefs() { 368 var ( 369 lastArch, lastName, lastVer []byte 370 arch, name, ver []byte 371 parts [][]byte 372 ) 373 374 for i := 0; i < len(l.Refs); i++ { 375 parts = bytes.Split(l.Refs[i][1:], []byte(" ")) 376 arch, name, ver = parts[0], parts[1], parts[2] 377 378 if bytes.Equal(arch, lastArch) && bytes.Equal(name, lastName) { 379 // Two packages are identical, check version and only one wins 380 vres := CompareVersions(string(ver), string(lastVer)) 381 382 // Remove the older refs from the result 383 if vres > 0 { 384 // ver[i] > ver[i-1], remove element i-1 385 l.Refs = append(l.Refs[:i-1], l.Refs[i:]...) 386 } else { 387 // ver[i] < ver[i-1], remove element i 388 l.Refs = append(l.Refs[:i], l.Refs[i+1:]...) 389 arch, name, ver = lastArch, lastName, lastVer 390 } 391 392 // Compensate for the reduced set 393 i-- 394 } 395 396 lastArch, lastName, lastVer = arch, name, ver 397 } 398} 399