X-Git-Url: https://git.giacomolli.uk/onechat/blobdiff_plain/9f17bfb1173524553fff5301b0664267b430e6e3..49566fe4e40a18434320829c5cb6a6eff1b4ec78:/view.go?ds=inline

diff --git a/view.go b/view.go
index 158b59e..233e089 100644
--- a/view.go
+++ b/view.go
@@ -9,67 +9,45 @@ import (
 )
 
 const (
-	// chatHigh and chatLow are the limits of the chat view in bytes.
-	chatHigh = 128000
-	chatLow  = 64000
-
-	// pending is the text of a line that is not built yet.
-	pending = "(not summarized yet: zoom it)"
+	// viewChatHigh and viewChatLow are the limits of the chat view in
+	// bytes.
+	viewChatHigh = 128000
+	viewChatLow  = 64000
+
+	// viewCompactionHigh and viewCompactionLow are the limits of the
+	// compaction view in bytes.
+	viewCompactionHigh = 32000
+	viewCompactionLow  = 16000
+
+	// viewPending is the text of a line that is not built yet.
+	viewPending = "(not summarized yet: zoom it)"
 )
 
-// nodeReader gives the built nodes of a tree.
-type nodeReader interface {
-	Node(level, index int) (Node, bool)
-}
-
-// View is a list of tree nodes that covers messages 0 to end-1 without a gap,
-// oldest first. Each new message appends its leaf as a line. Once the size of
-// the view goes above high, one batch merges the most due sibling pairs until
-// the size is at most low. A batch merges only pairs whose parent is built. If
-// the batch cannot get to low, it continues at each new message until it does.
-//
-// The size of a line is the size of its node text, or the size of the pending
-// text when the node is not built.
-//
-// For the sibling pair (l, i) and (l, i+1), due is (T - last) / 2^l, with T the
-// number of messages and last the ID of the last message of the pair. That is
-// how long ago the pair ended, measured in its own line size. With a budget of
-// the length of Taelin's rollback push list, this order makes the same merges
-// as the push. The oldest pair wins a tie.
-type View struct {
-	high    int
-	low     int
-	lines   []nodeKey
-	end     int
-	merging bool
-}
-
-// viewState is the saved form of a View. The limits are not part of it.
-type viewState struct {
-	Lines   [][2]int `json:"lines"`
-	Merging bool     `json:"merging"`
-}
-
 // newView returns an empty view with the limits high and low.
 func newView(high, low int) *View {
 	return &View{
-		high: high,
-		low:  low,
+		high:  high,
+		low:   low,
+		nodes: make(map[NodeKey]Node),
 	}
 }
 
 // restoreView returns the view of state with the limits high and low. Each line
 // must continue the one before it, and each line above level 0 must be built.
-func restoreView(state viewState, high, low int, tree nodeReader) (*View, error) {
+func restoreView(state ViewState, high, low int, tree ViewNodeReader) (*View, error) {
 	v := newView(high, low)
 	v.merging = state.Merging
 	for _, pair := range state.Lines {
-		line := nodeKey{pair[0], pair[1]}
+		line := NodeKey{pair[0], pair[1]}
 		if line.level < 0 || line.level >= bits.UintSize-2 || line.index < 0 || line.index<<line.level != v.end {
 			return nil, fmt.Errorf("view line (%d, %d) does not start at message %d", line.level, line.index, v.end)
 		}
 
-		_, built := tree.Node(line.level, line.index)
+		built, err := v.load(tree, line)
+		if err != nil {
+			return nil, err
+		}
+
 		if line.level > 0 && !built {
 			return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
 		}
@@ -81,9 +59,33 @@ func restoreView(state viewState, high, low int, tree nodeReader) (*View, error)
 	return v, nil
 }
 
+// View is a list of tree nodes that covers messages 0 to end-1 without a gap,
+// oldest first. Each new message appends its leaf as a line. Once the size of
+// the view goes above high, one batch merges the most due sibling pairs until
+// the size is at most low. A batch merges only pairs whose parent is built. If
+// the batch cannot get to low, it continues at each new message until it does.
+//
+// The view keeps the nodes of its built lines in memory, so its size and its
+// text need no read of the tree. The size of a line is the size of its node
+// text, or the size of the pending text when the node is not built.
+//
+// For the sibling pair (l, i) and (l, i+1), due is (T - last) / 2^l, with T the
+// number of messages and last the ID of the last message of the pair. That is
+// how long ago the pair ended, measured in its own line size. With a budget of
+// the length of the rollback push list of the reference design, this order
+// makes the same merges as the push. The oldest pair wins a tie.
+type View struct {
+	high    int
+	low     int
+	lines   []NodeKey
+	nodes   map[NodeKey]Node
+	end     int
+	merging bool
+}
+
 // State returns the saved form of the view.
-func (v *View) State() viewState {
-	state := viewState{
+func (v *View) State() ViewState {
+	state := ViewState{
 		Lines:   make([][2]int, len(v.lines)),
 		Merging: v.merging,
 	}
@@ -96,79 +98,125 @@ func (v *View) State() viewState {
 }
 
 // Append adds the leaf of the next message as a line and merges when the view
-// is too large.
-func (v *View) Append(tree nodeReader) {
-	v.lines = append(v.lines, nodeKey{0, v.end})
+// is too large. It tells if a merge changed the view.
+func (v *View) Append(tree ViewNodeReader) (bool, error) {
+	line := NodeKey{0, v.end}
+	_, err := v.load(tree, line)
+	if err != nil {
+		return false, err
+	}
+
+	v.lines = append(v.lines, line)
 	v.end++
-	v.fit(tree)
+
+	return v.fit(tree)
 }
 
-func (v *View) fit(tree nodeReader) {
-	size := v.Size(tree)
-	if size > v.high {
-		v.merging = true
-	}
+// Coarsen takes each merge of other, a view of the same messages, and then
+// merges in one batch until the size is at most low. Each line of the result is
+// the coarser of the two lines that start at its first message. Dyadic ranges
+// either nest or do not overlap, so the result covers the messages without a
+// gap.
+func (v *View) Coarsen(other *View, tree ViewNodeReader) error {
+	lines := make([]NodeKey, 0, len(v.lines))
+	nodes := make(map[NodeKey]Node, len(v.nodes))
+	mine, theirs := 0, 0
+	for start := 0; start < v.end; {
+		line := v.lines[mine]
+		node, built := v.nodes[line]
+		if other.lines[theirs].level > line.level {
+			line = other.lines[theirs]
+			node, built = other.nodes[line]
+		}
 
-	for v.merging && size > v.low {
-		best := v.mostDue(tree)
-		if best < 0 {
-			return
+		lines = append(lines, line)
+		if built {
+			nodes[line] = node
 		}
 
-		left, right := v.lines[best], v.lines[best+1]
-		parent := nodeKey{left.level + 1, left.index / 2}
-		size += lineSize(tree, parent) - lineSize(tree, left) - lineSize(tree, right)
-		v.lines[best] = parent
-		v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
+		start = nodeEnd(line.level, line.index)
+		for mine < len(v.lines) && v.lines[mine].index<<v.lines[mine].level < start {
+			mine++
+		}
+
+		for theirs < len(other.lines) && other.lines[theirs].index<<other.lines[theirs].level < start {
+			theirs++
+		}
 	}
 
-	v.merging = false
+	v.lines = lines
+	v.nodes = nodes
+	v.merging = true
+	_, err := v.fit(tree)
+
+	return err
 }
 
-// mostDue returns the position of the left line of the most due sibling pair
-// whose parent is built, or -1 when there is no such pair.
-func (v *View) mostDue(tree nodeReader) int {
-	best := -1
-	bestDue := 0.0
-	for n := 0; n+1 < len(v.lines); n++ {
-		left, right := v.lines[n], v.lines[n+1]
-		if left.index%2 != 0 || right.level != left.level || right.index != left.index+1 {
-			continue
+// Refresh keeps node when it is the node of a pending line.
+func (v *View) Refresh(node Node) {
+	key := NodeKey{node.Level, node.Index}
+	for n := len(v.lines) - 1; n >= 0; n-- {
+		line := v.lines[n]
+		if line == key {
+			v.nodes[key] = node
+			return
 		}
 
-		_, built := tree.Node(left.level+1, left.index/2)
-		if !built {
-			continue
+		if line.index<<line.level <= key.index<<key.level {
+			return
 		}
+	}
+}
 
-		last := nodeEnd(right.level, right.index) - 1
-		due := math.Ldexp(float64(v.end-last), -left.level)
-		if best < 0 || due > bestDue {
-			best = n
-			bestDue = due
+// Pending tells if a line of the view is not built yet.
+func (v *View) Pending() bool {
+	for _, line := range v.lines {
+		_, built := v.nodes[line]
+		if !built {
+			return true
 		}
 	}
 
-	return best
+	return false
 }
 
-// Size returns the sum of the line sizes.
-func (v *View) Size(tree nodeReader) int {
-	size := 0
+// Render returns the view as the model reads it: one line "id+n|text" for each
+// node inside <chat> tags, with the newlines of the text as spaces.
+func (v *View) Render() string {
+	return "<chat>\n" + strings.Join(v.LinesWithout(nil), "") + "</chat>"
+}
+
+// LinesWithout returns the lines of the view as the model reads them, each with
+// its newline, without the leaf lines of the messages in skip. A line that
+// merges such a message with others stays.
+func (v *View) LinesWithout(skip map[int]bool) []string {
+	lines := make([]string, 0, len(v.lines))
 	for _, line := range v.lines {
-		size += lineSize(tree, line)
+		if line.level == 0 && skip[line.index] {
+			continue
+		}
+
+		var text strings.Builder
+		v.renderLine(&text, line)
+		lines = append(lines, text.String())
 	}
 
-	return size
+	return lines
 }
 
-// Render returns the view as the model reads it: one line "id+n|text" for each
-// node inside <chat> tags, with the newlines of the text as spaces.
-func (v *View) Render(tree nodeReader) string {
+// Context returns the lines of the view before message end as the model reads
+// them. It stops at the first line that is not built, so a compaction never
+// sees a pending mark or a part of a message.
+func (v *View) Context(end int) string {
 	var text strings.Builder
 	text.WriteString("<chat>\n")
 	for _, line := range v.lines {
-		renderLine(&text, tree, line)
+		_, built := v.nodes[line]
+		if !built || nodeEnd(line.level, line.index) > end {
+			break
+		}
+
+		v.renderLine(&text, line)
 	}
 
 	text.WriteString("</chat>")
@@ -176,20 +224,57 @@ func (v *View) Render(tree nodeReader) string {
 	return text.String()
 }
 
-// lineSize returns the size of a view line.
-func lineSize(tree nodeReader, line nodeKey) int {
-	node, built := tree.Node(line.level, line.index)
-	if !built {
-		return len(pending)
+// load keeps the node of line when it is built, and tells if it is.
+func (v *View) load(tree ViewNodeReader, line NodeKey) (bool, error) {
+	node, built, err := tree.Node(line.level, line.index)
+	if err != nil || !built {
+		return false, err
 	}
 
-	return node.Size
+	v.nodes[line] = node
+
+	return true, nil
+}
+
+// fit merges the most due pairs while a batch runs, and tells if a merge
+// changed the view.
+func (v *View) fit(tree ViewNodeReader) (bool, error) {
+	size := v.Size()
+	if size > v.high {
+		v.merging = true
+	}
+
+	merged := false
+	for v.merging && size > v.low {
+		best, err := v.mostDue(tree)
+		if err != nil || best < 0 {
+			return merged, err
+		}
+
+		left, right := v.lines[best], v.lines[best+1]
+		parent := NodeKey{left.level + 1, left.index / 2}
+		_, err = v.load(tree, parent)
+		if err != nil {
+			return merged, err
+		}
+
+		size += v.lineSize(parent) - v.lineSize(left) - v.lineSize(right)
+		delete(v.nodes, left)
+		delete(v.nodes, right)
+		v.lines[best] = parent
+		v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
+		merged = true
+	}
+
+	v.merging = false
+
+	return merged, nil
 }
 
 // renderLine writes one view line, "id+n|text", and a newline.
-func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
-	body := pending
-	node, built := tree.Node(line.level, line.index)
+func (v *View) renderLine(text *strings.Builder, line NodeKey) {
+	body := viewPending
+	node, built := v.nodes[line]
 	if built {
 		body = strings.ReplaceAll(node.Text, "\n", " ")
 	}
@@ -201,3 +286,66 @@ func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
 	text.WriteString(body)
 	text.WriteByte('\n')
 }
+
+// Size returns the sum of the line sizes.
+func (v *View) Size() int {
+	size := 0
+	for _, line := range v.lines {
+		size += v.lineSize(line)
+	}
+
+	return size
+}
+
+// mostDue returns the position of the left line of the most due sibling pair
+// whose parent is built, or -1 when there is no such pair.
+func (v *View) mostDue(tree ViewNodeReader) (int, error) {
+	best := -1
+	bestDue := 0.0
+	for n := 0; n+1 < len(v.lines); n++ {
+		left, right := v.lines[n], v.lines[n+1]
+		if left.index%2 != 0 || right.level != left.level || right.index != left.index+1 {
+			continue
+		}
+
+		last := nodeEnd(right.level, right.index) - 1
+		due := math.Ldexp(float64(v.end-last), -left.level)
+		if best >= 0 && due <= bestDue {
+			continue
+		}
+
+		built, err := tree.Built(left.level+1, left.index/2)
+		if err != nil {
+			return -1, err
+		}
+
+		if built {
+			best = n
+			bestDue = due
+		}
+	}
+
+	return best, nil
+}
+
+// lineSize returns the size of a view line.
+func (v *View) lineSize(line NodeKey) int {
+	node, built := v.nodes[line]
+	if !built {
+		return len(viewPending)
+	}
+
+	return node.Size
+}
+
+// ViewState is the saved form of a View. The limits are not part of it.
+type ViewState struct {
+	Lines   [][2]int `json:"lines"`
+	Merging bool     `json:"merging"`
+}
+
+// ViewNodeReader gives the built nodes of a tree.
+type ViewNodeReader interface {
+	Built(level, index int) (bool, error)
+	Node(level, index int) (Node, bool, error)
+}