src/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         "unsafe"
   9 )
  10
  11 // The constant is known to the compiler.
  12 // There is no fundamental theory behind this number.
  13 const tmpStringBufSize = 32
  14
  15 type tmpBuf [tmpStringBufSize]byte
  16
  17 // concatstrings implements a Go string concatenation x+y+z+...
  18 // The operands are passed in the slice a.
  19 // If buf != nil, the compiler has determined that the result does not
  20 // escape the calling function, so the string data can be stored in buf
  21 // if small enough.
  22 func concatstrings(buf *tmpBuf, a []string) string {
  23         idx := 0
  24         l := 0
  25         count := 0
  26         for i, x := range a {
  27                 n := len(x)
  28                 if n == 0 {
  29                         continue
  30                 }
  31                 if l+n < l {
  32                         throw("string concatenation too long")
  33                 }
  34                 l += n
  35                 count++
  36                 idx = i
  37         }
  38         if count == 0 {
  39                 return ""
  40         }
  41
  42         // If there is just one string and either it is not on the stack
  43         // or our result does not escape the calling frame (buf != nil),
  44         // then we can return that string directly.
  45         if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
  46                 return a[idx]
  47         }
  48         s, b := rawstringtmp(buf, l)
  49         l = 0
  50         for _, x := range a {
  51                 copy(b[l:], x)
  52                 l += len(x)
  53         }
  54         return s
  55 }
  56
  57 func concatstring2(buf *tmpBuf, a [2]string) string {
  58         return concatstrings(buf, a[:])
  59 }
  60
  61 func concatstring3(buf *tmpBuf, a [3]string) string {
  62         return concatstrings(buf, a[:])
  63 }
  64
  65 func concatstring4(buf *tmpBuf, a [4]string) string {
  66         return concatstrings(buf, a[:])
  67 }
  68
  69 func concatstring5(buf *tmpBuf, a [5]string) string {
  70         return concatstrings(buf, a[:])
  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) 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 && l > 0 {
  84                 racereadrangepc(unsafe.Pointer(&b[0]),
  85                         uintptr(l),
  86                         getcallerpc(unsafe.Pointer(&b)),
  87                         funcPC(slicebytetostring))
  88         }
  89         s, c := rawstringtmp(buf, l)
  90         copy(c, b)
  91         return s
  92 }
  93
  94 // stringDataOnStack reports whether the string's data is
  95 // stored on the current goroutine's stack.
  96 func stringDataOnStack(s string) bool {
  97         ptr := uintptr((*stringStruct)(unsafe.Pointer(&s)).str)
  98         stk := getg().stack
  99         return stk.lo <= ptr && ptr < stk.hi
 100 }
 101
 102 func rawstringtmp(buf *tmpBuf, l int) (s string, b []byte) {
 103         if buf != nil && l <= len(buf) {
 104                 b = buf[:l]
 105                 s = slicebytetostringtmp(b)
 106         } else {
 107                 s, b = rawstring(l)
 108         }
 109         return
 110 }
 111
 112 func slicebytetostringtmp(b []byte) string {
 113         // Return a "string" referring to the actual []byte bytes.
 114         // This is only for use by internal compiler optimizations
 115         // that know that the string form will be discarded before
 116         // the calling goroutine could possibly modify the original
 117         // slice or synchronize with another goroutine.
 118         // First such case is a m[string(k)] lookup where
 119         // m is a string-keyed map and k is a []byte.
 120         // Second such case is "<"+string(b)+">" concatenation where b is []byte.
 121         // Third such case is string(b)=="foo" comparison where b is []byte.
 122
 123         if raceenabled && len(b) > 0 {
 124                 racereadrangepc(unsafe.Pointer(&b[0]),
 125                         uintptr(len(b)),
 126                         getcallerpc(unsafe.Pointer(&b)),
 127                         funcPC(slicebytetostringtmp))
 128         }
 129         return *(*string)(unsafe.Pointer(&b))
 130 }
 131
 132 func stringtoslicebyte(buf *tmpBuf, s string) []byte {
 133         var b []byte
 134         if buf != nil && len(s) <= len(buf) {
 135                 b = buf[:len(s)]
 136         } else {
 137                 b = rawbyteslice(len(s))
 138         }
 139         copy(b, s)
 140         return b
 141 }
 142
 143 func stringtoslicebytetmp(s string) []byte {
 144         // Return a slice referring to the actual string bytes.
 145         // This is only for use by internal compiler optimizations
 146         // that know that the slice won't be mutated.
 147         // The only such case today is:
 148         // for i, c := range []byte(str)
 149
 150         str := (*stringStruct)(unsafe.Pointer(&s))
 151         ret := slice{array: unsafe.Pointer(str.str), len: str.len, cap: str.len}
 152         return *(*[]byte)(unsafe.Pointer(&ret))
 153 }
 154
 155 func stringtoslicerune(buf *[tmpStringBufSize]rune, s string) []rune {
 156         // two passes.
 157         // unlike slicerunetostring, no race because strings are immutable.
 158         n := 0
 159         t := s
 160         for len(s) > 0 {
 161                 _, k := charntorune(s)
 162                 s = s[k:]
 163                 n++
 164         }
 165         var a []rune
 166         if buf != nil && n <= len(buf) {
 167                 a = buf[:n]
 168         } else {
 169                 a = rawruneslice(n)
 170         }
 171         n = 0
 172         for len(t) > 0 {
 173                 r, k := charntorune(t)
 174                 t = t[k:]
 175                 a[n] = r
 176                 n++
 177         }
 178         return a
 179 }
 180
 181 func slicerunetostring(buf *tmpBuf, a []rune) string {
 182         if raceenabled && len(a) > 0 {
 183                 racereadrangepc(unsafe.Pointer(&a[0]),
 184                         uintptr(len(a))*unsafe.Sizeof(a[0]),
 185                         getcallerpc(unsafe.Pointer(&a)),
 186                         funcPC(slicerunetostring))
 187         }
 188         var dum [4]byte
 189         size1 := 0
 190         for _, r := range a {
 191                 size1 += runetochar(dum[:], r)
 192         }
 193         s, b := rawstringtmp(buf, size1+3)
 194         size2 := 0
 195         for _, r := range a {
 196                 // check for race
 197                 if size2 >= size1 {
 198                         break
 199                 }
 200                 size2 += runetochar(b[size2:], r)
 201         }
 202         return s[:size2]
 203 }
 204
 205 type stringStruct struct {
 206         str unsafe.Pointer
 207         len int
 208 }
 209
 210 func intstring(buf *[4]byte, v int64) string {
 211         var s string
 212         var b []byte
 213         if buf != nil {
 214                 b = buf[:]
 215                 s = slicebytetostringtmp(b)
 216         } else {
 217                 s, b = rawstring(4)
 218         }
 219         n := runetochar(b, rune(v))
 220         return s[:n]
 221 }
 222
 223 // stringiter returns the index of the next
 224 // rune after the rune that starts at s[k].
 225 func stringiter(s string, k int) int {
 226         if k >= len(s) {
 227                 // 0 is end of iteration
 228                 return 0
 229         }
 230
 231         c := s[k]
 232         if c < runeself {
 233                 return k + 1
 234         }
 235
 236         // multi-char rune
 237         _, n := charntorune(s[k:])
 238         return k + n
 239 }
 240
 241 // stringiter2 returns the rune that starts at s[k]
 242 // and the index where the next rune starts.
 243 func stringiter2(s string, k int) (int, rune) {
 244         if k >= len(s) {
 245                 // 0 is end of iteration
 246                 return 0, 0
 247         }
 248
 249         c := s[k]
 250         if c < runeself {
 251                 return k + 1, rune(c)
 252         }
 253
 254         // multi-char rune
 255         r, n := charntorune(s[k:])
 256         return k + n, r
 257 }
 258
 259 // rawstring allocates storage for a new string. The returned
 260 // string and byte slice both refer to the same storage.
 261 // The storage is not zeroed. Callers should use
 262 // b to set the string contents and then drop b.
 263 func rawstring(size int) (s string, b []byte) {
 264         p := mallocgc(uintptr(size), nil, flagNoScan|flagNoZero)
 265
 266         (*stringStruct)(unsafe.Pointer(&s)).str = p
 267         (*stringStruct)(unsafe.Pointer(&s)).len = size
 268
 269         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}
 270
 271         for {
 272                 ms := maxstring
 273                 if uintptr(size) <= uintptr(ms) || casuintptr((*uintptr)(unsafe.Pointer(&maxstring)), uintptr(ms), uintptr(size)) {
 274                         return
 275                 }
 276         }
 277 }
 278
 279 // rawbyteslice allocates a new byte slice. The byte slice is not zeroed.
 280 func rawbyteslice(size int) (b []byte) {
 281         cap := roundupsize(uintptr(size))
 282         p := mallocgc(cap, nil, flagNoScan|flagNoZero)
 283         if cap != uintptr(size) {
 284                 memclr(add(p, uintptr(size)), cap-uintptr(size))
 285         }
 286
 287         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, int(cap)}
 288         return
 289 }
 290
 291 // rawruneslice allocates a new rune slice. The rune slice is not zeroed.
 292 func rawruneslice(size int) (b []rune) {
 293         if uintptr(size) > _MaxMem/4 {
 294                 throw("out of memory")
 295         }
 296         mem := roundupsize(uintptr(size) * 4)
 297         p := mallocgc(mem, nil, flagNoScan|flagNoZero)
 298         if mem != uintptr(size)*4 {
 299                 memclr(add(p, uintptr(size)*4), mem-uintptr(size)*4)
 300         }
 301
 302         *(*slice)(unsafe.Pointer(&b)) = slice{p, size, int(mem / 4)}
 303         return
 304 }
 305
 306 // used by cmd/cgo
 307 func gobytes(p *byte, n int) []byte {
 308         if n == 0 {
 309                 return make([]byte, 0)
 310         }
 311         x := make([]byte, n)
 312         memmove(unsafe.Pointer(&x[0]), unsafe.Pointer(p), uintptr(n))
 313         return x
 314 }
 315
 316 func gostring(p *byte) string {
 317         l := findnull(p)
 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 gostringn(p *byte, l int) string {
 327         if l == 0 {
 328                 return ""
 329         }
 330         s, b := rawstring(l)
 331         memmove(unsafe.Pointer(&b[0]), unsafe.Pointer(p), uintptr(l))
 332         return s
 333 }
 334
 335 func index(s, t string) int {
 336         if len(t) == 0 {
 337                 return 0
 338         }
 339         for i := 0; i < len(s); i++ {
 340                 if s[i] == t[0] && hasprefix(s[i:], t) {
 341                         return i
 342                 }
 343         }
 344         return -1
 345 }
 346
 347 func contains(s, t string) bool {
 348         return index(s, t) >= 0
 349 }
 350
 351 func hasprefix(s, t string) bool {
 352         return len(s) >= len(t) && s[:len(t)] == t
 353 }
 354
 355 func atoi(s string) int {
 356         n := 0
 357         for len(s) > 0 && '0' <= s[0] && s[0] <= '9' {
 358                 n = n*10 + int(s[0]) - '0'
 359                 s = s[1:]
 360         }
 361         return n
 362 }
 363
 364 //go:nosplit
 365 func findnull(s *byte) int {
 366         if s == nil {
 367                 return 0
 368         }
 369         p := (*[_MaxMem/2 - 1]byte)(unsafe.Pointer(s))
 370         l := 0
 371         for p[l] != 0 {
 372                 l++
 373         }
 374         return l
 375 }
 376
 377 func findnullw(s *uint16) int {
 378         if s == nil {
 379                 return 0
 380         }
 381         p := (*[_MaxMem/2/2 - 1]uint16)(unsafe.Pointer(s))
 382         l := 0
 383         for p[l] != 0 {
 384                 l++
 385         }
 386         return l
 387 }
 388
 389 var maxstring uintptr = 256 // a hint for print
 390
 391 //go:nosplit
 392 func gostringnocopy(str *byte) string {
 393         ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
 394         s := *(*string)(unsafe.Pointer(&ss))
 395         for {
 396                 ms := maxstring
 397                 if uintptr(len(s)) <= ms || casuintptr(&maxstring, ms, uintptr(len(s))) {
 398                         break
 399                 }
 400         }
 401         return s
 402 }
 403
 404 func gostringw(strw *uint16) string {
 405         var buf [8]byte
 406         str := (*[_MaxMem/2/2 - 1]uint16)(unsafe.Pointer(strw))
 407         n1 := 0
 408         for i := 0; str[i] != 0; i++ {
 409                 n1 += runetochar(buf[:], rune(str[i]))
 410         }
 411         s, b := rawstring(n1 + 4)
 412         n2 := 0
 413         for i := 0; str[i] != 0; i++ {
 414                 // check for race
 415                 if n2 >= n1 {
 416                         break
 417                 }
 418                 n2 += runetochar(b[n2:], rune(str[i]))
 419         }
 420         b[n2] = 0 // for luck
 421         return s[:n2]
 422 }