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