blob: a2eedb9baa1b5462336b6cc0e85c84ab43f66832 [file] [log] [blame]
// Copyright 2016 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 text
import (
"bytes"
"fmt"
"image"
"io"
"io/ioutil"
"math/rand"
"reflect"
"sort"
"strings"
"testing"
"unicode/utf8"
"golang.org/x/image/font"
"golang.org/x/image/math/fixed"
)
func min(a, b int) int {
if a < b {
return a
}
return b
}
func readAllText(dst []byte, f *Frame) []byte {
for p := f.FirstParagraph(); p != nil; p = p.Next(f) {
for l := p.FirstLine(f); l != nil; l = l.Next(f) {
for b := l.FirstBox(f); b != nil; b = b.Next(f) {
dst = append(dst, b.Text(f)...)
}
}
}
return dst
}
func readAllRunes(dst []rune, rr io.RuneReader) ([]rune, error) {
for {
r, size, err := rr.ReadRune()
if err == io.EOF {
return dst, nil
}
if err != nil {
return nil, err
}
// Check that r and size are consistent.
if wantSize := utf8.RuneLen(r); size == wantSize {
// OK.
} else if r == utf8.RuneError && size == 1 {
// Also OK; one byte of invalid UTF-8 was replaced by '\ufffd'.
} else {
return nil, fmt.Errorf("rune %#x: got size %d, want %d", r, size, wantSize)
}
dst = append(dst, r)
}
}
func runesEqual(xs, ys []rune) bool {
if len(xs) != len(ys) {
return false
}
for i := range xs {
if xs[i] != ys[i] {
return false
}
}
return true
}
func allASCII(rs []rune) bool {
for _, r := range rs {
if r >= 128 {
return false
}
}
return true
}
func runesLen(rs []rune) (n int) {
for _, r := range rs {
n += utf8.RuneLen(r)
}
return n
}
// insert inserts the insert argument into buf at the given offset.
//
// cap(buf) must be >= len(buf) + len(insert).
func insert(buf, insert []byte, offset int) []byte {
n := len(insert)
buf = buf[:len(buf)+n]
copy(buf[offset+n:], buf[offset:])
copy(buf[offset:offset+n], insert)
return buf
}
func rngIntPair(rng *rand.Rand, n int) (x, y int) {
x = rng.Intn(n)
y = rng.Intn(n)
if x > y {
x, y = y, x
}
return x, y
}
// toyFace implements the font.Face interface by measuring every rune's width
// as 1 pixel.
type toyFace struct{}
func (toyFace) Close() error {
return nil
}
func (toyFace) Glyph(dot fixed.Point26_6, r rune) (image.Rectangle, image.Image, image.Point, fixed.Int26_6, bool) {
panic("unimplemented")
}
func (toyFace) GlyphBounds(r rune) (fixed.Rectangle26_6, fixed.Int26_6, bool) {
panic("unimplemented")
}
func (toyFace) GlyphAdvance(r rune) (fixed.Int26_6, bool) {
return fixed.I(1), true
}
func (toyFace) Kern(r0, r1 rune) fixed.Int26_6 {
return 0
}
func (toyFace) Metrics() font.Metrics {
return font.Metrics{
Ascent: fixed.I(2),
Descent: fixed.I(1),
}
}
const toyFaceLineHeight = 3
// iRobot is some text that contains both ASCII and non-ASCII runes.
const iRobot = "\"I, Robot\" in Russian is \"Я, робот\".\nIt's about robots.\n"
var (
iRobotBytes = []byte(iRobot)
iRobotRunes = []rune(iRobot)
)
func iRobotFrame(maxWidth int) *Frame {
f := new(Frame)
f.SetFace(toyFace{})
f.SetMaxWidth(fixed.I(maxWidth))
c := f.NewCaret()
c.WriteString(iRobot)
c.Close()
return f
}
func TestZeroFrame(t *testing.T) {
f := new(Frame)
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
}
func TestSeek(t *testing.T) {
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
rng := rand.New(rand.NewSource(1))
seen := [1 + len(iRobot)]bool{}
for i := 0; i < 10*len(iRobot); i++ {
wantPos := int64(rng.Intn(len(iRobot) + 1))
gotPos, err := c.Seek(wantPos, SeekSet)
if err != nil {
t.Fatalf("i=%d: Seek: %v", i, err)
}
if gotPos != wantPos {
t.Fatalf("i=%d: Seek: got %d, want %d", i, gotPos, wantPos)
}
seen[gotPos] = true
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
gotByte, gotErr := c.ReadByte()
wantByte, wantErr := byte(0), io.EOF
if gotPos < int64(len(iRobot)) {
wantByte, wantErr = iRobot[gotPos], nil
}
if gotByte != wantByte || gotErr != wantErr {
t.Fatalf("i=%d: ReadByte: got %d, %v, want %d, %v", i, gotByte, gotErr, wantByte, wantErr)
}
}
for i, s := range seen {
if !s {
t.Errorf("randomly generated positions weren't exhaustive: position %d / %d not seen", i, len(iRobot))
}
}
}
func testRead(f *Frame, want string) error {
c := f.NewCaret()
defer c.Close()
asBytes, err := ioutil.ReadAll(c)
if err != nil {
return fmt.Errorf("ReadAll: %v", err)
}
if got := string(asBytes); got != want {
return fmt.Errorf("Read\ngot: %q\nwant: %q", got, want)
}
return nil
}
func TestRead(t *testing.T) {
f := iRobotFrame(10)
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
if err := testRead(f, iRobot); err != nil {
t.Fatal(err)
}
}
func TestReadByte(t *testing.T) {
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
got, want := []byte(nil), []byte(iRobot)
for {
x, err := c.ReadByte()
if err == io.EOF {
break
}
if err != nil {
t.Fatalf("ReadByte: %v", err)
}
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
got = append(got, x)
}
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
if !reflect.DeepEqual(got, want) {
t.Fatalf("\ngot: %v\nwant: %v", got, want)
}
}
func TestReadRune(t *testing.T) {
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
got, want := []rune(nil), []rune(iRobot)
for {
r, _, err := c.ReadRune()
if err == io.EOF {
break
}
if err != nil {
t.Fatalf("ReadRune: %v", err)
}
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
got = append(got, r)
}
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
if !reflect.DeepEqual(got, want) {
t.Fatalf("\ngot: %v\nwant: %v", got, want)
}
}
func TestWrite(t *testing.T) {
f := new(Frame)
c := f.NewCaret()
c.Write([]byte{0xff, 0xfe, 0xfd})
c.WriteByte(0x80)
c.WriteRune('\U0001f4a9')
c.WriteString("abc\x00")
c.Close()
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
got := f.text[:f.len]
want := []byte{0xff, 0xfe, 0xfd, 0x80, 0xf0, 0x9f, 0x92, 0xa9, 0x61, 0x62, 0x63, 0x00}
if !bytes.Equal(got, want) {
t.Fatalf("\ngot % x\nwant % x", got, want)
}
}
func TestManyWrites(t *testing.T) {
f := new(Frame)
f.SetFace(toyFace{})
f.SetMaxWidth(fixed.I(10))
c := f.NewCaret()
defer c.Close()
const n, abc16 = 100, "abcdefghijkl\n "
rng := rand.New(rand.NewSource(1))
buf := make([]byte, n)
for i := range buf {
buf[i] = abc16[rng.Intn(len(abc16))]
}
for i := 0; i < 100; i++ {
x, y := rngIntPair(rng, len(buf)+1)
c.Write(buf[x:y])
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
}
}
func TestRandomAccessWrite(t *testing.T) {
f := new(Frame)
c := f.NewCaret()
defer c.Close()
rng := rand.New(rand.NewSource(1))
gotBuf := make([]byte, 0, 10000)
want := make([]byte, 0, 10000)
buf := make([]byte, 10)
x := byte(0)
for i := 0; i < 100; i++ {
n := rng.Intn(len(buf) + 1)
for j := range buf[:n] {
buf[j] = x
x++
}
offset := rng.Intn(len(want) + 1)
// Insert buf[:n] into the Frame at the given offset.
c.Seek(int64(offset), SeekSet)
c.Write(buf[:n])
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
// Insert buf[:n] into want at the given offset.
want = insert(want, buf[:n], offset)
if got := readAllText(gotBuf[:0], f); !bytes.Equal(got, want) {
t.Errorf("i=%d:\ngot % x\nwant % x", i, got, want)
}
}
}
func TestWriteAtStart(t *testing.T) {
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
prefix := "The Truth of the Matter\n(insofaras): "
gotBuf := make([]byte, len(prefix)+len(iRobot))
want := make([]byte, len(iRobot), len(prefix)+len(iRobot))
copy(want, iRobot)
for i := 0; i < len(prefix); i++ {
x := prefix[len(prefix)-1-i]
c.Seek(0, SeekSet)
c.WriteByte(x)
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
want = want[:len(want)+1]
copy(want[1:], want)
want[0] = x
if got := readAllText(gotBuf[:0], f); !bytes.Equal(got, want) {
t.Fatalf("i=%d:\ngot % x\nwant % x", i, got, want)
}
}
if nl, nb := f.nUsedLines(), f.nUsedBoxes(); nl == nb {
t.Fatalf("before compaction: using %d lines and %d boxes, should be not equal", nl, nb)
}
f.compactText()
if nl, nb := f.nUsedLines(), f.nUsedBoxes(); nl != nb {
t.Fatalf("after compaction: using %d lines and %d boxes, should be equal", nl, nb)
}
}
func TestLineCount(t *testing.T) {
f := iRobotFrame(0)
testCases := []struct {
desc string
maxWidth int
wantLines []string
wantLineCounts []int
}{{
desc: "infinite maxWidth",
maxWidth: 0,
wantLines: []string{
`"I, Robot" in Russian is "Я, робот".`,
`It's about robots.`,
``,
},
wantLineCounts: []int{1, 1, 1},
}, {
desc: "finite maxWidth",
maxWidth: 10,
wantLines: []string{
`"I, Robot"`,
`in Russian`,
`is "Я,`,
`робот".`,
`It's about`,
`robots.`,
``,
},
wantLineCounts: []int{4, 2, 1},
}}
for _, tc := range testCases {
f.SetMaxWidth(fixed.I(tc.maxWidth))
lines, lineCounts := []string{}, []int{}
for p := f.FirstParagraph(); p != nil; p = p.Next(f) {
for l := p.FirstLine(f); l != nil; l = l.Next(f) {
var line []byte
for b := l.FirstBox(f); b != nil; b = b.Next(f) {
line = append(line, b.TrimmedText(f)...)
}
lines = append(lines, string(line))
}
lineCounts = append(lineCounts, p.LineCount(f))
}
if got, want := f.LineCount(), len(tc.wantLines); got != want {
t.Errorf("%s: LineCount: got %d, want %d", tc.desc, got, want)
continue
}
if !reflect.DeepEqual(lines, tc.wantLines) {
t.Errorf("%s: lines: got %q, want %q", tc.desc, lines, tc.wantLines)
continue
}
if got, want := f.ParagraphCount(), len(tc.wantLineCounts); got != want {
t.Errorf("%s: ParagraphCount: got %d, want %d", tc.desc, got, want)
continue
}
if !reflect.DeepEqual(lineCounts, tc.wantLineCounts) {
t.Errorf("%s: lineCounts: got %d, want %d", tc.desc, lineCounts, tc.wantLineCounts)
continue
}
if got, want := f.Height(), toyFaceLineHeight*len(tc.wantLines); got != want {
t.Errorf("%s: Height: got %d, want %d", tc.desc, got, want)
continue
}
}
}
func TestSetMaxWidth(t *testing.T) {
f := new(Frame)
f.SetFace(toyFace{})
want := ""
rng := rand.New(rand.NewSource(1))
for i := 0; i < 100; i++ {
if i%20 == 5 {
c := f.NewCaret()
c.WriteString(iRobot)
c.Close()
want += iRobot
}
maxWidth := rng.Intn(20)
f.SetMaxWidth(fixed.I(maxWidth))
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
if err := testRead(f, want); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
if want == "" {
continue
}
// Check that a zero (which means infinite) maxWidth corresponds to one
// Line per Paragraph.
np, nl := f.nUsedParagraphs(), f.nUsedLines()
if maxWidth == 0 {
if np != nl {
t.Fatalf("i=%d: maxWidth=0: got %d paragraphs and %d lines, should be equal", i, np, nl)
}
} else {
if np == nl {
t.Fatalf("i=%d: maxWidth=%d: got %d paragraphs and %d lines, should be unequal", i, maxWidth, np, nl)
}
}
}
}
func TestReadRuneAcrossBoxes(t *testing.T) {
rng := rand.New(rand.NewSource(1))
for i := 0; i < 6; i++ {
// text is a mixture of valid and invalid UTF-8.
text := "ab_\u0100\u0101_\ufffd中文_\xff\xffñ\xff_z_\U0001f4a9_\U0001f600" +
strings.Repeat("\xff", i)
wantBytes := []byte(text)
wantRunes := []rune(text)
gotBytesBuf := make([]byte, 0, len(text))
gotRunesBuf := make([]rune, 0, len(text))
for j := 0; j < 100; j++ {
f := new(Frame)
{
c := f.NewCaret()
c.WriteString(text)
// Split the sole Line into multiple Boxes at random byte offsets,
// possibly cutting across multi-byte UTF-8 encoded runes.
for {
if rng.Intn(8) == 0 {
break
}
c.Seek(int64(rng.Intn(len(text)+1)), SeekSet)
c.splitBox(false)
}
c.Close()
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d, j=%d: %v", i, j, err)
}
if gotBytes := readAllText(gotBytesBuf[:0], f); !bytes.Equal(gotBytes, wantBytes) {
t.Fatalf("i=%d, j=%d: bytes\ngot % x\nwant % x", i, j, gotBytes, wantBytes)
}
}
// Test lineReader.ReadRune.
{
p := f.firstP
l := f.paragraphs[p].firstL
b := f.lines[l].firstB
lr := f.lineReader(b, f.boxes[b].i)
gotRunes, err := readAllRunes(gotRunesBuf[:0], lr)
if err != nil {
t.Fatalf("i=%d, j=%d: lineReader readAllRunes: %v", i, j, err)
}
if !runesEqual(gotRunes, wantRunes) {
t.Fatalf("i=%d, j=%d: lineReader readAllRunes:\ngot %#x\nwant %#x",
i, j, gotRunes, wantRunes)
}
}
// Test Caret.ReadRune.
{
c := f.NewCaret()
gotRunes, err := readAllRunes(gotRunesBuf[:0], c)
c.Close()
if err != nil {
t.Fatalf("i=%d, j=%d: Caret readAllRunes: %v", i, j, err)
}
if !runesEqual(gotRunes, wantRunes) {
t.Fatalf("i=%d, j=%d: Caret readAllRunes:\ngot %#x\nwant %#x",
i, j, gotRunes, wantRunes)
}
}
}
}
}
func TestDelete(t *testing.T) {
rng := rand.New(rand.NewSource(1))
gotBytesBuf := make([]byte, 0, len(iRobot))
wantBytesBuf := make([]byte, 0, len(iRobot))
for i := 0; i < 100; i++ {
f := iRobotFrame(rng.Intn(len(iRobot) + 1))
c := f.NewCaret()
defer c.Close()
wantBytes := append(wantBytesBuf[:0], iRobot...)
for j := 0; j < 8; j++ {
// Delete the text in the byte range [x, y).
x, y := rngIntPair(rng, len(wantBytes)+1)
got, want := 0, y-x
if rng.Intn(2) == 0 {
c.Seek(int64(x), SeekSet)
got = c.Delete(Forwards, want)
} else {
c.Seek(int64(y), SeekSet)
got = c.Delete(Backwards, want)
}
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d, j=%d, x=%d, y=%d: %v", i, j, x, y, err)
}
if got != want {
t.Fatalf("i=%d, j=%d, x=%d, y=%d: Delete: got %d, want %d", i, j, x, y, got, want)
}
gotBytes := readAllText(gotBytesBuf[:0], f)
wantBytes = append(wantBytes[:x], wantBytes[y:]...)
if !bytes.Equal(gotBytes, wantBytes) {
t.Fatalf("i=%d, j=%d, x=%d, y=%d:\ngot %q\nwant %q", i, j, x, y, gotBytes, wantBytes)
}
}
}
}
func TestDeleteRunes(t *testing.T) {
rng := rand.New(rand.NewSource(1))
gotBytesBuf := make([]byte, 0, len(iRobot))
wantRunesBuf := make([]rune, 0, len(iRobot))
wantBytesBuf := make([]byte, 0, len(iRobot))
for i := 0; i < 100; i++ {
f := iRobotFrame(rng.Intn(len(iRobot) + 1))
c := f.NewCaret()
defer c.Close()
wantRunes := append(wantRunesBuf[:0], iRobotRunes...)
wantBytes := append(wantBytesBuf[:0], iRobot...)
for j := 0; j < 8; j++ {
xR, yR := rngIntPair(rng, len(wantRunes)+1)
xB := runesLen(wantRunes[:xR])
yB := runesLen(wantRunes[:yR])
// Delete the text in the byte range [xB, yB).
gotR, gotB, wantR, wantB := 0, 0, yR-xR, yB-xB
if rng.Intn(2) == 0 {
c.Seek(int64(xB), SeekSet)
gotR, gotB = c.DeleteRunes(Forwards, wantR)
} else {
c.Seek(int64(yB), SeekSet)
gotR, gotB = c.DeleteRunes(Backwards, wantR)
}
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d, j=%d, xR=%d, xB=%d, yR=%d, yB=%d: %v", i, j, xR, xB, yR, yB, err)
}
if gotR != wantR || gotB != wantB {
t.Fatalf("i=%d, j=%d, xR=%d, xB=%d, yR=%d, yB=%d: Delete: got %d runes, %d bytes, want %d, %d",
i, j, xR, xB, yR, yB, gotR, gotB, wantR, wantB)
}
gotBytes := readAllText(gotBytesBuf[:0], f)
wantRunes = append(wantRunes[:xR], wantRunes[yR:]...)
wantBytes = append(wantBytes[:xB], wantBytes[yB:]...)
if !bytes.Equal(gotBytes, wantBytes) {
t.Fatalf("i=%d, j=%d, xR=%d, xB=%d, yR=%d, yB=%d:\ngot %q\nwant %q",
i, j, xR, xB, yR, yB, gotBytes, wantBytes)
}
}
}
}
func TestDeleteTooMuch(t *testing.T) {
if len(iRobot) < 17+15 {
t.Fatal("iRobot string is too short")
}
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
c.Seek(-15, SeekEnd)
if got, want := c.Delete(Forwards, 16), 15; got != want {
t.Errorf("Delete Forwards: got %d, want %d", got, want)
}
c.Seek(+17, SeekSet)
if got, want := c.Delete(Backwards, 18), 17; got != want {
t.Errorf("Delete Backwards: got %d, want %d", got, want)
}
got := string(readAllText(nil, f))
want := iRobot[17 : len(iRobot)-15]
if got != want {
t.Errorf("\ngot %q\nwant %q", got, want)
}
}
func TestDeleteRunesTooMuch(t *testing.T) {
if len(iRobotRunes) < 30+24 {
t.Fatal("iRobotRunes []rune is too short")
}
prefix := iRobotRunes[:30]
suffix := iRobotRunes[len(iRobotRunes)-24:]
if allASCII(prefix) {
t.Fatal("prefix contains no non-ASCII runes")
}
if allASCII(suffix) {
t.Fatal("suffix contains no non-ASCII runes")
}
prefixB := runesLen(prefix)
suffixB := runesLen(suffix)
f := iRobotFrame(10)
c := f.NewCaret()
defer c.Close()
c.Seek(-int64(suffixB), SeekEnd)
wantR, wantB := len(suffix), suffixB
if gotR, gotB := c.DeleteRunes(Forwards, 25); gotR != wantR || gotB != wantB {
t.Errorf("DeleteRunes Forwards: got %d runes, %d bytes, want %d, %d", gotR, gotB, wantR, wantB)
}
c.Seek(+int64(prefixB), SeekSet)
wantR, wantB = len(prefix), prefixB
if gotR, gotB := c.DeleteRunes(Backwards, 31); gotR != wantR || gotB != wantB {
t.Errorf("DeleteRunes Backwards: got %d runes, %d bytes, want %d, %d", gotR, gotB, wantR, wantB)
}
got := string(readAllText(nil, f))
want := iRobot[prefixB : len(iRobot)-suffixB]
if got != want {
t.Errorf("\ngot %q\nwant %q", got, want)
}
}
func TestCompactText(t *testing.T) {
f := new(Frame)
f.SetFace(toyFace{})
f.SetMaxWidth(fixed.I(80))
c := f.NewCaret()
defer c.Close()
const n, abc64 = 1024, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ\n "
rng := rand.New(rand.NewSource(1))
buf := make([]byte, n)
for i := range buf {
buf[i] = abc64[rng.Intn(len(abc64))]
}
written, wantLen := 0, 0
for i := 0; written < 131072; i++ {
if rng.Intn(10) != 0 {
x, y := rngIntPair(rng, len(buf)+1)
c.Seek(int64(rng.Intn(f.Len()+1)), SeekSet)
c.Write(buf[x:y])
written += y - x
wantLen += y - x
}
if rng.Intn(10) != 0 {
x, y := rngIntPair(rng, wantLen+1)
c.Seek(int64(x), SeekSet)
c.Delete(Forwards, y-x)
wantLen -= y - x
}
// Calculate cached counts, some of the time.
if rng.Intn(3) == 0 {
f.ParagraphCount()
}
if rng.Intn(4) == 0 {
f.LineCount()
}
if rng.Intn(5) == 0 {
c.Seek(int64(rng.Intn(f.Len()+1)), SeekSet)
f.paragraphs[c.p].LineCount(f)
}
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
if gotLen := f.Len(); gotLen != wantLen {
t.Fatalf("i=%d: length: got %d, want %d", i, gotLen, wantLen)
}
}
if len(f.text) == written {
t.Fatal("f.text was not compacted")
}
}
func TestMergeIntoOneLine(t *testing.T) {
rng := rand.New(rand.NewSource(1))
for i := 0; i < 100; i++ {
f := new(Frame)
f.SetMaxWidth(fixed.I(100))
if !f.initialized() {
f.initialize()
}
p := f.firstP
pp := &f.paragraphs[p]
l := pp.firstL
ll := &f.lines[l]
b := ll.firstB
bb := &f.boxes[b]
// Make some Lines and Boxes.
wantNUsedBoxes := 0
prevIJ := int32(0)
emptyRun := true
for j := 0; ; j++ {
length := rng.Intn(3)
bb.i = prevIJ
prevIJ += int32(length)
bb.j = prevIJ
f.len += length
if length > 0 && emptyRun {
emptyRun = false
wantNUsedBoxes++
}
if rng.Intn(20) == 0 {
break
}
if rng.Intn(4) == 0 {
// Make a new Box on a new Line.
l1, realloc := f.newLine()
if realloc {
ll = &f.lines[l]
}
ll1 := &f.lines[l1]
ll.next = l1
ll1.prev = l
l, ll = l1, ll1
ll.firstB, _ = f.newBox()
b = ll.firstB
bb = &f.boxes[b]
} else {
// Make a new Box on the same Line.
b1, realloc := f.newBox()
if realloc {
bb = &f.boxes[b]
}
bb1 := &f.boxes[b1]
bb.next = b1
bb1.prev = b
b, bb = b1, bb1
}
if rng.Intn(5) == 0 {
// Put an i/j gap between this run and the previous one.
prevIJ += 1 + int32(rng.Intn(5))
emptyRun = true
}
}
// We normally remove all empty Boxes. However, if there is no text
// whatsoever, we still need one Box.
if f.len == 0 {
if wantNUsedBoxes != 0 {
t.Fatalf("i=%d: no text: wantNUsedBoxes: got %d, want 0", i, wantNUsedBoxes)
}
wantNUsedBoxes = 1
}
// Make f.text long enough to hold all of the Boxes' i's and j's.
f.text = make([]byte, prevIJ)
for i := range f.text {
f.text[i] = byte('a' + i%16)
}
// Do the merge.
if err := checkSomeInvariants(f, ignoreInvariantEmptyBoxes); err != nil {
t.Fatalf("i=%d: before: %v", i, err)
}
f.mergeIntoOneLine(p)
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: after: %v", i, err)
}
// Check that there is only one Line in use.
if n := f.nUsedLines(); n != 1 {
t.Errorf("i=%d: nUsedLines: got %d, want %d", i, n, 1)
}
// Check the number of Boxes in use.
if n := f.nUsedBoxes(); n != wantNUsedBoxes {
t.Errorf("i=%d: nUsedBoxes: got %d, want %d", i, n, wantNUsedBoxes)
}
}
}
// TestMultipleCarets tests multiple Carets all seeking, reading, writing and
// deleting text.
func TestMultipleCarets(t *testing.T) {
f := new(Frame)
f.SetFace(toyFace{})
f.SetMaxWidth(fixed.I(10))
rng := rand.New(rand.NewSource(1))
gotBuf := make([]byte, 0, 10000)
want := make([]byte, 0, 10000)
positions := map[*Caret]int{}
carets := []*Caret{}
defer func() {
for _, c := range carets {
c.Close()
}
}()
for i := 0; i < 1000; i++ {
if err := checkInvariants(f); err != nil {
t.Fatalf("i=%d: %v", i, err)
}
if len(carets) == 0 || rng.Intn(20) == 0 {
c := f.NewCaret()
carets = append(carets, c)
positions[c] = 0
continue
}
caretsIndex := rng.Intn(len(carets))
c := carets[caretsIndex]
if rng.Intn(40) == 0 {
c.Close()
carets[caretsIndex] = carets[len(carets)-1]
carets[len(carets)-1] = nil
carets = carets[:len(carets)-1]
delete(positions, c)
continue
}
// Seek, read, delete or write, with a slight bias to writing.
switch rng.Intn(5) {
case 0: // Seek.
p := rng.Intn(len(want) + 1)
c.Seek(int64(p), SeekSet)
positions[c] = p
case 1: // ReadByte.
gotB, gotErr := c.ReadByte()
wantB, wantErr := byte(0), io.EOF
if p := positions[c]; p < len(want) {
wantB, wantErr = want[p], nil
positions[c] = p + 1
}
if gotB != wantB || gotErr != wantErr {
t.Fatalf("i=%d: ReadByte: got %d, %v, want %d, %v", i, gotB, gotErr, wantB, wantErr)
}
case 2: // Delete.
dir := Direction(rng.Intn(2) == 0)
nBytes, dBytes := rng.Intn(len(want)), 0
pos, x, y := positions[c], 0, 0
if dir == Forwards {
dBytes = min(nBytes, len(want)-pos)
x, y = pos, pos+dBytes
} else {
dBytes = min(nBytes, pos)
x, y = pos-dBytes, pos
}
if d := c.Delete(dir, nBytes); d != dBytes {
t.Fatalf("i=%d: Delete: got %d bytes, want %d", i, d, dBytes)
}
want = append(want[:x], want[y:]...)
for _, cc := range carets {
if cc == c {
positions[cc] = x
continue
}
switch p := positions[cc]; {
case p <= x:
// No-op.
case p <= y:
positions[cc] = x
default:
positions[cc] -= dBytes
}
}
default: // Write.
i, j := rngIntPair(rng, len(iRobotBytes))
s := iRobotBytes[i:j]
c.Write(s)
pos := positions[c]
want = insert(want, s, pos)
for _, cc := range carets {
if cc == c || positions[cc] > pos {
positions[cc] += j - i
}
}
}
badPos := false
for ci, cc := range carets {
if int(cc.pos) != positions[cc] {
badPos = true
t.Errorf("i=%d, ci=%d: position: got %d, want %d", i, ci, cc.pos, positions[cc])
}
}
if badPos {
t.Fatalf("i=%d: there were inconsistent Caret positions", i)
}
if got := readAllText(gotBuf[:0], f); !bytes.Equal(got, want) {
t.Fatalf("i=%d:\ngot % x\nwant % x", i, got, want)
}
}
if err := checkInvariants(f); err != nil {
t.Fatal(err)
}
}
type ijRange struct {
i, j int32
}
type byI []ijRange
func (b byI) Len() int { return len(b) }
func (b byI) Less(x, y int) bool { return b[x].i < b[y].i }
func (b byI) Swap(x, y int) { b[x], b[y] = b[y], b[x] }
const (
ignoreInvariantEmptyBoxes = 1 << iota
)
func checkInvariants(f *Frame) error {
return checkSomeInvariants(f, 0)
}
func checkSomeInvariants(f *Frame, ignoredInvariants uint32) error {
const infinity = 1e6
if !f.initialized() {
if !reflect.DeepEqual(*f, Frame{}) {
return fmt.Errorf("uninitialized Frame is not zero-valued")
}
return nil
}
// Iterate through the Paragraphs, Lines and Boxes. Check that every first
// child has no previous sibling, and no child is the first child of
// multiple parents. Also check the cached Paragraph and Line counts.
nUsedParagraphs, nUsedLines, nUsedBoxes := 0, 0, 0
{
firstLines := map[int32]bool{}
firstBoxes := map[int32]bool{}
p := f.firstP
if p == 0 {
return fmt.Errorf("firstP is zero")
}
if x := f.paragraphs[p].prev; x != 0 {
return fmt.Errorf("first Paragraph %d's prev: got %d, want 0", p, x)
}
for ; p != 0; p = f.paragraphs[p].next {
l := f.paragraphs[p].firstL
if l == 0 {
return fmt.Errorf("paragraphs[%d].firstL is zero", p)
}
if x := f.lines[l].prev; x != 0 {
return fmt.Errorf("first Line %d's prev: got %d, want 0", l, x)
}
if firstLines[l] {
return fmt.Errorf("duplicate first Line %d", l)
}
firstLines[l] = true
nUsedLinesThisParagraph := 0
for ; l != 0; l = f.lines[l].next {
b := f.lines[l].firstB
if b == 0 {
return fmt.Errorf("lines[%d].firstB is zero", l)
}
if x := f.boxes[b].prev; x != 0 {
return fmt.Errorf("first Box %d's prev: got %d, want 0", b, x)
}
if firstBoxes[b] {
return fmt.Errorf("duplicate first Box %d", b)
}
firstBoxes[b] = true
for ; b != 0; b = f.boxes[b].next {
nUsedBoxes++
if nUsedBoxes >= infinity {
return fmt.Errorf("too many used Boxes (infinite loop?)")
}
}
nUsedLines++
nUsedLinesThisParagraph++
}
nUsedParagraphs++
if n := int(f.paragraphs[p].cachedLineCountPlus1 - 1); n >= 0 && n != nUsedLinesThisParagraph {
return fmt.Errorf("Paragraph cached Line count: got %d, want %d", n, nUsedLinesThisParagraph)
}
}
if n := int(f.cachedLineCountPlus1 - 1); n >= 0 && n != nUsedLines {
return fmt.Errorf("Frame cached Line count: got %d, want %d", n, nUsedLines)
}
if n := int(f.cachedParagraphCountPlus1 - 1); n >= 0 && n != nUsedParagraphs {
return fmt.Errorf("Frame cached Paragraph count: got %d, want %d", n, nUsedParagraphs)
}
}
// Check that only the last Box can be empty.
if ignoredInvariants&ignoreInvariantEmptyBoxes == 0 {
for p := f.firstP; p != 0; {
nextP := f.paragraphs[p].next
for l := f.paragraphs[p].firstL; l != 0; {
nextL := f.lines[l].next
for b := f.lines[l].firstB; b != 0; {
nextB := f.boxes[b].next
emptyBox := f.boxes[b].i == f.boxes[b].j
lastBox := nextP == 0 && nextL == 0 && nextB == 0
if emptyBox && !lastBox {
return fmt.Errorf("boxes[%d] is empty, but isn't the last Box", b)
}
b = nextB
}
l = nextL
}
p = nextP
}
}
// Check the paragraphs.
for p, pp := range f.paragraphs {
if p == 0 {
if pp != (Paragraph{}) {
return fmt.Errorf("paragraphs[0] is a non-zero Paragraph: %v", pp)
}
continue
}
if pp.next < 0 || len(f.paragraphs) <= int(pp.next) {
return fmt.Errorf("invalid paragraphs[%d].next: got %d, want in [0, %d)", p, pp.next, len(f.paragraphs))
}
if len(f.paragraphs) <= int(pp.prev) {
return fmt.Errorf("invalid paragraphs[%d].prev: got %d, want in [0, %d)", p, pp.prev, len(f.paragraphs))
}
if pp.prev < 0 {
// The Paragraph is in the free-list, which is checked separately below.
continue
}
if pp.next != 0 && f.paragraphs[pp.next].prev != int32(p) {
return fmt.Errorf("invalid links: paragraphs[%d].next=%d, paragraphs[%d].prev=%d",
p, pp.next, pp.next, f.paragraphs[pp.next].prev)
}
if pp.prev != 0 && f.paragraphs[pp.prev].next != int32(p) {
return fmt.Errorf("invalid links: paragraphs[%d].prev=%d, paragraphs[%d].next=%d",
p, pp.prev, pp.prev, f.paragraphs[pp.prev].next)
}
}
// Check the paragraphs' free-list.
nFreeParagraphs := 0
for p := f.freeP; p != 0; nFreeParagraphs++ {
if nFreeParagraphs >= infinity {
return fmt.Errorf("Paragraph free-list is too long (infinite loop?)")
}
if p < 0 || len(f.paragraphs) <= int(p) {
return fmt.Errorf("invalid Paragraph free-list index: got %d, want in [0, %d)", p, len(f.paragraphs))
}
pp := &f.paragraphs[p]
if pp.prev >= 0 {
return fmt.Errorf("paragraphs[%d] is an invalid free-list element: %#v", p, *pp)
}
p = pp.next
}
// Check the lines.
for l, ll := range f.lines {
if l == 0 {
if ll != (Line{}) {
return fmt.Errorf("lines[0] is a non-zero Line: %v", ll)
}
continue
}
if ll.next < 0 || len(f.lines) <= int(ll.next) {
return fmt.Errorf("invalid lines[%d].next: got %d, want in [0, %d)", l, ll.next, len(f.lines))
}
if len(f.lines) <= int(ll.prev) {
return fmt.Errorf("invalid lines[%d].prev: got %d, want in [0, %d)", l, ll.prev, len(f.lines))
}
if ll.prev < 0 {
// The Line is in the free-list, which is checked separately below.
continue
}
if ll.next != 0 && f.lines[ll.next].prev != int32(l) {
return fmt.Errorf("invalid links: lines[%d].next=%d, lines[%d].prev=%d",
l, ll.next, ll.next, f.lines[ll.next].prev)
}
if ll.prev != 0 && f.lines[ll.prev].next != int32(l) {
return fmt.Errorf("invalid links: lines[%d].prev=%d, lines[%d].next=%d",
l, ll.prev, ll.prev, f.lines[ll.prev].next)
}
}
// Check the lines' free-list.
nFreeLines := 0
for l := f.freeL; l != 0; nFreeLines++ {
if nFreeLines >= infinity {
return fmt.Errorf("Line free-list is too long (infinite loop?)")
}
if l < 0 || len(f.lines) <= int(l) {
return fmt.Errorf("invalid Line free-list index: got %d, want in [0, %d)", l, len(f.lines))
}
ll := &f.lines[l]
if ll.prev >= 0 {
return fmt.Errorf("lines[%d] is an invalid free-list element: %#v", l, *ll)
}
l = ll.next
}
// Check the boxes.
for b, bb := range f.boxes {
if b == 0 {
if bb != (Box{}) {
return fmt.Errorf("boxes[0] is a non-zero Box: %v", bb)
}
continue
}
if bb.next < 0 || len(f.boxes) <= int(bb.next) {
return fmt.Errorf("invalid boxes[%d].next: got %d, want in [0, %d)", b, bb.next, len(f.boxes))
}
if len(f.boxes) <= int(bb.prev) {
return fmt.Errorf("invalid boxes[%d].prev: got %d, want in [0, %d)", b, bb.prev, len(f.boxes))
}
if bb.prev < 0 {
// The Box is in the free-list, which is checked separately below.
continue
}
if bb.next != 0 && f.boxes[bb.next].prev != int32(b) {
return fmt.Errorf("invalid links: boxes[%d].next=%d, boxes[%d].prev=%d",
b, bb.next, bb.next, f.boxes[bb.next].prev)
}
if bb.prev != 0 && f.boxes[bb.prev].next != int32(b) {
return fmt.Errorf("invalid links: boxes[%d].prev=%d, boxes[%d].next=%d",
b, bb.prev, bb.prev, f.boxes[bb.prev].next)
}
if 0 > bb.i || bb.i > bb.j || bb.j > int32(len(f.text)) {
return fmt.Errorf("invalid boxes[%d] i/j range: i=%d, j=%d, len=%d", b, bb.i, bb.j, len(f.text))
}
}
// Check the boxes' free-list.
nFreeBoxes := 0
for b := f.freeB; b != 0; nFreeBoxes++ {
if nFreeBoxes >= infinity {
return fmt.Errorf("Box free-list is too long (infinite loop?)")
}
if b < 0 || len(f.boxes) <= int(b) {
return fmt.Errorf("invalid Box free-list index: got %d, want in [0, %d)", b, len(f.boxes))
}
bb := &f.boxes[b]
if bb.i != 0 || bb.j != 0 || bb.prev >= 0 {
return fmt.Errorf("boxes[%d] is an invalid free-list element: %#v", b, *bb)
}
b = bb.next
}
// Check that the boxes' i:j ranges do not overlap, and their total length
// equals f.len.
nText, ijRanges := 0, []ijRange{}
for _, bb := range f.boxes {
if bb.i < bb.j {
nText += int(bb.j - bb.i)
ijRanges = append(ijRanges, ijRange{i: bb.i, j: bb.j})
}
}
sort.Sort(byI(ijRanges))
for x := range ijRanges {
if x == 0 {
continue
}
if ijRanges[x-1].j > ijRanges[x].i {
return fmt.Errorf("overlapping Box i:j ranges: %v and %v", ijRanges[x-1], ijRanges[x])
}
}
if nText != f.len {
return fmt.Errorf("text length: got %d, want %d", nText, f.len)
}
// Check that every Paragraph, Line and Box, other than the 0th of each, is
// either used or free.
if len(f.paragraphs) != 1+nUsedParagraphs+nFreeParagraphs {
return fmt.Errorf("#paragraphs (%d) != 1 + #used (%d) + #free (%d)",
len(f.paragraphs), nUsedParagraphs, nFreeParagraphs)
}
if len(f.lines) != 1+nUsedLines+nFreeLines {
return fmt.Errorf("#lines (%d) != 1 + #used (%d) + #free (%d)", len(f.lines), nUsedLines, nFreeLines)
}
if len(f.boxes) != 1+nUsedBoxes+nFreeBoxes {
return fmt.Errorf("#boxes (%d) != 1 + #used (%d) + #free (%d)", len(f.boxes), nUsedBoxes, nFreeBoxes)
}
// Check that each Caret's pos is in the Frame's 0:len range. If the
// Caret's cached {p,l,b,k} values are valid, also check that the Caret's k
// is in its Box's i:j range, and its Box b is in its Line l is in its
// Paragraph p.
for i, c := range f.carets {
if c.pos < 0 || f.len < int(c.pos) {
return fmt.Errorf("caret[%d]: pos %d outside range [0, %d]", i, c.pos, f.len)
}
if c.seqNum != f.seqNum {
continue
}
if c.b < 1 || len(f.boxes) < int(c.b) {
return fmt.Errorf("caret[%d]: c.b %d outside range [1, %d]", i, c.b, len(f.boxes))
}
bb := &f.boxes[c.b]
if c.k < bb.i || bb.j < c.k {
return fmt.Errorf("caret[%d]: c.k %d outside range [%d, %d]", i, c.k, bb.i, bb.j)
}
if c.l < 1 || len(f.lines) < int(c.l) {
return fmt.Errorf("caret[%d]: c.l %d outside range [1, %d]", i, c.l, len(f.lines))
}
if !f.lines[c.l].contains(f, c.b) {
return fmt.Errorf("caret[%d]: Line %d does not contain Box %d", i, c.l, c.b)
}
if c.p < 1 || len(f.paragraphs) < int(c.p) {
return fmt.Errorf("caret[%d]: c.p %d outside range [1, %d]", i, c.p, len(f.paragraphs))
}
if !f.paragraphs[c.p].contains(f, c.l) {
return fmt.Errorf("caret[%d]: Paragraph %d does not contain Line %d", i, c.p, c.l)
}
}
return nil
}
func (f *Frame) nUsedParagraphs() (n int) {
for p, pp := range f.paragraphs {
// The 0th index is a special case. A negative prev means that the
// Paragraph is in the free-list.
if p != 0 && pp.prev >= 0 {
n++
}
}
return n
}
func (f *Frame) nUsedLines() (n int) {
for l, ll := range f.lines {
// The 0th index is a special case. A negative prev means that the
// Line is in the free-list.
if l != 0 && ll.prev >= 0 {
n++
}
}
return n
}
func (f *Frame) nUsedBoxes() (n int) {
for b, bb := range f.boxes {
// The 0th index is a special case. A negative prev means that the
// Box is in the free-list.
if b != 0 && bb.prev >= 0 {
n++
}
}
return n
}
func (p *Paragraph) contains(f *Frame, l int32) bool {
for x := p.firstL; x != 0; x = f.lines[x].next {
if x == l {
return true
}
}
return false
}
func (l *Line) contains(f *Frame, b int32) bool {
for x := l.firstB; x != 0; x = f.boxes[x].next {
if x == b {
return true
}
}
return false
}
// dump is used for debugging.
func dump(w io.Writer, f *Frame) {
for p := f.FirstParagraph(); p != nil; p = p.Next(f) {
for l := p.FirstLine(f); l != nil; l = l.Next(f) {
for b := l.FirstBox(f); b != nil; b = b.Next(f) {
fmt.Fprintf(w, "[%s]", b.TrimmedText(f))
}
fmt.Fprintln(w)
}
}
}