munin/internal/store/related.go

package store

import (
	"context"
	"fmt"
	"sort"
	"strings"
	"time"
)

// Richtung eines Verweises aus Sicht des Eintrags, über den ein verwandter
// Eintrag gefunden wurde (siehe RelatedEntry.Relation).
const (
	RelationLinksTo  = "links_to"  // der Vorgänger verweist auf diesen Eintrag
	RelationLinkedBy = "linked_by" // dieser Eintrag verweist auf den Vorgänger
)

// RelatedEntry ist ein Nachbar eines Eintrags im Verweisgraphen.
type RelatedEntry struct {
	Slug      string
	Title     string
	UpdatedAt time.Time

	// Distance zählt die Verweise bis zum Ausgangseintrag: 1 = direkt
	// verknüpft, 2 = über einen Zwischeneintrag.
	Distance int

	// Via ist der Eintrag, über den dieser gefunden wurde. Bei Distance 1 ist
	// das der Ausgangseintrag selbst, bei Distance 2 der Zwischeneintrag.
	Via string

	// Relation sagt, in welche Richtung der Verweis zwischen Via und diesem
	// Eintrag zeigt: RelationLinksTo oder RelationLinkedBy.
	Relation string
}

// RelatedEntries liefert die Nachbarn eines Eintrags im Verweisgraphen, bis zu
// maxDistance Schritte weit und höchstens limit Stück (siehe AUSBAUSTUFEN.md
// 3.7).
//
// # Wozu, wenn "get" schon links_to und linked_by liefert?
//
// "get" kennt nur die direkten Nachbarn, und das nur als nackte Bezeichner.
// Hier kommen Titel und Änderungsdatum dazu, und auf Wunsch auch die zweite
// Reihe: Was hängt an den Einträgen, die mit meinem Thema verknüpft sind? Für
// einen Agenten ist das ein zweiter Weg zum Kontext, neben der Suche. Er
// findet Einträge, die kein Suchwort gemeinsam haben, aber von einem Menschen
// bewusst verknüpft wurden.
//
// # Vorgehen
//
// Breitensuche, eine Ebene nach der anderen: erst alle direkten Nachbarn, dann
// deren Nachbarn. Die Richtung der Verweise spielt für die Suche keine Rolle.
// Wer auf mich verweist, ist genauso verwandt wie das, worauf ich verweise.
// Näheres steht vor Fernerem, innerhalb einer Ebene nach Titel sortiert.
//
// Verweise auf Bezeichner ohne Eintrag und Einträge im Papierkorb tauchen nicht
// auf. Für einen Agenten, der Kontext sucht, gibt es dort nichts zu lesen.
//
// Gibt es den Ausgangseintrag nicht, ist das ErrNotFound.
func (s *Store) RelatedEntries(ctx context.Context, projectID, slug string, maxDistance, limit int) ([]RelatedEntry, error) {
	// Den Ausgangseintrag selbst prüfen. Sonst bekäme ein Tippfehler im
	// Bezeichner eine leere Liste zurück, und der Agent hielte das Thema für
	// unverknüpft statt für nicht vorhanden.
	var existing int
	if err := s.read.QueryRowContext(ctx,
		`SELECT COUNT(*) FROM entries WHERE project_id = ? AND slug = ? AND `+notInTrash,
		projectID, slug,
	).Scan(&existing); err != nil {
		return nil, fmt.Errorf("Eintrag konnte nicht gelesen werden: %w", err)
	}
	if existing == 0 {
		return nil, ErrNotFound
	}

	// visited verhindert, dass ein Eintrag zweimal auftaucht, etwa wenn A auf
	// B verweist und B zurück auf A. Der Ausgangseintrag zählt von Anfang an
	// als besucht, er soll nicht als sein eigener Nachbar erscheinen.
	visited := map[string]bool{slug: true}
	level := []string{slug}

	var result []RelatedEntry

	for distance := 1; distance <= maxDistance && len(level) > 0 && len(result) < limit; distance++ {
		edges, err := s.neighbors(ctx, projectID, level)
		if err != nil {
			return nil, err
		}

		// Je neu entdecktem Bezeichner nur die erste Kante merken. Welcher
		// Vorgänger „gewinnt“, ist egal, aber es muss derselbe sein, egal in
		// welcher Reihenfolge die Datenbank die Zeilen liefert. Deshalb sind
		// die Kanten vorher sortiert (siehe neighbors).
		newer := make(map[string]RelatedEntry)
		var newSlugs []string
		for _, k := range edges {
			if visited[k.to] {
				continue
			}
			if _, already := newer[k.to]; already {
				continue
			}
			newer[k.to] = RelatedEntry{Slug: k.to, Distance: distance, Via: k.from, Relation: k.relation}
			newSlugs = append(newSlugs, k.to)
		}

		// Titel und Änderungsdatum nachladen. Dabei fallen Verweisziele ohne
		// Eintrag und Einträge im Papierkorb heraus: Sie stehen nicht in
		// der Antwort.
		details, err := s.entryHeads(ctx, projectID, newSlugs)
		if err != nil {
			return nil, err
		}

		var thisLevel []RelatedEntry
		level = level[:0]
		for _, neighbor := range newSlugs {
			visited[neighbor] = true
			head, ok := details[neighbor]
			if !ok {
				continue
			}
			r := newer[neighbor]
			r.Title = head.Title
			r.UpdatedAt = head.UpdatedAt
			thisLevel = append(thisLevel, r)
			level = append(level, neighbor)
		}

		sort.Slice(thisLevel, func(i, j int) bool { return thisLevel[i].Title < thisLevel[j].Title })
		result = append(result, thisLevel...)
	}

	if len(result) > limit {
		result = result[:limit]
	}
	return result, nil
}

// edge ist ein Verweis, gesehen von einem Eintrag der aktuellen Ebene aus.
type edge struct {
	from, to string
	relation string
}

// neighbors liefert alle Verweise, die einen der Bezeichner in slugs berühren,
// in beide Richtungen.
//
// Zwei Abfragen statt einer mit OR: So nutzt jede ihren eigenen Index. Die
// ausgehenden laufen über den Primärschlüssel (from_entry_id, to_slug), die
// eingehenden über idx_entry_links_project (project_id, to_slug).
func (s *Store) neighbors(ctx context.Context, projectID string, slugs []string) ([]edge, error) {
	placeholders, args := inList(projectID, slugs)

	var edges []edge

	// Ausgehend: Einträge der Ebene verweisen auf etwas.
	rows, err := s.read.QueryContext(ctx,
		`SELECT e.slug, l.to_slug
		 FROM entries e
		 JOIN entry_links l ON l.from_entry_id = e.id
		 WHERE e.project_id = ? AND e.slug IN (`+placeholders+`) AND e.deleted_at IS NULL`,
		args...,
	)
	if err != nil {
		return nil, fmt.Errorf("Verweise konnten nicht gelesen werden: %w", err)
	}
	for rows.Next() {
		var k edge
		if err := rows.Scan(&k.from, &k.to); err != nil {
			rows.Close()
			return nil, err
		}
		k.relation = RelationLinksTo
		edges = append(edges, k)
	}
	if err := rows.Err(); err != nil {
		rows.Close()
		return nil, err
	}
	rows.Close()

	// Eingehend: Etwas verweist auf Einträge der Ebene. Der verweisende
	// Eintrag ist hier der Nachbar, deshalb stehen die Spalten andersherum.
	rows, err = s.read.QueryContext(ctx,
		`SELECT l.to_slug, e.slug
		 FROM entry_links l
		 JOIN entries e ON e.id = l.from_entry_id
		 WHERE l.project_id = ? AND l.to_slug IN (`+placeholders+`) AND e.deleted_at IS NULL`,
		args...,
	)
	if err != nil {
		return nil, fmt.Errorf("Rückverweise konnten nicht gelesen werden: %w", err)
	}
	defer rows.Close()
	for rows.Next() {
		var k edge
		if err := rows.Scan(&k.from, &k.to); err != nil {
			return nil, err
		}
		k.relation = RelationLinkedBy
		edges = append(edges, k)
	}
	if err := rows.Err(); err != nil {
		return nil, err
	}

	// Feste Reihenfolge, damit dasselbe Projekt immer dieselbe Antwort gibt
	// (siehe RelatedEntries).
	sort.Slice(edges, func(i, j int) bool {
		if edges[i].to != edges[j].to {
			return edges[i].to < edges[j].to
		}
		if edges[i].from != edges[j].from {
			return edges[i].from < edges[j].from
		}
		return edges[i].relation < edges[j].relation
	})
	return edges, nil
}

// entryHead ist das Wenige, was RelatedEntries über einen Nachbarn braucht.
type entryHead struct {
	Title     string
	UpdatedAt time.Time
}

// entryHeads lädt Titel und Änderungsdatum zu einer Liste von Bezeichnern.
// Was nicht (mehr) existiert oder im Papierkorb liegt, fehlt in der Antwort.
func (s *Store) entryHeads(ctx context.Context, projectID string, slugs []string) (map[string]entryHead, error) {
	heads := make(map[string]entryHead, len(slugs))
	if len(slugs) == 0 {
		return heads, nil
	}

	placeholders, args := inList(projectID, slugs)
	rows, err := s.read.QueryContext(ctx,
		`SELECT slug, title, updated_at FROM entries
		 WHERE project_id = ? AND slug IN (`+placeholders+`) AND `+notInTrash,
		args...,
	)
	if err != nil {
		return nil, fmt.Errorf("Einträge konnten nicht gelesen werden: %w", err)
	}
	defer rows.Close()

	for rows.Next() {
		var slug, title, changed string
		if err := rows.Scan(&slug, &title, &changed); err != nil {
			return nil, err
		}
		heads[slug] = entryHead{Title: title, UpdatedAt: parseTime(changed)}
	}
	return heads, rows.Err()
}

// inList baut die Platzhalter für "IN (?, ?, …)" und die passenden
// Argumente, mit der Projekt-ID vorneweg.
//
// Die Werte werden nie in den SQL-Text geschrieben, sondern immer als
// Parameter übergeben. Nur so ist ausgeschlossen, dass ein Bezeichner die
// Abfrage verändert (SQL-Injection).
func inList(projectID string, values []string) (string, []any) {
	args := make([]any, 0, len(values)+1)
	args = append(args, projectID)
	for _, w := range values {
		args = append(args, w)
	}
	return strings.TrimSuffix(strings.Repeat("?, ", len(values)), ", "), args
}