Source: replace.go in package strings


package strings

import (
	"io"
	"sync"
)

Replacer replaces a list of strings with replacements. It is safe for concurrent use by multiple goroutines.

type Replacer struct {
	once   sync.Once // guards buildOnce method
	r      replacer
	oldnew []string
}

replacer is the interface that a replacement algorithm needs to implement.

type replacer interface {
	Replace(s string) string
	WriteString(w io.Writer, s string) (n int, err error)
}

NewReplacer returns a new Replacer from a list of old, new string pairs. Replacements are performed in the order they appear in the target string, without overlapping matches. The old string comparisons are done in argument order. NewReplacer panics if given an odd number of arguments.

func NewReplacer(oldnew ...string) *Replacer {
	if len(oldnew)%2 == 1 {
		panic("strings.NewReplacer: odd argument count")
	}
	return &Replacer{oldnew: append([]string(nil), oldnew...)}
}

func (r *Replacer) buildOnce() {
	r.r = r.build()
	r.oldnew = nil
}

func (b *Replacer) build() replacer {
	oldnew := b.oldnew
	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
		return makeSingleStringReplacer(oldnew[0], oldnew[1])
	}

	allNewBytes := true
	for i := 0; i < len(oldnew); i += 2 {
		if len(oldnew[i]) != 1 {
			return makeGenericReplacer(oldnew)
		}
		if len(oldnew[i+1]) != 1 {
			allNewBytes = false
		}
	}

	if allNewBytes {
		r := byteReplacer{}
		for i := range r {
			r[i] = byte(i)

The first occurrence of old->new map takes precedence over the others with the same old string.

		for i := len(oldnew) - 2; i >= 0; i -= 2 {
			o := oldnew[i][0]
			n := oldnew[i+1][0]
			r[o] = n
		}
		return &r
	}

The first occurrence of old->new map takes precedence over the others with the same old string.

	for i := len(oldnew) - 2; i >= 0; i -= 2 {
		o := oldnew[i][0]

To avoid counting repetitions multiple times.

We need to use string([]byte{o}) instead of string(o), to avoid utf8 encoding of o. E. g. byte(150) produces string of length 2.

			r.toReplace = append(r.toReplace, string([]byte{o}))
		}
		r.replacements[o] = []byte(n)

	}
	return &r
}

Replace returns a copy of s with all replacements performed.

func (r *Replacer) Replace(s string) string {
	r.once.Do(r.buildOnce)
	return r.r.Replace(s)
}

WriteString writes s to w with all replacements performed.

func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) {
	r.once.Do(r.buildOnce)
	return r.r.WriteString(w, s)
}

trieNode is a node in a lookup trie for prioritized key/value pairs. Keys and values may be empty. For example, the trie containing keys "ax", "ay", "bcbc", "x" and "xy" could have eight nodes: n0 - n1 a- n2 .x+ n3 .y+ n4 b- n5 .cbc+ n6 x+ n7 .y+ n0 is the root node, and its children are n1, n4 and n6; n1's children are n2 and n3; n4's child is n5; n6's child is n7. Nodes n0, n1 and n4 (marked with a trailing "-") are partial keys, and nodes n2, n3, n5, n6 and n7 (marked with a trailing "+") are complete keys.

value is the value of the trie node's key/value pair. It is empty if this node is not a complete key.

priority is the priority (higher is more important) of the trie node's key/value pair; keys are not necessarily matched shortest- or longest- first. Priority is positive if this node is a complete key, and zero otherwise. In the example above, positive/zero priorities are marked with a trailing "+" or "-".

	priority int

A trie node may have zero, one or more child nodes: * if the remaining fields are zero, there are no children. * if prefix and next are non-zero, there is one child in next. * if table is non-zero, it defines all the children. Prefixes are preferred over tables when there is one child, but the root node always uses a table for lookup efficiency.

prefix is the difference in keys between this trie node and the next. In the example above, node n4 has prefix "cbc" and n4's next node is n5. Node n5 has no children and so has zero prefix, next and table fields.

	prefix string
	next   *trieNode

table is a lookup table indexed by the next byte in the key, after remapping that byte through genericReplacer.mapping to create a dense index. In the example above, the keys only use 'a', 'b', 'c', 'x' and 'y', which remap to 0, 1, 2, 3 and 4. All other bytes remap to 5, and genericReplacer.tableSize will be 5. Node n0's table will be []*trieNode{ 0:n1, 1:n4, 3:n6 }, where the 0, 1 and 3 are the remapped 'a', 'b' and 'x'.

	table []*trieNode
}

func (t *trieNode) add(key, val string, priority int, r *genericReplacer) {
	if key == "" {
		if t.priority == 0 {
			t.value = val
			t.priority = priority
		}
		return
	}

Need to split the prefix among multiple nodes.

		var n int // length of the longest common prefix
		for ; n < len(t.prefix) && n < len(key); n++ {
			if t.prefix[n] != key[n] {
				break
			}
		}
		if n == len(t.prefix) {
			t.next.add(key[n:], val, priority, r)

First byte differs, start a new lookup table here. Looking up what is currently t.prefix[0] will lead to prefixNode, and looking up key[0] will lead to keyNode.

			var prefixNode *trieNode
			if len(t.prefix) == 1 {
				prefixNode = t.next
			} else {
				prefixNode = &trieNode{
					prefix: t.prefix[1:],
					next:   t.next,
				}
			}
			keyNode := new(trieNode)
			t.table = make([]*trieNode, r.tableSize)
			t.table[r.mapping[t.prefix[0]]] = prefixNode
			t.table[r.mapping[key[0]]] = keyNode
			t.prefix = ""
			t.next = nil
			keyNode.add(key[1:], val, priority, r)

Insert new node after the common section of the prefix.

			next := &trieNode{
				prefix: t.prefix[n:],
				next:   t.next,
			}
			t.prefix = t.prefix[:n]
			t.next = next
			next.add(key[n:], val, priority, r)
		}

Insert into existing table.

		m := r.mapping[key[0]]
		if t.table[m] == nil {
			t.table[m] = new(trieNode)
		}
		t.table[m].add(key[1:], val, priority, r)
	} else {
		t.prefix = key
		t.next = new(trieNode)
		t.next.add("", val, priority, r)
	}
}

Iterate down the trie to the end, and grab the value and keylen with the highest priority.

	bestPriority := 0
	node := &r.root
	n := 0
	for node != nil {
		if node.priority > bestPriority && !(ignoreRoot && node == &r.root) {
			bestPriority = node.priority
			val = node.value
			keylen = n
			found = true
		}

		if s == "" {
			break
		}
		if node.table != nil {
			index := r.mapping[s[0]]
			if int(index) == r.tableSize {
				break
			}
			node = node.table[index]
			s = s[1:]
			n++
		} else if node.prefix != "" && HasPrefix(s, node.prefix) {
			n += len(node.prefix)
			s = s[len(node.prefix):]
			node = node.next
		} else {
			break
		}
	}
	return
}

genericReplacer is the fully generic algorithm. It's used as a fallback when nothing faster can be used.

type genericReplacer struct {

tableSize is the size of a trie node's lookup table. It is the number of unique key bytes.

mapping maps from key bytes to a dense index for trieNode.table.

	mapping [256]byte
}

func makeGenericReplacer(oldnew []string) *genericReplacer {

Find each byte used, then assign them each an index.

	for i := 0; i < len(oldnew); i += 2 {
		key := oldnew[i]
		for j := 0; j < len(key); j++ {
			r.mapping[key[j]] = 1
		}
	}

	for _, b := range r.mapping {
		r.tableSize += int(b)
	}

	var index byte
	for i, b := range r.mapping {
		if b == 0 {
			r.mapping[i] = byte(r.tableSize)
		} else {
			r.mapping[i] = index
			index++
		}

Ensure root node uses a lookup table (for performance).

	r.root.table = make([]*trieNode, r.tableSize)

	for i := 0; i < len(oldnew); i += 2 {
		r.root.add(oldnew[i], oldnew[i+1], len(oldnew)-i, r)
	}
	return r
}

type appendSliceWriter []byte

Write writes to the buffer to satisfy io.Writer.

func (w *appendSliceWriter) Write(p []byte) (int, error) {
	*w = append(*w, p...)
	return len(p), nil
}

WriteString writes to the buffer without string->[]byte->string allocations.

func (w *appendSliceWriter) WriteString(s string) (int, error) {
	*w = append(*w, s...)
	return len(s), nil
}

type stringWriter struct {
	w io.Writer
}

func (w stringWriter) WriteString(s string) (int, error) {
	return w.w.Write([]byte(s))
}

func getStringWriter(w io.Writer) io.StringWriter {
	sw, ok := w.(io.StringWriter)
	if !ok {
		sw = stringWriter{w}
	}
	return sw
}

func (r *genericReplacer) Replace(s string) string {
	buf := make(appendSliceWriter, 0, len(s))
	r.WriteString(&buf, s)
	return string(buf)
}

func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var last, wn int
	var prevMatchEmpty bool

Fast path: s[i] is not a prefix of any pattern.

		if i != len(s) && r.root.priority == 0 {
			index := int(r.mapping[s[i]])
			if index == r.tableSize || r.root.table[index] == nil {
				i++
				continue
			}
		}

Ignore the empty match iff the previous loop found the empty match.

		val, keylen, match := r.lookup(s[i:], prevMatchEmpty)
		prevMatchEmpty = match && keylen == 0
		if match {
			wn, err = sw.WriteString(s[last:i])
			n += wn
			if err != nil {
				return
			}
			wn, err = sw.WriteString(val)
			n += wn
			if err != nil {
				return
			}
			i += keylen
			last = i
			continue
		}
		i++
	}
	if last != len(s) {
		wn, err = sw.WriteString(s[last:])
		n += wn
	}
	return
}

singleStringReplacer is the implementation that's used when there is only one string to replace (and that string has more than one byte).

type singleStringReplacer struct {

value is the new string that replaces that pattern when it's found.

	value string
}

func makeSingleStringReplacer(pattern string, value string) *singleStringReplacer {
	return &singleStringReplacer{finder: makeStringFinder(pattern), value: value}
}

func (r *singleStringReplacer) Replace(s string) string {
	var buf []byte
	i, matched := 0, false
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		matched = true
		buf = append(buf, s[i:i+match]...)
		buf = append(buf, r.value...)
		i += match + len(r.finder.pattern)
	}
	if !matched {
		return s
	}
	buf = append(buf, s[i:]...)
	return string(buf)
}

func (r *singleStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var i, wn int
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		wn, err = sw.WriteString(s[i : i+match])
		n += wn
		if err != nil {
			return
		}
		wn, err = sw.WriteString(r.value)
		n += wn
		if err != nil {
			return
		}
		i += match + len(r.finder.pattern)
	}
	wn, err = sw.WriteString(s[i:])
	n += wn
	return
}

byteReplacer is the implementation that's used when all the "old" and "new" values are single ASCII bytes. The array contains replacement bytes indexed by old byte.

type byteReplacer [256]byte

func (r *byteReplacer) Replace(s string) string {
	var buf []byte // lazily allocated
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r[b] != b {
			if buf == nil {
				buf = []byte(s)
			}
			buf[i] = r[b]
		}
	}
	if buf == nil {
		return s
	}
	return string(buf)
}

TODO(bradfitz): use io.WriteString with slices of s, avoiding allocation.

	bufsize := 32 << 10
	if len(s) < bufsize {
		bufsize = len(s)
	}
	buf := make([]byte, bufsize)

	for len(s) > 0 {
		ncopy := copy(buf, s)
		s = s[ncopy:]
		for i, b := range buf[:ncopy] {
			buf[i] = r[b]
		}
		wn, err := w.Write(buf[:ncopy])
		n += wn
		if err != nil {
			return n, err
		}
	}
	return n, nil
}

byteStringReplacer is the implementation that's used when all the "old" values are single ASCII bytes but the "new" values vary in size.

replacements contains replacement byte slices indexed by old byte. A nil []byte means that the old byte should not be replaced.

toReplace keeps a list of bytes to replace. Depending on length of toReplace and length of target string it may be faster to use Count, or a plain loop. We store single byte as a string, because Count takes a string.

	toReplace []string
}

countCutOff controls the ratio of a string length to a number of replacements at which (*byteStringReplacer).Replace switches algorithms. For strings with higher ration of length to replacements than that value, we call Count, for each replacement from toReplace. For strings, with a lower ratio we use simple loop, because of Count overhead. countCutOff is an empirically determined overhead multiplier. TODO(tocarip) revisit once we have register-based abi/mid-stack inlining.

const countCutOff = 8

func (r *byteStringReplacer) Replace(s string) string {
	newSize := len(s)

Is it faster to use Count?

	if len(r.toReplace)*countCutOff <= len(s) {
		for _, x := range r.toReplace {

The -1 is because we are replacing 1 byte with len(replacements[b]) bytes.

				newSize += c * (len(r.replacements[x[0]]) - 1)
				anyChanges = true
			}

		}
	} else {
		for i := 0; i < len(s); i++ {
			b := s[i]

See above for explanation of -1

				newSize += len(r.replacements[b]) - 1
				anyChanges = true
			}
		}
	}
	if !anyChanges {
		return s
	}
	buf := make([]byte, newSize)
	j := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] != nil {
			j += copy(buf[j:], r.replacements[b])
		} else {
			buf[j] = b
			j++
		}
	}
	return string(buf)
}

func (r *byteStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	last := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] == nil {
			continue
		}
		if last != i {
			nw, err := sw.WriteString(s[last:i])
			n += nw
			if err != nil {
				return n, err
			}
		}
		last = i + 1
		nw, err := w.Write(r.replacements[b])
		n += nw
		if err != nil {
			return n, err
		}
	}
	if last != len(s) {
		var nw int
		nw, err = sw.WriteString(s[last:])
		n += nw
	}
	return