Skip to content

RAGFlow is an agent-native database: a Retrieval-Augmented Generation (RAG) engine that grew into context infrastructure.

68.5 KB
Raw Blame
//
//  Copyright 2026 The InfiniFlow Authors. All Rights Reserved.
//
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
//

package nlp

import (
	"context"
	"encoding/json"
	"fmt"
	"sort"
	"strings"

	"ragflow/internal/common"
	"ragflow/internal/engine"
	"ragflow/internal/engine/types"
	"ragflow/internal/service/nav"
	"ragflow/internal/tokenizer"

	"go.uber.org/zap"
)

// Dataset-nav constants. These mirror Python's dataset_nav.py: nav rows live in
// the document index with type_kwd nav_doc/nav_cluster and available_int=0
// (invisible to the default retriever, which filters available_int=1), and the
// tree is threaded through parent_kwd ("root" for depth-0 clusters).
const (
	navRootParent = "root"

	navMergeThreshold = 0.80 // sim >= this -> merge doc into cluster
	navRecurse        = 0.65 // descend while sim >= this
	navMinSim         = 0.50 // sim >= this -> new sibling cluster
	navMaxDepth       = 6    // max descent levels during best-cluster search

	// Split thresholds (mirror Python dataset_nav._MAX_FANOUT / _MAX_DOCS_PER_CLUSTER).
	// Shared by maybeSplitCluster and the append-path guard so an append only pays
	// the children-search cost when the cluster is plausibly overfull.
	navMaxFanout         = 64 // max direct children before rebalance
	navMaxDocsPerCluster = 50 // max docs per leaf cluster before split

	// navTreeReadLimit bounds the single read a search uses to resolve the
	// ancestor path of its hits. A nav tree is small by construction (fanout,
	// docs-per-cluster and depth are all capped), so this is a guard against a
	// pathological dataset rather than a paging budget.
	navTreeReadLimit = 10000
)

// navNodeSelectFields are the columns every nav tree read needs: the label
// (title_kwd, plus docnm_kwd for rows Infinity folded the label into), the
// Python-era name column, the parent edge, the payload (description), and the
// leaf's document id.
var navNodeSelectFields = []string{
	"name", "title_kwd", "docnm_kwd", "parent_kwd", "depth_int",
	"content_with_weight", "doc_count_int", "type_kwd", "doc_id",
}

// NavEmbedder embeds text. tenantID lets a production implementation resolve
// the tenant's embedding model. Kept as an interface so tests inject a stub.
type NavEmbedder interface {
	Encode(ctx context.Context, tenantID string, texts []string) ([][]float32, error)
}

// NavQueryEmbedder is the optional query-side counterpart of NavEmbedder
// (Python LLMBundle.encode_queries). It is implemented by embedders whose model
// encodes queries and documents asymmetrically (Cohere / Voyage / Jina /
// NVIDIA); callers embedding a SEARCH QUERY must prefer it and fall back to
// Encode when it is absent.
type NavQueryEmbedder interface {
	EncodeQueries(ctx context.Context, tenantID string, texts []string) ([][]float32, error)
}

// encodeNavQuery embeds a search query, using the asymmetric query encoding
// when the embedder provides one, mirroring Python's encode_queries split.
func encodeNavQuery(ctx context.Context, emb NavEmbedder, tenantID string, texts []string) ([][]float32, error) {
	if q, ok := emb.(NavQueryEmbedder); ok {
		return q.EncodeQueries(ctx, tenantID, texts)
	}
	return emb.Encode(ctx, tenantID, texts)
}

// NavService is the concrete, ES-backed implementation of nav.NavService.
type NavService struct {
	embed  NavEmbedder
	engine engine.DocEngine // optional; falls back to engine.Get() when nil
	llm    nav.NavMergeLLM  // optional; nil disables LLM merge/summary
}

// EncodeQueryVector embeds one SEARCH QUERY for the tenant and returns it in the
// engine's float64 form.
//
// It is the query-side seam the agentic claim recall uses to run a KNN leg over
// claim rows (which store their own q_<dim>_vec). The vector is produced by the
// tenant's DEFAULT embedding model, so on a dataset whose embedding model
// differs in dimension the KNN leg addresses a column the rows do not carry and
// recall falls back to its lexical leg — the documented degradation, and the
// reason an error here returns nil instead of failing the caller.
func (s *NavService) EncodeQueryVector(ctx context.Context, tenantID, text string) []float64 {
	if s == nil || s.embed == nil || tenantID == "" || strings.TrimSpace(text) == "" {
		return nil
	}
	vectors, err := encodeNavQuery(ctx, s.embed, tenantID, []string{text})
	if err != nil || len(vectors) == 0 {
		return nil
	}
	return f32ToF64Slice(vectors[0])
}

// NewNavService builds the ES-backed NavService. embed may be nil when the
// caller guarantees every UpsertDocInput carries a precomputed Embedd.
func NewNavService(embed NavEmbedder) *NavService {
	return &NavService{embed: embed}
}

// SetNavMergeLLM installs the optional LLM used for cluster naming and
// description merging (mirroring Python dataset_nav._llm_create_summary /
// _llm_merge). When nil (the default), clusters keep the deterministic
// "<summary first line> <hash>" name and their existing description.
func (s *NavService) SetNavMergeLLM(llm nav.NavMergeLLM) {
	s.llm = llm
}

func (s *NavService) docEngine() (engine.DocEngine, error) {
	if s.engine != nil {
		return s.engine, nil
	}
	de := engine.Get()
	if de == nil {
		return nil, fmt.Errorf("document engine is not initialized")
	}
	return de, nil
}

// navIndexName returns the tenant document index name (ragflow_<tenantID>).
func (s *NavService) navIndexName(tenantID string) string {
	return fmt.Sprintf("ragflow_%s", tenantID)
}

// navFilter scopes navigation reads and writes to navigation row roles.
func navFilter(extra map[string]interface{}) map[string]interface{} {
	f := map[string]interface{}{"type_kwd": []string{nav.TypeNavDoc, nav.TypeNavCluster}}
	for k, v := range extra {
		f[k] = v
	}
	return f
}

// navSearch runs a filtered read over the tenant index for the dataset.
func (s *NavService) navSearch(ctx context.Context, tenantID, kbID string, filter map[string]interface{}, selectFields []string, offset, limit int, matchExprs []interface{}) ([]map[string]interface{}, int64, error) {
	de, err := s.docEngine()
	if err != nil {
		return nil, 0, err
	}
	merged := make(map[string]interface{}, len(filter)+1)
	for k, v := range filter {
		merged[k] = v
	}
	merged["kb_id"] = []string{kbID}
	req := &types.SearchRequest{
		IndexNames:   []string{s.navIndexName(tenantID)},
		KbIDs:        []string{kbID},
		Offset:       offset,
		Limit:        limit,
		SelectFields: selectFields,
		Filter:       merged,
		MatchExprs:   matchExprs,
		// Nav rows carry available_int=0, and Infinity adds available_int=1 to
		// every MATCH query unless the caller opts out (shouldDefaultAvailableFilter):
		// nav's own vector/keyword reads would otherwise see none of its rows. ES
		// never filters available_int; the compile_kwd filter scopes the read.
		IncludeUnavailable: true,
	}
	res, err := de.Search(ctx, req)
	if err != nil {
		return nil, 0, err
	}
	if res == nil {
		return nil, 0, nil
	}
	return res.Chunks, res.Total, nil
}

// ListClusters returns the depth-0 clusters (parent_kwd=root). When keywords is
// non-empty it searches the dataset's documents and returns the pruned forest
// around the hits (see searchNavForest) instead: one tree per root cluster,
// holding only the cluster path down to each matched nav_doc leaf.
//
// The total is a cluster count in both modes: the depth-0 clusters when browsing,
// the clusters holding a match when searching.
func (s *NavService) ListClusters(ctx context.Context, tenantID, kbID, keywords string, page, pageSize int) ([]nav.NavNode, int64, error) {
	if pageSize <= 0 {
		pageSize = 100
	}
	if strings.TrimSpace(keywords) != "" {
		return s.searchNavForest(ctx, tenantID, kbID, keywords, pageSize)
	}
	offset := page * pageSize
	filter := navFilter(map[string]interface{}{
		"type_kwd":   []string{"nav_cluster"},
		"parent_kwd": []string{navRootParent},
	})
	chunks, total, err := s.navSearch(ctx, tenantID, kbID, filter,
		navNodeSelectFields, offset, pageSize, navKeywordExpressions(keywords))
	if err != nil {
		return nil, 0, err
	}
	nodes := make([]nav.NavNode, 0, len(chunks))
	for _, c := range chunks {
		nodes = append(nodes, s.nodeFromRow(c, "cluster"))
	}
	return nodes, total, nil
}

// ListChildren returns the direct children of a cluster (parent_kwd=name),
// optionally filtered by keywords.
func (s *NavService) ListChildren(ctx context.Context, tenantID, kbID, name, keywords string, page, pageSize int) ([]nav.NavNode, int64, error) {
	if pageSize <= 0 {
		pageSize = 100
	}
	offset := page * pageSize
	chunks, total, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{"parent_kwd": []string{name}}),
		navNodeSelectFields, offset, pageSize,
		navKeywordExpressions(keywords))
	if err != nil {
		return nil, 0, err
	}
	nodes := make([]nav.NavNode, 0, len(chunks))
	for _, c := range chunks {
		typ := firstStringValue(c["type_kwd"])
		nodeType := "doc"
		if typ == "nav_cluster" {
			nodeType = "cluster"
		}
		nodes = append(nodes, s.nodeFromRow(c, nodeType))
	}
	return nodes, total, nil
}

// searchNavForest resolves a keyword search into the pruned forest the nav tree
// renders: the matched nav_doc leaves PLUS the cluster path from each match up to
// its root cluster, so every root cluster stays ONE tree holding only the
// branches that lead to a match. The rows carry parent_kwd (the tree edge) and
// matched (hits only), so the caller nests the flat list without another request.
//
// The total counts the clusters the hits landed in (see searchNavClusterCount):
// the same quantity the header shows while browsing. Matching is document-level
// on purpose (Python's tree search routes to documents too): a cluster appears
// only as the path above a matched leaf, so a cluster's own summary text alone
// does not surface a tree.
func (s *NavService) searchNavForest(ctx context.Context, tenantID, kbID, keywords string, limit int) ([]nav.NavNode, int64, error) {
	matches, _, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{"type_kwd": []string{nav.TypeNavDoc}}),
		navNodeSelectFields, 0, limit, navKeywordExpressions(keywords))
	if err != nil {
		return nil, 0, err
	}
	total := searchNavClusterCount(matches)
	if len(matches) == 0 {
		return []nav.NavNode{}, total, nil
	}
	// One read of the dataset's nav rows resolves every ancestor chain at once.
	// A nav tree is small by construction (fanout, docs-per-cluster and depth are
	// all capped), so this beats a parent-by-parent walk of navMaxDepth queries.
	rows, _, err := s.navSearch(ctx, tenantID, kbID, navFilter(nil), navNodeSelectFields, 0, navTreeReadLimit, nil)
	if err != nil {
		// The path lookup failed; the hits are still a valid — if flat — answer.
		common.Warn("datasetnav: nav path lookup for the search forest failed",
			zap.String("kb_id", kbID), zap.Error(err))
		return s.navNodesFromRows(matches), total, nil
	}
	clusters := make(map[string]map[string]interface{}, len(rows))
	for _, r := range rows {
		if firstStringValue(r["type_kwd"]) != nav.TypeNavCluster {
			continue
		}
		if key := navClusterRowKey(r); key != "" {
			clusters[key] = r
		}
	}

	kept := make(map[string]map[string]interface{}, len(matches))
	hit := make(map[string]bool, len(matches))
	for _, r := range matches {
		docID := firstStringValue(r["doc_id"])
		if docID == "" {
			continue
		}
		key := navDocRowKey(docID)
		kept[key] = r
		hit[key] = true
		// Walk up to (but excluding) the root sentinel. navMaxDepth bounds the
		// walk so a corrupt parent cycle can never spin.
		parent := firstStringValue(r["parent_kwd"])
		for depth := 0; parent != "" && parent != navRootParent && depth < navMaxDepth; depth++ {
			cluster, ok := clusters[parent]
			if !ok {
				break // orphaned edge: the path above it is unknown
			}
			kept[navClusterKey(parent)] = cluster
			parent = firstStringValue(cluster["parent_kwd"])
		}
	}
	// Deterministic order (shallowest first, then by key): the caller re-nests
	// anyway, but a stable order keeps the response diffable and testable.
	keys := make([]string, 0, len(kept))
	for key := range kept {
		keys = append(keys, key)
	}
	sort.Slice(keys, func(i, j int) bool {
		if di, dj := intValue(kept[keys[i]]["depth_int"]), intValue(kept[keys[j]]["depth_int"]); di != dj {
			return di < dj
		}
		return keys[i] < keys[j]
	})
	nodes := make([]nav.NavNode, 0, len(keys))
	for _, key := range keys {
		node := s.nodeFromRow(kept[key], "doc")
		node.Matched = hit[key]
		nodes = append(nodes, node)
	}
	return nodes, total, nil
}

// searchNavClusterCount returns the number of clusters a search's hits landed in
// — the header's number in search mode, like the depth-0 cluster count it shows
// while browsing. A hit leaf sits in exactly one cluster (its parent_kwd), so
// distinct parents count the clusters touched: two hits in one cluster count
// once, and an ancestor shared by hits in different sub-clusters is a path row,
// not a second cluster.
func searchNavClusterCount(matches []map[string]interface{}) int64 {
	seen := make(map[string]bool, len(matches))
	for _, r := range matches {
		// A leaf with no cluster edge (no writer produces one) has no cluster to
		// count.
		if key := firstStringValue(r["parent_kwd"]); key != "" && key != navRootParent {
			seen[key] = true
		}
	}
	return int64(len(seen))
}

// navNodesFromRows maps engine rows to NavNodes, all marked as hits (the degrade
// path of searchNavForest, where no path rows were resolved).
func (s *NavService) navNodesFromRows(rows []map[string]interface{}) []nav.NavNode {
	nodes := make([]nav.NavNode, 0, len(rows))
	for _, r := range rows {
		node := s.nodeFromRow(r, "doc")
		node.Matched = true
		nodes = append(nodes, node)
	}
	return nodes
}

// navRowLabel returns the nav row's stored label: the value parent_kwd
// references and the tree renders. Go's writer stores it in title_kwd, Python's
// in name. Rows persisted before Infinity kept title_kwd as a column of its own
// carry it only in docnm (see engine/infinity transformChunkFields), which reads
// back as docnm_kwd; without that fallback the API answered the description's
// first line as a cluster name, so the tree's child lookup by name (the frontend
// expands with GET /navigation/<name>/children) matched no row.
func navRowLabel(row map[string]interface{}) string {
	for _, col := range []string{"name", "title_kwd", "docnm_kwd"} {
		if v := firstStringValue(row[col]); v != "" {
			return v
		}
	}
	return ""
}

// navClusterRowKey is the key a cluster's children reference through parent_kwd:
// Python's writer stores it in `name`, Go's in `title_kwd`.
func navClusterRowKey(row map[string]interface{}) string {
	return navRowLabel(row)
}

// navDocRowKey / navClusterKey namespace the two row identities so a cluster and
// a document can never collide in the search forest's keyed sets.
func navDocRowKey(docID string) string { return "doc:" + docID }
func navClusterKey(name string) string { return "cluster:" + name }

// navKeywordExpressions builds the lexical search expression used by the REST
// navigation endpoints. These are the same indexed summary fields used by the
// Python navigation search, with a stronger weight on the main content field.
func navKeywordExpressions(keywords string) []interface{} {
	keywords = strings.TrimSpace(keywords)
	if keywords == "" {
		return nil
	}
	if tokenized, err := tokenizer.Tokenize(keywords); err == nil && tokenized != "" {
		keywords = tokenized
	}
	return []interface{}{&types.MatchTextExpr{
		Fields:       []string{"content_ltks^10", "content_sm_ltks"},
		MatchingText: keywords,
		TopN:         10000,
	}}
}

// nodeFromRow converts an engine row into a NavNode.
//
// The label is title_kwd — the summary's first line: one column serves both the
// tree and the model-facing readers (NavHit.Name), so no separate display column
// is written. An explicit readable `name` column (Python's writer stores one)
// wins when present.
func (s *NavService) nodeFromRow(row map[string]interface{}, fallbackType string) nav.NavNode {
	name := navRowLabel(row)
	// A raw id (doc_id or "cluster_<hash>") is not a human-readable name; fall
	// back to a title derived from the payload description. Cluster names are the
	// child-lookup key (parent_kwd references them verbatim), so they must stay
	// intact; only non-cluster (leaf) rows get the readable fallback, otherwise
	// GET /navigation/{cluster}/children would no longer match (review Major).
	isCluster := firstStringValue(row["type_kwd"]) == "nav_cluster"
	if !isCluster && graphIsRawID(name) {
		name = ""
	}
	node := nav.NavNode{
		Name:     name,
		DocCount: intValue(row["doc_count_int"]),
		Type:     fallbackType,
		DocID:    firstStringValue(row["doc_id"]),
		Parent:   firstStringValue(row["parent_kwd"]),
	}
	if t := firstStringValue(row["type_kwd"]); t != "" {
		if t == "nav_cluster" {
			node.Type = "cluster"
		} else {
			node.Type = "doc"
		}
	}
	if payload, ok := row["content_with_weight"].(string); ok {
		var m map[string]interface{}
		if err := json.Unmarshal([]byte(payload), &m); err == nil {
			if d, ok := m["description"].(string); ok {
				node.Description = d
			}
			if node.Name == "" {
				if t, ok := m["title"].(string); ok && strings.TrimSpace(t) != "" {
					node.Name = cleanTitle(t)
				} else if d, ok := m["description"].(string); ok && strings.TrimSpace(d) != "" {
					node.Name = cleanTitle(fallbackTitle(d))
				}
			}
		}
	}
	node.HasChildren = node.Type == "cluster"
	if node.DocCount <= 0 {
		node.DocCount = 1
	}
	return node
}

// graphIsRawID reports whether a name is a meaningless internal id (a doc id or
// a "cluster_<hex>" key) rather than a human-readable title.
func graphIsRawID(name string) bool {
	name = strings.TrimSpace(name)
	if name == "" {
		return true
	}
	if strings.HasPrefix(name, "cluster_") && len(name) == len("cluster_")+8 {
		return true
	}
	if len(name) == 32 && isHexString(name) {
		return true
	}
	return false
}

func isHexString(s string) bool {
	for _, r := range s {
		if !((r >= '0' && r <= '9') || (r >= 'a' && r <= 'f') || (r >= 'A' && r <= 'F')) {
			return false
		}
	}
	return true
}

// Search runs query KNN over nav rows and returns routed doc ids.
func (s *NavService) Search(ctx context.Context, tenantID, kbID, query string, embd []float32, docScope []string, topK int) ([]nav.NavHit, error) {
	if topK <= 0 {
		topK = 8
	}
	allowed := navScopeSet(docScope)
	vec := embd
	if len(vec) == 0 {
		if s.embed == nil {
			return nil, fmt.Errorf("datasetnav: no embedding available for Search")
		}
		embeddings, err := encodeNavQuery(ctx, s.embed, tenantID, []string{query})
		if err != nil {
			return nil, err
		}
		if len(embeddings) == 0 {
			return nil, fmt.Errorf("datasetnav: embedding produced no vector")
		}
		vec = embeddings[0]
	}
	f64 := f32ToF64Slice(vec)
	// An unscoped read takes one mixed KNN read: every row is already in scope,
	// so the engine's own topK budget cannot starve the result.
	if len(allowed) == 0 {
		return s.navScan(ctx, tenantID, kbID, navFilter(nil), f64, topK, nil)
	}
	// A scoped read pushes the scope into the query as two type-pinned legs —
	// nav_doc leaves filter on doc_id, nav_cluster rows on doc_ids_kwd — so the
	// ENGINE decides what is in scope, not an in-memory pass over a fixed pool.
	// A fixed pool cannot honor the scope-before-topK contract: a pool of any
	// size N is exhausted by N higher-ranked out-of-scope rows, which silently
	// drops in-scope rows that exist (Python hits the same wall — its mixed read
	// re-checks the scope in memory after a `top_k or 10000` pool, so its typed
	// leg is the only one that actually pushes the scope: dataset_nav.py:1371-1383,
	// 1400, 1444-1447).
	//
	// Two legs are needed because a single mixed condition cannot express both
	// keys at once: `_matches_condition` ANDs across fields, so one condition
	// cannot mean "doc_id IN scope" for leaves and "doc_ids_kwd intersects
	// scope" for clusters (dataset_nav.py:1374-1383 says exactly this).
	scope := navScopeList(allowed)
	leaves, err := s.navScan(ctx, tenantID, kbID, navFilter(map[string]interface{}{
		"type_kwd": []string{nav.TypeNavDoc},
		"doc_id":   scope,
	}), f64, topK, allowed)
	if err != nil {
		return nil, err
	}
	clusters, err := s.navScan(ctx, tenantID, kbID, navFilter(map[string]interface{}{
		"type_kwd":    []string{nav.TypeNavCluster},
		"doc_ids_kwd": scope,
	}), f64, topK, allowed)
	if err != nil {
		return nil, err
	}
	// Both legs score the same vector with the same cosine metric, so their
	// _score values are directly comparable. Taking each leg's top topK and
	// merging by score yields the global topK of the union: a row ranked below
	// its own leg's cap is already outranked by topK in-scope rows of that leg.
	merged := append(leaves, clusters...)
	sort.SliceStable(merged, func(i, j int) bool { return merged[i].Score > merged[j].Score })
	if len(merged) > topK {
		merged = merged[:topK]
	}
	return merged, nil
}

// navScan runs one KNN nav read behind filter, maps the rows to NavHits, and
// re-checks the scope in memory the way Python does unconditionally
// (dataset_nav.py:1444). The re-check is belt-and-braces on top of a pushed
// scope filter, and trims a cluster's coverage to the scoped set. allowed may
// be nil for an unscoped read.
func (s *NavService) navScan(ctx context.Context, tenantID, kbID string, filter map[string]interface{}, f64 []float64, limit int, allowed map[string]struct{}) ([]nav.NavHit, error) {
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		filter,
		[]string{"type_kwd", "title_kwd", "docnm_kwd", "doc_id", "doc_ids_kwd", "_score"}, 0, limit,
		[]interface{}{&types.MatchDenseExpr{
			VectorColumnName:  fmt.Sprintf("q_%d_vec", len(f64)),
			EmbeddingData:     f64,
			EmbeddingDataType: "float",
			DistanceType:      "cosine",
			TopN:              limit,
			ExtraOptions:      map[string]interface{}{"similarity": 0.0},
		}})
	if err != nil {
		return nil, err
	}
	hits := make([]nav.NavHit, 0, len(chunks))
	for _, c := range chunks {
		h := nav.NavHit{
			Type:   firstStringValue(c["type_kwd"]),
			Name:   navRowLabel(c),
			DocID:  firstStringValue(c["doc_id"]),
			DocIDs: firstStringSlice(c["doc_ids_kwd"]),
		}
		if sc, ok := c["_score"].(float64); ok {
			h.Score = sc
		} else if sc, ok := c["_score"].(float32); ok {
			h.Score = float64(sc)
		}
		if !navHitInScope(h, allowed) {
			continue
		}
		if len(allowed) > 0 && len(h.DocIDs) > 0 {
			// A scoped search must only surface in-scope documents: cut a
			// cluster's coverage list down to the scoped set so no out-of-scope
			// doc appears under a cluster that merely overlaps the scope
			// (dataset_nav.py:1460-1465).
			h.DocIDs = navIntersectScope(h.DocIDs, allowed)
		}
		hits = append(hits, h)
	}
	return hits, nil
}

// navScopeList renders a scope set as a sorted list for an engine filter, so the
// term order is deterministic run to run (Python sorts its scope the same way:
// dataset_nav.py:1381-1383).
func navScopeList(allowed map[string]struct{}) []string {
	out := make([]string, 0, len(allowed))
	for d := range allowed {
		out = append(out, d)
	}
	sort.Strings(out)
	return out
}

// navScopeSet normalizes a caller's doc scope the way search_dataset_nav does
// (dataset_nav.py:1364): trimmed, non-empty, deduped. A nil result means "no
// restriction".
func navScopeSet(docScope []string) map[string]struct{} {
	if len(docScope) == 0 {
		return nil
	}
	out := make(map[string]struct{}, len(docScope))
	for _, d := range docScope {
		if d = strings.TrimSpace(d); d != "" {
			out[d] = struct{}{}
		}
	}
	if len(out) == 0 {
		return nil
	}
	return out
}

// navHitInScope mirrors Python _in_nav_scope (dataset_nav.py:611): a nav_cluster
// row belongs when it covers at least one scoped document (a non-empty coverage
// list is the reliable discriminator — a cluster's doc_id is the kb_id, not a
// document), a nav_doc leaf when its doc_id is in scope.
func navHitInScope(h nav.NavHit, allowed map[string]struct{}) bool {
	if len(allowed) == 0 {
		return true
	}
	if len(h.DocIDs) > 0 {
		for _, d := range h.DocIDs {
			if _, ok := allowed[strings.TrimSpace(d)]; ok {
				return true
			}
		}
		return false
	}
	_, ok := allowed[strings.TrimSpace(h.DocID)]
	return ok
}

// navIntersectScope keeps only the doc ids that are inside the scope, preserving
// order.
func navIntersectScope(docIDs []string, allowed map[string]struct{}) []string {
	out := make([]string, 0, len(docIDs))
	for _, d := range docIDs {
		if _, ok := allowed[strings.TrimSpace(d)]; ok {
			out = append(out, d)
		}
	}
	return out
}

// SummariesByDocIDs returns the nav_doc description — the document's overall
// summary — keyed by doc_id for the given documents. It mirrors Python
// dataset_api_service._nav_doc_summaries: it reads the nav_doc rows
// (type_kwd=nav_doc) for the doc_ids and yields, per
// doc, the payload description. The description wins over the row's label on
// purpose: callers render this value to the model as the routed document's
// <summary>, and title_kwd holds only the summary's first line (length-capped).
// A row whose payload carries no description falls back to its readable label; a
// document with no nav_doc row is absent from the result.
func (s *NavService) SummariesByDocIDs(ctx context.Context, tenantID, kbID string, docIDs []string) map[string]string {
	if len(docIDs) == 0 {
		return map[string]string{}
	}
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{
			"type_kwd": []string{"nav_doc"},
			"doc_id":   docIDs,
		}),
		[]string{"type_kwd", "name", "title_kwd", "docnm_kwd", "content_with_weight", "doc_id"},
		0, len(docIDs), nil)
	if err != nil {
		return map[string]string{}
	}
	out := make(map[string]string, len(chunks))
	for _, c := range chunks {
		docID := firstStringValue(c["doc_id"])
		if docID == "" {
			continue
		}
		summary := ""
		if payload, ok := c["content_with_weight"].(string); ok {
			var m map[string]interface{}
			if json.Unmarshal([]byte(payload), &m) == nil {
				if d, ok := m["description"].(string); ok {
					summary = strings.TrimSpace(d)
				}
			}
		}
		if summary == "" {
			// No description in the payload: fall back to the stored label
			// (readable name, else title_kwd/docnm), rejecting raw ids — a
			// 32-hex id or "cluster_<hash>" is not a human label.
			summary = navRowLabel(c)
			if graphIsRawID(summary) {
				summary = ""
			}
		}
		if summary != "" {
			out[docID] = summary
		}
	}
	return out
}

// UpsertDoc places one document summary into the nav tree. Minimal closed loop:
// deterministic placement (KNN find best cluster -> merge if sim>=0.80, else a
// new root-level cluster). No LLM, no split/rebalance, no cascade cleanup.
func (s *NavService) UpsertDoc(ctx context.Context, in nav.UpsertDocInput) error {
	if strings.TrimSpace(in.Summary) == "" {
		return nil
	}
	in.CompileKind = types.CanonicalCompilationKind(in.CompileKind)
	if in.CompileKind == "" {
		in.CompileKind = "tree"
	}
	if in.CompileKind != "tree" && in.CompileKind != "page_index" {
		return fmt.Errorf("datasetnav: invalid compilation kind %q", in.CompileKind)
	}
	de, err := s.docEngine()
	if err != nil {
		return err
	}
	if s.embed == nil && len(in.Embedd) == 0 {
		return fmt.Errorf("datasetnav: embedder required for UpsertDoc")
	}
	vec := in.Embedd
	if len(vec) == 0 {
		embeddings, err := s.embed.Encode(ctx, in.TenantID, []string{in.Summary})
		if err != nil {
			return err
		}
		if len(embeddings) == 0 {
			return nil
		}
		vec = embeddings[0]
	}
	contentLtks, err := tokenizer.Tokenize(in.Summary)
	if err != nil || contentLtks == "" {
		contentLtks = in.Summary
	}
	contentSmLtks, err := tokenizer.FineGrainedTokenize(contentLtks)
	if err != nil || contentSmLtks == "" {
		contentSmLtks = contentLtks
	}

	// storeGet: skip if a nav_doc for this doc already exists with same summary.
	existing, _, err := s.navSearch(ctx, in.TenantID, in.KbID,
		navFilter(map[string]interface{}{
			"type_kwd": []string{nav.TypeNavDoc},
			"doc_id":   []string{in.DocID},
		}),
		[]string{"content_with_weight", "content_ltks", "content_sm_ltks", "title_kwd", "docnm_kwd", "compile_kwd", "scope_kwd"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(existing) > 0 {
		// The stored label can drift without the summary changing, so a recompile
		// refreshes it in place instead of leaving a stale row: a row written by an
		// older label rule (title_kwd holding the file name) goes back to the
		// summary's first line, or the model-facing readers would keep seeing a
		// file name. The tokenized text is (re)built when it is missing.
		title := navDocTitle(in.Summary)
		titleStale := navRowLabel(existing[0]) != title
		kindStale := firstStringValue(existing[0]["compile_kwd"]) != in.CompileKind
		scopeStale := firstStringValue(existing[0]["scope_kwd"]) != "doc"
		ltksStale := firstStringValue(existing[0]["content_ltks"]) == "" ||
			firstStringValue(existing[0]["content_sm_ltks"]) == ""
		if payload, ok := existing[0]["content_with_weight"].(string); ok {
			var m map[string]interface{}
			if err := json.Unmarshal([]byte(payload), &m); err == nil {
				if d, _ := m["description"].(string); d == in.Summary {
					if !titleStale && !ltksStale && !kindStale && !scopeStale {
						return nil // unchanged
					}
					updates := map[string]interface{}{}
					if scopeStale {
						updates["scope_kwd"] = "doc"
					}
					if kindStale {
						updates["compile_kwd"] = in.CompileKind
					}
					if titleStale {
						updates["title_kwd"] = title
					}
					if ltksStale {
						updates["content_ltks"] = contentLtks
						updates["content_sm_ltks"] = contentSmLtks
					}
					return de.UpdateChunks(ctx,
						map[string]interface{}{
							"type_kwd": []string{nav.TypeNavDoc},
							"doc_id":   []string{in.DocID},
							"kb_id":    in.KbID,
						},
						updates, s.navIndexName(in.TenantID), in.KbID)
				}
			}
		}
		// Changed summary: remove the old nav_doc first (and prune any emptied
		// cluster). The doc may have lived in a cluster; the cluster is then
		// decremented/cascaded by RemoveDoc's cleanup logic.
		parent, err := s.deleteNavDoc(ctx, in.TenantID, in.KbID, in.DocID)
		if err != nil {
			return err
		}
		if parent != "" && parent != navRootParent {
			if err := s.removeDocFromCluster(ctx, in.TenantID, in.KbID, parent, in.DocID); err != nil {
				return err
			}
		}
		if err := s.cleanupEmptyCluster(ctx, in.TenantID, in.KbID, parent); err != nil {
			return err
		}
	}

	bestName, sim, bestDepth, err := s.findBestCluster(ctx, in.TenantID, in.KbID, vec)
	if err != nil {
		return err
	}
	idx := s.navIndexName(in.TenantID)

	if bestName != "" && sim >= navMergeThreshold {
		parent := bestName
		// Fuse this document's summary into the cluster description and re-embed
		// the cluster with the merged text (Python upsert_dataset_nav_doc's merge
		// branch), so the cluster keeps describing every document it holds and the
		// next placement scores against the merged topic instead of the first
		// document's summary alone.
		if err := s.mergeClusterDescription(ctx, de, in.TenantID, in.KbID, bestName, in.Summary); err != nil {
			return err
		}
		if err := s.appendDocToCluster(ctx, de, in.TenantID, in.KbID, bestName, in.DocID,
			fmt.Sprintf("q_%d_vec", len(vec)), in.CompileKind); err != nil {
			return err
		}
		// Explicit stable id (A5): the nav_doc row is addressable by a
		// deterministic id (hash of the "dataset_nav:doc:{doc_id}" key) so
		// RemoveDoc / cascade cleanup can locate and delete it precisely,
		// instead of relying on a doc_id + type filter alone.
		row := map[string]interface{}{
			"id":            navDocID(in.TenantID, in.KbID, in.DocID),
			"compile_kwd":   in.CompileKind,
			"scope_kwd":     "doc",
			"available_int": 0,
			"type_kwd":      "nav_doc",
			// The nav_doc's label is a readable title derived from the summary
			// (Python _clean_title/_fallback_title) — never the raw doc id,
			// which is meaningless in the UI. The doc_id is still stored for
			// lookups; NavHit.Name reads this same column, so the tree and the
			// model-facing readers stay on one label.
			"title_kwd":  navDocTitle(in.Summary),
			"parent_kwd": parent,
			// The nav_doc sits one level below its (possibly nested) parent
			// cluster, so its depth is parentDepth+1 — not a hard-coded 1.
			"depth_int":           bestDepth + 1,
			"doc_id":              in.DocID,
			"doc_count_int":       1,
			"content_with_weight": payloadJSONNav(map[string]interface{}{"type": "nav_doc", "description": in.Summary}),
			"content_ltks":        contentLtks,
			"content_sm_ltks":     contentSmLtks,
			"q_" + fmt.Sprintf("%d", len(vec)) + "_vec": f32ToF64Slice(vec),
		}
		_, err = de.InsertChunks(ctx, []map[string]interface{}{row}, idx, in.KbID, "")
		return err
	}

	// A similar-but-not-mergeable document opens its own cluster (Python
	// _MIN_SIM=0.50). Where it lands follows the best match's depth:
	//
	//   - a ROOT-level best match opens a ROOT-level cluster, beside it. That is
	//     the case a fresh dataset always reaches, and it is what Python's branch
	//     does: it attaches the new cluster to `best_parent`, which for a root
	//     best match is the root sentinel. Hiding the new topic one level down
	//     instead (what this branch used to do) meant a second topic never showed
	//     up in the tree's top level.
	//   - a best match that is itself nested keeps the child semantics: the new
	//     cluster sits one level deeper, which is what keeps a large tree from
	//     flattening into one root per topic.
	parent := navRootParent
	depth := 0
	if bestName != "" && sim >= navMinSim && bestDepth > 0 {
		parent = bestName
		depth = bestDepth + 1
	}
	// New cluster: when an LLM is configured, generate a short name + summary
	// (Python _llm_create_summary); otherwise fall back to a deterministic name
	// (A1, graceful without LLM).
	name, summary := s.llmCreateSummary(ctx, in.TenantID, in.Summary)
	if summary == "" {
		summary = in.Summary
	}
	clusterContentLtks, err := tokenizer.Tokenize(summary)
	if err != nil || clusterContentLtks == "" {
		clusterContentLtks = summary
	}
	clusterContentSmLtks, err := tokenizer.FineGrainedTokenize(clusterContentLtks)
	if err != nil || clusterContentSmLtks == "" {
		clusterContentSmLtks = clusterContentLtks
	}
	clusterRow := map[string]interface{}{
		"id":                  navClusterID(in.TenantID, in.KbID, name),
		"doc_id":              in.KbID, // cluster rows carry the kb as doc_id (Python _build_nav_cluster_row), so ES InsertChunks does not skip them
		"compile_kwd":         in.CompileKind,
		"scope_kwd":           "dataset",
		"available_int":       0,
		"type_kwd":            "nav_cluster",
		"title_kwd":           name,
		"parent_kwd":          parent,
		"depth_int":           depth,
		"doc_count_int":       1,
		"doc_ids_kwd":         []string{in.DocID},
		"content_with_weight": payloadJSONNav(map[string]interface{}{"type": "nav_cluster", "description": summary}),
		"content_ltks":        clusterContentLtks,
		"content_sm_ltks":     clusterContentSmLtks,
		"q_" + fmt.Sprintf("%d", len(vec)) + "_vec": f32ToF64Slice(vec),
	}
	_, err = de.InsertChunks(ctx, []map[string]interface{}{clusterRow}, idx, in.KbID, "")
	if err != nil {
		return err
	}
	// Always emit a nav_doc leaf under the (new) cluster, mirroring Python
	// upsert_dataset_nav_doc (the merge branch does the same at its parent). A
	// new root cluster that only folds the doc into doc_ids_kwd would leave the
	// nav tree with a single cluster and no nav_doc child, so /children returns
	// empty. The nav_doc carries a readable title + parent_kwd = the cluster name.
	docRow := map[string]interface{}{
		"id":                  navDocID(in.TenantID, in.KbID, in.DocID),
		"compile_kwd":         in.CompileKind,
		"scope_kwd":           "doc",
		"available_int":       0,
		"type_kwd":            "nav_doc",
		"title_kwd":           navDocTitle(in.Summary),
		"parent_kwd":          name,
		"depth_int":           depth + 1,
		"doc_id":              in.DocID,
		"doc_count_int":       1,
		"content_with_weight": payloadJSONNav(map[string]interface{}{"type": "nav_doc", "description": in.Summary}),
		"content_ltks":        contentLtks,
		"content_sm_ltks":     contentSmLtks,
		"q_" + fmt.Sprintf("%d", len(vec)) + "_vec": f32ToF64Slice(vec),
	}
	_, err = de.InsertChunks(ctx, []map[string]interface{}{docRow}, idx, in.KbID, "")
	return err
}

// navDocID returns the explicit stable id for a nav_doc row (A5), a hash of the
// canonical "dataset_nav:doc:{doc_id}" key. It is deterministic so deletes and
// cascade cleanup can address the row without a doc_id+type filter scan.
func navDocID(tenantID, kbID, docID string) string {
	return "dataset_nav_doc_" + contentHash8(tenantID+"\x00"+kbID+"\x00"+docID)
}

// navClusterID returns the explicit stable id for a nav_cluster row (A5), a hash
// of the canonical "dataset_nav:cluster:{kb}:{name}" key (mirroring Python
// _nav_cluster_id).
func navClusterID(tenantID, kbID, name string) string {
	return "dataset_nav_cluster_" + contentHash8(tenantID+"\x00"+kbID+"\x00"+name)
}

// navClusterCondition addresses one nav cluster row by its deterministic row id,
// the way Python's dataset_nav does (every cluster update/delete resolves
// _nav_cluster_id and read-modify-writes that row). The label is not usable as a
// key: it is an LLM-written name that can share words with another cluster, and
// Infinity cannot match a multi-token value on these columns at all (see
// engine/infinity keywordFilterCondition). The row id is always single-token.
func navClusterCondition(tenantID, kbID, clusterName string) map[string]interface{} {
	return navFilter(map[string]interface{}{
		"id": []string{navClusterID(tenantID, kbID, clusterName)},
	})
}

// navChildRehomeCondition builds the condition that moves one split child under
// its new parent, or nil when the child cannot be addressed at all.
//
// The row id is preferred: the label is empty for rows the Infinity write path
// folded into docnm, and two children can share a summary's first line, so a
// label filter can miss the row or hit a sibling. A nav_doc leaf without a row id
// is still identifiable by its document. Nothing else is safe — with blank
// keywords dropped, a type-only condition would match every row of that type in
// the dataset.
func navChildRehomeCondition(child map[string]interface{}, kbID string) map[string]interface{} {
	typ := firstStringValue(child["type_kwd"])
	if typ == "" {
		return nil
	}
	cond := map[string]interface{}{
		"type_kwd": []string{nav.TypeNavDoc, nav.TypeNavCluster},
		"kb_id":    kbID,
	}
	if rowID := firstStringValue(child["id"]); rowID != "" {
		cond["id"] = []string{rowID}
		return cond
	}
	if docID := firstStringValue(child["doc_id"]); typ == "nav_doc" && docID != "" {
		cond["type_kwd"] = []string{typ}
		cond["doc_id"] = []string{docID}
		return cond
	}
	return nil
}

// cleanupEmptyCluster deletes a nav_cluster that holds no docs and no child
// clusters, then recurses to its parent (cascade, mirroring Python
// _cleanup_empty_cluster). It is called by RemoveDoc after deleting a nav_doc so
// an emptied cluster does not linger.
func (s *NavService) cleanupEmptyCluster(ctx context.Context, tenantID, kbID, clusterName string) error {
	if clusterName == "" || clusterName == navRootParent {
		return nil
	}
	de, err := s.docEngine()
	if err != nil {
		return err
	}
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navClusterCondition(tenantID, kbID, clusterName),
		[]string{"id", "parent_kwd", "doc_count_int", "doc_ids_kwd"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(chunks) == 0 {
		return nil
	}
	// Children: count any nav_cluster/nav_doc whose parent is this cluster.
	children, _, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{"parent_kwd": []string{clusterName}}),
		[]string{"id"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(children) > 0 {
		return nil // not empty: has children
	}
	parent := firstStringValue(chunks[0]["parent_kwd"])
	if intValue(chunks[0]["doc_count_int"]) > 0 {
		return nil // still has docs
	}
	// Delete this cluster by the row id returned by the search (robust whether
	// the engine preserves our explicit stable id or assigns its own).
	rowID := firstStringValue(chunks[0]["id"])
	if rowID == "" {
		rowID = navClusterID(tenantID, kbID, clusterName)
	}
	_, err = de.DeleteChunks(ctx,
		map[string]interface{}{"id": []string{rowID}, "kb_id": kbID},
		s.navIndexName(tenantID), kbID)
	if err != nil {
		return err
	}
	// Recurse upward.
	return s.cleanupEmptyCluster(ctx, tenantID, kbID, parent)
}

// findBestCluster finds the best-matching cluster via level-by-level descent
// (mirroring Python _find_best_cluster). It KNNs the current level's clusters
// and, while the match is >= recurse threshold, descends into that cluster's
// children. Returns the DEEPEST cluster reached — the strongest match is not
// kept, exactly like Python — plus its similarity and depth (0 = root), so the
// caller can assign consistent child depth_int values.
func (s *NavService) findBestCluster(ctx context.Context, tenantID, kbID string, vec []float32) (string, float64, int, error) {
	f64 := f32ToF64Slice(vec)
	parent := navRootParent
	bestName := ""
	bestSim := 0.0
	bestDepth := 0
	for level := 0; level < navMaxDepth; level++ {
		// KNN among clusters whose parent is the current level.
		chunks, _, err := s.navSearch(ctx, tenantID, kbID,
			navFilter(map[string]interface{}{
				"type_kwd":   []string{"nav_cluster"},
				"parent_kwd": []string{parent},
			}),
			[]string{"title_kwd", "docnm_kwd", "_score"}, 0, 1,
			[]interface{}{&types.MatchDenseExpr{
				VectorColumnName:  fmt.Sprintf("q_%d_vec", len(f64)),
				EmbeddingData:     f64,
				EmbeddingDataType: "float",
				DistanceType:      "cosine",
				TopN:              1,
				ExtraOptions:      map[string]interface{}{"similarity": 0.0},
			}})
		if err != nil {
			return "", 0, 0, err
		}
		if len(chunks) == 0 {
			break
		}
		name := navRowLabel(chunks[0])
		sim := rowScore(chunks[0])
		// Adopt-and-overwrite, mirroring Python _find_best_cluster: the result is
		// the DEEPEST cluster reached while the descent keeps clearing
		// navRecurse, not the strongest one seen. A strong ancestor therefore
		// does NOT shadow a weaker-but-recurseable descendant — the placement
		// then decides on the descendant's own similarity. The root (level 0) is
		// adopted unconditionally, exactly as Python seeds its `best` with the
		// top-1 root; a child is adopted only when it still clears the threshold.
		if level == 0 || sim >= navRecurse {
			bestName, bestSim, bestDepth = name, sim, level
		}
		// Descend only while the current match is strong enough that a deeper
		// child could be a better target.
		if sim < navRecurse {
			break
		}
		parent = name
	}
	return bestName, bestSim, bestDepth, nil
}

// rowScore extracts the engine's _score field as float64.
func rowScore(row map[string]interface{}) float64 {
	if sc, ok := row["_score"].(float64); ok {
		return sc
	}
	if sc, ok := row["_score"].(float32); ok {
		return float64(sc)
	}
	return 0
}

// maybeSplitCluster rebalances an overfull cluster into two sibling clusters,
// mirroring Python dataset_nav._maybe_split_cluster. A cluster is split when it
// has too many direct children (> _MAX_FANOUT=64) or too many nav_doc children
// (> _MAX_DOCS_PER_CLUSTER=50). The minimal loop uses a deterministic 2-way
// partition by child index parity (a stand-in for k-means) to keep behavior
// reproducible without an embedder; the LLM-enhanced implementation would pick
// the two best seed vectors instead.
func (s *NavService) maybeSplitCluster(ctx context.Context, tenantID, kbID, clusterName, vecCol string) error {
	de, err := s.docEngine()
	if err != nil {
		return err
	}
	// Count direct children (nav_cluster + nav_doc) of this cluster. vecCol (the
	// engine column q_<dim>_vec, e.g. from the doc being appended) is selected so
	// the split siblings can inherit a representative vector for KNN routing; an
	// empty vecCol skips it (callers without a known dim).
	selectFields := []string{"id", "doc_id", "doc_count_int", "doc_ids_kwd", "title_kwd", "docnm_kwd", "type_kwd"}
	if vecCol != "" {
		selectFields = append(selectFields, vecCol)
	}
	children, total, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{"parent_kwd": []string{clusterName}}),
		selectFields, 0, 200, nil)
	if err != nil {
		return err
	}
	if len(children) < 2 {
		return nil
	}
	// Split signal comes purely from the direct children (mirroring Python
	// dataset_nav._maybe_split_cluster): too many total children (fanout) or too
	// many nav_doc children (a leaf that accumulated more docs than the cap). The
	// cluster's own row is only re-read below when a split is actually happening,
	// so the common (under-threshold) append path performs a single children
	// search instead of two (review Major).
	fanout := 0
	navDocKids := 0
	for _, c := range children {
		if firstStringValue(c["type_kwd"]) == "nav_doc" {
			navDocKids++
		}
		fanout++
	}
	if fanout <= navMaxFanout && navDocKids <= navMaxDocsPerCluster {
		return nil
	}
	// The split needs the original cluster's row id, parent, depth and directly
	// held docs; select id + doc_ids_kwd so the split can delete by the
	// engine-assigned row id and inherit the cluster's directly-held documents.
	clusterChunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navClusterCondition(tenantID, kbID, clusterName),
		[]string{"id", "doc_count_int", "doc_ids_kwd", "parent_kwd", "depth_int", "compile_kwd"}, 0, 1, nil)
	if err != nil {
		return err
	}

	// Split into two sibling clusters "A"/"B", reparenting children by parity of
	// their doc count so each half gets a comparable load.
	parent := navRootParent
	if len(clusterChunks) > 0 {
		parent = firstStringValue(clusterChunks[0]["parent_kwd"])
	}
	splitA := clusterName + ":A"
	splitB := clusterName + ":B"
	// Rehome each child under splitA/splitB by parity of child index, and
	// accumulate the aggregate (doc_count_int, doc_ids_kwd, vector) that each
	// split must inherit so the replacement clusters stay searchable by KNN and
	// can support deletion bookkeeping (review issue 5). nav_doc children carry
	// doc_ids_kwd of their own doc; nav_cluster children carry their subtree's.
	accA := struct {
		count int
		ids   []string
		vec   []float32
	}{}
	accB := struct {
		count int
		ids   []string
		vec   []float32
	}{}
	// Every child must be addressable before the first write. The rehome points
	// children at splitA/splitB, and those rows are only inserted after the
	// original cluster is deleted, so a child that cannot be rehomed would be left
	// hanging off a name no query can reach — refuse the split instead of
	// half-moving the subtree.
	for _, child := range children {
		if navChildRehomeCondition(child, kbID) == nil {
			return fmt.Errorf("datasetnav: refusing to split cluster %q: child %q carries no row id, document id or type",
				clusterName, navRowLabel(child))
		}
	}
	for i, child := range children {
		acc := &accA
		if i%2 == 1 {
			acc = &accB
		}
		typ := firstStringValue(child["type_kwd"])
		// Aggregate this child's doc count + doc ids into the target split.
		if c := intValue(child["doc_count_int"]); c > 0 {
			acc.count += c
		}
		childDocIDs := firstStringSlice(child["doc_ids_kwd"])
		// nav_doc rows keep their sole member in doc_id; doc_ids_kwd belongs to
		// nav_cluster rows only. Preserve both shapes when rebuilding the split
		// clusters' membership indexes for RemoveDoc.
		if typ == "nav_doc" {
			childDocIDs = append(childDocIDs, firstStringValue(child["doc_id"]))
		}
		acc.ids = appendUnique(acc.ids, childDocIDs)
		childCond := navChildRehomeCondition(child, kbID)
		if childCond == nil {
			// Unreachable after the pre-pass above; kept so a future caller
			// cannot fall through to a condition that matches the whole dataset.
			return fmt.Errorf("datasetnav: refusing to rehome %s child %q", typ, navRowLabel(child))
		}
		if err := de.UpdateChunks(ctx, childCond,
			map[string]interface{}{"parent_kwd": accTarget(i, splitA, splitB)},
			s.navIndexName(tenantID), kbID); err != nil {
			return err
		}
	}
	// The original cluster may be tracked by a row id the engine assigned (not
	// our deterministic navClusterID); delete by the search-returned id, falling
	// back to the deterministic id, so the delete always matches (review Major).
	origRowID := ""
	if len(clusterChunks) > 0 {
		origRowID = firstStringValue(clusterChunks[0]["id"])
	}
	if origRowID == "" {
		origRowID = navClusterID(tenantID, kbID, clusterName)
	}
	// The original cluster may itself directly hold documents (the standalone
	// cluster case), which must be inherited by the split siblings.
	origIDs := []string{}
	if len(clusterChunks) > 0 {
		origIDs = firstStringSlice(clusterChunks[0]["doc_ids_kwd"])
	}
	// Delete the original cluster and insert the two split clusters carrying the
	// aggregated doc count, doc ids, and a representative vector so the split
	// clusters remain KNN-searchable.
	_, err = de.DeleteChunks(ctx,
		map[string]interface{}{"id": []string{origRowID}, "kb_id": kbID},
		s.navIndexName(tenantID), kbID)
	if err != nil {
		return err
	}
	splitCompileKind := "tree"
	if len(clusterChunks) > 0 && types.CompilationKind(clusterChunks[0]) == "page_index" {
		splitCompileKind = "page_index"
	}
	for _, spl := range []struct {
		name  string
		count int
		ids   []string
	}{{splitA, accA.count, accA.ids}, {splitB, accB.count, accB.ids}} {
		// Distribute the original cluster's directly-held docs into each split by
		// parity so no tracked document is lost (review Major).
		for i, d := range origIDs {
			if i%2 == 0 && spl.name == splitA {
				spl.ids = appendUnique(spl.ids, []string{d})
				spl.count++
			} else if i%2 == 1 && spl.name == splitB {
				spl.ids = appendUnique(spl.ids, []string{d})
				spl.count++
			}
		}
		description := "split of " + clusterName
		contentLtks, err := tokenizer.Tokenize(description)
		if err != nil || contentLtks == "" {
			contentLtks = description
		}
		contentSmLtks, err := tokenizer.FineGrainedTokenize(contentLtks)
		if err != nil || contentSmLtks == "" {
			contentSmLtks = contentLtks
		}
		row := map[string]interface{}{
			"id":                  navClusterID(tenantID, kbID, spl.name),
			"compile_kwd":         splitCompileKind,
			"scope_kwd":           "dataset",
			"available_int":       0,
			"type_kwd":            "nav_cluster",
			"title_kwd":           spl.name,
			"parent_kwd":          parent,
			"depth_int":           clusterDepth(clusterChunks),
			"doc_count_int":       spl.count,
			"doc_ids_kwd":         spl.ids,
			"content_with_weight": payloadJSONNav(map[string]interface{}{"type": "nav_cluster", "description": description}),
			"content_ltks":        contentLtks,
			"content_sm_ltks":     contentSmLtks,
		}
		// Representative vector: if any reparented child carried a vector, use it
		// so the split cluster participates in KNN routing. This is a heuristic
		// stand-in for Python's k-means centroid.
		if vec := pickAnyVector(children, i2boolForTarget(spl.name, splitA)); len(vec) > 0 {
			row["q_"+fmt.Sprintf("%d", len(vec))+"_vec"] = f32ToF64Slice(vec)
		}
		if _, err := de.InsertChunks(ctx, []map[string]interface{}{row}, s.navIndexName(tenantID), kbID, ""); err != nil {
			return err
		}
	}
	_ = total
	return nil
}

// accTarget returns the split target name for a child index by parity.
func accTarget(i int, splitA, splitB string) string {
	if i%2 == 1 {
		return splitB
	}
	return splitA
}

// i2boolForTarget reports whether name equals splitA (used to pick which split's
// children to source a representative vector from).
func i2boolForTarget(name, splitA string) bool { return name == splitA }

// pickAnyVector returns the first non-empty vector among the children that map
// to a given parity bucket (splitA→even, splitB→odd).
func pickAnyVector(children []map[string]interface{}, wantA bool) []float32 {
	for i, c := range children {
		if (i%2 == 1) == wantA {
			continue
		}
		// The engine returns dense vectors as []interface{} of float64 (q_<n>_vec
		// is unboxed); walk any key that looks like a q_*_vec.
		for k, v := range c {
			if !strings.HasPrefix(k, "q_") || !strings.HasSuffix(k, "_vec") {
				continue
			}
			return toF32Vector(v)
		}
	}
	return nil
}

// toF32Vector converts an engine vector value ([]interface{} of float64) into
// []float32, returning nil on mismatch.
func toF32Vector(v interface{}) []float32 {
	arr, ok := v.([]interface{})
	if !ok {
		return nil
	}
	out := make([]float32, 0, len(arr))
	for _, x := range arr {
		f, ok := x.(float64)
		if !ok {
			return nil
		}
		out = append(out, float32(f))
	}
	return out
}

// clusterDepth returns the depth_int of the original cluster (for the split
// siblings), defaulting to 0.
func clusterDepth(clusterChunks []map[string]interface{}) int {
	if len(clusterChunks) == 0 {
		return 0
	}
	return intValue(clusterChunks[0]["depth_int"])
}

// mergeClusterDescription fuses one document's summary into an existing
// cluster's description and re-embeds the cluster with the merged text
// (mirroring Python upsert_dataset_nav_doc's merge branch: _llm_merge, then a
// re-embed of the changed description). Nothing is written when there is no LLM
// — Python's _llm_merge returns the existing text when chat_mdl is nil — or when
// the model reply leaves the description unchanged, so a no-LLM deployment keeps
// its previous behaviour.
func (s *NavService) mergeClusterDescription(ctx context.Context, de engine.DocEngine, tenantID, kbID, clusterName, docSummary string) error {
	docSummary = strings.TrimSpace(docSummary)
	if docSummary == "" {
		return nil
	}
	rows, _, err := s.navSearch(ctx, tenantID, kbID,
		navClusterCondition(tenantID, kbID, clusterName),
		[]string{"content_with_weight"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(rows) == 0 {
		return nil
	}
	payload := map[string]interface{}{}
	if raw, ok := rows[0]["content_with_weight"].(string); ok {
		_ = json.Unmarshal([]byte(raw), &payload)
	}
	oldDesc := firstStringValue(payload["description"])
	if oldDesc == "" {
		// Nothing to fuse with: the row carries no description to preserve.
		return nil
	}
	merged := strings.TrimSpace(s.llmMergeDescription(ctx, tenantID, []string{oldDesc, docSummary}))
	if merged == "" || merged == oldDesc {
		return nil
	}
	// Mutate the parsed payload so any extra keys a writer stored there (Python
	// carries keywords/entities/graph_content) survive the rewrite.
	payload["description"] = merged
	updates := map[string]interface{}{"content_with_weight": payloadJSONNav(payload)}
	// The description is part of the cluster's keyword index, so its tokens are
	// refreshed alongside it.
	if ltks, err := tokenizer.Tokenize(merged); err == nil && ltks != "" {
		updates["content_ltks"] = ltks
		if smLtks, err := tokenizer.FineGrainedTokenize(ltks); err == nil && smLtks != "" {
			updates["content_sm_ltks"] = smLtks
		}
	}
	if s.embed != nil {
		if vecs, err := s.embed.Encode(ctx, tenantID, []string{merged}); err == nil && len(vecs) > 0 && len(vecs[0]) > 0 {
			updates[fmt.Sprintf("q_%d_vec", len(vecs[0]))] = f32ToF64Slice(vecs[0])
		}
	}
	return de.UpdateChunks(ctx,
		navClusterCondition(tenantID, kbID, clusterName), updates, s.navIndexName(tenantID), kbID)
}

// llmMergeDescription merges a set of source descriptions into one via the
// optional LLM (temperature 0.1, mirroring Python _llm_merge). texts is
// [existing description, new document summary]. Without an LLM — or when the
// model reply is unusable — the existing description is returned unchanged,
// mirroring Python's fallback (it keeps the old summary rather than
// concatenating).
func (s *NavService) llmMergeDescription(ctx context.Context, tenantID string, texts []string) string {
	existing := ""
	if len(texts) > 0 {
		existing = texts[0]
	}
	if s.llm != nil && len(texts) > 0 {
		merged, err := s.llm.Merge(ctx, tenantID, texts)
		if err != nil {
			// Keep the stored description; the warning is the only signal that the
			// configured chat model could not be used (Python logs the same way).
			common.Warn("datasetnav: LLM cluster-description merge failed, keeping the existing description",
				zap.String("tenant_id", tenantID), zap.Error(err))
		} else if strings.TrimSpace(merged) != "" {
			return merged
		}
	}
	return existing
}

// cleanTitle normalizes a raw title/summary into a one-line, length-capped
// display name (mirroring Python dataset_nav._clean_title).
func cleanTitle(title string) string {
	return truncateString(strings.Join(strings.Fields(title), " "), 48)
}

// fallbackTitle derives a short readable title from a summary by taking the
// first non-empty line and stripping Markdown emphasis/heading markers. The
// tree-root summaries carry a one-line Markdown title ("**Title**" or
// "## Title") on the first line, so this yields a clean, URL-friendly label —
// far more readable than taking the first whitespace words of the body.
func fallbackTitle(summary string) string {
	line := summary
	if idx := strings.IndexAny(line, "\n\r"); idx >= 0 {
		line = line[:idx]
	}
	line = strings.TrimSpace(line)
	// Strip Markdown emphasis and heading markers.
	line = strings.Trim(line, "*# \t")
	if line == "" {
		return "Cluster"
	}
	return line
}

// navDocTitle is the nav_doc leaf's label, stored in title_kwd: the summary's
// first line (Python _clean_title/_fallback_title). One column serves both
// readers — nodeFromRow renders it in the tree, and NavHit.Name carries it to
// the model as the routed document's <summary> (tool_navigation.go) — so it must
// stay a CONTENT label; a file name here would tell the model nothing about the
// document.
func navDocTitle(summary string) string {
	return cleanTitle(fallbackTitle(summary))
}

// readableClusterName returns a readable yet unique nav-cluster key of the form
// "<title> <8-hex>" (mirroring Python dataset_nav._readable_cluster_name): the
// title keeps the node name human-readable, the short hash of the seed keeps the
// per-KB uniqueness that the tree keying relies on.
func readableClusterName(title, seed string) string {
	t := cleanTitle(title)
	if t == "" {
		t = "Cluster"
	}
	return t + " " + shortHash8(seed)
}

// llmCreateSummary builds a cluster's name + summary for a source text. The
// name is always run through readableClusterName, so it keeps the " <8-hex>"
// suffix that makes it unique per KB and addressable as the cluster key
// (parent_kwd / row id) — Python does the same in its callers
// (_readable_cluster_name(new_title, summary)). With an LLM the title part is
// the model's topic name; without one it is the summary's first line, so nav
// clusters stay human-readable instead of "cluster_<hash>".
func (s *NavService) llmCreateSummary(ctx context.Context, tenantID, text string) (name, summary string) {
	if s.llm != nil {
		n, sm, err := s.llm.CreateSummary(ctx, tenantID, text)
		switch {
		case err != nil:
			// Fall back to the deterministic name; the warning is the only signal
			// that the configured chat model could not be used.
			common.Warn("datasetnav: LLM cluster naming failed, using the deterministic name",
				zap.String("tenant_id", tenantID), zap.Error(err))
		case n != "":
			return readableClusterName(n, text), sm
		}
	}
	return readableClusterName(fallbackTitle(text), text), text
}

// appendDocToCluster appends a doc id to a cluster's doc_ids_kwd and bumps its
// doc_count_int. Implemented as a read-modify-write. vecCol names the engine
// vector column (q_<dim>_vec) so an overfull-cluster split can inherit a
// representative vector; pass "" when the caller has no known dimension.
func (s *NavService) appendDocToCluster(ctx context.Context, de engine.DocEngine, tenantID, kbID, clusterName, docID, vecCol, compileKind string) error {
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navClusterCondition(tenantID, kbID, clusterName),
		[]string{"doc_ids_kwd", "doc_count_int", "compile_kwd"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(chunks) == 0 {
		return nil
	}
	// Use firstStringSlice (not a []interface{} assertion): the engine may return
	// doc_ids_kwd as either []string or []interface{}, and a bare type assertion
	// would silently clear the field on a []string (review Critical).
	ids := make([]string, 0, 8)
	for _, d := range firstStringSlice(chunks[0]["doc_ids_kwd"]) {
		if d != docID {
			ids = append(ids, d)
		}
	}
	found := false
	for _, id := range ids {
		if id == docID {
			found = true
			break
		}
	}
	if !found {
		ids = append(ids, docID)
	}
	count := intValue(chunks[0]["doc_count_int"])
	if !found {
		count++
	}
	// The condition addresses the cluster by its row id, so no other row can be
	// caught by the update — neither a regular chunk that happens to carry a
	// similar title nor a second cluster whose readable name shares words with
	// this one. The read-modify-write here is expected to run under a per-dataset
	// lock held by the UpsertDoc caller; without it, concurrent appends to the
	// same cluster can lose updates.
	updates := map[string]interface{}{"doc_ids_kwd": ids, "doc_count_int": count, "scope_kwd": "dataset"}
	if kind := types.CompilationKind(chunks[0]); kind != "tree" && kind != "page_index" {
		updates["compile_kwd"] = compileKind
	}
	if err := de.UpdateChunks(ctx,
		navClusterCondition(tenantID, kbID, clusterName),
		updates,
		s.navIndexName(tenantID), kbID); err != nil {
		return err
	}
	// Rebalance only when the cluster is plausibly overfull: the cluster's own
	// doc count already exceeds the per-cluster cap, so a split is possible.
	// Skipping the children-search on every append avoids 2N extra engine
	// round-trips for a dataset compile (review Major). maybeSplitCluster still
	// re-checks both thresholds, so fanout-only splits via the direct call path
	// (tests, rebuild) are unaffected. A split failure aborts the batch.
	if count <= navMaxDocsPerCluster {
		return nil
	}
	return s.maybeSplitCluster(ctx, tenantID, kbID, clusterName, vecCol)
}

// deleteNavDoc deletes a nav_doc row by doc_id, returning the doc's parent
// cluster name (if any) so RemoveDoc can run cascade cleanup. It reads the
// parent_kwd of the nav_doc before deleting so the emptied cluster can be pruned.
func (s *NavService) deleteNavDoc(ctx context.Context, tenantID, kbID, docID string) (string, error) {
	de, err := s.docEngine()
	if err != nil {
		return "", err
	}
	// Restrict the delete to nav_doc rows only (review issue 8): a nav_cluster
	// row must never be matched by a doc_id filter.
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navFilter(map[string]interface{}{"type_kwd": []string{"nav_doc"}, "doc_id": []string{docID}}),
		[]string{"id", "parent_kwd"}, 0, 100, nil)
	if err != nil {
		return "", err
	}
	ids := make([]string, 0, len(chunks))
	var parent string
	for _, c := range chunks {
		if id, ok := c["id"].(string); ok {
			ids = append(ids, id)
		}
		if parent == "" {
			parent = firstStringValue(c["parent_kwd"])
		}
	}
	if len(ids) == 0 {
		return "", nil
	}
	if _, err := de.DeleteChunks(ctx, map[string]interface{}{"id": ids, "kb_id": kbID}, s.navIndexName(tenantID), kbID); err != nil {
		return "", err
	}
	return parent, nil
}

// RemoveDoc removes a document's nav_doc (if any) and then cascades: the doc is
// removed from the cluster(s) that list it in doc_ids_kwd (decrementing
// doc_count_int), and any cluster left empty (no docs, no children) is pruned
// upward (A3, mirroring Python _cleanup_empty_cluster). A doc that created a
// standalone cluster (no separate nav_doc row) is handled by the
// doc-in-cluster lookup below.
func (s *NavService) RemoveDoc(ctx context.Context, tenantID, kbID, docID string) error {
	parent, err := s.deleteNavDoc(ctx, tenantID, kbID, docID)
	if err != nil {
		return err
	}
	// Remove the doc from its parent cluster's doc_ids_kwd and bump the count.
	if parent != "" && parent != navRootParent {
		if err := s.removeDocFromCluster(ctx, tenantID, kbID, parent, docID); err != nil {
			return err
		}
	} else {
		// No separate nav_doc: the doc is a member of a cluster's doc_ids_kwd
		// (it created a standalone cluster, or lives under a cluster but the
		// nav_doc row is absent). Locate and decrement that cluster.
		cluster, err := s.findClusterContainingDoc(ctx, tenantID, kbID, docID)
		if err != nil {
			return err
		}
		if cluster != "" {
			if err := s.removeDocFromCluster(ctx, tenantID, kbID, cluster, docID); err != nil {
				return err
			}
			parent = cluster
		}
	}
	// Cascade cleanup of the emptied cluster (and its ancestors).
	return s.cleanupEmptyCluster(ctx, tenantID, kbID, parent)
}

// findClusterContainingDoc returns the title_kwd of the first nav_cluster whose
// doc_ids_kwd contains docID, or "" when none does.
func (s *NavService) findClusterContainingDoc(ctx context.Context, tenantID, kbID, docID string) (string, error) {
	de, err := s.docEngine()
	if err != nil {
		return "", err
	}
	// Page through clusters (review issue 19) so a KB with more than one page of
	// clusters does not hide the doc's cluster past the first page.
	const pageSize = 500
	for offset := 0; ; offset += pageSize {
		res, err := de.Search(ctx, &types.SearchRequest{
			IndexNames:   []string{s.navIndexName(tenantID)},
			KbIDs:        []string{kbID},
			SelectFields: []string{"title_kwd", "docnm_kwd", "doc_ids_kwd"},
			Filter:       map[string]interface{}{"type_kwd": "nav_cluster"},
			Offset:       offset,
			Limit:        pageSize,
		})
		if err != nil {
			return "", err
		}
		for _, row := range res.Chunks {
			for _, d := range firstStringSlice(row["doc_ids_kwd"]) {
				if d == docID {
					return navRowLabel(row), nil
				}
			}
		}
		if len(res.Chunks) < pageSize {
			return "", nil
		}
	}
}

// removeDocFromCluster removes a doc id from a cluster's doc_ids_kwd and
// decrements its doc_count_int (read-modify-write). It is the inverse of
// appendDocToCluster.
func (s *NavService) removeDocFromCluster(ctx context.Context, tenantID, kbID, clusterName, docID string) error {
	de, err := s.docEngine()
	if err != nil {
		return err
	}
	chunks, _, err := s.navSearch(ctx, tenantID, kbID,
		navClusterCondition(tenantID, kbID, clusterName),
		[]string{"doc_ids_kwd", "doc_count_int"}, 0, 1, nil)
	if err != nil {
		return err
	}
	if len(chunks) == 0 {
		return nil
	}
	// Use firstStringSlice (not a []interface{} assertion): the engine may return
	// doc_ids_kwd as either []string or []interface{}, and a bare type assertion
	// would silently clear the field on a []string (review Critical).
	ids := make([]string, 0, 8)
	for _, d := range firstStringSlice(chunks[0]["doc_ids_kwd"]) {
		if d != docID {
			ids = append(ids, d)
		}
	}
	count := intValue(chunks[0]["doc_count_int"])
	if count > 0 {
		count--
	}
	return de.UpdateChunks(ctx,
		navClusterCondition(tenantID, kbID, clusterName),
		map[string]interface{}{"doc_ids_kwd": ids, "doc_count_int": count},
		s.navIndexName(tenantID), kbID)
}

// f32ToF64Slice converts a float32 vector to float64.
func f32ToF64Slice(v []float32) []float64 {
	out := make([]float64, len(v))
	for i, x := range v {
		out[i] = float64(x)
	}
	return out
}

// payloadJSONNav marshals a nav payload map into the content_with_weight JSON.
func payloadJSONNav(v map[string]interface{}) string {
	b, err := json.Marshal(v)
	if err != nil {
		return "{}"
	}
	return string(b)
}

// truncateString caps s to n runes (not bytes).
func truncateString(s string, n int) string {
	runes := []rune(s)
	if len(runes) <= n {
		return s
	}
	return string(runes[:n])
}

// shortHash8 is a stable 8-char hash suffix for readable nav names.
func shortHash8(s string) string {
	return contentHash8(s)
}

// contentHash8 is a stable 8-char hash.
func contentHash8(s string) string {
	h := uint32(2166136261)
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= 16777619
	}
	return fmt.Sprintf("%08x", h)
}

// firstStringValue returns the first string value of a (possibly list-wrapped)
// engine field.
func firstStringValue(v interface{}) string {
	switch tv := v.(type) {
	case string:
		return tv
	case []string:
		if len(tv) > 0 {
			return tv[0]
		}
	case []interface{}:
		if len(tv) > 0 {
			if s, ok := tv[0].(string); ok {
				return s
			}
		}
	}
	return ""
}

// firstStringSlice returns v as a []string, unwrapping a []interface{} whose
// elements are all strings; returns nil for any other type.
func firstStringSlice(v interface{}) []string {
	switch s := v.(type) {
	case []string:
		return s
	case []interface{}:
		out := make([]string, 0, len(s))
		for _, x := range s {
			if str, ok := x.(string); ok {
				out = append(out, str)
			}
		}
		return out
	}
	return nil
}

// appendUnique appends only values not already present, preserving order.
func appendUnique(dst, values []string) []string {
	seen := make(map[string]bool, len(dst)+len(values))
	for _, v := range dst {
		seen[v] = true
	}
	for _, v := range values {
		if v == "" || seen[v] {
			continue
		}
		seen[v] = true
		dst = append(dst, v)
	}
	return dst
}

func intValue(v interface{}) int {
	switch tv := v.(type) {
	case float64:
		return int(tv)
	case float32:
		return int(tv)
	case int:
		return tv
	case int64:
		return int(tv)
	case []float64:
		if len(tv) > 0 {
			return int(tv[0])
		}
	case []interface{}:
		if len(tv) > 0 {
			switch n := tv[0].(type) {
			case float64:
				return int(n)
			case int:
				return n
			}
		}
	}
	return 0
}