git.giacomolli.uk - onechat/blob - view.go

   1 package main
   2
   3 import (
   4         "fmt"
   5         "math"
   6         "math/bits"
   7         "strconv"
   8         "strings"
   9 )
  10
  11 const (
  12         // chatHigh and chatLow are the limits of the chat view in bytes.
  13         chatHigh = 128000
  14         chatLow  = 64000
  15
  16         // pending is the text of a line that is not built yet.
  17         pending = "(not summarized yet: zoom it)"
  18 )
  19
  20 // nodeReader gives the built nodes of a tree.
  21 type nodeReader interface {
  22         Node(level, index int) (Node, bool)
  23 }
  24
  25 // View is a list of tree nodes that covers messages 0 to end-1 without a gap,
  26 // oldest first. Each new message appends its leaf as a line. Once the size of
  27 // the view goes above high, one batch merges the most due sibling pairs until
  28 // the size is at most low. A batch merges only pairs whose parent is built. If
  29 // the batch cannot get to low, it continues at each new message until it does.
  30 //
  31 // The size of a line is the size of its node text, or the size of the pending
  32 // text when the node is not built.
  33 //
  34 // For the sibling pair (l, i) and (l, i+1), due is (T - last) / 2^l, with T the
  35 // number of messages and last the ID of the last message of the pair. That is
  36 // how long ago the pair ended, measured in its own line size. With a budget of
  37 // the length of Taelin's rollback push list, this order makes the same merges
  38 // as the push. The oldest pair wins a tie.
  39 type View struct {
  40         high    int
  41         low     int
  42         lines   []nodeKey
  43         end     int
  44         merging bool
  45 }
  46
  47 // viewState is the saved form of a View. The limits are not part of it.
  48 type viewState struct {
  49         Lines   [][2]int `json:"lines"`
  50         Merging bool     `json:"merging"`
  51 }
  52
  53 // newView returns an empty view with the limits high and low.
  54 func newView(high, low int) *View {
  55         return &View{
  56                 high: high,
  57                 low:  low,
  58         }
  59 }
  60
  61 // restoreView returns the view of state with the limits high and low. Each line
  62 // must continue the one before it, and each line above level 0 must be built.
  63 func restoreView(state viewState, high, low int, tree nodeReader) (*View, error) {
  64         v := newView(high, low)
  65         v.merging = state.Merging
  66         for _, pair := range state.Lines {
  67                 line := nodeKey{pair[0], pair[1]}
  68                 if line.level < 0 || line.level >= bits.UintSize-2 || line.index < 0 || line.index<<line.level != v.end {
  69                         return nil, fmt.Errorf("view line (%d, %d) does not start at message %d", line.level, line.index, v.end)
  70                 }
  71
  72                 _, built := tree.Node(line.level, line.index)
  73                 if line.level > 0 && !built {
  74                         return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
  75                 }
  76
  77                 v.lines = append(v.lines, line)
  78                 v.end = nodeEnd(line.level, line.index)
  79         }
  80
  81         return v, nil
  82 }
  83
  84 // State returns the saved form of the view.
  85 func (v *View) State() viewState {
  86         state := viewState{
  87                 Lines:   make([][2]int, len(v.lines)),
  88                 Merging: v.merging,
  89         }
  90
  91         for n, line := range v.lines {
  92                 state.Lines[n] = [2]int{line.level, line.index}
  93         }
  94
  95         return state
  96 }
  97
  98 // Append adds the leaf of the next message as a line and merges when the view
  99 // is too large.
 100 func (v *View) Append(tree nodeReader) {
 101         v.lines = append(v.lines, nodeKey{0, v.end})
 102         v.end++
 103         v.fit(tree)
 104 }
 105
 106 func (v *View) fit(tree nodeReader) {
 107         size := v.Size(tree)
 108         if size > v.high {
 109                 v.merging = true
 110         }
 111
 112         for v.merging && size > v.low {
 113                 best := v.mostDue(tree)
 114                 if best < 0 {
 115                         return
 116                 }
 117
 118                 left, right := v.lines[best], v.lines[best+1]
 119                 parent := nodeKey{left.level + 1, left.index / 2}
 120                 size += lineSize(tree, parent) - lineSize(tree, left) - lineSize(tree, right)
 121                 v.lines[best] = parent
 122                 v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
 123         }
 124
 125         v.merging = false
 126 }
 127
 128 // mostDue returns the position of the left line of the most due sibling pair
 129 // whose parent is built, or -1 when there is no such pair.
 130 func (v *View) mostDue(tree nodeReader) int {
 131         best := -1
 132         bestDue := 0.0
 133         for n := 0; n+1 < len(v.lines); n++ {
 134                 left, right := v.lines[n], v.lines[n+1]
 135                 if left.index%2 != 0 || right.level != left.level || right.index != left.index+1 {
 136                         continue
 137                 }
 138
 139                 _, built := tree.Node(left.level+1, left.index/2)
 140                 if !built {
 141                         continue
 142                 }
 143
 144                 last := nodeEnd(right.level, right.index) - 1
 145                 due := math.Ldexp(float64(v.end-last), -left.level)
 146                 if best < 0 || due > bestDue {
 147                         best = n
 148                         bestDue = due
 149                 }
 150         }
 151
 152         return best
 153 }
 154
 155 // Size returns the sum of the line sizes.
 156 func (v *View) Size(tree nodeReader) int {
 157         size := 0
 158         for _, line := range v.lines {
 159                 size += lineSize(tree, line)
 160         }
 161
 162         return size
 163 }
 164
 165 // Render returns the view as the model reads it: one line "id+n|text" for each
 166 // node inside <chat> tags, with the newlines of the text as spaces.
 167 func (v *View) Render(tree nodeReader) string {
 168         var text strings.Builder
 169         text.WriteString("<chat>\n")
 170         for _, line := range v.lines {
 171                 renderLine(&text, tree, line)
 172         }
 173
 174         text.WriteString("</chat>")
 175
 176         return text.String()
 177 }
 178
 179 // lineSize returns the size of a view line.
 180 func lineSize(tree nodeReader, line nodeKey) int {
 181         node, built := tree.Node(line.level, line.index)
 182         if !built {
 183                 return len(pending)
 184         }
 185
 186         return node.Size
 187 }
 188
 189 // renderLine writes one view line, "id+n|text", and a newline.
 190 func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
 191         body := pending
 192         node, built := tree.Node(line.level, line.index)
 193         if built {
 194                 body = strings.ReplaceAll(node.Text, "\n", " ")
 195         }
 196
 197         text.WriteString(strconv.Itoa(line.index << line.level))
 198         text.WriteByte('+')
 199         text.WriteString(strconv.Itoa(1 << line.level))
 200         text.WriteByte('|')
 201         text.WriteString(body)
 202         text.WriteByte('\n')
 203 }