// nodeReader gives the built nodes of a tree.
type nodeReader interface {
- Node(level, index int) (Node, bool)
+ 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,
// 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.
+// 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 Taelin's rollback push list, this order makes the same merges
-// as the push. The oldest pair wins a tie.
+// 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
}
// 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),
}
}
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)
}
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
+}
+
// State returns the saved form of the view.
func (v *View) State() viewState {
state := viewState{
// 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 {
- v.lines = append(v.lines, nodeKey{0, v.end})
+func (v *View) Append(tree nodeReader) (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++
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 {
- size := v.Size(tree)
+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 := v.mostDue(tree)
- if best < 0 {
- return merged
+ 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}
- size += lineSize(tree, parent) - lineSize(tree, left) - lineSize(tree, right)
+ _, 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
+ return merged, nil
}
// Coarsen takes each merge of other, a view of the same messages, and then
// 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) {
+func (v *View) Coarsen(other *View, tree nodeReader) 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++
}
v.lines = lines
+ v.nodes = nodes
v.merging = true
- v.fit(tree)
+ _, 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 {
+func (v *View) mostDue(tree nodeReader) (int, error) {
best := -1
bestDue := 0.0
for n := 0; n+1 < len(v.lines); n++ {
continue
}
- _, built := tree.Node(left.level+1, left.index/2)
- if !built {
+ last := nodeEnd(right.level, right.index) - 1
+ due := math.Ldexp(float64(v.end-last), -left.level)
+ if best >= 0 && due <= bestDue {
continue
}
- last := nodeEnd(right.level, right.index) - 1
- due := math.Ldexp(float64(v.end-last), -left.level)
- if best < 0 || due > bestDue {
+ built, err := tree.Built(left.level+1, left.index/2)
+ if err != nil {
+ return -1, err
+ }
+
+ if built {
best = n
bestDue = due
}
}
- return best
+ 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}
+ 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
+ }
+ }
}
// Size returns the sum of the line sizes.
-func (v *View) Size(tree nodeReader) int {
+func (v *View) Size() int {
size := 0
for _, line := range v.lines {
- size += lineSize(tree, line)
+ 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)
+ }
+
+ return node.Size
+}
+
// 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 {
+func (v *View) Render() string {
var text strings.Builder
text.WriteString("<chat>\n")
for _, line := range v.lines {
- renderLine(&text, tree, line)
+ v.renderLine(&text, line)
}
text.WriteString("</chat>")
return text.String()
}
+// renderLine writes one view line, "id+n|text", and a newline.
+func (v *View) renderLine(text *strings.Builder, line nodeKey) {
+ body := pending
+ 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(tree nodeReader, end int) string {
+func (v *View) Context(end int) string {
var text strings.Builder
text.WriteString("<chat>\n")
for _, line := range v.lines {
- _, built := tree.Node(line.level, line.index)
+ _, built := v.nodes[line]
if !built || nodeEnd(line.level, line.index) > end {
break
}
- renderLine(&text, tree, line)
+ v.renderLine(&text, line)
}
text.WriteString("</chat>")
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)
- }
-
- return node.Size
-}
-
-// 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)
- 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')
-}
projects / onechat / blobdiff