diff options
Diffstat (limited to 'src/pkg/utf8')
-rw-r--r-- | src/pkg/utf8/Makefile | 3 | ||||
-rw-r--r-- | src/pkg/utf8/string.go | 211 | ||||
-rw-r--r-- | src/pkg/utf8/string_test.go | 109 | ||||
-rw-r--r-- | src/pkg/utf8/utf8.go | 69 | ||||
-rw-r--r-- | src/pkg/utf8/utf8_test.go | 191 |
5 files changed, 533 insertions, 50 deletions
diff --git a/src/pkg/utf8/Makefile b/src/pkg/utf8/Makefile index a013913c3..b3574ba3b 100644 --- a/src/pkg/utf8/Makefile +++ b/src/pkg/utf8/Makefile @@ -2,10 +2,11 @@ # Use of this source code is governed by a BSD-style # license that can be found in the LICENSE file. -include ../../Make.$(GOARCH) +include ../../Make.inc TARG=utf8 GOFILES=\ + string.go\ utf8.go\ include ../../Make.pkg diff --git a/src/pkg/utf8/string.go b/src/pkg/utf8/string.go new file mode 100644 index 000000000..83b56b944 --- /dev/null +++ b/src/pkg/utf8/string.go @@ -0,0 +1,211 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package utf8 + +// String wraps a regular string with a small structure that provides more +// efficient indexing by code point index, as opposed to byte index. +// Scanning incrementally forwards or backwards is O(1) per index operation +// (although not as fast a range clause going forwards). Random access is +// O(N) in the length of the string, but the overhead is less than always +// scanning from the beginning. +// If the string is ASCII, random access is O(1). +// Unlike the built-in string type, String has internal mutable state and +// is not thread-safe. +type String struct { + str string + numRunes int + // If width > 0, the rune at runePos starts at bytePos and has the specified width. + width int + bytePos int + runePos int + nonASCII int // byte index of the first non-ASCII rune. +} + +// NewString returns a new UTF-8 string with the provided contents. +func NewString(contents string) *String { + return new(String).Init(contents) +} + +// Init initializes an existing String to hold the provided contents. +// It returns a pointer to the initialized String. +func (s *String) Init(contents string) *String { + s.str = contents + s.bytePos = 0 + s.runePos = 0 + for i := 0; i < len(contents); i++ { + if contents[i] >= RuneSelf { + // Not ASCII. + s.numRunes = RuneCountInString(contents) + _, s.width = DecodeRuneInString(contents) + s.nonASCII = i + return s + } + } + // ASCII is simple. Also, the empty string is ASCII. + s.numRunes = len(contents) + s.width = 0 + s.nonASCII = len(contents) + return s +} + +// String returns the contents of the String. This method also means the +// String is directly printable by fmt.Print. +func (s *String) String() string { + return s.str +} + +// RuneCount returns the number of runes (Unicode code points) in the String. +func (s *String) RuneCount() int { + return s.numRunes +} + +// IsASCII returns a boolean indicating whether the String contains only ASCII bytes. +func (s *String) IsASCII() bool { + return s.width == 0 +} + +// Slice returns the string sliced at rune positions [i:j]. +func (s *String) Slice(i, j int) string { + // ASCII is easy. Let the compiler catch the indexing error if there is one. + if j < s.nonASCII { + return s.str[i:j] + } + if i < 0 || j > s.numRunes || i > j { + panic(sliceOutOfRange) + } + if i == j { + return "" + } + // For non-ASCII, after At(i), bytePos is always the position of the indexed character. + var low, high int + switch { + case i < s.nonASCII: + low = i + case i == s.numRunes: + low = len(s.str) + default: + s.At(i) + low = s.bytePos + } + switch { + case j == s.numRunes: + high = len(s.str) + default: + s.At(j) + high = s.bytePos + } + return s.str[low:high] +} + +// At returns the rune with index i in the String. The sequence of runes is the same +// as iterating over the contents with a "for range" clause. +func (s *String) At(i int) int { + // ASCII is easy. Let the compiler catch the indexing error if there is one. + if i < s.nonASCII { + return int(s.str[i]) + } + + // Now we do need to know the index is valid. + if i < 0 || i >= s.numRunes { + panic(outOfRange) + } + + var rune int + + // Five easy common cases: within 1 spot of bytePos/runePos, or the beginning, or the end. + // With these cases, all scans from beginning or end work in O(1) time per rune. + switch { + + case i == s.runePos-1: // backing up one rune + rune, s.width = DecodeLastRuneInString(s.str[0:s.bytePos]) + s.runePos = i + s.bytePos -= s.width + return rune + case i == s.runePos+1: // moving ahead one rune + s.runePos = i + s.bytePos += s.width + fallthrough + case i == s.runePos: + rune, s.width = DecodeRuneInString(s.str[s.bytePos:]) + return rune + case i == 0: // start of string + rune, s.width = DecodeRuneInString(s.str) + s.runePos = 0 + s.bytePos = 0 + return rune + + case i == s.numRunes-1: // last rune in string + rune, s.width = DecodeLastRuneInString(s.str) + s.runePos = i + s.bytePos = len(s.str) - s.width + return rune + } + + // We need to do a linear scan. There are three places to start from: + // 1) The beginning + // 2) bytePos/runePos. + // 3) The end + // Choose the closest in rune count, scanning backwards if necessary. + forward := true + if i < s.runePos { + // Between beginning and pos. Which is closer? + // Since both i and runePos are guaranteed >= nonASCII, that's the + // lowest location we need to start from. + if i < (s.runePos-s.nonASCII)/2 { + // Scan forward from beginning + s.bytePos, s.runePos = s.nonASCII, s.nonASCII + } else { + // Scan backwards from where we are + forward = false + } + } else { + // Between pos and end. Which is closer? + if i-s.runePos < (s.numRunes-s.runePos)/2 { + // Scan forward from pos + } else { + // Scan backwards from end + s.bytePos, s.runePos = len(s.str), s.numRunes + forward = false + } + } + if forward { + // TODO: Is it much faster to use a range loop for this scan? + for { + rune, s.width = DecodeRuneInString(s.str[s.bytePos:]) + if s.runePos == i { + break + } + s.runePos++ + s.bytePos += s.width + } + } else { + for { + rune, s.width = DecodeLastRuneInString(s.str[0:s.bytePos]) + s.runePos-- + s.bytePos -= s.width + if s.runePos == i { + break + } + } + } + return rune +} + +// We want the panic in At(i) to satisfy os.Error, because that's what +// runtime panics satisfy, but we can't import os. This is our solution. + +// error is the type of the error returned if a user calls String.At(i) with i out of range. +// It satisfies os.Error and runtime.Error. +type error string + +func (err error) String() string { + return string(err) +} + +func (err error) RunTimeError() { +} + +var outOfRange = error("utf8.String: index out of range") +var sliceOutOfRange = error("utf8.String: slice index out of range") diff --git a/src/pkg/utf8/string_test.go b/src/pkg/utf8/string_test.go new file mode 100644 index 000000000..9dd847247 --- /dev/null +++ b/src/pkg/utf8/string_test.go @@ -0,0 +1,109 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package utf8_test + +import ( + "rand" + "testing" + . "utf8" +) + +func TestScanForwards(t *testing.T) { + for _, s := range testStrings { + runes := []int(s) + str := NewString(s) + if str.RuneCount() != len(runes) { + t.Errorf("%s: expected %d runes; got %d", s, len(runes), str.RuneCount()) + break + } + for i, expect := range runes { + got := str.At(i) + if got != expect { + t.Errorf("%s[%d]: expected %c (%U); got %c (%U)", s, i, expect, expect, got, got) + } + } + } +} + +func TestScanBackwards(t *testing.T) { + for _, s := range testStrings { + runes := []int(s) + str := NewString(s) + if str.RuneCount() != len(runes) { + t.Errorf("%s: expected %d runes; got %d", s, len(runes), str.RuneCount()) + break + } + for i := len(runes) - 1; i >= 0; i-- { + expect := runes[i] + got := str.At(i) + if got != expect { + t.Errorf("%s[%d]: expected %c (%U); got %c (%U)", s, i, expect, expect, got, got) + } + } + } +} + +const randCount = 100000 + +func TestRandomAccess(t *testing.T) { + for _, s := range testStrings { + if len(s) == 0 { + continue + } + runes := []int(s) + str := NewString(s) + if str.RuneCount() != len(runes) { + t.Errorf("%s: expected %d runes; got %d", s, len(runes), str.RuneCount()) + break + } + for j := 0; j < randCount; j++ { + i := rand.Intn(len(runes)) + expect := runes[i] + got := str.At(i) + if got != expect { + t.Errorf("%s[%d]: expected %c (%U); got %c (%U)", s, i, expect, expect, got, got) + } + } + } +} + +func TestRandomSliceAccess(t *testing.T) { + for _, s := range testStrings { + if len(s) == 0 || s[0] == '\x80' { // the bad-UTF-8 string fools this simple test + continue + } + runes := []int(s) + str := NewString(s) + if str.RuneCount() != len(runes) { + t.Errorf("%s: expected %d runes; got %d", s, len(runes), str.RuneCount()) + break + } + for k := 0; k < randCount; k++ { + i := rand.Intn(len(runes)) + j := rand.Intn(len(runes) + 1) + if i > j { // include empty strings + continue + } + expect := string(runes[i:j]) + got := str.Slice(i, j) + if got != expect { + t.Errorf("%s[%d:%d]: expected %q got %q", s, i, j, expect, got) + } + } + } +} + +func TestLimitSliceAccess(t *testing.T) { + for _, s := range testStrings { + str := NewString(s) + if str.Slice(0, 0) != "" { + t.Error("failure with empty slice at beginning") + } + nr := RuneCountInString(s) + if str.Slice(nr, nr) != "" { + t.Error("failure with empty slice at end") + } + } +} diff --git a/src/pkg/utf8/utf8.go b/src/pkg/utf8/utf8.go index 8e373e32d..455499e4d 100644 --- a/src/pkg/utf8/utf8.go +++ b/src/pkg/utf8/utf8.go @@ -209,6 +209,73 @@ func DecodeRuneInString(s string) (rune, size int) { return } +// DecodeLastRune unpacks the last UTF-8 encoding in p +// and returns the rune and its width in bytes. +func DecodeLastRune(p []byte) (rune, size int) { + end := len(p) + if end == 0 { + return RuneError, 0 + } + start := end - 1 + rune = int(p[start]) + if rune < RuneSelf { + return rune, 1 + } + // guard against O(n^2) behavior when traversing + // backwards through strings with long sequences of + // invalid UTF-8. + lim := end - UTFMax + if lim < 0 { + lim = 0 + } + for start--; start >= lim; start-- { + if RuneStart(p[start]) { + break + } + } + if start < 0 { + start = 0 + } + rune, size = DecodeRune(p[start:end]) + if start+size != end { + return RuneError, 1 + } + return rune, size +} + +// DecodeLastRuneInString is like DecodeLastRune but its input is a string. +func DecodeLastRuneInString(s string) (rune, size int) { + end := len(s) + if end == 0 { + return RuneError, 0 + } + start := end - 1 + rune = int(s[start]) + if rune < RuneSelf { + return rune, 1 + } + // guard against O(n^2) behavior when traversing + // backwards through strings with long sequences of + // invalid UTF-8. + lim := end - UTFMax + if lim < 0 { + lim = 0 + } + for start--; start >= lim; start-- { + if RuneStart(s[start]) { + break + } + } + if start < 0 { + start = 0 + } + rune, size = DecodeRuneInString(s[start:end]) + if start+size != end { + return RuneError, 1 + } + return rune, size +} + // RuneLen returns the number of bytes required to encode the rune. func RuneLen(rune int) int { switch { @@ -226,7 +293,7 @@ func RuneLen(rune int) int { // EncodeRune writes into p (which must be large enough) the UTF-8 encoding of the rune. // It returns the number of bytes written. -func EncodeRune(rune int, p []byte) int { +func EncodeRune(p []byte, rune int) int { // Negative values are erroneous. Making it unsigned addresses the problem. r := uint(rune) diff --git a/src/pkg/utf8/utf8_test.go b/src/pkg/utf8/utf8_test.go index 2466cf554..7a1db93e5 100644 --- a/src/pkg/utf8/utf8_test.go +++ b/src/pkg/utf8/utf8_test.go @@ -16,51 +16,53 @@ type Utf8Map struct { } var utf8map = []Utf8Map{ - Utf8Map{0x0000, "\x00"}, - Utf8Map{0x0001, "\x01"}, - Utf8Map{0x007e, "\x7e"}, - Utf8Map{0x007f, "\x7f"}, - Utf8Map{0x0080, "\xc2\x80"}, - Utf8Map{0x0081, "\xc2\x81"}, - Utf8Map{0x00bf, "\xc2\xbf"}, - Utf8Map{0x00c0, "\xc3\x80"}, - Utf8Map{0x00c1, "\xc3\x81"}, - Utf8Map{0x00c8, "\xc3\x88"}, - Utf8Map{0x00d0, "\xc3\x90"}, - Utf8Map{0x00e0, "\xc3\xa0"}, - Utf8Map{0x00f0, "\xc3\xb0"}, - Utf8Map{0x00f8, "\xc3\xb8"}, - Utf8Map{0x00ff, "\xc3\xbf"}, - Utf8Map{0x0100, "\xc4\x80"}, - Utf8Map{0x07ff, "\xdf\xbf"}, - Utf8Map{0x0800, "\xe0\xa0\x80"}, - Utf8Map{0x0801, "\xe0\xa0\x81"}, - Utf8Map{0xfffe, "\xef\xbf\xbe"}, - Utf8Map{0xffff, "\xef\xbf\xbf"}, - Utf8Map{0x10000, "\xf0\x90\x80\x80"}, - Utf8Map{0x10001, "\xf0\x90\x80\x81"}, - Utf8Map{0x10fffe, "\xf4\x8f\xbf\xbe"}, - Utf8Map{0x10ffff, "\xf4\x8f\xbf\xbf"}, - Utf8Map{0xFFFD, "\xef\xbf\xbd"}, -} - -// strings.Bytes with one extra byte at end -func makeBytes(s string) []byte { - s += "\x00" - b := []byte(s) - return b[0 : len(s)-1] + {0x0000, "\x00"}, + {0x0001, "\x01"}, + {0x007e, "\x7e"}, + {0x007f, "\x7f"}, + {0x0080, "\xc2\x80"}, + {0x0081, "\xc2\x81"}, + {0x00bf, "\xc2\xbf"}, + {0x00c0, "\xc3\x80"}, + {0x00c1, "\xc3\x81"}, + {0x00c8, "\xc3\x88"}, + {0x00d0, "\xc3\x90"}, + {0x00e0, "\xc3\xa0"}, + {0x00f0, "\xc3\xb0"}, + {0x00f8, "\xc3\xb8"}, + {0x00ff, "\xc3\xbf"}, + {0x0100, "\xc4\x80"}, + {0x07ff, "\xdf\xbf"}, + {0x0800, "\xe0\xa0\x80"}, + {0x0801, "\xe0\xa0\x81"}, + {0xfffe, "\xef\xbf\xbe"}, + {0xffff, "\xef\xbf\xbf"}, + {0x10000, "\xf0\x90\x80\x80"}, + {0x10001, "\xf0\x90\x80\x81"}, + {0x10fffe, "\xf4\x8f\xbf\xbe"}, + {0x10ffff, "\xf4\x8f\xbf\xbf"}, + {0xFFFD, "\xef\xbf\xbd"}, +} + +var testStrings = []string{ + "", + "abcd", + "☺☻☹", + "日a本b語ç日ð本Ê語þ日¥本¼語i日©", + "日a本b語ç日ð本Ê語þ日¥本¼語i日©日a本b語ç日ð本Ê語þ日¥本¼語i日©日a本b語ç日ð本Ê語þ日¥本¼語i日©", + "\x80\x80\x80\x80", } func TestFullRune(t *testing.T) { for i := 0; i < len(utf8map); i++ { m := utf8map[i] - b := makeBytes(m.str) + b := []byte(m.str) if !FullRune(b) { - t.Errorf("FullRune(%q) (rune %04x) = false, want true", b, m.rune) + t.Errorf("FullRune(%q) (%U) = false, want true", b, m.rune) } s := m.str if !FullRuneInString(s) { - t.Errorf("FullRuneInString(%q) (rune %04x) = false, want true", s, m.rune) + t.Errorf("FullRuneInString(%q) (%U) = false, want true", s, m.rune) } b1 := b[0 : len(b)-1] if FullRune(b1) { @@ -76,9 +78,9 @@ func TestFullRune(t *testing.T) { func TestEncodeRune(t *testing.T) { for i := 0; i < len(utf8map); i++ { m := utf8map[i] - b := makeBytes(m.str) + b := []byte(m.str) var buf [10]byte - n := EncodeRune(m.rune, buf[0:]) + n := EncodeRune(buf[0:], m.rune) b1 := buf[0:n] if !bytes.Equal(b, b1) { t.Errorf("EncodeRune(%#04x) = %q want %q", m.rune, b1, b) @@ -89,7 +91,7 @@ func TestEncodeRune(t *testing.T) { func TestDecodeRune(t *testing.T) { for i := 0; i < len(utf8map); i++ { m := utf8map[i] - b := makeBytes(m.str) + b := []byte(m.str) rune, size := DecodeRune(b) if rune != m.rune || size != len(b) { t.Errorf("DecodeRune(%q) = %#04x, %d want %#04x, %d", b, rune, size, m.rune, len(b)) @@ -141,15 +143,108 @@ func TestDecodeRune(t *testing.T) { if rune != RuneError || size != 1 { t.Errorf("DecodeRuneInString(%q) = %#04x, %d want %#04x, %d", s, rune, size, RuneError, 1) } + + } +} + +// Check that DecodeRune and DecodeLastRune correspond to +// the equivalent range loop. +func TestSequencing(t *testing.T) { + for _, ts := range testStrings { + for _, m := range utf8map { + for _, s := range []string{ts + m.str, m.str + ts, ts + m.str + ts} { + testSequence(t, s) + } + } + } +} + +// Check that a range loop and a []int conversion visit the same runes. +// Not really a test of this package, but the assumption is used here and +// it's good to verify +func TestIntConversion(t *testing.T) { + for _, ts := range testStrings { + runes := []int(ts) + if RuneCountInString(ts) != len(runes) { + t.Errorf("%q: expected %d runes; got %d", ts, len(runes), RuneCountInString(ts)) + break + } + i := 0 + for _, r := range ts { + if r != runes[i] { + t.Errorf("%q[%d]: expected %c (%U); got %c (%U)", ts, i, runes[i], runes[i], r, r) + } + i++ + } + } +} + +func testSequence(t *testing.T, s string) { + type info struct { + index int + rune int + } + index := make([]info, len(s)) + b := []byte(s) + si := 0 + j := 0 + for i, r := range s { + if si != i { + t.Errorf("Sequence(%q) mismatched index %d, want %d", s, si, i) + return + } + index[j] = info{i, r} + j++ + rune1, size1 := DecodeRune(b[i:]) + if r != rune1 { + t.Errorf("DecodeRune(%q) = %#04x, want %#04x", s[i:], rune1, r) + return + } + rune2, size2 := DecodeRuneInString(s[i:]) + if r != rune2 { + t.Errorf("DecodeRuneInString(%q) = %#04x, want %#04x", s[i:], rune2, r) + return + } + if size1 != size2 { + t.Errorf("DecodeRune/DecodeRuneInString(%q) size mismatch %d/%d", s[i:], size1, size2) + return + } + si += size1 + } + j-- + for si = len(s); si > 0; { + rune1, size1 := DecodeLastRune(b[0:si]) + rune2, size2 := DecodeLastRuneInString(s[0:si]) + if size1 != size2 { + t.Errorf("DecodeLastRune/DecodeLastRuneInString(%q, %d) size mismatch %d/%d", s, si, size1, size2) + return + } + if rune1 != index[j].rune { + t.Errorf("DecodeLastRune(%q, %d) = %#04x, want %#04x", s, si, rune1, index[j].rune) + return + } + if rune2 != index[j].rune { + t.Errorf("DecodeLastRuneInString(%q, %d) = %#04x, want %#04x", s, si, rune2, index[j].rune) + return + } + si -= size1 + if si != index[j].index { + t.Errorf("DecodeLastRune(%q) index mismatch at %d, want %d", s, si, index[j].index) + return + } + j-- + } + if si != 0 { + t.Errorf("DecodeLastRune(%q) finished at %d, not 0", s, si) } } // Check that negative runes encode as U+FFFD. func TestNegativeRune(t *testing.T) { errorbuf := make([]byte, UTFMax) - errorbuf = errorbuf[0:EncodeRune(RuneError, errorbuf)] + errorbuf = errorbuf[0:EncodeRune(errorbuf, RuneError)] buf := make([]byte, UTFMax) - buf = buf[0:EncodeRune(-1, buf)] + buf = buf[0:EncodeRune(buf, -1)] if !bytes.Equal(buf, errorbuf) { t.Errorf("incorrect encoding [% x] for -1; expected [% x]", buf, errorbuf) } @@ -161,10 +256,10 @@ type RuneCountTest struct { } var runecounttests = []RuneCountTest{ - RuneCountTest{"abcd", 4}, - RuneCountTest{"☺☻☹", 3}, - RuneCountTest{"1,2,3,4", 7}, - RuneCountTest{"\xe2\x00", 2}, + {"abcd", 4}, + {"☺☻☹", 3}, + {"1,2,3,4", 7}, + {"\xe2\x00", 2}, } func TestRuneCount(t *testing.T) { @@ -173,7 +268,7 @@ func TestRuneCount(t *testing.T) { if out := RuneCountInString(tt.in); out != tt.out { t.Errorf("RuneCountInString(%q) = %d, want %d", tt.in, out, tt.out) } - if out := RuneCount(makeBytes(tt.in)); out != tt.out { + if out := RuneCount([]byte(tt.in)); out != tt.out { t.Errorf("RuneCount(%q) = %d, want %d", tt.in, out, tt.out) } } @@ -194,14 +289,14 @@ func BenchmarkRuneCountTenJapaneseChars(b *testing.B) { func BenchmarkEncodeASCIIRune(b *testing.B) { buf := make([]byte, UTFMax) for i := 0; i < b.N; i++ { - EncodeRune('a', buf) + EncodeRune(buf, 'a') } } func BenchmarkEncodeJapaneseRune(b *testing.B) { buf := make([]byte, UTFMax) for i := 0; i < b.N; i++ { - EncodeRune('本', buf) + EncodeRune(buf, '本') } } |