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