1package deb 2 3import ( 4 "fmt" 5 "sort" 6 "strings" 7 8 "github.com/aptly-dev/aptly/aptly" 9 "github.com/aptly-dev/aptly/utils" 10) 11 12// Dependency options 13const ( 14 // DepFollowSource pulls source packages when required 15 DepFollowSource = 1 << iota 16 // DepFollowSuggests pulls from suggests 17 DepFollowSuggests 18 // DepFollowRecommends pulls from recommends 19 DepFollowRecommends 20 // DepFollowAllVariants follows all variants if depends on "a | b" 21 DepFollowAllVariants 22 // DepFollowBuild pulls build dependencies 23 DepFollowBuild 24 // DepVerboseResolve emits additional logs while dependencies are being resolved 25 DepVerboseResolve 26) 27 28// PackageList is list of unique (by key) packages 29// 30// It could be seen as repo snapshot, repo contents, result of filtering, 31// merge, etc. 32// 33// If indexed, PackageList starts supporting searching 34type PackageList struct { 35 // Straight list of packages as map 36 packages map[string]*Package 37 // Indexed list of packages, sorted by name internally 38 packagesIndex []*Package 39 // Map of packages for each virtual package (provides) 40 providesIndex map[string][]*Package 41 // Package key generation function 42 keyFunc func(p *Package) string 43 // Allow duplicates? 44 duplicatesAllowed bool 45 // Has index been prepared? 46 indexed bool 47} 48 49// PackageConflictError means that package can't be added to the list due to error 50type PackageConflictError struct { 51 error 52} 53 54// Verify interface 55var ( 56 _ sort.Interface = &PackageList{} 57 _ PackageCatalog = &PackageList{} 58) 59 60func packageShortKey(p *Package) string { 61 return string(p.ShortKey("")) 62} 63 64func packageFullKey(p *Package) string { 65 return string(p.Key("")) 66} 67 68// NewPackageList creates empty package list without duplicate package 69func NewPackageList() *PackageList { 70 return NewPackageListWithDuplicates(false, 1000) 71} 72 73// NewPackageListWithDuplicates creates empty package list which might allow or block duplicate packages 74func NewPackageListWithDuplicates(duplicates bool, capacity int) *PackageList { 75 if capacity == 0 { 76 capacity = 1000 77 } 78 79 result := &PackageList{ 80 packages: make(map[string]*Package, capacity), 81 duplicatesAllowed: duplicates, 82 keyFunc: packageShortKey, 83 } 84 85 if duplicates { 86 result.keyFunc = packageFullKey 87 } 88 89 return result 90} 91 92// NewPackageListFromRefList loads packages list from PackageRefList 93func NewPackageListFromRefList(reflist *PackageRefList, collection *PackageCollection, progress aptly.Progress) (*PackageList, error) { 94 // empty reflist 95 if reflist == nil { 96 return NewPackageList(), nil 97 } 98 99 result := NewPackageListWithDuplicates(false, reflist.Len()) 100 101 if progress != nil { 102 progress.InitBar(int64(reflist.Len()), false) 103 } 104 105 err := reflist.ForEach(func(key []byte) error { 106 p, err2 := collection.ByKey(key) 107 if err2 != nil { 108 return fmt.Errorf("unable to load package with key %s: %s", key, err2) 109 } 110 if progress != nil { 111 progress.AddBar(1) 112 } 113 return result.Add(p) 114 }) 115 116 if progress != nil { 117 progress.ShutdownBar() 118 } 119 120 if err != nil { 121 return nil, err 122 } 123 124 return result, nil 125} 126 127// Has checks whether package is already in the list 128func (l *PackageList) Has(p *Package) bool { 129 key := l.keyFunc(p) 130 _, ok := l.packages[key] 131 132 return ok 133} 134 135// Add appends package to package list, additionally checking for uniqueness 136func (l *PackageList) Add(p *Package) error { 137 key := l.keyFunc(p) 138 existing, ok := l.packages[key] 139 if ok { 140 if !existing.Equals(p) { 141 return &PackageConflictError{fmt.Errorf("conflict in package %s", p)} 142 } 143 return nil 144 } 145 l.packages[key] = p 146 147 if l.indexed { 148 for _, provides := range p.Provides { 149 l.providesIndex[provides] = append(l.providesIndex[provides], p) 150 } 151 152 i := sort.Search(len(l.packagesIndex), func(j int) bool { return l.lessPackages(p, l.packagesIndex[j]) }) 153 154 // insert p into l.packagesIndex in position i 155 l.packagesIndex = append(l.packagesIndex, nil) 156 copy(l.packagesIndex[i+1:], l.packagesIndex[i:]) 157 l.packagesIndex[i] = p 158 } 159 return nil 160} 161 162// ForEach calls handler for each package in list 163func (l *PackageList) ForEach(handler func(*Package) error) error { 164 var err error 165 for _, p := range l.packages { 166 err = handler(p) 167 if err != nil { 168 return err 169 } 170 } 171 return err 172} 173 174// ForEachIndexed calls handler for each package in list in indexed order 175func (l *PackageList) ForEachIndexed(handler func(*Package) error) error { 176 if !l.indexed { 177 panic("list not indexed, can't iterate") 178 } 179 180 var err error 181 for _, p := range l.packagesIndex { 182 err = handler(p) 183 if err != nil { 184 return err 185 } 186 } 187 return err 188} 189 190// Len returns number of packages in the list 191func (l *PackageList) Len() int { 192 return len(l.packages) 193} 194 195// Append adds content from one package list to another 196func (l *PackageList) Append(pl *PackageList) error { 197 if l.indexed { 198 panic("Append not supported when indexed") 199 } 200 for k, p := range pl.packages { 201 existing, ok := l.packages[k] 202 if ok { 203 if !existing.Equals(p) { 204 return fmt.Errorf("conflict in package %s", p) 205 } 206 } else { 207 l.packages[k] = p 208 } 209 } 210 211 return nil 212} 213 214// Remove removes package from the list, and updates index when required 215func (l *PackageList) Remove(p *Package) { 216 delete(l.packages, l.keyFunc(p)) 217 if l.indexed { 218 for _, provides := range p.Provides { 219 for i, pkg := range l.providesIndex[provides] { 220 if pkg.Equals(p) { 221 // remove l.ProvidesIndex[provides][i] w/o preserving order 222 l.providesIndex[provides][len(l.providesIndex[provides])-1], l.providesIndex[provides][i], l.providesIndex[provides] = 223 nil, l.providesIndex[provides][len(l.providesIndex[provides])-1], l.providesIndex[provides][:len(l.providesIndex[provides])-1] 224 break 225 } 226 } 227 } 228 229 i := sort.Search(len(l.packagesIndex), func(j int) bool { return l.packagesIndex[j].Name >= p.Name }) 230 for i < len(l.packagesIndex) && l.packagesIndex[i].Name == p.Name { 231 if l.packagesIndex[i].Equals(p) { 232 // remove l.packagesIndex[i] preserving order 233 copy(l.packagesIndex[i:], l.packagesIndex[i+1:]) 234 l.packagesIndex[len(l.packagesIndex)-1] = nil 235 l.packagesIndex = l.packagesIndex[:len(l.packagesIndex)-1] 236 break 237 } 238 i++ 239 } 240 } 241} 242 243// Architectures returns list of architectures present in packages and flag if source packages are present. 244// 245// If includeSource is true, meta-architecture "source" would be present in the list 246func (l *PackageList) Architectures(includeSource bool) (result []string) { 247 result = make([]string, 0, 10) 248 for _, pkg := range l.packages { 249 if pkg.Architecture != ArchitectureAll && (pkg.Architecture != ArchitectureSource || includeSource) && !utils.StrSliceHasItem(result, pkg.Architecture) { 250 result = append(result, pkg.Architecture) 251 } 252 } 253 return 254} 255 256// Strings builds list of strings with package keys 257func (l *PackageList) Strings() []string { 258 result := make([]string, l.Len()) 259 i := 0 260 261 for _, p := range l.packages { 262 result[i] = string(p.Key("")) 263 i++ 264 } 265 266 return result 267} 268 269// depSliceDeduplicate removes dups in slice of Dependencies 270func depSliceDeduplicate(s []Dependency) []Dependency { 271 l := len(s) 272 if l < 2 { 273 return s 274 } 275 if l == 2 { 276 if s[0] == s[1] { 277 return s[0:1] 278 } 279 return s 280 } 281 282 found := make(map[string]bool, l) 283 j := 0 284 for i, x := range s { 285 h := x.Hash() 286 if !found[h] { 287 found[h] = true 288 s[j] = s[i] 289 j++ 290 } 291 } 292 293 return s[:j] 294} 295 296// VerifyDependencies looks for missing dependencies in package list. 297// 298// Analysis would be performed for each architecture, in specified sources 299func (l *PackageList) VerifyDependencies(options int, architectures []string, sources *PackageList, progress aptly.Progress) ([]Dependency, error) { 300 l.PrepareIndex() 301 missing := make([]Dependency, 0, 128) 302 303 if progress != nil { 304 progress.InitBar(int64(l.Len())*int64(len(architectures)), false) 305 } 306 307 for _, arch := range architectures { 308 cache := make(map[string]bool, 2048) 309 310 for _, p := range l.packagesIndex { 311 if progress != nil { 312 progress.AddBar(1) 313 } 314 315 if !p.MatchesArchitecture(arch) { 316 continue 317 } 318 319 for _, dep := range p.GetDependencies(options) { 320 variants, err := ParseDependencyVariants(dep) 321 if err != nil { 322 return nil, fmt.Errorf("unable to process package %s: %s", p, err) 323 } 324 325 variants = depSliceDeduplicate(variants) 326 327 variantsMissing := make([]Dependency, 0, len(variants)) 328 329 for _, dep := range variants { 330 if dep.Architecture == "" { 331 dep.Architecture = arch 332 } 333 334 hash := dep.Hash() 335 satisfied, ok := cache[hash] 336 if !ok { 337 satisfied = sources.Search(dep, false) != nil 338 cache[hash] = satisfied 339 } 340 341 if !satisfied && !ok { 342 variantsMissing = append(variantsMissing, dep) 343 } 344 345 if satisfied && options&DepFollowAllVariants == 0 { 346 variantsMissing = nil 347 break 348 } 349 } 350 351 missing = append(missing, variantsMissing...) 352 } 353 } 354 } 355 356 if progress != nil { 357 progress.ShutdownBar() 358 } 359 360 if options&DepVerboseResolve == DepVerboseResolve && progress != nil { 361 missingStr := make([]string, len(missing)) 362 for i := range missing { 363 missingStr[i] = missing[i].String() 364 } 365 progress.ColoredPrintf("@{y}Missing dependencies:@| %s", strings.Join(missingStr, ", ")) 366 } 367 368 return missing, nil 369} 370 371// Swap swaps two packages in index 372func (l *PackageList) Swap(i, j int) { 373 l.packagesIndex[i], l.packagesIndex[j] = l.packagesIndex[j], l.packagesIndex[i] 374} 375 376func (l *PackageList) lessPackages(iPkg, jPkg *Package) bool { 377 if iPkg.Name == jPkg.Name { 378 cmp := CompareVersions(iPkg.Version, jPkg.Version) 379 if cmp == 0 { 380 return iPkg.Architecture < jPkg.Architecture 381 } 382 return cmp == 1 383 } 384 385 return iPkg.Name < jPkg.Name 386} 387 388// Less compares two packages by name (lexographical) and version (latest to oldest) 389func (l *PackageList) Less(i, j int) bool { 390 return l.lessPackages(l.packagesIndex[i], l.packagesIndex[j]) 391} 392 393// PrepareIndex prepares list for indexing 394func (l *PackageList) PrepareIndex() { 395 if l.indexed { 396 return 397 } 398 399 l.packagesIndex = make([]*Package, l.Len()) 400 l.providesIndex = make(map[string][]*Package, 128) 401 402 i := 0 403 for _, p := range l.packages { 404 l.packagesIndex[i] = p 405 i++ 406 407 for _, provides := range p.Provides { 408 l.providesIndex[provides] = append(l.providesIndex[provides], p) 409 } 410 } 411 412 sort.Sort(l) 413 414 l.indexed = true 415} 416 417// Scan searches package index using full scan 418func (l *PackageList) Scan(q PackageQuery) (result *PackageList) { 419 result = NewPackageListWithDuplicates(l.duplicatesAllowed, 0) 420 for _, pkg := range l.packages { 421 if q.Matches(pkg) { 422 result.Add(pkg) 423 } 424 } 425 426 return 427} 428 429// SearchSupported returns true for PackageList 430func (l *PackageList) SearchSupported() bool { 431 return true 432} 433 434// SearchByKey looks up package by exact key reference 435func (l *PackageList) SearchByKey(arch, name, version string) (result *PackageList) { 436 result = NewPackageListWithDuplicates(l.duplicatesAllowed, 0) 437 438 pkg := l.packages["P"+arch+" "+name+" "+version] 439 if pkg != nil { 440 result.Add(pkg) 441 } 442 443 return 444} 445 446// Search searches package index for specified package(s) using optimized queries 447func (l *PackageList) Search(dep Dependency, allMatches bool) (searchResults []*Package) { 448 if !l.indexed { 449 panic("list not indexed, can't search") 450 } 451 452 i := sort.Search(len(l.packagesIndex), func(j int) bool { return l.packagesIndex[j].Name >= dep.Pkg }) 453 454 for i < len(l.packagesIndex) && l.packagesIndex[i].Name == dep.Pkg { 455 p := l.packagesIndex[i] 456 if p.MatchesDependency(dep) { 457 searchResults = append(searchResults, p) 458 459 if !allMatches { 460 break 461 } 462 } 463 464 i++ 465 } 466 467 if dep.Relation == VersionDontCare { 468 for _, p := range l.providesIndex[dep.Pkg] { 469 if dep.Architecture == "" || p.MatchesArchitecture(dep.Architecture) { 470 searchResults = append(searchResults, p) 471 472 if !allMatches { 473 break 474 } 475 } 476 } 477 } 478 479 return 480} 481 482// Filter filters package index by specified queries (ORed together), possibly pulling dependencies 483func (l *PackageList) Filter(queries []PackageQuery, withDependencies bool, source *PackageList, dependencyOptions int, architecturesList []string) (*PackageList, error) { 484 return l.FilterWithProgress(queries, withDependencies, source, dependencyOptions, architecturesList, nil) 485} 486 487// FilterWithProgress filters package index by specified queries (ORed together), possibly pulling dependencies and displays progress 488func (l *PackageList) FilterWithProgress(queries []PackageQuery, withDependencies bool, source *PackageList, dependencyOptions int, architecturesList []string, progress aptly.Progress) (*PackageList, error) { 489 if !l.indexed { 490 panic("list not indexed, can't filter") 491 } 492 493 result := NewPackageList() 494 495 for _, query := range queries { 496 result.Append(query.Query(l)) 497 } 498 499 if withDependencies { 500 added := result.Len() 501 result.PrepareIndex() 502 503 dependencySource := NewPackageList() 504 if source != nil { 505 dependencySource.Append(source) 506 } 507 dependencySource.Append(result) 508 dependencySource.PrepareIndex() 509 510 // while some new dependencies were discovered 511 for added > 0 { 512 added = 0 513 514 // find missing dependencies 515 missing, err := result.VerifyDependencies(dependencyOptions, architecturesList, dependencySource, progress) 516 if err != nil { 517 return nil, err 518 } 519 520 // try to satisfy dependencies 521 for _, dep := range missing { 522 if dependencyOptions&DepFollowAllVariants == 0 { 523 // dependency might have already been satisfied 524 // with packages already been added 525 // 526 // when follow-all-variants is enabled, we need to try to expand anyway, 527 // as even if dependency is satisfied now, there might be other ways to satisfy dependency 528 if result.Search(dep, false) != nil { 529 if dependencyOptions&DepVerboseResolve == DepVerboseResolve && progress != nil { 530 progress.ColoredPrintf("@{y}Already satisfied dependency@|: %s with %s", &dep, result.Search(dep, true)) 531 } 532 continue 533 } 534 } 535 536 searchResults := l.Search(dep, true) 537 if len(searchResults) > 0 { 538 for _, p := range searchResults { 539 if result.Has(p) { 540 continue 541 } 542 543 if dependencyOptions&DepVerboseResolve == DepVerboseResolve && progress != nil { 544 progress.ColoredPrintf("@{g}Injecting package@|: %s", p) 545 } 546 result.Add(p) 547 dependencySource.Add(p) 548 added++ 549 if dependencyOptions&DepFollowAllVariants == 0 { 550 break 551 } 552 } 553 } else { 554 if dependencyOptions&DepVerboseResolve == DepVerboseResolve && progress != nil { 555 progress.ColoredPrintf("@{r}Unsatisfied dependency@|: %s", dep.String()) 556 } 557 558 } 559 } 560 } 561 } 562 563 return result, nil 564} 565