shiny/text/caret.go

// 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

// TODO: do we care about "\n" vs "\r" vs "\r\n"? We only recognize "\n" for
// now.

import (
	"bytes"
	"errors"
	"io"
	"strings"
	"unicode/utf8"

	"golang.org/x/image/math/fixed"
)

// Caret is a location in a Frame's text, and is the mechanism for adding and
// removing bytes of text. Conceptually, a Caret and a Frame's text is like an
// int c and a []byte t such that the text before and after that Caret is t[:c]
// and t[c:]. That byte-count location remains unchanged even when a Frame is
// re-sized and laid out into a new tree of Paragraphs, Lines and Boxes.
//
// A Frame can have multiple open Carets. For example, the beginning and end of
// a text selection can be represented by two Carets. Multiple Carets for the
// one Frame are not safe to use concurrently, but it is valid to interleave
// such operations sequentially. For example, if two Carets c0 and c1 for the
// one Frame are positioned at the 10th and 20th byte, and 4 bytes are written
// to c0, inserting what becomes the equivalent of text[10:14], then c0's
// position is updated to be 14 but c1's position is also updated to be 24.
type Caret struct {
	f *Frame

	// caretsIndex is the index of this Caret in the f.carets slice.
	caretsIndex int

	// seqNum is the Frame f's sequence number for which this Caret's cached p,
	// l, b and k fields are valid. If f has been modified since then, those
	// fields will have to be re-calculated based on the pos field (which is
	// always valid).
	//
	// TODO: when re-calculating p, l, b and k, be more efficient than a linear
	// scan from the start or end?
	seqNum uint64

	// p, l and b cache the index of the Caret's Paragraph, Line and Box. None
	// of these values can be zero.
	p, l, b int32

	// k caches the Caret's position in the text, in Frame.text order. It is
	// valid to index the Frame.text slice with k, analogous to the Box.i and
	// Box.j fields. For a Caret c, letting bb := c.f.boxes[c.b], an invariant
	// is that bb.i <= c.k && c.k <= bb.j if the cache is valid (i.e. the
	// Caret's seqNum equals the Frame's seqNum).
	k int32

	// pos is the Caret's position in the text, in layout order. It is the "c"
	// as in "t[:c]" in the doc comment for type Caret above. It is not valid
	// to index the Frame.text slice with pos, since the Frame.text slice does
	// not necessarily hold the textual content in layout order.
	pos int32

	tmp [utf8.UTFMax]byte
}

// Close closes the Caret.
func (c *Caret) Close() error {
	i, j := c.caretsIndex, len(c.f.carets)-1

	// Swap c with the last element of c.f.carets.
	if i != j {
		other := c.f.carets[j]
		other.caretsIndex = i
		c.f.carets[i] = other
	}

	c.f.carets[j] = nil
	c.f.carets = c.f.carets[:j]
	*c = Caret{}
	return nil
}

type leanResult int

const (
	// leanOK means that the lean changed the Caret's Box.
	leanOK leanResult = iota
	// leanFailedEOF means that the lean did not change the Caret's Box,
	// because the Caret was already at the end / beginning of the Frame (when
	// leaning forwards / backwards).
	leanFailedEOF
	// leanFailedNotEOB means that the lean did not change the Caret's Box,
	// because the Caret was not placed at the end / beginning of the Box (when
	// leaning forwards / backwards).
	leanFailedNotEOB
)

// leanForwards moves the Caret from the right end of one Box to the left end
// of the next Box, crossing Lines and Paragraphs to find that next Box. It
// returns whether the Caret moved to a different Box.
//
// Diagramatically, suppose we have two adjacent boxes (shown by square
// brackets below), with the Caret (an integer location called Caret.pos in the
// Frame's text) in the middle of the "foo2bar3" word:
//	[foo0 foo1 foo2]^[bar3 bar4 bar5]
// leanForwards moves Caret.k from fooBox.j to barBox.i, also updating the
// Caret's p, l and b. Caret.pos remains unchanged.
func (c *Caret) leanForwards() leanResult {
	if c.k != c.f.boxes[c.b].j {
		return leanFailedNotEOB
	}
	if nextB := c.f.boxes[c.b].next; nextB != 0 {
		c.b = nextB
		c.k = c.f.boxes[c.b].i
		return leanOK
	}
	if nextL := c.f.lines[c.l].next; nextL != 0 {
		c.l = nextL
		c.b = c.f.lines[c.l].firstB
		c.k = c.f.boxes[c.b].i
		return leanOK
	}
	if nextP := c.f.paragraphs[c.p].next; nextP != 0 {
		c.p = nextP
		c.l = c.f.paragraphs[c.p].firstL
		c.b = c.f.lines[c.l].firstB
		c.k = c.f.boxes[c.b].i
		return leanOK
	}
	return leanFailedEOF
}

// leanBackwards is like leanForwards but in the other direction.
func (c *Caret) leanBackwards() leanResult {
	if c.k != c.f.boxes[c.b].i {
		return leanFailedNotEOB
	}
	if prevB := c.f.boxes[c.b].prev; prevB != 0 {
		c.b = prevB
		c.k = c.f.boxes[c.b].j
		return leanOK
	}
	if prevL := c.f.lines[c.l].prev; prevL != 0 {
		c.l = prevL
		c.b = c.f.lines[c.l].lastBox(c.f)
		c.k = c.f.boxes[c.b].j
		return leanOK
	}
	if prevP := c.f.paragraphs[c.p].prev; prevP != 0 {
		c.p = prevP
		c.l = c.f.paragraphs[c.p].lastLine(c.f)
		c.b = c.f.lines[c.l].lastBox(c.f)
		c.k = c.f.boxes[c.b].j
		return leanOK
	}
	return leanFailedEOF
}

func (c *Caret) seekStart() {
	c.p = c.f.firstP
	c.l = c.f.paragraphs[c.p].firstL
	c.b = c.f.lines[c.l].firstB
	c.k = c.f.boxes[c.b].i
	c.pos = 0
}

func (c *Caret) seekEnd() {
	c.p = c.f.lastParagraph()
	c.l = c.f.paragraphs[c.p].lastLine(c.f)
	c.b = c.f.lines[c.l].lastBox(c.f)
	c.k = c.f.boxes[c.b].j
	c.pos = int32(c.f.len)
}

// calculatePLBK ensures that the Caret's cached p, l, b and k fields are
// valid.
func (c *Caret) calculatePLBK() {
	if c.seqNum != c.f.seqNum {
		c.seek(c.pos)
	}
}

// Seek satisfies the io.Seeker interface.
func (c *Caret) Seek(offset int64, whence int) (int64, error) {
	switch whence {
	case SeekSet:
		// No-op.
	case SeekCur:
		offset += int64(c.pos)
	case SeekEnd:
		offset += int64(c.f.len)
	default:
		return 0, errors.New("text: invalid seek whence")
	}
	if offset < 0 {
		return 0, errors.New("text: negative seek position")
	}
	if offset > int64(c.f.len) {
		offset = int64(c.f.len)
	}
	c.seek(int32(offset))
	return offset, nil
}

func (c *Caret) seek(off int32) {
	delta := off - c.pos
	// If the new offset is closer to the start or the end than to the current
	// c.pos, or if c's cached {p,l,b,k} values are invalid, move to the start
	// or end first. In case of a tie, we prefer to seek forwards (i.e. set
	// delta > 0).
	if (delta < 0 && -delta >= off) || (c.seqNum != c.f.seqNum) {
		c.seekStart()
		delta = off - c.pos
	}
	if delta > 0 && delta > int32(c.f.len)-off {
		c.seekEnd()
		delta = off - c.pos
	}

	if delta != 0 {
		// Seek forwards.
		for delta > 0 {
			if n := c.f.boxes[c.b].j - c.k; n > 0 {
				if n > delta {
					n = delta
				}
				c.pos += n
				c.k += n
				delta -= n
			} else if c.leanForwards() != leanOK {
				panic("text: invalid state")
			}
		}

		// Seek backwards.
		for delta < 0 {
			if n := c.f.boxes[c.b].i - c.k; n < 0 {
				if n < delta {
					n = delta
				}
				c.pos += n
				c.k += n
				delta -= n
			} else if c.leanBackwards() != leanOK {
				panic("text: invalid state")
			}
		}

		// A Caret can't be placed at the end of a Paragraph, unless it is the
		// final Paragraph. A simple way to enforce this is to lean forwards.
		c.leanForwards()
	}

	c.seqNum = c.f.seqNum
}

// Read satisfies the io.Reader interface by copying those bytes after the
// Caret and incrementing the Caret.
func (c *Caret) Read(buf []byte) (n int, err error) {
	c.calculatePLBK()
	for len(buf) > 0 {
		if j := c.f.boxes[c.b].j; c.k < j {
			nn := copy(buf, c.f.text[c.k:j])
			buf = buf[nn:]
			n += nn
			c.pos += int32(nn)
			c.k += int32(nn)
		}
		// A Caret can't be placed at the end of a Paragraph, unless it is the
		// final Paragraph. A simple way to enforce this is to lean forwards.
		if c.leanForwards() == leanFailedEOF {
			break
		}
	}
	if int(c.pos) == c.f.len {
		err = io.EOF
	}
	return n, err
}

// ReadByte returns the next byte after the Caret and increments the Caret.
func (c *Caret) ReadByte() (x byte, err error) {
	c.calculatePLBK()
	for {
		if j := c.f.boxes[c.b].j; c.k < j {
			x = c.f.text[c.k]
			c.pos++
			c.k++
			// A Caret can't be placed at the end of a Paragraph, unless it is
			// the final Paragraph. A simple way to enforce this is to lean
			// forwards.
			c.leanForwards()
			return x, nil
		}
		if c.leanForwards() == leanFailedEOF {
			return 0, io.EOF
		}
	}
}

// ReadRune returns the next rune after the Caret and increments the Caret.
func (c *Caret) ReadRune() (r rune, size int, err error) {
	c.calculatePLBK()
	for {
		if c.k < c.f.boxes[c.b].j {
			r, size, c.b, c.k = c.f.readRune(c.b, c.k)
			c.pos += int32(size)
			// A Caret can't be placed at the end of a Paragraph, unless it is
			// the final Paragraph. A simple way to enforce this is to lean
			// forwards.
			c.leanForwards()
			return r, size, nil
		}
		if c.leanForwards() == leanFailedEOF {
			return 0, 0, io.EOF
		}
	}
}

// WriteByte inserts x into the Frame's text at the Caret and increments the
// Caret.
func (c *Caret) WriteByte(x byte) error {
	c.tmp[0] = x
	return c.write(c.tmp[:1], "")
}

// WriteRune inserts r into the Frame's text at the Caret and increments the
// Caret.
func (c *Caret) WriteRune(r rune) (size int, err error) {
	size = utf8.EncodeRune(c.tmp[:], r)
	if err = c.write(c.tmp[:size], ""); err != nil {
		return 0, err
	}
	return size, nil
}

// WriteString inserts s into the Frame's text at the Caret and increments the
// Caret.
func (c *Caret) WriteString(s string) (n int, err error) {
	for len(s) > 0 {
		i := 1 + strings.IndexByte(s, '\n')
		if i == 0 {
			i = len(s)
		}
		if err = c.write(nil, s[:i]); err != nil {
			break
		}
		n += i
		s = s[i:]
	}
	return n, err
}

// Write inserts s into the Frame's text at the Caret and increments the Caret.
func (c *Caret) Write(s []byte) (n int, err error) {
	for len(s) > 0 {
		i := 1 + bytes.IndexByte(s, '\n')
		if i == 0 {
			i = len(s)
		}
		if err = c.write(s[:i], ""); err != nil {
			break
		}
		n += i
		s = s[i:]
	}
	return n, err
}

// write inserts a []byte or string into the Frame's text at the Caret.
//
// Exactly one of s0 and s1 must be non-empty. That non-empty argument must
// contain at most one '\n' and if it does contain one, it must be the final
// byte.
func (c *Caret) write(s0 []byte, s1 string) error {
	if m := maxLen - len(c.f.text); len(s0) > m || len(s1) > m {
		return errors.New("text: insufficient space for writing")
	}

	// Ensure that the Caret is at the end of its Box, and that Box's text is
	// at the end of the Frame's buffer.
	c.calculatePLBK()
	for {
		bb, n := &c.f.boxes[c.b], int32(len(c.f.text))
		if c.k == bb.j && c.k == n {
			break
		}

		// If the Box's text is empty, move its empty i:j range to the
		// equivalent empty range at the end of c.f.text.
		if bb.i == bb.j {
			bb.i = n
			bb.j = n
			for _, cc := range c.f.carets {
				if cc.b == c.b {
					cc.k = n
				}
			}
			continue
		}

		// Make the Caret be at the end of its Box.
		if c.k != bb.j {
			c.splitBox(true)
			continue
		}

		// Make a new empty Box and move the Caret to it.
		c.splitBox(true)
		c.leanForwards()
	}

	c.f.invalidateCaches()
	c.f.paragraphs[c.p].invalidateCaches()
	c.f.lines[c.l].invalidateCaches()

	length, nl := len(s0), false
	if length > 0 {
		nl = s0[length-1] == '\n'
		c.f.text = append(c.f.text, s0...)
	} else {
		length = len(s1)
		nl = s1[length-1] == '\n'
		c.f.text = append(c.f.text, s1...)
	}
	c.f.len += length
	c.f.boxes[c.b].j += int32(length)
	c.k += int32(length)
	for _, cc := range c.f.carets {
		if cc.pos > c.pos {
			cc.pos += int32(length)
		}
	}
	c.pos += int32(length)
	oldL := c.l

	if nl {
		breakParagraph(c.f, c.p, c.l, c.b)
		c.p = c.f.paragraphs[c.p].next
		c.l = c.f.paragraphs[c.p].firstL
		c.b = c.f.lines[c.l].firstB
		c.k = c.f.boxes[c.b].i
	}

	// TODO: re-layout the new c.p paragraph, if we saw '\n'.
	layout(c.f, oldL)

	c.f.seqNum++
	return nil
}

// breakParagraph breaks the Paragraph p into two Paragraphs, just after Box b
// in Line l in Paragraph p. b's text must end with a '\n'. The new Paragraph
// is inserted after p.
func breakParagraph(f *Frame, p, l, b int32) {
	// Assert that the Box b's text ends with a '\n'.
	if j := f.boxes[b].j; j == 0 || f.text[j-1] != '\n' {
		panic("text: invalid state")
	}

	// Make a new, empty Paragraph after this Paragraph p.
	newP, _ := f.newParagraph()
	nextP := f.paragraphs[p].next
	if nextP != 0 {
		f.paragraphs[nextP].prev = newP
	}
	f.paragraphs[newP].next = nextP
	f.paragraphs[newP].prev = p
	f.paragraphs[p].next = newP

	// Any Lines in this Paragraph after the break point's Line l move to the
	// newP Paragraph.
	if nextL := f.lines[l].next; nextL != 0 {
		f.lines[l].next = 0
		f.lines[nextL].prev = 0
		f.paragraphs[newP].firstL = nextL
	}

	// Any Boxes in this Line after the break point's Box b move to a new Line
	// at the start of the newP Paragraph.
	if nextB := f.boxes[b].next; nextB != 0 {
		f.boxes[b].next = 0
		f.boxes[nextB].prev = 0
		newL, _ := f.newLine()
		f.lines[newL].firstB = nextB
		if newPFirstL := f.paragraphs[newP].firstL; newPFirstL != 0 {
			f.lines[newL].next = newPFirstL
			f.lines[newPFirstL].prev = newL
		}
		f.paragraphs[newP].firstL = newL
	}

	// Make the newP Paragraph's first Line and first Box explicit, since
	// Carets require an explicit p, l and b.
	{
		pp := &f.paragraphs[newP]
		if pp.firstL == 0 {
			pp.firstL, _ = f.newLine()
		}
		ll := &f.lines[pp.firstL]
		if ll.firstB == 0 {
			ll.firstB, _ = f.newBox()
		}
	}

	// TODO: re-layout the newP paragraph.
}

// breakLine breaks the Line l at text index k in Box b. The b-and-k index must
// not be at the start or end of the Line. Text to the right of b-and-k in the
// Line l will be moved to the start of the next Line in the Paragraph, with
// that next Line being created if it didn't already exist.
func breakLine(f *Frame, l, b, k int32) {
	// Split this Box into two if necessary, so that k equals a Box's j end.
	bb := &f.boxes[b]
	if k != bb.j {
		if k == bb.i {
			panic("TODO: degenerate split left, possibly adjusting the Line's firstB??")
		}
		newB, realloc := f.newBox()
		if realloc {
			bb = &f.boxes[b]
		}
		nextB := bb.next
		if nextB != 0 {
			f.boxes[nextB].prev = newB
		}
		f.boxes[newB].next = nextB
		f.boxes[newB].prev = b
		f.boxes[newB].i = k
		f.boxes[newB].j = bb.j
		bb.next = newB
		bb.j = k
	}

	// Assert that the break point isn't already at the start or end of the Line.
	if bb.next == 0 || (bb.prev == 0 && k == bb.i) {
		panic("text: invalid state")
	}

	// Insert a line after this one, if one doesn't already exist.
	ll := &f.lines[l]
	if ll.next == 0 {
		newL, realloc := f.newLine()
		if realloc {
			ll = &f.lines[l]
		}
		f.lines[newL].prev = l
		ll.next = newL
	}

	// Move the remaining boxes to the next line.
	nextB, nextL := bb.next, ll.next
	bb.next = 0
	f.boxes[nextB].prev = 0
	fb := f.lines[nextL].firstB
	f.lines[nextL].firstB = nextB

	// If the next Line already contained Boxes, append them to the end of the
	// nextB chain, and join the two newly linked Boxes if possible.
	if fb != 0 {
		lb := f.lines[nextL].lastBox(f)
		lbb := &f.boxes[lb]
		fbb := &f.boxes[fb]
		lbb.next = fb
		fbb.prev = lb
		f.joinBoxes(lb, fb, lbb, fbb)
	}
}

// layout inserts a soft return in the Line l if its text measures longer than
// f.maxWidth and a suitable line break point is found. This may spill text
// onto the next line, which will also be laid out, and so on recursively.
func layout(f *Frame, l int32) {
	if f.maxWidth <= 0 || f.face == nil {
		return
	}
	f.seqNum++

	for ; l != 0; l = f.lines[l].next {
		var (
			firstB     = f.lines[l].firstB
			reader     = f.lineReader(firstB, f.boxes[firstB].i)
			breakPoint bAndK
			prevR      rune
			prevRValid bool
			advance    fixed.Int26_6
		)
		for {
			r, _, err := reader.ReadRune()
			if err != nil || r == '\n' {
				return
			}
			if prevRValid {
				advance += f.face.Kern(prevR, r)
			}
			// TODO: match all whitespace, not just ' '?
			if r == ' ' {
				breakPoint = reader.bAndK()
			}
			a, ok := f.face.GlyphAdvance(r)
			if !ok {
				panic("TODO: is falling back on the U+FFFD glyph the responsibility of the caller or the Face?")
			}
			advance += a
			if r != ' ' && advance > f.maxWidth && breakPoint.b != 0 {
				breakLine(f, l, breakPoint.b, breakPoint.k)
				break
			}
			prevR, prevRValid = r, true
		}
	}
}

// Delete deletes nBytes bytes in the specified direction from the Caret's
// location. It returns the number of bytes deleted, which can be fewer than
// that requested if it hits the beginning or end of the Frame.
func (c *Caret) Delete(dir Direction, nBytes int) (dBytes int) {
	if nBytes <= 0 {
		return 0
	}

	// Convert a backwards delete of n bytes from position p to a forwards
	// delete of n bytes from position p-n.
	//
	// In general, it's easier to delete forwards than backwards. For example,
	// when crossing paragraph boundaries, it's easier to find the first line
	// of the next paragraph than the last line of the previous paragraph.
	if dir == Backwards {
		newPos := int(c.pos) - nBytes
		if newPos < 0 {
			newPos = 0
			nBytes = int(c.pos)
			if nBytes == 0 {
				return 0
			}
		}
		c.seek(int32(newPos))
	}

	if int(c.pos) == c.f.len {
		return 0
	}

	c.calculatePLBK()
	c.leanForwards()
	if c.f.boxes[c.b].i != c.k && c.splitBox(false) {
		c.leanForwards()
	}
	for nBytes > 0 && int(c.pos) != c.f.len {
		bb := &c.f.boxes[c.b]
		n := bb.j - bb.i
		newLine := n != 0 && c.f.text[bb.j-1] == '\n'
		if int(n) > nBytes {
			n = int32(nBytes)
		}
		bb.i += n
		c.k += n
		dBytes += int(n)
		nBytes -= int(n)
		c.f.len -= int(n)

		if bb.i != bb.j {
			break
		}

		if newLine {
			c.joinNextParagraph()
		}
		c.leanForwards()
	}

	// The mergeIntoOneLine will shake out any empty Boxes.
	l := c.f.mergeIntoOneLine(c.p)
	layout(c.f, l)
	c.f.invalidateCaches()

	// Compact c.f.text if it's large enough and the fraction of deleted text
	// is above some threshold. The actual threshold value (25%) is arbitrary.
	// A lower value means more frequent compactions, so less memory on average
	// but more CPU. A higher value means the opposite.
	if len(c.f.text) > 4096 && len(c.f.text)/4 < c.f.deletedLen() {
		c.f.compactText()
	}

	c.f.seqNum++
	for _, cc := range c.f.carets {
		if cc == c {
			continue
		}
		switch relPos := cc.pos - c.pos; {
		case relPos <= 0:
			// No-op.
		case relPos <= int32(dBytes):
			cc.pos = c.pos
		default:
			cc.pos -= int32(dBytes)
		}
	}
	return dBytes
}

// DeleteRunes deletes nRunes runes in the specified direction from the Caret's
// location. It returns the number of runes and bytes deleted, which can be
// fewer than that requested if it hits the beginning or end of the Frame.
func (c *Caret) DeleteRunes(dir Direction, nRunes int) (dRunes, dBytes int) {
	// Save the current Caret position, move the Caret by nRunes runes to
	// calculate how many bytes to delete, restore that saved Caret position,
	// then delete that many bytes.
	c.calculatePLBK()
	savedC := *c
	if dir == Forwards {
		for dRunes < nRunes {
			var size int
			_, size, c.b, c.k = c.f.readRune(c.b, c.k)
			if size != 0 {
				dRunes++
				dBytes += size
			} else if c.leanForwards() != leanOK {
				break
			}
		}
	} else {
		for dRunes < nRunes {
			var size int
			_, size, c.b, c.k = c.f.readLastRune(c.b, c.k)
			if size != 0 {
				dRunes++
				dBytes += size
			} else if c.leanBackwards() != leanOK {
				break
			}
		}
	}
	*c = savedC
	if dBytes != c.Delete(dir, dBytes) {
		panic("text: invalid state")
	}
	return dRunes, dBytes
}

// joinNextParagraph joins c's current and next Paragraph. That next Paragraph
// must exist, and c must be at the last Line of its current Paragraph.
func (c *Caret) joinNextParagraph() {
	pp0 := &c.f.paragraphs[c.p]
	ll0 := &c.f.lines[c.l]
	if pp0.next == 0 || ll0.next != 0 {
		panic("text: invalid state")
	}
	pp1 := &c.f.paragraphs[pp0.next]
	l1 := pp1.firstL

	ll0.next = l1
	c.f.lines[l1].prev = c.l

	toFree := pp0.next
	pp0.next = pp1.next
	if pp0.next != 0 {
		c.f.paragraphs[pp0.next].prev = c.p
	}

	c.f.freeParagraph(toFree)
}

// splitBox splits the Caret's Box into two, at the Caret's location. Unless
// force is set, it does nothing if the Caret is at either edge of its Box. It
// returns whether the Box was split. If so, the new Box is created after, not
// before, the Caret's current Box.
func (c *Caret) splitBox(force bool) bool {
	bb := &c.f.boxes[c.b]
	if !force && (c.k == bb.i || c.k == bb.j) {
		return false
	}
	newB, realloc := c.f.newBox()
	if realloc {
		bb = &c.f.boxes[c.b]
	}
	nextB := bb.next
	if nextB != 0 {
		c.f.boxes[nextB].prev = newB
	}
	c.f.boxes[newB] = Box{
		next: nextB,
		prev: c.b,
		i:    c.k,
		j:    bb.j,
	}
	bb.next = newB
	bb.j = c.k
	return true
}