// few bytes over it, because the view measures the real sizes.
const nodeBytes = 512
-// Node is one line of the summary tree. Node (l, i) covers the 2^l messages
-// from i*2^l on. A node of level 0 holds one message. A node of a higher level
-// merges its two children, (l-1, 2i) and (l-1, 2i+1). Size is the UTF-8 byte
-// length of Text.
-type Node struct {
- Level int `json:"l"`
- Index int `json:"i"`
- Text string `json:"text"`
- Size int `json:"size"`
+// treeRecordBytes is the size of a record of index/tree.idx: the position of
+// the node line, the node index, and the node level.
+const treeRecordBytes = 32
+
+// openTree opens the tree of the chat in root and indexes its new lines. A chat
+// of total messages cannot have a node that covers a later message.
+func openTree(ctx context.Context, root string, total int, clock func() time.Time) (*Tree, error) {
+ for _, dir := range []string{"tree", "index"} {
+ err := os.MkdirAll(filepath.Join(root, dir), 0o700)
+ if err != nil {
+ return nil, fmt.Errorf("create %s directory: %w", dir, err)
+ }
+ }
+
+ t := &Tree{
+ clock: clock,
+ journal: Journal{
+ dir: filepath.Join(root, "tree"),
+ },
+ dir: filepath.Join(root, "index"),
+ levels: make(map[int]*Records),
+ }
+
+ err := t.open(ctx, total)
+ if err != nil {
+ return nil, errors.Join(fmt.Errorf("index tree: %w", err), t.Close())
+ }
+
+ return t, nil
}
-// nodeKey names the node (l, i).
-type nodeKey struct {
- level int
- index int
+// leafSource returns the text that the leaf of message holds or summarizes.
+func leafSource(message Message) string {
+ return message.Kind + ": " + message.Text
}
-// treeRecordBytes is the size of a record of index/tree.idx: the position of
-// the node line, the node index, and the node level.
-const treeRecordBytes = 32
+// freeLeaf returns the leaf of message when its source fits in a node. Such a
+// leaf holds the source word for word and needs no model call.
+func freeLeaf(message Message) (Node, bool) {
+ text := leafSource(message)
+ if len(text) > nodeBytes {
+ return Node{}, false
+ }
+
+ return Node{
+ Level: 0,
+ Index: message.ID,
+ Text: text,
+ Size: len(text),
+ }, true
+}
+
+// freeMerge returns the parent of two sibling nodes when both texts, joined by
+// a newline, fit in a node. Such a parent needs no model call.
+func freeMerge(left, right Node) (Node, bool) {
+ if left.Size+1+right.Size > nodeBytes {
+ return Node{}, false
+ }
+
+ text := left.Text + "\n" + right.Text
+
+ return Node{
+ Level: left.Level + 1,
+ Index: left.Index / 2,
+ Text: text,
+ Size: len(text),
+ }, true
+}
+
+// nodeEnd returns the ID after the last message of node (l, i).
+func nodeEnd(level, index int) int {
+ return (index + 1) << level
+}
// Tree holds the built nodes of one chat. It writes one JSON line for each node
// to tree/YYYY-MM-DD.jsonl, named for the local day of the build. Each node is
// built again from the day files.
type Tree struct {
clock func() time.Time
- journal journal
+ journal Journal
dir string
- order *records
- levels map[int]*records
+ order *Records
+ levels map[int]*Records
failure error
}
-// openTree opens the tree of the chat in root and indexes its new lines. A chat
-// of total messages cannot have a node that covers a later message.
-func openTree(ctx context.Context, root string, total int, clock func() time.Time) (*Tree, error) {
- for _, dir := range []string{"tree", "index"} {
- err := os.MkdirAll(filepath.Join(root, dir), 0o700)
- if err != nil {
- return nil, fmt.Errorf("create %s directory: %w", dir, err)
- }
+// Close closes the files of the tree.
+func (t *Tree) Close() error {
+ err := t.journal.Close()
+ if t.order != nil {
+ err = errors.Join(err, t.order.Close())
+ t.order = nil
}
- t := &Tree{
- clock: clock,
- journal: journal{
- dir: filepath.Join(root, "tree"),
- },
- dir: filepath.Join(root, "index"),
- levels: make(map[int]*records),
+ for level, index := range t.levels {
+ err = errors.Join(err, index.Close())
+
+ delete(t.levels, level)
}
- err := t.open(ctx, total)
+ return err
+}
+
+// Add writes a new node to the tree.
+func (t *Tree) Add(node Node) error {
+ if t.failure != nil {
+ return fmt.Errorf("tree needs a reopen after a failed write: %w", t.failure)
+ }
+
+ err := t.check(node)
if err != nil {
- return nil, errors.Join(fmt.Errorf("index tree: %w", err), t.Close())
+ return err
}
- return t, nil
+ line, err := json.Marshal(node)
+ if err != nil {
+ return fmt.Errorf("encode node: %w", err)
+ }
+
+ place, err := t.journal.Write(t.clock().Format(time.DateOnly), append(line, '\n'))
+ if err == nil {
+ err = t.addIndex(NodeKey{node.Level, node.Index}, place)
+ }
+
+ if err != nil {
+ t.failure = err
+ return fmt.Errorf("write node (%d, %d): %w", node.Level, node.Index, err)
+ }
+
+ return nil
+}
+
+// Built tells if the node (l, i) is built.
+func (t *Tree) Built(level, index int) (bool, error) {
+ _, built, err := t.place(level, index)
+ return built, err
+}
+
+// Node reads the node (l, i) if it is built.
+func (t *Tree) Node(level, index int) (Node, bool, error) {
+ place, built, err := t.place(level, index)
+ if err != nil || !built {
+ return Node{}, false, err
+ }
+
+ line, err := t.journal.Read(place)
+ if err != nil {
+ return Node{}, false, fmt.Errorf("read node (%d, %d): %w", level, index, err)
+ }
+
+ var node Node
+
+ err = json.Unmarshal(line, &node)
+ if err != nil {
+ return Node{}, false, fmt.Errorf("decode node (%d, %d): %w", level, index, err)
+ }
+
+ if node.Level != level || node.Index != index {
+ return Node{}, false, fmt.Errorf("index of node (%d, %d) points to node (%d, %d)", level, index, node.Level, node.Index)
+ }
+
+ return node, true, nil
+}
+
+// Keys returns the keys of the built nodes, ordered by level and then by index.
+func (t *Tree) Keys() ([]NodeKey, error) {
+ keys := make([]NodeKey, 0, t.order.count)
+ for n := range t.order.count {
+ record, _, err := t.order.Read(n)
+ if err != nil {
+ return nil, err
+ }
+
+ key, _ := treeDecodeRecord(record)
+ keys = append(keys, key)
+ }
+
+ slices.SortFunc(keys, func(a, b NodeKey) int {
+ return cmp.Or(cmp.Compare(a.level, b.level), cmp.Compare(a.index, b.index))
+ })
+
+ return keys, nil
}
func (t *Tree) open(ctx context.Context, total int) error {
var err error
+
t.order, err = openRecords(filepath.Join(t.dir, "tree.idx"), treeRecordBytes)
if err != nil {
return err
}
- start := position{}
+ start := Position{}
if t.order.count == 0 {
err = t.removeLevels()
if err != nil {
// A crash can stop an add between the two index writes, so the
// last node gets its level record again.
- node, last := decodeTreeRecord(record)
+ node, last := treeDecodeRecord(record)
err = t.writeLevel(node, last)
if err != nil {
return err
}
- start = position{
+ start = Position{
day: last.day,
offset: last.offset + uint64(last.length),
}
}
- return t.journal.Scan(ctx, start, func(line []byte, place position) error {
+ return t.journal.Scan(ctx, start, func(line []byte, place Position) error {
var node Node
+
err := json.Unmarshal(line, &node)
if err != nil {
- return err
+ return fmt.Errorf("decode tree node: %w", err)
}
err = t.check(node)
return fmt.Errorf("node (%d, %d) covers messages after the log", node.Level, node.Index)
}
- return t.addIndex(nodeKey{node.Level, node.Index}, place)
+ return t.addIndex(NodeKey{node.Level, node.Index}, place)
})
}
-// removeLevels removes the level indexes, which are not valid without the order
-// index.
-func (t *Tree) removeLevels() error {
- paths, err := filepath.Glob(filepath.Join(t.dir, "tree-*.idx"))
- if err != nil {
- return fmt.Errorf("list level indexes: %w", err)
- }
-
- for _, path := range paths {
- err = os.Remove(path)
- if err != nil {
- return fmt.Errorf("remove level index: %w", err)
- }
- }
-
- return nil
-}
-
-// writeLevel writes the position of node to its level index.
-func (t *Tree) writeLevel(node nodeKey, place position) error {
- level, err := t.level(node.level)
- if err != nil {
- return err
- }
-
- record := make([]byte, positionBytes)
- encodePosition(record, place)
-
- return level.Write(node.index, record)
-}
-
-// level returns the index of level, and opens it at first use.
-func (t *Tree) level(level int) (*records, error) {
- index, open := t.levels[level]
- if open {
- return index, nil
- }
-
- index, err := openRecords(filepath.Join(t.dir, fmt.Sprintf("tree-%d.idx", level)), positionBytes)
- if err != nil {
- return nil, err
- }
-
- t.levels[level] = index
-
- return index, nil
-}
-
// check makes sure that node is valid and can join the tree now.
func (t *Tree) check(node Node) error {
if node.Level < 0 || node.Level >= bits.UintSize-2 || node.Index < 0 {
}
// addIndex adds the node line at place to both indexes.
-func (t *Tree) addIndex(node nodeKey, place position) error {
+func (t *Tree) addIndex(node NodeKey, place Position) error {
record := make([]byte, treeRecordBytes)
encodePosition(record, place)
binary.LittleEndian.PutUint64(record[positionBytes:], uint64(node.index))
return t.writeLevel(node, place)
}
-// Close closes the files of the tree.
-func (t *Tree) Close() error {
- err := t.journal.Close()
- if t.order != nil {
- err = errors.Join(err, t.order.Close())
- t.order = nil
- }
-
- for level, index := range t.levels {
- err = errors.Join(err, index.Close())
- delete(t.levels, level)
- }
-
- return err
-}
-
-// Add writes a new node to the tree.
-func (t *Tree) Add(node Node) error {
- if t.failure != nil {
- return fmt.Errorf("tree needs a reopen after a failed write: %w", t.failure)
- }
-
- err := t.check(node)
- if err != nil {
- return err
- }
-
- line, err := json.Marshal(node)
- if err != nil {
- return fmt.Errorf("encode node: %w", err)
- }
-
- place, err := t.journal.Write(t.clock().Format(time.DateOnly), append(line, '\n'))
- if err == nil {
- err = t.addIndex(nodeKey{node.Level, node.Index}, place)
- }
-
- if err != nil {
- t.failure = err
- return fmt.Errorf("write node (%d, %d): %w", node.Level, node.Index, err)
- }
-
- return nil
-}
-
-// Built tells if the node (l, i) is built.
-func (t *Tree) Built(level, index int) (bool, error) {
- _, built, err := t.place(level, index)
- return built, err
-}
-
// place returns the position of the node (l, i) if it is built.
-func (t *Tree) place(level, index int) (position, bool, error) {
+func (t *Tree) place(level, index int) (Position, bool, error) {
if level < 0 || level >= bits.UintSize-2 || index < 0 {
- return position{}, false, nil
+ return Position{}, false, nil
}
records, err := t.level(level)
if err != nil {
- return position{}, false, err
+ return Position{}, false, err
}
record, found, err := records.Read(index)
if err != nil || !found {
- return position{}, false, err
+ return Position{}, false, err
}
place := decodePosition(record)
return place, place.length > 0, nil
}
-// Node reads the node (l, i) if it is built.
-func (t *Tree) Node(level, index int) (Node, bool, error) {
- place, built, err := t.place(level, index)
- if err != nil || !built {
- return Node{}, false, err
- }
-
- line, err := t.journal.Read(place)
+// removeLevels removes the level indexes, which are not valid without the order
+// index.
+func (t *Tree) removeLevels() error {
+ paths, err := filepath.Glob(filepath.Join(t.dir, "tree-*.idx"))
if err != nil {
- return Node{}, false, fmt.Errorf("read node (%d, %d): %w", level, index, err)
+ return fmt.Errorf("list level indexes: %w", err)
}
- var node Node
- err = json.Unmarshal(line, &node)
- if err != nil {
- return Node{}, false, fmt.Errorf("decode node (%d, %d): %w", level, index, err)
+ for _, path := range paths {
+ err = os.Remove(path)
+ if err != nil {
+ return fmt.Errorf("remove level index: %w", err)
+ }
}
- if node.Level != level || node.Index != index {
- return Node{}, false, fmt.Errorf("index of node (%d, %d) points to node (%d, %d)", level, index, node.Level, node.Index)
+ return nil
+}
+
+// writeLevel writes the position of node to its level index.
+func (t *Tree) writeLevel(node NodeKey, place Position) error {
+ level, err := t.level(node.level)
+ if err != nil {
+ return err
}
- return node, true, nil
-}
+ record := make([]byte, positionBytes)
+ encodePosition(record, place)
-// Count returns the number of built nodes.
-func (t *Tree) Count() int {
- return t.order.count
+ return level.Write(node.index, record)
}
-// Keys returns the keys of the built nodes, ordered by level and then by index.
-func (t *Tree) Keys() ([]nodeKey, error) {
- keys := make([]nodeKey, 0, t.order.count)
- for n := range t.order.count {
- record, _, err := t.order.Read(n)
- if err != nil {
- return nil, err
- }
+// level returns the index of level, and opens it at first use.
+func (t *Tree) level(level int) (*Records, error) {
+ index, open := t.levels[level]
+ if open {
+ return index, nil
+ }
- key, _ := decodeTreeRecord(record)
- keys = append(keys, key)
+ index, err := openRecords(filepath.Join(t.dir, fmt.Sprintf("tree-%d.idx", level)), positionBytes)
+ if err != nil {
+ return nil, err
}
- slices.SortFunc(keys, func(a, b nodeKey) int {
- return cmp.Or(cmp.Compare(a.level, b.level), cmp.Compare(a.index, b.index))
- })
+ t.levels[level] = index
- return keys, nil
+ return index, nil
}
-// leafSource returns the text that the leaf of message holds or summarizes.
-func leafSource(message Message) string {
- return message.Kind + ": " + message.Text
+// Count returns the number of built nodes.
+func (t *Tree) Count() int {
+ return t.order.count
}
-// freeLeaf returns the leaf of message when its source fits in a node. Such a
-// leaf holds the source word for word and needs no model call.
-func freeLeaf(message Message) (Node, bool) {
- text := leafSource(message)
- if len(text) > nodeBytes {
- return Node{}, false
- }
-
- return Node{
- Level: 0,
- Index: message.ID,
- Text: text,
- Size: len(text),
- }, true
+// Node is one line of the summary tree. Node (l, i) covers the 2^l messages
+// from i*2^l on. A node of level 0 holds one message. A node of a higher level
+// merges its two children, (l-1, 2i) and (l-1, 2i+1). Size is the UTF-8 byte
+// length of Text.
+type Node struct {
+ Level int `json:"l"`
+ Index int `json:"i"`
+ Text string `json:"text"`
+ Size int `json:"size"`
}
-// freeMerge returns the parent of two sibling nodes when both texts, joined by
-// a newline, fit in a node. Such a parent needs no model call.
-func freeMerge(left, right Node) (Node, bool) {
- if left.Size+1+right.Size > nodeBytes {
- return Node{}, false
- }
-
- text := left.Text + "\n" + right.Text
-
- return Node{
- Level: left.Level + 1,
- Index: left.Index / 2,
- Text: text,
- Size: len(text),
- }, true
+// NodeKey names the node (l, i).
+type NodeKey struct {
+ level int
+ index int
}
-// decodeTreeRecord reads the key and the position of a record of
+// treeDecodeRecord reads the key and the position of a record of
// index/tree.idx.
-func decodeTreeRecord(record []byte) (nodeKey, position) {
- key := nodeKey{
+func treeDecodeRecord(record []byte) (NodeKey, Position) {
+ key := NodeKey{
level: int(binary.LittleEndian.Uint32(record[positionBytes+8:])),
index: int(binary.LittleEndian.Uint64(record[positionBytes:])),
}
return key, decodePosition(record)
}
-
-// nodeEnd returns the ID after the last message of node (l, i).
-func nodeEnd(level, index int) int {
- return (index + 1) << level
-}
projects / onechat / blobdiff