1 // Copyright 2021 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Package slices defines various functions useful with slices of any type. 6 package slices 7 8 import ( 9 "unsafe" 10 11 "cuelabs.dev/go/oci/ociregistry/internal/exp/constraints" 12 ) 13 14 // Equal reports whether two slices are equal: the same length and all 15 // elements equal. If the lengths are different, Equal returns false. 16 // Otherwise, the elements are compared in increasing index order, and the 17 // comparison stops at the first unequal pair. 18 // Floating point NaNs are not considered equal. 19 func Equal[S ~[]E, E comparable](s1, s2 S) bool { 20 if len(s1) != len(s2) { 21 return false 22 } 23 for i := range s1 { 24 if s1[i] != s2[i] { 25 return false 26 } 27 } 28 return true 29 } 30 31 // EqualFunc reports whether two slices are equal using an equality 32 // function on each pair of elements. If the lengths are different, 33 // EqualFunc returns false. Otherwise, the elements are compared in 34 // increasing index order, and the comparison stops at the first index 35 // for which eq returns false. 36 func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool { 37 if len(s1) != len(s2) { 38 return false 39 } 40 for i, v1 := range s1 { 41 v2 := s2[i] 42 if !eq(v1, v2) { 43 return false 44 } 45 } 46 return true 47 } 48 49 // Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair 50 // of elements. The elements are compared sequentially, starting at index 0, 51 // until one element is not equal to the other. 52 // The result of comparing the first non-matching elements is returned. 53 // If both slices are equal until one of them ends, the shorter slice is 54 // considered less than the longer one. 55 // The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2. 56 func Compare[S ~[]E, E constraints.Ordered](s1, s2 S) int { 57 for i, v1 := range s1 { 58 if i >= len(s2) { 59 return +1 60 } 61 v2 := s2[i] 62 if c := cmpCompare(v1, v2); c != 0 { 63 return c 64 } 65 } 66 if len(s1) < len(s2) { 67 return -1 68 } 69 return 0 70 } 71 72 // CompareFunc is like [Compare] but uses a custom comparison function on each 73 // pair of elements. 74 // The result is the first non-zero result of cmp; if cmp always 75 // returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), 76 // and +1 if len(s1) > len(s2). 77 func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int { 78 for i, v1 := range s1 { 79 if i >= len(s2) { 80 return +1 81 } 82 v2 := s2[i] 83 if c := cmp(v1, v2); c != 0 { 84 return c 85 } 86 } 87 if len(s1) < len(s2) { 88 return -1 89 } 90 return 0 91 } 92 93 // Index returns the index of the first occurrence of v in s, 94 // or -1 if not present. 95 func Index[S ~[]E, E comparable](s S, v E) int { 96 for i := range s { 97 if v == s[i] { 98 return i 99 } 100 } 101 return -1 102 } 103 104 // IndexFunc returns the first index i satisfying f(s[i]), 105 // or -1 if none do. 106 func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int { 107 for i := range s { 108 if f(s[i]) { 109 return i 110 } 111 } 112 return -1 113 } 114 115 // Contains reports whether v is present in s. 116 func Contains[S ~[]E, E comparable](s S, v E) bool { 117 return Index(s, v) >= 0 118 } 119 120 // ContainsFunc reports whether at least one 121 // element e of s satisfies f(e). 122 func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool { 123 return IndexFunc(s, f) >= 0 124 } 125 126 // Insert inserts the values v... into s at index i, 127 // returning the modified slice. 128 // The elements at s[i:] are shifted up to make room. 129 // In the returned slice r, r[i] == v[0], 130 // and r[i+len(v)] == value originally at r[i]. 131 // Insert panics if i is out of range. 132 // This function is O(len(s) + len(v)). 133 func Insert[S ~[]E, E any](s S, i int, v ...E) S { 134 m := len(v) 135 if m == 0 { 136 return s 137 } 138 n := len(s) 139 if i == n { 140 return append(s, v...) 141 } 142 if n+m > cap(s) { 143 // Use append rather than make so that we bump the size of 144 // the slice up to the next storage class. 145 // This is what Grow does but we don't call Grow because 146 // that might copy the values twice. 147 s2 := append(s[:i], make(S, n+m-i)...) 148 copy(s2[i:], v) 149 copy(s2[i+m:], s[i:]) 150 return s2 151 } 152 s = s[:n+m] 153 154 // before: 155 // s: aaaaaaaabbbbccccccccdddd 156 // ^ ^ ^ ^ 157 // i i+m n n+m 158 // after: 159 // s: aaaaaaaavvvvbbbbcccccccc 160 // ^ ^ ^ ^ 161 // i i+m n n+m 162 // 163 // a are the values that don't move in s. 164 // v are the values copied in from v. 165 // b and c are the values from s that are shifted up in index. 166 // d are the values that get overwritten, never to be seen again. 167 168 if !overlaps(v, s[i+m:]) { 169 // Easy case - v does not overlap either the c or d regions. 170 // (It might be in some of a or b, or elsewhere entirely.) 171 // The data we copy up doesn't write to v at all, so just do it. 172 173 copy(s[i+m:], s[i:]) 174 175 // Now we have 176 // s: aaaaaaaabbbbbbbbcccccccc 177 // ^ ^ ^ ^ 178 // i i+m n n+m 179 // Note the b values are duplicated. 180 181 copy(s[i:], v) 182 183 // Now we have 184 // s: aaaaaaaavvvvbbbbcccccccc 185 // ^ ^ ^ ^ 186 // i i+m n n+m 187 // That's the result we want. 188 return s 189 } 190 191 // The hard case - v overlaps c or d. We can't just shift up 192 // the data because we'd move or clobber the values we're trying 193 // to insert. 194 // So instead, write v on top of d, then rotate. 195 copy(s[n:], v) 196 197 // Now we have 198 // s: aaaaaaaabbbbccccccccvvvv 199 // ^ ^ ^ ^ 200 // i i+m n n+m 201 202 rotateRight(s[i:], m) 203 204 // Now we have 205 // s: aaaaaaaavvvvbbbbcccccccc 206 // ^ ^ ^ ^ 207 // i i+m n n+m 208 // That's the result we want. 209 return s 210 } 211 212 // Delete removes the elements s[i:j] from s, returning the modified slice. 213 // Delete panics if s[i:j] is not a valid slice of s. 214 // Delete is O(len(s)-j), so if many items must be deleted, it is better to 215 // make a single call deleting them all together than to delete one at a time. 216 // Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those 217 // elements contain pointers you might consider zeroing those elements so that 218 // objects they reference can be garbage collected. 219 func Delete[S ~[]E, E any](s S, i, j int) S { 220 _ = s[i:j] // bounds check 221 222 return append(s[:i], s[j:]...) 223 } 224 225 // DeleteFunc removes any elements from s for which del returns true, 226 // returning the modified slice. 227 // When DeleteFunc removes m elements, it might not modify the elements 228 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider 229 // zeroing those elements so that objects they reference can be garbage 230 // collected. 231 func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S { 232 i := IndexFunc(s, del) 233 if i == -1 { 234 return s 235 } 236 // Don't start copying elements until we find one to delete. 237 for j := i + 1; j < len(s); j++ { 238 if v := s[j]; !del(v) { 239 s[i] = v 240 i++ 241 } 242 } 243 return s[:i] 244 } 245 246 // Replace replaces the elements s[i:j] by the given v, and returns the 247 // modified slice. Replace panics if s[i:j] is not a valid slice of s. 248 func Replace[S ~[]E, E any](s S, i, j int, v ...E) S { 249 _ = s[i:j] // verify that i:j is a valid subslice 250 251 if i == j { 252 return Insert(s, i, v...) 253 } 254 if j == len(s) { 255 return append(s[:i], v...) 256 } 257 258 tot := len(s[:i]) + len(v) + len(s[j:]) 259 if tot > cap(s) { 260 // Too big to fit, allocate and copy over. 261 s2 := append(s[:i], make(S, tot-i)...) // See Insert 262 copy(s2[i:], v) 263 copy(s2[i+len(v):], s[j:]) 264 return s2 265 } 266 267 r := s[:tot] 268 269 if i+len(v) <= j { 270 // Easy, as v fits in the deleted portion. 271 copy(r[i:], v) 272 if i+len(v) != j { 273 copy(r[i+len(v):], s[j:]) 274 } 275 return r 276 } 277 278 // We are expanding (v is bigger than j-i). 279 // The situation is something like this: 280 // (example has i=4,j=8,len(s)=16,len(v)=6) 281 // s: aaaaxxxxbbbbbbbbyy 282 // ^ ^ ^ ^ 283 // i j len(s) tot 284 // a: prefix of s 285 // x: deleted range 286 // b: more of s 287 // y: area to expand into 288 289 if !overlaps(r[i+len(v):], v) { 290 // Easy, as v is not clobbered by the first copy. 291 copy(r[i+len(v):], s[j:]) 292 copy(r[i:], v) 293 return r 294 } 295 296 // This is a situation where we don't have a single place to which 297 // we can copy v. Parts of it need to go to two different places. 298 // We want to copy the prefix of v into y and the suffix into x, then 299 // rotate |y| spots to the right. 300 // 301 // v[2:] v[:2] 302 // | | 303 // s: aaaavvvvbbbbbbbbvv 304 // ^ ^ ^ ^ 305 // i j len(s) tot 306 // 307 // If either of those two destinations don't alias v, then we're good. 308 y := len(v) - (j - i) // length of y portion 309 310 if !overlaps(r[i:j], v) { 311 copy(r[i:j], v[y:]) 312 copy(r[len(s):], v[:y]) 313 rotateRight(r[i:], y) 314 return r 315 } 316 if !overlaps(r[len(s):], v) { 317 copy(r[len(s):], v[:y]) 318 copy(r[i:j], v[y:]) 319 rotateRight(r[i:], y) 320 return r 321 } 322 323 // Now we know that v overlaps both x and y. 324 // That means that the entirety of b is *inside* v. 325 // So we don't need to preserve b at all; instead we 326 // can copy v first, then copy the b part of v out of 327 // v to the right destination. 328 k := startIdx(v, s[j:]) 329 copy(r[i:], v) 330 copy(r[i+len(v):], r[i+k:]) 331 return r 332 } 333 334 // Clone returns a copy of the slice. 335 // The elements are copied using assignment, so this is a shallow clone. 336 func Clone[S ~[]E, E any](s S) S { 337 // Preserve nil in case it matters. 338 if s == nil { 339 return nil 340 } 341 return append(S([]E{}), s...) 342 } 343 344 // Compact replaces consecutive runs of equal elements with a single copy. 345 // This is like the uniq command found on Unix. 346 // Compact modifies the contents of the slice s and returns the modified slice, 347 // which may have a smaller length. 348 // When Compact discards m elements in total, it might not modify the elements 349 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider 350 // zeroing those elements so that objects they reference can be garbage collected. 351 func Compact[S ~[]E, E comparable](s S) S { 352 if len(s) < 2 { 353 return s 354 } 355 i := 1 356 for k := 1; k < len(s); k++ { 357 if s[k] != s[k-1] { 358 if i != k { 359 s[i] = s[k] 360 } 361 i++ 362 } 363 } 364 return s[:i] 365 } 366 367 // CompactFunc is like [Compact] but uses an equality function to compare elements. 368 // For runs of elements that compare equal, CompactFunc keeps the first one. 369 func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S { 370 if len(s) < 2 { 371 return s 372 } 373 i := 1 374 for k := 1; k < len(s); k++ { 375 if !eq(s[k], s[k-1]) { 376 if i != k { 377 s[i] = s[k] 378 } 379 i++ 380 } 381 } 382 return s[:i] 383 } 384 385 // Grow increases the slice's capacity, if necessary, to guarantee space for 386 // another n elements. After Grow(n), at least n elements can be appended 387 // to the slice without another allocation. If n is negative or too large to 388 // allocate the memory, Grow panics. 389 func Grow[S ~[]E, E any](s S, n int) S { 390 if n < 0 { 391 panic("cannot be negative") 392 } 393 if n -= cap(s) - len(s); n > 0 { 394 // TODO(https://go.dev/issue/53888): Make using []E instead of S 395 // to workaround a compiler bug where the runtime.growslice optimization 396 // does not take effect. Revert when the compiler is fixed. 397 s = append([]E(s)[:cap(s)], make([]E, n)...)[:len(s)] 398 } 399 return s 400 } 401 402 // Clip removes unused capacity from the slice, returning s[:len(s):len(s)]. 403 func Clip[S ~[]E, E any](s S) S { 404 return s[:len(s):len(s)] 405 } 406 407 // Rotation algorithm explanation: 408 // 409 // rotate left by 2 410 // start with 411 // 0123456789 412 // split up like this 413 // 01 234567 89 414 // swap first 2 and last 2 415 // 89 234567 01 416 // join first parts 417 // 89234567 01 418 // recursively rotate first left part by 2 419 // 23456789 01 420 // join at the end 421 // 2345678901 422 // 423 // rotate left by 8 424 // start with 425 // 0123456789 426 // split up like this 427 // 01 234567 89 428 // swap first 2 and last 2 429 // 89 234567 01 430 // join last parts 431 // 89 23456701 432 // recursively rotate second part left by 6 433 // 89 01234567 434 // join at the end 435 // 8901234567 436 437 // TODO: There are other rotate algorithms. 438 // This algorithm has the desirable property that it moves each element exactly twice. 439 // The triple-reverse algorithm is simpler and more cache friendly, but takes more writes. 440 // The follow-cycles algorithm can be 1-write but it is not very cache friendly. 441 442 // rotateLeft rotates b left by n spaces. 443 // s_final[i] = s_orig[i+r], wrapping around. 444 func rotateLeft[E any](s []E, r int) { 445 for r != 0 && r != len(s) { 446 if r*2 <= len(s) { 447 swap(s[:r], s[len(s)-r:]) 448 s = s[:len(s)-r] 449 } else { 450 swap(s[:len(s)-r], s[r:]) 451 s, r = s[len(s)-r:], r*2-len(s) 452 } 453 } 454 } 455 func rotateRight[E any](s []E, r int) { 456 rotateLeft(s, len(s)-r) 457 } 458 459 // swap swaps the contents of x and y. x and y must be equal length and disjoint. 460 func swap[E any](x, y []E) { 461 for i := 0; i < len(x); i++ { 462 x[i], y[i] = y[i], x[i] 463 } 464 } 465 466 // overlaps reports whether the memory ranges a[0:len(a)] and b[0:len(b)] overlap. 467 func overlaps[E any](a, b []E) bool { 468 if len(a) == 0 || len(b) == 0 { 469 return false 470 } 471 elemSize := unsafe.Sizeof(a[0]) 472 if elemSize == 0 { 473 return false 474 } 475 // TODO: use a runtime/unsafe facility once one becomes available. See issue 12445. 476 // Also see crypto/internal/alias/alias.go:AnyOverlap 477 return uintptr(unsafe.Pointer(&a[0])) <= uintptr(unsafe.Pointer(&b[len(b)-1]))+(elemSize-1) && 478 uintptr(unsafe.Pointer(&b[0])) <= uintptr(unsafe.Pointer(&a[len(a)-1]))+(elemSize-1) 479 } 480 481 // startIdx returns the index in haystack where the needle starts. 482 // prerequisite: the needle must be aliased entirely inside the haystack. 483 func startIdx[E any](haystack, needle []E) int { 484 p := &needle[0] 485 for i := range haystack { 486 if p == &haystack[i] { 487 return i 488 } 489 } 490 // TODO: what if the overlap is by a non-integral number of Es? 491 panic("needle not found") 492 } 493 494 // Reverse reverses the elements of the slice in place. 495 func Reverse[S ~[]E, E any](s S) { 496 for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { 497 s[i], s[j] = s[j], s[i] 498 } 499 } 500