Send the compaction view in blocks of four lines

[onechat] / view.go

diff --git a/view.go b/view.go
index 158b59e65a130df5def07ed10ea6e32d53a87fd4..70182d0114470f36df90543f70a7faab103a086b 100644 (file)
--- a/view.go
+++ b/view.go
@@ -13,13 +13,19 @@ const (
        chatHigh = 128000
        chatLow  = 64000
 
        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)"
 )
 
 // nodeReader gives the built nodes of a tree.
 type nodeReader interface {
        // pending is the text of a line that is not built yet.
        pending = "(not summarized yet: zoom it)"
 )
 
 // 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,
 }
 
 // View is a list of tree nodes that covers messages 0 to end-1 without a gap,


@@ -28,18 +34,20 @@ type nodeReader interface {
 // 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 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
 //
 // 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
 type View struct {
        high    int
        low     int
        lines   []nodeKey

+       nodes   map[nodeKey]Node

        end     int
        merging bool
 }
        end     int
        merging bool
 }


@@ -53,8 +61,9 @@ type viewState struct {
 // newView returns an empty view with the limits high and low.
 func newView(high, low int) *View {
        return &View{
 // 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),

        }
 }
 
        }
 }
 


@@ -69,7 +78,11 @@ func restoreView(state viewState, high, low int, tree nodeReader) (*View, error)
                        return nil, fmt.Errorf("view line (%d, %d) does not start at message %d", line.level, line.index, 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)
                }
                if line.level > 0 && !built {
                        return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
                }


@@ -81,6 +94,18 @@ func restoreView(state viewState, high, low int, tree nodeReader) (*View, error)
        return v, nil
 }
 
        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{
 // State returns the saved form of the view.
 func (v *View) State() viewState {
        state := viewState{


@@ -96,38 +121,98 @@ func (v *View) State() viewState {
 }
 
 // Append adds the leaf of the next message as a line and merges when the view
 }
 
 // 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 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++
        v.end++

-       v.fit(tree)
+
+       return v.fit(tree)

 }
 
 }
 

-func (v *View) fit(tree nodeReader) {
-       size := v.Size(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
        }
 
        if size > v.high {
                v.merging = true
        }
 

+       merged := false

        for v.merging && size > v.low {
        for v.merging && size > v.low {

-               best := v.mostDue(tree)
-               if best < 0 {
-                       return
+               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}
                }
 
                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:]...)
                v.lines[best] = parent
                v.lines = append(v.lines[:best+1], v.lines[best+2:]...)

+               merged = true

        }
 
        v.merging = false
        }
 
        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))
+       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

 }
 
 // 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.
 }
 
 // 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++ {
        best := -1
        bestDue := 0.0
        for n := 0; n+1 < len(v.lines); n++ {


@@ -136,39 +221,69 @@ func (v *View) mostDue(tree nodeReader) int {
                        continue
                }
 
                        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
                }
 
                        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
                }
        }
 
                        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.
 }
 
 // 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 := 0
        for _, line := range v.lines {

-               size += lineSize(tree, line)
+               size += v.lineSize(line)

        }
 
        return size
 }
 
        }
 
        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.
 // 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 {
        var text strings.Builder
        text.WriteString("<chat>\n")
        for _, line := range v.lines {

-               renderLine(&text, tree, line)
+               v.renderLine(&text, line)

        }
 
        text.WriteString("</chat>")
        }
 
        text.WriteString("</chat>")


@@ -176,20 +291,10 @@ func (v *View) Render(tree nodeReader) string {
        return text.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)
-       }
-
-       return node.Size
-}
-

 // renderLine writes one view line, "id+n|text", and a newline.
 // renderLine writes one view line, "id+n|text", and a newline.

-func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
+func (v *View) renderLine(text *strings.Builder, line nodeKey) {

        body := pending
        body := pending

-       node, built := tree.Node(line.level, line.index)
+       node, built := v.nodes[line]

        if built {
                body = strings.ReplaceAll(node.Text, "\n", " ")
        }
        if built {
                body = strings.ReplaceAll(node.Text, "\n", " ")
        }


@@ -201,3 +306,23 @@ func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
        text.WriteString(body)
        text.WriteByte('\n')
 }
        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()
+}