libgo/go/runtime/string.go

   1 // Copyright 2014 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 runtime
   6
   7 import (
   8         "internal/bytealg"
   9         "unsafe"
  10 )
  11
  12 // For gccgo, use go:linkname to export compiler-called functions.
  13 //
  14 //go:linkname concatstrings
  15 //go:linkname slicebytetostring
  16 //go:linkname slicebytetostringtmp
  17 //go:linkname stringtoslicebyte
  18 //go:linkname stringtoslicerune
  19 //go:linkname slicerunetostring
  20 //go:linkname intstring
  21 // Temporary for C code to call:
  22 //go:linkname gostringnocopy
  23 //go:linkname findnull
  24
  25 // The constant is known to the compiler.
  26 // There is no fundamental theory behind this number.
  27 const tmpStringBufSize = 32
  28
  29 type tmpBuf [tmpStringBufSize]byte
  30
  31 // concatstrings implements a Go string concatenation x+y+z+...
  32 // The operands are passed in the slice a.
  33 // If buf != nil, the compiler has determined that the result does not
  34 // escape the calling function, so the string data can be stored in buf
  35 // if small enough.
  36 func concatstrings(buf *tmpBuf, p *string, n int) string {
  37         var a []string
  38         *(*slice)(unsafe.Pointer(&a)) = slice{unsafe.Pointer(p), n, n}
  39         // idx := 0
  40         l := 0
  41         count := 0
  42         for _, x := range a {
  43                 n := len(x)
  44                 if n == 0 {
  45                         continue
  46                 }
  47                 if l+n < l {
  48                         throw("string concatenation too long")
  49                 }
  50                 l += n
  51                 count++
  52                 // idx = i
  53         }
  54         if count == 0 {
  55                 return ""
  56         }
  57
  58         // If there is just one string and either it is not on the stack
  59         // or our result does not escape the calling frame (buf != nil),
  60         // then we can return that string directly.
  61         // Commented out for gccgo--no implementation of stringDataOnStack.
  62         // if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
  63         //      return a[idx]
  64         // }
  65         s, b := rawstringtmp(buf, l)
  66         for _, x := range a {
  67                 copy(b, x)
  68                 b = b[len(x):]
  69         }
  70         return s
  71 }
  72
  73 // Buf is a fixed-size buffer for the result,
  74 // it is not nil if the result does not escape.
  75 func slicebytetostring(buf *tmpBuf, b []byte) (str string) {
  76         l := len(b)
  77         if l == 0 {
  78                 // Turns out to be a relatively common case.
  79                 // Consider that you want to parse out data between parens in "foo()bar",
  80                 // you find the indices and convert the subslice to string.
  81                 return ""
  82         }
  83         if raceenabled {
  84                 racereadrangepc(unsafe.Pointer(&b[0]),
  85                         uintptr(l),
  86                         getcallerpc(),
  87                         funcPC(slicebytetostring))
  88         }
  89         if msanenabled {
  90                 msanread(unsafe.Pointer(&b[0]), uintptr(l))
  91         }
  92         if l == 1 {
  93                 stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]])
  94                 stringStructOf(&str).len = 1
  95                 return
  96         }
  97
  98         var p unsafe.Pointer
  99         if buf != nil && len(b) <= len(buf) {
 100                 p = unsafe.Pointer(buf)
 101         } else {
 102                 p = mallocgc(uintptr(len(b)), nil, false)
 103         }
 104         stringStructOf(&str).str = p
 105         stringStructOf(&str).len = len(b)
 106         memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b)))
 107         return
 108 }
 109
 110 func rawstringtmp(buf *tmpBuf, l int) (s string, b []byte) {
 111         if buf != nil && l <= len(buf) {
 112                 b = buf[:l]
 113                 s = slicebytetostringtmp(b)
 114         } else {
 115                 s, b = rawstring(l)
 116         }
 117         return
 118 }
 119
 120 // slicebytetostringtmp returns a "string" referring to the actual []byte bytes.
 121 //
 122 // Callers need to ensure that the returned string will not be used after
 123 // the calling goroutine modifies the original slice or synchronizes with
 124 // another goroutine.
 125 //
 126 // The function is only called when instrumenting
 127 // and otherwise intrinsified by the compiler.
 128 //
 129 // Some internal compiler optimizations use this function.
 130 // - Used for m[T1{... Tn{..., string(k), ...} ...}] and m[string(k)]
 131 //   where k is []byte, T1 to Tn is a nesting of struct and array literals.
 132 // - Used for "<"+string(b)+">" concatenation where b is []byte.
 133 // - Used for string(b)=="foo" comparison where b is []byte.
 134 func slicebytetostringtmp(b []byte) string {
 135         if raceenabled && len(b) > 0 {
 136                 racereadrangepc(unsafe.Pointer(&b[0]),
 137                         uintptr(len(b)),
 138                         getcallerpc(),
 139                         funcPC(slicebytetostringtmp))
 140         }
 141         if msanenabled && len(b) > 0 {
 142                 msanread(unsafe.Pointer(&b[0]), uintptr(len(b)))
 143         }
 144         return *(*string)(unsafe.Pointer(&b))
 145 }
 146
 147 func stringtoslicebyte(buf *tmpBuf, s string) []byte {
 148         var b []byte
 149         if buf != nil && len(s) <= len(buf) {
 150                 *buf = tmpBuf{}
 151                 b = buf[:len(s)]
 152         } else {
 153                 b = rawbyteslice(len(s))
 154         }
 155         copy(b, s)
 156         return b
 157 }
 158
 159 func stringtoslicerune(buf *[tmpStringBufSize]rune, s string) []rune {
 160         // two passes.
 161         // unlike slicerunetostring, no race because strings are immutable.
 162         n := 0
 163         for range s {
 164                 n++
 165         }
 166
 167         var a []rune
 168         if buf != nil && n <= len(buf) {
 169                 *buf = [tmpStringBufSize]rune{}
 170                 a = buf[:n]
 171         } else {
 172                 a = rawruneslice(n)
 173         }
 174
 175         n = 0
 176         for _, r := range s {
 177                 a[n] = r
 178                 n++
 179         }
 180         return a
 181 }
 182
 183 func slicerunetostring(buf *tmpBuf, a []rune) string {
 184         if raceenabled && len(a) > 0 {
 185                 racereadrangepc(unsafe.Pointer(&a[0]),
 186                         uintptr(len(a))*unsafe.Sizeof(a[0]),
 187                         getcallerpc(),
 188                         funcPC(slicerunetostring))
 189         }
 190         if msanenabled && len(a) > 0 {
 191                 msanread(unsafe.Pointer(&a[0]), uintptr(len(a))*unsafe.Sizeof(a[0]))
 192         }
 193         var dum [4]byte
 194         size1 := 0
 195         for _, r := range a {
 196                 size1 += encoderune(dum[:], r)
 197         }
 198         s, b := rawstringtmp(buf, size1+3)
 199         size2 := 0
 200         for _, r := range a {
 201                 // check for race
 202                 if size2 >= size1 {
 203                         break
 204                 }
 205                 size2 += encoderune(b[size2:], r)
 206         }
 207         return s[:size2]
 208 }
 209
 210 type stringStruct struct {
 211         str unsafe.Pointer
 212         len int
 213 }
 214
 215 // Variant with *byte pointer type for DWARF debugging.
 216 type stringStructDWARF struct {
 217         str *byte
 218         len int
 219 }
 220
 221 func stringStructOf(sp *string) *stringStruct {
 222         return (*stringStruct)(unsafe.Pointer(sp))
 223 }
 224
 225 func intstring(buf *[4]byte, v int64) (s string) {
 226         if v >= 0 && v < runeSelf {
 227                 stringStructOf(&s).str = unsafe.Pointer(&staticbytes[v])
 228                 stringStructOf(&s).len = 1
 229                 return
 230         }
 231
 232         var b []byte
 233         if buf != nil {
 234                 b = buf[:]
 235                 s = slicebytetostringtmp(b)
 236         } else {
 237                 s, b = rawstring(4)
 238         }
 239         if int64(rune(v)) != v {
 240                 v = runeError
 241         }
 242         n := encoderune(b, rune(v))
 243         return s[:n]
 244 }
 245
 246 // rawstring allocates storage for a new string. The returned
 247 // string and byte slice both refer to the same storage.
 248 // The storage is not zeroed. Callers should use
 249 // b to set the string contents and then drop b.
 250 func rawstring(size int) (s string, b []byte) {
 251         p := mallocgc(uintptr(size), nil, false)
 252
 253         stringStructOf(&s).str = p
 254         stringStructOf(&s).len = size
 255
 256         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}
 257
 258         return
 259 }
 260
 261 // rawbyteslice allocates a new byte slice. The byte slice is not zeroed.
 262 func rawbyteslice(size int) (b []byte) {
 263         cap := roundupsize(uintptr(size))
 264         p := mallocgc(cap, nil, false)
 265         if cap != uintptr(size) {
 266                 memclrNoHeapPointers(add(p, uintptr(size)), cap-uintptr(size))
 267         }
 268
 269         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, int(cap)}
 270         return
 271 }
 272
 273 // rawruneslice allocates a new rune slice. The rune slice is not zeroed.
 274 func rawruneslice(size int) (b []rune) {
 275         if uintptr(size) > maxAlloc/4 {
 276                 throw("out of memory")
 277         }
 278         mem := roundupsize(uintptr(size) * 4)
 279         p := mallocgc(mem, nil, false)
 280         if mem != uintptr(size)*4 {
 281                 memclrNoHeapPointers(add(p, uintptr(size)*4), mem-uintptr(size)*4)
 282         }
 283
 284         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, int(mem / 4)}
 285         return
 286 }
 287
 288 // used by cmd/cgo
 289 func gobytes(p *byte, n int) (b []byte) {
 290         if n == 0 {
 291                 return make([]byte, 0)
 292         }
 293
 294         if n < 0 || uintptr(n) > maxAlloc {
 295                 panic(errorString("gobytes: length out of range"))
 296         }
 297
 298         bp := mallocgc(uintptr(n), nil, false)
 299         memmove(bp, unsafe.Pointer(p), uintptr(n))
 300
 301         *(*slice)(unsafe.Pointer(&b)) = slice{bp, n, n}
 302         return
 303 }
 304
 305 // This is exported via linkname to assembly in syscall (for Plan9).
 306 //go:linkname gostring
 307 func gostring(p *byte) string {
 308         l := findnull(p)
 309         if l == 0 {
 310                 return ""
 311         }
 312         s, b := rawstring(l)
 313         memmove(unsafe.Pointer(&b[0]), unsafe.Pointer(p), uintptr(l))
 314         return s
 315 }
 316
 317 func gostringn(p *byte, l int) string {
 318         if l == 0 {
 319                 return ""
 320         }
 321         s, b := rawstring(l)
 322         memmove(unsafe.Pointer(&b[0]), unsafe.Pointer(p), uintptr(l))
 323         return s
 324 }
 325
 326 func index(s, t string) int {
 327         if len(t) == 0 {
 328                 return 0
 329         }
 330         for i := 0; i < len(s); i++ {
 331                 if s[i] == t[0] && hasPrefix(s[i:], t) {
 332                         return i
 333                 }
 334         }
 335         return -1
 336 }
 337
 338 func contains(s, t string) bool {
 339         return index(s, t) >= 0
 340 }
 341
 342 func hasPrefix(s, prefix string) bool {
 343         return len(s) >= len(prefix) && s[:len(prefix)] == prefix
 344 }
 345
 346 func hasSuffix(s, suffix string) bool {
 347         return len(s) >= len(suffix) && s[len(s)-len(suffix):] == suffix
 348 }
 349
 350 const (
 351         maxUint = ^uint(0)
 352         maxInt  = int(maxUint >> 1)
 353 )
 354
 355 // atoi parses an int from a string s.
 356 // The bool result reports whether s is a number
 357 // representable by a value of type int.
 358 func atoi(s string) (int, bool) {
 359         if s == "" {
 360                 return 0, false
 361         }
 362
 363         neg := false
 364         if s[0] == '-' {
 365                 neg = true
 366                 s = s[1:]
 367         }
 368
 369         un := uint(0)
 370         for i := 0; i < len(s); i++ {
 371                 c := s[i]
 372                 if c < '0' || c > '9' {
 373                         return 0, false
 374                 }
 375                 if un > maxUint/10 {
 376                         // overflow
 377                         return 0, false
 378                 }
 379                 un *= 10
 380                 un1 := un + uint(c) - '0'
 381                 if un1 < un {
 382                         // overflow
 383                         return 0, false
 384                 }
 385                 un = un1
 386         }
 387
 388         if !neg && un > uint(maxInt) {
 389                 return 0, false
 390         }
 391         if neg && un > uint(maxInt)+1 {
 392                 return 0, false
 393         }
 394
 395         n := int(un)
 396         if neg {
 397                 n = -n
 398         }
 399
 400         return n, true
 401 }
 402
 403 // atoi32 is like atoi but for integers
 404 // that fit into an int32.
 405 func atoi32(s string) (int32, bool) {
 406         if n, ok := atoi(s); n == int(int32(n)) {
 407                 return int32(n), ok
 408         }
 409         return 0, false
 410 }
 411
 412 //go:nosplit
 413 func findnull(s *byte) int {
 414         if s == nil {
 415                 return 0
 416         }
 417
 418         // Avoid IndexByteString on Plan 9 because it uses SSE instructions
 419         // on x86 machines, and those are classified as floating point instructions,
 420         // which are illegal in a note handler.
 421         if GOOS == "plan9" {
 422                 p := (*[maxAlloc/2 - 1]byte)(unsafe.Pointer(s))
 423                 l := 0
 424                 for p[l] != 0 {
 425                         l++
 426                 }
 427                 return l
 428         }
 429
 430         // pageSize is the unit we scan at a time looking for NULL.
 431         // It must be the minimum page size for any architecture Go
 432         // runs on. It's okay (just a minor performance loss) if the
 433         // actual system page size is larger than this value.
 434         const pageSize = 4096
 435
 436         offset := 0
 437         ptr := unsafe.Pointer(s)
 438         // IndexByteString uses wide reads, so we need to be careful
 439         // with page boundaries. Call IndexByteString on
 440         // [ptr, endOfPage) interval.
 441         safeLen := int(pageSize - uintptr(ptr)%pageSize)
 442
 443         for {
 444                 t := *(*string)(unsafe.Pointer(&stringStruct{ptr, safeLen}))
 445                 // Check one page at a time.
 446                 if i := bytealg.IndexByteString(t, 0); i != -1 {
 447                         return offset + i
 448                 }
 449                 // Move to next page
 450                 ptr = unsafe.Pointer(uintptr(ptr) + uintptr(safeLen))
 451                 offset += safeLen
 452                 safeLen = pageSize
 453         }
 454 }
 455
 456 func findnullw(s *uint16) int {
 457         if s == nil {
 458                 return 0
 459         }
 460         p := (*[maxAlloc/2/2 - 1]uint16)(unsafe.Pointer(s))
 461         l := 0
 462         for p[l] != 0 {
 463                 l++
 464         }
 465         return l
 466 }
 467
 468 //go:nosplit
 469 func gostringnocopy(str *byte) string {
 470         ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
 471         s := *(*string)(unsafe.Pointer(&ss))
 472         return s
 473 }
 474
 475 func gostringw(strw *uint16) string {
 476         var buf [8]byte
 477         str := (*[maxAlloc/2/2 - 1]uint16)(unsafe.Pointer(strw))
 478         n1 := 0
 479         for i := 0; str[i] != 0; i++ {
 480                 n1 += encoderune(buf[:], rune(str[i]))
 481         }
 482         s, b := rawstring(n1 + 4)
 483         n2 := 0
 484         for i := 0; str[i] != 0; i++ {
 485                 // check for race
 486                 if n2 >= n1 {
 487                         break
 488                 }
 489                 n2 += encoderune(b[n2:], rune(str[i]))
 490         }
 491         b[n2] = 0 // for luck
 492         return s[:n2]
 493 }
 494
 495 // These two functions are called by code generated by cgo -gccgo.
 496
 497 //go:linkname __go_byte_array_to_string __go_byte_array_to_string
 498 func __go_byte_array_to_string(p unsafe.Pointer, l int) string {
 499         if l == 0 {
 500                 return ""
 501         }
 502         s, c := rawstringtmp(nil, l)
 503         memmove(unsafe.Pointer(&c[0]), p, uintptr(l))
 504         return s
 505 }
 506
 507 //go:linkname __go_string_to_byte_array __go_string_to_byte_array
 508 func __go_string_to_byte_array(s string) []byte {
 509         return stringtoslicebyte(nil, s)
 510 }
 511
 512 // parseRelease parses a dot-separated version number. It follows the
 513 // semver syntax, but allows the minor and patch versions to be
 514 // elided.
 515 func parseRelease(rel string) (major, minor, patch int, ok bool) {
 516         // Strip anything after a dash or plus.
 517         for i := 0; i < len(rel); i++ {
 518                 if rel[i] == '-' || rel[i] == '+' {
 519                         rel = rel[:i]
 520                         break
 521                 }
 522         }
 523
 524         next := func() (int, bool) {
 525                 for i := 0; i < len(rel); i++ {
 526                         if rel[i] == '.' {
 527                                 ver, ok := atoi(rel[:i])
 528                                 rel = rel[i+1:]
 529                                 return ver, ok
 530                         }
 531                 }
 532                 ver, ok := atoi(rel)
 533                 rel = ""
 534                 return ver, ok
 535         }
 536         if major, ok = next(); !ok || rel == "" {
 537                 return
 538         }
 539         if minor, ok = next(); !ok || rel == "" {
 540                 return
 541         }
 542         patch, ok = next()
 543         return
 544 }