Store shared private images by content hash

[onechat] / view.go

diff --git a/view.go b/view.go
index a75b1d8418fc9857d6aafbf38a822c989a817d77..235719877517ad1cbce460dfa18ccb3c07af5366 100644 (file)
--- a/view.go
+++ b/view.go
@@ -9,71 +9,36 @@ import (
 )
 
 const (
 )
 
 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,
 // 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.
        }
 }
 
 // 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 {
        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)
                }
                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)
                }


@@ -94,21 +59,33 @@ 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
+// 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.
 }
 
 // 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,
        }
                Lines:   make([][2]int, len(v.lines)),
                Merging: v.merging,
        }


@@ -122,8 +99,8 @@ func (v *View) 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.
 
 // 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
        _, err := v.load(tree, line)
        if err != nil {
                return false, err


@@ -135,49 +112,14 @@ func (v *View) Append(tree nodeReader) (bool, error) {
        return v.fit(tree)
 }
 
        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.
 // 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]
        mine, theirs := 0, 0
        for start := 0; start < v.end; {
                line := v.lines[mine]


@@ -210,40 +152,9 @@ func (v *View) Coarsen(other *View, tree nodeReader) error {
        return err
 }
 
        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) {
 // 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 {
        for n := len(v.lines) - 1; n >= 0; n-- {
                line := v.lines[n]
                if line == key {


@@ -257,24 +168,16 @@ func (v *View) Refresh(node Node) {
        }
 }
 
        }
 }
 

-// 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 {
        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
 }
 
 // Render returns the view as the model reads it: one line "id+n|text" for each


@@ -294,16 +197,88 @@ func (v *View) LinesWithout(skip map[int]bool) []string {
                }
 
                var text strings.Builder
                }
 
                var text strings.Builder

+

                v.renderLine(&text, line)
                v.renderLine(&text, line)

+

                lines = append(lines, text.String())
        }
 
        return lines
 }
 
                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)
+       }
+
+       text.WriteString("</chat>")
+
+       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.
 // 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", " ")
        node, built := v.nodes[line]
        if built {
                body = strings.ReplaceAll(node.Text, "\n", " ")


@@ -317,22 +292,65 @@ func (v *View) renderLine(text *strings.Builder, line nodeKey) {
        text.WriteByte('\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 {
        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, fmt.Errorf("check parent node: %w", 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)

 }
 }