[onechat] / view.go

package main

import (
        "fmt"
        "math"
        "math/bits"
        "strconv"
        "strings"
)

const (
        // 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)"
)

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

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

// newView returns an empty view with the limits high and low.
func newView(high, low int) *View {
        return &View{
                high:  high,
                low:   low,
                nodes: make(map[NodeKey]Node),
        }
}

// State returns the saved form of the view.
func (v *View) State() ViewState {
        state := ViewState{
                Lines:   make([][2]int, len(v.lines)),
                Merging: v.merging,
        }

        for n, line := range v.lines {
                state.Lines[n] = [2]int{line.level, line.index}
        }

        return state
}

// Append adds the leaf of the next message as a line and merges when the view
// 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, fmt.Errorf("load appended leaf: %w", err)
        }

        v.lines = append(v.lines, line)
        v.end++

        return v.fit(tree)
}

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

        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 {
                        if err != nil {
                                return merged, fmt.Errorf("choose merge candidate: %w", err)
                        }

                        return merged, nil
                }

                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, fmt.Errorf("load merged parent: %w", 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
}

// 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, fmt.Errorf("check parent node: %w", 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
}

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

                lines = append(lines, line)
                if built {
                        nodes[line] = node
                }

                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.lines = lines
        v.nodes = nodes
        v.merging = true
        _, err := v.fit(tree)

        return err
}

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

                if line.index<<line.level <= key.index<<key.level {
                        return
                }
        }
}

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

// 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 {
                if line.level == 0 && skip[line.index] {
                        continue
                }

                var text strings.Builder

                v.renderLine(&text, line)

                lines = append(lines, text.String())
        }

        return lines
}

// renderLine writes one view line, "id+n|text", and a newline.
func (v *View) renderLine(text *strings.Builder, line NodeKey) {
        body := viewPending
        node, built := v.nodes[line]
        if built {
                body = strings.ReplaceAll(node.Text, "\n", " ")
        }

        text.WriteString(strconv.Itoa(line.index << line.level))
        text.WriteByte('+')
        text.WriteString(strconv.Itoa(1 << line.level))
        text.WriteByte('|')
        text.WriteString(body)
        text.WriteByte('\n')
}

// 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 {
                _, built := v.nodes[line]
                if !built || nodeEnd(line.level, line.index) > end {
                        break
                }

                v.renderLine(&text, line)
        }

        text.WriteString("</chat>")

        return text.String()
}

// 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 ViewNodeReader) (*View, error) {
        v := newView(high, low)
        v.merging = state.Merging
        for _, pair := range state.Lines {
                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, err := v.load(tree, line)
                if err != nil {
                        return nil, fmt.Errorf("load restored view node: %w", err)
                }

                if line.level > 0 && !built {
                        return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
                }

                v.lines = append(v.lines, line)
                v.end = nodeEnd(line.level, line.index)
        }

        return v, nil
}