libgo/go/bytes/bytes.go

   1 // Copyright 2009 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 // The bytes package implements functions for the manipulation of byte slices.
   6 // Analogous to the facilities of the strings package.
   7 package bytes
   8
   9 import (
  10         "unicode"
  11         "utf8"
  12 )
  13
  14 // Compare returns an integer comparing the two byte arrays lexicographically.
  15 // The result will be 0 if a==b, -1 if a < b, and +1 if a > b
  16 func Compare(a, b []byte) int {
  17         m := len(a)
  18         if m > len(b) {
  19                 m = len(b)
  20         }
  21         for i, ac := range a[0:m] {
  22                 bc := b[i]
  23                 switch {
  24                 case ac > bc:
  25                         return 1
  26                 case ac < bc:
  27                         return -1
  28                 }
  29         }
  30         switch {
  31         case len(a) < len(b):
  32                 return -1
  33         case len(a) > len(b):
  34                 return 1
  35         }
  36         return 0
  37 }
  38
  39 // Equal returns a boolean reporting whether a == b.
  40 func Equal(a, b []byte) bool {
  41         if len(a) != len(b) {
  42                 return false
  43         }
  44         for i, c := range a {
  45                 if c != b[i] {
  46                         return false
  47                 }
  48         }
  49         return true
  50 }
  51
  52 // explode splits s into an array of UTF-8 sequences, one per Unicode character (still arrays of bytes),
  53 // up to a maximum of n byte arrays. Invalid UTF-8 sequences are chopped into individual bytes.
  54 func explode(s []byte, n int) [][]byte {
  55         if n <= 0 {
  56                 n = len(s)
  57         }
  58         a := make([][]byte, n)
  59         var size int
  60         na := 0
  61         for len(s) > 0 {
  62                 if na+1 >= n {
  63                         a[na] = s
  64                         na++
  65                         break
  66                 }
  67                 _, size = utf8.DecodeRune(s)
  68                 a[na] = s[0:size]
  69                 s = s[size:]
  70                 na++
  71         }
  72         return a[0:na]
  73 }
  74
  75 // Count counts the number of non-overlapping instances of sep in s.
  76 func Count(s, sep []byte) int {
  77         if len(sep) == 0 {
  78                 return utf8.RuneCount(s) + 1
  79         }
  80         c := sep[0]
  81         n := 0
  82         for i := 0; i+len(sep) <= len(s); i++ {
  83                 if s[i] == c && (len(sep) == 1 || Equal(s[i:i+len(sep)], sep)) {
  84                         n++
  85                         i += len(sep) - 1
  86                 }
  87         }
  88         return n
  89 }
  90
  91 // Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
  92 func Index(s, sep []byte) int {
  93         n := len(sep)
  94         if n == 0 {
  95                 return 0
  96         }
  97         c := sep[0]
  98         for i := 0; i+n <= len(s); i++ {
  99                 if s[i] == c && (n == 1 || Equal(s[i:i+n], sep)) {
 100                         return i
 101                 }
 102         }
 103         return -1
 104 }
 105
 106 func indexBytePortable(s []byte, c byte) int {
 107         for i, b := range s {
 108                 if b == c {
 109                         return i
 110                 }
 111         }
 112         return -1
 113 }
 114
 115 // LastIndex returns the index of the last instance of sep in s, or -1 if sep is not present in s.
 116 func LastIndex(s, sep []byte) int {
 117         n := len(sep)
 118         if n == 0 {
 119                 return len(s)
 120         }
 121         c := sep[0]
 122         for i := len(s) - n; i >= 0; i-- {
 123                 if s[i] == c && (n == 1 || Equal(s[i:i+n], sep)) {
 124                         return i
 125                 }
 126         }
 127         return -1
 128 }
 129
 130 // IndexRune interprets s as a sequence of UTF-8-encoded Unicode code points.
 131 // It returns the byte index of the first occurrence in s of the given rune.
 132 // It returns -1 if rune is not present in s.
 133 func IndexRune(s []byte, rune int) int {
 134         for i := 0; i < len(s); {
 135                 r, size := utf8.DecodeRune(s[i:])
 136                 if r == rune {
 137                         return i
 138                 }
 139                 i += size
 140         }
 141         return -1
 142 }
 143
 144 // IndexAny interprets s as a sequence of UTF-8-encoded Unicode code points.
 145 // It returns the byte index of the first occurrence in s of any of the Unicode
 146 // code points in chars.  It returns -1 if chars is empty or if there is no code
 147 // point in common.
 148 func IndexAny(s []byte, chars string) int {
 149         if len(chars) > 0 {
 150                 var rune, width int
 151                 for i := 0; i < len(s); i += width {
 152                         rune = int(s[i])
 153                         if rune < utf8.RuneSelf {
 154                                 width = 1
 155                         } else {
 156                                 rune, width = utf8.DecodeRune(s[i:])
 157                         }
 158                         for _, r := range chars {
 159                                 if rune == r {
 160                                         return i
 161                                 }
 162                         }
 163                 }
 164         }
 165         return -1
 166 }
 167
 168 // LastIndexAny interprets s as a sequence of UTF-8-encoded Unicode code
 169 // points.  It returns the byte index of the last occurrence in s of any of
 170 // the Unicode code points in chars.  It returns -1 if chars is empty or if
 171 // there is no code point in common.
 172 func LastIndexAny(s []byte, chars string) int {
 173         if len(chars) > 0 {
 174                 for i := len(s); i > 0; {
 175                         rune, size := utf8.DecodeLastRune(s[0:i])
 176                         i -= size
 177                         for _, m := range chars {
 178                                 if rune == m {
 179                                         return i
 180                                 }
 181                         }
 182                 }
 183         }
 184         return -1
 185 }
 186
 187 // Generic split: splits after each instance of sep,
 188 // including sepSave bytes of sep in the subarrays.
 189 func genSplit(s, sep []byte, sepSave, n int) [][]byte {
 190         if n == 0 {
 191                 return nil
 192         }
 193         if len(sep) == 0 {
 194                 return explode(s, n)
 195         }
 196         if n < 0 {
 197                 n = Count(s, sep) + 1
 198         }
 199         c := sep[0]
 200         start := 0
 201         a := make([][]byte, n)
 202         na := 0
 203         for i := 0; i+len(sep) <= len(s) && na+1 < n; i++ {
 204                 if s[i] == c && (len(sep) == 1 || Equal(s[i:i+len(sep)], sep)) {
 205                         a[na] = s[start : i+sepSave]
 206                         na++
 207                         start = i + len(sep)
 208                         i += len(sep) - 1
 209                 }
 210         }
 211         a[na] = s[start:]
 212         return a[0 : na+1]
 213 }
 214
 215 // Split slices s into subslices separated by sep and returns a slice of
 216 // the subslices between those separators.
 217 // If sep is empty, Split splits after each UTF-8 sequence.
 218 // The count determines the number of subslices to return:
 219 //   n > 0: at most n subslices; the last subslice will be the unsplit remainder.
 220 //   n == 0: the result is nil (zero subslices)
 221 //   n < 0: all subslices
 222 func Split(s, sep []byte, n int) [][]byte { return genSplit(s, sep, 0, n) }
 223
 224 // SplitAfter slices s into subslices after each instance of sep and
 225 // returns a slice of those subslices.
 226 // If sep is empty, Split splits after each UTF-8 sequence.
 227 // The count determines the number of subslices to return:
 228 //   n > 0: at most n subslices; the last subslice will be the unsplit remainder.
 229 //   n == 0: the result is nil (zero subslices)
 230 //   n < 0: all subslices
 231 func SplitAfter(s, sep []byte, n int) [][]byte {
 232         return genSplit(s, sep, len(sep), n)
 233 }
 234
 235 // Fields splits the array s around each instance of one or more consecutive white space
 236 // characters, returning a slice of subarrays of s or an empty list if s contains only white space.
 237 func Fields(s []byte) [][]byte {
 238         return FieldsFunc(s, unicode.IsSpace)
 239 }
 240
 241 // FieldsFunc interprets s as a sequence of UTF-8-encoded Unicode code points.
 242 // It splits the array s at each run of code points c satisfying f(c) and
 243 // returns a slice of subarrays of s.  If no code points in s satisfy f(c), an
 244 // empty slice is returned.
 245 func FieldsFunc(s []byte, f func(int) bool) [][]byte {
 246         n := 0
 247         inField := false
 248         for i := 0; i < len(s); {
 249                 rune, size := utf8.DecodeRune(s[i:])
 250                 wasInField := inField
 251                 inField = !f(rune)
 252                 if inField && !wasInField {
 253                         n++
 254                 }
 255                 i += size
 256         }
 257
 258         a := make([][]byte, n)
 259         na := 0
 260         fieldStart := -1
 261         for i := 0; i <= len(s) && na < n; {
 262                 rune, size := utf8.DecodeRune(s[i:])
 263                 if fieldStart < 0 && size > 0 && !f(rune) {
 264                         fieldStart = i
 265                         i += size
 266                         continue
 267                 }
 268                 if fieldStart >= 0 && (size == 0 || f(rune)) {
 269                         a[na] = s[fieldStart:i]
 270                         na++
 271                         fieldStart = -1
 272                 }
 273                 if size == 0 {
 274                         break
 275                 }
 276                 i += size
 277         }
 278         return a[0:na]
 279 }
 280
 281 // Join concatenates the elements of a to create a single byte array.   The separator
 282 // sep is placed between elements in the resulting array.
 283 func Join(a [][]byte, sep []byte) []byte {
 284         if len(a) == 0 {
 285                 return []byte{}
 286         }
 287         if len(a) == 1 {
 288                 return a[0]
 289         }
 290         n := len(sep) * (len(a) - 1)
 291         for i := 0; i < len(a); i++ {
 292                 n += len(a[i])
 293         }
 294
 295         b := make([]byte, n)
 296         bp := 0
 297         for i := 0; i < len(a); i++ {
 298                 s := a[i]
 299                 for j := 0; j < len(s); j++ {
 300                         b[bp] = s[j]
 301                         bp++
 302                 }
 303                 if i+1 < len(a) {
 304                         s = sep
 305                         for j := 0; j < len(s); j++ {
 306                                 b[bp] = s[j]
 307                                 bp++
 308                         }
 309                 }
 310         }
 311         return b
 312 }
 313
 314 // HasPrefix tests whether the byte array s begins with prefix.
 315 func HasPrefix(s, prefix []byte) bool {
 316         return len(s) >= len(prefix) && Equal(s[0:len(prefix)], prefix)
 317 }
 318
 319 // HasSuffix tests whether the byte array s ends with suffix.
 320 func HasSuffix(s, suffix []byte) bool {
 321         return len(s) >= len(suffix) && Equal(s[len(s)-len(suffix):], suffix)
 322 }
 323
 324 // Map returns a copy of the byte array s with all its characters modified
 325 // according to the mapping function. If mapping returns a negative value, the character is
 326 // dropped from the string with no replacement.  The characters in s and the
 327 // output are interpreted as UTF-8-encoded Unicode code points.
 328 func Map(mapping func(rune int) int, s []byte) []byte {
 329         // In the worst case, the array can grow when mapped, making
 330         // things unpleasant.  But it's so rare we barge in assuming it's
 331         // fine.  It could also shrink but that falls out naturally.
 332         maxbytes := len(s) // length of b
 333         nbytes := 0        // number of bytes encoded in b
 334         b := make([]byte, maxbytes)
 335         for i := 0; i < len(s); {
 336                 wid := 1
 337                 rune := int(s[i])
 338                 if rune >= utf8.RuneSelf {
 339                         rune, wid = utf8.DecodeRune(s[i:])
 340                 }
 341                 rune = mapping(rune)
 342                 if rune >= 0 {
 343                         if nbytes+utf8.RuneLen(rune) > maxbytes {
 344                                 // Grow the buffer.
 345                                 maxbytes = maxbytes*2 + utf8.UTFMax
 346                                 nb := make([]byte, maxbytes)
 347                                 copy(nb, b[0:nbytes])
 348                                 b = nb
 349                         }
 350                         nbytes += utf8.EncodeRune(b[nbytes:maxbytes], rune)
 351                 }
 352                 i += wid
 353         }
 354         return b[0:nbytes]
 355 }
 356
 357 // Repeat returns a new byte slice consisting of count copies of b.
 358 func Repeat(b []byte, count int) []byte {
 359         nb := make([]byte, len(b)*count)
 360         bp := 0
 361         for i := 0; i < count; i++ {
 362                 for j := 0; j < len(b); j++ {
 363                         nb[bp] = b[j]
 364                         bp++
 365                 }
 366         }
 367         return nb
 368 }
 369
 370 // ToUpper returns a copy of the byte array s with all Unicode letters mapped to their upper case.
 371 func ToUpper(s []byte) []byte { return Map(unicode.ToUpper, s) }
 372
 373 // ToUpper returns a copy of the byte array s with all Unicode letters mapped to their lower case.
 374 func ToLower(s []byte) []byte { return Map(unicode.ToLower, s) }
 375
 376 // ToTitle returns a copy of the byte array s with all Unicode letters mapped to their title case.
 377 func ToTitle(s []byte) []byte { return Map(unicode.ToTitle, s) }
 378
 379 // ToUpperSpecial returns a copy of the byte array s with all Unicode letters mapped to their
 380 // upper case, giving priority to the special casing rules.
 381 func ToUpperSpecial(_case unicode.SpecialCase, s []byte) []byte {
 382         return Map(func(r int) int { return _case.ToUpper(r) }, s)
 383 }
 384
 385 // ToLowerSpecial returns a copy of the byte array s with all Unicode letters mapped to their
 386 // lower case, giving priority to the special casing rules.
 387 func ToLowerSpecial(_case unicode.SpecialCase, s []byte) []byte {
 388         return Map(func(r int) int { return _case.ToLower(r) }, s)
 389 }
 390
 391 // ToTitleSpecial returns a copy of the byte array s with all Unicode letters mapped to their
 392 // title case, giving priority to the special casing rules.
 393 func ToTitleSpecial(_case unicode.SpecialCase, s []byte) []byte {
 394         return Map(func(r int) int { return _case.ToTitle(r) }, s)
 395 }
 396
 397
 398 // isSeparator reports whether the rune could mark a word boundary.
 399 // TODO: update when package unicode captures more of the properties.
 400 func isSeparator(rune int) bool {
 401         // ASCII alphanumerics and underscore are not separators
 402         if rune <= 0x7F {
 403                 switch {
 404                 case '0' <= rune && rune <= '9':
 405                         return false
 406                 case 'a' <= rune && rune <= 'z':
 407                         return false
 408                 case 'A' <= rune && rune <= 'Z':
 409                         return false
 410                 case rune == '_':
 411                         return false
 412                 }
 413                 return true
 414         }
 415         // Letters and digits are not separators
 416         if unicode.IsLetter(rune) || unicode.IsDigit(rune) {
 417                 return false
 418         }
 419         // Otherwise, all we can do for now is treat spaces as separators.
 420         return unicode.IsSpace(rune)
 421 }
 422
 423 // BUG(r): The rule Title uses for word boundaries does not handle Unicode punctuation properly.
 424
 425 // Title returns a copy of s with all Unicode letters that begin words
 426 // mapped to their title case.
 427 func Title(s []byte) []byte {
 428         // Use a closure here to remember state.
 429         // Hackish but effective. Depends on Map scanning in order and calling
 430         // the closure once per rune.
 431         prev := ' '
 432         return Map(
 433                 func(r int) int {
 434                         if isSeparator(prev) {
 435                                 prev = r
 436                                 return unicode.ToTitle(r)
 437                         }
 438                         prev = r
 439                         return r
 440                 },
 441                 s)
 442 }
 443
 444 // TrimLeftFunc returns a subslice of s by slicing off all leading UTF-8-encoded
 445 // Unicode code points c that satisfy f(c).
 446 func TrimLeftFunc(s []byte, f func(r int) bool) []byte {
 447         i := indexFunc(s, f, false)
 448         if i == -1 {
 449                 return nil
 450         }
 451         return s[i:]
 452 }
 453
 454 // TrimRightFunc returns a subslice of s by slicing off all trailing UTF-8
 455 // encoded Unicode code points c that satisfy f(c).
 456 func TrimRightFunc(s []byte, f func(r int) bool) []byte {
 457         i := lastIndexFunc(s, f, false)
 458         if i >= 0 && s[i] >= utf8.RuneSelf {
 459                 _, wid := utf8.DecodeRune(s[i:])
 460                 i += wid
 461         } else {
 462                 i++
 463         }
 464         return s[0:i]
 465 }
 466
 467 // TrimFunc returns a subslice of s by slicing off all leading and trailing
 468 // UTF-8-encoded Unicode code points c that satisfy f(c).
 469 func TrimFunc(s []byte, f func(r int) bool) []byte {
 470         return TrimRightFunc(TrimLeftFunc(s, f), f)
 471 }
 472
 473 // IndexFunc interprets s as a sequence of UTF-8-encoded Unicode code points.
 474 // It returns the byte index in s of the first Unicode
 475 // code point satisfying f(c), or -1 if none do.
 476 func IndexFunc(s []byte, f func(r int) bool) int {
 477         return indexFunc(s, f, true)
 478 }
 479
 480 // LastIndexFunc interprets s as a sequence of UTF-8-encoded Unicode code points.
 481 // It returns the byte index in s of the last Unicode
 482 // code point satisfying f(c), or -1 if none do.
 483 func LastIndexFunc(s []byte, f func(r int) bool) int {
 484         return lastIndexFunc(s, f, true)
 485 }
 486
 487 // indexFunc is the same as IndexFunc except that if
 488 // truth==false, the sense of the predicate function is
 489 // inverted.
 490 func indexFunc(s []byte, f func(r int) bool, truth bool) int {
 491         start := 0
 492         for start < len(s) {
 493                 wid := 1
 494                 rune := int(s[start])
 495                 if rune >= utf8.RuneSelf {
 496                         rune, wid = utf8.DecodeRune(s[start:])
 497                 }
 498                 if f(rune) == truth {
 499                         return start
 500                 }
 501                 start += wid
 502         }
 503         return -1
 504 }
 505
 506 // lastIndexFunc is the same as LastIndexFunc except that if
 507 // truth==false, the sense of the predicate function is
 508 // inverted.
 509 func lastIndexFunc(s []byte, f func(r int) bool, truth bool) int {
 510         for i := len(s); i > 0; {
 511                 rune, size := utf8.DecodeLastRune(s[0:i])
 512                 i -= size
 513                 if f(rune) == truth {
 514                         return i
 515                 }
 516         }
 517         return -1
 518 }
 519
 520 func makeCutsetFunc(cutset string) func(rune int) bool {
 521         return func(rune int) bool {
 522                 for _, c := range cutset {
 523                         if c == rune {
 524                                 return true
 525                         }
 526                 }
 527                 return false
 528         }
 529 }
 530
 531 // Trim returns a subslice of s by slicing off all leading and
 532 // trailing UTF-8-encoded Unicode code points contained in cutset.
 533 func Trim(s []byte, cutset string) []byte {
 534         return TrimFunc(s, makeCutsetFunc(cutset))
 535 }
 536
 537 // TrimLeft returns a subslice of s by slicing off all leading
 538 // UTF-8-encoded Unicode code points contained in cutset.
 539 func TrimLeft(s []byte, cutset string) []byte {
 540         return TrimLeftFunc(s, makeCutsetFunc(cutset))
 541 }
 542
 543 // TrimRight returns a subslice of s by slicing off all trailing
 544 // UTF-8-encoded Unicode code points that are contained in cutset.
 545 func TrimRight(s []byte, cutset string) []byte {
 546         return TrimRightFunc(s, makeCutsetFunc(cutset))
 547 }
 548
 549 // TrimSpace returns a subslice of s by slicing off all leading and
 550 // trailing white space, as defined by Unicode.
 551 func TrimSpace(s []byte) []byte {
 552         return TrimFunc(s, unicode.IsSpace)
 553 }
 554
 555 // Runes returns a slice of runes (Unicode code points) equivalent to s.
 556 func Runes(s []byte) []int {
 557         t := make([]int, utf8.RuneCount(s))
 558         i := 0
 559         for len(s) > 0 {
 560                 r, l := utf8.DecodeRune(s)
 561                 t[i] = r
 562                 i++
 563                 s = s[l:]
 564         }
 565         return t
 566 }
 567
 568 // Replace returns a copy of the slice s with the first n
 569 // non-overlapping instances of old replaced by new.
 570 // If n < 0, there is no limit on the number of replacements.
 571 func Replace(s, old, new []byte, n int) []byte {
 572         if n == 0 {
 573                 return s // avoid allocation
 574         }
 575         // Compute number of replacements.
 576         if m := Count(s, old); m == 0 {
 577                 return s // avoid allocation
 578         } else if n <= 0 || m < n {
 579                 n = m
 580         }
 581
 582         // Apply replacements to buffer.
 583         t := make([]byte, len(s)+n*(len(new)-len(old)))
 584         w := 0
 585         start := 0
 586         for i := 0; i < n; i++ {
 587                 j := start
 588                 if len(old) == 0 {
 589                         if i > 0 {
 590                                 _, wid := utf8.DecodeRune(s[start:])
 591                                 j += wid
 592                         }
 593                 } else {
 594                         j += Index(s[start:], old)
 595                 }
 596                 w += copy(t[w:], s[start:j])
 597                 w += copy(t[w:], new)
 598                 start = j + len(old)
 599         }
 600         w += copy(t[w:], s[start:])
 601         return t[0:w]
 602 }