// errNoView tells that a chat has messages but no saved view.
var errNoView = errors.New("the chat has messages but no saved view")
-// Memory is the memory of one chat: the message log, the summary tree, and the
-// view. It saves the view to view.json after each change and loads it at start.
-// It never builds the view again from the log, because a new view differs from
-// the live one and so loses the prompt cache.
+// Memory is the memory of one chat: the message log, the summary tree, the chat
+// view, and the compaction view. The compaction view is the chat view merged
+// further, at the limits of 16 to 32 KB. It takes the same new lines, and it
+// merges again in one batch when it is too large or when the chat view merges.
+// So the compactions share its prefix in the prompt cache. It saves the views
+// to view.json after each change and loads them at start. It never builds the
+// views again from the log, because a new view differs from the live one and so
+// loses the prompt cache.
type Memory struct {
mutex sync.Mutex
root string
log *Log
tree *Tree
chat *View
+ cview *View
}
// viewFile is the content of view.json.
type viewFile struct {
- Chat viewState `json:"chat"`
+ Chat viewState `json:"chat"`
+ Compaction viewState `json:"compaction"`
}
// openMemory opens the chat in root. The clock gives the dates of new messages
data, err := os.ReadFile(m.viewPath())
if errors.Is(err, os.ErrNotExist) && m.log.Len() == 0 {
m.chat = newView(chatHigh, chatLow)
+ m.cview = newView(compactionHigh, compactionLow)
+
return nil
}
m.chat, err = restoreView(file.Chat, chatHigh, chatLow, m.tree)
if err != nil {
- return err
+ return fmt.Errorf("chat view: %w", err)
+ }
+
+ m.cview, err = restoreView(file.Compaction, compactionHigh, compactionLow, m.tree)
+ if err != nil {
+ return fmt.Errorf("compaction view: %w", err)
+ }
+
+ if m.cview.end != m.chat.end {
+ return fmt.Errorf("compaction view covers %d messages, but the chat view %d", m.cview.end, m.chat.end)
}
if m.chat.end > m.log.Len() {
}
}
- m.chat.Append(m.tree)
+ merged := m.chat.Append(m.tree)
+ m.cview.Append(m.tree)
+ if merged {
+ m.cview.Coarsen(m.chat, m.tree)
+ }
return nil
}
// save writes the views to view.json.
func (m *Memory) save() error {
data, err := json.Marshal(viewFile{
- Chat: m.chat.State(),
+ Chat: m.chat.State(),
+ Compaction: m.cview.State(),
})
if err != nil {
return fmt.Errorf("encode view: %w", err)
return m.chat.Render(m.tree)
}
+// Context returns the compaction view for the build of node (l, i). It ends
+// before the message of a leaf, or after the last message of a merge, and it
+// stops at the first line that is not built.
+func (m *Memory) Context(level, index int) string {
+ m.mutex.Lock()
+ defer m.mutex.Unlock()
+
+ return m.context(level, index)
+}
+
+func (m *Memory) context(level, index int) string {
+ end := index
+ if level > 0 {
+ end = nodeEnd(level, index)
+ }
+
+ return m.cview.Context(m.tree, end)
+}
+
// writeFileAtomic replaces the file at path with data. A reader or a crash sees
// the old file or the new file, never a part of one.
func writeFileAtomic(path string, data []byte) error {
memory.chat.high = 200
memory.chat.low = 100
+ memory.cview.high = 80
+ memory.cview.low = 40
for n := range 100 {
_, err = memory.Append("user", fmt.Sprint(n))
require.NoError(t, err)
}
view := memory.View()
+ context := memory.Context(0, 100)
saved, err := os.ReadFile(filepath.Join(root, "view.json"))
require.NoError(t, err)
require.Less(t, len(memory.chat.lines), 100)
}()
require.Equal(t, view, memory.View())
+ require.Equal(t, context, memory.Context(0, 100))
loaded, err := os.ReadFile(filepath.Join(root, "view.json"))
require.NoError(t, err)
require.Equal(t, saved, loaded)
}
+func TestMemoryKeepsTheCompactionViewCoarser(t *testing.T) {
+ memory, err := openMemory(t.Context(), t.TempDir(), newTestClock().Now)
+ require.NoError(t, err)
+
+ defer func() {
+ require.NoError(t, memory.Close())
+ }()
+
+ memory.chat.high = 200
+ memory.chat.low = 100
+ memory.cview.high = 80
+ memory.cview.low = 40
+ for n := range 64 {
+ _, err = memory.Append("user", fmt.Sprint(n%10))
+ require.NoError(t, err)
+
+ coarse := 0
+ for _, line := range memory.chat.lines {
+ outer := memory.cview.lines[coarse]
+ for nodeEnd(outer.level, outer.index) <= line.index<<line.level {
+ coarse++
+ outer = memory.cview.lines[coarse]
+ }
+
+ require.GreaterOrEqual(t, outer.level, line.level, "message %d", n)
+ }
+ }
+}
+
func TestMemoryBuildsFreeParents(t *testing.T) {
memory, err := openMemory(t.Context(), t.TempDir(), newTestClock().Now)
require.NoError(t, err)
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)"
)
}
// Append adds the leaf of the next message as a line and merges when the view
-// is too large.
-func (v *View) Append(tree nodeReader) {
+// is too large. It tells if a merge changed the view.
+func (v *View) Append(tree nodeReader) bool {
v.lines = append(v.lines, nodeKey{0, v.end})
v.end++
- v.fit(tree)
+
+ return v.fit(tree)
}
-func (v *View) fit(tree nodeReader) {
+// 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 {
size := v.Size(tree)
if size > v.high {
v.merging = true
}
+ merged := false
for v.merging && size > v.low {
best := v.mostDue(tree)
if best < 0 {
- return
+ return merged
}
left, right := v.lines[best], v.lines[best+1]
size += lineSize(tree, parent) - lineSize(tree, left) - lineSize(tree, right)
v.lines[best] = parent
v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
+ merged = true
}
v.merging = false
+
+ return merged
+}
+
+// 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) {
+ lines := make([]nodeKey, 0, len(v.lines))
+ mine, theirs := 0, 0
+ for start := 0; start < v.end; {
+ line := v.lines[mine]
+ if other.lines[theirs].level > line.level {
+ line = other.lines[theirs]
+ }
+
+ lines = append(lines, line)
+ start = nodeEnd(line.level, line.index)
+ for mine < len(v.lines) && v.lines[mine].index<<v.lines[mine].level < start {
+ mine++
+ }
+
+ for theirs < len(other.lines) && other.lines[theirs].index<<other.lines[theirs].level < start {
+ theirs++
+ }
+ }
+
+ v.lines = lines
+ v.merging = true
+ v.fit(tree)
}
// mostDue returns the position of the left line of the most due sibling pair
return text.String()
}
+// 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(tree nodeReader, end int) string {
+ var text strings.Builder
+ text.WriteString("<chat>\n")
+ for _, line := range v.lines {
+ _, built := tree.Node(line.level, line.index)
+ if !built || nodeEnd(line.level, line.index) > end {
+ break
+ }
+
+ renderLine(&text, tree, line)
+ }
+
+ text.WriteString("</chat>")
+
+ return text.String()
+}
+
// lineSize returns the size of a view line.
func lineSize(tree nodeReader, line nodeKey) int {
node, built := tree.Node(line.level, line.index)
require.Equal(t, 7+len(pending), view.Size(tree))
}
+func TestViewCoarsenTakesTheCoarserLines(t *testing.T) {
+ view, err := restoreView(viewState{
+ Lines: [][2]int{{1, 0}, {0, 2}, {0, 3}, {0, 4}, {0, 5}},
+ }, 100, 100, builtTree{})
+ require.NoError(t, err)
+
+ other, err := restoreView(viewState{
+ Lines: [][2]int{{0, 0}, {0, 1}, {1, 1}, {0, 4}, {0, 5}},
+ }, 100, 100, builtTree{})
+ require.NoError(t, err)
+
+ view.Coarsen(other, builtTree{})
+ require.Equal(t, []nodeKey{{1, 0}, {1, 1}, {0, 4}, {0, 5}}, view.lines)
+
+ view.low = 2
+ view.Coarsen(other, builtTree{})
+ require.Equal(t, []nodeKey{{2, 0}, {1, 2}}, view.lines)
+ require.False(t, view.merging)
+}
+
+func TestViewContextStopsAtTheFirstPendingLine(t *testing.T) {
+ tree := partTree{
+ sizes: map[nodeKey]int{
+ {0, 0}: 1,
+ {0, 1}: 1,
+ {1, 0}: 1,
+ {0, 3}: 1,
+ },
+ }
+
+ view, err := restoreView(viewState{
+ Lines: [][2]int{{1, 0}, {0, 2}, {0, 3}},
+ }, 100, 100, tree)
+ require.NoError(t, err)
+ require.Equal(t, "<chat>\n</chat>", view.Context(tree, 0))
+ require.Equal(t, "<chat>\n0+2|a\n</chat>", view.Context(tree, 2))
+ require.Equal(t, "<chat>\n0+2|a\n</chat>", view.Context(tree, 3))
+}
+
func TestRestoreViewRejectsAGap(t *testing.T) {
_, err := restoreView(viewState{
Lines: [][2]int{{0, 0}, {0, 2}},
projects / onechat / commitdiff