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         // compactionHigh and compactionLow are the limits of the compaction
  17         // view in bytes.
  18         compactionHigh = 32000
  19         compactionLow  = 16000
  20
  21         // pending is the text of a line that is not built yet.
  22         pending = "(not summarized yet: zoom it)"
  23 )
  24
  25 // nodeReader gives the built nodes of a tree.
  26 type nodeReader interface {
  27         Built(level, index int) (bool, error)
  28         Node(level, index int) (Node, bool, error)
  29 }
  30
  31 // View is a list of tree nodes that covers messages 0 to end-1 without a gap,
  32 // oldest first. Each new message appends its leaf as a line. Once the size of
  33 // the view goes above high, one batch merges the most due sibling pairs until
  34 // the size is at most low. A batch merges only pairs whose parent is built. If
  35 // the batch cannot get to low, it continues at each new message until it does.
  36 //
  37 // The view keeps the nodes of its built lines in memory, so its size and its
  38 // text need no read of the tree. The size of a line is the size of its node
  39 // text, or the size of the pending text when the node is not built.
  40 //
  41 // For the sibling pair (l, i) and (l, i+1), due is (T - last) / 2^l, with T the
  42 // number of messages and last the ID of the last message of the pair. That is
  43 // how long ago the pair ended, measured in its own line size. With a budget of
  44 // the length of the rollback push list of the reference design, this order
  45 // makes the same merges as the push. The oldest pair wins a tie.
  46 type View struct {
  47         high    int
  48         low     int
  49         lines   []nodeKey
  50         nodes   map[nodeKey]Node
  51         end     int
  52         merging bool
  53 }
  54
  55 // viewState is the saved form of a View. The limits are not part of it.
  56 type viewState struct {
  57         Lines   [][2]int `json:"lines"`
  58         Merging bool     `json:"merging"`
  59 }
  60
  61 // newView returns an empty view with the limits high and low.
  62 func newView(high, low int) *View {
  63         return &View{
  64                 high:  high,
  65                 low:   low,
  66                 nodes: make(map[nodeKey]Node),
  67         }
  68 }
  69
  70 // restoreView returns the view of state with the limits high and low. Each line
  71 // must continue the one before it, and each line above level 0 must be built.
  72 func restoreView(state viewState, high, low int, tree nodeReader) (*View, error) {
  73         v := newView(high, low)
  74         v.merging = state.Merging
  75         for _, pair := range state.Lines {
  76                 line := nodeKey{pair[0], pair[1]}
  77                 if line.level < 0 || line.level >= bits.UintSize-2 || line.index < 0 || line.index<<line.level != v.end {
  78                         return nil, fmt.Errorf("view line (%d, %d) does not start at message %d", line.level, line.index, v.end)
  79                 }
  80
  81                 built, err := v.load(tree, line)
  82                 if err != nil {
  83                         return nil, err
  84                 }
  85
  86                 if line.level > 0 && !built {
  87                         return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
  88                 }
  89
  90                 v.lines = append(v.lines, line)
  91                 v.end = nodeEnd(line.level, line.index)
  92         }
  93
  94         return v, nil
  95 }
  96
  97 // load keeps the node of line when it is built, and tells if it is.
  98 func (v *View) load(tree nodeReader, line nodeKey) (bool, error) {
  99         node, built, err := tree.Node(line.level, line.index)
 100         if err != nil || !built {
 101                 return false, err
 102         }
 103
 104         v.nodes[line] = node
 105
 106         return true, nil
 107 }
 108
 109 // State returns the saved form of the view.
 110 func (v *View) State() viewState {
 111         state := viewState{
 112                 Lines:   make([][2]int, len(v.lines)),
 113                 Merging: v.merging,
 114         }
 115
 116         for n, line := range v.lines {
 117                 state.Lines[n] = [2]int{line.level, line.index}
 118         }
 119
 120         return state
 121 }
 122
 123 // Append adds the leaf of the next message as a line and merges when the view
 124 // is too large. It tells if a merge changed the view.
 125 func (v *View) Append(tree nodeReader) (bool, error) {
 126         line := nodeKey{0, v.end}
 127         _, err := v.load(tree, line)
 128         if err != nil {
 129                 return false, err
 130         }
 131
 132         v.lines = append(v.lines, line)
 133         v.end++
 134
 135         return v.fit(tree)
 136 }
 137
 138 // fit merges the most due pairs while a batch runs, and tells if a merge
 139 // changed the view.
 140 func (v *View) fit(tree nodeReader) (bool, error) {
 141         size := v.Size()
 142         if size > v.high {
 143                 v.merging = true
 144         }
 145
 146         merged := false
 147         for v.merging && size > v.low {
 148                 best, err := v.mostDue(tree)
 149                 if err != nil || best < 0 {
 150                         return merged, err
 151                 }
 152
 153                 left, right := v.lines[best], v.lines[best+1]
 154                 parent := nodeKey{left.level + 1, left.index / 2}
 155                 _, err = v.load(tree, parent)
 156                 if err != nil {
 157                         return merged, err
 158                 }
 159
 160                 size += v.lineSize(parent) - v.lineSize(left) - v.lineSize(right)
 161                 delete(v.nodes, left)
 162                 delete(v.nodes, right)
 163                 v.lines[best] = parent
 164                 v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
 165                 merged = true
 166         }
 167
 168         v.merging = false
 169
 170         return merged, nil
 171 }
 172
 173 // Coarsen takes each merge of other, a view of the same messages, and then
 174 // merges in one batch until the size is at most low. Each line of the result is
 175 // the coarser of the two lines that start at its first message. Dyadic ranges
 176 // either nest or do not overlap, so the result covers the messages without a
 177 // gap.
 178 func (v *View) Coarsen(other *View, tree nodeReader) error {
 179         lines := make([]nodeKey, 0, len(v.lines))
 180         nodes := make(map[nodeKey]Node, len(v.nodes))
 181         mine, theirs := 0, 0
 182         for start := 0; start < v.end; {
 183                 line := v.lines[mine]
 184                 node, built := v.nodes[line]
 185                 if other.lines[theirs].level > line.level {
 186                         line = other.lines[theirs]
 187                         node, built = other.nodes[line]
 188                 }
 189
 190                 lines = append(lines, line)
 191                 if built {
 192                         nodes[line] = node
 193                 }
 194
 195                 start = nodeEnd(line.level, line.index)
 196                 for mine < len(v.lines) && v.lines[mine].index<<v.lines[mine].level < start {
 197                         mine++
 198                 }
 199
 200                 for theirs < len(other.lines) && other.lines[theirs].index<<other.lines[theirs].level < start {
 201                         theirs++
 202                 }
 203         }
 204
 205         v.lines = lines
 206         v.nodes = nodes
 207         v.merging = true
 208         _, err := v.fit(tree)
 209
 210         return err
 211 }
 212
 213 // mostDue returns the position of the left line of the most due sibling pair
 214 // whose parent is built, or -1 when there is no such pair.
 215 func (v *View) mostDue(tree nodeReader) (int, error) {
 216         best := -1
 217         bestDue := 0.0
 218         for n := 0; n+1 < len(v.lines); n++ {
 219                 left, right := v.lines[n], v.lines[n+1]
 220                 if left.index%2 != 0 || right.level != left.level || right.index != left.index+1 {
 221                         continue
 222                 }
 223
 224                 last := nodeEnd(right.level, right.index) - 1
 225                 due := math.Ldexp(float64(v.end-last), -left.level)
 226                 if best >= 0 && due <= bestDue {
 227                         continue
 228                 }
 229
 230                 built, err := tree.Built(left.level+1, left.index/2)
 231                 if err != nil {
 232                         return -1, err
 233                 }
 234
 235                 if built {
 236                         best = n
 237                         bestDue = due
 238                 }
 239         }
 240
 241         return best, nil
 242 }
 243
 244 // Refresh keeps node when it is the node of a pending line.
 245 func (v *View) Refresh(node Node) {
 246         key := nodeKey{node.Level, node.Index}
 247         for n := len(v.lines) - 1; n >= 0; n-- {
 248                 line := v.lines[n]
 249                 if line == key {
 250                         v.nodes[key] = node
 251                         return
 252                 }
 253
 254                 if line.index<<line.level <= key.index<<key.level {
 255                         return
 256                 }
 257         }
 258 }
 259
 260 // Size returns the sum of the line sizes.
 261 func (v *View) Size() int {
 262         size := 0
 263         for _, line := range v.lines {
 264                 size += v.lineSize(line)
 265         }
 266
 267         return size
 268 }
 269
 270 // lineSize returns the size of a view line.
 271 func (v *View) lineSize(line nodeKey) int {
 272         node, built := v.nodes[line]
 273         if !built {
 274                 return len(pending)
 275         }
 276
 277         return node.Size
 278 }
 279
 280 // Render returns the view as the model reads it: one line "id+n|text" for each
 281 // node inside <chat> tags, with the newlines of the text as spaces.
 282 func (v *View) Render() string {
 283         var text strings.Builder
 284         text.WriteString("<chat>\n")
 285         for _, line := range v.lines {
 286                 v.renderLine(&text, line)
 287         }
 288
 289         text.WriteString("</chat>")
 290
 291         return text.String()
 292 }
 293
 294 // renderLine writes one view line, "id+n|text", and a newline.
 295 func (v *View) renderLine(text *strings.Builder, line nodeKey) {
 296         body := pending
 297         node, built := v.nodes[line]
 298         if built {
 299                 body = strings.ReplaceAll(node.Text, "\n", " ")
 300         }
 301
 302         text.WriteString(strconv.Itoa(line.index << line.level))
 303         text.WriteByte('+')
 304         text.WriteString(strconv.Itoa(1 << line.level))
 305         text.WriteByte('|')
 306         text.WriteString(body)
 307         text.WriteByte('\n')
 308 }
 309
 310 // Context returns the lines of the view before message end as the model reads
 311 // them. It stops at the first line that is not built, so a compaction never
 312 // sees a pending mark or a part of a message.
 313 func (v *View) Context(end int) string {
 314         var text strings.Builder
 315         text.WriteString("<chat>\n")
 316         for _, line := range v.lines {
 317                 _, built := v.nodes[line]
 318                 if !built || nodeEnd(line.level, line.index) > end {
 319                         break
 320                 }
 321
 322                 v.renderLine(&text, line)
 323         }
 324
 325         text.WriteString("</chat>")
 326
 327         return text.String()
 328 }