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

View as plain text