)
const (
- // chatHigh and chatLow are the limits of the chat view in bytes.
- chatHigh = 128000
- chatLow = 64000
-
- // compactionHigh and compactionLow are the limits of the compaction
- // view in bytes.
- compactionHigh = 32000
- compactionLow = 16000
-
- // 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 {
- Built(level, index int) (bool, error)
- Node(level, index int) (Node, bool, error)
-}
-
-// 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"`
-}
-
// 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),
+ 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)
}
return v, nil
}
-// load keeps the node of line when it is built, and tells if it is.
-func (v *View) load(tree nodeReader, 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
+// 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,
}
// 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 nodeReader) (bool, error) {
- line := nodeKey{0, v.end}
+func (v *View) Append(tree ViewNodeReader) (bool, error) {
+ line := NodeKey{0, v.end}
_, err := v.load(tree, line)
if err != nil {
return false, err
return v.fit(tree)
}
-// fit merges the most due pairs while a batch runs, and tells if a merge
-// changed the view.
-func (v *View) fit(tree nodeReader) (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
-}
-
// 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 nodeReader) error {
- lines := make([]nodeKey, 0, len(v.lines))
- nodes := make(map[nodeKey]Node, len(v.nodes))
+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]
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, 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
-}
-
// Refresh keeps node when it is the node of a pending line.
func (v *View) Refresh(node Node) {
- key := nodeKey{node.Level, node.Index}
+ key := NodeKey{node.Level, node.Index}
for n := len(v.lines) - 1; n >= 0; n-- {
line := v.lines[n]
if line == key {
}
}
-// Size returns the sum of the line sizes.
-func (v *View) Size() int {
- size := 0
+// Pending tells if a line of the view is not built yet.
+func (v *View) Pending() bool {
for _, line := range v.lines {
- size += v.lineSize(line)
- }
-
- return size
-}
-
-// lineSize returns the size of a view line.
-func (v *View) lineSize(line nodeKey) int {
- node, built := v.nodes[line]
- if !built {
- return len(pending)
+ _, built := v.nodes[line]
+ if !built {
+ return true
+ }
}
- return node.Size
+ 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 v.RenderWithout(nil)
+ return "<chat>\n" + strings.Join(v.LinesWithout(nil), "") + "</chat>"
}
-// RenderWithout returns the view as Render does, without the leaf lines of the
-// messages in skip. A line that merges such a message with others stays.
-func (v *View) RenderWithout(skip map[int]bool) string {
- var text strings.Builder
- text.WriteString("<chat>\n")
+// 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
+}
+
+// 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)
}
return text.String()
}
+// 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 {
+ 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 (v *View) renderLine(text *strings.Builder, line nodeKey) {
- body := pending
+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.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")
+// Size returns the sum of the line sizes.
+func (v *View) Size() int {
+ size := 0
for _, line := range v.lines {
- _, built := v.nodes[line]
- if !built || nodeEnd(line.level, line.index) > end {
- break
+ 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
}
- v.renderLine(&text, line)
+ 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
+ }
}
- text.WriteString("</chat>")
+ return best, nil
+}
- return text.String()
+// 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)
}
projects / onechat / blobdiff